溫馨提示×
您好，登錄后才能下訂單哦！
點擊 登錄注冊 即表示同意《億速云用戶服務條款》
您好，登錄后才能下訂單哦！
這篇文章主要講解了“C語言數據結構中雙向帶頭循環鏈表怎么實現”，文中的講解內容簡單清晰，易于學習與理解，下面請大家跟著小編的思路慢慢深入，一起來研究和學習“C語言數據結構中雙向帶頭循環鏈表怎么實現”吧！
來畫張圖總體回顧下：
在我們學習的鏈表中，其實總共有8種，都是單雙向和帶不帶頭以及帶不帶環的任意組合
今兒要學習的是雙向 - 帶頭 - 循環鏈表，聽名字就覺著結構很復雜，要比曾經學的單向 - 不帶頭 - 不循環 鏈表的結構復雜的多 ，確實也是。先來畫張圖整體感受下：
解釋：
雙向：就要確保每個數據存兩個指針next和prev。next指向下一個節點，prev指向上一個節點
帶頭：帶一個哨兵位的頭節點在數據的最前頭。
循環：尾節點的next指向哨兵位頭節點，而哨兵位的上一個節點prev指向尾節點，構成循環。
正文開始：
因為是雙向鏈表，所以在結構體里頭必然有兩個指針，一個next指向下一個節點，一個prev指向上一個節點。
List.h 文件：
//創建雙向鏈表結構
typedef int LTDataType; //方便后續更改數據類型，本文以int整型為主
typedef struct ListNode
{
LTDataType data; //存儲數據
struct ListNode* next; //指向下一個
struct ListNode* prev; //指向上一個
}LTNode; //方便后續使用，不需要重復些struct思路：
在初始化的時候要傳地址，因為形參的改變不會影響實參，pphead的改變不會影響pList，要傳pList的地址，用**pphead來接收，此時就要assert斷言了，因為二級指針地址不可能位空。因為是雙向循環鏈表，所以要將創建好的哨兵位節點的next和prev均指向自己。
List.h 文件：（1）
//初始化鏈表（二級指針版） void ListInit(LTNode* pphead);
List.c 文件：（1）
//初始化鏈表（二級指針版）
void ListInit(LTNode** pphead)
{
//傳二級指針，那么當然要斷言
assert(pphead);
*pphead = BuyLTNode(0);//因為是帶哨兵位的頭節點，所以一開始就要給一個節點
//為了循環，要讓哨兵位的next和prev均指向自己
(*pphead)->next = *pphead; //注意優先級，*pphead要加括號
(*pphead)->prev = *pphead;
}注意：
上一種方法我們傳的是二級指針，那么可以傳一級指針嗎，其實也是可以的，只需寫個函數返回指針即可
List.h 文件：（2）
//初始化鏈表（一級指針版本） LTNode* ListInit();
List.c 文件：（2）
//初始化鏈表（一級指針版）
LTNode* ListInit()
{
LTNode* phead = BuyLTNode(0);
phead->next = phead;
phead->prev = phead;
return phead;
}List.c 文件：
//創建新節點
LTNode* BuyLTNode(LTDataType x)
{
LTNode* newnode = (LTNode*)malloc(sizeof(LTNode));
if (newnode == NULL)
{
printf("malloc fail\n");
exit(-1);
}
newnode->data = x;
newnode->next = NULL;
newnode->prev = NULL;
return newnode; //返回新創建的節點
}思路：
既然是打印，首先要搞明白一點，哨兵位不用來存放有效數據，那么就不需要打印，定義一個cur指針來迭代，那么應該從phead的next開始打印，當cur走完一遍，重又回到phead的時候停止
List.h 文件：
//打印鏈表 void ListPrint(LTNode* phead);
List.c 文件：
//打印鏈表
void ListPrint(LTNode* phead)
{
assert(phead);//斷言
LTNode* cur = phead->next;
while (cur != phead)
{
printf("%d ", cur->data);
cur = cur->next;
}
printf("\n");
}思路：
既然是銷毀鏈表了，那么自然是要把鏈表的所有元素包括哨兵位都給銷毀掉，但畢竟剛開始傳phead的時候是不能為空的，所以要斷言，在把所有有效數據銷毀后最后再銷毀哨兵位即可。
法一：遍歷
定義一個指針cur，從phead的next第一個有效數據開始free，保存下一個，再free，依次遍歷下去
法二：附用ListErase函數
此法也可以，不過每次Erase完，都會把前后兩個節點再鏈接起來，雖說最后都會銷毀，但duck不必多此一舉，所有直接采用法一比較好
List.h 文件：
//銷毀鏈表 void ListDestory(LTNode* phead);
List.c 文件：
//銷毀鏈表
void ListDestory(LTNode* phead)
{
assert(phead);
LTNode* cur = phead->next;
//銷毀從第一個節點到尾部的數據
while (cur != phead)
{
LTNode* next = cur->next;
//ListErase(cur);
free(cur);
cur = next;
}
//置空哨兵位節點phead
free(phead);
phead = NULL;
}Test.c 文件：
void TestList7()
{
LTNode* pList = ListInit();
for (int i = 1; i <= 7; i++)
{
ListPushBack(pList, i); //尾插7個數字
}
ListPrint(pList);//打印
//銷毀鏈表
ListDestory(pList);
pList = NULL;
}思路：
假設我們已經進行了尾插4個數字，現在想在數字3的前面插入30，那么首先就要查找有無數字3，若有，則插入。注意：這里需要用到后文才講到的查找函數，這里直接引用了，詳解看后文即可，問題不大！
首先，將30放到新創建的節點newnode里頭，為了實現雙向，要先把3的前一個數據2的next指向新節點newnode，把newnode的prev指向2，newnode的next指向3，3的prev指向newnode。
List.h 文件：
//在pos前插入數據 void ListInsert(LTNode* pos, LTDataType x);
List.c 文件：
//在pos前插入數據
void ListInsert(LTNode* pos, LTDataType x)
{
assert(pos);
//創建插入數據的新節點
LTNode* newnode = BuyLTNode(x);
//鏈接左側
pos->prev->next = newnode;
newnode->prev = pos->prev;
//鏈接右側
newnode->next = pos;
pos->prev = newnode;
}Test.c 文件：
void TestList3()
{
LTNode* pList = ListInit();
for (int i = 1; i <= 7; i++)
{
ListPushBack(pList, i); //尾插7個數據
}
ListPrint(pList);//打印尾插的7個
//尋找數字
LTNode* pos = ListFind(pList, 3);
if (pos)
{
ListInsert(pos, 30); //找到數字3就插入
}
ListPrint(pList);//打印
}效果如下：
思路：
首先，因為此鏈表是帶哨兵位的頭節點，所以頭節點必然不為空，剛開始就要assert斷言。其次，單鏈表尾插需要找尾，雙向鏈表雖然也需要，不過非常簡單，不需要再遍歷鏈表了，因為哨兵位頭節點的phead的上一個節點指向的就是尾，這就充分體現了雙向循環的好處，找到了尾節點就需要再創建一個節點存儲插入數據，方便尾插。
List.h 文件：
//尾插 void ListPushBack(LTNode* phead, LTDataType x);
List.c 文件：1.0
//尾插1.0
void ListPushBack(LTNode* phead, LTDataType x)
{
assert(phead); //斷言，防止頭節點為空
LTNode* tail = phead->prev; //找到尾節點，便于后續插入數據
LTNode* newnode = BuyLTNode(x);//創建新節點
//將此新插入的尾節點與上一個節點鏈接起來
tail->next = newnode;
newnode->prev = tail;
//將尾節點與哨兵位phead鏈接起來構成循環
newnode->next = phead;
phead->prev = newnode;
}Test.c 文件：
void TestList1()
{
//初始化（法一）
/*LTNode* pList = NULL;
ListInit(&pList);*/
//初始化（法二）
LTNode* pList = ListInit();
for (int i = 1; i <= 7; i++)
{
ListPushBack(pList, i); //尾插7個數據
}
ListPrint(pList);//打印尾插的7個
}效果如下：
注意：
在上文中，我們學習了在pos前插入數據，那么設想一下，當pos就等于phead的時候，它（phead）的前不就是鏈表的尾部嗎，那么理所應當，尾插也可以這樣完成：
List.c 文件：2.0
//尾插2.0
void ListPushBack(LTNode* phead, LTDataType x)
{
assert(phead);
ListInsert(phead, x);
}思路：
前面我們已經學習了在pos前插入數據，那么頭插的實現就尤為簡單了，當pos為原第一個數據phead->next時，此時就是在其之前插入數據，那么實現的不久是頭插嗎，如下：
List.h 文件：
//頭插 void ListPushFront(LTNode* phead, LTDataType x);
List.c 文件：
//頭插
void ListPushFront(LTNode* phead, LTDataType x)
{
assert(phead);
ListInsert(phead->next, x);
}Test.c 文件：
void TestList4()
{
LTNode* pList = ListInit();
for (int i = 1; i <= 7; i++)
{
ListPushBack(pList, i); //尾插7個數字
}
ListPrint(pList);//打印
for (int i = -2; i <= 0; i++)
{
ListPushFront(pList, i); //頭插3個數字
}
ListPrint(pList);//打印
}效果如下：
思路：
刪除pos處數據其實也很簡單，有點類似于把pos處直接忽略的思想，或者說是繞過去。首先，需要找到pos的上一個節點prev和下一個節點next，將prev和next互相鏈接即可，直接跳過了pos，這樣就實現了刪除pos處節點的數據，記得把pos處給free釋放掉。這里我們以pos為2示例：
List.h 文件：
//刪除pos處數據 void ListErase(LTNode* pos);
List.c 文件：
//刪除pos處數據
void ListErase(LTNode* pos)
{
assert(pos);
//定義兩個指針保存pos兩邊的節點
LTNode* prev = pos->prev;
LTNode* next = pos->next;
//將prev和next鏈接起來
prev->next = next;
next->prev = prev;
//free釋放
free(pos);
pos = NULL;
}Test.c 文件：
void TestList5()
{
LTNode* pList = ListInit();
for (int i = 1; i <= 7; i++)
{
ListPushBack(pList, i); //尾插7個數據
}
ListPrint(pList);//打印尾插的7個
//尋找數字
LTNode* pos = ListFind(pList, 3);
if (pos)
{
ListErase(pos); //刪除pos處數據
pos = NULL; //形參的改變不會影響實參，最好在這置空pos
}
ListPrint(pList);//打印
}效果如下：
思路：
雙向循環鏈表的特點將再次得以體現，根據其特性，我們知道phead的prev指向尾節點，用tail指針保存，再定義一個指針tailPrev指向tail的prev，現僅需將tailPrev的next指向哨兵位節點phead，再把哨兵位phead的prev重新置成tailPrev即可，但是別忘記把刪掉的尾節點給釋放掉，得free(tail)。記得要斷言鏈表不能為空，因為不能刪除哨兵位節點。
List.H 文件：
//尾刪 void ListPopBack(LTNode* phead);
List.c 文件：1.0
//尾刪
void ListPopBack(LTNode* phead)
{
assert(phead);//本身就有哨兵位，不能為空，要斷言
assert(phead->next != phead); //防止鏈表為空，導致刪除哨兵位節點
LTNode* tail = phead->prev;
LTNode* tailPrev = tail->prev;
//釋放尾節點
free(tail);
tail = NULL;
//將鏈表循環起來
tailPrev->next = phead;
phead->prev = tailPrev;
}Test.c 文件：
void TestList2()
{
LTNode* pList = ListInit();
for (int i = 1; i <= 7; i++)
{
ListPushBack(pList, i); //尾插7個數據
}
ListPrint(pList);//打印尾插的7個
//尾刪兩次
ListPopBack(pList);
ListPopBack(pList);
ListPrint(pList);//再次打印
}效果如下：
注意：
前文我們已經學了刪除pos處節點的數據，那么當pos為phead->prev時，刪除的是不是就是尾節點，所以，尾刪理所應當可以這樣寫：
List.c 文件：2.0
//尾刪
void ListPopBack(LTNode* phead)
{
assert(phead);//本身就有哨兵位，不能為空，要斷言
assert(phead->next != phead); //防止鏈表為空，導致刪除哨兵位節點
ListErase(phead->prev);
}思路：
有了上文之鑒，我們可以直接利用前面寫的刪除pos處數據的函數來完成，當pos為phead->prev時，pos的位置就是尾，此時刪除的就是尾。當然還得注意一點，需要額外assert斷言防止刪除的數據為哨兵位的節點。
List.h 文件：
//頭刪 void ListPopFront(LTNode* phead);
List.c 文件：
//頭刪
void ListPopFront(LTNode* phead)
{
assert(phead);
assert(phead->next != phead); //防止刪除哨兵位節點
ListErase(phead->next);
}Test.c 文件：
void TestList6()
{
LTNode* pList = ListInit();
for (int i = 1; i <= 7; i++)
{
ListPushBack(pList, i); //尾插7個數字
}
ListPrint(pList);//打印
//頭插3個數字
ListPushFront(pList, 0);
ListPushFront(pList, -1);
ListPushFront(pList, -2);
ListPrint(pList);//打印
//尾刪3個數字
ListPopBack(pList);
ListPopBack(pList);
ListPopBack(pList);
ListPrint(pList);//打印
//頭刪3個數字
ListPopFront(pList);
ListPopFront(pList);
ListPopFront(pList);
ListPrint(pList);//打印
}效果如下：
思路：
查找數據其實也比較簡單，首先，定義一個指針cur指向哨兵位phead的next，依次遍歷cur看cur->data是否為查找的數據x，如果是，則返回cur，否則繼續（cur=cur->next），若找不到則返回NULL。
List.h 文件：
//鏈表查找 LTNode* ListFind(LTNode* phead, LTDataType x);
List.c 文件：
//鏈表查找
LTNode* ListFind(LTNode* phead, LTDataType x)
{
assert(phead);
LTNode* cur = phead->next;
while (cur != phead)
{
if (cur->data == x)
{
return cur; //找到就返回cur
}
cur = cur->next;
}
return NULL; //找不到就返回空
}#pragma once
#include<stdio.h>
#include<assert.h>
#include<stdlib.h>
//創建雙向鏈表結構
typedef int LTDataType; //方便后續更改數據類型，本文以int整型為主
typedef struct ListNode
{
LTDataType data; //存儲數據
struct ListNode* next; //指向下一個
struct ListNode* prev; //指向上一個
}LTNode; //方便后續使用，不需要重復些struct
//初始化鏈表（二級指針版本）
/*void ListInit(LTNode** pphead);*/
//初始化鏈表（一級指針版本）
LTNode* ListInit();
//打印鏈表
void ListPrint(LTNode* phead);
//鏈表查找
LTNode* ListFind(LTNode* phead, LTDataType x);
//銷毀鏈表
void ListDestory(LTNode* phead);
//尾插
void ListPushBack(LTNode* phead, LTDataType x);
//尾刪
void ListPopBack(LTNode* phead);
//頭插
void ListPushFront(LTNode* phead, LTDataType x);
//頭刪
void ListPopFront(LTNode* phead);
//在pos前插入數據
void ListInsert(LTNode* pos, LTDataType x);
//刪除pos處數據
void ListErase(LTNode* pos);#define _CRT_SECURE_NO_WARNINGS 1
#include"List.h"
//創建新節點
LTNode* BuyLTNode(LTDataType x)
{
LTNode* newnode = (LTNode*)malloc(sizeof(LTNode));
if (newnode == NULL)
{
printf("malloc fail\n");
exit(-1);
}
newnode->data = x;
newnode->next = NULL;
newnode->prev = NULL;
return newnode; //返回新創建的節點
}
//初始化鏈表（二級指針版）
/*void ListInit(LTNode** pphead)
{
//傳二級指針，那么當然要斷言
assert(pphead);
*pphead = BuyLTNode(0);//因為是帶哨兵位的頭節點，所以一開始就要給一個節點
//為了循環，要讓哨兵位的next和prev均指向自己
(*pphead)->next = *pphead; //注意優先級，*pphead要加括號
(*pphead)->prev = *pphead;
}*/
//初始化鏈表（一級指針版）
LTNode* ListInit()
{
LTNode* phead = BuyLTNode(0);
phead->next = phead;
phead->prev = phead;
return phead;
}
//打印鏈表
void ListPrint(LTNode* phead)
{
assert(phead);//斷言
LTNode* cur = phead->next;
while (cur != phead)
{
printf("%d ", cur->data);
cur = cur->next;
}
printf("\n");
}
//鏈表查找
LTNode* ListFind(LTNode* phead, LTDataType x)
{
assert(phead);
LTNode* cur = phead->next;
while (cur != phead)
{
if (cur->data == x)
{
return cur; //找到就返回cur
}
cur = cur->next;
}
return NULL; //找不到就返回空
}
//銷毀鏈表
void ListDestory(LTNode* phead)
{
assert(phead);
LTNode* cur = phead->next;
//銷毀從第一個節點到尾部的數據
while (cur != phead)
{
LTNode* next = cur->next;
//ListErase(cur);
free(cur);
cur = next;
}
//置空哨兵位節點phead
free(phead);
phead = NULL;
}
//尾插
void ListPushBack(LTNode* phead, LTDataType x)
{
assert(phead); //斷言，防止頭節點為空
/*
法一：
LTNode* tail = phead->prev; //找到尾節點，便于后續插入數據
LTNode* newnode = BuyLTNode(x);//創建新節點
//將此新插入的尾節點與上一個節點鏈接起來
tail->next = newnode;
newnode->prev = tail;
//將尾節點與哨兵位phead鏈接起來構成循環
newnode->next = phead;
phead->prev = newnode;
*/
//法二：
ListInsert(phead, x);
}
//尾刪
void ListPopBack(LTNode* phead)
{
assert(phead);//本身就有哨兵位，不能為空，要斷言
assert(phead->next != phead); //防止鏈表為空，導致刪除哨兵位節點
/*
法一：
LTNode* tail = phead->prev;
LTNode* tailPrev = tail->prev;
//釋放尾節點
free(tail);
tail = NULL;
//將鏈表循環起來
tailPrev->next = phead;
phead->prev = tailPrev;
*/
//法二：
ListErase(phead->prev);
}
//頭插
void ListPushFront(LTNode* phead, LTDataType x)
{
assert(phead);
ListInsert(phead->next, x);
}
//頭刪
void ListPopFront(LTNode* phead)
{
assert(phead);
assert(phead->next != phead); //防止刪除哨兵位節點
ListErase(phead->next);
}
//在pos前插入數據
void ListInsert(LTNode* pos, LTDataType x)
{
assert(pos);
//創建插入數據的新節點
LTNode* newnode = BuyLTNode(x);
//鏈接左側
pos->prev->next = newnode;
newnode->prev = pos->prev;
//鏈接右側
newnode->next = pos;
pos->prev = newnode;
}
//刪除pos處數據
void ListErase(LTNode* pos)
{
assert(pos);
//定義兩個指針保存pos兩邊的節點
LTNode* prev = pos->prev;
LTNode* next = pos->next;
//將prev和next鏈接起來
prev->next = next;
next->prev = prev;
//free釋放
free(pos);
pos = NULL;
}#define _CRT_SECURE_NO_WARNINGS 1
#include"List.h"
void TestList1()
{
//初始化（法一）
/*LTNode* pList = NULL;
ListInit(&pList);*/
//初始化（法二）
LTNode* pList = ListInit();
for (int i = 1; i <= 7; i++)
{
ListPushBack(pList, i); //尾插7個數據
}
ListPrint(pList);//打印尾插的7個
}
void TestList2()
{
LTNode* pList = ListInit();
for (int i = 1; i <= 7; i++)
{
ListPushBack(pList, i); //尾插7個數據
}
ListPrint(pList);//打印尾插的7個
//尾刪兩次
ListPopBack(pList);
ListPopBack(pList);
ListPrint(pList);//再次打印
}
void TestList3()
{
LTNode* pList = ListInit();
for (int i = 1; i <= 7; i++)
{
ListPushBack(pList, i); //尾插7個數據
}
ListPrint(pList);//打印尾插的7個
//尋找數字
LTNode* pos = ListFind(pList, 3);
if (pos)
{
ListInsert(pos, 30); //找到數字3就插入
}
ListPrint(pList);//打印
}
void TestList4()
{
LTNode* pList = ListInit();
for (int i = 1; i <= 7; i++)
{
ListPushBack(pList, i); //尾插7個數字
}
ListPrint(pList);//打印
for (int i = -2; i <= 0; i++)
{
ListPushFront(pList, i); //頭插3個數字
}
ListPrint(pList);//打印
}
void TestList5()
{
LTNode* pList = ListInit();
for (int i = 1; i <= 7; i++)
{
ListPushBack(pList, i); //尾插7個數據
}
ListPrint(pList);//打印尾插的7個
//尋找數字
LTNode* pos = ListFind(pList, 3);
if (pos)
{
ListErase(pos); //刪除pos處數據
pos = NULL; //形參的改變不會影響實參，最好在這置空pos
}
ListPrint(pList);//打印
}
void TestList6()
{
LTNode* pList = ListInit();
for (int i = 1; i <= 7; i++)
{
ListPushBack(pList, i); //尾插7個數字
}
ListPrint(pList);//打印
//頭插3個數字
ListPushFront(pList, 0);
ListPushFront(pList, -1);
ListPushFront(pList, -2);
ListPrint(pList);//打印
//尾刪3個數字
ListPopBack(pList);
ListPopBack(pList);
ListPopBack(pList);
ListPrint(pList);//打印
//頭刪3個數字
ListPopFront(pList);
ListPopFront(pList);
ListPopFront(pList);
ListPrint(pList);//打印
//銷毀鏈表
ListDestory(pList);
pList = NULL;
}
void TestList7()
{
LTNode* pList = ListInit();
for (int i = 1; i <= 7; i++)
{
ListPushBack(pList, i); //尾插7個數字
}
ListPrint(pList);//打印
//銷毀鏈表
ListDestory(pList);
pList = NULL;
}
int main()
{
//TestList1();
//TestList2();
//TestList3();
//TestList4();
//TestList5();
//TestList6();
TestList7();
return 0;
}對比順序表和鏈表
| 不同點 | 順序表 | 鏈表 |
| 存儲空間上 | 物理上一定連續 | 邏輯上連續，但物理上不一定連續 |
| 隨機訪問 | 支持O(1) | 不支持O(N) |
| 任意位置插入或者刪除元素 | 可能需要搬移元素，效率低O(N) | 只需修改指針指向 |
| 插入 | 動態順序表，空間不夠時需要擴容 | 沒有容量的概念 |
| 應用場景 | 元素高效存儲+頻繁訪問 | 任意位置插入和刪除數據 |
| 緩存利用率 | 高 | 低 |
優缺點對比：
| 順序表 | 鏈表 | |
| 優點 | 1、物理空間是連續的，方便用下標隨機訪問。 2、CPU高速緩存命中率會更高。（補充） | 1、按需申請釋放空間。 2、任意位置可以O(1)插入刪除數據。 |
| 缺點 | 1、正因為物理空間連續，空間不夠需要擴容，擴容本身又一定消耗，其次擴容機制還存在一定的空間浪費。 2、頭部或者中部插入刪除，挪動數據，效率低，O(N)。 | 1、不支持下標的隨機訪問。 2、有些算法不適合在它上面進行，如：二分查找、排序等。 |
感謝各位的閱讀，以上就是“C語言數據結構中雙向帶頭循環鏈表怎么實現”的內容了，經過本文的學習后，相信大家對C語言數據結構中雙向帶頭循環鏈表怎么實現這一問題有了更深刻的體會，具體使用情況還需要大家實踐驗證。這里是億速云，小編將為大家推送更多相關知識點的文章，歡迎關注！
免責聲明：本站發布的內容（圖片、視頻和文字）以原創、轉載和分享為主，文章觀點不代表本網站立場，如果涉及侵權請聯系站長郵箱：is@yisu.com進行舉報，并提供相關證據，一經查實，將立刻刪除涉嫌侵權內容。
