目錄
概念
帶頭雙向循環(huán)鏈表的實現(xiàn)
前情提示
雙向鏈表的結(jié)構(gòu)體定義
雙向鏈表的初始化
關(guān)于無頭單向非循環(huán)鏈表無需初始化函數(shù)，順序表、帶頭雙向循環(huán)鏈表需要的思考
雙向鏈表在pos位置之前插入x
雙向鏈表的打印
雙鏈表刪除pos位置的結(jié)點
雙向鏈表的尾插
關(guān)于單鏈表的尾插需要用到二級指針，雙向鏈表不需要用到二級指針的思考
雙向鏈表的判空
雙向鏈表的尾刪
雙向鏈表的頭插?
雙向鏈表的頭刪
雙向鏈表查找值為x的結(jié)點
雙向鏈表的銷毀?
雙向鏈表的修改
雙向鏈表刪除值為x的結(jié)點
?雙向鏈表計算結(jié)點總數(shù)(不計phead)
雙向鏈表獲取第i位置的結(jié)點
雙向鏈表的清空
總代碼（想直接看結(jié)果的可以看這里）
概念
雙向鏈表也叫雙鏈表，是鏈表的一種，它的每個數(shù)據(jù)結(jié)點中都有兩個指針，分別指向直接后繼和直接前驅(qū)。所以，從雙向鏈表中的任意一個結(jié)點開始，都可以很方便地訪問它的前驅(qū)結(jié)點和后繼結(jié)點。我們一般構(gòu)造雙向循環(huán)鏈表。循環(huán)鏈表是一種鏈式存儲結(jié)構(gòu)，它的最后一個結(jié)點指向頭結(jié)點，形成一個環(huán)。因此，從循環(huán)鏈表中的任何一個結(jié)點出發(fā)都能找到任何其它結(jié)點。
帶頭雙向循環(huán)鏈表的實現(xiàn)
前情提示
List.h??用于? 引用的頭文件、雙向鏈表的定義、函數(shù)的聲明。
List.c? 用于? 函數(shù)的定義。
Test.c?用于? 雙向鏈表功能的測試。
雙向鏈表的結(jié)構(gòu)體定義
在List.h下
#pragma once//使同一個文件不會被包含(include)多次,不必擔(dān)心宏名沖突
//先將可能使用到的頭文件寫上
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<stdbool.h>
typedef int LTDataType;//假設(shè)結(jié)點的數(shù)據(jù)域類型為 int
//給變量定義一個易于記憶且意義明確的新名字,并且便于以后存儲其它類型時方便改動
//（比如我晚點想存double類型的數(shù)據(jù)，我就直接將 int 改為 double )
// 帶哨兵位雙向循環(huán)鏈表的結(jié)構(gòu)體定義
typedef struct ListNode
{
struct ListNode* prev;//前驅(qū)指針域:存放上一個結(jié)點的地址
struct ListNode* next;//后繼指針域:存放下一個結(jié)點的地址
LTDataType data;//數(shù)據(jù)域
}LTNode;
//struct 關(guān)鍵字和 ListNode 一起構(gòu)成了這個結(jié)構(gòu)類型
//typedef 為這個結(jié)構(gòu)起了一個別名,叫 LTNode,即：typedef struct ListNode LTNode
//現(xiàn)在就可以像 int 和 double 那樣直接使用 LTNode 來定義變量雙向鏈表的初始化
在List.h下
// 雙向鏈表的初始化
// 如果是單鏈表直接給個空指針就行，不需要單獨寫一個函數(shù)進行初始化
// 即：LTNode* plist = NULL;
// 那為什么順序表、帶頭雙向循環(huán)鏈表有呢？
// 因為順序表、帶頭雙向循環(huán)鏈表的結(jié)構(gòu)并不簡單，
// 如: 順序表順序表為空size要為0,還要看capacity是否要開空間,
// 若不開空間capacity=0,指針要給空,若開空間,還要檢查malloc是否成功
// 帶頭雙向循環(huán)鏈表要開個結(jié)點,檢查malloc是否成功,然后讓結(jié)點自己指向自己
// 順序表和雙向循環(huán)鏈表的初始化有點復(fù)雜,最好構(gòu)建一個函數(shù)
LTNode* LTInit();在List.c下
#include"List.h"http://別忘了
//動態(tài)申請一個結(jié)點
LTNode* BuyListNode(LTDataType x)
{
LTNode* node = (LTNode*)malloc(sizeof(LTNode));
if (node == NULL)//如果malloc失敗
{
perror("malloc fail");
return NULL;
}
//如果malloc成功
//初始化一下，防止野指針，如果看到返回的是空指針，那邏輯可能有些錯誤
node->next = NULL;
node->prev = NULL;
node->data = x;
return node;
}
// 雙向鏈表的初始化
LTNode* LTInit()
{
LTNode* phead = BuyListNode(-1);//創(chuàng)建哨兵位
//自己指向自己
phead->next = phead;
phead->prev = phead;
return phead;
}關(guān)于無頭單向非循環(huán)鏈表無需初始化函數(shù)，順序表、帶頭雙向循環(huán)鏈表需要的思考
無頭單向非循環(huán)鏈表結(jié)構(gòu)太簡單了，初始化只需直接賦空指針，無需單獨寫一個函數(shù)進行初始化。
即：LTNode* plist = NULL;那為什么順序表、帶頭雙向循環(huán)鏈表有單獨寫一個函數(shù)進行初始化呢？
因為順序表、帶頭雙向循環(huán)鏈表的結(jié)構(gòu)并不簡單。
如:
順序表順序表為空size要為0,還要看capacity是否要開空間,若不開空間capacity=0,指針要給空，若開空間,還要檢查malloc是否成功。
帶頭雙向循環(huán)鏈表要開個結(jié)點,檢查malloc是否成功,然后讓結(jié)點自己指向自己。
順序表和雙向循環(huán)鏈表的初始化有點復(fù)雜,最好構(gòu)建一個函數(shù)。
雙向鏈表在pos位置之前插入x
在List.h下
// 雙向鏈表在pos位置之前進行插入
void LTInsert(LTNode* pos, LTDataType x);在List.c下
// 雙向鏈表在pos位置之前進行插入
void LTInsert(LTNode* pos, LTDataType x)
{
assert(pos);//pos肯定不為空
LTNode* prev = pos->prev;
LTNode* newnode = BuyListNode(x);//創(chuàng)建一個需要插入的結(jié)點
prev->next = newnode;
newnode->prev = prev;
newnode->next = pos;
pos->prev = newnode;
}
雙向鏈表的打印
在List.h下
// 雙向鏈表打印
void LTPrint(LTNode* phead);在List.c下
// 雙向鏈表打印
void LTPrint(LTNode* phead)
{
assert(phead);//有哨兵位
printf("<=>phead<=>");
LTNode* cur = phead->next;//cur指向第一個要打印的結(jié)點
while (cur != phead)//cur等于頭結(jié)點時打印就結(jié)束了
{
printf("%d<=>", cur->data);
cur = cur->next;
}
printf("\n");
}在Test.c下
#include"List.h"http://別忘了
//測試函數(shù)
void TestList1()
{
LTNode* plist = LTInit();
LTInsert(plist, 1);
LTInsert(plist, 2);
LTInsert(plist, 3);
LTInsert(plist, 4);
LTPrint(plist);
}
int main()
{
TestList1();
return 0;
}
雙鏈表刪除pos位置的結(jié)點
在List.h下
// 雙向鏈表刪除pos位置的結(jié)點
void LTErase(LTNode* pos);在List.c下
// 雙向鏈表刪除pos位置的結(jié)點
void LTErase(LTNode* pos)
{
assert(pos);//pos肯定不為空
LTNode* posprev = pos->prev;
LTNode* posnext = pos->next;
posprev->next = posnext;
posnext->prev = posprev;
free(pos);
pos = NULL;
//這個置空其實已經(jīng)沒有意義了，形參的改變不會改變實參
}在Test.c下
//測試函數(shù)
void TestList1()
{
LTNode* plist = LTInit();
LTInsert(plist, 1);
LTInsert(plist, 2);
LTInsert(plist, 3);
LTInsert(plist, 4);
LTPrint(plist);
LTErase(plist->next);
LTPrint(plist);
}
int main()
{
TestList1();
return 0;
}
雙向鏈表的尾插
在List.h下
//雙向鏈表優(yōu)于單鏈表的點——不需要找尾、二級指針
//（我們改的不是結(jié)構(gòu)體的指針，改的是結(jié)構(gòu)體的變量）
// 雙向鏈表的尾插
void LTPushBack(LTNode* phead, LTDataType x);在List.c下
法一:（便于新手更好地理解雙向鏈表的尾插）?
// 雙向鏈表的尾插
void LTPushBack(LTNode* phead, LTDataType x)
{
assert(phead);//有哨兵位
//法一:(便于新手更好地理解雙向鏈表的尾插)
//一步就可完成鏈表為空/不為空的尾插——因為有哨兵位
LTNode* newnode = BuyListNode(x);//創(chuàng)建一個要插入的結(jié)點
LTNode* tail = phead->prev;
tail->next = newnode;
newnode->prev = tail;
newnode->next = phead;
phead->prev = newnode;
}法二：函數(shù)復(fù)用（簡單方便）
// 雙向鏈表的尾插
void LTPushBack(LTNode* phead, LTDataType x)
{
assert(phead);//有哨兵位
//法二:函數(shù)復(fù)用（簡單方便）
LTInsert(phead, x);
}
關(guān)于單鏈表的尾插需要用到二級指針，雙向鏈表不需要用到二級指針的思考
單鏈表改變的是結(jié)構(gòu)體的指針，雙向鏈表改變的是結(jié)構(gòu)體的變量
二級指針和一級指針的區(qū)別在于指針?biāo)赶蜃兞康膶蛹壊煌?strong>一級指針指向的是結(jié)構(gòu)體的變量，而二級指針指向的是結(jié)構(gòu)體指針的地址。
單鏈表中，在進行鏈表結(jié)點的刪除或插入操作時，需要更新結(jié)點之間的指針指向。若使用一級指針，則操作會直接改變指向結(jié)點的指針，很難實現(xiàn)目標(biāo)。因此需要傳遞二級指針，讓函數(shù)能夠修改指向結(jié)點指針的地址，也就是修改之前結(jié)點指針變量存放的地址。
而雙向鏈表中，每個結(jié)點除了保存指向下一結(jié)點的指針外，還有保存指向上一結(jié)點的指針，結(jié)點之間的雙向指針關(guān)系使得結(jié)點的插入和刪除操作更加方便。雙向鏈表不需要傳遞二級指針，因為在結(jié)點的刪除和插入操作中，只需要先修改當(dāng)前結(jié)點前后結(jié)點的指針，無需直接改變前后結(jié)點指針變量存放的地址。
綜上所述，單鏈表只有指向下一結(jié)點的指針，通過傳遞二級指針來修改結(jié)點之間的指針關(guān)系，使得操作更加靈活；而雙向鏈表的結(jié)點之間有雙向指針關(guān)系，無需直接改變前后結(jié)點指針變量存放的地址，因此只需要傳遞一級指針即可。
單鏈表（對比）：
在Test.c下
//測試函數(shù)
void TestList2()
{
LTNode* plist = LTInit();
LTPushBack(plist, 5);
LTPushBack(plist, 6);
LTPushBack(plist, 7);
LTPushBack(plist, 8);
LTPrint(plist);
}
int main()
{
TestList2();
return 0;
}
雙向鏈表的判空
在尾刪/頭刪之前，我們要先判斷鏈表是否為空。
在List.h下
// 雙向鏈表的判空
bool LTEmpty(LTNode* phead);在List.c下
// 雙向鏈表的判空
bool LTEmpty(LTNode* phead)
{
assert(phead);
return phead->next == phead;
//兩者相等就是空鏈表(返回真),兩者不相等就不是空鏈表(返回假)
}雙向鏈表的尾刪
在List.h下
// 雙向鏈表的尾刪
void LTPopBack(LTNode* phead);在List.c下
法一：（便于新手更好地理解雙向鏈表的尾刪）
// 雙向鏈表的尾刪
void LTPopBack(LTNode* phead)
{
assert(phead);//有哨兵位
assert(!LTEmpty(phead));//判空
//法一：（便于新手更好地理解雙向鏈表的尾刪）
LTNode* tail = phead->prev;
LTNode* tailPrev = tail->prev;
tailPrev->next = phead;
phead->prev = tailPrev;
free(tail);
tail = NULL;
}法二：函數(shù)復(fù)用（簡單方便）
// 雙向鏈表的尾刪
void LTPopBack(LTNode* phead)
{
assert(phead);//有哨兵位
assert(!LTEmpty(phead));//判空
//法二:函數(shù)復(fù)用
LTErase(phead->prev);
}在Test.c下
//測試函數(shù)
void TestList2()
{
LTNode* plist = LTInit();
LTPushBack(plist, 5);
LTPushBack(plist, 6);
LTPushBack(plist, 7);
LTPushBack(plist, 8);
LTPrint(plist);
LTPopBack(plist);
LTPopBack(plist);
LTPrint(plist);
}
int main()
{
TestList2();
return 0;
}
雙向鏈表的頭插?
在List.h下
// 雙向鏈表頭插
void LTPushFront(LTNode* phead, LTDataType x);在List.c下
法一:只用phead和newnode兩個指針（便于新手更好地理解雙向鏈表的頭插）
// 雙向鏈表頭插
void LTPushFront(LTNode* phead, LTDataType x)
{
assert(phead);//有哨兵位
LTNode* newnode = BuyListNode(x);//創(chuàng)建一個要插入的結(jié)點
//法一:只用phead和newnode兩個指針（便于新手更好地理解雙向鏈表的頭插）
//順序很重要?。?！
newnode->next = phead->next;
phead->next->prev = newnode;
phead->next = newnode;
newnode->prev = phead;
}法二:多用了first記錄第一個結(jié)點的位置（便于新手更好地理解雙向鏈表的頭插）
// 雙向鏈表頭插
void LTPushFront(LTNode* phead, LTDataType x)
{
assert(phead);//哨兵位
LTNode* newnode = BuyListNode(x);//創(chuàng)建一個要插入的結(jié)點
//法二：多用了first先記住第一個結(jié)點（便于新手更好地理解雙向鏈表的頭插）
LTNode* first = phead->next;
phead->next = newnode;
newnode->prev = phead;
newnode->next = first;
first->prev = newnode;
}法三:函數(shù)復(fù)用（簡單方便）
// 雙向鏈表頭插
void LTPushFront(LTNode* phead, LTDataType x)
{
assert(phead);//有哨兵位
//法三:函數(shù)復(fù)用（簡單方便）
LTInsert(phead->next, x);
}在Test.c下
//測試函數(shù)
void TestList3()
{
LTNode* plist = LTInit();
LTPushFront(plist, 1);
LTPushFront(plist, 2);
LTPushFront(plist, 3);
LTPushFront(plist, 4);
LTPrint(plist);
}
int main()
{
TestList3();
return 0;
}
雙向鏈表的頭刪
在List.h下
// 雙向鏈表頭刪
void LTPopFront(LTNode* phead);在List.c下
法一:（便于新手更好地理解雙向鏈表的頭刪）
// 雙向鏈表頭刪
void LTPopFront(LTNode* phead)
{
assert(phead);//有哨兵位
assert(!LTEmpty(phead));//判空
//法一:（便于新手更好地理解雙向鏈表的頭刪）
LTNode* head = phead->next;
LTNode* headnext = head->next;
phead->next = headnext;
headnext->prev = phead;
free(head);
head = NULL;
}法二:函數(shù)復(fù)用（簡單方便）?
// 雙向鏈表頭刪
void LTPopFront(LTNode* phead)
{
assert(phead);//有哨兵位
assert(!LTEmpty(phead));//判空
//法二:函數(shù)復(fù)用（簡單方便）
LTErase(phead->next);
}
在Test.c下
//測試函數(shù)
void TestList3()
{
LTNode* plist = LTInit();
LTPushFront(plist, 1);
LTPushFront(plist, 2);
LTPushFront(plist, 3);
LTPushFront(plist, 4);
LTPrint(plist);
LTPopFront(plist);
LTPopFront(plist);
LTPrint(plist);
}
int main()
{
TestList3();
return 0;
}
雙向鏈表查找值為x的結(jié)點
在List.h下
// 雙向鏈表查找值為x的結(jié)點
LTNode* LTFind(LTNode* phead, LTDataType x);在List.c下
// 雙向鏈表查找值為x的結(jié)點
LTNode* LTFind(LTNode* phead, LTDataType x)
{
assert(phead);//有哨兵位
LTNode* cur = phead->next;
while (cur != phead)//讓cur去遍歷
{
if (cur->data == x)//如果找到
{
return cur;
}
cur = cur->next;
}
return NULL;//如果沒找到
}在Test.c下
//測試函數(shù)
TestList4()
{
LTNode* plist = LTInit();
LTInsert(plist, 1);
LTInsert(plist, 2);
LTInsert(plist, 3);
LTInsert(plist, 4);
LTPrint(plist);
LTNode* pos = LTFind(plist, 3);
if (pos)
{
LTErase(pos);
pos = NULL;
}
LTPrint(plist);
}
int main()
{
TestList4();
return 0;
}
雙向鏈表的銷毀?
在List.h下
// 雙向鏈表的銷毀
void LTDestory(LTNode* phead);在List.c下
? ?
??
?
// 雙向鏈表的銷毀
void LTDestory(LTNode* phead)
{
assert(phead);
LTNode* cur = phead->next;//讓cur遍歷
while (cur != phead)
{
LTNode* curnext = cur->next;
free(cur);
cur = curnext;
}
free(phead);
phead = NULL;
//這個置空其實已經(jīng)沒有意義了，形參的改變不會改變實參
//我們?yōu)榱吮３纸涌诘囊恢滦?不傳二級指針,選擇在測試的時候置空
}在Test.c下
//測試函數(shù)
TestList4()
{
LTNode* plist = LTInit();
LTInsert(plist, 1);
LTInsert(plist, 2);
LTInsert(plist, 3);
LTInsert(plist, 4);
LTPrint(plist);
LTNode* pos = LTFind(plist, 3);
if (pos)
{
LTErase(pos);
pos = NULL;
}
LTPrint(plist);
LTDestory(plist);
plist = NULL;//在這里置空
}雙向鏈表的修改
在List.h下
// 雙向鏈表的修改,修改pos位置的值為x
void LTModify(LTNode* pos, LTDataType x);在List.c下
// 雙向鏈表的修改,修改pos位置的值為x
void LTModify(LTNode* pos, LTDataType x)
{
assert(pos);
pos->data = x;
}在Test.c下
//測試函數(shù)
TestList5()
{
LTNode* plist = LTInit();
LTInsert(plist, 1);
LTInsert(plist, 2);
LTInsert(plist, 3);
LTInsert(plist, 4);
LTPrint(plist);
LTModify(plist->next,5);
LTPrint(plist);
}
int main()
{
TestList5();
return 0;
}
雙向鏈表刪除值為x的結(jié)點
在List.h下
// 雙向鏈表刪除值為x的結(jié)點
void LTRemove(LTNode* phead,LTDataType x);在List.c下
// 雙向鏈表刪除值為x的結(jié)點
void LTRemove(LTNode* phead, LTDataType x)
{
assert(phead);//有哨兵位
LTNode* pos = phead->next;
while (pos != phead)
{
pos = LTFind(phead, x);
if (pos == NULL)//如果遍歷完
{
return NULL;
}
LTErase(pos);
pos = pos->next;
}
}在Test.c下
TestList6()
{
LTNode* plist = LTInit();
LTInsert(plist, 1);
LTInsert(plist, 3);
LTInsert(plist, 3);
LTInsert(plist, 4);
LTInsert(plist, 3);
LTPrint(plist);
LTRemove(plist, 3);
LTPrint(plist);
}
int main()
{
TestList6();
return 0;
}
?雙向鏈表計算結(jié)點總數(shù)(不計phead)
在List.h下
// 雙向鏈表計算結(jié)點總數(shù)(不計phead)
int LTTotal(LTNode* phead);在List.c下
// 雙向鏈表計算結(jié)點總數(shù)(不計phead)
int LTTotal(LTNode* phead)
{
assert(phead);//有哨兵位
int count = 0;//count來計數(shù)
LTNode* cur = phead->next;//讓cur去遍歷
while (cur != phead)
{
count++;
cur = cur->next;
}
return count;
}在Test.c下
TestList6()
{
LTNode* plist = LTInit();
LTInsert(plist, 1);
LTInsert(plist, 3);
LTInsert(plist, 3);
LTInsert(plist, 4);
LTInsert(plist, 3);
LTPrint(plist);
LTRemove(plist, 3);
LTPrint(plist);
printf("%d\n", LTTotal(plist));
}
int main()
{
TestList6();
return 0;
}
雙向鏈表獲取第i位置的結(jié)點
在List.h下
// 雙向鏈表獲取第i位置的結(jié)點
LTNode* LTGet(LTNode* phead, int i);在List.c下
// 雙向鏈表獲取第i位置的結(jié)點
LTNode* LTGet(LTNode* phead, int i)
{
assert(phead);//有哨兵位
int length = LTTotal(phead);
LTNode* cur = phead->next;
if (i == 0)
{
return phead;
}
else if (i<0 || i>length)//位置不合法
{
return NULL;
}
else if (i <= (length / 2))//從表頭開始遍歷
{
cur = phead->next;
for (int count = 1; count < i; count++)
{
cur = cur->next;
}
}
else//從表尾開始遍歷
{
cur = phead->prev;
for (int count = 1; count <= length - i; count++)
{
cur = cur->prev;
}
}
return cur;
}在Test.c下
//測試函數(shù)
TestList7()
{
LTNode* plist = LTInit();
LTInsert(plist, 5);
LTInsert(plist, 6);
LTInsert(plist, 7);
LTInsert(plist, 8);
LTInsert(plist, 9);
LTPrint(plist);
LTNode* pos = LTGet(plist,3);
if (pos)
{
LTErase(pos);
pos = NULL;
}
LTPrint(plist);
}
int main()
{
TestList7();
return 0;
}雙向鏈表的清空
在List.h下
// 雙向鏈表的清空
void LTClean(LTNode* phead);在List.c下
// 雙向鏈表的清空
void LTClear(LTNode* phead)
{
assert(phead);//有哨兵位
while (!LTEmpty(phead))//如果不為空就一直頭刪
{
LTPopFront(phead);
}
}在Test.c下
//測試函數(shù)
TestList8()
{
LTNode* plist = LTInit();
LTInsert(plist, 5);
LTInsert(plist, 6);
LTInsert(plist, 7);
LTInsert(plist, 8);
LTInsert(plist, 9);
LTPrint(plist);
LTClear(plist);
LTPrint(plist);
}
int main()
{
TestList8();
return 0;
}總代碼（想直接看結(jié)果的可以看這里）
在List.h下
#pragma once//使同一個文件不會被包含(include)多次,不必擔(dān)心宏名沖突
//先將可能使用到的頭文件寫上
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<stdbool.h>
typedef int LTDataType;//假設(shè)結(jié)點的數(shù)據(jù)域類型為 int
//給變量定義一個易于記憶且意義明確的新名字,并且便于以后存儲其它類型時方便改動
//（比如我晚點想存double類型的數(shù)據(jù)，我就直接將 int 改為 double )
// 帶哨兵位雙向循環(huán)鏈表的結(jié)構(gòu)體定義
typedef struct ListNode
{
struct ListNode* prev;//前驅(qū)指針域:存放上一個結(jié)點的地址
struct ListNode* next;//后繼指針域:存放下一個結(jié)點的地址
LTDataType data;//數(shù)據(jù)域
}LTNode;
//struct 關(guān)鍵字和 ListNode 一起構(gòu)成了這個結(jié)構(gòu)類型
//typedef 為這個結(jié)構(gòu)起了一個別名,叫 LTNode,即：typedef struct ListNode LTNode
//現(xiàn)在就可以像 int 和 double 那樣直接使用 LTNode 來定義變量
// 雙向鏈表的初始化
// 如果是單鏈表直接給個空指針就行，不需要單獨寫一個函數(shù)進行初始化
// 即：LTNode* plist = NULL;
// 那為什么順序表、帶頭雙向循環(huán)鏈表有呢？
// 因為順序表、帶頭雙向循環(huán)鏈表的結(jié)構(gòu)并不簡單，
// 如:順序表順序表為空size要為0,還要看capacity是否要開空間,
//若不開空間capacity=0,指針要給空,若開空間,還要檢查malloc是否成功
// 帶頭雙向循環(huán)鏈表要開個結(jié)點,檢查malloc是否成功,然后讓結(jié)點自己指向自己
// 順序表和雙向循環(huán)鏈表的初始化有點復(fù)雜,最好構(gòu)建一個函數(shù)
LTNode* LTInit();
// 雙向鏈表在pos位置之前進行插入x
void LTInsert(LTNode* pos, LTDataType x);
// 雙向鏈表的打印
void LTPrint(LTNode* phead);
// 雙向鏈表刪除pos位置的結(jié)點
void LTErase(LTNode* pos);
//雙向鏈表優(yōu)于單鏈表的點——不需要找尾、二級指針
// （我們改的不是結(jié)構(gòu)體的指針，改的是結(jié)構(gòu)體的變量）
// 雙向鏈表的尾插
void LTPushBack(LTNode* phead, LTDataType x);
// 雙向鏈表的判空
bool LTEmpty(LTNode* phead);
// 雙向鏈表的尾刪
void LTPopBack(LTNode* phead);
// 雙向鏈表頭插
void LTPushFront(LTNode* phead, LTDataType x);
// 雙向鏈表頭刪
void LTPopFront(LTNode* phead);
// 雙向鏈表查找值為x的結(jié)點
LTNode* LTFind(LTNode* phead, LTDataType x);
// 雙向鏈表的銷毀
void LTDestory(LTNode* phead);
// 雙向鏈表的修改,修改pos位置的值為x
void LTModify(LTNode* pos, LTDataType x);
// 雙向鏈表刪除值為x的結(jié)點
void LTRemove(LTNode* phead, LTDataType x);
// 雙向鏈表計算結(jié)點總數(shù)(不計phead)
int LTTotal(LTNode* phead);
// 雙向鏈表獲取第i位置的結(jié)點
LTNode* LTGet(LTNode* phead, int i);
// 雙向鏈表的清空
void LTClear(LTNode* phead);在List.c下
#include"List.h"
//動態(tài)申請一個結(jié)點
LTNode* BuyListNode(LTDataType x)
{
LTNode* node = (LTNode*)malloc(sizeof(LTNode));
if (node == NULL)//如果malloc失敗
{
perror("malloc fail");
return NULL;
}
//如果malloc成功
//初始化一下，防止野指針，如果看到返回的是空指針，那邏輯可能有些錯誤
node->next = NULL;
node->prev = NULL;
node->data = x;
return node;
}
// 雙向鏈表的初始化
LTNode* LTInit()
{
LTNode* phead = BuyListNode(-1);
//自己指向自己
phead->next = phead;
phead->prev = phead;
return phead;
}
// 雙向鏈表在pos位置之前進行插入x
void LTInsert(LTNode* pos, LTDataType x)
{
assert(pos);//pos肯定不為空
LTNode* prev = pos->prev;
LTNode* newnode = BuyListNode(x);//創(chuàng)建一個需要插入的結(jié)點
prev->next = newnode;
newnode->prev = prev;
newnode->next = pos;
pos->prev = newnode;
}
// 雙向鏈表的打印
void LTPrint(LTNode* phead)
{
assert(phead);//有哨兵位
printf("<=>phead<=>");
LTNode* cur = phead->next;//cur指向第一個要打印的結(jié)點
while (cur != phead)//cur等于頭結(jié)點時打印就結(jié)束了
{
printf("%d<=>", cur->data);
cur = cur->next;
}
printf("\n");
}
// 雙向鏈表刪除pos位置的結(jié)點
void LTErase(LTNode* pos)
{
assert(pos);//pos肯定不為空
LTNode* posprev = pos->prev;
LTNode* posnext = pos->next;
posprev->next = posnext;
posnext->prev = posprev;
free(pos);
pos = NULL;
//這個置空其實已經(jīng)沒有意義了，形參的改變不會改變實參
}
// 雙向鏈表的尾插
void LTPushBack(LTNode* phead, LTDataType x)
{
assert(phead);//有哨兵位
//法一:（便于新手更好地理解雙向鏈表的尾插）
//一步就可完成鏈表為空/不為空的尾插
//LTNode* newnode = BuyListNode(x);
//LTNode* tail = phead->prev;
//tail->next = newnode;
//newnode->prev = tail;
//newnode->next = phead;
//phead->prev = newnode;
//法二:函數(shù)復(fù)用（簡單方便）
LTInsert(phead, x);
}
// 雙向鏈表的判空
bool LTEmpty(LTNode* phead)
{
assert(phead);
return phead->next == phead;
//兩者相等就是空鏈表(返回真),兩者不相等就不是空鏈表(返回假)
}
// 雙向鏈表的尾刪
void LTPopBack(LTNode* phead)
{
assert(phead);//有哨兵位
//法一:（便于新手更好地理解雙向鏈表的尾刪）
//assert(!LTEmpty(phead));//判空
//LTNode* tail = phead->prev;
//LTNode* tailPrev = tail->prev;
//tailPrev->next = phead;
//phead->prev = tailPrev;
//free(tail);
//tail = NULL;
//法二:函數(shù)復(fù)用
LTErase(phead->prev);
}
// 雙向鏈表頭插
void LTPushFront(LTNode* phead, LTDataType x)
{
assert(phead);//有哨兵位
//LTNode* newnode = BuyListNode(x);//創(chuàng)建一個要插入的結(jié)點
//法一:只用phead和newnode兩個指針（便于新手更好地理解雙向鏈表的頭插）
//newnode->next = phead->next;
//phead->next->prev = newnode;
//phead->next = newnode;
//newnode->prev = phead;
//法二:多用了first先記住第一個結(jié)點（便于新手更好地理解雙向鏈表的頭插）
//LTNode* first = phead->next;
//phead->next = newnode;
//newnode->prev = phead;
//newnode->next = first;
//first->prev = newnode;
//法三:函數(shù)復(fù)用(簡單方便)
LTInsert(phead->next, x);
}
// 雙向鏈表頭刪
void LTPopFront(LTNode* phead)
{
assert(phead);//有哨兵位
assert(!LTEmpty(phead));//判空
//法一:（便于新手更好地理解雙向鏈表的頭刪）
//LTNode* head = phead->next;
//LTNode* headnext = head->next;
//phead->next = headnext;
//headnext->prev = phead;
//free(head);
//head = NULL;
//法二:函數(shù)復(fù)用（簡單方便）
LTErase(phead->next);
}
// 雙向鏈表查找值為x的結(jié)點
LTNode* LTFind(LTNode* phead, LTDataType x)
{
assert(phead);//有哨兵位
LTNode* cur = phead->next;
while (cur != phead)//讓cur去遍歷
{
if (cur->data == x)
{
return cur;
}
cur = cur->next;
}
return NULL;
}
// 雙向鏈表的銷毀
void LTDestory(LTNode* phead)
{
assert(phead);
LTNode* cur = phead->next;
while (cur != phead)
{
LTNode* curnext = cur->next;
free(cur);
cur = curnext;
}
free(phead);
phead = NULL;
//這個置空其實已經(jīng)沒有意義了，形參的改變不會改變實參
//我們?yōu)榱吮３纸涌诘囊恢滦?不傳二級指針,選擇在測試的時候置空
}
// 雙向鏈表的修改,修改pos位置的值為x
void LTModify(LTNode* pos, LTDataType x)
{
assert(pos);//pos肯定不為空
pos->data = x;
}
// 雙向鏈表刪除值為x的結(jié)點
void LTRemove(LTNode* phead, LTDataType x)
{
assert(phead);//有哨兵位
LTNode* pos = phead->next;
while (pos != phead)
{
pos = LTFind(phead, x);
if (pos == NULL)//如果遍歷完
{
return NULL;
}
LTErase(pos);
pos = pos->next;
}
}
// 雙向鏈表計算結(jié)點總數(shù)(不計phead)
int LTTotal(LTNode* phead)
{
assert(phead);//有哨兵位
int count = 0;//count來計數(shù)
LTNode* cur = phead->next;//讓cur去遍歷
while (cur != phead)
{
count++;
cur = cur->next;
}
return count;
}
// 雙向鏈表獲取第i位置的結(jié)點
LTNode* LTGet(LTNode* phead, int i)
{
assert(phead);//有哨兵位
int length = LTTotal(phead);
LTNode* cur = phead->next;
if (i == 0)
{
return phead;
}
else if (i<0 || i>length)//位置不合法
{
return NULL;
}
else if (i <= (length / 2))//從表頭開始遍歷
{
cur = phead->next;
for (int count = 1; count < i; count++)
{
cur = cur->next;
}
}
else//從表尾開始遍歷
{
cur = phead->prev;
for (int count = 1; count <= length - i; count++)
{
cur = cur->prev;
}
}
return cur;
}
// 雙向鏈表的清空
void LTClear(LTNode* phead)
{
assert(phead);//有哨兵位
while (!LTEmpty(phead))//如果不為空就一直頭刪
{
LTPopFront(phead);
}
}在Test.c下
#include"List.h"
//測試函數(shù)
void TestList1()
{
LTNode* plist = LTInit();
LTInsert(plist, 1);
LTInsert(plist, 2);
LTInsert(plist, 3);
LTInsert(plist, 4);
LTPrint(plist);
LTErase(plist->next);
LTPrint(plist);
}
//測試函數(shù)
void TestList2()
{
LTNode* plist = LTInit();
LTPushBack(plist, 5);
LTPushBack(plist, 6);
LTPushBack(plist, 7);
LTPushBack(plist, 8);
LTPrint(plist);
LTPopBack(plist);
LTPopBack(plist);
LTPrint(plist);
}
//測試函數(shù)
void TestList3()
{
LTNode* plist = LTInit();
LTPushFront(plist, 1);
LTPushFront(plist, 2);
LTPushFront(plist, 3);
LTPushFront(plist, 4);
LTPrint(plist);
LTPopFront(plist);
LTPopFront(plist);
LTPrint(plist);
}
//測試函數(shù)
TestList4()
{
LTNode* plist = LTInit();
LTInsert(plist, 1);
LTInsert(plist, 2);
LTInsert(plist, 3);
LTInsert(plist, 4);
LTPrint(plist);
LTNode* pos = LTFind(plist, 3);
if (pos)
{
LTErase(pos);
pos = NULL;
}
LTPrint(plist);
LTDestory(plist);
plist = NULL;//在這里置空
}
//測試函數(shù)
TestList5()
{
LTNode* plist = LTInit();
LTInsert(plist, 1);
LTInsert(plist, 2);
LTInsert(plist, 3);
LTInsert(plist, 4);
LTPrint(plist);
LTModify(plist->next, 5);
LTPrint(plist);
}
TestList6()
{
LTNode* plist = LTInit();
LTInsert(plist, 1);
LTInsert(plist, 3);
LTInsert(plist, 3);
LTInsert(plist, 4);
LTInsert(plist, 3);
LTPrint(plist);
LTRemove(plist, 3);
LTPrint(plist);
printf("%d\n", LTTotal(plist));
}
//測試函數(shù)
TestList7()
{
LTNode* plist = LTInit();
LTInsert(plist, 5);
LTInsert(plist, 6);
LTInsert(plist, 7);
LTInsert(plist, 8);
LTInsert(plist, 9);
LTPrint(plist);
LTNode* pos = LTGet(plist, 3);
if (pos)
{
LTErase(pos);
pos = NULL;
}
LTPrint(plist);
LTClear(plist);
LTPrint(plist);
}
//測試函數(shù)
TestList8()
{
LTNode* plist = LTInit();
LTInsert(plist, 5);
LTInsert(plist, 6);
LTInsert(plist, 7);
LTInsert(plist, 8);
LTInsert(plist, 9);
LTPrint(plist);
LTClear(plist);
LTPrint(plist);
}
int main()
{
//TestList1();
//TestList2();
//TestList3();
//TestList4();
//TestList5();
//TestList6();
//TestList7();
TestList8();
return 0;
}歡迎指正?
文章來源：http://www.zghlxwxcb.cn/news/detail-439784.html
?文章來源地址http://www.zghlxwxcb.cn/news/detail-439784.html
到了這里，關(guān)于雙向鏈表(數(shù)據(jù)結(jié)構(gòu))(C語言)的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
