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