C語(yǔ)言超詳細(xì)講解數(shù)據(jù)結(jié)構(gòu)中雙向帶頭循環(huán)鏈表
一、概念
前文我們已經(jīng)學(xué)習(xí)了單向鏈表，并通過(guò)oj題目深入了解了帶頭節(jié)點(diǎn)的鏈表以及帶環(huán)鏈表，來(lái)畫(huà)張圖總體回顧下：
在我們學(xué)習(xí)的鏈表中，其實(shí)總共有8種，都是單雙向和帶不帶頭以及帶不帶環(huán)的任意組合
今兒要學(xué)習(xí)的是雙向 - 帶頭 - 循環(huán)鏈表，聽(tīng)名字就覺(jué)著結(jié)構(gòu)很復(fù)雜，要比曾經(jīng)學(xué)的單向 - 不帶頭 - 不循環(huán) 鏈表的結(jié)構(gòu)復(fù)雜的多 ，確實(shí)也是。先來(lái)畫(huà)張圖整體感受下：
解釋：
- 雙向：就要確保每個(gè)數(shù)據(jù)存兩個(gè)指針next和prev。next指向下一個(gè)節(jié)點(diǎn)，prev指向上一個(gè)節(jié)點(diǎn)
- 帶頭：帶一個(gè)哨兵位的頭節(jié)點(diǎn)在數(shù)據(jù)的最前頭。
- 循環(huán)：尾節(jié)點(diǎn)的next指向哨兵位頭節(jié)點(diǎn)，而哨兵位的上一個(gè)節(jié)點(diǎn)prev指向尾節(jié)點(diǎn)，構(gòu)成循環(huán)。
正文開(kāi)始：
二、必備工作
2.1、創(chuàng)建雙向鏈表結(jié)構(gòu)
因?yàn)槭请p向鏈表，所以在結(jié)構(gòu)體里頭必然有兩個(gè)指針，一個(gè)next指向下一個(gè)節(jié)點(diǎn)，一個(gè)prev指向上一個(gè)節(jié)點(diǎn)。
List.h 文件：
//創(chuàng)建雙向鏈表結(jié)構(gòu)
typedef int LTDataType; //方便后續(xù)更改數(shù)據(jù)類型，本文以int整型為主
typedef struct ListNode
{
LTDataType data; //存儲(chǔ)數(shù)據(jù)
struct ListNode* next; //指向下一個(gè)
struct ListNode* prev; //指向上一個(gè)
}LTNode; //方便后續(xù)使用，不需要重復(fù)些struct2.2、初始化鏈表
思路：
在初始化的時(shí)候要傳地址，因?yàn)樾螀⒌母淖儾粫?huì)影響實(shí)參，pphead的改變不會(huì)影響pList，要傳pList的地址，用**pphead來(lái)接收，此時(shí)就要assert斷言了，因?yàn)槎?jí)指針地址不可能位空。因?yàn)槭请p向循環(huán)鏈表，所以要將創(chuàng)建好的哨兵位節(jié)點(diǎn)的next和prev均指向自己。
List.h 文件：（1）
//初始化鏈表（二級(jí)指針版） void ListInit(LTNode* pphead);
List.c 文件：（1）
//初始化鏈表（二級(jí)指針版）
void ListInit(LTNode** pphead)
{
//傳二級(jí)指針，那么當(dāng)然要斷言
assert(pphead);
*pphead = BuyLTNode(0);//因?yàn)槭菐诒坏念^節(jié)點(diǎn)，所以一開(kāi)始就要給一個(gè)節(jié)點(diǎn)
//為了循環(huán)，要讓哨兵位的next和prev均指向自己
(*pphead)->next = *pphead; //注意優(yōu)先級(jí)，*pphead要加括號(hào)
(*pphead)->prev = *pphead;
}注意：
上一種方法我們傳的是二級(jí)指針，那么可以傳一級(jí)指針嗎，其實(shí)也是可以的，只需寫(xiě)個(gè)函數(shù)返回指針即可
List.h 文件：（2）
//初始化鏈表（一級(jí)指針版本） LTNode* ListInit();
List.c 文件：（2）
//初始化鏈表（一級(jí)指針版）
LTNode* ListInit()
{
LTNode* phead = BuyLTNode(0);
phead->next = phead;
phead->prev = phead;
return phead;
}2.3、動(dòng)態(tài)申請(qǐng)節(jié)點(diǎn)
List.c 文件：
//創(chuàng)建新節(jié)點(diǎn)
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; //返回新創(chuàng)建的節(jié)點(diǎn)
}2.4、打印鏈表
思路：
既然是打印，首先要搞明白一點(diǎn)，哨兵位不用來(lái)存放有效數(shù)據(jù)，那么就不需要打印，定義一個(gè)cur指針來(lái)迭代，那么應(yīng)該從phead的next開(kāi)始打印，當(dāng)cur走完一遍，重又回到phead的時(shí)候停止
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");
}2.5、銷毀鏈表
思路：
既然是銷毀鏈表了，那么自然是要把鏈表的所有元素包括哨兵位都給銷毀掉，但畢竟剛開(kāi)始傳phead的時(shí)候是不能為空的，所以要斷言，在把所有有效數(shù)據(jù)銷毀后最后再銷毀哨兵位即可。
法一：遍歷
定義一個(gè)指針cur，從phead的next第一個(gè)有效數(shù)據(jù)開(kāi)始free，保存下一個(gè)，再free，依次遍歷下去
法二：附用ListErase函數(shù)
此法也可以，不過(guò)每次Erase完，都會(huì)把前后兩個(gè)節(jié)點(diǎn)再鏈接起來(lái)，雖說(shuō)最后都會(huì)銷毀，但duck不必多此一舉，所有直接采用法一比較好
List.h 文件：
//銷毀鏈表 void ListDestory(LTNode* phead);
List.c 文件：
//銷毀鏈表
void ListDestory(LTNode* phead)
{
assert(phead);
LTNode* cur = phead->next;
//銷毀從第一個(gè)節(jié)點(diǎn)到尾部的數(shù)據(jù)
while (cur != phead)
{
LTNode* next = cur->next;
//ListErase(cur);
free(cur);
cur = next;
}
//置空哨兵位節(jié)點(diǎn)phead
free(phead);
phead = NULL;
}Test.c 文件：
void TestList7()
{
LTNode* pList = ListInit();
for (int i = 1; i <= 7; i++)
{
ListPushBack(pList, i); //尾插7個(gè)數(shù)字
}
ListPrint(pList);//打印
//銷毀鏈表
ListDestory(pList);
pList = NULL;
}三、主要功能
3.1、在pos節(jié)點(diǎn)前插入數(shù)據(jù)
思路：
假設(shè)我們已經(jīng)進(jìn)行了尾插4個(gè)數(shù)字，現(xiàn)在想在數(shù)字3的前面插入30，那么首先就要查找有無(wú)數(shù)字3，若有，則插入。注意：這里需要用到后文才講到的查找函數(shù)，這里直接引用了，詳解看后文即可，問(wèn)題不大！
首先，將30放到新創(chuàng)建的節(jié)點(diǎn)newnode里頭，為了實(shí)現(xiàn)雙向，要先把3的前一個(gè)數(shù)據(jù)2的next指向新節(jié)點(diǎn)newnode，把newnode的prev指向2，newnode的next指向3，3的prev指向newnode。
List.h 文件：
//在pos前插入數(shù)據(jù) void ListInsert(LTNode* pos, LTDataType x);
List.c 文件：
//在pos前插入數(shù)據(jù)
void ListInsert(LTNode* pos, LTDataType x)
{
assert(pos);
//創(chuàng)建插入數(shù)據(jù)的新節(jié)點(diǎn)
LTNode* newnode = BuyLTNode(x);
//鏈接左側(cè)
pos->prev->next = newnode;
newnode->prev = pos->prev;
//鏈接右側(cè)
newnode->next = pos;
pos->prev = newnode;
}Test.c 文件：
void TestList3()
{
LTNode* pList = ListInit();
for (int i = 1; i <= 7; i++)
{
ListPushBack(pList, i); //尾插7個(gè)數(shù)據(jù)
}
ListPrint(pList);//打印尾插的7個(gè)
//尋找數(shù)字
LTNode* pos = ListFind(pList, 3);
if (pos)
{
ListInsert(pos, 30); //找到數(shù)字3就插入
}
ListPrint(pList);//打印
}效果如下：
尾插
思路：
首先，因?yàn)榇随湵硎菐诒坏念^節(jié)點(diǎn)，所以頭節(jié)點(diǎn)必然不為空，剛開(kāi)始就要assert斷言。其次，單鏈表尾插需要找尾，雙向鏈表雖然也需要，不過(guò)非常簡(jiǎn)單，不需要再遍歷鏈表了，因?yàn)樯诒活^節(jié)點(diǎn)的phead的上一個(gè)節(jié)點(diǎn)指向的就是尾，這就充分體現(xiàn)了雙向循環(huán)的好處，找到了尾節(jié)點(diǎn)就需要再創(chuàng)建一個(gè)節(jié)點(diǎn)存儲(chǔ)插入數(shù)據(jù)，方便尾插。
List.h 文件：
//尾插 void ListPushBack(LTNode* phead, LTDataType x);
List.c 文件：1.0
//尾插1.0
void ListPushBack(LTNode* phead, LTDataType x)
{
assert(phead); //斷言，防止頭節(jié)點(diǎn)為空
LTNode* tail = phead->prev; //找到尾節(jié)點(diǎn)，便于后續(xù)插入數(shù)據(jù)
LTNode* newnode = BuyLTNode(x);//創(chuàng)建新節(jié)點(diǎn)
//將此新插入的尾節(jié)點(diǎn)與上一個(gè)節(jié)點(diǎn)鏈接起來(lái)
tail->next = newnode;
newnode->prev = tail;
//將尾節(jié)點(diǎn)與哨兵位phead鏈接起來(lái)構(gòu)成循環(huán)
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個(gè)數(shù)據(jù)
}
ListPrint(pList);//打印尾插的7個(gè)
}效果如下：
注意：
在上文中，我們學(xué)習(xí)了在pos前插入數(shù)據(jù)，那么設(shè)想一下，當(dāng)pos就等于phead的時(shí)候，它（phead）的前不就是鏈表的尾部嗎，那么理所應(yīng)當(dāng)，尾插也可以這樣完成：
List.c 文件：2.0
//尾插2.0
void ListPushBack(LTNode* phead, LTDataType x)
{
assert(phead);
ListInsert(phead, x);
}頭插
思路：
前面我們已經(jīng)學(xué)習(xí)了在pos前插入數(shù)據(jù)，那么頭插的實(shí)現(xiàn)就尤為簡(jiǎn)單了，當(dāng)pos為原第一個(gè)數(shù)據(jù)phead->next時(shí)，此時(shí)就是在其之前插入數(shù)據(jù)，那么實(shí)現(xiàn)的不久是頭插嗎，如下：
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個(gè)數(shù)字
}
ListPrint(pList);//打印
for (int i = -2; i <= 0; i++)
{
ListPushFront(pList, i); //頭插3個(gè)數(shù)字
}
ListPrint(pList);//打印
}效果如下：
3.2、刪除pos處節(jié)點(diǎn)數(shù)據(jù)
思路：
刪除pos處數(shù)據(jù)其實(shí)也很簡(jiǎn)單，有點(diǎn)類似于把pos處直接忽略的思想，或者說(shuō)是繞過(guò)去。首先，需要找到pos的上一個(gè)節(jié)點(diǎn)prev和下一個(gè)節(jié)點(diǎn)next，將prev和next互相鏈接即可，直接跳過(guò)了pos，這樣就實(shí)現(xiàn)了刪除pos處節(jié)點(diǎn)的數(shù)據(jù)，記得把pos處給free釋放掉。這里我們以pos為2示例：
List.h 文件：
//刪除pos處數(shù)據(jù) void ListErase(LTNode* pos);
List.c 文件：
//刪除pos處數(shù)據(jù)
void ListErase(LTNode* pos)
{
assert(pos);
//定義兩個(gè)指針保存pos兩邊的節(jié)點(diǎn)
LTNode* prev = pos->prev;
LTNode* next = pos->next;
//將prev和next鏈接起來(lái)
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個(gè)數(shù)據(jù)
}
ListPrint(pList);//打印尾插的7個(gè)
//尋找數(shù)字
LTNode* pos = ListFind(pList, 3);
if (pos)
{
ListErase(pos); //刪除pos處數(shù)據(jù)
pos = NULL; //形參的改變不會(huì)影響實(shí)參，最好在這置空pos
}
ListPrint(pList);//打印
}效果如下：
尾刪
思路：
雙向循環(huán)鏈表的特點(diǎn)將再次得以體現(xiàn)，根據(jù)其特性，我們知道phead的prev指向尾節(jié)點(diǎn)，用tail指針保存，再定義一個(gè)指針tailPrev指向tail的prev，現(xiàn)僅需將tailPrev的next指向哨兵位節(jié)點(diǎn)phead，再把哨兵位phead的prev重新置成tailPrev即可，但是別忘記把刪掉的尾節(jié)點(diǎn)給釋放掉，得free(tail)。記得要斷言鏈表不能為空，因?yàn)椴荒軇h除哨兵位節(jié)點(diǎn)。
List.H 文件：
//尾刪 void ListPopBack(LTNode* phead);
List.c 文件：1.0
//尾刪
void ListPopBack(LTNode* phead)
{
assert(phead);//本身就有哨兵位，不能為空，要斷言
assert(phead->next != phead); //防止鏈表為空，導(dǎo)致刪除哨兵位節(jié)點(diǎn)
LTNode* tail = phead->prev;
LTNode* tailPrev = tail->prev;
//釋放尾節(jié)點(diǎn)
free(tail);
tail = NULL;
//將鏈表循環(huán)起來(lái)
tailPrev->next = phead;
phead->prev = tailPrev;
}Test.c 文件：
void TestList2()
{
LTNode* pList = ListInit();
for (int i = 1; i <= 7; i++)
{
ListPushBack(pList, i); //尾插7個(gè)數(shù)據(jù)
}
ListPrint(pList);//打印尾插的7個(gè)
//尾刪兩次
ListPopBack(pList);
ListPopBack(pList);
ListPrint(pList);//再次打印
}效果如下：
注意：
前文我們已經(jīng)學(xué)了刪除pos處節(jié)點(diǎn)的數(shù)據(jù)，那么當(dāng)pos為phead->prev時(shí)，刪除的是不是就是尾節(jié)點(diǎn)，所以，尾刪理所應(yīng)當(dāng)可以這樣寫(xiě)：
List.c 文件：2.0
//尾刪
void ListPopBack(LTNode* phead)
{
assert(phead);//本身就有哨兵位，不能為空，要斷言
assert(phead->next != phead); //防止鏈表為空，導(dǎo)致刪除哨兵位節(jié)點(diǎn)
ListErase(phead->prev);
}頭刪
思路：
有了上文之鑒，我們可以直接利用前面寫(xiě)的刪除pos處數(shù)據(jù)的函數(shù)來(lái)完成，當(dāng)pos為phead->prev時(shí)，pos的位置就是尾，此時(shí)刪除的就是尾。當(dāng)然還得注意一點(diǎn)，需要額外assert斷言防止刪除的數(shù)據(jù)為哨兵位的節(jié)點(diǎn)。
List.h 文件：
//頭刪 void ListPopFront(LTNode* phead);
List.c 文件：
//頭刪
void ListPopFront(LTNode* phead)
{
assert(phead);
assert(phead->next != phead); //防止刪除哨兵位節(jié)點(diǎn)
ListErase(phead->next);
}Test.c 文件：
void TestList6()
{
LTNode* pList = ListInit();
for (int i = 1; i <= 7; i++)
{
ListPushBack(pList, i); //尾插7個(gè)數(shù)字
}
ListPrint(pList);//打印
//頭插3個(gè)數(shù)字
ListPushFront(pList, 0);
ListPushFront(pList, -1);
ListPushFront(pList, -2);
ListPrint(pList);//打印
//尾刪3個(gè)數(shù)字
ListPopBack(pList);
ListPopBack(pList);
ListPopBack(pList);
ListPrint(pList);//打印
//頭刪3個(gè)數(shù)字
ListPopFront(pList);
ListPopFront(pList);
ListPopFront(pList);
ListPrint(pList);//打印
}效果如下：
3.3、查找數(shù)據(jù)
思路：
查找數(shù)據(jù)其實(shí)也比較簡(jiǎn)單，首先，定義一個(gè)指針cur指向哨兵位phead的next，依次遍歷cur看cur->data是否為查找的數(shù)據(jù)x，如果是，則返回cur，否則繼續(xù)（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; //找不到就返回空
}四、總代碼
List.h 文件
#pragma once
#include<stdio.h>
#include<assert.h>
#include<stdlib.h>
//創(chuàng)建雙向鏈表結(jié)構(gòu)
typedef int LTDataType; //方便后續(xù)更改數(shù)據(jù)類型，本文以int整型為主
typedef struct ListNode
{
LTDataType data; //存儲(chǔ)數(shù)據(jù)
struct ListNode* next; //指向下一個(gè)
struct ListNode* prev; //指向上一個(gè)
}LTNode; //方便后續(xù)使用，不需要重復(fù)些struct
//初始化鏈表（二級(jí)指針版本）
/*void ListInit(LTNode** pphead);*/
//初始化鏈表（一級(jí)指針版本）
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前插入數(shù)據(jù)
void ListInsert(LTNode* pos, LTDataType x);
//刪除pos處數(shù)據(jù)
void ListErase(LTNode* pos);List.c 文件
#define _CRT_SECURE_NO_WARNINGS 1
#include"List.h"
//創(chuàng)建新節(jié)點(diǎn)
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; //返回新創(chuàng)建的節(jié)點(diǎn)
}
//初始化鏈表（二級(jí)指針版）
/*void ListInit(LTNode** pphead)
{
//傳二級(jí)指針，那么當(dāng)然要斷言
assert(pphead);
*pphead = BuyLTNode(0);//因?yàn)槭菐诒坏念^節(jié)點(diǎn)，所以一開(kāi)始就要給一個(gè)節(jié)點(diǎn)
//為了循環(huán)，要讓哨兵位的next和prev均指向自己
(*pphead)->next = *pphead; //注意優(yōu)先級(jí)，*pphead要加括號(hào)
(*pphead)->prev = *pphead;
}*/
//初始化鏈表（一級(jí)指針版）
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;
//銷毀從第一個(gè)節(jié)點(diǎn)到尾部的數(shù)據(jù)
while (cur != phead)
{
LTNode* next = cur->next;
//ListErase(cur);
free(cur);
cur = next;
}
//置空哨兵位節(jié)點(diǎn)phead
free(phead);
phead = NULL;
}
//尾插
void ListPushBack(LTNode* phead, LTDataType x)
{
assert(phead); //斷言，防止頭節(jié)點(diǎn)為空
/*
法一：
LTNode* tail = phead->prev; //找到尾節(jié)點(diǎn)，便于后續(xù)插入數(shù)據(jù)
LTNode* newnode = BuyLTNode(x);//創(chuàng)建新節(jié)點(diǎn)
//將此新插入的尾節(jié)點(diǎn)與上一個(gè)節(jié)點(diǎn)鏈接起來(lái)
tail->next = newnode;
newnode->prev = tail;
//將尾節(jié)點(diǎn)與哨兵位phead鏈接起來(lái)構(gòu)成循環(huán)
newnode->next = phead;
phead->prev = newnode;
*/
//法二：
ListInsert(phead, x);
}
//尾刪
void ListPopBack(LTNode* phead)
{
assert(phead);//本身就有哨兵位，不能為空，要斷言
assert(phead->next != phead); //防止鏈表為空，導(dǎo)致刪除哨兵位節(jié)點(diǎn)
/*
法一：
LTNode* tail = phead->prev;
LTNode* tailPrev = tail->prev;
//釋放尾節(jié)點(diǎn)
free(tail);
tail = NULL;
//將鏈表循環(huán)起來(lái)
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); //防止刪除哨兵位節(jié)點(diǎn)
ListErase(phead->next);
}
//在pos前插入數(shù)據(jù)
void ListInsert(LTNode* pos, LTDataType x)
{
assert(pos);
//創(chuàng)建插入數(shù)據(jù)的新節(jié)點(diǎn)
LTNode* newnode = BuyLTNode(x);
//鏈接左側(cè)
pos->prev->next = newnode;
newnode->prev = pos->prev;
//鏈接右側(cè)
newnode->next = pos;
pos->prev = newnode;
}
//刪除pos處數(shù)據(jù)
void ListErase(LTNode* pos)
{
assert(pos);
//定義兩個(gè)指針保存pos兩邊的節(jié)點(diǎn)
LTNode* prev = pos->prev;
LTNode* next = pos->next;
//將prev和next鏈接起來(lái)
prev->next = next;
next->prev = prev;
//free釋放
free(pos);
pos = NULL;
}Test.c 文件
#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個(gè)數(shù)據(jù)
}
ListPrint(pList);//打印尾插的7個(gè)
}
void TestList2()
{
LTNode* pList = ListInit();
for (int i = 1; i <= 7; i++)
{
ListPushBack(pList, i); //尾插7個(gè)數(shù)據(jù)
}
ListPrint(pList);//打印尾插的7個(gè)
//尾刪兩次
ListPopBack(pList);
ListPopBack(pList);
ListPrint(pList);//再次打印
}
void TestList3()
{
LTNode* pList = ListInit();
for (int i = 1; i <= 7; i++)
{
ListPushBack(pList, i); //尾插7個(gè)數(shù)據(jù)
}
ListPrint(pList);//打印尾插的7個(gè)
//尋找數(shù)字
LTNode* pos = ListFind(pList, 3);
if (pos)
{
ListInsert(pos, 30); //找到數(shù)字3就插入
}
ListPrint(pList);//打印
}
void TestList4()
{
LTNode* pList = ListInit();
for (int i = 1; i <= 7; i++)
{
ListPushBack(pList, i); //尾插7個(gè)數(shù)字
}
ListPrint(pList);//打印
for (int i = -2; i <= 0; i++)
{
ListPushFront(pList, i); //頭插3個(gè)數(shù)字
}
ListPrint(pList);//打印
}
void TestList5()
{
LTNode* pList = ListInit();
for (int i = 1; i <= 7; i++)
{
ListPushBack(pList, i); //尾插7個(gè)數(shù)據(jù)
}
ListPrint(pList);//打印尾插的7個(gè)
//尋找數(shù)字
LTNode* pos = ListFind(pList, 3);
if (pos)
{
ListErase(pos); //刪除pos處數(shù)據(jù)
pos = NULL; //形參的改變不會(huì)影響實(shí)參，最好在這置空pos
}
ListPrint(pList);//打印
}
void TestList6()
{
LTNode* pList = ListInit();
for (int i = 1; i <= 7; i++)
{
ListPushBack(pList, i); //尾插7個(gè)數(shù)字
}
ListPrint(pList);//打印
//頭插3個(gè)數(shù)字
ListPushFront(pList, 0);
ListPushFront(pList, -1);
ListPushFront(pList, -2);
ListPrint(pList);//打印
//尾刪3個(gè)數(shù)字
ListPopBack(pList);
ListPopBack(pList);
ListPopBack(pList);
ListPrint(pList);//打印
//頭刪3個(gè)數(shù)字
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個(gè)數(shù)字
}
ListPrint(pList);//打印
//銷毀鏈表
ListDestory(pList);
pList = NULL;
}
int main()
{
//TestList1();
//TestList2();
//TestList3();
//TestList4();
//TestList5();
//TestList6();
TestList7();
return 0;
}五、拓展
對(duì)比順序表和鏈表
| 不同點(diǎn) | 順序表 | 鏈表 |
| 存儲(chǔ)空間上 | 物理上一定連續(xù) | 邏輯上連續(xù)，但物理上不一定連續(xù) |
| 隨機(jī)訪問(wèn) | 支持O(1) | 不支持O(N) |
| 任意位置插入或者刪除元素 | 可能需要搬移元素，效率低O(N) | 只需修改指針指向 |
| 插入 | 動(dòng)態(tài)順序表，空間不夠時(shí)需要擴(kuò)容 | 沒(méi)有容量的概念 |
| 應(yīng)用場(chǎng)景 | 元素高效存儲(chǔ)+頻繁訪問(wèn) | 任意位置插入和刪除數(shù)據(jù) |
| 緩存利用率 | 高 | 低 |
優(yōu)缺點(diǎn)對(duì)比：
| 順序表 | 鏈表 | |
| 優(yōu)點(diǎn) | 1、物理空間是連續(xù)的，方便用下標(biāo)隨機(jī)訪問(wèn)。 2、CPU高速緩存命中率會(huì)更高。（補(bǔ)充） | 1、按需申請(qǐng)釋放空間。 2、任意位置可以O(shè)(1)插入刪除數(shù)據(jù)。 |
| 缺點(diǎn) | 1、正因?yàn)槲锢砜臻g連續(xù)，空間不夠需要擴(kuò)容，擴(kuò)容本身又一定消耗，其次擴(kuò)容機(jī)制還存在一定的空間浪費(fèi)。 2、頭部或者中部插入刪除，挪動(dòng)數(shù)據(jù)，效率低，O(N)。 | 1、不支持下標(biāo)的隨機(jī)訪問(wèn)。 2、有些算法不適合在它上面進(jìn)行，如：二分查找、排序等。 |
到此這篇關(guān)于C語(yǔ)言超詳細(xì)講解數(shù)據(jù)結(jié)構(gòu)中雙向帶頭循環(huán)鏈表的文章就介紹到這了,更多相關(guān)C語(yǔ)言 雙向帶頭循環(huán)鏈表內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！
- C語(yǔ)言中帶頭雙向循環(huán)鏈表基本操作的實(shí)現(xiàn)詳解
- C語(yǔ)言帶頭雙向循環(huán)鏈表的示例代碼
- 詳解C語(yǔ)言如何實(shí)現(xiàn)雙向帶頭循環(huán)鏈表
- C語(yǔ)言詳解如何實(shí)現(xiàn)帶頭雙向循環(huán)鏈表
- C語(yǔ)言手把手帶你掌握帶頭雙向循環(huán)鏈表
- C語(yǔ)言實(shí)現(xiàn)帶頭雙向循環(huán)鏈表
- C語(yǔ)言編程數(shù)據(jù)結(jié)構(gòu)帶頭雙向循環(huán)鏈表全面詳解
- C語(yǔ)言實(shí)現(xiàn)帶頭雙向循環(huán)鏈表的接口
- C語(yǔ)言超詳細(xì)講解雙向帶頭循環(huán)鏈表
相關(guān)文章
本文主要介紹C語(yǔ)言 共用體,這里整理了相關(guān)資料及示例代碼，幫助大家學(xué)習(xí)理解此部分的知識(shí)，有興趣的小伙伴可以參考下2016-08-08
C語(yǔ)言開(kāi)發(fā)實(shí)現(xiàn)通訊錄管理系統(tǒng)
這篇文章主要為大家詳細(xì)介紹了C語(yǔ)言開(kāi)發(fā)實(shí)現(xiàn)通訊錄管理系統(tǒng)，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下2022-08-08
C語(yǔ)言數(shù)組棧實(shí)現(xiàn)模板
這篇文章主要為大家詳細(xì)介紹了C語(yǔ)言數(shù)組棧實(shí)現(xiàn)模板，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下2018-12-12
C++ Primer Plus 第四章之C++ Primer Plus復(fù)合類型學(xué)習(xí)筆記
數(shù)組（array）是一種數(shù)據(jù)格式，能夠存儲(chǔ)多個(gè)同類型的值。每個(gè)值都存儲(chǔ)在一個(gè)獨(dú)立的數(shù)組元素中，計(jì)算機(jī)在內(nèi)存中依次存儲(chǔ)數(shù)組的各個(gè)元素，今天給大家重點(diǎn)介紹C++ Primer Plus復(fù)合類型的實(shí)例詳解，感興趣的朋友一起看看吧2021-07-07
OpenCV提取圖像中圓線上的數(shù)據(jù)具體流程
在對(duì)圖像進(jìn)行處理時(shí)，經(jīng)常會(huì)要提取出圖像中某條直線、圓線或者ROI區(qū)域內(nèi)的感興趣數(shù)據(jù)，進(jìn)行重點(diǎn)關(guān)注。本文主要介紹了利用OpenCV獲取圖像中圓線上的數(shù)據(jù)，需要的可以參考一下2021-11-11
C++右值引用與移動(dòng)構(gòu)造函數(shù)基礎(chǔ)與應(yīng)用詳解
左值和右值都是針對(duì)表達(dá)式,左值是指表達(dá)式結(jié)束后依然存在的持久對(duì)象,右值是指表達(dá)式結(jié)束時(shí)就不再存在的臨時(shí)對(duì)象,下面這篇文章主要給大家介紹了關(guān)于C++11右值引用和移動(dòng)語(yǔ)義的相關(guān)資料,需要的朋友可以參考下2023-02-02
C++?高精度乘法運(yùn)算的實(shí)現(xiàn)
本文主要介紹了C++?高精度乘法運(yùn)算的實(shí)現(xiàn)，文中通過(guò)示例代碼介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值，需要的朋友們下面隨著小編來(lái)一起學(xué)習(xí)學(xué)習(xí)吧2023-01-01
C++中簡(jiǎn)單讀寫(xiě)文本文件的實(shí)現(xiàn)方法
本篇文章是對(duì)C++中簡(jiǎn)單讀寫(xiě)文本文件的方法進(jìn)行了詳細(xì)的分析介紹，需要的朋友參考下2013-05-05
VC中SendMessage和PostMessage的區(qū)別
這篇文章主要介紹了VC中SendMessage和PostMessage的區(qū)別,較為全面的分析了SendMessage和PostMessage運(yùn)行原理及用法上的不同之處,非常具有實(shí)用價(jià)值,需要的朋友可以參考下2014-10-10
VS Code遠(yuǎn)程連接Linux服務(wù)器調(diào)試C程序的操作方法
這篇文章主要介紹了VS Code遠(yuǎn)程連接Linux服務(wù)器調(diào)試C程序的操作方法,打開(kāi)遠(yuǎn)程 Linux 服務(wù)器上的文件夾本文以 /root/ 為例,給大家介紹的非常詳細(xì),對(duì)大家的學(xué)習(xí)或工作具有一定的參考借鑒價(jià)值,需要的朋友參考下吧2023-12-12