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

第詳解C語(yǔ)言如何實(shí)現(xiàn)雙向帶頭循環(huán)鏈表目錄一、雙向循環(huán)鏈表與順序表的區(qū)別二、List.h三、List.c1、帶頭雙向循環(huán)鏈表的初始化2、帶頭雙向循環(huán)鏈表的銷(xiāo)毀3、帶頭雙向循環(huán)鏈表的打印4、動(dòng)態(tài)開(kāi)辟一個(gè)節(jié)點(diǎn)5、帶頭雙向循環(huán)鏈表的判空6、帶頭雙向循環(huán)鏈表的尾插、尾刪7、帶頭雙向循環(huán)鏈表的頭插、頭刪8、帶頭雙向循環(huán)鏈表的長(zhǎng)度9、帶頭雙向循環(huán)鏈表的查找、任意位置插入、刪除

一、雙向循環(huán)鏈表與順序表的區(qū)別

不同點(diǎn)順序表雙向帶頭循環(huán)鏈表在內(nèi)存中的存儲(chǔ)方式連續(xù)存儲(chǔ)不一定連續(xù)隨機(jī)訪問(wèn)支持隨機(jī)訪問(wèn)不支持隨訪問(wèn)任意元素插入或刪除尾插O(1)，其他O(N)，可能需要挪動(dòng)元素通過(guò)修改指針指向即可應(yīng)用場(chǎng)景元素高效存儲(chǔ)、頻繁訪問(wèn)任意位置插入刪除頻繁三級(jí)緩存命中率高低

寄存器的速度遠(yuǎn)快于主存，所以需要三級(jí)緩存先將數(shù)據(jù)取出，寄存器讀取時(shí)將相鄰地址的數(shù)據(jù)進(jìn)行讀取，所以順序表內(nèi)存地址連續(xù)的特點(diǎn)使其三級(jí)緩存命中率高。

雙向帶頭循環(huán)鏈表雖然在鏈表中結(jié)構(gòu)最復(fù)雜，但是解決了單鏈表找前一個(gè)節(jié)點(diǎn)需要遍歷、要判斷頭結(jié)點(diǎn)是否為空的缺點(diǎn)。

二、List.h

#pragmaonce

#includestdio.h

#includeassert.h

#includestdbool.h

#includestdlib.h

typedefintListDateType;

typedefstructListNode

structListNode*next;

structListNode*prev;

ListDateTypedate;

}ListNode;

ListNode*ListInit();//初始化

voidListDestroy(ListNode*phead);//銷(xiāo)毀

voidPrintList(ListNode*phead);//打印

boolListEmpty(ListNode*phead);//判斷鏈表是否為空（只有頭節(jié)點(diǎn)）

voidListPushBack(ListNode*phead,ListDateTypex);//尾插

voidListPopback(ListNode*phead);//尾刪

voidListPushFront(ListNode*phead,ListDateTypex);//頭插

voidListPopFront(ListNode*phead);//頭刪

size_tListSize(ListNode*phead);//有效節(jié)點(diǎn)個(gè)數(shù)

ListNode*ListFind(ListNode*phead,ListDateTypex);//查找（可用于修改）

voidListInsert(ListNode*pos,ListDateTypex);//pos位置插入

voidListErase(ListNode*pos);//刪除pos位置

結(jié)構(gòu)體內(nèi)包含指向下一個(gè)節(jié)點(diǎn)的指針next、指向上一個(gè)節(jié)點(diǎn)的指針prev和本節(jié)點(diǎn)存儲(chǔ)的數(shù)據(jù)date

三、List.c

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

ListNode*ListInit()//初始化，返回帶哨兵位的頭結(jié)點(diǎn)

ListNode*guard=(ListNode*)malloc(sizeof(ListNode));

if(guard==NULL)

perror("ListInitfail:\n");

exit(-1);

guard-next=guard;

guard-prev=guard;

returnguard;

malloc一個(gè)哨兵位的頭結(jié)點(diǎn)，并將其next和prev指針置空。

2、帶頭雙向循環(huán)鏈表的銷(xiāo)毀

voidListDestroy(ListNode*phead)//銷(xiāo)毀，傳一級(jí)指針調(diào)用方需要在外部將頭結(jié)點(diǎn)指針置空

assert(phead);

ListNode*cur=phead-next;

while(cur!=phead)//釋放非頭結(jié)點(diǎn)

ListNode*next=cur-next;

free(cur);

cur=next;

free(phead);//再釋放頭結(jié)點(diǎn)

為了保持接口的一致性，形參用一級(jí)指針，所以需要調(diào)用者在外部對(duì)頭指針置空。

先釋放非頭結(jié)點(diǎn)，再釋放頭結(jié)點(diǎn)。

3、帶頭雙向循環(huán)鏈表的打印

voidPrintList(ListNode*phead)//打印

assert(phead);

ListNode*cur=phead-next;

while(cur!=phead)

printf("%d=",cur-date);

cur=cur-next;

printf("\n");

從頭結(jié)點(diǎn)的next開(kāi)始，遍歷打印

4、動(dòng)態(tài)開(kāi)辟一個(gè)節(jié)點(diǎn)

ListNode*BuyNode(ListDateTypex)//動(dòng)態(tài)開(kāi)辟一個(gè)節(jié)點(diǎn)

ListNode*newnode=(ListNode*)malloc(sizeof(ListNode));

if(newnode==NULL)

perror("BuyNode:\n");

exit(-1);

newnode-date=x;

newnode-prev=NULL;

newnode-next=NULL;

returnnewnode;

將值放入這個(gè)節(jié)點(diǎn)，并將兩個(gè)指針置空

5、帶頭雙向循環(huán)鏈表的判空

boolListEmpty(ListNode*phead)//判斷鏈表是否只有頭節(jié)點(diǎn)

assert(phead);

returnphead-next==phead;

只有哨兵位這一個(gè)頭結(jié)點(diǎn)即為空

6、帶頭雙向循環(huán)鏈表的尾插、尾刪

voidListPushBack(ListNode*phead,ListDateTypex)//尾插

assert(phead);

ListNode*tail=phead-prev;

ListNode*newnode=BuyNode(x);

newnode-next=phead;

newnode-prev=tail;

tail-next=newnode;

phead-prev=newnode;

voidListPopback(ListNode*phead)//尾刪

assert(phead);

assert(!ListEmpty(phead));

ListNode*tail=phead-prev;

ListNode*prev=tail-prev;

free(tail);

prev-next=phead;

phead-prev=prev;

}

注意尾刪前需要判空

7、帶頭雙向循環(huán)鏈表的頭插、頭刪

voidListPushFront(ListNode*phead,ListDateTypex)//頭插

assert(phead);

ListNode*cur=phead-next;

ListNode*newnode=BuyNode(x);

newnode-next=cur;

newnode-prev=phead;

cur-prev=newnode;

phead-next=newnode;

voidListPopFront(ListNode*phead)//頭刪

assert(phead);

assert(!ListEmpty(phead));

ListNode*cur=phead-next;

ListNode*next=cur-next;

free(cur);

phead-next=next;

next-prev=phead;

}

注意頭刪前需要判空

8、帶頭雙向循環(huán)鏈表的長(zhǎng)度

size_tListSize(ListNode*phead)//有效節(jié)點(diǎn)個(gè)數(shù)

assert(phead);

ListNode*cur=phead-next;

size_tcount=0;

while(cur!=phead)

cur=cur-next;

++count;

returncount;

循環(huán)計(jì)數(shù)即可，哨兵位不算

9、帶頭雙向循環(huán)鏈表的查找、任意位置插入、刪除

ListNode*ListFind(ListNode*phead,ListDateTypex)//查找（可用于修改）

assert(phead);

ListNode*cur=phead-next;

while(cur!=phead)

if(cur-date==x)

returncur;

cur=cur-next;

returnNULL;

voidListInsert(ListNode*pos,ListDateTypex)//pos位置之前插入

assert(pos);

ListNode*newnode=BuyNode(x);

ListNode*prev=pos-prev;

prev-next=newnode;

newnode-prev=prev;

newnode-next=pos;

pos-prev=newnode;

voidListErase(ListNode*pos)//刪除pos位置

assert(pos);