C語言實現帶頭雙向環形鏈表
雙向循環鏈表
上一次我們講瞭單向無頭非循環鏈表的實現,單向無頭非循環鏈表的特點是:結構簡單,一般不會單獨用來存數據。實際中更多是作為其他數據結構的子結構。而帶頭雙向循環鏈表則恰恰與無頭單向非循環鏈表相反,它的結構最復雜,一般用來單獨存儲數據。這個結構雖然復雜,但是使用單嗎實現後會發現,這個結構用起來很簡單。
結構示意圖
帶頭雙向循環鏈表在邏輯上大概就是這樣的一個樣子,鏈表的最後一個節點的後繼指向的是頭結點。而頭結點的前驅則是指向鏈表的最後一個結點。所以,一個空的帶頭雙向循環鏈表的邏輯結構應該是這樣的:
它的前驅和後繼都是指向的頭結點。
實現帶頭雙向循環鏈表
#pragma once #include<stdio.h> #include<stdlib.h> #include<assert.h> typedef int LTDataType; // 定義鏈表的節點 typedef struct ListNode { LTDataType data; struct ListNode* prev; struct ListNode* next; }LTNode; // 創建返回鏈表的頭結點. LTNode* ListCreate(); // 雙向鏈表銷毀 void ListDestory(LTNode* pHead); // 雙向鏈表打印 void ListPrint(LTNode* pHead); // 雙向鏈表尾插 void ListPushBack(LTNode* pHead, LTDataType x); // 雙向鏈表尾刪 void ListPopBack(LTNode* pHead); // 雙向鏈表頭插 void ListPushFront(LTNode* pHead, LTDataType x); // 雙向鏈表頭刪 void ListPopFront(LTNode* pHead); // 雙向鏈表查找 LTNode* ListFind(LTNode* pHead, LTDataType x); // 雙向鏈表在pos的前面進行插入 void ListInsert(LTNode* pos, LTDataType x); // 雙向鏈表刪除pos位置的節點 void ListErase(LTNode* pos);
首先我們得定義一個結點的結構,它由前驅指針、後繼指針和數據這三部分組成。
// 定義鏈表的節點 typedef struct ListNode { LTDataType data; struct ListNode* prev; struct ListNode* next; }LTNode;
定義好之後,我們要創建一個頭結點。我們把創建頭結點的過程也封裝成一個函數,這個函數的返回值就是頭結點的指針。我們在使用的時候就創建一個變量來接收這個指針。
**註意:**頭結點創建的時候,它的data部分是不存數據的,它的前驅和後繼都是指向它自己
LTNode* ListCreate() { LTNode* head = (LTNode*)malloc(sizeof(LTNode)); head->next = head; head->prev = head; return head; } // 在main函數中是這樣使用的 int main(){ LTNode* head = ListCreate(); return 0; }
創建好頭結點之後就可以向鏈表中插入數據瞭,首先實現尾插,就是在鏈表的最後一個結點後面再插入一個結點。然後就是頭插法,頭插法就是在頭結點的後面插入一個新節點。
// 雙向鏈表尾插 void ListPushBack(LTNode* pHead, LTDataType x) { assert(pHead); LTNode* newnode = (LTNode*)malloc(sizeof(LTNode)); // 創建的新節點 newnode->data = x; // 將新節點插入到鏈表中 LTNode* prev = pHead->prev; prev->next = newnode; newnode->prev = prev; newnode->next = pHead; pHead->prev = newnode; }
// 雙向鏈表頭插 void ListPushFront(LTNode* pHead, LTDataType x) { assert(pHead); // 創建新節點 LTNode* newnode = (LTNode*)malloc(sizeof(LTNode)); newnode->data = x; //將新節點插入鏈表 LTNode* next = pHead->next; pHead->next = newnode; newnode->prev = pHead; newnode->next = next; next->prev = newnode; }
有插入數據就有刪除數據,同樣的刪除數據也有兩種,一個是頭刪一個是尾刪。頭刪就是將頭結點的next指向的那個結點刪除。尾刪,就是將最後一個節點刪掉。帶頭雙向循環鏈表,在我們尾刪的時候就很方便。因為頭結點的前驅指向的節點就是鏈表的最後一個節點,就不需要我們再遍歷鏈表去找最後一個節點的地址。
// 雙向鏈表頭刪 void ListPopFront(LTNode* pHead) { assert(pHead); assert(pHead->next != pHead); // 定義一個臨時變量來保存我們要刪掉的節點的位置 LTNode* popnode = pHead->next; // 將要刪除節點的鏈都斷掉 LTNode* next = popnode->next; pHead->next = popnode->next; next->prev = pHead; // free掉那個節點 free(popnode); popnode = NULL; }
// 雙向鏈表尾刪 void ListPopBack(LTNode* pHead) { assert(pHead); assert(pHead->prev != pHead); LTNode* popnode = pHead->prev; LTNode* prev = popnode->prev; prev->next = pHead; pHead->prev = prev; free(popnode); popnode = NULL; }
在實現瞭增加和刪除節點之後,我們就實現查找結點。方法也是遍歷整個鏈表,如果有一個節點的data的值和x相同就返回這個節點的地址。如果沒找到就返回空。
// 雙向鏈表查找 LTNode* ListFind(LTNode* pHead, LTDataType x) { if (pHead->next == pHead) { return NULL; } LTNode* find = pHead->next; while (find != pHead) { if (find->data == x) { return find; } find = find->next; } return NULL; }
實現隨機插入數據,這裡的隨機插入的意思是,我們把新節點插入到我們指定的節點的後面一個或前面一個。這個節點可以是在鏈表的任何一個地方。我們這個函數會傳入一個節點的地址,通過那個地址可以找到要出入的那個節點,把新節點連接到那個節點後面就可以瞭
// 雙向鏈表刪除pos位置的節點 void ListErase(LTNode* pos) { assert(pos); LTNode* prev = pos->prev; LTNode* next = pos->next; prev->next = next; next->prev = prev; free(pos); pos = NULL; }
打印雙向循環鏈表,也是通過遍歷鏈表來打印
// 雙向鏈表打印 void ListPrint(LTNode* pHead) { assert(pHead); LTNode* tail = pHead->next; while (tail != pHead) { printf("%d->", tail->data); tail = tail->next; } }
在我們使用完鏈表後,要記得銷毀鏈表,防止內存泄漏
// 雙向鏈表銷毀 void ListDestory(LTNode* pHead) { assert(pHead); LTNode* tail = pHead->next; while (tail != pHead) { LTNode* tmp = tail->next; free(tail); tail = tmp; } free(pHead); pHead = NULL; }
以上就是本文的全部內容,希望對大傢的學習有所幫助,也希望大傢多多支持WalkonNet。