詳解C語言中雙向循環(huán)鏈表的實(shí)現(xiàn)
更新時(shí)間：2022年06月17日 10:21:15 作者：MT_125
雙向鏈表也叫雙鏈表，是鏈表的一種，它的每個(gè)數(shù)據(jù)結(jié)點(diǎn)中都有兩個(gè)指針，分別指向直接后繼和直接前驅(qū)。本文將用C語言實(shí)現(xiàn)雙向循環(huán)鏈表，需要的可以參考一下
實(shí)現(xiàn)細(xì)節(jié)
1、帶一個(gè)哨兵位（哨兵節(jié)點(diǎn)，初始節(jié)點(diǎn)，不存儲有效數(shù)據(jù)，用來方便后期數(shù)據(jù)的存儲與查找）
2、與單向鏈表不同的是，雙向鏈表中每個(gè)數(shù)據(jù)節(jié)點(diǎn)包含兩個(gè)指針，分別指向前后兩個(gè)節(jié)點(diǎn)
3、雙向鏈表是循環(huán)的，其尾節(jié)點(diǎn)后不是空指針，而是與頭部的哨兵節(jié)點(diǎn)通過指針相連
輔助理解圖
具體實(shí)現(xiàn)代碼
1、對鏈表進(jìn)行初始化
初始化：哨兵位的前后指針均指向哨兵節(jié)點(diǎn)本身
void ListInit(ListNode** pphead)
{
*pphead = (ListNode*)malloc(sizeof(ListNode));
if (*pphead == NULL)
{
perror("ListInit");
exit(-1);
}
(*pphead)->date = -1;
(*pphead)->next = *pphead;
(*pphead)->prev = *pphead;
}
2、任意位置前的插入
注意：插入位置前后節(jié)點(diǎn)中的前后指針要進(jìn)行相應(yīng)的更換
void Any_insert(ListNode* pos,Listtype date)
{
ListNode* Prev = pos->prev;
//建立新節(jié)點(diǎn)
ListNode* NewNode = (ListNode*)malloc(sizeof(ListNode));
if (NewNode == NULL)
{
perror("Any_insert");
exit(-1);
}
NewNode->date = date;
NewNode->next = pos;
pos->prev = NewNode;
Prev->next = NewNode;
NewNode->prev = Prev;
}
3、任意位置的刪除
細(xì)節(jié)點(diǎn)：當(dāng)鏈表中沒有數(shù)據(jù)時(shí)，就不用刪除，因此需要建立一個(gè)函數(shù)進(jìn)行判斷
bool Determine(ListNode* pphead)
{//判斷鏈表中有無元素
assert(pphead);
return pphead == pphead->next;
}
void Any_delet(ListNode* pos)
{
assert(!Determine(pos));
ListNode* Next = pos->next;
ListNode* Prev = pos->prev;
Next->prev = Prev;
Prev->next = Next;
free(pos);
}
4、頭插和尾刪
此處的插入和刪除，十分方便，即：對上面的任插和任刪進(jìn)行套用
頭插如下：
void Head_insert(ListNode* pphead, Listtype date)
{
ListNode* NewNode = (ListNode*)malloc(sizeof(ListNode));
if (NewNode == NULL)
{
perror("Head_insert");
exit(-1);
}
//單獨(dú)實(shí)現(xiàn)
//NewNode->date = date;
//NewNode->prev = pphead;
//NewNode->next = pphead->next;
//pphead->next->prev = NewNode;
//pphead->next = NewNode;
//進(jìn)行任插的復(fù)用
Any_insert(pphead->next ,date);
}
尾刪如下：
void Tail_delet(ListNode* pphead)
{
assert(pphead);
//單獨(dú)實(shí)現(xiàn)
//assert(Determine(pphead));
/*ListNode* tail = pphead->prev;
if (tail != pphead)
{
ListNode* tailprev = tail->prev;
tailprev->next = pphead;
pphead->prev = tailprev;
free(tail);
}*/
//尾刪的復(fù)用
Any_delet(pphead->prev);
}
完整代碼
頭文件
#pragma once
#include<stdio.h>
#include<malloc.h>
#include<stdlib.h>
#include<assert.h>
#include<stdbool.h>
typedef int Listtype;
typedef struct ListNode
{
struct ListNode* prev;
Listtype date;
struct ListNode* next;
}ListNode;
void ListInit(ListNode** pphead); //鏈表初始化
void ListNode_ADD(ListNode* pphead, Listtype date); //尾插
void Head_insert(ListNode* pphead, Listtype date); //頭插
void ListNode_Print(ListNode* pphead); //鏈表打印
void Tail_delet(ListNode* pphead); //尾刪
bool Determine(ListNode* pphead); //判斷表中有無數(shù)據(jù)
void Any_insert(ListNode* pos, Listtype date); //任插
void Any_delet(ListNode* pos); //任刪
void List_Destory(ListNode* pos); //鏈表清空
具體函數(shù)
#define _CRT_SECURE_NO_WARNINGS 1
#include "List.h"
//鏈表打印
void ListNode_Print(ListNode* pphead)
{
assert(pphead);
ListNode* phead = pphead;
pphead = pphead->next;
for (; pphead != phead; pphead = pphead->next)
{
printf("%d ", pphead->date);
}
printf("\n");
}
bool Determine(ListNode* pphead)
{//判斷鏈表中有無元素
assert(pphead);
return pphead == pphead->next;
}
//鏈表初始化
void ListInit(ListNode** pphead)
{
*pphead = (ListNode*)malloc(sizeof(ListNode));
if (*pphead == NULL)
{
perror("ListInit");
exit(-1);
}
(*pphead)->date = -1;
(*pphead)->next = *pphead;
(*pphead)->prev = *pphead;
}
//尾插
void ListNode_ADD(ListNode* pphead,Listtype date)
{
//ListNode* NewNode = (ListNode*)malloc(sizeof(ListNode));
//if (NewNode == NULL)
//{
// perror("ADD_malloc");
// exit(-1);
//}
//NewNode->date = date;
//NewNode->prev = pphead->prev;
//pphead->prev->next = NewNode;
//pphead->prev = NewNode;
//NewNode->next = pphead;
//任插的復(fù)用
Any_insert(pphead, date);
}
void Head_insert(ListNode* pphead, Listtype date)
{
ListNode* NewNode = (ListNode*)malloc(sizeof(ListNode));
if (NewNode == NULL)
{
perror("Head_insert");
exit(-1);
}
//NewNode->date = date;
//NewNode->prev = pphead;
//NewNode->next = pphead->next;
//pphead->next->prev = NewNode;
//pphead->next = NewNode;
//進(jìn)行任插的復(fù)用
Any_insert(pphead->next ,date);
}
void Tail_delet(ListNode* pphead)
{
assert(pphead);
//assert(Determine(pphead));
/*ListNode* tail = pphead->prev;
if (tail != pphead)
{
ListNode* tailprev = tail->prev;
tailprev->next = pphead;
pphead->prev = tailprev;
free(tail);
}*/
//尾刪的復(fù)用
Any_delet(pphead->prev);
}
//在任意位置前插入
void Any_insert(ListNode* pos,Listtype date)
{
ListNode* Prev = pos->prev;
ListNode* NewNode = (ListNode*)malloc(sizeof(ListNode));
if (NewNode == NULL)
{
perror("Any_insert");
exit(-1);
}
NewNode->date = date;
NewNode->next = pos;
pos->prev = NewNode;
Prev->next = NewNode;
NewNode->prev = Prev;
}
//任意位置刪除
void Any_delet(ListNode* pos)
{
assert(!Determine(pos));
ListNode* Next = pos->next;
ListNode* Prev = pos->prev;
Next->prev = Prev;
Prev->next = Next;
free(pos);
}
//鏈表清空
void List_Destory(ListNode* pos)
{
ListNode* head = pos,*Prev = pos->prev;
for (pos = pos->prev; head != pos;pos = Prev)
{
Prev = pos->prev;
Any_delet(pos);
}
printf("\n清空完成\n");
}測試
#define _CRT_SECURE_NO_WARNINGS 1
#include "List.h"
void ListTest(ListNode** pphead)
{
ListInit(pphead);
Head_insert(*pphead, 60);
Head_insert(*pphead, 100);
Head_insert(*pphead, 60);
Head_insert(*pphead, 50);
ListNode_Print(*pphead);
Tail_delet(*pphead);
Tail_delet(*pphead);
Tail_delet(*pphead);
ListNode_Print(*pphead);
}
int main()
{
ListNode* pphead = NULL;
ListTest(&pphead);
return 0 ;
}以上就是詳解C語言中雙向循環(huán)鏈表的實(shí)現(xiàn)的詳細(xì)內(nèi)容，更多關(guān)于C語言雙向循環(huán)鏈表的資料請關(guān)注腳本之家其它相關(guān)文章！
相關(guān)文章
fatal error LNK1104: 無法打開文件“l(fā)ibc.lib”的解決方法
本篇文章是對fatal error LNK1104: 無法打開文件“l(fā)ibc.lib”的解決方法進(jìn)行了詳細(xì)的分析介紹，需要的朋友參考下2013-05-05
這篇文章主要介紹了C++編寫頭文件，在一個(gè)C++程序中，只包含兩類文件——.cpp文件和.h文件。其中，.cpp文件被稱作C++源文件，里面放的都是C++的源代碼；而.h文件則被稱作C++頭文件，里面放的也是C++的源代碼，感興趣的小伙伴一起來看下面文章的詳細(xì)介紹吧2021-12-12
這篇文章主要介紹了如何用C++制作LeetCode刷題小技巧-錯題記錄本的方法,需要的朋友可以參考下2021-04-04
下面小編就為大家?guī)硪黄獪\談C++的淺拷貝出現(xiàn)的錯誤。小編覺得挺不錯的，現(xiàn)在就分享給大家，也給大家做個(gè)參考。一起跟隨小編過來看看吧2017-01-01
這篇文章主要該大家分享C語言算法佩奇存錢的練習(xí)，文章主要通過描述佩奇存錢的問題然后確定程序框架將結(jié)果運(yùn)算出來，下面來看詳細(xì)內(nèi)容吧,需要的朋友可以參考一下2022-04-04
這篇文章主要為大家詳細(xì)介紹了C語言編寫掃雷小程序，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下2022-09-09
c++連接mysql數(shù)據(jù)庫的兩種方法(ADO連接和mysql api連接)
現(xiàn)在正做一個(gè)接口，通過不同的連接字符串操作不同的數(shù)據(jù)庫。要用到mysql數(shù)據(jù)庫，C++連接mysql有2種方法：利用ADO連接、利用mysql自己的api函數(shù)進(jìn)行連接，下面看看如何用吧2013-12-12
這篇文章主要為大家詳細(xì)介紹了C語言實(shí)現(xiàn)鏈隊(duì)列基本操作，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下2021-09-09
INI（Initialization?File）文件是一種簡單直觀的數(shù)據(jù)存儲格式,常用于配置應(yīng)用程序的初始化設(shè)置,使用?iniparser?庫的應(yīng)用程序可以很方便地讀取和解析INI文件中的配置信息,大大簡化了對配置文件的處理工作,降低了程序的開發(fā)復(fù)雜度,感興趣的的朋友跟隨小編一起看看吧2024-04-04
這篇文章主要給大家介紹了關(guān)于C++ string的內(nèi)部究竟是什么樣的，文中通過示例代碼的非常詳細(xì)，對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值，需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧2021-01-01