1.前言
? ? ??博主CSDN:杭電碼農(nóng)-NEO????????
?
? ? ?專欄分類:數(shù)據(jù)結(jié)構(gòu)學(xué)習(xí)分享(持續(xù)更新中??)???????
?
? ? 我們上一期說到,兩鏈表中有兩個(gè)最常用的結(jié)構(gòu),一個(gè)是最簡(jiǎn)單的無頭不循環(huán)單向鏈表,還有一個(gè)就是 結(jié)構(gòu)相對(duì)比較復(fù)雜的帶頭雙向循環(huán)鏈表 ,我們這一章節(jié)就來分享雙向帶頭循環(huán)鏈表的具體實(shí)現(xiàn):
要看所有代碼的朋友:? ? ? ? ?? 我的碼云放在了最后 ??
2. 結(jié)構(gòu)分析
與我們上一章講的單鏈表不同,這里雙向帶頭循環(huán)鏈表的結(jié)構(gòu)要復(fù)雜一點(diǎn),主要需要注意這幾個(gè)點(diǎn):
- 定義結(jié)構(gòu)體時(shí),單鏈表只需要定義一個(gè)指針next,雙鏈表需要定義額外一個(gè)指針:prev用來指向上一個(gè)節(jié)點(diǎn)
- 帶頭(帶哨兵位)的鏈表在初始化時(shí)就要給哨兵位開辟一份空間,并且哨兵位不存儲(chǔ)數(shù)據(jù),第一個(gè)節(jié)點(diǎn)要鏈接在哨兵位的下一個(gè)位置
- 循環(huán)的鏈表的尾節(jié)點(diǎn)的next不能指向NULL,要指向第一個(gè)節(jié)點(diǎn),形成循環(huán)結(jié)構(gòu)
- 我們?cè)谶M(jìn)行插入刪除的時(shí)候可以不傳二級(jí)指針!因?yàn)槲覀儞碛辛松诒蛔鳛槲覀冎羔樦赶虻牡谝粋€(gè)位置,并且哨兵位是不會(huì)改變的!
- 不循環(huán)的鏈表判斷尾節(jié)點(diǎn)是cur->next == NULL時(shí),然而循環(huán)的帶頭鏈表判斷尾節(jié)點(diǎn)是cur->next==head時(shí),這里的head指的是哨兵位
3. 雙鏈表的實(shí)現(xiàn)
單鏈表我們使用的名字是SList,意為single list 就是單個(gè)的意思,這里我們直接用List表示雙鏈表
3.1 初始化結(jié)構(gòu)
#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<malloc.h>
typedef int LTDateType;//隨時(shí)可以改變類型
typedef struct ListNode
{
LTDateType data;
struct ListNode* prev;//指向上一個(gè)節(jié)點(diǎn)
struct ListNode* next;//指向下一個(gè)節(jié)點(diǎn)
}LTNode;//簡(jiǎn)化名字
3.2 初始化函數(shù)
在我們寫初始化函數(shù)之前我們要先明白一點(diǎn),那就是當(dāng)鏈表為空時(shí),我們哨兵位的next和prev都指向自己本身!
LTNode* ListInit()
{
LTNode* phead = (LTNode*)malloc(sizeof(LTNode));//為哨兵位開辟一個(gè)節(jié)點(diǎn)
phead->next = phead;
phead->prev = phead;
return phead;//將phead返回后,在test.c文件中賦值給結(jié)構(gòu)體指針
}
void TestList1()
{
LTNode* plist = ListInit();//plist里面存儲(chǔ)一個(gè)哨兵位
}
3.3 尾插函數(shù)
我們說存儲(chǔ)數(shù)據(jù)的結(jié)構(gòu)都離不開增刪查改,這里我們定義的雙向帶頭循環(huán)鏈表進(jìn)行增刪查改是很簡(jiǎn)單的
void ListPushBack(LTNode* phead, LTDateType x)//尾插
{
assert(phead);
LTNode* newnode = (LTNode*)malloc(sizeof(LTNode));//為插入的數(shù)據(jù)開辟空間
if (newnode == NULL)//這個(gè)if語句是為了判斷我們的動(dòng)態(tài)開辟空間有沒有失敗
{
printf("fail");
exit(-1);
}
newnode->data = x;//將數(shù)據(jù)x給上
LTNode* tail = phead->prev;//這里也可以不定義tail,直接用phead->prev表示尾
tail->next = newnode;//尾節(jié)點(diǎn)與新節(jié)點(diǎn)相連
newnode->prev = tail;//新的尾節(jié)點(diǎn)的prev與舊的尾相連
newnode->next = phead;//新的尾節(jié)點(diǎn)與頭相連形成循環(huán)
phead->prev = newnode;
}
我們發(fā)現(xiàn)當(dāng)我們定義鏈表結(jié)構(gòu)為雙向帶頭循環(huán)鏈表時(shí),插入數(shù)據(jù)是很方便的,只需要判斷好鏈接關(guān)系就可以了,而我們之前的單鏈表還需要判斷鏈表為空的情況,這種情況要拿出來特殊處理,但是這個(gè)地方當(dāng)鏈表為空時(shí)也是沒有問題的!
3.4 尾刪函數(shù)
我們有了之前的基礎(chǔ)后,直接上代碼!
void ListPopBack(LTNode* phead)
{
assert(phead);
assert(phead->next != phead);//不能把哨兵為給刪除了
LTNode* tail = phead->prev;
LTNode* prev = tail->prev;//后面就處理鏈接關(guān)系
free(tail);
tail = NULL;
prev->next = phead;
phead->prev = prev;
}
值得注意的是,這里的assert(phead->next!=phead)是當(dāng)我們的phead->next等于自己本身時(shí),代表我們鏈表中已經(jīng)沒有數(shù)據(jù)了,只剩下一個(gè)哨兵位了.這時(shí)需要斷言報(bào)錯(cuò) ??????
3.5 頭插函數(shù)
void ListPushFront(LTNode* phead, LTDateType x)
{
assert(phead);
LTNode* newnode = (LTNode*)malloc(sizeof(LTNode));//只要是插入數(shù)據(jù)就需要開辟空間
newnode->data = x;
LTNode* next = phead->next;//頭插相當(dāng)于就是插入在哨兵位后面
phead->next = newnode;//注意鏈接關(guān)系別寫漏就沒問題
newnode->prev = phead;
newnode->next = next;
next->prev = newnode;
}
同樣的,當(dāng)我們鏈表中沒有數(shù)據(jù)時(shí),這時(shí)的頭插也是沒有問題的,這里我就不做過多說明
3.6 頭刪函數(shù)
void ListPopFront(LTNode* phead)
{
assert(phead);
assert(phead->next != phead);
LTNode* next = phead->next;
phead->next = next->next;
next->next->prev = phead;
free(next);
next = NULL;
}
頭刪和尾刪一樣,不能把哨兵位一起刪了,并且需要注意一點(diǎn),我們的free不能太早使用,不然我們就找不到我們next的next和next的prev了,所以我們要把所有鏈接關(guān)系全部修改完之后,才能把next的空間給釋放掉
3.7 銷毀鏈表
void ListDestroy(LTNode* phead)
{
assert(phead);
LTNode* cur = phead->next;
while (cur!=phead)//釋放掉所有的數(shù)據(jù)空間
{
LTNode* next = cur->next;//這里需要定義一個(gè)next指針,因?yàn)槲覀儼裞ur給釋放掉后就找不到cur->next的了
free(cur);
cur = next;
}
free(phead);//最后將哨兵位也釋放掉,然后置空
phead = NULL;
}
3.8 其他函數(shù)
這里我給出幾個(gè)除了頭插頭刪,尾插尾刪的函數(shù).
- Find函數(shù):返回與x值相同的節(jié)點(diǎn)
LTNode* ListFind(LTNode* phead, LTDateType x)
{
assert(phead);
LTNode* cur = phead->next;
while ( cur != phead)
{
if (cur->data == x)
{
return cur;
}
cur = cur->next;
}
return NULL;
}
- Insert函數(shù):在pos位置之前插入數(shù)據(jù)
void ListInsert(LTNode* pos, LTDateType x)
{
assert(pos);
LTNode* prev = pos->prev;
LTNode* next = pos->next;
LTNode* newnode = (LTNode*)malloc(sizeof(LTNode));
newnode->data = x;
newnode->prev = prev;
newnode->next = pos;
pos->prev = newnode;
prev->next = newnode;
}
- Erase函數(shù):刪除pos位置的節(jié)點(diǎn)
void ListErase(LTNode* pos)
{
assert(pos);
LTNode* prev = pos->prev;
LTNode* next = pos->next;
prev->next = next;
next->prev = prev;
free(pos);
pos = NULL;
}
4. 緩存利用率
我們上一章總結(jié)順序表和鏈表的區(qū)別的時(shí)候提到:順序表的緩存利用率高,鏈表的緩存利用率低,那么到底什么是緩存利用率?這里我給大家大致提一下:我們的計(jì)算器存在很多存儲(chǔ)方式:
我們?cè)跀?shù)組中開辟空間和在鏈表上開辟空間時(shí),這種緩存的命中是不一樣的,有興趣了解的朋友具體的細(xì)節(jié)可以參考這篇文章CPU緩存知識(shí).
5. 總結(jié)
我們關(guān)于鏈表的知識(shí)的分享就要告一段落了,但是鏈表這一章節(jié)雖然只有兩次分享,但是它在諸多面試題中考察的概率是很高的,特別是單鏈表,因?yàn)槲覀冎绬捂湵硎怯泻芏嗳毕莸?所以在校招和很多OJ題中,單鏈表考察的地方非常之多,建議多刷刷題找找思路,我的專欄單鏈表OJ中也總結(jié)了不少OJ題的思路以及衍生問題,有興趣的朋友可以來指導(dǎo)指導(dǎo).文章來源：http://www.zghlxwxcb.cn/news/detail-439312.html
?? 我的碼云:gitee-杭電碼農(nóng)-NEO??文章來源地址http://www.zghlxwxcb.cn/news/detail-439312.html
到了這里，關(guān)于數(shù)據(jù)結(jié)構(gòu)學(xué)習(xí)分享之雙向鏈表詳解的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
