W...Y的主頁
今天我們接著來說數(shù)據(jù)結(jié)構(gòu)——帶頭雙向鏈表
目錄
帶頭雙向鏈表的實現(xiàn)
結(jié)構(gòu)體的創(chuàng)建
初始化兵創(chuàng)建哨兵節(jié)點
釋放鏈表所以內(nèi)容?
打印鏈表函數(shù)
尾插
尾刪
頭插
?編輯
頭刪
計數(shù)函數(shù)實現(xiàn)
查找數(shù)據(jù)相應(yīng)位置函數(shù)
在pos位置之前插入?
在pos位置刪除?
順序表與鏈表的差別
帶頭雙向鏈表（Doubly Linked List with Head）相對于普通的雙向鏈表，添加了一個頭節(jié)點（head node），頭節(jié)點不存儲任何實際的數(shù)據(jù)，僅用于指示鏈表的起始位置。下面是帶頭雙向鏈表的一些優(yōu)點：
鏈表操作方便：帶頭雙向鏈表提供了直接訪問鏈表頭部和尾部的能力，使得鏈表的插入、刪除等操作更加高效。你可以通過頭節(jié)點快速插入第一個元素，也可以通過尾節(jié)點快速插入新元素。同時，由于鏈表的雙向性，你可以輕松地在鏈表中的任意位置進行插入和刪除操作。
遍歷靈活性：帶頭雙向鏈表可以從頭到尾或從尾到頭兩個方向遍歷。這意味著你可以根據(jù)需要選擇合適的遍歷方式，無論是從前向后還是從后向前遍歷鏈表，都能方便地獲取元素。
反向查找：帶頭雙向鏈表的一個重要優(yōu)點是可以通過后向鏈接（back link）從任意節(jié)點快速訪問該節(jié)點的前一個節(jié)點。這使得在鏈表中進行反向查找變得高效。與單鏈表相比，帶頭雙向鏈表的反向查找時間復(fù)雜度從O(n)降至O(1)，這對某些應(yīng)用程序可能非常重要。
方便的刪除節(jié)點：在帶頭雙向鏈表中，刪除一個節(jié)點不需要訪問其前一個節(jié)點，只需修改當(dāng)前節(jié)點的前后鏈接即可。這樣，節(jié)點的刪除操作變得更為方便和高效。
帶頭雙向循環(huán)鏈表：結(jié)構(gòu)最復(fù)雜，一般用在單獨存儲數(shù)據(jù)。實際中使用的鏈表數(shù)據(jù)結(jié)構(gòu)，都是帶頭雙向循環(huán)鏈表。另外這個結(jié)構(gòu)雖然結(jié)構(gòu)復(fù)雜，但是使用代碼實現(xiàn)以后會發(fā)現(xiàn)結(jié)構(gòu)會帶 來很多優(yōu)勢，實現(xiàn)反而簡單了，后面我們代碼實現(xiàn)了就知道了。
帶頭雙向鏈表的實現(xiàn)
結(jié)構(gòu)體的創(chuàng)建
typedef int LTDataType;
typedef struct ListNode
{
int data;
struct ListNode* next;
struct ListNode* prev;
}LTNode;創(chuàng)建結(jié)構(gòu)體使用typedef將其改名LTNode方便使用，創(chuàng)建next和prev節(jié)點用來保存下一個節(jié)點與上一個節(jié)點。
初始化兵創(chuàng)建哨兵節(jié)點
我們創(chuàng)建哨兵位時，可以在data中間增加-1，創(chuàng)建好后將next與prev全部指向自己。但是這個功能與怎加節(jié)點函數(shù)內(nèi)容及其相似，所以我們可以先創(chuàng)建節(jié)點函數(shù)，然后再初始化哨兵位時將其調(diào)用即可，防止冗余現(xiàn)象。
LTNode* BuyLTNode(LTDataType x)
{
LTNode* node = (LTNode*)malloc(sizeof(LTNode));
if (node == NULL)
{
perror("malloc fail");
exit(-1);
}
node->data = x;
node->prev = NULL;
return node;
}LTNode* LTInit()
{
LTNode* phead = BuyLTNode(-1);
phead->next = phead;
phead->prev = phead;
return phead;
}?我們再創(chuàng)建好兩個函數(shù)時，讓LTInit函數(shù)去調(diào)用BuyLTNode函數(shù)，將哨兵位初始化即可。
釋放鏈表所以內(nèi)容?
因為鏈表使用realloc開辟的空間全部在堆區(qū)，所以必須將鏈表開辟的空間全部釋放，防止內(nèi)存泄漏。
void LTDestory(LTNode* phead)
{
assert(phead);
LTNode* cur = phead->next;
while (cur != phead)
{
LTNode* next = cur->next;
free(cur);
cur = next;
}
free(phead);
phead = NULL;
}打印鏈表函數(shù)
在打印鏈表時，我們要將次鏈表與單鏈表區(qū)分。單鏈表只需找到尾NULL即可停止，而雙向鏈表的尾部指向哨兵位，所以我們可以換一種方法進行檢測。
void LTPrint(LTNode* phead)
{
assert(phead);
LTNode* cur = phead->next;
printf("phead<->");
while (cur != phead)
{
printf("%d<->", cur->data);
cur = cur->next;
}
}我們創(chuàng)建一個遍歷指針cur，讓cur = phead->next指向哨兵位下一個節(jié)點。然后進行遍歷，如果遍歷返回到哨兵位phead停止即可。
尾插
尾插相對于單鏈表也非常方便，不用遍歷找尾節(jié)點，只需要訪問phead的prev即可找到尾節(jié)點。?
void LTPushBack(LTNode* phead, LTDataType x)
{
assert(phead);
LTNode* tail = phead->prev;
LTNode* newnode = BuyLTNode(x);
newnode->prev = tail;
newnode->next = phead;
tail->next = newnode;
phead->prev = newnode;
}
尾刪
我們首先得檢測phead哨兵位是否為空，如果鏈表為空我們也不能正常進行刪除，所以我們得繼續(xù)判斷phead->next != phead。自己的下一個節(jié)點不能指向自己。
void LTPopBack(LTNode* phead)
{
assert(phead);
assert(phead->next != phead);
LTNode* tail = phead->prev;
phead->prev = tail->prev;
tail->prev->next = phead;
free(tail);
}刪除就非常簡單，訪問最后一個節(jié)點記作tail，將phead連接尾節(jié)點的地址切換成尾節(jié)點的上一個節(jié)點，然后將尾節(jié)點上一個節(jié)點的next換成哨兵位地址，free掉tail尾節(jié)點即可。?
頭插
頭插與尾插原理基本相同，只需要將哨兵位的內(nèi)容進行改變即可。
void LTPushFront(LTNode* phead, LTDataType x)
{
assert(phead);
LTNode* newnode = BuyLTNode(x);
/*newnode->next = phead->next;
phead->next->prev = newhead;
phead->next = newhead;
newhead->prev = phead;*/
LTNode* first = phead->next;
phead->next = newnode;
newnode->prev = phead;
first->prev = newnode;
newnode->next = first;
}
?我們可以參照上述代碼進行頭插，分別有兩種方法。第一種(已注釋)是不創(chuàng)建任何指針變量進行交換替代，第二種(未注釋)即創(chuàng)建變量進行交換。第一種方法再交換次序上必須嚴(yán)謹(jǐn)，先進行尾節(jié)點的交互，再進行首節(jié)點的交互，否則會交換失敗出現(xiàn)錯誤數(shù)據(jù)。
頭刪
在刪除時，務(wù)必檢測鏈表是否為空，鏈表是否只有哨兵位方可進行刪除操作。
void LTPopFront(LTNode* phead)
{
assert(phead);
assert(phead->next != phead);
LTNode* first = phead->next;
LTNode* second = first->next;
free(first);
phead->next = second;
second->prev = phead;
}
計數(shù)函數(shù)實現(xiàn)
當(dāng)我們錄入數(shù)據(jù)量過大時，為了方便計數(shù)所創(chuàng)建的函數(shù)。‘
int LTsize(LTNode* phead)
{
assert(phead);
int size = 0;
LTNode* cur = phead->next;
while (cur != phead)
{
++size;
cur = cur->next;
}
return size;
}這里只需遍歷鏈表種的每一個節(jié)點直到返回到哨兵位即可。
查找數(shù)據(jù)相應(yīng)位置函數(shù)
當(dāng)操作人員想知道某個數(shù)據(jù)在鏈表中的位置并進行操作時，我們即可調(diào)用此函數(shù)來返回相應(yīng)數(shù)據(jù)所在節(jié)點的地址。
LTNode* LTFind(LTNode* phead, LTDataType x)
{
assert(phead);
LTNode* cur = phead->next;
while(cur != phead)
{
if (cur->data == x)
return cur;
}
return NULL;
}這里我們使用暴力查找的算法進行整組鏈表搜索，找到對應(yīng)數(shù)據(jù)即可返回。
在pos位置之前插入?
這里我們就需要與查找位置函數(shù)進行聯(lián)動配合進行調(diào)用。
void LTInsert(LTNode* pos, LTDataType x)
{
assert(pos);
LTNode* posprev = pos->prev;
LTNode* newnode = BuyLTNode(x);
posprev->next = newnode;
newnode->next = pos;
newnode->prev = posprev;
pos->prev = newnode;
}這里其實與頭插尾插原理一樣，所以我們也可以用此函數(shù)進行頭插尾插，只需將pos參數(shù)傳入正確，分別為phead->next(頭插)、phead->prev(尾插)。
在pos位置刪除?
void LTErase(LTNode* pos)
{
assert(pos);
LTNode* posprev = pos->prev;
LTNode* posnext = pos->next;
free(pos);
posprev->next = posnext;
posnext->prev = posprev;
}這里也是與頭刪尾刪原理相同，只需將參數(shù)傳入正確即可變成頭刪和尾刪。
順序表與鏈表的差別
文章來源：http://www.zghlxwxcb.cn/news/detail-634508.html
所以在不同情況下選擇不同的數(shù)據(jù)結(jié)構(gòu)時是很關(guān)鍵的，我們需要足夠了解其中的差別與優(yōu)勢，才能滿足各種問題下不同的需求。文章來源地址http://www.zghlxwxcb.cn/news/detail-634508.html
到了這里，關(guān)于玩轉(zhuǎn)帶頭雙向鏈表——【數(shù)據(jù)結(jié)構(gòu)】的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
