一般情況下,我們使用鏈表無非就是在鏈表結點中保存該鏈表中下一個元素的指針.如果為了刪除方便,可能需要保存前一個元素的指針,也就是雙向鏈表,這樣在刪除一個結點的時候就可以很快的定位到前面和后面的結點,并且改變它們相應的指向.在這些操作里面,指向鏈表元素的指針無疑是最關鍵的數據.
考慮這樣一個問題,如果兩個進程進行通信,A進程負責管理鏈表,B進程向A進程發出分配或者刪除鏈表元素的請求.這種情況下,像上面所描述的那樣A進程直接向B進程返回鏈表元素的指針是不能做到的了,很自然的,可以想到返回另一個key標示該鏈表元素.但是,當需要查找或者刪除該鏈表元素的時候,就不能像上面那樣馬上定位到鏈表元素的位置了,需要遍歷整個鏈表.原來常量級時間復雜度的算法,在使用情形變換了之后變成了O(n)級別的復雜度.
可以找到別的辦法來解決這個問題.第一可以返回一個key標示該鏈表元素,第二保證了時間的復雜度,在這里需要定義一種新的數據結構和算法來解決這個問題.
首先,我們使用一個數組,數組中的元素是指向鏈表元素的指針,而指針的索引則是每個鏈表元素的id,這樣,通過id就可以馬上定位到對應的鏈表元素.
但是這里又會出現另一個問題,該id是從零開始的,假如在一段時間之后,需要分配一個新的鏈表元素,如何知道數組中的哪個位置是可以分配的?在這里,使用了一個整型數據的數組,數組中的每個元素是該id對應的鏈表元素在鏈表中下一個結點的id(有點拗口).我們使用兩個鏈表頭,一個將已經使用的鏈表元素id連接起來,另一個則將未使用的鏈表元素id連接起來.于是,在程序初始化的時候,未使用的鏈表中保存了所有的id,而已經使用的鏈表為空.每次分配了一個新的鏈表元素,將它的id放在使用鏈表的最開始;而每次釋放一個鏈表元素,將它的id放到未使用的鏈表頭部.
同時,改變原先鏈表元素的定義,在該結構體中,保存的不再是指針,而是鏈表中前一個元素的數組索引id.而它的下一個元素id則保存在上面的那個數組中.
如果上面我的解釋還不夠明白,可以看看下面的代碼:
#include <stdio.h>
#define LIST_NODE_NULL -1
#define ARRAY_SIZE 200
/* 鏈表元素定義 */
typedef struct list_node
{
int prev; /* 下一個鏈表元素在list_array中的id */
}list_node;
/* 存放鏈表元素指針的數組 */
list_node* list_array[ARRAY_SIZE];
/* 未使用鏈表的頭結點id */
int top_of_free;
/* 已使用鏈表的頭結點id */
int top_of_used;
/* 保存鏈表下一個元素結點id的鏈表 */
int next_list[ARRAY_SIZE];
void init_list()
{
int i;
for (i = 0; i < ARRAY_SIZE; ++i)
{
list_array[i] = NULL;
/* 初始時,next_list中每個結點的值都是下一個id */
next_list[i] = i + 1;
}
/* 最后一個結點是空 */
next_list[i - 1] = LIST_NODE_NULL;
top_of_free = 0;
top_of_used = LIST_NODE_NULL;
}
int alloc_list_node()
{
int id;
/* 從未使用鏈表頭部取出一個id */
id = top_of_free;
if (LIST_NODE_NULL == id)
{
return LIST_NODE_NULL;
}
/* 未使用鏈表頭結點往下走一步 */
top_of_free = next_list[top_of_free];
if (NULL == list_array[id])
{
list_array[id] = (list_node*)malloc(sizeof(list_node));
if (NULL == list_array[id])
{
return LIST_NODE_NULL;
}
}
if (LIST_NODE_NULL == top_of_used)
{
next_list[id] = top_of_used;
top_of_used = id;
}
else
{
/* 修改prev和next */
list_array[top_of_used]->prev = id;
list_array[id]->prev = LIST_NODE_NULL;
next_list[id] = top_of_used;
top_of_used = id;
}
return id;
}
void free_list_node(int id)
{
int prev, next;
prev = list_array[id]->prev;
next = next_list[id];
/* 修改next和prev */
if (LIST_NODE_NULL != prev)
{
next_list[prev] = next_list[id];
}
if (LIST_NODE_NULL != next && NULL != list_array[next])
{
list_array[next]->prev = prev;
}
if (id == top_of_used)
{
top_of_used = next_list[id];
}
/* 將鏈表id返回到free鏈表頭部并且修改free鏈表頭結點 */
next_list[id] = top_of_free;
top_of_free = id;
}
int main()
{
int id;
init_list();
id = alloc_list_node();
free_list_node(id);
return 0;
}
這個想法很巧妙,有效的避免了查找和刪除數組元素帶來的開銷.我不知道具體的出處在哪里,如果您知道,勞煩告訴我一聲:)