一.帶頭雙向鏈表的概念

帶頭雙向循環(huán)鏈表（Doubly Circular Linked List with a Head）是一種鏈表數(shù)據(jù)結構，它具有以下特點：

頭節(jié)點（哨兵位）：帶頭雙向循環(huán)鏈表包含一個頭節(jié)點，它位于鏈表的起始位置，并且不存儲實際數(shù)據(jù)。頭節(jié)點的前驅(qū)指針指向尾節(jié)點，頭節(jié)點的后繼指針指向第一個實際數(shù)據(jù)節(jié)點。

循環(huán)連接：尾節(jié)點的后繼指針指向頭節(jié)點，而頭節(jié)點的前驅(qū)指針指向尾節(jié)點，將鏈表形成一個循環(huán)連接的閉環(huán)。這樣可以使鏈表在遍歷時可以無限循環(huán)，方便實現(xiàn)循環(huán)操作。

雙向連接：每個節(jié)點都有一個前驅(qū)指針和一個后繼指針，使得節(jié)點可以向前和向后遍歷。前驅(qū)指針指向前一個節(jié)點，后繼指針指向后一個節(jié)點。

總結:帶頭雙向循環(huán)鏈表可以支持在鏈表的任意位置進行插入和刪除操作，并且可以實現(xiàn)正向和反向的循環(huán)遍歷。通過循環(huán)連接的特性，鏈表可以在連續(xù)的循環(huán)中遍歷所有節(jié)點，使得鏈表的操作更加靈活和高效。

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

1.實現(xiàn)框架

通過將int定義為LTDataType，可以在代碼中使用LTDataType作為數(shù)據(jù)類型，而不是直接使用int。這樣做的好處有以下幾點：

1. 可讀性：使用LTDataType作為數(shù)據(jù)類型可以使代碼更具可讀性。LTDataType作為一個自定義的數(shù)據(jù)類型名稱，可以更好地表達代碼中數(shù)據(jù)的含義和用途，提高代碼的可理解性。
2. 可維護性：將int定義為LTDataType可以方便地在代碼中統(tǒng)一修改數(shù)據(jù)類型。如果將來需要將數(shù)據(jù)類型更改為其他類型，只需修改typedef語句中的定義，而不需要在整個代碼中逐個修改具體的數(shù)據(jù)類型，減少了修改的工作量和出錯的可能性。
3. 靈活性：通過使用LTDataType，可以在代碼中輕松更改數(shù)據(jù)類型，而不會對代碼的其他部分產(chǎn)生影響。這種抽象化的方式可以使代碼更具通用性，便于在不同的場景中重用。

2.動態(tài)內(nèi)存開辟申請

此函數(shù)是關于一個結點動態(tài)申請的實現(xiàn)，包含兩個指針域，一個數(shù)據(jù)域。如果分配成功，它會返回指向該內(nèi)存塊起始位置的指針。你可以使用這個指針來訪問和操作所分配的內(nèi)存。如果分配失敗，malloc會返回NULL指針，表示內(nèi)存分配未成功。

3.鏈表的初始化

鏈表的初始化就是要創(chuàng)建哨兵位的頭節(jié)點,此頭節(jié)點不存儲有效數(shù)據(jù)，并且因一開始不知道指向誰，所以根據(jù)雙向鏈表循環(huán)的特性，就讓該結點的兩個指針自己指向自己。

4.鏈表打印

打印鏈表就是,遍歷鏈表的每一個結點的數(shù)據(jù)域，開始時用assert斷言傳過來的結點地址是否為NULL。接著cur用phead->next賦值的原因是，phead傳過來的是哨兵位的頭節(jié)點，它的下一位才是鏈表真正的頭節(jié)點（有數(shù)據(jù)域），接著遍歷鏈表，當cur指針回到哨兵位時，遍歷結束。

5. 釋放鏈表所申請的動態(tài)內(nèi)存空間

在動態(tài)內(nèi)存使用完后，需要把這部分內(nèi)存的使用權限還給操作系統(tǒng)，否則會造成內(nèi)存泄漏。將頭節(jié)點的下一個節(jié)點賦值給cur，讓cur遍歷鏈表一遍，當cur遍歷完成到phead頭節(jié)點的時候，釋放結束，退出循環(huán)。

6.判斷鏈表是否為空。

在上面的釋放動態(tài)內(nèi)存函數(shù)中用到了另外一個函數(shù)LTEmpty，這個函數(shù)的作用是用來判斷鏈表是否只有哨兵位，空鏈表的話是不能進行釋放的。為此，引用了布爾值，如果為空則返回true，不空則返回false。

7.鏈表尾部插入節(jié)點

首先創(chuàng)建一個指針用于存儲最后一個節(jié)點，防止尾插時找不到，之后將鏈表與新節(jié)點鏈接起來就可以了。

測試用例：

尾插幾個數(shù)據(jù)之后，打印出來，最后將內(nèi)存返回個操作系統(tǒng)，釋放哨兵位，防止內(nèi)存泄露。

這是測試打印出來的數(shù)據(jù)。

8.鏈表頭部插入節(jié)點

首先創(chuàng)建一個指針用于存儲第一個節(jié)點，防止尾插時找不到，之后將鏈表與新節(jié)點鏈接起來就可以了。

測試用例：

插入幾個數(shù)據(jù)之后，打印出來，最后將內(nèi)存返回個操作系統(tǒng)，釋放哨兵位，防止內(nèi)存泄露。

測試數(shù)據(jù)：

9.鏈表尾部刪除節(jié)點

具體怎么實現(xiàn)的都注釋在代碼邊上了，就直接開始測試用例看一下有沒有問題。

為了方便對比，每次刪除一個節(jié)點后都有打印一次鏈表在屏幕上。

可以看出這個代碼是成功的了，將尾部的三個數(shù)據(jù)都成功的刪除了。
那么再來看一下assert函數(shù)能不能起作用，這邊故意多刪除幾個，看會不會報錯。


這里也是能看見是報錯了的，并且能夠直接看出來是在list.c文件的第75行出的問題，如果再看一次實現(xiàn)函數(shù)的代碼的話，確實就能看見是75行的assert報的錯誤。

10.鏈表頭部刪除節(jié)點

函數(shù)實現(xiàn)：

測試用例：

可以看出，頭刪也是成功了，因為assert函數(shù)的實現(xiàn)是一樣的，這邊就不過多測試了。

11.查找和修改節(jié)點

函數(shù)實現(xiàn)：

函數(shù)的測試用例：


可以看到這個查找和修改的功能也是成功了。

12.在鏈表pos之前插入節(jié)點

函數(shù)實現(xiàn)：

測試用例：


數(shù)字9也是成功的插入到了3的前面，那么這個函數(shù)也是成功的實現(xiàn)了。
而成功的實現(xiàn)了這個函數(shù)，我們就可以將這個函數(shù)復用到頭插和尾插函數(shù)當中。
函數(shù)復用實現(xiàn)：

1. 頭插：
2. 尾插：

13.在鏈表pos處刪除該節(jié)點

函數(shù)實現(xiàn)：

測試用例：

可以看到結果也是與我們預期的相符合，這個函數(shù)也是成功了。
同樣這個函數(shù)也是可以復用到頭刪和尾刪中的。

1. 頭刪：

2. 尾刪：

test.c

那么接下來就把所有的代碼放在這里。
test.c是函數(shù)主題的框架，用來執(zhí)行函數(shù)的功能。

list.c

list.c是每個功能函數(shù)具體實現(xiàn)的代碼

list.h

list.h是聲明頭文件和函數(shù)指針以及定義結構體的部分。
本篇完畢，如有錯誤，歡迎大佬指正！文章來源地址http://www.zghlxwxcb.cn/news/detail-860595.html

到了這里，關于【數(shù)據(jù)結構】帶頭雙向循環(huán)鏈表（小白作品，如果有誤，請大佬指點）的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關文章，希望大家以后多多支持TOY模板網(wǎng)！