C語言超詳細(xì)講解數(shù)據(jù)結(jié)構(gòu)中雙向帶頭循環(huán)鏈表
一、概念
前文我們已經(jīng)學(xué)習(xí)了單向鏈表，并通過oj題目深入了解了帶頭節(jié)點(diǎn)的鏈表以及帶環(huán)鏈表，來畫張圖總體回顧下：
在我們學(xué)習(xí)的鏈表中，其實(shí)總共有8種，都是單雙向和帶不帶頭以及帶不帶環(huán)的任意組合
今兒要學(xué)習(xí)的是雙向 - 帶頭 - 循環(huán)鏈表，聽名字就覺著結(jié)構(gòu)很復(fù)雜，要比曾經(jīng)學(xué)的單向 - 不帶頭 - 不循環(huán) 鏈表的結(jié)構(gòu)復(fù)雜的多 ，確實(shí)也是。先來畫張圖整體感受下：
解釋：
- 雙向：就要確保每個數(shù)據(jù)存兩個指針next和prev。next指向下一個節(jié)點(diǎn)，prev指向上一個節(jié)點(diǎn)
- 帶頭：帶一個哨兵位的頭節(jié)點(diǎn)在數(shù)據(jù)的最前頭。
- 循環(huán)：尾節(jié)點(diǎn)的next指向哨兵位頭節(jié)點(diǎn)，而哨兵位的上一個節(jié)點(diǎn)prev指向尾節(jié)點(diǎn)，構(gòu)成循環(huán)。
正文開始：
二、必備工作
2.1、創(chuàng)建雙向鏈表結(jié)構(gòu)
因?yàn)槭请p向鏈表，所以在結(jié)構(gòu)體里頭必然有兩個指針，一個next指向下一個節(jié)點(diǎn)，一個prev指向上一個節(jié)點(diǎn)。
List.h 文件：
//創(chuàng)建雙向鏈表結(jié)構(gòu)
typedef int LTDataType; //方便后續(xù)更改數(shù)據(jù)類型，本文以int整型為主
typedef struct ListNode
{
LTDataType data; //存儲數(shù)據(jù)
struct ListNode* next; //指向下一個
struct ListNode* prev; //指向上一個
}LTNode; //方便后續(xù)使用，不需要重復(fù)些struct2.2、初始化鏈表
思路：
在初始化的時候要傳地址，因?yàn)樾螀⒌母淖儾粫绊憣?shí)參，pphead的改變不會影響pList，要傳pList的地址，用**pphead來接收，此時就要assert斷言了，因?yàn)槎壷羔樀刂凡豢赡芪豢?。因?yàn)槭请p向循環(huán)鏈表，所以要將創(chuàng)建好的哨兵位節(jié)點(diǎn)的next和prev均指向自己。
List.h 文件：（1）
//初始化鏈表（二級指針版） void ListInit(LTNode* pphead);
List.c 文件：（1）
//初始化鏈表（二級指針版）
void ListInit(LTNode** pphead)
{
//傳二級指針，那么當(dāng)然要斷言
assert(pphead);
*pphead = BuyLTNode(0);//因?yàn)槭菐诒坏念^節(jié)點(diǎn)，所以一開始就要給一個節(jié)點(diǎn)
//為了循環(huán)，要讓哨兵位的next和prev均指向自己
(*pphead)->next = *pphead; //注意優(yōu)先級，*pphead要加括號
(*pphead)->prev = *pphead;
}注意：
上一種方法我們傳的是二級指針，那么可以傳一級指針嗎，其實(shí)也是可以的，只需寫個函數(shù)返回指針即可
List.h 文件：（2）
//初始化鏈表（一級指針版本） LTNode* ListInit();
List.c 文件：（2）
//初始化鏈表（一級指針版）
LTNode* ListInit()
{
LTNode* phead = BuyLTNode(0);
phead->next = phead;
phead->prev = phead;
return phead;
}2.3、動態(tài)申請節(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)，哨兵位不用來存放有效數(shù)據(jù)，那么就不需要打印，定義一個cur指針來迭代，那么應(yīng)該從phead的next開始打印，當(dāng)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");
}2.5、銷毀鏈表
思路：
既然是銷毀鏈表了，那么自然是要把鏈表的所有元素包括哨兵位都給銷毀掉，但畢竟剛開始傳phead的時候是不能為空的，所以要斷言，在把所有有效數(shù)據(jù)銷毀后最后再銷毀哨兵位即可。
法一：遍歷
定義一個指針cur，從phead的next第一個有效數(shù)據(jù)開始free，保存下一個，再free，依次遍歷下去
法二：附用ListErase函數(shù)
此法也可以，不過每次Erase完，都會把前后兩個節(jié)點(diǎn)再鏈接起來，雖說最后都會銷毀，但duck不必多此一舉，所有直接采用法一比較好
List.h 文件：
//銷毀鏈表 void ListDestory(LTNode* phead);
List.c 文件：
//銷毀鏈表
void ListDestory(LTNode* phead)
{
assert(phead);
LTNode* cur = phead->next;
//銷毀從第一個節(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個數(shù)字
}
ListPrint(pList);//打印
//銷毀鏈表
ListDestory(pList);
pList = NULL;
}三、主要功能
3.1、在pos節(jié)點(diǎn)前插入數(shù)據(jù)
思路：
假設(shè)我們已經(jīng)進(jìn)行了尾插4個數(shù)字，現(xiàn)在想在數(shù)字3的前面插入30，那么首先就要查找有無數(shù)字3，若有，則插入。注意：這里需要用到后文才講到的查找函數(shù)，這里直接引用了，詳解看后文即可，問題不大！
首先，將30放到新創(chuàng)建的節(jié)點(diǎn)newnode里頭，為了實(shí)現(xiàn)雙向，要先把3的前一個數(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個數(shù)據(jù)
}
ListPrint(pList);//打印尾插的7個
//尋找數(shù)字
LTNode* pos = ListFind(pList, 3);
if (pos)
{
ListInsert(pos, 30); //找到數(shù)字3就插入
}
ListPrint(pList);//打印
}效果如下：
尾插
思路：
首先，因?yàn)榇随湵硎菐诒坏念^節(jié)點(diǎn)，所以頭節(jié)點(diǎn)必然不為空，剛開始就要assert斷言。其次，單鏈表尾插需要找尾，雙向鏈表雖然也需要，不過非常簡單，不需要再遍歷鏈表了，因?yàn)樯诒活^節(jié)點(diǎn)的phead的上一個節(jié)點(diǎn)指向的就是尾，這就充分體現(xiàn)了雙向循環(huán)的好處，找到了尾節(jié)點(diǎn)就需要再創(chuàng)建一個節(jié)點(diǎn)存儲插入數(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)與上一個節(jié)點(diǎn)鏈接起來
tail->next = newnode;
newnode->prev = tail;
//將尾節(jié)點(diǎn)與哨兵位phead鏈接起來構(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個數(shù)據(jù)
}
ListPrint(pList);//打印尾插的7個
}效果如下：
注意：
在上文中，我們學(xué)習(xí)了在pos前插入數(shù)據(jù)，那么設(shè)想一下，當(dāng)pos就等于phead的時候，它（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)就尤為簡單了，當(dāng)pos為原第一個數(shù)據(jù)phead->next時，此時就是在其之前插入數(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個數(shù)字
}
ListPrint(pList);//打印
for (int i = -2; i <= 0; i++)
{
ListPushFront(pList, i); //頭插3個數(shù)字
}
ListPrint(pList);//打印
}效果如下：
3.2、刪除pos處節(jié)點(diǎn)數(shù)據(jù)
思路：
刪除pos處數(shù)據(jù)其實(shí)也很簡單，有點(diǎn)類似于把pos處直接忽略的思想，或者說是繞過去。首先，需要找到pos的上一個節(jié)點(diǎn)prev和下一個節(jié)點(diǎn)next，將prev和next互相鏈接即可，直接跳過了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);
//定義兩個指針保存pos兩邊的節(jié)點(diǎn)
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個數(shù)據(jù)
}
ListPrint(pList);//打印尾插的7個
//尋找數(shù)字
LTNode* pos = ListFind(pList, 3);
if (pos)
{
ListErase(pos); //刪除pos處數(shù)據(jù)
pos = NULL; //形參的改變不會影響實(shí)參，最好在這置空pos
}
ListPrint(pList);//打印
}效果如下：
尾刪
思路：
雙向循環(huán)鏈表的特點(diǎn)將再次得以體現(xiàn)，根據(jù)其特性，我們知道phead的prev指向尾節(jié)點(diǎn)，用tail指針保存，再定義一個指針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)起來
tailPrev->next = phead;
phead->prev = tailPrev;
}Test.c 文件：
void TestList2()
{
LTNode* pList = ListInit();
for (int i = 1; i <= 7; i++)
{
ListPushBack(pList, i); //尾插7個數(shù)據(jù)
}
ListPrint(pList);//打印尾插的7個
//尾刪兩次
ListPopBack(pList);
ListPopBack(pList);
ListPrint(pList);//再次打印
}效果如下：
注意：
前文我們已經(jīng)學(xué)了刪除pos處節(jié)點(diǎn)的數(shù)據(jù)，那么當(dāng)pos為phead->prev時，刪除的是不是就是尾節(jié)點(diǎn)，所以，尾刪理所應(yīng)當(dāng)可以這樣寫：
List.c 文件：2.0
//尾刪
void ListPopBack(LTNode* phead)
{
assert(phead);//本身就有哨兵位，不能為空，要斷言
assert(phead->next != phead); //防止鏈表為空，導(dǎo)致刪除哨兵位節(jié)點(diǎn)
ListErase(phead->prev);
}頭刪
思路：
有了上文之鑒，我們可以直接利用前面寫的刪除pos處數(shù)據(jù)的函數(shù)來完成，當(dāng)pos為phead->prev時，pos的位置就是尾，此時刪除的就是尾。當(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個數(shù)字
}
ListPrint(pList);//打印
//頭插3個數(shù)字
ListPushFront(pList, 0);
ListPushFront(pList, -1);
ListPushFront(pList, -2);
ListPrint(pList);//打印
//尾刪3個數(shù)字
ListPopBack(pList);
ListPopBack(pList);
ListPopBack(pList);
ListPrint(pList);//打印
//頭刪3個數(shù)字
ListPopFront(pList);
ListPopFront(pList);
ListPopFront(pList);
ListPrint(pList);//打印
}效果如下：
3.3、查找數(shù)據(jù)
思路：
查找數(shù)據(jù)其實(shí)也比較簡單，首先，定義一個指針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; //存儲數(shù)據(jù)
struct ListNode* next; //指向下一個
struct ListNode* prev; //指向上一個
}LTNode; //方便后續(xù)使用，不需要重復(fù)些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前插入數(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)
}
//初始化鏈表（二級指針版）
/*void ListInit(LTNode** pphead)
{
//傳二級指針，那么當(dāng)然要斷言
assert(pphead);
*pphead = BuyLTNode(0);//因?yàn)槭菐诒坏念^節(jié)點(diǎn)，所以一開始就要給一個節(jié)點(diǎn)
//為了循環(huán)，要讓哨兵位的next和prev均指向自己
(*pphead)->next = *pphead; //注意優(yōu)先級，*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;
//銷毀從第一個節(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)與上一個節(jié)點(diǎn)鏈接起來
tail->next = newnode;
newnode->prev = tail;
//將尾節(jié)點(diǎn)與哨兵位phead鏈接起來構(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)起來
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);
//定義兩個指針保存pos兩邊的節(jié)點(diǎn)
LTNode* prev = pos->prev;
LTNode* next = pos->next;
//將prev和next鏈接起來
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個數(shù)據(jù)
}
ListPrint(pList);//打印尾插的7個
}
void TestList2()
{
LTNode* pList = ListInit();
for (int i = 1; i <= 7; i++)
{
ListPushBack(pList, i); //尾插7個數(shù)據(jù)
}
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個數(shù)據(jù)
}
ListPrint(pList);//打印尾插的7個
//尋找數(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個數(shù)字
}
ListPrint(pList);//打印
for (int i = -2; i <= 0; i++)
{
ListPushFront(pList, i); //頭插3個數(shù)字
}
ListPrint(pList);//打印
}
void TestList5()
{
LTNode* pList = ListInit();
for (int i = 1; i <= 7; i++)
{
ListPushBack(pList, i); //尾插7個數(shù)據(jù)
}
ListPrint(pList);//打印尾插的7個
//尋找數(shù)字
LTNode* pos = ListFind(pList, 3);
if (pos)
{
ListErase(pos); //刪除pos處數(shù)據(jù)
pos = NULL; //形參的改變不會影響實(shí)參，最好在這置空pos
}
ListPrint(pList);//打印
}
void TestList6()
{
LTNode* pList = ListInit();
for (int i = 1; i <= 7; i++)
{
ListPushBack(pList, i); //尾插7個數(shù)字
}
ListPrint(pList);//打印
//頭插3個數(shù)字
ListPushFront(pList, 0);
ListPushFront(pList, -1);
ListPushFront(pList, -2);
ListPrint(pList);//打印
//尾刪3個數(shù)字
ListPopBack(pList);
ListPopBack(pList);
ListPopBack(pList);
ListPrint(pList);//打印
//頭刪3個數(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個數(shù)字
}
ListPrint(pList);//打印
//銷毀鏈表
ListDestory(pList);
pList = NULL;
}
int main()
{
//TestList1();
//TestList2();
//TestList3();
//TestList4();
//TestList5();
//TestList6();
TestList7();
return 0;
}五、拓展
對比順序表和鏈表
| 不同點(diǎn) | 順序表 | 鏈表 |
| 存儲空間上 | 物理上一定連續(xù) | 邏輯上連續(xù)，但物理上不一定連續(xù) |
| 隨機(jī)訪問 | 支持O(1) | 不支持O(N) |
| 任意位置插入或者刪除元素 | 可能需要搬移元素，效率低O(N) | 只需修改指針指向 |
| 插入 | 動態(tài)順序表，空間不夠時需要擴(kuò)容 | 沒有容量的概念 |
| 應(yīng)用場景 | 元素高效存儲+頻繁訪問 | 任意位置插入和刪除數(shù)據(jù) |
| 緩存利用率 | 高 | 低 |
優(yōu)缺點(diǎn)對比：
| 順序表 | 鏈表 | |
| 優(yōu)點(diǎn) | 1、物理空間是連續(xù)的，方便用下標(biāo)隨機(jī)訪問。 2、CPU高速緩存命中率會更高。（補(bǔ)充） | 1、按需申請釋放空間。 2、任意位置可以O(shè)(1)插入刪除數(shù)據(jù)。 |
| 缺點(diǎn) | 1、正因?yàn)槲锢砜臻g連續(xù)，空間不夠需要擴(kuò)容，擴(kuò)容本身又一定消耗，其次擴(kuò)容機(jī)制還存在一定的空間浪費(fèi)。 2、頭部或者中部插入刪除，挪動數(shù)據(jù)，效率低，O(N)。 | 1、不支持下標(biāo)的隨機(jī)訪問。 2、有些算法不適合在它上面進(jìn)行，如：二分查找、排序等。 |
到此這篇關(guān)于C語言超詳細(xì)講解數(shù)據(jù)結(jié)構(gòu)中雙向帶頭循環(huán)鏈表的文章就介紹到這了,更多相關(guān)C語言 雙向帶頭循環(huán)鏈表內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！
相關(guān)文章
這篇文章主要介紹了C語言對歸并排序算法的使用,歸并排序算法的平均事件復(fù)雜度為(n\log n),需要的朋友可以參考下2016-05-05
c語言之char*和unsigned?char*的區(qū)別及說明
這篇文章主要介紹了c語言之char*和unsigned?char*的區(qū)別及說明,具有很好的參考價值,希望對大家有所幫助,如有錯誤或未考慮完全的地方,望不吝賜教2023-08-08
探究在C++程序并發(fā)時保護(hù)共享數(shù)據(jù)的問題
這篇文章主要介紹了探究在C++程序并發(fā)時保護(hù)共享數(shù)據(jù)的問題,也有利于大家更好地理解C++多線程的一些機(jī)制,需要的朋友可以參考下2015-07-07
為了解決內(nèi)存泄漏的問題，C++中提出了智能指針。內(nèi)存泄漏的產(chǎn)生原因有很多，即使我們正確的使用malloc和free關(guān)鍵字也有可能產(chǎn)生內(nèi)存泄漏，如在malloc和free之間如果存在拋異常，那也會產(chǎn)生內(nèi)存泄漏。這種問題被稱為異常安全2022-05-05
這篇文章主要為大家介紹了C語言的順序表，具有一定的參考價值，感興趣的小伙伴們可以參考一下，希望能夠給你帶來幫助2021-11-11
本文主要介紹了C++11中的幾種鎖，文中通過示例代碼介紹的非常詳細(xì)，具有一定的參考價值，感興趣的小伙伴們可以參考一下2022-01-01
在本篇文章當(dāng)中主要給大家介紹?OpenMP?當(dāng)中線程的同步和互斥機(jī)制，在?OpenMP?當(dāng)中主要有三種不同的線程之間的互斥方式。下面就來和大家來討論一下OpenMP當(dāng)中的互斥操作，需要的可以參考一下2023-01-01
這篇文章主要介紹了C++中的模板類繼承和成員訪問問題，具有很好的參考價值，希望對大家有所幫助。如有錯誤或未考慮完全的地方，望不吝賜教2022-11-11
簡單分析C語言中指針數(shù)組與數(shù)組指針的區(qū)別
這篇文章主要介紹了C語言中指針數(shù)組與數(shù)組指針的區(qū)別,是C語言入門學(xué)習(xí)中的基礎(chǔ)知識,需要的朋友可以參考下2015-11-11
這篇文章主要該大家分享C語言算法佩奇存錢的練習(xí)，文章主要通過描述佩奇存錢的問題然后確定程序框架將結(jié)果運(yùn)算出來，下面來看詳細(xì)內(nèi)容吧,需要的朋友可以參考一下2022-04-04