我們知道，在內(nèi)存中的空間都是連續(xù)的。也就是說，0x00000001下面的地址必然是0x00000002。所以，空間上是不會出現(xiàn)地址的突變的。那什么數(shù)據(jù)結(jié)構(gòu)類型是連續(xù)內(nèi)部空間呢，其實就是數(shù)組，當然也可以是堆。數(shù)組有很多優(yōu)勢，它可以在一段連續(xù)空間內(nèi)保存相同類型的數(shù)據(jù)，并且對這些數(shù)據(jù)進行管理。所以從這個意義上說，掌握了數(shù)組才能說明你數(shù)據(jù)結(jié)構(gòu)入門了。

那么，在實際開發(fā)中，我們對線性結(jié)構(gòu)應該注意些什么呢？我個人的觀點：

（1）數(shù)組的資源是有限的，必須確定資源的范圍

（2）數(shù)組中資源的申請和釋放必須一一對應，否則很容易造成資源泄漏的現(xiàn)象

（3）數(shù)組中的注意事項同樣應用于堆分配的連續(xù)內(nèi)存資源空間中

下面是自己設計的一個int分配的小程序，大家可以一起嘗試一下：

a）設計內(nèi)存節(jié)點的數(shù)據(jù)形式

typedef struct _DATA_NODE
{
    int* pData;
    char* pFlag;
    int num;
}DATA_NODE;

#define STATUS int
#define TRUE 1
#define FALSE 0

b）創(chuàng)建內(nèi)存節(jié)點

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） 刪除內(nèi)存節(jié)點

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）判斷當前是否還有內(nèi)存可以分配

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） 分配內(nèi)存空間

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）回收內(nèi)存空間

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）統(tǒng)計當前已經(jīng)分配了多少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）修改成可以自由分配很多內(nèi)存，注意需要同時修改flag的結(jié)構(gòu)類型

（2）修改成先到先得的內(nèi)存分配類型

（3）修改成最合適空間的內(nèi)存分配類型

（4）修改成debug類型的內(nèi)存分配形式，每次分配和釋放的時候都檢查內(nèi)存是否越界、是否沒有成對運行，注意需要添加對應的判斷函數(shù)