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

 

【 声明：版权所有，欢迎转载，请勿用于商业用途。  联系信箱：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类型的内存分配形式，每次分配和释放的时候都检查内存是否越界、是否没有成对运行，注意需要添加对应的判断函数