詳解C語言中雙向循環(huán)鏈表的實現(xiàn)

第詳解C語言中雙向循環(huán)鏈表的實現(xiàn)目錄實現(xiàn)細(xì)節(jié)輔助理解圖具體實現(xiàn)代碼1、對鏈表進行初始化2、任意位置前的插入3、任意位置的刪除4、頭插和尾刪完整代碼頭文件具體函數(shù)測試

實現(xiàn)細(xì)節(jié)

1、帶一個哨兵位（哨兵節(jié)點，初始節(jié)點，不存儲有效數(shù)據(jù)，用來方便后期數(shù)據(jù)的存儲與查找）

2、與單向鏈表不同的是，雙向鏈表中每個數(shù)據(jù)節(jié)點包含兩個指針，分別指向前后兩個節(jié)點

3、雙向鏈表是循環(huán)的，其尾節(jié)點后不是空指針，而是與頭部的哨兵節(jié)點通過指針相連

輔助理解圖

具體實現(xiàn)代碼

1、對鏈表進行初始化

初始化：哨兵位的前后指針均指向哨兵節(jié)點本身

voidListInit(ListNode**pphead)

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

if(*pphead==NULL)

perror("ListInit");

exit(-1);

(*pphead)-date=-1;

(*pphead)-next=*pphead;

(*pphead)-prev=*pphead;

2、任意位置前的插入

注意：插入位置前后節(jié)點中的前后指針要進行相應(yīng)的更換

voidAny_insert(ListNode*pos,Listtypedate)

ListNode*Prev=pos-prev;

//建立新節(jié)點

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

if(NewNode==NULL)

perror("Any_insert");

exit(-1);

NewNode-date=date;

NewNode-next=pos;

pos-prev=NewNode;

Prev-next=NewNode;

NewNode-prev=Prev;

3、任意位置的刪除

細(xì)節(jié)點：當(dāng)鏈表中沒有數(shù)據(jù)時，就不用刪除，因此需要建立一個函數(shù)進行判斷

boolDetermine(ListNode*pphead)

{//判斷鏈表中有無元素

assert(pphead);

returnpphead==pphead-next;

voidAny_delet(ListNode*pos)

assert(!Determine(pos));

ListNode*Next=pos-next;

ListNode*Prev=pos-prev;

Next-prev=Prev;

Prev-next=Next;

free(pos);

4、頭插和尾刪

此處的插入和刪除，十分方便，即：對上面的任插和任刪進行套用

頭插如下：

voidHead_insert(ListNode*pphead,Listtypedate)

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

if(NewNode==NULL)

perror("Head_insert");

exit(-1);

//單獨實現(xiàn)

//NewNode-date=date;

//NewNode-prev=pphead;

//NewNode-next=pphead-next;

//pphead-next-prev=NewNode;

//pphead-next=NewNode;

//進行任插的復(fù)用

Any_insert(pphead-next,date);

尾刪如下：

voidTail_delet(ListNode*pphead)

assert(pphead);

//單獨實現(xiàn)

//assert(Determine(pphead));

/*ListNode*tail=pphead-prev;

if(tail!=pphead)

ListNode*tailprev=tail-prev;

tailprev-next=pphead;

pphead-prev=tailprev;

free(tail);

//尾刪的復(fù)用

Any_delet(pphead-prev);

完整代碼

頭文件

#pragmaonce

#includestdio.h

#includemalloc.h

#includestdlib.h

#includeassert.h

#includestdbool.h

typedefintListtype;

typedefstructListNode

structListNode*prev;

Listtypedate;

structListNode*next;

}ListNode;

voidListInit(ListNode**pphead);//鏈表初始化

voidListNode_ADD(ListNode*pphead,Listtypedate);//尾插

voidHead_insert(ListNode*pphead,Listtypedate);//頭插

voidListNode_Print(ListNode*pphead);//鏈表打印

voidTail_delet(ListNode*pphead);//尾刪

boolDetermine(ListNode*pphead);//判斷表中有無數(shù)據(jù)

voidAny_insert(ListNode*pos,Listtypedate);//任插

voidAny_delet(ListNode*pos);//任刪

voidList_Destory(ListNode*pos);//鏈表清空

具體函數(shù)

#define_CRT_SECURE_NO_WARNINGS1

#include"List.h"

//鏈表打印

voidListNode_Print(ListNode*pphead)

assert(pphead);

ListNode*phead=pphead;

pphead=pphead-next;

for(;pphead!=phead;pphead=pphead-next)

printf("%d",pphead-date);

printf("\n");

boolDetermine(ListNode*pphead)

{//判斷鏈表中有無元素

assert(pphead);

returnpphead==pphead-next;

//鏈表初始化

voidListInit(ListNode**pphead)

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

if(*pphead==NULL)

perror("ListInit");

exit(-1);

(*pphead)-date=-1;

(*pphead)-next=*pphead;

(*pphead)-prev=*pphead;

voidListNode_ADD(ListNode*pphead,Listtypedate)

//ListNode*NewNode=(ListNode*)malloc(sizeof(ListNode));

//if(NewNode==NULL)

//perror("ADD_malloc");

//exit(-1);

//NewNode-date=date;

//NewNode-prev=pphead-prev;

//pphead-prev-next=NewNode;

//pphead-prev=NewNode;

//NewNode-next=pphead;

//任插的復(fù)用

Any_insert(pphead,date);

voidHead_insert(ListNode*pphead,Listtypedate)

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

if(NewNode==NULL)

perror("Head_insert");

exit(-1);

//NewNode-date=date;

//NewNode-prev=pphead;

//NewNode-next=pphead-next;

//pphead-next-prev=NewNode;

//pphead-next=NewNode;

//進行任插的復(fù)用

Any_insert(pphead-next,date);

voidTail_delet(ListNode*pphead)

assert(pphead);

//assert(Determine(pphead));

/*ListNode*tail=pphead-prev;

if(tail!=pphead)

ListNode*tailprev=tail-prev;

tailprev-next=pphead;

pphead-prev=tailprev;

free(tail);

//尾刪的復(fù)用

Any_delet(pphead-prev);

//在任意位置前插入

voidAny_insert(ListNode*pos,Listtypedate)

ListNode*Prev=pos-prev;

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

if(NewNode==NULL)

perror("Any_insert");

exit(-1);

NewNode-date=date;

NewNode-next=pos;

pos-prev=NewNode;

Prev-next=NewNode;

NewNode-prev=Prev;

//任意位置刪除

voidAny_delet(ListNode*pos)

assert(!Determine(pos));

ListNode*Next=pos-next;

ListNode*Prev=pos-prev;

Next-prev=Prev;

Prev-next=Next;

free(pos);

//鏈表清空

voidList_Destory(ListNode*pos)

ListNode*head=pos,*Prev=pos-prev;

for(pos=pos-prev;head!=pos;pos=Prev)

Prev=pos-prev;

Any_delet(pos);

printf("\n清空完成\n");

}

測試

#define_CRT_SECURE_NO_WARNINGS1

#include"List.h"

voidListTest(ListNode**pphead)

ListInit(pphead);

Head_insert(*pphead,60);

Head_insert(*pphead,100);

Head_insert(*pphead,60);

Head_insert