首页 > 代码库 > 一步一步写算法（之线性结构的处理）

一步一步写算法（之线性结构的处理）

2024-08-07 08:48:03   215人阅读

原文: 一步一步写算法（之线性结构的处理）

【 声明：版权所有，欢迎转载，请勿用于商业用途。  联系信箱：feixiaoxing @163.com】


    我们知道，在内存中的空间都是连续的。也就是说，0x00000001下面的地址必然是0x00000002。所以，空间上是不会出现地址的突变的。那什么数据结构类型是连续内部空间呢，其实就是数组，当然也可以是堆。数组有很多优势，它可以在一段连续空间内保存相同类型的数据，并且对这些数据进行管理。所以从这个意义上说，掌握了数组才能说明你数据结构入门了。

    那么，在实际开发中，我们对线性结构应该注意些什么呢？我个人的观点：

    （1）数组的资源是有限的，必须确定资源的范围

    （2）数组中资源的申请和释放必须一一对应，否则很容易造成资源泄漏的现象

    （3）数组中的注意事项同样应用于堆分配的连续内存资源空间中

    下面是自己设计的一个int分配的小程序，大家可以一起尝试一下：

    a）设计内存节点的数据形式

typedef struct _DATA_NODE{	int* pData;	char* pFlag;	int num;}DATA_NODE;#define STATUS int#define TRUE 1#define FALSE 0
    b）创建内存节点

DATA_NODE* malloc_node(int number){	DATA_NODE* pDataNode = NULL;	if(0 == number)		return NULL;	pDataNode = (DATA_NODE*) malloc(sizeof(DATA_NODE));	assert(NULL != pDataNode);	memset(pDataNode, 0, sizeof(DATA_NODE));	pDataNode->pData = http://www.mamicode.com/(int*)malloc(sizeof(int) * number);>    c） 删除内存节点
STATUS free_node(const DATA_NODE* pDataNode){	if(NULL == pDataNode)		return FALSE;	assert(NULL != pDataNode ->pData);	assert(NULL != pDataNode-> pFlag);	assert(0 != pDataNode);	free(pDataNode->pFlag);	free(pDataNode->pData);	free((void*)pDataNode);	return TRUE;}
    d）判断当前是否还有内存可以分配
int check_if_data_exist(const DATA_NODE* pDataNode){	int number = pDataNode->num;	char* pFlag = pDataNode->pFlag;	unsigned char flag = 0;	int loop = 1;	while(loop <= number){		flag = pFlag[(loop + 7) >> 3 - 1] & (0x1 << ((loop + 7) % 8));		if(0 != flag){			return loop;		}		loop ++;	}	return -1;}
    e） 分配内存空间
int* alloca_data(const DATA_NODE* pDataNode){	int* pData = http://www.mamicode.com/NULL;>    f）回收内存空间
STATUS free_data(const DATA_NODE* pDataNode, const int* pData){	int pos = 0;	if(NULL == pDataNode || NULL == pData)		return FALSE;	if(pData < pDataNode->pData || pData > (pDataNode->pData + pDataNode->num))		return FALSE;	pos = (pData - pDataNode->pData) >> 3;	pDataNode->pFlag[(pos + 7) -1]  &= ~(0x1 << ((pos + 7) % 8));	return TRUE;}
    g）统计当前已经分配了多少DWORD空间
int count_free_space(const DATA_NODE* pDataNode){	int count = 0;	int loop = 1;	char flag = 0;	if(NULL == pDataNode)		return 0;	for(; loop <= pDataNode->num; loop++)	{		flag = pDataNode->pFlag[(loop + 7) >> 3 - 1] & (0x1 << ((loop + 7) % 8));		if(0 == flag){			count ++;		}	}		return count;}

   上面的代码只是一个示范，大家可以在这个基础之上加以改进，比如说：
    （1）修改成可以自由分配很多内存，注意需要同时修改flag的结构类型
    （2）修改成先到先得的内存分配类型
    （3）修改成最合适空间的内存分配类型
    （4）修改成debug类型的内存分配形式，每次分配和释放的时候都检查内存是否越界、是否没有成对运行，注意需要添加对应的判断函数

【预告： 下面一篇博客介绍队列线性表】

一步一步写算法（之线性结构的处理）


联系
我们