【 聲明：版權所有，歡迎轉載，請勿用於商業用途。 聯系信箱：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類型的內存分配形式，每次分配和釋放的時候都檢查內存是否越界、是否沒有成對運行，注意需要添加對應的判斷函數
