詳解C語言中雙向循環(huán)鏈表的實現(xiàn)
更新時間：2022年06月17日 10:21:15 作者：MT_125
雙向鏈表也叫雙鏈表，是鏈表的一種，它的每個數(shù)據(jù)結點中都有兩個指針，分別指向直接后繼和直接前驅。本文將用C語言實現(xiàn)雙向循環(huán)鏈表，需要的可以參考一下
實現(xiàn)細節(jié)
1、帶一個哨兵位（哨兵節(jié)點，初始節(jié)點，不存儲有效數(shù)據(jù)，用來方便后期數(shù)據(jù)的存儲與查找）
2、與單向鏈表不同的是，雙向鏈表中每個數(shù)據(jù)節(jié)點包含兩個指針，分別指向前后兩個節(jié)點
3、雙向鏈表是循環(huán)的，其尾節(jié)點后不是空指針，而是與頭部的哨兵節(jié)點通過指針相連
輔助理解圖
具體實現(xiàn)代碼
1、對鏈表進行初始化
初始化：哨兵位的前后指針均指向哨兵節(jié)點本身
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é)點中的前后指針要進行相應的更換
void Any_insert(ListNode* pos,Listtype date)
{
ListNode* Prev = pos->prev;
//建立新節(jié)點
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、任意位置的刪除
細節(jié)點：當鏈表中沒有數(shù)據(jù)時，就不用刪除，因此需要建立一個函數(shù)進行判斷
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、頭插和尾刪
此處的插入和刪除，十分方便，即：對上面的任插和任刪進行套用
頭插如下：
void Head_insert(ListNode* pphead, Listtype date)
{
ListNode* NewNode = (ListNode*)malloc(sizeof(ListNode));
if (NewNode == NULL)
{
perror("Head_insert");
exit(-1);
}
//單獨實現(xiàn)
//NewNode->date = date;
//NewNode->prev = pphead;
//NewNode->next = pphead->next;
//pphead->next->prev = NewNode;
//pphead->next = NewNode;
//進行任插的復用
Any_insert(pphead->next ,date);
}
尾刪如下：
void Tail_delet(ListNode* pphead)
{
assert(pphead);
//單獨實現(xiàn)
//assert(Determine(pphead));
/*ListNode* tail = pphead->prev;
if (tail != pphead)
{
ListNode* tailprev = tail->prev;
tailprev->next = pphead;
pphead->prev = tailprev;
free(tail);
}*/
//尾刪的復用
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;
//任插的復用
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;
//進行任插的復用
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);
}*/
//尾刪的復用
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)鏈表的實現(xiàn)的詳細內(nèi)容，更多關于C語言雙向循環(huán)鏈表的資料請關注腳本之家其它相關文章！
相關文章
這篇文章主要介紹了VC++編程獲取窗口句柄的方法,簡單總結分析了VC++獲取窗口句柄的常見函數(shù)與使用技巧,需要的朋友可以參考下2017-07-07
C語言的動態(tài)內(nèi)存分配及動態(tài)內(nèi)存分配函數(shù)詳解
這篇文章主要為大家詳細介紹了C語言的動態(tài)內(nèi)存分配及動態(tài)內(nèi)存分配函數(shù)，文中示例代碼介紹的非常詳細，具有一定的參考價值，感興趣的小伙伴們可以參考一下，希望能夠給你帶來幫助2022-03-03
這篇文章主要介紹了C++ std::bind用法詳解,本篇文章通過簡要的案例,講解了該項技術的了解與使用,以下就是詳細內(nèi)容,需要的朋友可以參考下2021-09-09
這篇文章主要為大家詳細介紹了C++中常用的四種類型轉換方式：static_cast＜Type＞、dynamic_cast＜Type＞、const_case＜Type＞和reinterpret_cast，感興趣的可以了解一下2022-08-08
這篇文章主要為大家詳細介紹了如何利用Qt實現(xiàn)顯示與桌面上并可以隨意拖拽至桌面任意位置的電子時鐘案例，感興趣的小伙伴可以嘗試一下2022-06-06
詳解C++編程中的靜態(tài)成員與可變數(shù)據(jù)成員
這篇文章主要介紹了詳解C++編程中的靜態(tài)成員與可變數(shù)據(jù)成員,是C++入門學習中的基礎知識,需要的朋友可以參考下2016-01-01
這篇文章主要為大家介紹了C++中的const和constexpr ，具有一定的參考價值，感興趣的小伙伴們可以參考一下，希望能夠給你帶來幫助2021-12-12
chrono是c++ 11中的時間庫，本文就來詳細的介紹一下chrono庫的具體使用，關鍵是理解里面時間段(Durations)、時間點(Time points)的概念，感興趣的可以了解一下2021-11-11
這篇文章主要介紹了c語言如何實現(xiàn)兩數(shù)之和，具有很好的參考價值，希望對大家有所幫助。如有錯誤或未考慮完全的地方，望不吝賜教2022-07-07
一篇文章徹底弄懂C++虛函數(shù)的實現(xiàn)機制
C++中的虛函數(shù)的作用主要是實現(xiàn)了多態(tài)的機制,基類定義虛函數(shù),子類可以重寫該函數(shù),在派生類中對基類定義的虛函數(shù)進行重寫時,需要在派生類中聲明該方法為虛方法,這篇文章主要給大家介紹了關于如何通過一篇文章徹底弄懂C++虛函數(shù)的實現(xiàn)機制,需要的朋友可以參考下2021-06-06