雙向循環(huán)鏈表函數(shù)是什么？如何去實現(xiàn)它？

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

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

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

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

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

可以看到很多函數(shù)都會返回一個dlist_t類型的指針，其實這是頭結(jié)點。很多時候為了書寫方便我們會采用typedef定義自己的數(shù)據(jù)類型，結(jié)點定義里為什么next和prev指針可以那樣寫，參考我上一篇文章，后面會大量這樣使用。

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

為了更方便釋放一個結(jié)點內(nèi)存，我們定義了一個文件作用域靜態(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é)點

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; }

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

插入結(jié)點

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

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

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

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

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

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

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

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

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

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

是否是頭結(jié)點

是否超出了鏈表長度

銷毀鏈表

void dlist_destroy(dlist_t *list){ if(list== NULL){ return; } //如果只有一個結(jié)點 if(list->next == list){ free_dlist_node(list); return; } dlist_t *temp = list; list= list->next; while(list!= temp){ list= list->next; //遍歷下一個結(jié)點 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(" "); }

最后我們寫個小程序驗證一下雙向循環(huán)鏈表函數(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); //刪除第一個結(jié)點 ????list?= dlist_delete(list, 3); //刪除第四個結(jié)點 ????printf("打印刪除2個結(jié)點后的鏈表 "); ????dlist_print(list); ????dlist_t?*node = dlist_index_of(list, 2); ????printf("第3個結(jié)點是：%d ", node->data); printf("銷毀鏈表 "); dlist_destroy(list); list= NULL; return0; }

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

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

驗證完全正確。

責(zé)任編輯：lq6