目錄
1.單向鏈表的劣勢
2.帶頭雙向循環(huán)鏈表
? ? ? ? 1.邏輯結(jié)構(gòu)
? ? ? ?2.結(jié)點的代碼實現(xiàn)
3.雙向鏈表接口的實現(xiàn)
????????1.接口1---初始化
????????2.接口2，3---頭插，尾插
????????3. 接口4，5---頭刪，尾刪
????????3. 接口6---查找
?????????4. 接口7，8--插入，刪除
????????5.?接口8---打印
????????6.?接口9--銷毀
4.完整代碼及效果展示?
1.單向鏈表的劣勢
? ? ? ? 上期我們講解了鏈表8種結(jié)構(gòu)中最為常用的兩種結(jié)構(gòu)之一的單向不帶頭不循環(huán)鏈表的基本概念和實現(xiàn)方法（傳送門：動圖詳解單向鏈表）。但是在實現(xiàn)時我們發(fā)現(xiàn)了以下局限性：
- 由于單鏈表是單向的，當(dāng)我們想進行插入或者刪除時，由于無法直接找到前驅(qū)結(jié)點，導(dǎo)致我們還需再使用一個指針遍歷鏈表找到前一個結(jié)點的位置。這就導(dǎo)致了進行插入和刪除的時間復(fù)雜度為O(N)，時間效率較低。
- 由于我們需要再使用一個指針指向鏈表前一個結(jié)點，這也可能在一些情況下導(dǎo)致出錯，例如鏈表只有一個結(jié)點。（詳情請見上一期，含動圖分析）
- 由于其不帶頭結(jié)點，頭指針直接指向第一個有效結(jié)點，所以在進行頭插等可能改變頭指針的操作時我們?nèi)绻麄饕患壷羔樉蜁鲥e。
2.帶頭雙向循環(huán)鏈表
? ? ? ? 1.邏輯結(jié)構(gòu)
? ? ? ? 那么，我們要如何解決以上劣勢呢？這就不得不說到另一種最為常見的鏈表結(jié)構(gòu)：帶頭雙向循環(huán)鏈表。
? ? ? ? 頭結(jié)點：所謂頭結(jié)點，其作用就是標(biāo)識鏈表的有效部分。我們之前實現(xiàn)的無頭結(jié)點的鏈表，都是通過頭指針直接指向鏈表的有效數(shù)據(jù)部分。而帶頭結(jié)點的鏈表，則是用頭指針指向一個不存放有效數(shù)據(jù)的結(jié)點，這個結(jié)點就稱作頭結(jié)點。這個結(jié)點的next指針存放的下一個結(jié)點才是鏈表的有效結(jié)點部分。圖示如下：
??????????帶頭雙向循環(huán)鏈表：其結(jié)構(gòu)是8種結(jié)構(gòu)中最復(fù)雜的，一般用在單獨存儲數(shù)據(jù)。實際中使用的鏈表數(shù)據(jù)結(jié)構(gòu)，都是帶頭雙向循環(huán)鏈表。此鏈表的結(jié)點在單向鏈表的基礎(chǔ)上，添加了前驅(qū)指針prev指向上一個結(jié)點，然后添加了上述所描述的頭結(jié)點，而循環(huán)則是體現(xiàn)在首尾結(jié)點相連上。另外這個結(jié)構(gòu)雖然結(jié)構(gòu)復(fù)雜，但是使用代碼實現(xiàn)以后會發(fā)現(xiàn)結(jié)構(gòu)會帶來很多優(yōu)勢，實現(xiàn)起來反而更加簡單。邏輯結(jié)構(gòu)如下：
注：藍色箭頭代表邏輯上指針的指向，均表示某個結(jié)點next或prev指針指向另一個結(jié)點，下同。
? ? ? ?2.結(jié)點的代碼實現(xiàn)
? ? ? ? 根據(jù)單向鏈表結(jié)點的代碼實現(xiàn)和雙向鏈表的結(jié)構(gòu)體，我們可以得出其結(jié)點的結(jié)構(gòu)體定義如下：
3.雙向鏈表接口的實現(xiàn)
? ? ? ? 我們同樣先在主函數(shù)中定義一個頭指針用于指向我們的頭結(jié)點，后續(xù)通過這個指針來完成對鏈表各種接口的實現(xiàn)。由于頭指針并不直接指向有效數(shù)據(jù)部分，有效數(shù)據(jù)是從第二個結(jié)點開始的，因此當(dāng)我們對數(shù)據(jù)進行操作時并不需要改變頭指針的內(nèi)容，只需進行傳值調(diào)用，用一級指針接收即可，可以有效避免頭指針被無意修改。
????????1.接口1---初始化
? ? ? ? 在使用鏈表前，我們需要對鏈表進行初始化。我們可以在初始化接口中創(chuàng)建一個頭結(jié)點并將其返回給頭指針，代碼如下：
//用于創(chuàng)建新結(jié)點
ListNode* CreatNode(ListDateType x)
{
ListNode* cur=(ListNode*)malloc(sizeof(ListNode));
cur->date = x;
cur->next = NULL;
cur->prev = NULL;
return cur;
}
//鏈表初始化
ListNode* InitList()
{
ListNode* phead=CreatNode(0); //創(chuàng)建頭結(jié)點
phead->next = phead; //前驅(qū)指針指向自身
phead->prev = phead; //后繼指針指向自身
return phead; //將這個結(jié)點返回
}????????2.接口2，3---頭插，尾插
? ? ? ? 對于頭插，根據(jù)雙向循環(huán)鏈表結(jié)構(gòu)圖，我們只需將頭結(jié)點的next指向新結(jié)點，新結(jié)點的prev指向頭結(jié)點，next指向下一結(jié)點，下一結(jié)點的prev指向新結(jié)點即可完成頭插。具體過程如下：
? ? ? ? ?代碼實現(xiàn)如下：
//頭插
void ListPushFront(ListNode* phead, ListDateType x) //不改變頭指針，無需傳址
{
assert(phead != NULL); //保證鏈表有頭結(jié)點，即完成了初始化
ListNode* NewNode = CreatNode(x); //創(chuàng)建新結(jié)點
ListNode* frist = phead->next; //找到鏈表頭
//進行頭插
phead->next = NewNode;
NewNode->prev = phead;
NewNode->next = frist;
frist->prev = NewNode;
}?????????對于尾插，由于雙向循環(huán)鏈表結(jié)構(gòu)的特殊性，我們不需要向單鏈表一樣遍歷鏈表找到鏈表尾，直接通過頭結(jié)點的prev指針就可直接找到鏈表尾，也不需要再遍歷鏈表找到上一個結(jié)點。代碼反而變得更加簡單，只需要通過改變結(jié)點的prev和next指針即可完成尾插，這就是結(jié)構(gòu)帶來的優(yōu)勢。其時間復(fù)雜度為O(1)。具體過程如下：
? ? ? ? 具體代碼如下：?
//尾插
void ListPushBack(ListNode* phead, ListDateType x)
{
assert(phead != NULL); //保證鏈表已經(jīng)初始化
ListNode* NewNode = CreatNode(x); //創(chuàng)建新結(jié)點
ListNode* tail = phead->prev; //找到鏈表尾
//進行尾插
tail->next = NewNode;
NewNode->prev = tail;
NewNode->next = phead;
phead->prev = NewNode;
}需要注意的是，與單鏈表不同，這里是雙向循環(huán)鏈表，所以鏈表尾并不是指向NULL，而是指向頭結(jié)點。同時不會出現(xiàn)對NULL解引用的情況，不需要對單向鏈表一樣進行分類討論。
????????3. 接口4，5---頭刪，尾刪
? ? ? ??對于頭刪，我們只需要將頭結(jié)點指向下一個位置，然后將原來指向的空間free()掉即可。如果鏈表為空，我們就讓函數(shù)直接返回，具體動態(tài)效果如下：
? ? ? ? ?代碼實現(xiàn)如下：
//頭刪
void ListPopFront(ListNode* phead)
{
assert(phead != NULL); //確保鏈表初始化
if (phead->next == phead)
{
return; //鏈表為空直接返回，防止把頭結(jié)點刪除
}
ListNode* frist = phead->next; //找到鏈表頭
ListNode* second = frist->next; //找到鏈表頭下一個結(jié)點
//進行頭刪
phead->next = second;
second->prev = phead;
free(frist); //釋放結(jié)點
frist = NULL;
}????????對于尾刪，我們同樣通過頭結(jié)點的prev指針直接找到鏈表尾，然后進行刪除操作，過程與頭刪類似，時間復(fù)雜度為O(1)。具體過程如下：
? ? ? ? 具體代碼如下：
//尾刪
void ListPopBack(ListNode* phead)
{
assert(phead != NULL); //確保鏈表已經(jīng)初始化
if (phead->next == phead)
{
return; //鏈表為空直接返回，防止把頭結(jié)點刪除
}
ListNode* tail = phead->prev; //找到鏈表尾
ListNode* prev = tail->prev; //找到前驅(qū)
//進行尾刪
phead->prev = prev;
prev->next = phead;
free(tail); //釋放空間
tail = NULL;
}????????3. 接口6---查找
? ? ? ? 對于查找，其方法與單向鏈表一樣，通過遍歷鏈表的所有結(jié)點即可。有一點不同的是我們的雙向鏈表是循環(huán)的，因此循環(huán)的條件不再是cur！=NULL而是cur！=phead，當(dāng)cur等于頭指針時則說明已經(jīng)成功遍歷一遍了。代碼如下：
//查找
ListNode* ListFind(ListNode* phead, ListDateType x)
{
assert(phead != NULL); //確保已經(jīng)初始化
ListNode* cur = phead->next; //指向第一個有效結(jié)點，準(zhǔn)備遍歷
while (cur != phead) //遍歷一圈
{
if (cur->date == x)
{
return cur; //找到了，返回結(jié)點
}
cur = cur->next; //指向下一結(jié)點
}
//找不到，返回空指針
return NULL;
}?????????4. 接口7，8--插入，刪除
? ? ? ? 對于插入，我們可以實現(xiàn)一個在指定結(jié)點前插入一個新結(jié)點的接口，而這個指定結(jié)點我們可以通過查找接口來獲取。由于我們的鏈表是雙向的，我們就可以很容易的得到新結(jié)點的前一個與后一個結(jié)點的位置，進而實現(xiàn)插入接口，其時間復(fù)雜度為O(1)。動態(tài)效果如下：
//插入
void ListInsert(ListNode* phead, ListNode* pos, ListDateType x)
{
assert(pos != NULL); //確保已經(jīng)初始化
ListNode* NewNode = CreatNode(x); //創(chuàng)建新結(jié)點
ListNode* prev = pos->prev; //前一個結(jié)點
//進行插入
NewNode->next = pos;
pos->prev = NewNode;
prev->next = NewNode;
NewNode->prev = prev;
}? ? ? ? 對于刪除，我們同樣可以實現(xiàn)一個刪除指定結(jié)點的接口，而這個指定結(jié)點我們依舊可以通過查找接口來獲取。同樣的，由于結(jié)構(gòu)上的優(yōu)勢，我們可以很方便的直接對指定位置進行刪除，時間復(fù)雜度為O(1)。具體過程如下：
? ? ? ? 具體代碼如下：?
//刪除
void ListErase(ListNode* phead, ListNode* pos)
{
assert(pos != NULL); //確保已經(jīng)初始化
ListNode* next = pos->next; //后一個結(jié)點
ListNode* prev = pos->prev; //前一個結(jié)點
//進行刪除
prev->next = next;
next->prev = prev;
free(pos); //釋放空間
pos = NULL;
}????????5.?接口8---打印
? ? ? ? 對于打印，很簡單，遍歷一圈鏈表即可，當(dāng)cur等于頭結(jié)點地址時停止打印。動圖效果如下：
? ? ? ? 具體代碼如下：?
//打印
void ListPrint(ListNode* phead)
{
assert(phead != NULL); //確保鏈表已經(jīng)初始化
ListNode* cur = phead->next; //指向有效部分
while (cur != phead) //遍歷一圈
{
printf("%d ", cur->date); //打印數(shù)據(jù)
cur = cur->next; //指向下一結(jié)點
}
printf("\n");
}????????6.?接口9--銷毀
? ? ? ? 對于銷毀，我們動態(tài)內(nèi)存申請所得到的空間，當(dāng)我們不需要的時候，需要我們進行手動銷毀。因此，我們還需要一個接口對使用完畢的鏈表進行free()，具體代碼如下：
//銷毀
void ListDestroy(ListNode* phead)
{
assert(phead != NULL); //確保已經(jīng)初始化
ListNode* cur = phead->next; //指向有效部分
while (cur != phead) //釋放有效結(jié)點
{
ListNode* next = cur->next;
free(cur);
cur = next;
}
//釋放頭結(jié)點
free(phead);
phead = NULL;
}通過上面一個個接口的實現(xiàn)，我們發(fā)現(xiàn)：
? ? ? ? 雖然雙向帶頭循環(huán)鏈表的結(jié)構(gòu)比起單向鏈表結(jié)構(gòu)復(fù)雜太多，但對于各接口的實現(xiàn)反而變得更加方便，并且很多接口時間效率更加地高。因此，一個好的結(jié)構(gòu)不僅可以簡化我們的代碼量，也可以提高我們代碼的效率。
4.完整代碼及效果展示?
? ? ? ? 我們同樣采用多文件編寫的形式，將上述接口的定義實現(xiàn)放在List.c文件中，然后將接口的聲明和結(jié)構(gòu)體的定義放于List.h頭文件中，以達到封裝的效果。這樣我們?nèi)绻枰褂秒p向鏈表，就只需要在文件中包含對應(yīng)的頭文件List.h就可以使用我們上面定義的各種接口。以下為本文實現(xiàn)的帶頭雙向循環(huán)鏈表完整代碼以及效果展示：
//List.h文件，用于聲明接口函數(shù)，定義結(jié)構(gòu)體
#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
typedef int ListDateType; //重命名便于維護
typedef struct ListNode
{
ListDateType date;
struct ListNode* next; //指向前一個結(jié)點
struct ListNode* prev; //指向后一個結(jié)點
}ListNode;
//初始化
ListNode* InitList();
//尾插
void ListPushBack(ListNode* phead, ListDateType x);
//頭插
void ListPushFront(ListNode* phead, ListDateType x);
//尾刪
void ListPopBack(ListNode* phead);
//頭刪
void ListPopFront(ListNode* phead);
//查找
ListNode* ListFind(ListNode* phead, ListDateType x);
//刪除
void ListErase(ListNode* phead, ListNode* pos);
//插入
void ListInsert(ListNode* phead, ListNode* pos, ListDateType x);
//打印
void ListPrint(ListNode * phead);
//銷毀
void ListDestroy(ListNode* phead);//SList.c文件，用于定義接口函數(shù)
#define _CRT_SECURE_NO_WARNINGS 1
#include "List.h"
ListNode* CreatNode(ListDateType x)
{
ListNode* cur=(ListNode*)malloc(sizeof(ListNode));
cur->date = x;
cur->next = NULL;
cur->prev = NULL;
return cur;
}
ListNode* InitList()
{
ListNode* phead = CreatNode(0); //創(chuàng)建頭結(jié)點
phead->next = phead; //前驅(qū)指針指向自身
phead->prev = phead; //后繼指針指向自身
return phead; //將這個結(jié)點返回
}
void ListPushBack(ListNode* phead, ListDateType x)
{
assert(phead != NULL);
ListNode* NewNode = CreatNode(x);
ListNode* tail = phead->prev; //找到鏈表尾
tail->next = NewNode;
NewNode->prev = tail;
NewNode->next = phead;
phead->prev = NewNode;
}
void ListPushFront(ListNode* phead, ListDateType x) //不改變頭指針，無需傳址
{
assert(phead != NULL); //保證鏈表有頭結(jié)點，即完成了初始化
ListNode* NewNode = CreatNode(x); //創(chuàng)建新結(jié)點
ListNode* frist = phead->next; //找到鏈表頭
//進行頭插
phead->next = NewNode;
NewNode->prev = phead;
NewNode->next = frist;
frist->prev = NewNode;
}
void ListPopBack(ListNode* phead)
{
assert(phead != NULL);
if (phead->next == NULL)
{
return; //鏈表為空直接返回
}
ListNode* tail = phead->prev; //找到鏈表尾
ListNode* prev = tail->prev; //找到前驅(qū)
phead->prev = prev;
prev->next = phead;
free(tail);
tail = NULL;
}
void ListPopFront(ListNode* phead)
{
assert(phead != NULL); //確保鏈表初始化
if (phead->next == NULL)
{
return; //鏈表為空直接返回
}
ListNode* frist = phead->next; //找到鏈表頭
ListNode* second = frist->next; //找到鏈表頭下一個結(jié)點
//進行頭刪
phead->next = second;
second->prev = phead;
free(frist); //釋放結(jié)點
frist = NULL;
}
ListNode* ListFind(ListNode* phead, ListDateType x)
{
assert(phead != NULL); //確保已經(jīng)初始化
ListNode* cur = phead->next; //指向第一個有效結(jié)點，準(zhǔn)備遍歷
while (cur != phead) //遍歷一圈
{
if (cur->date == x)
{
return cur; //找到了，返回結(jié)點
}
cur = cur->next; //指向下一結(jié)點
}
//找不到，返回空指針
return NULL;
}
void ListErase(ListNode* phead, ListNode* pos)
{
assert(pos != NULL); //確保已經(jīng)初始化
ListNode* next = pos->next; //后一個結(jié)點
ListNode* prev = pos->prev; //前一個結(jié)點
//進行刪除
prev->next = next;
next->prev = prev;
free(pos); //釋放空間
pos = NULL;
}
void ListInsert(ListNode* phead, ListNode* pos, ListDateType x)
{
assert(pos != NULL); //確保已經(jīng)初始化
ListNode* NewNode = CreatNode(x); //創(chuàng)建新結(jié)點
ListNode* prev = pos->prev; //前一個結(jié)點
//進行插入
NewNode->next = pos;
pos->prev = NewNode;
prev->next = NewNode;
NewNode->prev = prev;
}
void ListPrint(ListNode* phead)
{
assert(phead != NULL); //確保鏈表已經(jīng)初始化
ListNode* cur = phead->next; //指向有效部分
while (cur != phead) //遍歷一圈
{
printf("%d ", cur->date); //打印數(shù)據(jù)
cur = cur->next; //指向下一結(jié)點
}
printf("\n");
}
void ListDestroy(ListNode* phead)
{
assert(phead != NULL); //確保已經(jīng)初始化
ListNode* cur = phead->next; //指向有效部分
while (cur != phead) //釋放有效結(jié)點
{
ListNode* next = cur->next;
free(cur);
cur = next;
}
//釋放頭結(jié)點
free(phead);
phead = NULL;
}? ? ? ?最后， 我們在text.c文件調(diào)用雙向循環(huán)鏈表各個接口進行測試，如下：
//text.c文件，用于測試
#define _CRT_SECURE_NO_WARNINGS 1
#include "List.h"
void ListText()
{
ListNode* plist = NULL;
//初始化
plist = InitList();
printf("鏈表起始數(shù)據(jù):\n");
ListPrint(plist);
//尾插
ListPushBack(plist, 1);
ListPushBack(plist, 2);
ListPushBack(plist, 3);
printf("尾插后數(shù)據(jù):\n");
ListPrint(plist);
//頭插
ListPushFront(plist, 4);
ListPushFront(plist,5);
ListPushFront(plist, 6);
printf("頭插后數(shù)據(jù):\n");
ListPrint(plist);
//尾刪
ListPopBack(plist);
printf("尾刪后數(shù)據(jù):\n");
ListPrint(plist);
//頭刪
ListPopFront(plist);
printf("頭刪后數(shù)據(jù):\n");
ListPrint(plist);
//修改數(shù)據(jù)為5的結(jié)點為50
ListNode* cur1 = ListFind(plist, 5); //找數(shù)據(jù)為5結(jié)點
if (cur1)
{
cur1->date = 50; //查找附帶著修改的作用
}
printf("修改數(shù)據(jù)為5的結(jié)點為50后\n");
ListPrint(plist);
//在date為4的結(jié)點前插入數(shù)據(jù)為7的結(jié)點
ListNode* cur2 = ListFind(plist,4); //找數(shù)據(jù)為4結(jié)點
if (cur2)
{
ListInsert(plist, cur2, 7); //插入
}
printf("在4前插入7后數(shù)據(jù):\n");
ListPrint(plist);
//刪除數(shù)據(jù)為1的結(jié)點
ListNode* cur3 = ListFind(plist, 1); //找數(shù)據(jù)為1結(jié)點
if (cur3)
{
ListErase(plist, cur3); //刪除
}
printf("刪除1后數(shù)據(jù):\n");
ListPrint(plist);
//銷毀
ListDestroy(plist);
}
int main()
{
ListText();
return 0;
}? ? ? ? 以下就是測試的最終效果：
?以上，就是本期的全部內(nèi)容。文章來源：http://www.zghlxwxcb.cn/news/detail-819143.html
制作不易，能否點個贊再走呢qwq文章來源地址http://www.zghlxwxcb.cn/news/detail-819143.html
到了這里，關(guān)于【數(shù)據(jù)結(jié)構(gòu)】動圖詳解雙向鏈表的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
