C語言帶頭雙向循環(huán)鏈表的示例代碼
更新時間：2022年11月08日 08:40:12 作者：南猿北者
這篇文章主要介紹了如何利用C語言實現(xiàn)帶頭雙向循環(huán)鏈表，文中通過示例代碼介紹的非常詳細，具有一定的參考價值，感興趣的小伙伴們可以參考一下
前言
對于鏈表來說，不只有單鏈表這一個品種；
鏈表有很多種形態(tài)
按方向分：單向、雙向
按帶不帶頭：帶頭、不帶頭
按循環(huán)：循環(huán)、不循環(huán)
1、單向或則雙向：
2、帶頭或者不帶頭：
3、循環(huán)或者不循環(huán)：
組合排列一下的話，鏈表一共有8種形態(tài)?。?！
今天我們就來學習一下結(jié)構(gòu)最復雜的帶頭雙向循環(huán)鏈表?。。?；
雖然名字聽上去比較復雜，但是實現(xiàn)起來比單鏈表（全名：不帶頭、不循環(huán)、單向鏈表）更加簡單，也不需要過多考慮特殊情況；
兩種鏈表的比較：（上面是單鏈表，下面是帶頭雙向循環(huán)鏈表）
結(jié)構(gòu)分析
首先鏈表的頭節(jié)點是不存儲有效數(shù)據(jù)的（該節(jié)點被稱為哨兵位），其次我們只需要知道改頭節(jié)點的指針就能找到整個鏈表，并且便于對整個鏈表進行維護；
當然既然是雙向的嘛，那節(jié)點一定有個指針域指向前一個節(jié)點，另一個指針域指向后一個節(jié)點；
那么我們的單個節(jié)點的數(shù)據(jù)結(jié)構(gòu)就是：
現(xiàn)在我們定義了一個plist指針用來維護整個鏈表，根據(jù)上面說的plist就應該用來存儲哨兵位的頭節(jié)點的指針，那么如何表示鏈表為NULL的情況？
鏈表為空：
就是:
head->next=head;
head->prev=head;
鏈表的基本操作實現(xiàn)
創(chuàng)建節(jié)點
ListNode* ListCreate(LTDataType x)
{
ListNode* NewNode = (ListNode*)malloc(sizeof(ListNode));
if (!NewNode)
exit(-1);
NewNode->val = x;
NewNode->prev = NULL;
NewNode->next = NULL;
return NewNode;
}
我們在創(chuàng)建節(jié)點的時候就一起將數(shù)據(jù)域初始化，方標后續(xù)操作；
初始化鏈表
void InitDummyHead(ListNode* pHead)
{
assert(pHead);
pHead->prev = pHead;
pHead->next = pHead;
}
鏈表銷毀
// 雙向鏈表銷毀
void ListDestory(ListNode* pHead)
{
assert(pHead);
ListNode* cur = pHead->next;
ListNode* next = NULL;
while (cur!=pHead)
{
next = cur->next;
free(cur);
cur = next;
}
free(cur);
}
實現(xiàn)思路：
打印鏈表
除了哨兵位的節(jié)點存到是無效數(shù)據(jù)不打印外，其他節(jié)點的數(shù)據(jù)都要打?。?/p>
// 雙向鏈表打印
void ListPrint(ListNode* pHead)
{
assert(pHead);
ListNode* cur = pHead->next;
while (cur != pHead)
{
ListNode* next = cur->next;
printf("%d->",cur->val);
cur = next;
}
printf("NULL\n");
}
鏈表尾插
該鏈表的尾插，比單鏈表的尾插簡單太多了，不用遍歷找尾：
// 雙向鏈表尾插
void ListPushBack(ListNode* pHead, LTDataType x)
{
assert(pHead);
ListNode* NewNode = ListCreate(x);
ListNode* tail = pHead->prev;
tail->next = NewNode;
NewNode->prev = tail;
pHead->prev = NewNode;
NewNode->next = pHead;
}
鏈表尾刪
由于是循環(huán)的，哨兵位的前一個節(jié)點就是尾節(jié)點，同時尾節(jié)點的前一個節(jié)點我們也不用遍歷，可以很輕松的拿到：
// 雙向鏈表尾刪
void ListPopBack(ListNode* pHead)
{
assert(pHead);
assert(!is_Empty(pHead));//判空
ListNode* tail = pHead->prev;
ListNode* prev = tail->prev;
ListNode* next = pHead;
free(tail);
prev->next = next;
next->prev = prev;
}
鏈表頭插
// 雙向鏈表頭插
void ListPushFront(ListNode* pHead, LTDataType x)
{
assert(pHead);
ListNode* prev = pHead;
ListNode* cur = pHead->next;
ListNode* NewNode = ListCreate(x);
prev->next = NewNode;
NewNode->prev = prev;
NewNode->next = cur;
cur->prev = NewNode;
}
鏈表頭刪
// 雙向鏈表頭刪
void ListPopFront(ListNode* pHead)
{
assert(pHead);
assert(!is_Empty(pHead));//判空
ListNode* prev = pHead;
ListNode* cur = pHead->next;
ListNode* next = cur->next;
free(cur);
prev->next = next;
next->prev = prev;
}
鏈表查找
// 雙向鏈表查找
ListNode* ListFind(ListNode* pHead, LTDataType x)
{
assert(pHead);
assert(!is_Empty(pHead));//表都為NULL了，就沒辦法找了
ListNode* cur = pHead->next;
while (cur != pHead)
{
if (cur->val == x)
return cur;
else
cur = cur->next;
}
return NULL;
}
鏈表pos位置前面去插入
// 雙向鏈表在pos的前面進行插入
void ListInsert(ListNode* pos, LTDataType x)
{
assert(pos);//pos不能為NULL,由于參數(shù)限制我們無法對pos判斷是否為哨兵位頭節(jié)點，因此我們假設pos傳的都是合法指針和NULL
ListNode* NewNode = ListCreate(x);
ListNode* prev = pos->prev;
NewNode->next = pos;
pos->prev = NewNode;
prev->next = NewNode;
NewNode->prev = prev;
}
刪除pos位置
// 雙向鏈表刪除pos位置的節(jié)點
void ListErase(ListNode* pos)
{
assert(pos);//由于參數(shù)限制，我們無法判斷表是否為NULL；
ListNode* prev = pos->prev;
ListNode* next = pos->next;
free(pos);
prev->next = next;
next->prev = prev;
}
鏈表判空
//判斷鏈表是否為NULL
bool is_Empty(ListNode* pHead)
{
assert(pHead);
return pHead == pHead->prev;
}
代碼復用
我們上面既然實現(xiàn)了在pos位置之前插入和刪除pos位置的數(shù)據(jù)；
那么：
ListInsert(plist,x);//相當于尾插 ListInsert(plist->next, x);//相當于頭插 ListErase(plist->next);//相當于頭刪 ListErase(plist->prev);//相當于尾刪;
那么實際上我們只要實現(xiàn)ListInsert、ListErase這兩個接口就能快速實現(xiàn)出帶頭雙向循環(huán)鏈表了；
總代碼及頭文件
頭文件的包含：
#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<stdbool.h>
// 帶頭+雙向+循環(huán)鏈表增刪查改實現(xiàn)
typedef int LTDataType;
typedef struct ListNode
{
LTDataType val;
struct ListNode* next;
struct ListNode* prev;
}ListNode;
// 創(chuàng)建返回鏈表的頭結(jié)點.
ListNode* ListCreate(LTDataType x);
//初始化哨兵位的頭節(jié)點;
void InitDummyHead(ListNode* pHead);
// 雙向鏈表銷毀
void ListDestory(ListNode* pHead);
// 雙向鏈表打印
void ListPrint(ListNode* pHead);
// 雙向鏈表尾插
void ListPushBack(ListNode* pHead, LTDataType x);
// 雙向鏈表尾刪
void ListPopBack(ListNode* pHead);
// 雙向鏈表頭插
void ListPushFront(ListNode* pHead, LTDataType x);
// 雙向鏈表頭刪
void ListPopFront(ListNode* pHead);
// 雙向鏈表查找
ListNode* ListFind(ListNode* pHead, LTDataType x);
// 雙向鏈表在pos的前面進行插入
void ListInsert(ListNode* pos, LTDataType x);
// 雙向鏈表刪除pos位置的節(jié)點
void ListErase(ListNode* pos);
//判斷鏈表是否為NULL
bool is_Empty(ListNode* pHead);
功能代碼實現(xiàn)：
#include"DList.h"
ListNode* ListCreate(LTDataType x)
{
ListNode* NewNode = (ListNode*)malloc(sizeof(ListNode));
if (!NewNode)
exit(-1);
NewNode->val = x;
NewNode->prev = NULL;
NewNode->next = NULL;
return NewNode;
}
void InitDummyHead(ListNode* pHead)
{
assert(pHead);
pHead->prev = pHead;
pHead->next = pHead;
}
// 雙向鏈表銷毀
void ListDestory(ListNode* pHead)
{
assert(pHead);
ListNode* cur = pHead->next;
ListNode* next = NULL;
while (cur!=pHead)
{
next = cur->next;
free(cur);
cur = next;
}
free(cur);
}
// 雙向鏈表打印
void ListPrint(ListNode* pHead)
{
assert(pHead);
ListNode* cur = pHead->next;
while (cur != pHead)
{
ListNode* next = cur->next;
printf("%d->",cur->val);
cur = next;
}
printf("NULL\n");
}
// 雙向鏈表尾插
void ListPushBack(ListNode* pHead, LTDataType x)
{
assert(pHead);
/*ListNode* NewNode = ListCreate(x);
ListNode* tail = pHead->prev;
tail->next = NewNode;
NewNode->prev = tail;
pHead->prev = NewNode;
NewNode->next = pHead;*/
ListInsert(pHead,x);//函數(shù)復用
}
// 雙向鏈表尾刪
void ListPopBack(ListNode* pHead)
{
assert(pHead);
assert(!is_Empty(pHead));//判空
/*ListNode* tail = pHead->prev;
ListNode* prev = tail->prev;
ListNode* next = pHead;
free(tail);
prev->next = next;
next->prev = prev;*/
ListErase(pHead->prev);//函數(shù)復用
}
// 雙向鏈表頭插
void ListPushFront(ListNode* pHead, LTDataType x)
{
assert(pHead);
/*ListNode* prev = pHead;
ListNode* cur = pHead->next;
ListNode* NewNode = ListCreate(x);
prev->next = NewNode;
NewNode->prev = prev;
NewNode->next = cur;
cur->prev = NewNode;*/
ListInsert(pHead->next,x);//函數(shù)復用
}
// 雙向鏈表頭刪
void ListPopFront(ListNode* pHead)
{
assert(pHead);
assert(!is_Empty(pHead));//判空
/*ListNode* prev = pHead;
ListNode* cur = pHead->next;
ListNode* next = cur->next;
free(cur);
prev->next = next;
next->prev = prev;*/
ListErase(pHead->next);//函數(shù)復用
}
// 雙向鏈表查找
ListNode* ListFind(ListNode* pHead, LTDataType x)
{
assert(pHead);
assert(!is_Empty(pHead));//表都為NULL了，就沒辦法找了
ListNode* cur = pHead->next;
while (cur != pHead)
{
if (cur->val == x)
return cur;
else
cur = cur->next;
}
return NULL;
}
// 雙向鏈表在pos的前面進行插入
void ListInsert(ListNode* pos, LTDataType x)
{
assert(pos);//pos不能為NULL,由于參數(shù)限制我們無法對pos判斷是否為哨兵位頭節(jié)點，因此我們假設pos傳的都是合法指針和NULL
ListNode* NewNode = ListCreate(x);
ListNode* prev = pos->prev;
NewNode->next = pos;
pos->prev = NewNode;
prev->next = NewNode;
NewNode->prev = prev;
}
// 雙向鏈表刪除pos位置的節(jié)點
void ListErase(ListNode* pos)
{
assert(pos);//由于參數(shù)限制，我們無法判斷表是否為NULL；
ListNode* prev = pos->prev;
ListNode* next = pos->next;
free(pos);
prev->next = next;
next->prev = prev;
}
//判斷鏈表是否為NULL
bool is_Empty(ListNode* pHead)
{
assert(pHead);
return pHead == pHead->prev;
}
以上就是C語言帶頭雙向循環(huán)鏈表的示例代碼的詳細內(nèi)容，更多關(guān)于C語言帶頭雙向循環(huán)鏈表的資料請關(guān)注腳本之家其它相關(guān)文章！
相關(guān)文章
棧只允許在一端進行插入或刪除操作的線性表。首先棧是一種線性表，但是限定這種線性表只能在某一端進行插入和刪除操作，這篇文章主要介紹了C語言對棧的實現(xiàn)基本操作2021-07-07
這篇文章主要介紹了C++之list容器介紹及使用方式，具有很好的參考價值，希望對大家有所幫助。如有錯誤或未考慮完全的地方，望不吝賜教2023-02-02
這篇文章主要介紹了C/C++中的內(nèi)存管理小結(jié)，文中通過示例代碼介紹的非常詳細，對大家的學習或者工作具有一定的參考學習價值，需要的朋友們下面隨著小編來一起學習學習吧2021-09-09
這篇文章主要介紹了C語言Static?關(guān)鍵字解析，C語言中staic關(guān)鍵字很簡單，簡單到你的任何一個項目中可以不寫一個staic關(guān)鍵字也是沒有問題的。寫這篇章主要是一下自己的staic的理解和應用，當然在章開頭依舊要照本宣科簡述一下static關(guān)鍵字,需要的朋友可以參考一下2022-02-02
這篇文章主要介紹了VC實現(xiàn)屏幕截詞功能的方法詳解,對于深入的理解windows程序運行原理很有幫助,需要的朋友可以參考下2014-07-07
這篇文章主要為大家詳細介紹一下C語言中回調(diào)函數(shù)的用法教程，文中的示例代碼講解詳細，對我們學習C語言有一定幫助，需要的可以參考一下2022-12-12
c++ sqlite3如何利用事務(BEGIN;COMMIT;)批量操作
這篇文章主要介紹了c++ sqlite3如何利用事務(BEGIN;COMMIT;)批量操作,具有很好的參考價值,希望對大家有所幫助,如有錯誤或未考慮完全的地方,望不吝賜教2023-08-08
深入剖析Android中init進程實現(xiàn)的C語言源碼
這篇文章主要介紹了Android中init進程實現(xiàn)的C語言源碼,init屬性服務在安卓中屬于系統(tǒng)的底層Linux服務,需要的朋友可以參考下2015-07-07
c語言中的局部跳轉(zhuǎn)及全局跳轉(zhuǎn)功能
本文介紹了C語言中的goto語句,以及如何使用setjmp和longjmp實現(xiàn)跨函數(shù)的跳轉(zhuǎn),詳細講解了setjmp和longjmp的使用方法和注意事項,以及使用這種全局跳轉(zhuǎn)后變量狀態(tài)的不確定性,感興趣的朋友一起看看吧2024-09-09
C++的type_traits是一套純粹編譯期的邏輯，可以進行一些類型判斷、分支選擇等，主要用于模板編程。使用type_traits并不難，但是我們希望能夠更加深入了解其實現(xiàn)方式，與此同時，可以更進一步體驗C++的模板編程2022-08-08