C語言詳解如何實(shí)現(xiàn)帶頭雙向循環(huán)鏈表
創(chuàng)建鏈表存儲(chǔ)結(jié)構(gòu)
我們需要?jiǎng)?chuàng)建一個(gè)結(jié)構(gòu)體來存儲(chǔ)一個(gè)鏈表結(jié)點(diǎn)的相關(guān)信息。
typedef int ListDataType;//將ListDataType先定義為int類型,根據(jù)需要可以改為不同的類型 //創(chuàng)建一個(gè)鏈表的結(jié)構(gòu)體 typedef struct ListNode { ListDataType data;//存儲(chǔ)數(shù)據(jù) struct ListNode* next;//存儲(chǔ)下一個(gè)結(jié)點(diǎn)的地址的指針 struct ListNode* prev;//存儲(chǔ)上一個(gè)結(jié)點(diǎn)的地址的指針 }ListNode;
創(chuàng)建結(jié)點(diǎn)
我們每次增加數(shù)據(jù)都要?jiǎng)?chuàng)建一個(gè)新的結(jié)點(diǎn),但每次都創(chuàng)建就會(huì)非常的麻煩。所以我們考慮把創(chuàng)建一個(gè)結(jié)點(diǎn)這個(gè)功能封裝成一個(gè)函數(shù),每次要使用只要調(diào)用一下就可以了。
ListNode* BuyListNode(ListDataType x) { ListNode* newnode = (ListNode*)malloc(sizeof(ListNode));//向內(nèi)存申請一個(gè)新的結(jié)點(diǎn) if (newnode == NULL) { printf("BuyListNode::%s\n", strerror(errno));//打印結(jié)點(diǎn)空間申請失敗的原因 exit(-1);//終止程序 } newnode->data = x;//將x放入申請的結(jié)點(diǎn)數(shù)據(jù)區(qū) newnode->next = NULL;//讓新結(jié)點(diǎn)的next指向空 newnode->prev = NULL;//讓新結(jié)點(diǎn)的prev指向空 return newnode;//返回新結(jié)點(diǎn)的地址 }
鏈表的初始化
帶頭雙向循環(huán)鏈表我們對其初始化就是申請一個(gè)帶哨兵位的頭結(jié)點(diǎn)。接下來我們看初始化的兩種方法。
void ListInit(ListNode** pphead)//這里我們需要對頭結(jié)點(diǎn)進(jìn)行改變,所以傳二級指針 { assert(pphead);//檢測傳過來的pphead的地址是否為空 *pphead = BuyListNode(0);//創(chuàng)建一個(gè)新的哨兵位頭結(jié)點(diǎn) (*pphead)->next = *pphead;//讓這個(gè)結(jié)點(diǎn)指向自己 (*pphead)->prev = *pphead; }
ListNode* ListInit() { ListNode* phead = BuyListNode(0);//創(chuàng)建一個(gè)新的哨兵位頭結(jié)點(diǎn) phead->next = phead;//讓這個(gè)結(jié)點(diǎn)的next指向自己 phead->prev = phead;//讓prev指向自己 return phead;//返回哨兵位頭結(jié)點(diǎn)的地址 }
雙向鏈表的打印
我們才用遍歷鏈表的方式來打印鏈表中的數(shù)據(jù)。
void ListPrint(ListNode* phead) { assert(phead); ListNode* cur = phead->next;//讓cur指向哨兵位的下一個(gè)結(jié)點(diǎn) while (cur != phead)//鏈表打印是否結(jié)束的條件判斷 { printf("%d ", cur->data); cur = cur->next; } printf("\n"); }
雙向鏈表尾插
雙向循環(huán)鏈表結(jié)構(gòu)比較優(yōu),所以很方便找到尾結(jié)點(diǎn)。尾結(jié)點(diǎn)就是哨兵位結(jié)點(diǎn)prev指向的結(jié)點(diǎn)。
void ListPushBack(ListNode* phead, ListDataType x) { assert(phead);//檢查傳過來的頭結(jié)點(diǎn)是否為空 ListNode* tail = phead->prev;//找到鏈表的尾結(jié)點(diǎn) ListNode* newnode = BuyListNode(x);//創(chuàng)建一個(gè)新的結(jié)點(diǎn) tail->next = newnode;//讓尾結(jié)點(diǎn)的next指向新的結(jié)點(diǎn) newnode->prev = tail;//讓新結(jié)點(diǎn)的prev指向之前的尾結(jié)點(diǎn) newnode->next = phead;//讓新的結(jié)點(diǎn)的next指向頭結(jié)點(diǎn) phead->prev = newnode;//讓頭結(jié)點(diǎn)指向新的尾結(jié)點(diǎn) }
雙向鏈表尾刪
void ListPopBack(ListNode* phead) { assert(phead); if (phead->next == phead)//如果鏈表只有哨兵位結(jié)點(diǎn)的情況,就不能繼續(xù)刪除了 return; ListNode* tail = phead->prev;//找到尾結(jié)點(diǎn) ListNode* tailPrev = tail->prev;//定義尾結(jié)點(diǎn)的前一個(gè)結(jié)點(diǎn) free(tail);//釋放要?jiǎng)h除的結(jié)點(diǎn) tailPrev->next = phead;//讓前一個(gè)結(jié)點(diǎn)指向哨兵位結(jié)點(diǎn) phead->prev = tailPrev;//讓哨兵位結(jié)點(diǎn)指向新的尾結(jié)點(diǎn) }
雙向鏈表頭插
雙向鏈表的頭插就是在哨兵位結(jié)點(diǎn)的下一個(gè)位置插入一個(gè)新的數(shù)據(jù)。
注意:這一種方法種的指向關(guān)系不能隨意顛倒,否則就會(huì)出錯(cuò)。
void ListPushFront(ListNode* phead, ListDataType x) { assert(phead); ListNode* newnode = BuyListNode(x);//創(chuàng)建一個(gè)新結(jié)點(diǎn) newnode->next = phead->next;//新結(jié)點(diǎn)的next指向頭結(jié)點(diǎn)的下一個(gè)結(jié)點(diǎn) phead->next->prev = newnode;//頭結(jié)點(diǎn)的下一個(gè)結(jié)點(diǎn)指向新結(jié)點(diǎn) phead->next = newnode;//頭結(jié)點(diǎn)指向新結(jié)點(diǎn) newnode->prev = phead;//新結(jié)點(diǎn)prev指向頭結(jié)點(diǎn) }
我們可以對上一種情況進(jìn)行優(yōu)化,定義一個(gè)next記錄頭結(jié)點(diǎn)的下一個(gè)結(jié)點(diǎn)的地址。這樣我們就可以不用在意指向順序的問題,可以減少出錯(cuò)的概率。
void ListPushFront(ListNode* phead, ListDataType x) { assert(phead); ListNode* newnode = BuyListNode(x);//創(chuàng)建一個(gè)新結(jié)點(diǎn) ListNode* next = phead->next;//定義next記錄頭節(jié)點(diǎn)的下一個(gè)結(jié)點(diǎn)的位置 phead->next = newnode;//頭結(jié)點(diǎn)next指向新結(jié)點(diǎn) newnode->prev = phead;//新結(jié)點(diǎn)的prev指向頭結(jié)點(diǎn) next->prev = newnode;//頭結(jié)點(diǎn)的下一個(gè)結(jié)點(diǎn)的prev指向新階段 newnode->next = next;//新結(jié)點(diǎn)的next指向原頭結(jié)點(diǎn)的下一個(gè)結(jié)點(diǎn) }
雙向鏈表頭刪
我們先找到頭結(jié)點(diǎn)的下一個(gè)結(jié)點(diǎn),然后在把它釋放掉。這里需要注意的是如果鏈表為空,只有哨兵位頭結(jié)點(diǎn)的情況,我們需要對其進(jìn)行特殊的處理。
void ListPopFront(ListNode* phead) { assert(phead); if (phead->next == NULL)//只有哨兵位頭結(jié)點(diǎn)的情況 return; ListNode* next = phead->next->next;//定義next指向要?jiǎng)h除結(jié)點(diǎn)的下一個(gè)結(jié)點(diǎn) free(phead->next);//釋放要?jiǎng)h除的結(jié)點(diǎn) phead->next = next;//讓哨兵位頭結(jié)點(diǎn)指向要?jiǎng)h除的下一個(gè)結(jié)點(diǎn) next->prev = phead;//讓要?jiǎng)h除的下一個(gè)結(jié)點(diǎn)的prev指向toujied }
雙向鏈表查找
若我們想要對指定的位置的結(jié)點(diǎn)進(jìn)行相應(yīng)的改變就得先找到對應(yīng)的結(jié)點(diǎn),所以我們將查找指定數(shù)據(jù)封裝成一個(gè)函數(shù)。方便后續(xù)調(diào)用。
ListNode* ListFind(ListNode* phead, ListDataType x) { assert(phead); ListNode* cur = phead->next;//讓cur指向哨兵位頭結(jié)點(diǎn)的下一個(gè)結(jié)點(diǎn) while (cur != phead)//鏈表循環(huán)是否結(jié)束的判斷條件 { if (cur->data == x) return cur; cur = cur->next; } return NULL;//找不到對于的結(jié)點(diǎn) }
雙向鏈表pos前插入結(jié)點(diǎn)
推薦使用第二種方法,不容易出錯(cuò)。
void ListInsert(ListNode* pos, ListDataType x) { assert(pos); ListNode* newnode = BuyListNode(x);//創(chuàng)建一個(gè)新的結(jié)點(diǎn) pos->prev->next = newnode;//pos的前一個(gè)結(jié)點(diǎn)的next指向新結(jié)點(diǎn) newnode->prev = pos->prev;//新結(jié)點(diǎn)的prev指向pos的前一個(gè)結(jié)點(diǎn) newnode->next = pos;//新結(jié)點(diǎn)的next指向pos結(jié)點(diǎn) pos->prev = newnode;//pos的prev指向新結(jié)點(diǎn) }
void ListInsert(ListNode* pos, ListDataType x) { assert(pos); ListNode* newnode = BuyListNode(x);//創(chuàng)建一個(gè)新的結(jié)點(diǎn) ListNode* posPrev = pos->prev;//定義pos的前一個(gè)結(jié)點(diǎn) posPrev->next = newnode;//讓pos的pos前一個(gè)結(jié)點(diǎn)的next指向新結(jié)點(diǎn) newnode->prev = posPrev;//新結(jié)點(diǎn)的prev指向pos的前一個(gè)結(jié)點(diǎn) newnode->next = pos;//新結(jié)點(diǎn)的next指向pos pos->prev = newnode;//pos的prev指向新結(jié)點(diǎn) }
雙向鏈表刪除pos位置的結(jié)點(diǎn)
void ListErase(ListNode* pos) { assert(pos); ListNode* prev = pos->prev;//prev為pos的前一個(gè)結(jié)點(diǎn) ListNode* next = pos->next;//next為pos的后一個(gè)結(jié)點(diǎn) free(pos);//釋放posjied prev->next = next; next->prev = prev; }
雙向鏈表的銷毀
void ListDestroy(ListNode* phead) { assert(phead); ListNode* cur = phead->next;//指向哨兵位結(jié)點(diǎn)的下一個(gè)結(jié)點(diǎn) while (cur != phead)//依次循環(huán)找鏈表的每一個(gè)結(jié)點(diǎn) { ListNode* next = cur->next;//記錄cur的下一個(gè)結(jié)點(diǎn)位置 free(cur);//釋放cur位置的結(jié)點(diǎn) cur = next;//指向下一個(gè)結(jié)點(diǎn) } free(phead);//釋放哨兵位頭結(jié)點(diǎn) }
注意:在寫雙向鏈表的頭插,頭刪,尾插,尾刪時(shí)我們可以復(fù)用雙向鏈表的任意位置插入和任意位置刪除那兩個(gè)函數(shù)。那兩個(gè)函數(shù)就可以完成頭插,頭刪,尾插,尾刪這幾個(gè)功能。
順序表和鏈表的區(qū)別
順序表優(yōu)點(diǎn):
1.物理空間是連續(xù)的,方便用下標(biāo)隨機(jī)訪問。
2.CPU高速緩存命中率會(huì)更高。
順序表缺點(diǎn):
1.由于需要物理空間連續(xù),空間不夠需要擴(kuò)容。擴(kuò)容本身有一定消耗。其次擴(kuò)容機(jī)制還存在一定的空間浪費(fèi)。
2.頭部或者中部插入刪除,挪動(dòng)數(shù)據(jù),效率低。O(N)
鏈表優(yōu)點(diǎn):
1.任意位置插入刪除數(shù)據(jù)效率高。O(1)
2.按需申請和釋放空間
鏈表缺點(diǎn):
不支持下標(biāo)的隨機(jī)訪問。有些算法不適合在它上面運(yùn)行。如:二分查找、排序等。
關(guān)于CPU相關(guān)的知識可以參考這一篇文章:CPU緩存知識
到此這篇關(guān)于C語言詳解如何實(shí)現(xiàn)帶頭雙向循環(huán)鏈表的文章就介紹到這了,更多相關(guān)C語言帶頭雙向循環(huán)鏈表內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家!
- C語言中帶頭雙向循環(huán)鏈表基本操作的實(shí)現(xiàn)詳解
- C語言帶頭雙向循環(huán)鏈表的示例代碼
- 詳解C語言如何實(shí)現(xiàn)雙向帶頭循環(huán)鏈表
- C語言手把手帶你掌握帶頭雙向循環(huán)鏈表
- C語言超詳細(xì)講解數(shù)據(jù)結(jié)構(gòu)中雙向帶頭循環(huán)鏈表
- C語言實(shí)現(xiàn)帶頭雙向循環(huán)鏈表
- C語言編程數(shù)據(jù)結(jié)構(gòu)帶頭雙向循環(huán)鏈表全面詳解
- C語言實(shí)現(xiàn)帶頭雙向循環(huán)鏈表的接口
- C語言超詳細(xì)講解雙向帶頭循環(huán)鏈表
相關(guān)文章
C++ Thread實(shí)現(xiàn)簡單的socket多線程通信
本文主要介紹了C++ Thread實(shí)現(xiàn)簡單的socket多線程通信,文中通過示例代碼介紹的非常詳細(xì),對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值,需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧2022-07-07C++子類父類成員函數(shù)的覆蓋和隱藏實(shí)例詳解
這篇文章主要介紹了C++子類父類成員函數(shù)的覆蓋和隱藏實(shí)例詳解的相關(guān)資料,需要的朋友可以參考下2017-06-06C++中的while循環(huán)和for循環(huán)語句學(xué)習(xí)教程
這篇文章主要介紹了C++中的while循環(huán)和for循環(huán)語句學(xué)習(xí)教程,是C++入門學(xué)習(xí)中的基礎(chǔ)知識,需要的朋友可以參考下2015-09-09在Visual Studio中用C++語言創(chuàng)建DLL動(dòng)態(tài)鏈接庫圖文教程
這篇文章主要介紹了在Visual Studio中用C++語言創(chuàng)建DLL動(dòng)態(tài)鏈接庫圖文教程,本文詳細(xì)講解了DLL庫的創(chuàng)建過程,并給出了代碼示例,需要的朋友可以參考下2014-09-09