1、雙向循環(huán)鏈表結(jié)點(diǎn)定義和函數(shù)聲明

雙向循環(huán)鏈表結(jié)點(diǎn)內(nèi)部有2個(gè)指針prev和next分別指向前后的結(jié)點(diǎn)，結(jié)點(diǎn)定義代碼如下：

typedefstructdlist{ intdata; structdlist*next; structdlist*prev; }dlist_t;

現(xiàn)在我們聲明一些雙向循環(huán)鏈表操作函數(shù)，代碼如下：

externdlist_t *new_dlist_node(intdata); //新建一個(gè)結(jié)點(diǎn) externdlist_t *dlist_add(dlist_t*list, intdata); //插入一個(gè)結(jié)點(diǎn) externdlist_t *dlist_delete(dlist_t*list, intindex); //刪除索引對(duì)應(yīng)的結(jié)點(diǎn)（索引從0開始） externdlist_t *dlist_index_of(dlist_t*list, intindex); //查找索引對(duì)應(yīng)的結(jié)點(diǎn) externvoiddlist_destroy(dlist_t*list); //銷毀雙向循環(huán)鏈表 externvoiddlist_print(dlist_t*list); //打印鏈表數(shù)據(jù)

可以看到很多函數(shù)都會(huì)返回一個(gè)dlist_t類型的指針，其實(shí)這是頭結(jié)點(diǎn)。很多時(shí)候?yàn)榱藭鴮懛奖阄覀儠?huì)采用typedef定義自己的數(shù)據(jù)類型，結(jié)點(diǎn)定義里為什么next和prev指針可以那樣寫，參考我上一篇文章，后面會(huì)大量這樣使用。

2、雙向循環(huán)鏈表函數(shù)實(shí)現(xiàn)

為了更方便釋放一個(gè)結(jié)點(diǎn)內(nèi)存，我們定義了一個(gè)文件作用域靜態(tài)函數(shù)free_dlist_node。

voidfree_dlist_node(dlist_t*node){ if(node == NULL){ return; } node->next = NULL; node->prev = NULL; free(node); node = NULL; }

該函數(shù)只負(fù)責(zé)釋放內(nèi)存的操作。

新建鏈表結(jié)點(diǎn)

dlist_t*new_dlist_node(intdata){ dlist_t*node = (dlist_t*)malloc(sizeof(dlist_t)); if(node == NULL){ returnNULL; } node->data = data; node->next = node; node->prev = node; returnnode; }

這里我們主要注意一點(diǎn)就是新建立的結(jié)點(diǎn)next和prev指針會(huì)初始化為指向自身，事實(shí)上雙向循環(huán)鏈表頭結(jié)點(diǎn)必須這樣初始化才能更好的利用雙向循環(huán)鏈表特性執(zhí)行插入、刪除和查詢等操作。

插入結(jié)點(diǎn)

dlist_t *dlist_add(dlist_t *list, int data){ if(list== NULL){ returnNULL; } //新建一個(gè)結(jié)點(diǎn) dlist_t *node = new_dlist_node(data); if(node == NULL){ returnlist; } //將結(jié)點(diǎn)插入雙向循環(huán)鏈表 list->prev->next = node; //最后的結(jié)點(diǎn)next指針指向node node->next = list; //node的next指針指向頭結(jié)點(diǎn) node->prev = list->prev; //node的prev指針指向原尾結(jié)點(diǎn) list->prev = node; //頭結(jié)點(diǎn)的prev指針指向新尾結(jié)點(diǎn) returnlist; }

這里list是傳入的頭結(jié)點(diǎn)，我們采用尾插法插入一個(gè)結(jié)點(diǎn)，最后返回頭結(jié)點(diǎn)。這里需要注意：每次插入結(jié)點(diǎn)都要更新頭結(jié)點(diǎn)的prev指針。

刪除指定位置的結(jié)點(diǎn)

dlist_t *dlist_delete(dlist_t *list, int index){ if(list== NULL|| index < 0){ ????????return?list; ????} ????dlist_t *head = list; ????int list_index = 0; ????//刪除鏈表頭結(jié)點(diǎn) ????if(index == 0){ ????????//鏈表只有一個(gè)結(jié)點(diǎn) ????????if(head == list->next){ free_dlist_node(list); list= NULL; returnNULL; }else{ //鏈表有大于1個(gè)結(jié)點(diǎn) head = head->next; //頭結(jié)點(diǎn)往后移一個(gè) head->prev = list->prev; //頭結(jié)點(diǎn)的prev指向尾部結(jié)點(diǎn) list->prev->next = head; //尾部結(jié)點(diǎn)的next指針指向頭結(jié)點(diǎn) free_dlist_node(list); //釋放結(jié)點(diǎn)內(nèi)存 returnhead; } } list= list->next; list_index++; //查詢目標(biāo)結(jié)點(diǎn)，通過檢查當(dāng)前結(jié)點(diǎn)是否是頭結(jié)點(diǎn)判斷是否已經(jīng)把雙線循環(huán)鏈表遍歷了一遍 while(list_index < index && head != list){ ????????list?= list->next; list_index++; } //沒有找到即將刪除的結(jié)點(diǎn) if(head == list){ returnhead; } //找到即將刪除的結(jié)點(diǎn) else{ list->prev->next = list->next; //目標(biāo)結(jié)點(diǎn)的上一個(gè)結(jié)點(diǎn)的next指針指向目標(biāo)結(jié)點(diǎn)的下一個(gè)結(jié)點(diǎn) list->next->prev = list->prev; //目標(biāo)結(jié)點(diǎn)的下一個(gè)結(jié)點(diǎn)的prev指針指向目標(biāo)結(jié)點(diǎn)的上一個(gè)結(jié)點(diǎn) free_dlist_node(list); //釋放結(jié)點(diǎn)內(nèi)存 returnhead; //返回頭結(jié)點(diǎn) } }

刪除結(jié)點(diǎn)一定要注意：

判斷被刪除的結(jié)點(diǎn)是否是頭結(jié)點(diǎn)

指定的位置是否超出了鏈表的長度。

查找指定位置的結(jié)點(diǎn)

dlist_t*dlist_index_of(dlist_t*list, intindex){ if(list== NULL|| index < 0){ ????????return?NULL; ????} ????//如果想要獲取頭結(jié)點(diǎn)，則直接返回頭結(jié)點(diǎn) ????if(index == 0){ ????????return?list; ????} ????dlist_t?*head = list; ????list?= list->next; intlist_index = 1; //遍歷鏈表查找指定的索引，通過檢查當(dāng)前結(jié)點(diǎn)是否等于頭結(jié)點(diǎn)判斷是否已遍歷完畢 while(list_index < index && list?!= head){ ????????list_index++; ????????list?= list->next; } //沒有找到索引對(duì)應(yīng)的結(jié)點(diǎn) if(list== head){ returnNULL; } //找到了索引對(duì)應(yīng)的結(jié)點(diǎn) returnlist; }

查找指定位置結(jié)點(diǎn)要注意幾個(gè)地方：

是否是頭結(jié)點(diǎn)

是否超出了鏈表長度

銷毀鏈表

void dlist_destroy(dlist_t *list){ if(list== NULL){ return; } //如果只有一個(gè)結(jié)點(diǎn) if(list->next == list){ free_dlist_node(list); return; } dlist_t *temp = list; list= list->next; while(list!= temp){ list= list->next; //遍歷下一個(gè)結(jié)點(diǎn) temp->prev->next = list; list->prev = temp->prev; temp->next = NULL; temp->prev = NULL; free(temp); temp = list; } free_dlist_node(list); }

打印鏈表數(shù)據(jù)

voiddlist_print(dlist_t*list){ if(list== NULL){ return; } dlist_t*head = list; printf("%d, ", list->data); list= list->next; while(list!= head){ printf("%d, ", list->data); list= list->next; } printf(" "); }

最后我們寫個(gè)小程序驗(yàn)證一下雙向循環(huán)鏈表函數(shù)實(shí)現(xiàn)是否正確。

#include #include"dlist.h" intmain(){ dlist_t*list= new_dlist_node(2); inti = 0; for(i = 0; i < 7; i++){ ????????list?= dlist_add(list, 3?+ i); ????} ????printf("打印未處理過的完整鏈表 "); ????dlist_print(list); ????list?= dlist_delete(list, 0); //刪除第一個(gè)結(jié)點(diǎn) ????list?= dlist_delete(list, 3); //刪除第四個(gè)結(jié)點(diǎn) ????printf("打印刪除2個(gè)結(jié)點(diǎn)后的鏈表 "); ????dlist_print(list); ????dlist_t?*node = dlist_index_of(list, 2); ????printf("第3個(gè)結(jié)點(diǎn)是：%d ", node->data); printf("銷毀鏈表 "); dlist_destroy(list); list= NULL; return0; }

編譯運(yùn)行輸出：

打印未處理過的完整鏈表 2, 3, 4, 5, 6, 7, 8, 9, 打印刪除2個(gè)結(jié)點(diǎn)后的鏈表 3, 4, 5, 7, 8, 9, 第3個(gè)結(jié)點(diǎn)是：5 銷毀鏈表

驗(yàn)證完全正確。

責(zé)任編輯：lq6