C語(yǔ)言中雙鏈表的基本操作
更新時(shí)間：2023年02月05日 10:06:33 作者：安河橋畔
這篇文章主要介紹了C語(yǔ)言中雙鏈表的基本操作，具有很好的參考價(jià)值，希望對(duì)大家有所幫助。如有錯(cuò)誤或未考慮完全的地方，望不吝賜教
帶頭結(jié)點(diǎn)的雙向循環(huán)鏈表
鏈表結(jié)構(gòu)如下：
每個(gè)節(jié)點(diǎn)都有一個(gè)數(shù)據(jù)域和兩個(gè)指針域，這兩個(gè)指針分別指向鏈表的前驅(qū)節(jié)點(diǎn)和后繼節(jié)點(diǎn)，頭節(jié)點(diǎn)的前驅(qū)節(jié)點(diǎn)是鏈表的最后一個(gè)節(jié)點(diǎn)，鏈表最后一個(gè)節(jié)點(diǎn)的后繼節(jié)點(diǎn)是頭節(jié)點(diǎn)。
正因?yàn)槿绱?，帶頭結(jié)點(diǎn)的雙向循環(huán)鏈表沒有空節(jié)點(diǎn)，在進(jìn)行遍歷時(shí)，循環(huán)條件也與單鏈表不同：
單鏈表用cur->next為空判斷當(dāng)前節(jié)點(diǎn)是否為最后一個(gè)節(jié)點(diǎn)，帶頭的雙向循環(huán)鏈表則需判斷cur->next是否等于頭節(jié)點(diǎn)。
定義：
typedef int DataType;
typedef struct ListNode
{
DataType data;//數(shù)據(jù)域
struct ListNode* next;//指向下一個(gè)節(jié)點(diǎn)
struct ListNode* prev;//指向前一個(gè)節(jié)點(diǎn)
}ListNode;
基本操作
創(chuàng)建
創(chuàng)建鏈表需要先申請(qǐng)一段內(nèi)存，然后再進(jìn)行賦值，這里BuyListNode函數(shù)用于申請(qǐng)內(nèi)存空間，在插入節(jié)點(diǎn)時(shí)，也需要調(diào)用BuyListNode函數(shù)。
申請(qǐng)節(jié)點(diǎn)：
static ListNode* BuyListNode(int x)
{
ListNode* newNode = NULL;
newNode = (ListNode*)malloc(sizeof(ListNode));//為節(jié)點(diǎn)動(dòng)態(tài)申請(qǐng)一段內(nèi)存
if (NULL == newNode)
{
assert(0);
return NULL;
}
//為申請(qǐng)的節(jié)點(diǎn)賦值
newNode->data = x;
newNode->next = NULL;
newNode->prev = NULL;
return newNode;
}
創(chuàng)建鏈表：
ListNode* ListCreate()
{
ListNode*head=BuyListNode(0);//調(diào)用申請(qǐng)節(jié)點(diǎn)的函數(shù)
//為頭節(jié)點(diǎn)指針域賦值，鏈表為空時(shí)，prev和next都指向頭節(jié)點(diǎn)
head->next = head;
head->prev = head;
return head;
}
銷毀
使用鏈表時(shí)會(huì)申請(qǐng)內(nèi)存空間，所使用完畢后要進(jìn)行釋放，避免內(nèi)存泄漏，這里銷毀鏈表用了頭刪的思想，每次刪除鏈表中的第一個(gè)節(jié)點(diǎn)并釋放空間，具體過程如圖：
循環(huán)執(zhí)行上述過程，直到鏈表為空，最后再釋放頭節(jié)點(diǎn)空間。
程序如下：
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;
}
這里需要注意的是，銷毀鏈表要改變鏈表頭結(jié)點(diǎn)的指向，所以傳參時(shí)需要傳二級(jí)指針。在對(duì)帶頭結(jié)點(diǎn)的雙鏈表的操作中，只有銷毀會(huì)改變指向頭結(jié)點(diǎn)的指針plist的指向，所以只有銷毀時(shí)需要傳二級(jí)指針，其余操作傳一級(jí)指針即可。
打印
鏈表打印的思想比較簡(jiǎn)單，只需要遍歷打印即可。
程序：
void ListPrint(ListNode* plist)
{
assert(plist);
ListNode* cur = plist->next;
while (cur != plist)//遍歷的循環(huán)條件
{
printf("%d--->", cur->data);
cur = cur->next;
}
printf("\n");
}
尾插法
步驟
- 申請(qǐng)新節(jié)點(diǎn)newNode
- 對(duì)newNode的prev和next進(jìn)行賦值
- 使原鏈表最后一個(gè)節(jié)點(diǎn)的next指向新節(jié)點(diǎn)
- 鏈表頭指針的prev指向新節(jié)點(diǎ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;
}
尾刪
刪除節(jié)點(diǎn)時(shí)需要先判斷鏈表是否為空，先寫出鏈表判空的方法
鏈表判空
看plist->next是否等于plist即可判斷鏈表是否為空
static int IsEmpty(ListNode*plist)
{
assert(plist);
if (plist->next == plist)
{
return 1;//鏈表為空，返回1
}
return 0;//鏈表非空，返回0
}
尾刪法
步驟
- 用del標(biāo)記最后一個(gè)節(jié)點(diǎn)
- 使del前一個(gè)節(jié)點(diǎn)的next指向頭節(jié)點(diǎn)
- 頭結(jié)點(diǎn)的prev指向del的前一個(gè)節(jié)點(diǎn)
- 釋放del的空間
- 這里中間兩步將del節(jié)點(diǎn)從鏈表中移除出來，最后一步則釋放內(nèi)存空間
- 如圖：
程序
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;
}
頭插
步驟
- 申請(qǐng)新節(jié)點(diǎn)newNode
- 使新節(jié)點(diǎn)的prev指向頭節(jié)點(diǎn)
- 令新節(jié)點(diǎn)的next指向原來鏈表第二個(gè)節(jié)點(diǎn)
- 令原來第二個(gè)節(jié)點(diǎn)的prev指向newNode
- 令頭節(jié)點(diǎn)的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標(biāo)記鏈表的第一個(gè)節(jié)點(diǎn)
- 令頭結(jié)點(diǎn)的next指向del->next
- 原鏈表中第二個(gè)節(jié)點(diǎn)的prev指向頭節(jié)點(diǎn)，成為新的第一個(gè)節(jié)點(diǎn)
- 釋放刪除節(jié)點(diǎn)的空間
程序
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;
}
查找元素位置
對(duì)鏈表進(jìn)行遍歷，比對(duì)，找到與目標(biāo)值相等的數(shù)時(shí)，返回當(dāng)前的地址
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;
}
任意位置插入
由于雙鏈表有兩個(gè)指針域，所以可以在pos位置的前面進(jìn)行插入
步驟
- 申請(qǐng)一個(gè)新節(jié)點(diǎn)newNode
- 為新節(jié)點(diǎn)的prev和next賦值，使其分別指向pos的前一個(gè)節(jié)點(diǎn)和pos
- 使原來pos前一個(gè)節(jié)點(diǎn)的next指向新節(jié)點(diǎn)
- 令pos的prev指向新節(jié)點(diǎn)
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é)點(diǎn)pos
- pos前一個(gè)節(jié)點(diǎn)的next指向pos的下一個(gè)節(jié)點(diǎn)
- pos下一個(gè)節(jié)點(diǎn)的prev指向pos的前一個(gè)節(jié)點(diǎn)
- 釋放pos占用的內(nèi)存空間
程序
void ListErase(ListNode* pos)
{
assert(pos);
pos->prev->next = pos->next;
pos->next->prev = pos->prev;
free(pos);
pos = NULL;
}
完整代碼及測(cè)試
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)建返回鏈表的頭結(jié)點(diǎn).
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的前面進(jìn)行插入
void ListErase(ListNode* pos);// 雙向鏈表刪除pos位置的節(jié)點(diǎn)
work.c
#include"work.h"
//申請(qǐng)節(jié)點(diǎn)
static ListNode* BuyListNode(int x)
{
ListNode* newNode = NULL;
newNode = (ListNode*)malloc(sizeof(ListNode));//為節(jié)點(diǎn)動(dòng)態(tài)申請(qǐng)一段內(nèi)存
if (NULL == newNode)
{
assert(0);
return NULL;
}
//為申請(qǐng)的節(jié)點(diǎn)賦值
newNode->data = x;
newNode->next = NULL;
newNode->prev = NULL;
return newNode;
}
//創(chuàng)建鏈表
ListNode* ListCreate()
{
ListNode*head=BuyListNode(0);//調(diào)用申請(qǐng)節(jié)點(diǎn)的函數(shù)
//為頭節(jié)點(diǎn)指針域賦值，鏈表為空時(shí)，prev和next都指向頭節(jié)點(diǎn)
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)建一個(gè)雙向非循環(huán)鏈表
//尾插五個(gè)節(jié)點(diǎn)
ListPushBack(plist, 1);
ListPushBack(plist, 2);
ListPushBack(plist, 3);
ListPushBack(plist, 4);
ListPushBack(plist, 5);
ListPrint(plist);
//頭插一個(gè)節(jié)點(diǎn)
ListPushFront(plist, 0);
ListPrint(plist);
//尾刪一個(gè)節(jié)點(diǎn)
ListPopBack(plist);
ListPrint(plist);
//頭刪一個(gè)節(jié)點(diǎn)
ListPopFront(plist);
ListPrint(plist);
//在元素3前面插入一個(gè)節(jié)點(diǎn)
ListInsert(ListFind(plist,3),9);
ListPrint(plist);
//刪除值為9的節(jié)點(diǎn)
ListErase(ListFind(plist,9));
ListPrint(plist);
//銷毀鏈表
ListDestory(&plist);
system("pause");
return 0;
}
測(cè)試結(jié)果：
總結(jié)
以上為個(gè)人經(jīng)驗(yàn)，希望能給大家一個(gè)參考，也希望大家多多支持腳本之家。
您可能感興趣的文章:
相關(guān)文章
c++使用Easyx圖形庫(kù)實(shí)現(xiàn)飛機(jī)大戰(zhàn)
本文詳細(xì)講解了c++使用Easyx圖形庫(kù)實(shí)現(xiàn)飛機(jī)大戰(zhàn)，文中通過示例代碼介紹的非常詳細(xì)。對(duì)大家的學(xué)習(xí)或工作具有一定的參考借鑒價(jià)值，需要的朋友可以參考下2021-12-12
詳解C++編程中類的成員變量和成員函數(shù)的相關(guān)知識(shí)
這篇文章主要介紹了C++編程中類的成員變量和成員函數(shù)的相關(guān)知識(shí),是C++入門學(xué)習(xí)中的基礎(chǔ)知識(shí),需要的朋友可以參考下2015-09-09
C語(yǔ)言深入探索數(shù)據(jù)類型的存儲(chǔ)
使用編程語(yǔ)言進(jìn)行編程時(shí)，需要用到各種變量來存儲(chǔ)各種信息。變量保留的是它所存儲(chǔ)的值的內(nèi)存位置。這意味著，當(dāng)您創(chuàng)建一個(gè)變量時(shí)，就會(huì)在內(nèi)存中保留一些空間。您可能需要存儲(chǔ)各種數(shù)據(jù)類型的信息，操作系統(tǒng)會(huì)根據(jù)變量的數(shù)據(jù)類型，來分配內(nèi)存和決定在保留內(nèi)存中存儲(chǔ)什么2022-07-07
C語(yǔ)言詳細(xì)講解通過遞歸實(shí)現(xiàn)掃雷的展開
windows自帶的游戲《掃雷》是陪伴了無數(shù)人的經(jīng)典游戲，本文將利用C語(yǔ)言實(shí)現(xiàn)這一經(jīng)典的游戲，文中的示例代碼講解詳細(xì)，感興趣的可以學(xué)習(xí)一下2022-05-05
這篇文章主要為大家介紹了C語(yǔ)言strcpy庫(kù)函數(shù)，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下，希望能夠給你帶來幫助2021-11-11
在處理跨平臺(tái)的數(shù)據(jù)交換或網(wǎng)絡(luò)通信時(shí),字節(jié)流的重要性更加突出,不同的系統(tǒng)可能有不同的字節(jié)序（大端序或小端序）,因此在發(fā)送和接收字節(jié)流時(shí),可能需要考慮字節(jié)序的轉(zhuǎn)換,這篇文章主要介紹了C++實(shí)用庫(kù)之字節(jié)流合成器,需要的朋友可以參考下2024-04-04
C++中異常處理的基本思想及throw語(yǔ)句拋出異常的使用
這篇文章主要介紹了C++中異常處理的基本思想及throw類拋出異常的使用,也深入談到了異常被拋出后的棧解旋unwinding過程,需要的朋友可以參考下2016-03-03
C語(yǔ)言實(shí)現(xiàn)通用數(shù)據(jù)結(jié)構(gòu)之通用鏈表
這篇文章主要為大家詳細(xì)介紹了c語(yǔ)言實(shí)現(xiàn)通用數(shù)據(jù)結(jié)構(gòu)之通用鏈表，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下2021-11-11
詳解Matlab繪制3D玫瑰花的方法(內(nèi)附旋轉(zhuǎn)版本)
這篇文章主要為大家介紹了如何利用Matlab繪制3D版的玫瑰花以及旋轉(zhuǎn)版的3D玫瑰花，文中的示例代碼講解詳細(xì)，感興趣的小伙伴可以動(dòng)手試一試2022-03-03
Qt使用QCamera實(shí)現(xiàn)切換相機(jī),分辨率和圖像捕獲功能
這篇文章主要為大家介紹了如何利用Qt中的相機(jī)類QCamera，取景器類QCameraViewfinder，圖像捕獲類QCameraImageCapture實(shí)現(xiàn)切換相機(jī)、分辨率和圖像捕獲功能，需要的可以了解一下2023-04-04