C語言超詳細(xì)講解雙向帶頭循環(huán)鏈表
在上一篇所講述的單鏈表中，存在一些缺陷：
1、在進行尾插和尾刪時，需要遍歷鏈表找到尾結(jié)點
2、在進行中間插入和刪除時，也需要先遍歷鏈表找到前一個結(jié)點
對于這些缺陷，可以采用一種結(jié)構(gòu)更為復(fù)雜的鏈表 雙向帶頭循環(huán)鏈表
雙向帶頭循環(huán)鏈表結(jié)構(gòu)雖然復(fù)雜，但在鏈表的操作上帶來了很大的優(yōu)勢
一、雙向帶頭循環(huán)鏈表的結(jié)構(gòu)
//存儲數(shù)據(jù)的類型，這里以 int 來舉例
typedef int LTDataType;
//結(jié)點的類型
typedef struct ListNode
{
LTDataType data;
struct ListNode* prev;
struct ListNode* next;
}LTNode;
二、雙向帶頭循環(huán)鏈表的函數(shù)接口
1. 申請結(jié)點
在插入等操作時需要申請結(jié)點，為了避免麻煩重復(fù)的操作，這里將申請結(jié)點封裝為一個函數(shù)
申請結(jié)點函數(shù)如下：
LTNode* BuyLTNode(LTDataType x)
{
LTNode* newnode = (LTNode*)malloc(sizeof(LTNode));
if (newnode == NULL)
{
//開辟空間失敗，打印錯誤信息
perror("malloc");
//結(jié)束程序
exit(-1);
}
newnode->data = x;
newnode->prev = newnode->next = NULL;
return newnode;
}
2. 初識化
在雙向帶頭循環(huán)鏈表中，即使沒有存儲數(shù)據(jù)也 至少會包含一個哨兵位的頭結(jié)點
初始化函數(shù)如下：
LTNode* InitLT()
{
//申請頭結(jié)點，頭結(jié)點的數(shù)據(jù)存什么無關(guān)緊要
LTNode* phead = BuyLTNode(-1);
//改變指針指向，構(gòu)成循環(huán)
phead->prev = phead->next = phead;
return phead;
}
3. 打印
為了驗證插入、刪除等得到的結(jié)果是否正確，提供打印函數(shù)，這里數(shù)據(jù)類型以 int 為例，當(dāng)讀者采用的類型不同時，自行更改函數(shù)即可
打印函數(shù)如下：
void LTPrint(LTNode* phead)
{
//鏈表不能為空
assert(phead);
LTNode* cur = phead->next;
printf("head->");
while (cur != phead)
{
printf("%d->", cur->data);
cur = cur->next;
}
printf("head\n");
}
4. 尾插尾刪
尾插：在鏈表的最后一個結(jié)點之后插入結(jié)點
尾插函數(shù)如下：
void LTPushBack(LTNode* phead, LTDataType x)
{
//鏈表不能為空
assert(phead);
LTNode* newnode = BuyLTNode(x);
//找到尾結(jié)點
LTNode* tail = phead->prev;
//改變指針指向
tail->next = newnode;
newnode->prev = tail;
newnode->next = phead;
phead->prev = newnode;
}
尾刪：刪除鏈表最后一個結(jié)點
尾刪函數(shù)如下：
void LTPopBack(LTNode* phead)
{
assert(phead); //鏈表不能為空
assert(phead->next != phead); //空鏈表不能刪
//找尾結(jié)點及尾結(jié)點的前一個結(jié)點
LTNode* tail = phead->prev;
LTNode* tailPrev = tail->prev;
//改變指針指向
tailPrev->next = phead;
phead->prev = tailPrev;
free(tail);
}
5. 頭插頭刪
頭插： 在第一個結(jié)點之前插入新結(jié)點
頭插函數(shù)如下：
void LTPushFront(LTNode* phead, LTDataType x)
{
//鏈表不能為空
assert(phead);
LTNode* newnode = BuyLTNode(x);
//找到頭結(jié)點后的第一個結(jié)點
LTNode* first = phead->next;
//改變指針指向
phead->next = newnode;
newnode->prev = phead;
newnode->next = first;
first->prev = newnode;
}
頭刪：刪除鏈表的第一個結(jié)點
頭刪函數(shù)如下：
void LTPopFront(LTNode* phead)
{
assert(phead); //鏈表不能為空
assert(phead->next != phead); //空鏈表不能刪
//找到頭結(jié)點后的第一個和第二個結(jié)點
LTNode* first = phead->next;
LTNode* second = first->next;
//改變指針指向
phead->next = second;
second->prev = phead;
free(first);
}
6. 查找
查找：如果數(shù)據(jù)存在，返回該數(shù)據(jù)結(jié)點的指針，不存在返回 NULL
查找函數(shù)如下：
LTNode* LTFind(LTNode* phead, LTDataType x)
{
//鏈表不能為空
assert(phead);
LTNode* cur = phead->next;
while (cur != phead)
{
if (cur->data == x) return cur;
cur = cur->next;
}
return NULL;
}
7. 中間插入和刪除
中間插入：通過查找函數(shù) LTFind 獲得指向結(jié)點的指針 pos，在 pos 指向的 結(jié)點之前 插入結(jié)點
在 pos 之前插入結(jié)點函數(shù)如下：
void LTInsert(LTNode* pos, LTDataType x)
{
//pos 不能為空
assert(pos);
LTNode* newnode = BuyLTNode(x);
//找到 pos 的前一個結(jié)點
LTNode* posPrev = pos->prev;
//改變指針指向
posPrev->next = newnode;
newnode->prev = posPrev;
newnode->next = pos;
pos->prev = newnode;
}
在調(diào)用中間插入函數(shù) LTInsert 時
- 如果在鏈表頭結(jié)點之前插入數(shù)據(jù)，便和尾插函數(shù)的功能一樣
- 如果在鏈表頭結(jié)點之后插入數(shù)據(jù)，便和頭插函數(shù)的功能一樣
因此在尾插和頭插函數(shù)的實現(xiàn)中可以直接調(diào)用中間插入函數(shù) LTInsert
尾插和頭插函數(shù)更改如下：
//尾插
void LTPushBack(LTNode* phead, LTDataType x)
{
//鏈表不能為空
assert(phead);
LTInsert(phead, x);
}
//頭插
void LTPushFront(LTNode* phead, LTDataType x)
{
//鏈表不能為空
assert(phead);
LTInsert(phead->next, x);
}
中間刪除：通過查找函數(shù) LTFind 獲得指向結(jié)點的指針 pos，刪除 pos 指向的結(jié)點
刪除 pos 指向的結(jié)點函數(shù)如下：
void LTErase(LTNode* pos)
{
//pos 不能為空
assert(pos);
//找到 pos 的前一個和后一個結(jié)點
LTNode* posPrev = pos->prev;
LTNode* posNext = pos->next;
//改變指針指向
posPrev->next = posNext;
posNext->prev = posPrev;
free(pos);
}
在調(diào)用中間刪除函數(shù) LTErase 時
- 如果刪除鏈表頭結(jié)點的前一個結(jié)點，便和尾刪函數(shù)的功能一樣
- 如果刪除鏈表頭結(jié)點的后一個結(jié)點，便和頭刪函數(shù)的功能一樣
因此在尾刪和頭刪函數(shù)的實現(xiàn)中可以直接調(diào)用中間刪除函數(shù) LTErase
尾刪和頭刪函數(shù)更改如下：
//尾刪
void LTPopBack(LTNode* phead)
{
assert(phead); //鏈表不能為空
assert(phead->next != phead); //空鏈表不能刪
LTErase(phead->prev);
}
//頭刪
void LTPopFront(LTNode* phead)
{
assert(phead); //鏈表不能為空
assert(phead->next != phead); //空鏈表不能刪
LTErase(phead->next);
}
8. 判空及求鏈表長度
判空：判斷鏈表是否為空
判空函數(shù)如下：
bool LTEmpty(LTNode* phead)
{
//鏈表不能為空
assert(phead);
return phead->next == phead;
}
鏈表長度：鏈表有效數(shù)據(jù)個數(shù)
鏈表長度函數(shù)如下：
size_t LTSize(LTNode* phead)
{
//鏈表不能為空
assert(phead);
size_t size = 0;
LTNode* cur = phead->next;
while (cur != phead)
{
size++;
cur = cur->next;
}
return size;
}
9. 銷毀單鏈表
在鏈表中，存儲數(shù)據(jù)的結(jié)點是由自己開辟的，當(dāng)不使用鏈表時，應(yīng)將其銷毀
銷毀鏈表函數(shù)如下：
void LTDestroy(LTNode* phead)
{
//鏈表不能為空
assert(phead);
LTNode* cur = phead->next;
while (cur != phead)
{
LTNode* curNext = cur->next;
free(cur);
cur = curNext;
}
free(phead);
}
到此這篇關(guān)于C語言超詳細(xì)講解雙向帶頭循環(huán)鏈表的文章就介紹到這了,更多相關(guān)C語言雙向帶頭循環(huán)鏈表內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！
相關(guān)文章
下面小編就為大家?guī)硪黄狢++ Assert()斷言機制原理以及使用方法。小編覺得挺不錯的，現(xiàn)在就分享給大家，也給大家做個參考。一起跟隨小編過來看看吧2017-01-01
這篇文章主要介紹了C++如何調(diào)用matlab函數(shù)的相關(guān)資料,非常不錯，具有參考借鑒價值，需要的朋友可以參考下2016-11-11
這篇文章主要為大家詳細(xì)介紹了OpenCV實現(xiàn)圖像連通域，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價值，感興趣的小伙伴們可以參考一下2021-06-06
使用VS2010的時候，發(fā)現(xiàn)了不少問題，而本文則是介紹使用中需要的問題，已經(jīng)解決方案。2014-10-10
詳解Qt6?QML?Settings?location?不創(chuàng)建指定路徑文件
到Qt6以后,?棄用了fileName屬性,改用location屬性,但有個坑,本文就來介紹一下Qt6?QML?Settings?location不創(chuàng)建指定路徑文件,具有一定的參考價值,感興趣的可以了解一下2025-03-03
這篇文章主要為大家詳細(xì)介紹了C語言鏈表的完整操作演示，具有一定的參考價值，感興趣的小伙伴們可以參考一下2018-05-05
const_cast該函數(shù)用于去除指針變量的常量屬性，將它轉(zhuǎn)換為一個對應(yīng)指針類型的普通變量。反過來，也可以將一個非常量的指針變量轉(zhuǎn)換為一個常指針變量2013-10-10
這篇文章主要介紹了C++成員初始化列表，除了可以使用構(gòu)造函數(shù)對類成員進行初始化之外，C++還提供了另外一種初始化的方法，叫做成員初始化列表。下面來看看文章的詳細(xì)吧,需要的朋友可以參考一下2022-04-04
本文主要介紹jquery ready,這里整理了相關(guān)資料及相關(guān)示例代碼幫助大家學(xué)習(xí)參考，有興趣的小伙伴可以參考下2016-08-08
這篇文章主要介紹了循環(huán)隊列詳解及隊列的順序表示和實現(xiàn)的相關(guān)資料,需要的朋友可以參考下2016-12-12