首页 > 程序开发 > 软件开发 > C语言 >

一步一步写算法(之线性结构的处理)

2011-10-23

【 声明:版权所有,欢迎转载,请勿用于商业用途。 联系信箱:feixiaoxing @163.com】 我们知道,在内存中的空间都是连续的。也就是说,0x00000001下面的地址必然是0x00000002。所以,空间上是不会出现地址的...

【 声明:版权所有,欢迎转载,请勿用于商业用途。 联系信箱: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

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 = (int*)malloc(sizeof(int) * number);

if(NULL == pDataNode->pData){

free(pDataNode);

return NULL;

}

pDataNode->pFlag = (char*) malloc( (number + 7) >> 3);

if(NULL == pDataNode->pFlag){

free(pDataNode->pData);

free(pDataNode);

return NULL;

}

memset(pDataNode->pData, 0, sizeof(int) * number);

memset(pDataNode->pFlag, 0, (number + 7) >> 3);

pDataNode->num = number;

return pDataNode;

}

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 = (int*)malloc(sizeof(int) * number);

if(NULL == pDataNode->pData){

free(pDataNode);

return NULL;

}

pDataNode->pFlag = (char*) malloc( (number + 7) >> 3);

if(NULL == pDataNode->pFlag){

free(pDataNode->pData);

free(pDataNode);

return NULL;

}

memset(pDataNode->pData, 0, sizeof(int) * number);

memset(pDataNode->pFlag, 0, (number + 7) >> 3);

pDataNode->num = number;

return pDataNode;

} 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;

}

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;

}

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 = NULL;

int pos;

if(NULL == pDataNode)

return NULL;

if(-1 == (pos = check_if_data_exist(pDataNode)))

return NULL;

pDataNode->pFlag[(pos + 7) >> 3 - 1] |= 0x1 << ((pos + 7)% 8);

return pDataNode->pData + (pos - 1);

}

int* alloca_data(const DATA_NODE* pDataNode)

{

int* pData = NULL;

int pos;

if(NULL == pDataNode)

return NULL;

if(-1 == (pos = check_if_data_exist(pDataNode)))

return NULL;

pDataNode->pFlag[(pos + 7) >> 3 - 1] |= 0x1 << ((pos + 7)% 8);

return pDataNode->pData + (pos - 1);

} 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;

}

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;

}

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类型的内存分配形式,每次分配和释放的时候都检查内存是否越界、是否没有成对运行,注意需要添加对应的判断函数

相关文章
最新文章
热点推荐