C語言中帶頭雙向循環(huán)鏈表基本操作的實現詳解
更新時間：2022年11月14日 14:18:37 作者：蝸牛牛啊
無頭單向非循環(huán)鏈表結構簡單，一般不會單獨用來存數據。而帶頭雙向循環(huán)鏈表的結構較為復雜，一般用在單獨存儲數據。本文將介紹帶頭雙向循環(huán)鏈表的基本操作，需要的可以參考一下
一、概念與結構
無頭單向非循環(huán)鏈表結構簡單，一般不會單獨用來存數據。實際中更多的是作為其他數據結構的子結構，如哈希桶、圖的鄰接表等等。而帶頭雙向循環(huán)鏈表的結構較為復雜，一般用在單獨存儲數據。實際中使用的鏈表數據結構，都是帶頭雙向循環(huán)鏈表，雖然它的結構復雜但是因為結構優(yōu)勢用代碼實現起來會變得簡單。
二、基本操作的實現
1.創(chuàng)建結點
LTNode* BuyListNode(ListDataType x)
{
LTNode* newnode = (LTNode*)malloc(sizeof(LTNode));
if (newnode == NULL)
{
perror("malloc");
exit(-1);
}
newnode->val = x;
newnode->prev = NULL;
newnode->next = NULL;
return newnode;
}
2.初始化鏈表
void ListInit(LTNode** pphead)//初始化
{
*pphead = (LTNode*)malloc(sizeof(LTNode));
*pphead = BuyListNode(-1);
(*pphead)->next = *pphead;
(*pphead)->prev = *pphead;
}
//LTNode* ListInit()//初始化
//{
// LTNode* phead = BuyListNode(-1);//初始化時將頭結點置為-1;
// phead->next = phead;
// phead->prev = phead;
// return phead;
//}
初始化鏈表有兩種方式，一種是有返回類型（注釋部分），另一種是在初始化函數中給結構體開辟空間（不過注意參數要為二級指針）。因為是帶頭結點的循環(huán)鏈表，所以prev和next指針都指向自己。
3.打印鏈表
void ListPrint(LTNode* phead)//打印
{
assert(phead);
LTNode* cur = phead->next;
while (cur != phead)
{
printf("%d ", cur->val);
cur = cur->next;
}
printf("\n");
}
注意while循環(huán)的結束條件，保證能夠打印鏈表中的所有有效值。要對頭結點進行assert判斷，不能為空。
4.尾插
void ListPushBack(LTNode* phead, ListDataType x)//尾插
{
assert(phead);
LTNode* newnode = BuyListNode(x);
LTNode* tail = phead->prev;
newnode->next = tail->next;
phead->prev = newnode;
newnode->prev = tail;
tail->next = newnode;
//ListInsert(phead, x);
}
5.尾刪
void ListPopBack(LTNode* phead)//尾刪
{
assert(phead);
assert(phead->next != phead);
LTNode* prevnode = phead->prev;
prevnode->prev->next = phead;
phead->prev = prevnode->prev;
free(prevnode);
//ListErase(phead->prev);
}
尾刪時要注意判斷phead->next != phead，不能刪除頭結點，同時記得要free(prevnode)釋放刪除后的空間。
6.頭插
void ListPushFront(LTNode* phead, ListDataType x)//頭插
{
assert(phead);
LTNode* tail = phead->next;
LTNode* newnode = BuyListNode(x);
tail->prev = newnode;
newnode->next = tail;
newnode->prev = phead;
phead->next = newnode;
//ListInsert(phead->next,x);
}
7.頭刪
void ListPopFront(LTNode* phead)//頭刪
{
assert(phead);
assert(phead->next != phead);
LTNode* tail = phead->next;
phead->next = tail->next;
tail->next->prev = phead;
//ListErase(phead->next);
}
8.查找某個數并返回其指針
LTNode* ListFind(LTNode* phead, ListDataType x)//找某個數返回其指針
{
assert(phead);
LTNode* cur = phead->next;
while (cur != phead)
{
if (cur->val == x)
{
return cur;
}
cur = cur->next;
}
return NULL;
}
9.在某個位置之前插入
void ListInsert(LTNode* pos, ListDataType x)//在pos之前插入
{
assert(pos);
LTNode* newnode = BuyListNode(x);
LTNode* tail = pos->prev;
tail->next = newnode;
newnode->prev = tail;
newnode->next = pos;
pos->prev = newnode;
}
10.刪除某個位置
void ListErase(LTNode* pos)//刪除pos位置
{
assert(pos);
LTNode* prevnode = pos->prev;
LTNode* nextnode = pos->next;
free(pos);
prevnode->next = nextnode;
nextnode->prev = prevnode;
/*pos->next->prev = pos->prev;
pos->prev->next = pos->next;
free(pos);*/
}
11.判斷鏈表是否為空
bool ListEmpty(LTNode* phead)//判斷是否為空,如果是空，返回true
{
assert(phead);
return phead->next == phead;
}
12.計算鏈表中有效值的個數
size_t ListSize(LTNode* phead)//計算鏈表中有效值的個數
{
assert(phead);
size_t size = 0;
LTNode* tail = phead->next;
while (tail != phead)
{
size++;
tail = tail->next;
}
return size;
}
13.銷毀鏈表
void ListDestroy(LTNode* phead)//銷毀鏈表
{
assert(phead);
LTNode* tail = phead->next;
while (tail != phead)
{
LTNode* nextnode = tail->next;
free(tail);
tail = nextnode;
}
free(phead);
}
銷毀鏈表時要注意要保證每個結點都釋放，同時最后也要將頭結點釋放free(phead)。
三、測試代碼
#define _CRT_SECURE_NO_WARNINGS 1
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <assert.h>
typedef int ListDataType;
typedef struct ListNode {
ListDataType val;
struct ListNode* prev;
struct ListNode* next;
}LTNode;
LTNode* BuyListNode(ListDataType x)
{
LTNode* newnode = (LTNode*)malloc(sizeof(LTNode));
if (newnode == NULL)
{
perror("malloc");
exit(-1);
}
newnode->val = x;
newnode->prev = NULL;
newnode->next = NULL;
return newnode;
}
void ListInit(LTNode** pphead)//初始化
{
*pphead = (LTNode*)malloc(sizeof(LTNode));
*pphead = BuyListNode(-1);
(*pphead)->next = *pphead;
(*pphead)->prev = *pphead;
}
//LTNode* ListInit()//初始化
//{
// LTNode* phead = BuyListNode(-1);//初始化時將頭結點置為-1;
// phead->next = phead;
// phead->prev = phead;
// return phead;
//}
void ListPrint(LTNode* phead)//打印
{
assert(phead);
LTNode* cur = phead->next;
while (cur != phead)
{
printf("%d ", cur->val);
cur = cur->next;
}
printf("\n");
}
void ListPushBack(LTNode* phead, ListDataType x)//尾插
{
assert(phead);
LTNode* newnode = BuyListNode(x);
LTNode* tail = phead->prev;
newnode->next = tail->next;
phead->prev = newnode;
newnode->prev = tail;
tail->next = newnode;
//ListInsert(phead, x);
}
void ListPopBack(LTNode* phead)//尾刪
{
assert(phead);
assert(phead->next != phead);
LTNode* prevnode = phead->prev;
prevnode->prev->next = phead;
phead->prev = prevnode->prev;
free(prevnode);
//ListErase(phead->prev);
}
void ListPushFront(LTNode* phead, ListDataType x)//頭插
{
assert(phead);
LTNode* tail = phead->next;
LTNode* newnode = BuyListNode(x);
tail->prev = newnode;
newnode->next = tail;
newnode->prev = phead;
phead->next = newnode;
//ListInsert(phead->next,x);
}
void ListPopFront(LTNode* phead)//頭刪
{
assert(phead);
assert(phead->next != phead);
LTNode* tail = phead->next;
phead->next = tail->next;
tail->next->prev = phead;
//ListErase(phead->next);
}
LTNode* ListFind(LTNode* phead, ListDataType x)//找某個數返回其指針
{
assert(phead);
LTNode* cur = phead->next;
while (cur != phead)
{
if (cur->val == x)
{
return cur;
}
cur = cur->next;
}
return NULL;
}
void ListInsert(LTNode* pos, ListDataType x)//在pos之前插入
{
assert(pos);
LTNode* newnode = BuyListNode(x);
LTNode* tail = pos->prev;
tail->next = newnode;
newnode->prev = tail;
newnode->next = pos;
pos->prev = newnode;
}
void ListErase(LTNode* pos)//刪除pos位置
{
assert(pos);
LTNode* prevnode = pos->prev;
LTNode* nextnode = pos->next;
free(pos);
prevnode->next = nextnode;
nextnode->prev = prevnode;
/*pos->next->prev = pos->prev;
pos->prev->next = pos->next;
free(pos);*/
}
bool ListEmpty(LTNode* phead)//判斷是否為空,如果是空，返回true
{
assert(phead);
return phead->next == phead;
}
size_t ListSize(LTNode* phead)//計算鏈表中有效值的個數
{
assert(phead);
size_t size = 0;
LTNode* tail = phead->next;
while (tail != phead)
{
size++;
tail = tail->next;
}
return size;
}
void ListDestroy(LTNode* phead)//銷毀鏈表
{
assert(phead);
LTNode* tail = phead->next;
while (tail != phead)
{
LTNode* nextnode = tail->next;
free(tail);
tail = nextnode;
}
free(phead);
}
void TestList()
{
//LTNode* plist = ListInit(&plist);
LTNode* plist = NULL;
ListInit(&plist);
ListPushBack(plist, 100);
ListPushBack(plist, 200);
ListPushBack(plist, 300);
ListPushBack(plist, 400);
ListPushBack(plist, 500);
ListPopBack(plist);
ListPopBack(plist);
ListPopBack(plist);
ListPrint(plist);
ListPushFront(plist, 1000);
ListPushFront(plist, 2000);
ListPushFront(plist, 3000);
ListPopFront(plist);
ListPopFront(plist);
ListPrint(plist);
LTNode* pos = ListFind(plist, 1000);
if (pos != NULL)
{
ListInsert(pos, 500);
ListErase(pos);
}
ListPrint(plist);
if (!ListEmpty(plist))
printf("%d\n", ListSize(plist));
}
int main()
{
TestList();
return 0;
}
以上就是C語言中帶頭雙向循環(huán)鏈表基本操作的實現詳解的詳細內容，更多關于C語言 帶頭雙向循環(huán)鏈表的資料請關注腳本之家其它相關文章！
相關文章
驅動與應用程序的通信是非常有必要的，內核中執(zhí)行代碼后需要將其動態(tài)顯示給應用層。為了實現內核與應用層數據交互則必須有通信的方法，微軟為我們提供了三種通信方式，本文先來介紹通過ReadFile系列函數實現的通信模式2022-09-09
這篇文章主要介紹了CrashRpt使用案例詳解,本篇文章通過簡要的案例,講解了該項技術的了解與使用,以下就是詳細內容,需要的朋友可以參考下2021-08-08
這篇文章主要介紹了C數據結構循環(huán)鏈表實現約瑟夫環(huán)的相關資料,需要的朋友可以參考下2017-05-05
這篇文章主要介紹了C++ 計數排序實例詳解的相關資料,需要的朋友可以參考下2017-07-07
這篇文章主要為大家詳細介紹了C語言源碼實現俄羅斯方塊，文中示例代碼介紹的非常詳細，具有一定的參考價值，感興趣的小伙伴們可以參考一下2018-06-06
C/C++ 運用Npcap發(fā)送UDP數據包的完美過程
UDP 是一種無連接、輕量級的傳輸層協(xié)議,與 TCP 相比,它不提供可靠性、流控制和錯誤恢復機制,但卻更加簡單且具有較低的開銷,這篇文章主要介紹了C/C++ 運用Npcap發(fā)送UDP數據包,需要的朋友可以參考下2023-11-11
這篇文章主要介紹了詳解C++ STL vector容器訪問元素的幾種方式，文中通過示例代碼介紹的非常詳細，對大家的學習或者工作具有一定的參考學習價值，需要的朋友們下面隨著小編來一起學習學習吧2021-05-05
這篇文章主要介紹了詳解C++編程中的虛函數,包括在什么情況下應當聲明虛函數的相關講解,需要的朋友可以參考下2015-09-09
這篇文章主要為大家詳細介紹了如何利用c語言實現將文件中十六進制數據與二進制數據相互轉換，文中的示例代碼講解詳細，具有一定的借鑒價值，感興趣的可以學習一下2022-11-11
這篇文章主要介紹了C++使用ADO實現存取圖片的方法,需要的朋友可以參考下2014-07-07