柚子快報(bào)激活碼778899分享：數(shù)據(jù)結(jié)構(gòu) C語(yǔ)言實(shí)現(xiàn)雙向鏈表
柚子快報(bào)激活碼778899分享：數(shù)據(jù)結(jié)構(gòu) C語(yǔ)言實(shí)現(xiàn)雙向鏈表
前言
? ? ? ?在講雙向鏈表之前，我會(huì)先總結(jié)一下前面的知識(shí)點(diǎn)，如需直接看雙向鏈表的，可以直接跳轉(zhuǎn)到雙向鏈表的實(shí)現(xiàn)去閱讀~~
鏈表的分類
? ? ? ?在上一篇的8道算法題，我提到了用哨兵位可以很好地進(jìn)行插入，這個(gè)哨兵位就是頭結(jié)點(diǎn)！還有在解決約瑟夫問題時(shí)，我提到了使用循環(huán)鏈表的概念，循環(huán)鏈表就是頭尾相連，形成一個(gè)環(huán)。 鏈表的分類有這幾種情況：帶不帶頭（頭結(jié)點(diǎn)==哨兵位），單向還是雙向（就是一個(gè)節(jié)點(diǎn)只能找到下一個(gè)節(jié)點(diǎn)的就是單向，如果既能找到上一個(gè)節(jié)點(diǎn)又能找到下一個(gè)節(jié)點(diǎn)就是雙向），循環(huán)還是不循環(huán)（頭尾相連的就是循環(huán)，頭尾不相連的就是不循環(huán)）
所以鏈表一共有八大類，那我們回顧一下什么是單鏈表，單鏈表實(shí)際上就是不帶頭單向不循環(huán)的鏈表，這里我要講的雙向鏈表實(shí)際上是帶頭雙向循環(huán)的鏈表，只要我們會(huì)這兩個(gè)鏈表的實(shí)現(xiàn)，其他的鏈表實(shí)現(xiàn)也是很簡(jiǎn)單的~~
鏈表的優(yōu)勢(shì)
? ? ? ?在C語(yǔ)言進(jìn)階的第一篇文章中，我?guī)Т蠹覍?shí)現(xiàn)了動(dòng)態(tài)順序表，但是動(dòng)態(tài)順序表還是有存在空間浪費(fèi)的出現(xiàn)，舉個(gè)例子，我一共有101個(gè)數(shù)據(jù)需要保存，但是順序表在第一百零一的時(shí)候會(huì)進(jìn)行2倍或3倍擴(kuò)容，假設(shè)擴(kuò)2倍，那就是變成200容量，這時(shí)候就有99個(gè)空間浪費(fèi)了，鏈表就可以實(shí)現(xiàn)一個(gè)數(shù)據(jù)一個(gè)數(shù)據(jù)的申請(qǐng)節(jié)點(diǎn)，不會(huì)有空間的浪費(fèi)，但是單鏈表有一個(gè)缺陷，尾插尾刪等操作時(shí)需要遍歷所有節(jié)點(diǎn)導(dǎo)致效率不高，這時(shí)候我們就可以使用雙向鏈表來大幅減少這種遍歷的出現(xiàn)，也就是我會(huì)在下面提到的鏈表結(jié)構(gòu)。
但是鏈表也有一個(gè)缺點(diǎn)，在數(shù)據(jù)量少的情況下，鏈表其實(shí)浪費(fèi)的空間可能更大，因?yàn)殒湵斫Y(jié)構(gòu)是需要帶一個(gè)或者兩個(gè)指針的~~
任何事物都有兩面性，我們需要根據(jù)實(shí)際情況來選擇合適的數(shù)據(jù)結(jié)構(gòu)來解決問題才是最perfect?。?！
雙向鏈表的實(shí)現(xiàn)
雙向鏈表的含義
? ? ? ?雙向鏈表是帶頭結(jié)點(diǎn)（哨兵位），每一個(gè)結(jié)點(diǎn)都能找到前一個(gè)和后一個(gè)節(jié)點(diǎn)，并且頭尾是相連的。形成帶頭雙向循環(huán)的鏈表，雙向鏈表就是它的簡(jiǎn)稱。
那我們來定義雙向鏈表的結(jié)構(gòu)體：
typedef int ListDataType;
typedef struct ListNode
{
ListDataType data;
struct ListNode* next;
struct ListNode* prev;
}ListNode;
初始化和創(chuàng)建新節(jié)點(diǎn)
? ? ? ?注意雙向鏈表是一個(gè)帶頭的循環(huán)的鏈表，帶頭意味著我們?cè)诔跏蓟獎(jiǎng)?chuàng)建一個(gè)頭結(jié)點(diǎn)，那頭結(jié)點(diǎn)的兩個(gè)指針怎么處理？由于這是雙向鏈表，需要頭尾相連，因此我們將頭節(jié)點(diǎn)的兩個(gè)指針都指向自己！既然如此，我們就寫一個(gè)函數(shù)來創(chuàng)建新節(jié)點(diǎn)，讓每個(gè)新節(jié)點(diǎn)的指針開始都指向自己~~
//創(chuàng)建新節(jié)點(diǎn)
ListNode* CreatNewnode(ListDataType x)
{
ListNode* newnode = (ListNode*)malloc(sizeof(ListNode));
if (newnode == NULL)
{
perror("malloc fail"); exit(1);
}
newnode->data = x;
newnode->next = newnode->prev = newnode;
return newnode;
}
注意了，由于創(chuàng)建新節(jié)點(diǎn)的函數(shù)我們需要傳入一個(gè)值，那我們的頭結(jié)點(diǎn)就隨便傳入一個(gè)值，但是我們自己要知道頭結(jié)點(diǎn)知識(shí)一個(gè)站崗的，不會(huì)存放有效值。 會(huì)不會(huì)有人會(huì)問，為什么不專門寫一個(gè)函數(shù)來創(chuàng)建頭結(jié)點(diǎn)，你可以自己嘗試，我覺得沒有必要，多寫一個(gè)和創(chuàng)建新節(jié)點(diǎn)的代碼感覺很浪費(fèi)也沒有很大必要~~
//初始化
void ListInit(ListNode** pphead)
{
*pphead = CreatNewnode(-1);
}
頭指針的傳參問題
我們要知道初始化鏈表的時(shí)候就創(chuàng)建好頭結(jié)點(diǎn)了，頭指針就是指向這個(gè)頭結(jié)點(diǎn)，所以我們不需要改變頭結(jié)點(diǎn)，它是一個(gè)放哨的，與鏈表是共存亡的，所以我們一般情況下傳一級(jí)指針就可以了~~ 簡(jiǎn)單來說：頭指針是指向頭結(jié)點(diǎn)的，只要頭結(jié)點(diǎn)還存在，頭指針就沒有必要發(fā)生改變~~
尾插
尾插操作，我們需要改變?nèi)齻€(gè)節(jié)點(diǎn)，分別是newnode，head，還有原來的尾節(jié)點(diǎn)head->prev。
//尾插
void ListPushBack(ListNode* phead, ListDataType x)
{
ListNode* newnode = CreatNewnode(x);
newnode->prev = phead->prev;
newnode->next = phead;
phead->prev->next = newnode;
phead->prev = newnode;
}
這里建議大家先將newnode 的next和prev兩個(gè)指針先連接好，畢竟改變newnode的指向不會(huì)影響到另外兩個(gè)節(jié)點(diǎn)，這時(shí)候我們就要考慮剩下兩個(gè)節(jié)點(diǎn)怎么連接，為了避免找不到d3這個(gè)節(jié)點(diǎn)，所以我先改變d3這個(gè)節(jié)點(diǎn)，再改變head的節(jié)點(diǎn)~~
頭插
頭插，我們需要改變?nèi)齻€(gè)節(jié)點(diǎn)，newnode，head，d1；我們還是先改變newnode（不會(huì)對(duì)另外兩個(gè)產(chǎn)生影響），再改變d1（防止改變head的時(shí)候找不到d1），最后改變head。
//頭插
void ListPushFront(ListNode* phead, ListDataType x)
{
ListNode* newnode = CreatNewnode(x);
newnode->prev = phead;
newnode->next = phead->next;
phead->next->prev = newnode;
phead->next = newnode;
}
打印
注意頭結(jié)點(diǎn)存放的值是無(wú)效的，所以從頭結(jié)點(diǎn)的下一個(gè)結(jié)點(diǎn)開始打印，由于鏈表是循環(huán)的，所以當(dāng)回到頭結(jié)點(diǎn)的時(shí)候就要停止打?。ㄑh(huán)停止的條件）
//打印
void ListPrint(ListNode* phead)
{
ListNode* pcur = phead->next;
while (pcur != phead)
{
printf("%d->", pcur->data);
pcur = pcur->next;
}
printf("\n");
}
尾刪
為了更好的進(jìn)行刪除操作，我使用一個(gè)變量保存要?jiǎng)h除的節(jié)點(diǎn)，便于要?jiǎng)h除的節(jié)點(diǎn)的前一個(gè)節(jié)點(diǎn)與頭結(jié)點(diǎn)進(jìn)行連接~~
//尾刪
void ListPopBack(ListNode* phead)
{
assert(phead && phead->next != phead);
ListNode* del = phead->prev;
del->prev->next = phead;
phead->prev = del->prev;
free(del);
del = NULL;
}
頭刪
注意這里的頭刪是刪除第一個(gè)有效的節(jié)點(diǎn)，不是我們的哨兵位！?。?/p>
還是一樣，使用一個(gè)變量保存要?jiǎng)h除的節(jié)點(diǎn)
//頭刪
void ListPopFront(ListNode* phead)
{
assert(phead && phead->next != phead);
ListNode* del = phead->next;
phead->next = del->next;
del->next->prev = phead;
free(del);
del = NULL;
}
查找
從第一個(gè)有效節(jié)點(diǎn)開始遍歷鏈表進(jìn)行查找即可~~
//查找
ListNode* ListFind(ListNode* phead, ListDataType x)
{
ListNode* pcur = phead->next;
while (pcur != phead)
{
if (pcur->data == x)
{
return pcur;
}
pcur = pcur->next;
}
return NULL;
}
寫這一個(gè)查找函數(shù)是為了方便我們后續(xù)指定位置的相關(guān)操作~~ 還有要注意如果找不到就會(huì)放回NULL，所以后面的指定位置操作是記得判斷pos是否有效?。?！
指定位置刪除
需要改變?nèi)齻€(gè)節(jié)點(diǎn)pos，pos->prev，pos->next這三個(gè)節(jié)點(diǎn)~~
//指定位置刪除
void ListPopPos(ListNode* pos)
{
assert(pos);
pos->prev->next = pos->next;
pos->next->prev = pos->prev;
free(pos);
pos = NULL;
}
這里要注意了pos 如果就是頭指針的話，是不可以進(jìn)行刪除操作的，由于我沒有傳頭指針，所以沒有判斷這個(gè)條件~~
刪除指定位置之前的數(shù)據(jù)
這里要注意，指定位置之前需要有有效的節(jié)點(diǎn)才能進(jìn)行刪除！??！所以這里你可以判斷一下，傳入頭指針是為了更好地進(jìn)行判斷處理~~
//刪除指定位置前的數(shù)據(jù)
void ListPopPosFront(ListNode* phead, ListNode* pos)
{
assert(phead);
assert(pos && pos->prev != phead);
ListNode* del = pos->prev;
del->prev->next = pos;
pos->prev = del->prev;
free(del);
del = NULL;
}
刪除指定位置之后的數(shù)據(jù)
這里要注意，指定位置之后需要有有效的節(jié)點(diǎn)才能進(jìn)行刪除?。?！所以這里你可以判斷一下，傳入頭指針是為了更好地進(jìn)行判斷處理~~
//刪除指定位置之后的數(shù)據(jù)
void ListPopPosAfter(ListNode* phead, ListNode* pos)
{
assert(phead);
assert(pos && pos->next != phead);
ListNode* del = pos->next;
del->next->prev = pos;
pos->next = del->next;
free(del);
del = NULL;
}
在指定位置之前插入數(shù)據(jù)
//在指定位置之前插入數(shù)據(jù)
void ListPushPosFront(ListNode* pos, ListDataType x)
{
assert(pos);
ListNode* newnode = CreatNewnode(x);
newnode->next = pos;
newnode->prev = pos->prev;
pos->prev->next = newnode;
pos->prev = newnode;
}
在指定位置之后插入數(shù)據(jù)
//在指定位置之后插入數(shù)據(jù)
void ListPushPosAfter(ListNode* pos, ListDataType x)
{
assert(pos);
ListNode* newnode = CreatNewnode(x);
newnode->prev = pos;
newnode->next = pos->next;
pos->next->prev = newnode;
pos->next = newnode;
}
銷毀鏈表
銷毀鏈表我們需要傳入頭結(jié)點(diǎn)的二級(jí)指針了，因?yàn)轭^結(jié)點(diǎn)也需要進(jìn)行銷毀，頭指針要置為NULL 但是這里我卻使用了一級(jí)指針，是為了保持接口的一致性~~ 因?yàn)樯厦娴暮瘮?shù)除了初始化都是傳一級(jí)指針，也是為了方便別人來使用我們的接口函數(shù)，減少使用者的記憶負(fù)擔(dān)~~
//銷毀鏈表
void ListDestroy(ListNode* phead)
{
assert(phead);
ListNode* pcur = phead->next;
while (pcur != phead)
{
ListNode* next = pcur->next;
free(pcur);
pcur = next;
}
free(phead);
phead = NULL;
}
如果你還想讓接口函數(shù)更加完美，我們可以改變一下初始化函數(shù)的：
//初始化
ListNode* ListInit()
{
ListNode* phead = CreatNewnode(-1);
return phead;
}
小結(jié)
在實(shí)現(xiàn)雙向鏈表的時(shí)候，我們可以通過畫圖理解的方式進(jìn)行理解和書寫相應(yīng)的代碼~~
封裝函數(shù)
List.h
#pragma once
#include
#include
#include
typedef int ListDataType;
typedef struct ListNode
{
ListDataType data;
struct ListNode* next;
struct ListNode* prev;
}ListNode;
//初始化
void ListInit(ListNode** pphead);
//打印
void ListPrint(ListNode* phead);
//插入
void ListPushBack(ListNode* phead, ListDataType x);
void ListPushFront(ListNode* phead, ListDataType x);
//刪除
void ListPopBack(ListNode* phead);
void ListPopFront(ListNode* phead);
//查找
ListNode* ListFind(ListNode* phead, ListDataType x);
//指定位置刪除
void ListPopPos(ListNode* pos);
//刪除指定位置前的數(shù)據(jù)
void ListPopPosFront(ListNode* phead, ListNode* pos);
//刪除指定位置之后的數(shù)據(jù)
void ListPopPosAfter(ListNode* phead, ListNode* pos);
//在指定位置前插入數(shù)據(jù)
void ListPushPosFront(ListNode* pos, ListDataType x);
//在指定位置之后插入數(shù)據(jù)
void ListPushPosAfter(ListNode* pos, ListDataType x);
//銷毀鏈表
void ListDestroy(ListNode* phead);
List.c
#include "List.h"
//創(chuàng)建新節(jié)點(diǎn)
ListNode* CreatNewnode(ListDataType x)
{
ListNode* newnode = (ListNode*)malloc(sizeof(ListNode));
if (newnode == NULL)
{
perror("malloc fail"); exit(1);
}
newnode->data = x;
newnode->next = newnode->prev = newnode;
return newnode;
}
//初始化
void ListInit(ListNode** pphead)
{
*pphead = CreatNewnode(-1);
}
//尾插
void ListPushBack(ListNode* phead, ListDataType x)
{
ListNode* newnode = CreatNewnode(x);
newnode->prev = phead->prev;
newnode->next = phead;
phead->prev->next = newnode;
phead->prev = newnode;
}
//打印
void ListPrint(ListNode* phead)
{
ListNode* pcur = phead->next;
while (pcur != phead)
{
printf("%d->", pcur->data);
pcur = pcur->next;
}
printf("\n");
}
//頭插
void ListPushFront(ListNode* phead, ListDataType x)
{
ListNode* newnode = CreatNewnode(x);
newnode->prev = phead;
newnode->next = phead->next;
phead->next->prev = newnode;
phead->next = newnode;
}
//尾刪
void ListPopBack(ListNode* phead)
{
assert(phead && phead->next != phead);
ListNode* del = phead->prev;
del->prev->next = phead;
phead->prev = del->prev;
free(del);
del = NULL;
}
//頭刪
void ListPopFront(ListNode* phead)
{
assert(phead && phead->next != phead);
ListNode* del = phead->next;
phead->next = del->next;
del->next->prev = phead;
free(del);
del = NULL;
}
//查找
ListNode* ListFind(ListNode* phead, ListDataType x)
{
ListNode* pcur = phead->next;
while (pcur != phead)
{
if (pcur->data == x)
{
return pcur;
}
pcur = pcur->next;
}
return NULL;
}
//指定位置刪除
void ListPopPos(ListNode* pos)
{
assert(pos);
pos->prev->next = pos->next;
pos->next->prev = pos->prev;
free(pos);
pos = NULL;
}
//刪除指定位置前的數(shù)據(jù)
void ListPopPosFront(ListNode* phead, ListNode* pos)
{
assert(phead);
assert(pos && pos->prev != phead);
ListNode* del = pos->prev;
del->prev->next = pos;
pos->prev = del->prev;
free(del);
del = NULL;
}
//刪除指定位置之后的數(shù)據(jù)
void ListPopPosAfter(ListNode* phead, ListNode* pos)
{
assert(phead);
assert(pos && pos->next != phead);
ListNode* del = pos->next;
del->next->prev = pos;
pos->next = del->next;
free(del);
del = NULL;
}
//在指定位置前插入數(shù)據(jù)
void ListPushPosFront(ListNode* pos, ListDataType x)
{
assert(pos);
ListNode* newnode = CreatNewnode(x);
newnode->next = pos;
newnode->prev = pos->prev;
pos->prev->next = newnode;
pos->prev = newnode;
}
//在指定位置之后插入數(shù)據(jù)
void ListPushPosAfter(ListNode* pos, ListDataType x)
{
assert(pos);
ListNode* newnode = CreatNewnode(x);
newnode->prev = pos;
newnode->next = pos->next;
pos->next->prev = newnode;
pos->next = newnode;
}
//銷毀鏈表
void ListDestroy(ListNode* phead)
{
assert(phead);
ListNode* pcur = phead->next;
while (pcur != phead)
{
ListNode* next = pcur->next;
free(pcur);
pcur = next;
}
free(phead);
phead = NULL;
}
雙向鏈表完結(jié)撒花~~
柚子快報(bào)激活碼778899分享：數(shù)據(jù)結(jié)構(gòu) C語(yǔ)言實(shí)現(xiàn)雙向鏈表
精彩內(nèi)容
本文內(nèi)容根據(jù)網(wǎng)絡(luò)資料整理，出于傳遞更多信息之目的，不代表金鑰匙跨境贊同其觀點(diǎn)和立場(chǎng)。
轉(zhuǎn)載請(qǐng)注明，如有侵權(quán)，聯(lián)系刪除。
TubeMarket國(guó)際視頻購(gòu)
