詳解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)，不存儲(chǔ)有效數(shù)據(jù)，用來方便后期數(shù)據(jù)的存儲(chǔ)與查找）
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、對(duì)鏈表進(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、頭插和尾刪
此處的插入和刪除，十分方便，即：對(duì)上面的任插和任刪進(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)文章
這篇文章主要介紹了VC++編程獲取窗口句柄的方法,簡單總結(jié)分析了VC++獲取窗口句柄的常見函數(shù)與使用技巧,需要的朋友可以參考下2017-07-07
C語言的動(dòng)態(tài)內(nèi)存分配及動(dòng)態(tài)內(nèi)存分配函數(shù)詳解
這篇文章主要為大家詳細(xì)介紹了C語言的動(dòng)態(tài)內(nèi)存分配及動(dòng)態(tài)內(nèi)存分配函數(shù)，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下，希望能夠給你帶來幫助2022-03-03
這篇文章主要介紹了C++ std::bind用法詳解,本篇文章通過簡要的案例,講解了該項(xiàng)技術(shù)的了解與使用,以下就是詳細(xì)內(nèi)容,需要的朋友可以參考下2021-09-09
這篇文章主要為大家詳細(xì)介紹了C++中常用的四種類型轉(zhuǎn)換方式：static_cast＜Type＞、dynamic_cast＜Type＞、const_case＜Type＞和reinterpret_cast，感興趣的可以了解一下2022-08-08
這篇文章主要為大家詳細(xì)介紹了如何利用Qt實(shí)現(xiàn)顯示與桌面上并可以隨意拖拽至桌面任意位置的電子時(shí)鐘案例，感興趣的小伙伴可以嘗試一下2022-06-06
詳解C++編程中的靜態(tài)成員與可變數(shù)據(jù)成員
這篇文章主要介紹了詳解C++編程中的靜態(tài)成員與可變數(shù)據(jù)成員,是C++入門學(xué)習(xí)中的基礎(chǔ)知識(shí),需要的朋友可以參考下2016-01-01
這篇文章主要為大家介紹了C++中的const和constexpr ，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下，希望能夠給你帶來幫助2021-12-12
c++11 chrono全面解析(最高可達(dá)納秒級(jí)別的精度)
chrono是c++ 11中的時(shí)間庫，本文就來詳細(xì)的介紹一下chrono庫的具體使用，關(guān)鍵是理解里面時(shí)間段(Durations)、時(shí)間點(diǎn)(Time points)的概念，感興趣的可以了解一下2021-11-11
這篇文章主要介紹了c語言如何實(shí)現(xiàn)兩數(shù)之和，具有很好的參考價(jià)值，希望對(duì)大家有所幫助。如有錯(cuò)誤或未考慮完全的地方，望不吝賜教2022-07-07
一篇文章徹底弄懂C++虛函數(shù)的實(shí)現(xiàn)機(jī)制
C++中的虛函數(shù)的作用主要是實(shí)現(xiàn)了多態(tài)的機(jī)制,基類定義虛函數(shù),子類可以重寫該函數(shù),在派生類中對(duì)基類定義的虛函數(shù)進(jìn)行重寫時(shí),需要在派生類中聲明該方法為虛方法,這篇文章主要給大家介紹了關(guān)于如何通過一篇文章徹底弄懂C++虛函數(shù)的實(shí)現(xiàn)機(jī)制,需要的朋友可以參考下2021-06-06