【數據結構和算法初階(C語言)】雙向循環帶頭鏈表的增刪查改詳解（天才設計的鏈表結構，應用簡單逆天！！！！！）

?編輯?編輯

1.雙向鏈表的定義：前赴后繼?

2.帶頭鏈表的定義-----哨兵位?

3.增刪查改

3.1創建新節點函數----方便后續增加節點調用

3.2創建哨兵位----創建頭結點?

3.3增加節點，尾部插入數據?

3.4尾刪除?

3.5查找函數----遍歷+對比，返回節點地址?

3.6頭刪函數

3.7頭插函數?

3.8 計算數組的長度

3.9在任意位置pos前插入?

3.10在任意位置刪除

3.11鏈表的銷毀?

?4、結語及整個源碼含測試用例

1.雙向鏈表的定義：前赴后繼?

typedef int LTDataTYpe;
typedef struct ListNode
{struct ListNode* next;struct ListNode* prev;LTDataTYpe data;
}LTNode;

2.帶頭鏈表的定義-----哨兵位?

3.增刪查改

先寫一個打印函數來方便后續測試：

void LTPrint(LTNode* phead)
{assert(phead);LTNode* cur= phead->next;while (cur != phead){//printf("phead");printf("%d<=>", cur->data);cur = cur->next;}}

3.1創建新節點函數----方便后續增加節點調用

申請節點，將前后指針置空同時可以給節點賦值，返回這個節點的地址，也就是指向這個節點的指針

LTNode* BuyNode(LTDataTYpe x)
{LTNode* phead = (LTNode*)malloc(sizeof(LTNode));if (phead == NULL){perror("malloc");exit(-1);}phead->data = x;phead->next = NULL;phead->prev = NULL;return phead;
}

3.2創建哨兵位----創建頭結點?

后續所有節點可以增加在哨兵位的前后就對應前插、尾插。

最開始的哨兵位前后指針都應該指向自己。

LTNode* LTInit()
{LTNode* phead = BuyNode(-1);//首先有一個節點phead->next = phead;phead->prev = phead;return phead;
}

3.3增加節點，尾部插入數據?

兩種情況一樣：


void LTPushBack(LTNode* phead, LTDataTYpe x)
{assert(phead);LTNode* tail = phead->prev;LTNode* newnode = BuyNode(x);newnode->prev = tail;tail->next = newnode;newnode->next = phead;phead->prev = newnode;}

3.4尾刪除?


void LTPopBack(LTNode* phead)
{assert(phead);assert(phead->next != phead);LTNode* tail = phead->prev;LTNode* tailprev = tail->prev;free(tail);tail->next = phead;phead->prev = tailprev;
}

3.5查找函數----遍歷+對比，返回節點地址?

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

3.6頭刪函數

void LTPodFront(LTNode* phead)
{assert(phead);assert(phead->next != phead);LTNode* after = phead->next;LTNode* tail = after->next;phead->next = tail;tail->prev = phead;free(after);
}

3.7頭插函數?

void LTPushFront(LTNode* phead, LTDataTYpe x)
{assert(phead);LTNode* d1 = phead->next;LTNode* newnode = BuyNode(x);phead->next = newnode;newnode->next = d1;d1->prev = newnode;newnode->prev = phead;}

3.8 計算數組的長度

?這里對于大家可能有一個誤區，我們的頭結點也就是哨兵位，數據領域沒有保存值，就會有伙伴像在數據域保存鏈表的大小，增加就+1，減少就-1，但是這種情況只針對數據域是整型的情況，如果數據領域是浮點數或者字符型，加1可能就導致數據不準確，

方法：遍歷+計數

int LTSize(LTNode* phead)
{assert(phead);//不能是空指針int size = 0;LTNode* cur = phead->next;//定義遍歷指針while (cur != phead){size++;cur = cur->next;}return size;
}

3.9在任意位置pos前插入?

如果pos=head就是尾插

如果pos = head->next就是頭插

void LTInsert(LTNode* pos, LTDataTYpe x)
{//首先要查找的節點不能為空assert(pos);LTNode* newnode = BuyNode(x);LTNode* prv = pos->prev;prv->next = newnode;newnode->prev = prv;newnode->next = pos;pos->prev = newnode;}

3.10在任意位置刪除

刪除一定注意保護頭結點---使用斷言

void LTErase(LTNode* pos)
{assert(pos);LTNode* posprev = pos->prev;LTNode* posnext = pos->next;free(pos);posprev->next = posnext;posnext->prev = posprev;
}

也是可以復用實現頭刪尾刪

3.11鏈表的銷毀?

鏈表不是連續的空間就不會像那種順序表找到頭一下子釋放而是注意釋放

void LTDestory(LTNode* phead)
{assert(phead);LTNode* cur = phead->next;while (cur != phead){LTNode* next = cur->next;free(cur);cur = next;}free(phead);//可以外部置空，不設置返回值和二級指針。}

?4、結語及整個源碼含測試用例

雙向鏈表是一個快捷使用的數據結構，非常實用，不過對于初學建議畫圖來理解增刪查改。很大程度上增刪查改避免了二級指針的傳參，就是因為使用了哨兵位的好處。以上就是本期的所有內容，知識含量蠻多，大家可以配合解釋和原碼運行理解。創作不易，大家如果覺得還可以的話，歡迎大家三連，有問題的地方歡迎大家指正，一起交流學習，一起成長，我是Nicn，正在c++方向前行的奮斗者，數據結構內容持續更新中，感謝大家的關注與喜歡。

源碼：

test.c

#include"List.h"
void test()
{LTNode* plist = LTInit();LTPushBack(plist, 1);LTPushBack(plist, 2);LTPushBack(plist, 3);LTPodFront(plist);LTPushFront(plist, 1);LTPrint(plist);printf("\n");//LTInsert(plist,1);//LTPrint(plist);
}
int main()
{test();return 0;
}

?List.h

#include<stdio.h>
#include<stdlib.h>
#include<assert.h>typedef int LTDataTYpe;
typedef struct ListNode
{struct ListNode* next;struct ListNode* prev;LTDataTYpe data;
}LTNode;//創建新節點函數
LTNode* BuyNode(LTDataTYpe x);
//初始化創建哨兵位
LTNode* LTInit();
//尾插一下
void LTPushBack(LTNode* phead, LTDataTYpe x);
//打印鏈表
void LTPrint(LTNode* phead);
//尾刪
void LTPopBack(LTNode* phead);
//計算鏈表的大小或者記錄鏈表的大小
int LTSize(LTNode* phead);
//頭刪函數
void LTPodFront(LTNode* phead);
//頭插一下
void LTPushFront(LTNode* phead, LTDataTYpe x);
//查找函數
LTNode* LTFind(LTNode* phead, LTDataTYpe x);
//在尋找到的任意pos位置之前插入
void LTInsert(LTNode* pos, LTDataTYpe x);//刪除任意位置，pos
void LTErase(LTNode* pos);
//鏈表的銷毀
//鏈表不是連續的空間就不會像那種順序表找到頭一下子釋放而是注意釋放
void LTDestory(LTNode* phead);

List.c

LTNode* BuyNode(LTDataTYpe x)
{LTNode* phead = (LTNode*)malloc(sizeof(LTNode));if (phead == NULL){perror("malloc");exit(-1);}phead->data = x;phead->next = NULL;phead->prev = NULL;return phead;
}LTNode* LTInit()
{LTNode* phead = BuyNode(-1);//首先有一個節點phead->next = phead;phead->prev = phead;return phead;
}void LTPushBack(LTNode* phead, LTDataTYpe x)
{assert(phead);LTNode* tail = phead->prev;LTNode* newnode = BuyNode(x);newnode->prev = tail;tail->next = newnode;newnode->next = phead;phead->prev = newnode;}
void LTPushFront(LTNode* phead, LTDataTYpe x)
{assert(phead);LTNode* d1 = phead->next;LTNode* newnode = BuyNode(x);phead->next = newnode;newnode->next = d1;d1->prev = newnode;newnode->prev = phead;}void LTPrint(LTNode* phead)
{assert(phead);LTNode* cur= phead->next;while (cur != phead){//printf("phead");printf("%d<=>", cur->data);cur = cur->next;}}void LTPopBack(LTNode* phead)
{assert(phead);assert(phead->next != phead);LTNode* tail = phead->prev;LTNode* tailprev = tail->prev;free(tail);tail->next = phead;phead->prev = tailprev;
}int LTSize(LTNode* phead)
{assert(phead);//不能是空指針int size = 0;LTNode* cur = phead->next;//定義遍歷指針while (cur != phead){size++;cur = cur->next;}return size;
}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;
}void LTInsert(LTNode* pos, LTDataTYpe x)
{//首先要查找的節點不能為空assert(pos);LTNode* newnode = BuyNode(x);LTNode* prv = pos->prev;prv->next = newnode;newnode->prev = prv;newnode->next = pos;pos->prev = newnode;}void LTErase(LTNode* pos)
{assert(pos);LTNode* posprev = pos->prev;LTNode* posnext = pos->next;free(pos);posprev->next = posnext;posnext->prev = posprev;
}void LTPodFront(LTNode* phead)
{assert(phead);assert(phead->next != phead);LTNode* after = phead->next;LTNode* tail = after->next;phead->next = tail;tail->prev = phead;free(after);
}void LTDestory(LTNode* phead)
{assert(phead);LTNode* cur = phead->next;while (cur != phead){LTNode* next = cur->next;free(cur);cur = next;}free(phead);//可以外部置空，不設置返回值和二級指針。}