C語(yǔ)言實(shí)現(xiàn)帶頭雙向循環(huán)鏈表

第C語(yǔ)言實(shí)現(xiàn)帶頭雙向循環(huán)鏈表目錄前言1.創(chuàng)建結(jié)構(gòu)體2.malloc新節(jié)點(diǎn)3.創(chuàng)建哨兵位節(jié)點(diǎn)4.尾插5.打印6.尾刪7.頭插8.在指定位置pos的前面進(jìn)行插入9.刪除指定位置pos節(jié)點(diǎn)10.銷(xiāo)毀鏈表

前言

在實(shí)際生活中最常用的就是這兩種鏈表。無(wú)頭單向非循環(huán)鏈表。和帶頭雙向循環(huán)鏈表。

無(wú)頭單向非循環(huán)鏈表：結(jié)構(gòu)簡(jiǎn)單，一般不會(huì)單獨(dú)用來(lái)存數(shù)據(jù)。實(shí)際中更多是作為其他數(shù)據(jù)結(jié)構(gòu)的子結(jié)構(gòu)，如哈希桶、圖的鄰接表等等。另外這種結(jié)構(gòu)在筆試面試中出現(xiàn)很多。

帶頭雙向循環(huán)鏈表：結(jié)構(gòu)最復(fù)雜，一般用在單獨(dú)存儲(chǔ)數(shù)據(jù)。實(shí)際中使用的鏈表數(shù)據(jù)結(jié)構(gòu)，都是帶頭雙向循環(huán)鏈表。另外這個(gè)結(jié)構(gòu)雖然結(jié)構(gòu)復(fù)雜，但是使用代碼實(shí)現(xiàn)以后會(huì)發(fā)現(xiàn)結(jié)構(gòu)會(huì)帶來(lái)很多優(yōu)勢(shì)，實(shí)現(xiàn)反而簡(jiǎn)單了，后面我們代碼實(shí)現(xiàn)了就知道了。

1.創(chuàng)建結(jié)構(gòu)體

注意：typedef起作用是在第7行哦。所以第5,6還需要寫(xiě)structListNode類(lèi)型。

typedefintLNDataType;

typedefstructListNode

structListNode*prev;

structListNode*next;

LNDataTypeval;

2.malloc新節(jié)點(diǎn)

注意：需判斷新開(kāi)辟的節(jié)點(diǎn)是否為空。

//申請(qǐng)一個(gè)新節(jié)點(diǎn)

LN*BuynewNode(LNDataTypex)

LN*newNode=(LN*)malloc(sizeof(LN));

if(newNode==NULL)

printf("mallocfail");

exit(-1);

newNode-next=NULL;

newNode-prev=NULL;

newNode-val=x;

returnnewNode;

3.創(chuàng)建哨兵位節(jié)點(diǎn)

注意：這里因?yàn)樾枰淖僷list指針的內(nèi)容，也就是改變plist指針的指向，所以需要傳遞plist的地址。

一句話就是：需要改變誰(shuí)的內(nèi)容，就傳誰(shuí)的地址。

這里有一點(diǎn)非常巧非常妙，就是phead的后繼和前驅(qū)都是指向自己（phead），這里是模仿C++STL庫(kù)里的哨兵位節(jié)點(diǎn)。

只能佩服想出來(lái)這些東西的大神。這樣設(shè)計(jì)哨兵位節(jié)點(diǎn)的話，后續(xù)尾插，尾刪，都特別的巧妙。

test.c

LN*plist=NULL;

ListNodeInit(plist);

List.h

//初始化節(jié)點(diǎn)

voidListNodeInit(LN**pphead)

LN*newNode=BuynewNode(0);

*pphead=newNode;

(*pphead)-next=*pphead;

(*pphead)-prev=*pphead;

4.尾插

注意：需要斷言的原因是因?yàn)?，即使鏈表沒(méi)有一個(gè)節(jié)點(diǎn)，那鏈表至少還有個(gè)頭，所以phead肯定不為空。

這里沒(méi)有傳地址的原因是因?yàn)?，你不需要改變plist的指向，你改變的是plist指向的結(jié)構(gòu)體里面的值。

多個(gè)節(jié)點(diǎn)尾插的情況如圖。

一個(gè)節(jié)點(diǎn)的尾插。

//尾插

voidListNodePushBack(LN*phead,LNDataTypex)

assert(phead);

LN*newNode=BuynewNode(x);

LN*tail=phead-prev;

tail-next=newNode;

newNode-prev=tail;

newNode-next=phead;

phead-prev=newNode;

5.打印

注意：因?yàn)閹€(gè)頭，所以cur從第二個(gè)位置開(kāi)始。

//打印

voidListNodePrint(LN*phead)

LN*cur=phead-next;

while(cur!=phead)

printf("%d",cur-val);

cur=cur-next;

printf("\n");

6.尾刪

注意不能刪掉頭結(jié)點(diǎn)，free掉頭結(jié)點(diǎn)的話會(huì)造成野指針，再次訪問(wèn)時(shí)會(huì)造成非法訪問(wèn)。

所以要用assert斷言不為首節(jié)點(diǎn)。

//尾刪

voidListNodePopBack(LN*phead)

assert(phead);

assert(phead-next!=phead);

LN*tail=phead-prev;

LN*tailPrev=tail-prev;

free(tail);

tail=NULL;

phead-prev=tailPrev;

tailPrev-next=phead;

7.頭插

最好用next記錄下一個(gè)節(jié)點(diǎn)。這樣方便，思路清晰

//頭插

voidListNodePushFront(LN*phead,LNDataTypex)

assert(phead);

LN*newNode=BuynewNode(x);

LN*next=phead-next;

phead-next=newNode;

newNode-prev=phead;

newNode-next=next;

next-prev=newNode;

8.在指定位置pos的前面進(jìn)行插入

一般情況

只有一個(gè)節(jié)點(diǎn)時(shí)。

兩種情況都適用以下代碼。

//指定位置前插入，極限是頭插

voidListNodeInsert(LN*pos,LNDataTypex)

if(pos==NULL)

printf("沒(méi)有找到這個(gè)數(shù)\n");

return;

LN*newNode=BuynewNode(x);

LN*tailPrev=pos-prev;

tailPrev-next=newNode;

newNode-prev=tailPrev;

newNode-next=pos;

pos-prev=newNode;

9.刪除指定位置pos節(jié)點(diǎn)

正常情況

極限尾刪

兩種情況都適用以下代碼。

//指定位置刪除

voidListNodeErease(LN*phead,LN*pos)

if(pos==phead||pos==NULL)

printf("pos指向頭，或?yàn)榭誠(chéng)n");

return;

LN*posPrev=pos-prev;

LN*posNext=pos-next;

posPrev-next=posNext;

posNext-prev=posPrev;

free(pos);

pos=NULL;

10.銷(xiāo)毀鏈表

注意：這里相當(dāng)于malloc用完之后的free。否則會(huì)造成內(nèi)存泄漏。

cur可以置空，但用處不大，因?yàn)閏ur是形參，形參是實(shí)參的一份臨時(shí)拷貝，形參置空并不能改變實(shí)參。外部的實(shí)參還是依舊能非法訪問(wèn)到cur所指向的空間。

//鏈表銷(xiāo)毀

voidListNodeDestroy(LN*phead)

assert(phead);