第C語言實現(xiàn)帶頭雙向環(huán)形鏈表雙向循環(huán)鏈表

上一次我們講了單向無頭非循環(huán)鏈表的實現(xiàn)，單向無頭非循環(huán)鏈表的特點是：結(jié)構(gòu)簡單，一般不會單獨用來存數(shù)據(jù)。實際中更多是作為其他數(shù)據(jù)結(jié)構(gòu)的子結(jié)構(gòu)。而帶頭雙向循環(huán)鏈表則恰恰與無頭單向非循環(huán)鏈表相反，它的結(jié)構(gòu)最復(fù)雜，一般用來單獨存儲數(shù)據(jù)。這個結(jié)構(gòu)雖然復(fù)雜，但是使用單嗎實現(xiàn)后會發(fā)現(xiàn)，這個結(jié)構(gòu)用起來很簡單。

結(jié)構(gòu)示意圖

帶頭雙向循環(huán)鏈表在邏輯上大概就是這樣的一個樣子，鏈表的最后一個節(jié)點的后繼指向的是頭結(jié)點。而頭結(jié)點的前驅(qū)則是指向鏈表的最后一個結(jié)點。所以，一個空的帶頭雙向循環(huán)鏈表的邏輯結(jié)構(gòu)應(yīng)該是這樣的：

它的前驅(qū)和后繼都是指向的頭結(jié)點。

實現(xiàn)帶頭雙向循環(huán)鏈表

#pragmaonce

#includestdio.h

#includestdlib.h

#includeassert.h

typedefintLTDataType;

//定義鏈表的節(jié)點

typedefstructListNode{

LTDataTypedata;

structListNode*prev;

structListNode*next;

}LTNode;

//創(chuàng)建返回鏈表的頭結(jié)點.

LTNode*ListCreate();

//雙向鏈表銷毀

voidListDestory(LTNode*pHead);

//雙向鏈表打印

voidListPrint(LTNode*pHead);

//雙向鏈表尾插

voidListPushBack(LTNode*pHead,LTDataTypex);

//雙向鏈表尾刪

voidListPopBack(LTNode*pHead);

//雙向鏈表頭插

voidListPushFront(LTNode*pHead,LTDataTypex);

//雙向鏈表頭刪

voidListPopFront(LTNode*pHead);

//雙向鏈表查找

LTNode*ListFind(LTNode*pHead,LTDataTypex);

//雙向鏈表在pos的前面進(jìn)行插入

voidListInsert(LTNode*pos,LTDataTypex);

//雙向鏈表刪除pos位置的節(jié)點

voidListErase(LTNode*pos);

首先我們得定義一個結(jié)點的結(jié)構(gòu)，它由前驅(qū)指針、后繼指針和數(shù)據(jù)這三部分組成。

//定義鏈表的節(jié)點

typedefstructListNode{

LTDataTypedata;

structListNode*prev;

structListNode*next;

}LTNode;

定義好之后，我們要創(chuàng)建一個頭結(jié)點。我們把創(chuàng)建頭結(jié)點的過程也封裝成一個函數(shù)，這個函數(shù)的返回值就是頭結(jié)點的指針。我們在使用的時候就創(chuàng)建一個變量來接收這個指針。

**注意：**頭結(jié)點創(chuàng)建的時候，它的data部分是不存數(shù)據(jù)的，它的前驅(qū)和后繼都是指向它自己

LTNode*ListCreate(){

LTNode*head=(LTNode*)malloc(sizeof(LTNode));

head-next=head;

head-prev=head;

returnhead;

//在main函數(shù)中是這樣使用的

intmain(){

LTNode*head=ListCreate();

return0;

}

創(chuàng)建好頭結(jié)點之后就可以向鏈表中插入數(shù)據(jù)了，首先實現(xiàn)尾插，就是在鏈表的最后一個結(jié)點后面再插入一個結(jié)點。然后就是頭插法，頭插法就是在頭結(jié)點的后面插入一個新節(jié)點。

//雙向鏈表尾插

voidListPushBack(LTNode*pHead,LTDataTypex){

assert(pHead);

LTNode*newnode=(LTNode*)malloc(sizeof(LTNode));//創(chuàng)建的新節(jié)點

newnode-data=x;

//將新節(jié)點插入到鏈表中

LTNode*prev=pHead-prev;

prev-