




版權說明:本文檔由用戶提供并上傳,收益歸屬內容提供方,若內容存在侵權,請進行舉報或認領
文檔簡介
第詳解C語言如何實現雙向帶頭循環鏈表目錄一、雙向循環鏈表與順序表的區別二、List.h三、List.c1、帶頭雙向循環鏈表的初始化2、帶頭雙向循環鏈表的銷毀3、帶頭雙向循環鏈表的打印4、動態開辟一個節點5、帶頭雙向循環鏈表的判空6、帶頭雙向循環鏈表的尾插、尾刪7、帶頭雙向循環鏈表的頭插、頭刪8、帶頭雙向循環鏈表的長度9、帶頭雙向循環鏈表的查找、任意位置插入、刪除
一、雙向循環鏈表與順序表的區別
不同點順序表雙向帶頭循環鏈表在內存中的存儲方式連續存儲不一定連續隨機訪問支持隨機訪問不支持隨訪問任意元素插入或刪除尾插O(1),其他O(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);//銷毀
voidPrintList(ListNode*phead);//打印
boolListEmpty(ListNode*phead);//判斷鏈表是否為空(只有頭節點)
voidListPushBack(ListNode*phead,ListDateTypex);//尾插
voidListPopback(ListNode*phead);//尾刪
voidListPushFront(ListNode*phead,ListDateTypex);//頭插
voidListPopFront(ListNode*phead);//頭刪
size_tListSize(ListNode*phead);//有效節點個數
ListNode*ListFind(ListNode*phead,ListDateTypex);//查找(可用于修改)
voidListInsert(ListNode*pos,ListDateTypex);//pos位置插入
voidListErase(ListNode*pos);//刪除pos位置
結構體內包含指向下一個節點的指針next、指向上一個節點的指針prev和本節點存儲的數據date
三、List.c
1、帶頭雙向循環鏈表的初始化
ListNode*ListInit()//初始化,返回帶哨兵位的頭結點
ListNode*guard=(ListNode*)malloc(sizeof(ListNode));
if(guard==NULL)
perror("ListInitfail:\n");
exit(-1);
guard-next=guard;
guard-prev=guard;
returnguard;
malloc一個哨兵位的頭結點,并將其next和prev指針置空。
2、帶頭雙向循環鏈表的銷毀
voidListDestroy(ListNode*phead)//銷毀,傳一級指針調用方需要在外部將頭結點指針置空
assert(phead);
ListNode*cur=phead-next;
while(cur!=phead)//釋放非頭結點
ListNode*next=cur-next;
free(cur);
cur=next;
free(phead);//再釋放頭結點
為了保持接口的一致性,形參用一級指針,所以需要調用者在外部對頭指針置空。
先釋放非頭結點,再釋放頭結點。
3、帶頭雙向循環鏈表的打印
voidPrintList(ListNode*phead)//打印
assert(phead);
ListNode*cur=phead-next;
while(cur!=phead)
printf("%d=",cur-date);
cur=cur-next;
printf("\n");
從頭結點的next開始,遍歷打印
4、動態開辟一個節點
ListNode*BuyNode(ListDateTypex)//動態開辟一個節點
ListNode*newnode=(ListNode*)malloc(sizeof(ListNode));
if(newnode==NULL)
perror("BuyNode:\n");
exit(-1);
newnode-date=x;
newnode-prev=NULL;
newnode-next=NULL;
returnnewnode;
將值放入這個節點,并將兩個指針置空
5、帶頭雙向循環鏈表的判空
boolListEmpty(ListNode*phead)//判斷鏈表是否只有頭節點
assert(phead);
returnphead-next==phead;
只有哨兵位這一個頭結點即為空
6、帶頭雙向循環鏈表的尾插、尾刪
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、帶頭雙向循環鏈表的頭插、頭刪
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、帶頭雙向循環鏈表的長度
size_tListSize(ListNode*phead)//有效節點個數
assert(phead);
ListNode*cur=phead-next;
size_tcount=0;
while(cur!=phead)
cur=cur-next;
++count;
returncount;
循環計數即可,哨兵位不算
9、帶頭雙向循環鏈表的查找、任意位置插入、刪除
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);
溫馨提示
- 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
- 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請聯系上傳者。文件的所有權益歸上傳用戶所有。
- 3. 本站RAR壓縮包中若帶圖紙,網頁內容里面會有圖紙預覽,若沒有圖紙預覽就沒有圖紙。
- 4. 未經權益所有人同意不得將文件中的內容挪作商業或盈利用途。
- 5. 人人文庫網僅提供信息存儲空間,僅對用戶上傳內容的表現方式做保護處理,對用戶上傳分享的文檔內容本身不做任何修改或編輯,并不能對任何下載內容負責。
- 6. 下載文件中如有侵權或不適當內容,請與我們聯系,我們立即糾正。
- 7. 本站不保證下載資源的準確性、安全性和完整性, 同時也不承擔用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。
最新文檔
- 民間個人貿易協議書
- 機械租貨安全協議書
- 村委砍伐合同協議書
- 正規領養孩童協議書
- 支架家屬和解協議書
- 施工簽訂居間協議書
- 民事按摩和解協議書
- 榕基軟件股權協議書
- 2025年新進廠職工安全培訓考試試題附參考答案【考試直接用】
- 2025企業員工安全培訓考試試題附完整答案【必刷】
- 部編版《道德與法治》六年級下冊第1課《學會尊重》精美課件
- 企業VI設計報價清單
- 監控工程驗收單-范本模板
- 浙江開放大學2024年《法律文化》形考作業1-4答案
- 政治審查表(模板)
- T∕CACM 1107-2018 中醫治未病實踐指南 亞健康中醫干預
- 數字貿易學 課件 第20、21章 數字絲綢之路與數字基礎設施、數字自由貿易與數字貿易壁壘
- 地理畢業生實習報告5000字范本2篇
- (完整版)鋁合金門窗施工合同范本
- 新生兒音樂療法課件
- 2023年心理健康知識競賽題庫100題(含答案)
評論
0/150
提交評論