C++實(shí)現(xiàn)帶頭雙向循環(huán)鏈表的示例詳解
更新時(shí)間：2022年12月06日 15:13:05 作者：蔣靈瑜的筆記本
這篇文章主要介紹了如何利用C++實(shí)現(xiàn)帶頭雙向循環(huán)鏈表，文中通過(guò)示例代碼介紹的非常詳細(xì)，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下
一、雙向循環(huán)鏈表與順序表的區(qū)別
| 不同點(diǎn) | 順序表 | 雙向帶頭循環(huán)鏈表 |
| 在內(nèi)存中的存儲(chǔ)方式 | 連續(xù)存儲(chǔ) | 不一定連續(xù) |
| 隨機(jī)訪(fǎng)問(wèn) | 支持隨機(jī)訪(fǎng)問(wèn) | 不支持隨訪(fǎng)問(wèn) |
| 任意元素插入或刪除 | 尾插O(1)，其他O(N)，可能需要挪動(dòng)元素 | 通過(guò)修改指針指向即可 |
| 應(yīng)用場(chǎng)景 | 元素高效存儲(chǔ)、頻繁訪(fǎng)問(wèn) | 任意位置插入刪除頻繁 |
| 三級(jí)緩存命中率 | 高 | 低 |
寄存器的速度遠(yuǎn)快于主存，所以需要三級(jí)緩存先將數(shù)據(jù)取出，寄存器讀取時(shí)將相鄰地址的數(shù)據(jù)進(jìn)行讀取，所以順序表內(nèi)存地址連續(xù)的特點(diǎn)使其三級(jí)緩存命中率高。
雙向帶頭循環(huán)鏈表雖然在鏈表中結(jié)構(gòu)最復(fù)雜，但是解決了單鏈表找前一個(gè)節(jié)點(diǎn)需要遍歷、要判斷頭結(jié)點(diǎn)是否為空的缺點(diǎn)。
二、List.h
#pragma once
#include <stdio.h>
#include <assert.h>
#include <stdbool.h>
#include <stdlib.h>
typedef int ListDataType;
typedef struct ListNode
{
struct ListNode* next;
struct ListNode* prev;
ListDataType data;
}ListNode;
ListNode* ListInit();//初始化
void ListDestroy(ListNode* phead);//銷(xiāo)毀
void PrintList(ListNode* phead);//打印
bool ListEmpty(ListNode* phead);//判斷鏈表是否為空（只有頭節(jié)點(diǎn)）
void ListPushBack(ListNode* phead, ListDataType x);//尾插
void ListPopback(ListNode* phead);//尾刪
void ListPushFront(ListNode* phead, ListDataType x);//頭插
size_t ListSize(ListNode* phead);//有效節(jié)點(diǎn)個(gè)數(shù)
ListNode* ListFind(ListNode* phead, ListDataType x);//查找（可用于修改）
void ListInsert(ListNode* pos, ListDataType x);//pos位置插入
void ListErase(ListNode* pos);//刪除pos位置結(jié)構(gòu)體內(nèi)包含指向下一個(gè)節(jié)點(diǎn)的指針next、指向上一個(gè)節(jié)點(diǎn)的指針prev和本節(jié)點(diǎn)存儲(chǔ)的數(shù)據(jù)data
三、List.c
1、帶頭雙向循環(huán)鏈表的初始化
ListNode* ListInit()//初始化，返回帶哨兵位的頭結(jié)點(diǎn)
{
ListNode* guard = (ListNode*)malloc(sizeof(ListNode));
if (guard == NULL)
{
perror("ListInit fail:\n");
exit(-1);
}
guard->next = guard;
guard->prev = guard;
return guard;
}
malloc一個(gè)哨兵位的頭結(jié)點(diǎn)，并將其next和prev指針置空。
2、帶頭雙向循環(huán)鏈表的銷(xiāo)毀
void ListDestroy(ListNode* phead)//銷(xiāo)毀，傳一級(jí)指針調(diào)用方需要在外部將頭結(jié)點(diǎn)指針置空
{
assert(phead);
ListNode* cur = phead->next;
while (cur != phead)//釋放非頭結(jié)點(diǎn)
{
ListNode* next = cur->next;
free(cur);
cur = next;
}
free(phead);//再釋放頭結(jié)點(diǎn)
}
為了保持接口的一致性，形參用一級(jí)指針，所以需要調(diào)用者在外部對(duì)頭指針置空。
先釋放非頭結(jié)點(diǎn)，再釋放頭結(jié)點(diǎn)。
3、帶頭雙向循環(huán)鏈表的打印
void PrintList(ListNode* phead)//打印
{
assert(phead);
ListNode* cur = phead->next;
while (cur != phead)
{
printf("%d<=>", cur->data);
cur = cur->next;
}
printf("\n");
}
從頭結(jié)點(diǎn)的next開(kāi)始，遍歷打印
4、動(dòng)態(tài)開(kāi)辟一個(gè)節(jié)點(diǎn)
ListNode* BuyNode(ListDataType x)//動(dòng)態(tài)開(kāi)辟一個(gè)節(jié)點(diǎn)
{
ListNode* newnode = (ListNode*)malloc(sizeof(ListNode));
if (newnode == NULL)
{
perror("BuyNode:\n");
exit(-1);
}
newnode->data = x;
newnode->prev = NULL;
newnode->next = NULL;
return newnode;
}
將值放入這個(gè)節(jié)點(diǎn)，并將兩個(gè)指針置空
5、帶頭雙向循環(huán)鏈表的判空
bool ListEmpty(ListNode* phead)//判斷鏈表是否只有頭節(jié)點(diǎn)
{
assert(phead);
return phead->next == phead;
}
只有哨兵位這一個(gè)頭結(jié)點(diǎn)即為空
6、帶頭雙向循環(huán)鏈表的尾插、尾刪
void ListPushBack(ListNode* phead, ListDataType x)//尾插
{
assert(phead);
ListNode* tail = phead->prev;
ListNode* newnode = BuyNode(x);
newnode->next = phead;
newnode->prev = tail;
tail->next = newnode;
phead->prev = newnode;
}
void ListPopback(ListNode* phead)//尾刪
{
assert(phead);
assert(!ListEmpty(phead));
ListNode* tail = phead->prev;
ListNode* prev = tail->prev;
free(tail);
prev->next = phead;
phead->prev = prev;
}注意尾刪前需要判空
7、帶頭雙向循環(huán)鏈表的頭插、頭刪
void ListPushFront(ListNode* phead, ListDataType x)//頭插
{
assert(phead);
ListNode* cur = phead->next;
ListNode* newnode = BuyNode(x);
newnode->next = cur;
newnode->prev = phead;
cur->prev = newnode;
phead->next = newnode;
}
void ListPopFront(ListNode* phead)//頭刪
{
assert(phead);
assert(!ListEmpty(phead));
ListNode* cur = phead->next;
ListNode* next = cur->next;
free(cur);
phead->next = next;
next->prev = phead;
}注意頭刪前需要判空
8、帶頭雙向循環(huán)鏈表的長(zhǎng)度
size_t ListSize(ListNode* phead)//有效節(jié)點(diǎn)個(gè)數(shù)
{
assert(phead);
ListNode* cur = phead->next;
size_t count = 0;
while (cur != phead)
{
cur = cur->next;
++count;
}
return count;
}
循環(huán)計(jì)數(shù)即可，哨兵位不算
9、帶頭雙向循環(huán)鏈表的查找、任意位置插入、刪除
ListNode* ListFind(ListNode* phead, ListDataType x)//查找（可用于修改）
{
assert(phead);
ListNode* cur = phead->next;
while (cur!=phead)
{
if (cur->data == x)
return cur;
cur = cur->next;
}
return NULL;
}
void ListInsert(ListNode* pos, ListDataType x)//pos位置之前插入
{
assert(pos);
ListNode* newnode = BuyNode(x);
ListNode* prev = pos->prev;
prev->next = newnode;
newnode->prev = prev;
newnode->next = pos;
pos->prev = newnode;
}
void ListErase(ListNode* pos)//刪除pos位置
{
assert(pos);
ListNode* prev = pos->prev;
ListNode* next = pos->next;
free(pos);
prev->next = next;
next->prev = prev;
}查找：遍歷鏈表，返回第一個(gè)data==x的節(jié)點(diǎn)指針，查找通常配合下面兩個(gè)接口使用
任意位置插入、刪除：使用pos位置進(jìn)行插入刪除操作。
頭插、頭刪、尾插、尾刪接口可以復(fù)用上面三個(gè)接口
到此這篇關(guān)于C++實(shí)現(xiàn)帶頭雙向循環(huán)鏈表的示例詳解的文章就介紹到這了,更多相關(guān)C++帶頭雙向循環(huán)鏈表內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！
相關(guān)文章
對(duì)于線(xiàn)性表，我們可能要執(zhí)行下列操作：訪(fǎng)問(wèn)表的第k個(gè)結(jié)點(diǎn)、在k這個(gè)結(jié)點(diǎn)之前或者之后插入一個(gè)新結(jié)點(diǎn)，抑或是刪除第k個(gè)結(jié)點(diǎn)等等操作，其中我們會(huì)遇到值對(duì)第一個(gè)或者最后一個(gè)結(jié)點(diǎn)插入、刪除、和訪(fǎng)問(wèn)值的線(xiàn)性表，我們給它們以特殊的名稱(chēng)：棧、隊(duì)列、雙端隊(duì)列2022-05-05
詳解C++中賦值,關(guān)系,函數(shù)調(diào)用運(yùn)算符重載的實(shí)現(xiàn)
本文主要為大家講解一下三個(gè)C++中的運(yùn)算符重載，分別是賦值運(yùn)算符重載、關(guān)系運(yùn)算符重載和函數(shù)調(diào)用運(yùn)算符重載，感興趣的小伙伴可以跟隨小編一起學(xué)習(xí)一下2022-06-06
這篇文章主要給大家介紹了關(guān)于c語(yǔ)言/c++溢出問(wèn)題的相關(guān)資料，文中通過(guò)圖文介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值，需要的朋友們下面隨著小編來(lái)一起學(xué)習(xí)學(xué)習(xí)吧2021-02-02
趁空閑時(shí)間，小編決定把C++的排序算法分析并總結(jié)下，以便溫故知新。也方便需要的朋友可以參考學(xué)習(xí)。2016-07-07
這篇文章主要介紹了 C++ 類(lèi)的繼承與派生實(shí)例詳解的相關(guān)資料,需要的朋友可以參考下2017-06-06
這篇文章主要介紹了C++類(lèi)型轉(zhuǎn)換歸納總結(jié),通過(guò)本文可以加深讀者對(duì)于C++變量類(lèi)型及其相互轉(zhuǎn)換方法的理解,需要的朋友可以參考下2014-07-07
本文給大家介紹的是C++多線(xiàn)程編程，由于C++本身沒(méi)有多線(xiàn)程機(jī)制，在windows下我們使用調(diào)用SDK win32 api來(lái)實(shí)現(xiàn)，示例都很簡(jiǎn)單，講解的也很詳細(xì)，推薦給大家2021-09-09
這篇文章主要介紹了關(guān)于C語(yǔ)言中#define的副作用，文中通過(guò)示例代碼介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值，需要的朋友們下面隨著小編來(lái)一起學(xué)習(xí)學(xué)習(xí)吧2019-03-03
本篇文章主要介紹C語(yǔ)言中char的知識(shí),并附有代碼實(shí)例,以便大家在學(xué)習(xí)的時(shí)候更好的理解,有需要的可以看一下2016-07-07
C語(yǔ)言編程之動(dòng)態(tài)內(nèi)存與柔性數(shù)組的了解
本文是C語(yǔ)言編程篇，這篇文章主要為大家介紹了C語(yǔ)言編程中動(dòng)態(tài)內(nèi)存的函數(shù)與柔性數(shù)組的特點(diǎn)，有需要的朋友可以借鑒參考下，希望可以有所幫助2021-09-09