1、雙向循環鏈表結點定義和函數聲明

雙向循環鏈表結點內部有2個指針prev和next分別指向前后的結點，結點定義代碼如下：

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

現在我們聲明一些雙向循環鏈表操作函數，代碼如下：

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

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

2、雙向循環鏈表函數實現

為了更方便釋放一個結點內存，我們定義了一個文件作用域靜態函數free_dlist_node。

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

該函數只負責釋放內存的操作。

新建鏈表結點

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

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

插入結點

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

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

刪除指定位置的結點

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

刪除結點一定要注意：

判斷被刪除的結點是否是頭結點

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

查找指定位置的結點

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

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

是否是頭結點

是否超出了鏈表長度

銷毀鏈表

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

打印鏈表數據

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(" "); }

最后我們寫個小程序驗證一下雙向循環鏈表函數實現是否正確。

#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); //刪除第一個結點 ????list?= dlist_delete(list, 3); //刪除第四個結點 ????printf("打印刪除2個結點后的鏈表 "); ????dlist_print(list); ????dlist_t?*node = dlist_index_of(list, 2); ????printf("第3個結點是：%d ", node->data); printf("銷毀鏈表 "); dlist_destroy(list); list= NULL; return0; }

編譯運行輸出：

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

驗證完全正確。

責任編輯：lq6