詳解C語言如何實現雙向帶頭循環(huán)鏈表
更新時間：2022年08月12日 11:18:02 作者：蔣靈瑜的流水賬
雙向帶頭循環(huán)鏈表應該是鏈表中非常方便的一種，可以很容易的在任意位置上進行插入和刪除，可以很容易的對鏈表進行管理。本文將利用C語言實現雙向帶頭循環(huán)鏈表，需要的可以參考一下
一、雙向循環(huán)鏈表與順序表的區(qū)別
| 不同點 | 順序表 | 雙向帶頭循環(huán)鏈表 |
| 在內存中的存儲方式 | 連續(xù)存儲 | 不一定連續(xù) |
| 隨機訪問 | 支持隨機訪問 | 不支持隨訪問 |
| 任意元素插入或刪除 | 尾插O(1)，其他O(N)，可能需要挪動元素 | 通過修改指針指向即可 |
| 應用場景 | 元素高效存儲、頻繁訪問 | 任意位置插入刪除頻繁 |
| 三級緩存命中率 | 高 | 低 |
寄存器的速度遠快于主存，所以需要三級緩存先將數據取出，寄存器讀取時將相鄰地址的數據進行讀取，所以順序表內存地址連續(xù)的特點使其三級緩存命中率高。
雙向帶頭循環(huán)鏈表雖然在鏈表中結構最復雜，但是解決了單鏈表找前一個節(jié)點需要遍歷、要判斷頭結點是否為空的缺點。
二、List.h
#pragma once
#include <stdio.h>
#include <assert.h>
#include <stdbool.h>
#include <stdlib.h>
typedef int ListDateType;
typedef struct ListNode
{
struct ListNode* next;
struct ListNode* prev;
ListDateType date;
}ListNode;
ListNode* ListInit();//初始化
void ListDestroy(ListNode* phead);//銷毀
void PrintList(ListNode* phead);//打印
bool ListEmpty(ListNode* phead);//判斷鏈表是否為空（只有頭節(jié)點）
void ListPushBack(ListNode* phead, ListDateType x);//尾插
void ListPopback(ListNode* phead);//尾刪
void ListPushFront(ListNode* phead, ListDateType x);//頭插
void ListPopFront(ListNode* phead);//頭刪
size_t ListSize(ListNode* phead);//有效節(jié)點個數
ListNode* ListFind(ListNode* phead, ListDateType x);//查找（可用于修改）
void ListInsert(ListNode* pos, ListDateType x);//pos位置插入
void ListErase(ListNode* pos);//刪除pos位置結構體內包含指向下一個節(jié)點的指針next、指向上一個節(jié)點的指針prev和本節(jié)點存儲的數據date
三、List.c
1、帶頭雙向循環(huán)鏈表的初始化
ListNode* ListInit()//初始化，返回帶哨兵位的頭結點
{
ListNode* guard = (ListNode*)malloc(sizeof(ListNode));
if (guard == NULL)
{
perror("ListInit fail:\n");
exit(-1);
}
guard->next = guard;
guard->prev = guard;
return guard;
}
malloc一個哨兵位的頭結點，并將其next和prev指針置空。
2、帶頭雙向循環(huán)鏈表的銷毀
void ListDestroy(ListNode* phead)//銷毀，傳一級指針調用方需要在外部將頭結點指針置空
{
assert(phead);
ListNode* cur = phead->next;
while (cur != phead)//釋放非頭結點
{
ListNode* next = cur->next;
free(cur);
cur = next;
}
free(phead);//再釋放頭結點
}
為了保持接口的一致性，形參用一級指針，所以需要調用者在外部對頭指針置空。
先釋放非頭結點，再釋放頭結點。
3、帶頭雙向循環(huán)鏈表的打印
void PrintList(ListNode* phead)//打印
{
assert(phead);
ListNode* cur = phead->next;
while (cur != phead)
{
printf("%d<=>", cur->date);
cur = cur->next;
}
printf("\n");
}
從頭結點的next開始，遍歷打印
4、動態(tài)開辟一個節(jié)點
ListNode* BuyNode(ListDateType x)//動態(tài)開辟一個節(jié)點
{
ListNode* newnode = (ListNode*)malloc(sizeof(ListNode));
if (newnode == NULL)
{
perror("BuyNode:\n");
exit(-1);
}
newnode->date = x;
newnode->prev = NULL;
newnode->next = NULL;
return newnode;
}
將值放入這個節(jié)點，并將兩個指針置空
5、帶頭雙向循環(huán)鏈表的判空
bool ListEmpty(ListNode* phead)//判斷鏈表是否只有頭節(jié)點
{
assert(phead);
return phead->next == phead;
}
只有哨兵位這一個頭結點即為空
6、帶頭雙向循環(huán)鏈表的尾插、尾刪
void ListPushBack(ListNode* phead, ListDateType x)//尾插
{
assert(phead);
ListNode* tail = phead->prev;
ListNode* newnode = BuyNode(x);
newnode->next = phead;
newnode->prev = tail;
tail->next = newnode;
phead->prev = newnode;
}
void ListPopback(ListNode* phead)//尾刪
{
assert(phead);
assert(!ListEmpty(phead));
ListNode* tail = phead->prev;
ListNode* prev = tail->prev;
free(tail);
prev->next = phead;
phead->prev = prev;
}注意尾刪前需要判空
7、帶頭雙向循環(huán)鏈表的頭插、頭刪
void ListPushFront(ListNode* phead, ListDateType x)//頭插
{
assert(phead);
ListNode* cur = phead->next;
ListNode* newnode = BuyNode(x);
newnode->next = cur;
newnode->prev = phead;
cur->prev = newnode;
phead->next = newnode;
}
void ListPopFront(ListNode* phead)//頭刪
{
assert(phead);
assert(!ListEmpty(phead));
ListNode* cur = phead->next;
ListNode* next = cur->next;
free(cur);
phead->next = next;
next->prev = phead;
}注意頭刪前需要判空
8、帶頭雙向循環(huán)鏈表的長度
size_t ListSize(ListNode* phead)//有效節(jié)點個數
{
assert(phead);
ListNode* cur = phead->next;
size_t count = 0;
while (cur != phead)
{
cur = cur->next;
++count;
}
return count;
}
循環(huán)計數即可，哨兵位不算
9、帶頭雙向循環(huán)鏈表的查找、任意位置插入、刪除
ListNode* ListFind(ListNode* phead, ListDateType x)//查找（可用于修改）
{
assert(phead);
ListNode* cur = phead->next;
while (cur!=phead)
{
if (cur->date == x)
return cur;
cur = cur->next;
}
return NULL;
}
void ListInsert(ListNode* pos, ListDateType x)//pos位置之前插入
{
assert(pos);
ListNode* newnode = BuyNode(x);
ListNode* prev = pos->prev;
prev->next = newnode;
newnode->prev = prev;
newnode->next = pos;
pos->prev = newnode;
}
void ListErase(ListNode* pos)//刪除pos位置
{
assert(pos);
ListNode* prev = pos->prev;
ListNode* next = pos->next;
free(pos);
prev->next = next;
next->prev = prev;
}查找：遍歷鏈表，返回第一個date==x的節(jié)點指針，查找通常配合下面兩個接口使用
任意位置插入、刪除：使用pos位置進行插入刪除操作。
頭插、頭刪、尾插、尾刪接口可以復用上面三個接口
到此這篇關于詳解C語言如何實現雙向帶頭循環(huán)鏈表的文章就介紹到這了,更多相關C語言雙向帶頭循環(huán)鏈表內容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關文章希望大家以后多多支持腳本之家！
相關文章
蛇形矩陣（Snake matrix）是矩陣的一種，常被應用在編程題目與數學數列中，需要提取每條斜線里最小的數字，本篇文章將會通過遞歸和非遞歸來分別實現蛇形矩陣2022-02-02
本篇文章主要介紹了C語言WinSock學習筆記，小編覺得挺不錯的，現在分享給大家，也給大家做個參考。一起跟隨小編過來看看吧2007-12-12
作為一名編程初學者,通常學習中,發(fā)生內存錯誤是件非常麻煩的事情,下面這篇文章主要給大家介紹了關于c++動態(tài)內存管理new/delete的相關資料,文中通過實例代碼介紹的非常詳細,需要的朋友可以參考下2022-03-03
這篇文章主要為大家詳細介紹了C++通過COM接口操作PPT的相關資料，具有一定的參考價值，感興趣的小伙伴們可以參考一下2017-05-05
這篇文章主要為大家詳細介紹了C語言實現簡易計算器功能，文中示例代碼介紹的非常詳細，具有一定的參考價值，感興趣的小伙伴們可以參考一下2022-01-01
AT&T 匯編是一種和intel匯編在語法上完全不同的匯編語言，為避免混淆intel語法，本文只介紹AT&T匯編，AT&T的第一個特點就是每個寄存器名前必須加‘%’,立即數前必須加‘$’2019-02-02
本文主要介紹了C++?AVL樹的兩單旋和兩雙旋的項目實踐,根據節(jié)點插入位置的不同,AVL樹的旋轉分為四種,下面就來介紹一下,感興趣的可以了解一下2024-03-03
本篇文章是對C中數值與真假進行了詳細的分析介紹，需要的朋友參考下2013-05-05
本文主要介紹了C++11、C++14、C++17、C++20常用新特性，文中通過示例代碼介紹的非常詳細，對大家的學習或者工作具有一定的參考學習價值，需要的朋友們下面隨著小編來一起學習學習吧2023-03-03
本文主要介紹了VS2022連接sqlserver數據庫教程，文中通過示例代碼介紹的非常詳細，對大家的學習或者工作具有一定的參考學習價值，需要的朋友們下面隨著小編來一起學習學習吧2022-07-07