C語言超詳細講解雙向帶頭循環(huán)鏈表
在上一篇所講述的單鏈表中,存在一些缺陷:
1、在進行尾插和尾刪時,需要遍歷鏈表找到尾結(jié)點
2、在進行中間插入和刪除時,也需要先遍歷鏈表找到前一個結(jié)點
對于這些缺陷,可以采用一種結(jié)構(gòu)更為復雜的鏈表 雙向帶頭循環(huán)鏈表
雙向帶頭循環(huán)鏈表結(jié)構(gòu)雖然復雜,但在鏈表的操作上帶來了很大的優(yōu)勢
一、雙向帶頭循環(huán)鏈表的結(jié)構(gòu)
//存儲數(shù)據(jù)的類型,這里以 int 來舉例 typedef int LTDataType; //結(jié)點的類型 typedef struct ListNode { LTDataType data; struct ListNode* prev; struct ListNode* next; }LTNode;
二、雙向帶頭循環(huán)鏈表的函數(shù)接口
1. 申請結(jié)點
在插入等操作時需要申請結(jié)點,為了避免麻煩重復的操作,這里將申請結(jié)點封裝為一個函數(shù)
申請結(jié)點函數(shù)如下:
LTNode* BuyLTNode(LTDataType x) { LTNode* newnode = (LTNode*)malloc(sizeof(LTNode)); if (newnode == NULL) { //開辟空間失敗,打印錯誤信息 perror("malloc"); //結(jié)束程序 exit(-1); } newnode->data = x; newnode->prev = newnode->next = NULL; return newnode; }
2. 初識化
在雙向帶頭循環(huán)鏈表中,即使沒有存儲數(shù)據(jù)也 至少會包含一個哨兵位的頭結(jié)點
初始化函數(shù)如下:
LTNode* InitLT() { //申請頭結(jié)點,頭結(jié)點的數(shù)據(jù)存什么無關(guān)緊要 LTNode* phead = BuyLTNode(-1); //改變指針指向,構(gòu)成循環(huán) phead->prev = phead->next = phead; return phead; }
3. 打印
為了驗證插入、刪除等得到的結(jié)果是否正確,提供打印函數(shù),這里數(shù)據(jù)類型以 int 為例,當讀者采用的類型不同時,自行更改函數(shù)即可
打印函數(shù)如下:
void LTPrint(LTNode* phead) { //鏈表不能為空 assert(phead); LTNode* cur = phead->next; printf("head->"); while (cur != phead) { printf("%d->", cur->data); cur = cur->next; } printf("head\n"); }
4. 尾插尾刪
尾插:在鏈表的最后一個結(jié)點之后插入結(jié)點
尾插函數(shù)如下:
void LTPushBack(LTNode* phead, LTDataType x) { //鏈表不能為空 assert(phead); LTNode* newnode = BuyLTNode(x); //找到尾結(jié)點 LTNode* tail = phead->prev; //改變指針指向 tail->next = newnode; newnode->prev = tail; newnode->next = phead; phead->prev = newnode; }
尾刪:刪除鏈表最后一個結(jié)點
尾刪函數(shù)如下:
void LTPopBack(LTNode* phead) { assert(phead); //鏈表不能為空 assert(phead->next != phead); //空鏈表不能刪 //找尾結(jié)點及尾結(jié)點的前一個結(jié)點 LTNode* tail = phead->prev; LTNode* tailPrev = tail->prev; //改變指針指向 tailPrev->next = phead; phead->prev = tailPrev; free(tail); }
5. 頭插頭刪
頭插: 在第一個結(jié)點之前插入新結(jié)點
頭插函數(shù)如下:
void LTPushFront(LTNode* phead, LTDataType x) { //鏈表不能為空 assert(phead); LTNode* newnode = BuyLTNode(x); //找到頭結(jié)點后的第一個結(jié)點 LTNode* first = phead->next; //改變指針指向 phead->next = newnode; newnode->prev = phead; newnode->next = first; first->prev = newnode; }
頭刪:刪除鏈表的第一個結(jié)點
頭刪函數(shù)如下:
void LTPopFront(LTNode* phead) { assert(phead); //鏈表不能為空 assert(phead->next != phead); //空鏈表不能刪 //找到頭結(jié)點后的第一個和第二個結(jié)點 LTNode* first = phead->next; LTNode* second = first->next; //改變指針指向 phead->next = second; second->prev = phead; free(first); }
6. 查找
查找:如果數(shù)據(jù)存在,返回該數(shù)據(jù)結(jié)點的指針,不存在返回 NULL
查找函數(shù)如下:
LTNode* LTFind(LTNode* phead, LTDataType x) { //鏈表不能為空 assert(phead); LTNode* cur = phead->next; while (cur != phead) { if (cur->data == x) return cur; cur = cur->next; } return NULL; }
7. 中間插入和刪除
中間插入:通過查找函數(shù) LTFind 獲得指向結(jié)點的指針 pos,在 pos 指向的 結(jié)點之前 插入結(jié)點
在 pos 之前插入結(jié)點函數(shù)如下:
void LTInsert(LTNode* pos, LTDataType x) { //pos 不能為空 assert(pos); LTNode* newnode = BuyLTNode(x); //找到 pos 的前一個結(jié)點 LTNode* posPrev = pos->prev; //改變指針指向 posPrev->next = newnode; newnode->prev = posPrev; newnode->next = pos; pos->prev = newnode; }
在調(diào)用中間插入函數(shù) LTInsert 時
- 如果在鏈表頭結(jié)點之前插入數(shù)據(jù),便和尾插函數(shù)的功能一樣
- 如果在鏈表頭結(jié)點之后插入數(shù)據(jù),便和頭插函數(shù)的功能一樣
因此在尾插和頭插函數(shù)的實現(xiàn)中可以直接調(diào)用中間插入函數(shù) LTInsert
尾插和頭插函數(shù)更改如下:
//尾插 void LTPushBack(LTNode* phead, LTDataType x) { //鏈表不能為空 assert(phead); LTInsert(phead, x); } //頭插 void LTPushFront(LTNode* phead, LTDataType x) { //鏈表不能為空 assert(phead); LTInsert(phead->next, x); }
中間刪除:通過查找函數(shù) LTFind 獲得指向結(jié)點的指針 pos,刪除 pos 指向的結(jié)點
刪除 pos 指向的結(jié)點函數(shù)如下:
void LTErase(LTNode* pos) { //pos 不能為空 assert(pos); //找到 pos 的前一個和后一個結(jié)點 LTNode* posPrev = pos->prev; LTNode* posNext = pos->next; //改變指針指向 posPrev->next = posNext; posNext->prev = posPrev; free(pos); }
在調(diào)用中間刪除函數(shù) LTErase 時
- 如果刪除鏈表頭結(jié)點的前一個結(jié)點,便和尾刪函數(shù)的功能一樣
- 如果刪除鏈表頭結(jié)點的后一個結(jié)點,便和頭刪函數(shù)的功能一樣
因此在尾刪和頭刪函數(shù)的實現(xiàn)中可以直接調(diào)用中間刪除函數(shù) LTErase
尾刪和頭刪函數(shù)更改如下:
//尾刪 void LTPopBack(LTNode* phead) { assert(phead); //鏈表不能為空 assert(phead->next != phead); //空鏈表不能刪 LTErase(phead->prev); } //頭刪 void LTPopFront(LTNode* phead) { assert(phead); //鏈表不能為空 assert(phead->next != phead); //空鏈表不能刪 LTErase(phead->next); }
8. 判空及求鏈表長度
判空:判斷鏈表是否為空
判空函數(shù)如下:
bool LTEmpty(LTNode* phead) { //鏈表不能為空 assert(phead); return phead->next == phead; }
鏈表長度:鏈表有效數(shù)據(jù)個數(shù)
鏈表長度函數(shù)如下:
size_t LTSize(LTNode* phead) { //鏈表不能為空 assert(phead); size_t size = 0; LTNode* cur = phead->next; while (cur != phead) { size++; cur = cur->next; } return size; }
9. 銷毀單鏈表
在鏈表中,存儲數(shù)據(jù)的結(jié)點是由自己開辟的,當不使用鏈表時,應將其銷毀
銷毀鏈表函數(shù)如下:
void LTDestroy(LTNode* phead) { //鏈表不能為空 assert(phead); LTNode* cur = phead->next; while (cur != phead) { LTNode* curNext = cur->next; free(cur); cur = curNext; } free(phead); }
到此這篇關(guān)于C語言超詳細講解雙向帶頭循環(huán)鏈表的文章就介紹到這了,更多相關(guān)C語言雙向帶頭循環(huán)鏈表內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家!
相關(guān)文章
C++入門教程詳解之命名空間、函數(shù)重載、缺省參數(shù)
這篇文章主要介紹了C++入門教程詳解之命名空間、函數(shù)重載、缺省參數(shù),本文通過實例代碼給大家介紹的非常詳細,對大家的學習或工作具有一定的參考借鑒價值,需要的朋友可以參考下2023-06-06CreateCompatibleDC()函數(shù)案例詳解
這篇文章主要介紹了CreateCompatibleDC()函數(shù)案例詳解,本篇文章通過簡要的案例,講解了該項技術(shù)的了解與使用,以下就是詳細內(nèi)容,需要的朋友可以參考下2021-08-08Matlab計算變異函數(shù)并繪制經(jīng)驗半方差圖詳解
這篇文章主要為大家詳細介紹了基于MATLAB求取空間數(shù)據(jù)的變異函數(shù),并繪制經(jīng)驗半方差圖的方法。文中的示例代碼講解詳細,感興趣的可以了解一下2023-04-04