C語言中雙鏈表的基本操作
更新時間：2023年02月05日 10:06:33 作者：安河橋畔
這篇文章主要介紹了C語言中雙鏈表的基本操作，具有很好的參考價值，希望對大家有所幫助。如有錯誤或未考慮完全的地方，望不吝賜教
帶頭結點的雙向循環(huán)鏈表
鏈表結構如下：
每個節(jié)點都有一個數據域和兩個指針域，這兩個指針分別指向鏈表的前驅節(jié)點和后繼節(jié)點，頭節(jié)點的前驅節(jié)點是鏈表的最后一個節(jié)點，鏈表最后一個節(jié)點的后繼節(jié)點是頭節(jié)點。
正因為如此，帶頭結點的雙向循環(huán)鏈表沒有空節(jié)點，在進行遍歷時，循環(huán)條件也與單鏈表不同：
單鏈表用cur->next為空判斷當前節(jié)點是否為最后一個節(jié)點，帶頭的雙向循環(huán)鏈表則需判斷cur->next是否等于頭節(jié)點。
定義：
typedef int DataType;
typedef struct ListNode
{
DataType data;//數據域
struct ListNode* next;//指向下一個節(jié)點
struct ListNode* prev;//指向前一個節(jié)點
}ListNode;
基本操作
創(chuàng)建
創(chuàng)建鏈表需要先申請一段內存，然后再進行賦值，這里BuyListNode函數用于申請內存空間，在插入節(jié)點時，也需要調用BuyListNode函數。
申請節(jié)點：
static ListNode* BuyListNode(int x)
{
ListNode* newNode = NULL;
newNode = (ListNode*)malloc(sizeof(ListNode));//為節(jié)點動態(tài)申請一段內存
if (NULL == newNode)
{
assert(0);
return NULL;
}
//為申請的節(jié)點賦值
newNode->data = x;
newNode->next = NULL;
newNode->prev = NULL;
return newNode;
}
創(chuàng)建鏈表：
ListNode* ListCreate()
{
ListNode*head=BuyListNode(0);//調用申請節(jié)點的函數
//為頭節(jié)點指針域賦值，鏈表為空時，prev和next都指向頭節(jié)點
head->next = head;
head->prev = head;
return head;
}
銷毀
使用鏈表時會申請內存空間，所使用完畢后要進行釋放，避免內存泄漏，這里銷毀鏈表用了頭刪的思想，每次刪除鏈表中的第一個節(jié)點并釋放空間，具體過程如圖：
循環(huán)執(zhí)行上述過程，直到鏈表為空，最后再釋放頭節(jié)點空間。
程序如下：
void ListDestory(ListNode** plist)
{
assert(plist);
ListNode* cur = (*plist)->next;
while (cur!=(*plist))
{
(*plist)->next = cur->next;
free(cur);
cur = (*plist)->next;
}
free(*plist);
*plist = NULL;
}
這里需要注意的是，銷毀鏈表要改變鏈表頭結點的指向，所以傳參時需要傳二級指針。在對帶頭結點的雙鏈表的操作中，只有銷毀會改變指向頭結點的指針plist的指向，所以只有銷毀時需要傳二級指針，其余操作傳一級指針即可。
打印
鏈表打印的思想比較簡單，只需要遍歷打印即可。
程序：
void ListPrint(ListNode* plist)
{
assert(plist);
ListNode* cur = plist->next;
while (cur != plist)//遍歷的循環(huán)條件
{
printf("%d--->", cur->data);
cur = cur->next;
}
printf("\n");
}
尾插法
步驟
- 申請新節(jié)點newNode
- 對newNode的prev和next進行賦值
- 使原鏈表最后一個節(jié)點的next指向新節(jié)點
- 鏈表頭指針的prev指向新節(jié)點
void ListPushBack(ListNode* plist, DataType x)
{
assert(plist);
ListNode* newNode =BuyListNode(x);
newNode->prev = plist->prev;
newNode->next = plist;
plist->prev->next = newNode;
plist->prev = newNode;
}
尾刪
刪除節(jié)點時需要先判斷鏈表是否為空，先寫出鏈表判空的方法
鏈表判空
看plist->next是否等于plist即可判斷鏈表是否為空
static int IsEmpty(ListNode*plist)
{
assert(plist);
if (plist->next == plist)
{
return 1;//鏈表為空，返回1
}
return 0;//鏈表非空，返回0
}
尾刪法
步驟
- 用del標記最后一個節(jié)點
- 使del前一個節(jié)點的next指向頭節(jié)點
- 頭結點的prev指向del的前一個節(jié)點
- 釋放del的空間
- 這里中間兩步將del節(jié)點從鏈表中移除出來，最后一步則釋放內存空間
- 如圖：
程序
void ListPopBack(ListNode * plist)
{
assert(plist);
if (IsEmpty(plist))
{
return;
}
ListNode* del = plist->prev;
del->prev->next = plist;
plist->prev = del->prev;
free(del);
del = NULL;
}
頭插
步驟
- 申請新節(jié)點newNode
- 使新節(jié)點的prev指向頭節(jié)點
- 令新節(jié)點的next指向原來鏈表第二個節(jié)點
- 令原來第二個節(jié)點的prev指向newNode
- 令頭節(jié)點的next指向newNode
程序
void ListPushFront(ListNode* plist, DataType x)
{
assert(plist);
ListNode* newNode = BuyListNode(0);
newNode->prev = plist;
newNode->next = plist->next;
plist->next->prev = newNode;
plist->next = newNode;
}
頭刪
- 用del標記鏈表的第一個節(jié)點
- 令頭結點的next指向del->next
- 原鏈表中第二個節(jié)點的prev指向頭節(jié)點，成為新的第一個節(jié)點
- 釋放刪除節(jié)點的空間
程序
void ListPopFront(ListNode* plist)
{
assert(plist);
if (IsEmpty(plist))//先判空
{
return;
}
ListNode* del = plist->next;
plist->next = del->next;
del->next->prev = plist;
free(del);
del = NULL;
}
查找元素位置
對鏈表進行遍歷，比對，找到與目標值相等的數時，返回當前的地址
ListNode* ListFind(ListNode* plist, DataType x)
{
assert(plist);
ListNode* cur = plist->next;
while (cur != plist)
{
if (cur->data == x)
{
return cur;
}
cur = cur->next;
}
return NULL;
}
任意位置插入
由于雙鏈表有兩個指針域，所以可以在pos位置的前面進行插入
步驟
- 申請一個新節(jié)點newNode
- 為新節(jié)點的prev和next賦值，使其分別指向pos的前一個節(jié)點和pos
- 使原來pos前一個節(jié)點的next指向新節(jié)點
- 令pos的prev指向新節(jié)點
void ListInsert(ListNode* pos, DataType x)
{
assert(pos);
ListNode* newNode = BuyListNode(x);
//在pos前面插入
newNode->prev = pos->prev;
newNode->next = pos;
pos->prev->next = newNode;
pos->prev = newNode;
}
任意位置刪除
刪除給定的節(jié)點pos
- pos前一個節(jié)點的next指向pos的下一個節(jié)點
- pos下一個節(jié)點的prev指向pos的前一個節(jié)點
- 釋放pos占用的內存空間
程序
void ListErase(ListNode* pos)
{
assert(pos);
pos->prev->next = pos->next;
pos->next->prev = pos->prev;
free(pos);
pos = NULL;
}
完整代碼及測試
work.h
#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<Windows.h>
typedef int DataType;
typedef struct ListNode
{
DataType data;
struct ListNode* next;
struct ListNode* prev;
}ListNode;
ListNode* ListCreate();// 創(chuàng)建返回鏈表的頭結點.
void ListDestory(ListNode** plist);// 雙向鏈表銷毀
void ListPrint(ListNode* plist);// 雙向鏈表打印
void ListPushBack(ListNode* plist, DataType x);// 雙向鏈表尾插
void ListPopBack(ListNode* plist);// 雙向鏈表尾刪
void ListPushFront(ListNode* plist, DataType x);// 雙向鏈表頭插
void ListPopFront(ListNode* plist);// 雙向鏈表頭刪
ListNode* ListFind(ListNode* plist, DataType x);// 雙向鏈表查找
void ListInsert(ListNode* pos, DataType x);// 雙向鏈表在pos的前面進行插入
void ListErase(ListNode* pos);// 雙向鏈表刪除pos位置的節(jié)點
work.c
#include"work.h"
//申請節(jié)點
static ListNode* BuyListNode(int x)
{
ListNode* newNode = NULL;
newNode = (ListNode*)malloc(sizeof(ListNode));//為節(jié)點動態(tài)申請一段內存
if (NULL == newNode)
{
assert(0);
return NULL;
}
//為申請的節(jié)點賦值
newNode->data = x;
newNode->next = NULL;
newNode->prev = NULL;
return newNode;
}
//創(chuàng)建鏈表
ListNode* ListCreate()
{
ListNode*head=BuyListNode(0);//調用申請節(jié)點的函數
//為頭節(jié)點指針域賦值，鏈表為空時，prev和next都指向頭節(jié)點
head->next = head;
head->prev = head;
return head;
}
//銷毀鏈表
void ListDestory(ListNode** plist)
{
assert(plist);
ListNode* cur = (*plist)->next;
while (cur!=(*plist))
{
(*plist)->next = cur->next;
free(cur);
cur = (*plist)->next;
}
free(*plist);
*plist = NULL;
}
// 打印鏈表
void ListPrint(ListNode* plist)
{
assert(plist);
ListNode* cur = plist->next;
while (cur != plist)
{
printf("%d--->", cur->data);
cur = cur->next;
}
printf("\n");
}
//尾插法
void ListPushBack(ListNode* plist, DataType x)
{
assert(plist);
ListNode* newNode =BuyListNode(x);
newNode->prev = plist->prev;
newNode->next = plist;
plist->prev->next = newNode;
plist->prev = newNode;
}
//判斷鏈表是否為空
static int IsEmpty(ListNode*plist)
{
assert(plist);
if (plist->next == plist)
{
return 1;
}
return 0;
}
// 尾刪法
void ListPopBack(ListNode * plist)
{
assert(plist);
if (IsEmpty(plist))
{
return;
}
ListNode* del = plist->prev;
del->prev->next = plist;
plist->prev = del->prev;
free(del);
del = NULL;
}
// 雙向鏈表頭插
void ListPushFront(ListNode* plist, DataType x)
{
assert(plist);
ListNode* newNode = BuyListNode(0);
newNode->prev = plist;
newNode->next = plist->next;
plist->next->prev = newNode;
plist->next = newNode;
}
// 雙向鏈表頭刪
void ListPopFront(ListNode* plist)
{
assert(plist);
if (IsEmpty(plist))
{
return;
}
ListNode* del = plist->next;
plist->next = del->next;
del->next->prev = plist;
free(del);
del = NULL;
}
// 查找元素位置
ListNode* ListFind(ListNode* plist, DataType x)
{
assert(plist);
ListNode* cur = plist->next;
while (cur != plist)
{
if (cur->data == x)
{
return cur;
}
cur = cur->next;
}
return NULL;
}
// 任意位置插入
void ListInsert(ListNode* pos, DataType x)
{
assert(pos);
ListNode* newNode = BuyListNode(x);
//在pos前面插入
newNode->prev = pos->prev;
newNode->next = pos;
pos->prev->next = newNode;
pos->prev = newNode;
}
//任意位置刪除
void ListErase(ListNode* pos)
{
assert(pos);
pos->prev->next = pos->next;
pos->next->prev = pos->prev;
free(pos);
pos = NULL;
}
main.c
#include"work.h"
int main()
{
ListNode*plist= ListCreate();//創(chuàng)建一個雙向非循環(huán)鏈表
//尾插五個節(jié)點
ListPushBack(plist, 1);
ListPushBack(plist, 2);
ListPushBack(plist, 3);
ListPushBack(plist, 4);
ListPushBack(plist, 5);
ListPrint(plist);
//頭插一個節(jié)點
ListPushFront(plist, 0);
ListPrint(plist);
//尾刪一個節(jié)點
ListPopBack(plist);
ListPrint(plist);
//頭刪一個節(jié)點
ListPopFront(plist);
ListPrint(plist);
//在元素3前面插入一個節(jié)點
ListInsert(ListFind(plist,3),9);
ListPrint(plist);
//刪除值為9的節(jié)點
ListErase(ListFind(plist,9));
ListPrint(plist);
//銷毀鏈表
ListDestory(&plist);
system("pause");
return 0;
}
測試結果：
總結
以上為個人經驗，希望能給大家一個參考，也希望大家多多支持腳本之家。
相關文章
在C語言和C++等語言中，數組元素全為指針變量的數組稱為指針數組，指針數組中的元素都必須具有相同的存儲類型、指向相同數據類型的指針變量。指針數組比較適合用來指向若干個字符串，使字符串處理更加方便、靈活2022-04-04
本文主要介紹了幾種C++類型轉換，文中通過示例代碼介紹的非常詳細，具有一定的參考價值，感興趣的小伙伴們可以參考一下2021-08-08
這篇文章主要為大家詳細介紹了C語言實現簡單停車場管理系統(tǒng)，文中示例代碼介紹的非常詳細，具有一定的參考價值，感興趣的小伙伴們可以參考一下2019-12-12
本篇文章是c語言基礎篇，主要為大家介紹了C語言的sizeof與strlen的基本理論知識，希望可以幫助大家快速入門c語言的世界，更好的理解c語言2021-08-08
這篇文章主要為大家詳細介紹了C語言掃雷游戲的實現代碼，文中示例代碼介紹的非常詳細，具有一定的參考價值，感興趣的小伙伴們可以參考一下2020-11-11
這篇文章主要為大家詳細介紹了C語言實現出棧序列合法性判定，文中示例代碼介紹的非常詳細，具有一定的參考價值，感興趣的小伙伴們可以參考一下2021-05-05
這篇文章主要介紹了C++實現LeetCode(71.簡化路徑),本篇文章通過簡要的案例,講解了該項技術的了解與使用,以下就是詳細內容,需要的朋友可以參考下2021-07-07
一般而言，每個C++/C程序通常由頭文件和定義文件組成。頭文件作為一種包含功能函數、數據接口聲明的載體文件，主要用于保存程序的聲明，而定義文件用于保存程序的實現 。2017-02-02
Visual Studio2022+QT6創(chuàng)建桌面應用實現
本文主要介紹了Visual Studio2022+QT6創(chuàng)建桌面應用實現,文中通過圖文介紹的非常詳細,對大家的學習或者工作具有一定的參考學習價值,需要的朋友們下面隨著小編來一起學習學習吧2024-02-02
本篇文章是對階乘進行了詳細的分析介紹，需要的朋友參考下2013-05-05