C語言超詳細(xì)介紹與實(shí)現(xiàn)線性表中的帶頭雙向循環(huán)鏈表

第C語言超詳細(xì)介紹與實(shí)現(xiàn)線性表中的帶頭雙向循環(huán)鏈表目錄一、本章重點(diǎn)二、帶頭雙向循環(huán)鏈表介紹2.1什么是帶頭雙向循環(huán)鏈表？2.2最常用的兩種鏈表結(jié)構(gòu)三、帶頭雙向循環(huán)鏈表常用接口實(shí)現(xiàn)

3.1結(jié)構(gòu)體創(chuàng)建3.2帶頭雙向循環(huán)鏈表的初始化

3.3創(chuàng)建新節(jié)點(diǎn)3.4尾插3.5打印鏈表3.6頭插3.7尾刪3.8頭刪3.9查找data（返回data的節(jié)點(diǎn)地址）3.10在pos位置之前插入節(jié)點(diǎn)3.11刪除pos位置的節(jié)點(diǎn)四、實(shí)現(xiàn)接口總結(jié)五、在線oj訓(xùn)練與詳解

一、本章重點(diǎn)

帶頭雙向循環(huán)鏈表介紹

帶頭雙向循環(huán)鏈表常用接口實(shí)現(xiàn)

實(shí)現(xiàn)接口總結(jié)

在線oj訓(xùn)練與詳解

二、帶頭雙向循環(huán)鏈表介紹

2.1什么是帶頭雙向循環(huán)鏈表？

帶頭：存在一個哨兵位的頭節(jié)點(diǎn)，該節(jié)點(diǎn)是個無效節(jié)點(diǎn)，不存儲任何有效信息，但使用它可以方便我們頭尾插和頭尾刪時不用判斷頭節(jié)點(diǎn)指向NULL的情況，同時也不需要改變頭指針的指向，也就不需要傳二級指針了。

雙向：每個結(jié)構(gòu)體有兩個指針，分別指向前一個結(jié)構(gòu)體和后一個結(jié)構(gòu)體。

循環(huán)：最后一個結(jié)構(gòu)體的指針不再指向NULL，而是指向第一個結(jié)構(gòu)體。（單向）

第一個結(jié)構(gòu)體的前指針指向最后一個結(jié)構(gòu)體，最后一個結(jié)構(gòu)體的后指針指向第一個結(jié)構(gòu)體（雙向）。

圖解

2.2最常用的兩種鏈表結(jié)構(gòu)

更具有無頭，單雙向，是否循環(huán)組合起來有8種結(jié)構(gòu)，但最長用的還是無頭單向非循環(huán)鏈表和帶頭雙向循環(huán)鏈表

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

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

三、帶頭雙向循環(huán)鏈表常用接口實(shí)現(xiàn)

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

typedefintDataType;

typedefstructDListNode

DataTypedata;

DListNode*prev;

DListNode*next;

}DListNode;

3.2帶頭雙向循環(huán)鏈表的初始化

voidDListInint(DListNode**pphead)

*pphead=(DListNode*)malloc(sizeof(DListNode));

(*pphead)-next=(*pphead);

(*pphead)-prev=(*pphead);

}

或者使用返回節(jié)點(diǎn)的方法也能實(shí)現(xiàn)初始化

DListNode*DListInit()

DListNode*phead=(DListNode*)malloc(sizeof(DListNode));

phead-next=phead;

phead-prev=phead;

returnphead;

}

3.3創(chuàng)建新節(jié)點(diǎn)

DListNode*BuyDListNode(DataTypex)

DListNode*temp=(DListNode*)malloc(sizeof(DListNode));

if(temp==NULL)

printf("mallocfail\n");

exit(-1);

temp-prev=NULL;

temp-next=NULL;

temp-data=x;

returntemp;

}

3.4尾插

voidDListPushBack(DListNode*phead,DataTypex)

DListNode*newnode=BuyDListNode(x);

DListNode*tail=phead-prev;

tail-next=newnode;

newnode-prev=tail;

newnode-next=phead;

phead-prev=newnode;

}

3.5打印鏈表

voidDListNodePrint(DListNode*phead)

DListNode*cur=phead-next;

while(cur!=phead)

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

cur=cur-next;

printf("NULL\n");

}

3.6頭插

voidDListNodePushFront(DListNode*phead,DataTypex)

DListNode*next=phead-next;

DListNode*newnode=BuyDListNode(x);

next-prev=newnode;

newnode-next=next;

newnode-prev=phead;

phead-next=newnode;

}

3.7尾刪

voidDListNodePopBack(DListNode*phead)

if(phead-next==phead)

return;

DListNode*tail=phead-prev;

DListNode*prev=tail-prev;

prev-next=phead;

phead-prev=prev;

free(tail);

tail=NULL;

}

3.8頭刪

voidDListNodePopFront(DListNode*phead)

if(phead-next==phead)

return;

DListNode*firstnode=phead-next;

DListNode*secondnode=firstnode-next;

secondnode-prev=phead;

phead-next=secondnode;

free(firstnode);

firstnode=NULL;

}

3.9查找data（返回data的節(jié)點(diǎn)地址）

DListNode*DListNodeFind(DListNode*phead,DataTypex)

DListNode*firstnode=phead-next;

while(firstnode!=phead)

if(firstnode-data==x)

returnfirstnode;

firstnode=firstnode-next;

returnNULL;

}

3.10在pos位置之前插入節(jié)點(diǎn)

voidDListNodeInsert(DListNode*pos,DataTypex)

DListNode*prev=pos-prev;

DListNode*newnode=BuyDListNode(x);

newnode-next=pos;

newnode-prev=prev;

prev-next=newnode;

pos-prev=newnode;

}

3.11刪除pos位置的節(jié)點(diǎn)

voidDListNodeErase(DListNode*pos)

DListNode*prev=pos-prev;

DListNode*next=pos-next;

prev-next=next;

next-prev=prev;

free(pos);

pos=NULL;

}

四、實(shí)現(xiàn)接口總結(jié)

多畫圖：能給清晰展示變化的過程，有利于實(shí)現(xiàn)編程。

小知識：head-next既可表示前一個結(jié)構(gòu)體的成員變量，有可表示后一個結(jié)構(gòu)體的地址。當(dāng)head-next作為左值時代表的是成員變量，作右值時代表的是后一個結(jié)構(gòu)體的地址。對于鏈表來說理解這一點(diǎn)非常重要。

實(shí)踐：實(shí)踐出真知

帶頭雙向循環(huán)鏈表：相比于單鏈表，它實(shí)現(xiàn)起來更簡單，不用向單鏈表一樣分情況討論鏈表的長度。雖然結(jié)構(gòu)較復(fù)雜，但使用起來更簡單，更方便。

五、在線oj訓(xùn)練與詳解

鏈表的中間節(jié)點(diǎn)（力扣）

給定一個頭結(jié)點(diǎn)為

head

的非空單鏈表，返回鏈表的中間結(jié)點(diǎn)。

如果有兩個中間結(jié)點(diǎn)，則返回第二個中間結(jié)點(diǎn)。

輸入：[1,2,3,4,5]

輸出：此列表中的結(jié)點(diǎn)3(序列化形式：[3,4,5])

返回的結(jié)點(diǎn)值為3。(測評系統(tǒng)對該結(jié)點(diǎn)序列化表述是[3,4,5])。

注意，我們返回了一個ListNode類型的對象ans，

這樣：

ans.val=3,ans.next.val=4,ans.next.next.val=5,以及ans.next.next.next=NULL.

來源：力扣（LeetCode）

思路：快慢指針

取兩個指針，初始時均指向head，一個為快指針（fast）一次走兩步，另一個為慢指針（slow）一次走一步，當(dāng)快指針滿足fast==NULL（偶數(shù)個節(jié)點(diǎn)）或者fast-next==NULL（奇數(shù)個節(jié)點(diǎn)）時，slow指向中間