C語言帶頭雙向循環(huán)鏈表的示例代碼
更新時間：2022年11月08日 08:40:12 作者：南猿北者
這篇文章主要介紹了如何利用C語言實現帶頭雙向循環(huán)鏈表，文中通過示例代碼介紹的非常詳細，具有一定的參考價值，感興趣的小伙伴們可以參考一下
前言
對于鏈表來說，不只有單鏈表這一個品種；
鏈表有很多種形態(tài)
按方向分：單向、雙向
按帶不帶頭：帶頭、不帶頭
按循環(huán)：循環(huán)、不循環(huán)
1、單向或則雙向：
2、帶頭或者不帶頭：
3、循環(huán)或者不循環(huán)：
組合排列一下的話，鏈表一共有8種形態(tài)?。?！
今天我們就來學習一下結構最復雜的帶頭雙向循環(huán)鏈表！?。。?/p>
雖然名字聽上去比較復雜，但是實現起來比單鏈表（全名：不帶頭、不循環(huán)、單向鏈表）更加簡單，也不需要過多考慮特殊情況；
兩種鏈表的比較：（上面是單鏈表，下面是帶頭雙向循環(huán)鏈表）
結構分析
首先鏈表的頭節(jié)點是不存儲有效數據的（該節(jié)點被稱為哨兵位），其次我們只需要知道改頭節(jié)點的指針就能找到整個鏈表，并且便于對整個鏈表進行維護；
當然既然是雙向的嘛，那節(jié)點一定有個指針域指向前一個節(jié)點，另一個指針域指向后一個節(jié)點；
那么我們的單個節(jié)點的數據結構就是：
現在我們定義了一個plist指針用來維護整個鏈表，根據上面說的plist就應該用來存儲哨兵位的頭節(jié)點的指針，那么如何表示鏈表為NULL的情況？
鏈表為空：
就是:
head->next=head;
head->prev=head;
鏈表的基本操作實現
創(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é)點的時候就一起將數據域初始化，方標后續(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);
}
實現思路：
打印鏈表
除了哨兵位的節(jié)點存到是無效數據不打印外，其他節(jié)點的數據都要打?。?/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,由于參數限制我們無法對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);//由于參數限制，我們無法判斷表是否為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;
}
代碼復用
我們上面既然實現了在pos位置之前插入和刪除pos位置的數據；
那么：
ListInsert(plist,x);//相當于尾插 ListInsert(plist->next, x);//相當于頭插 ListErase(plist->next);//相當于頭刪 ListErase(plist->prev);//相當于尾刪;
那么實際上我們只要實現ListInsert、ListErase這兩個接口就能快速實現出帶頭雙向循環(huán)鏈表了；
總代碼及頭文件
頭文件的包含：
#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<stdbool.h>
// 帶頭+雙向+循環(huán)鏈表增刪查改實現
typedef int LTDataType;
typedef struct ListNode
{
LTDataType val;
struct ListNode* next;
struct ListNode* prev;
}ListNode;
// 創(chuàng)建返回鏈表的頭結點.
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);
功能代碼實現：
#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);//函數復用
}
// 雙向鏈表尾刪
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);//函數復用
}
// 雙向鏈表頭插
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);//函數復用
}
// 雙向鏈表頭刪
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);//函數復用
}
// 雙向鏈表查找
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,由于參數限制我們無法對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);//由于參數限制，我們無法判斷表是否為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)鏈表的示例代碼的詳細內容，更多關于C語言帶頭雙向循環(huán)鏈表的資料請關注腳本之家其它相關文章！
相關文章
這篇文章主要介紹了C語言中的運算符優(yōu)先級,文中簡單總結了一些常用運算符的優(yōu)先級順序以及記憶技巧,需要的朋友可以參考下2016-05-05
這篇文章主要介紹了C++驗證LeetCode包圍區(qū)域的DFS方法,本篇文章通過簡要的案例,講解了該項技術的了解與使用,以下就是詳細內容,需要的朋友可以參考下2021-07-07
這篇文章主要介紹了C++中判斷成員函數是否重寫的相關資料,需要的朋友可以參考下2017-04-04
OpenCV作為機器視覺開源庫,使用起來非常不錯,這篇文章主要給大家介紹了關于C++如何調用opencv完成運動目標捕捉的相關資料,文中通過實例代碼介紹的非常詳細,需要的朋友可以參考下2022-05-05
最近我學習了C++中的迭代器失效問題，迭代器失效問題是非常非常重要的，所以特意整理出來一篇文章供我們一起復習和學習2022-08-08
這篇文章主要介紹了C++獲取類的成員函數的函數指針詳解及實例代碼的相關資料,需要的朋友可以參考下2017-02-02
緩沖區(qū)又稱為緩存,它是內存空間的一部分,也就是說在內存空間中預留了一定的存儲空間,這些存儲空間用來緩沖輸入或輸出的數據,這部分預留的空間就叫做緩沖區(qū),這篇文章主要給大家介紹了關于c語言中緩沖區(qū)問題的相關資料,需要的朋友可以參考下2021-11-11
這篇文章主要為大家詳細介紹了基于MATLAB求取空間數據的變異函數，并繪制經驗半方差圖的方法。文中的示例代碼講解詳細，感興趣的可以了解一下2023-04-04
Qt是一個跨平臺的 C++ 開發(fā)庫，主要用來開發(fā)圖形用戶界面程序，當然也可以開發(fā)不帶界面的命令行程序，本文重點給大家介紹Qt?關于容器的遍歷迭代器的使用問題小結，感興趣的朋友一起看看吧2022-03-03
這篇文章主要為大家詳細介紹了C++連接并使用MySQL數據庫，文中示例代碼介紹的非常詳細，具有一定的參考價值，感興趣的小伙伴們可以參考一下2020-07-07