【數(shù)據(jù)結(jié)構(gòu)初階】四、線性表里的鏈表（帶頭+雙向+循環(huán) 鏈表 -- C語言實(shí)現(xiàn)）

這篇具有很好參考價(jià)值的文章主要介紹了【數(shù)據(jù)結(jié)構(gòu)初階】四、線性表里的鏈表（帶頭+雙向+循環(huán) 鏈表 -- C語言實(shí)現(xiàn)）。希望對大家有所幫助。如果存在錯(cuò)誤或未考慮完全的地方，請大家不吝賜教，您也可以點(diǎn)擊"舉報(bào)違法"按鈕提交疑問。

=========================================================================

相關(guān)代碼gitee自取：

C語言學(xué)習(xí)日記: 加油努力 (gitee.com)

?=========================================================================

接上期：

【數(shù)據(jù)結(jié)構(gòu)初階】三、線性表里的鏈表（無頭+單向+非循環(huán)鏈表 -- C語言實(shí)現(xiàn)）-CSDN博客

?=========================================================================

? ? ? ? ? ? ? ? ? ? ?

?引言?

通過上期對單鏈表（無頭+單向+非循環(huán)鏈表）的介紹和使用

我們可以知道順序表和鏈表的區(qū)別：

? ? ? ? ? ? ??

? ? ? ? ? ? ??

順序表和鏈表的一些區(qū)別：

? ? ? ? ? ? ??

單鏈表（無頭+單向+非循環(huán)鏈表）只有一個(gè)后繼指針next指向下一個(gè)結(jié)點(diǎn)，
而雙向鏈表不僅有后繼指針next還有一個(gè)前驅(qū)指針prev指向上一個(gè)結(jié)點(diǎn)
? ? ? ? ? ? ? ? ? ? ?

上篇單鏈表只能順著往后遍歷，不能倒著往回走，
會(huì)造成一些操作很困難（回文、逆置等操作），
而雙向鏈表能順著往后遍歷也能倒著往回遍歷

更多區(qū)別圖示：

不同點(diǎn)（方面）順序表鏈表

存儲(chǔ)空間上物理上一定連續(xù) 邏輯上連續(xù)，但物理上不一定連續(xù)

隨機(jī)訪問支持 -- O(1) 不支持 -- O(N)

任意位置插入或者刪除可能需要搬移元素，效率低 -- O(N) 只需修改指針指向

插入時(shí)的容量（空間）動(dòng)態(tài)順序表，空間不夠時(shí)需要擴(kuò)容沒有容量的概念（分成一個(gè)個(gè)結(jié)點(diǎn)）

應(yīng)用場景元素高效存儲(chǔ)+頻繁訪問頻繁在任意位置插入和刪除

緩存利用率高低

注：緩存利用率參考存儲(chǔ)體系結(jié)構(gòu) 以及局部原理性

? ? ? ? ? ? ? ?

? ? ? ? ? ? ? ??

回顧上期中提到的帶頭雙向循環(huán)鏈表：

? ? ? ? ? ?

帶頭雙向循環(huán)鏈表

簡介：

結(jié)構(gòu)最復(fù)雜，一般用在單獨(dú)存儲(chǔ)數(shù)據(jù)。

實(shí)際中使用的鏈表數(shù)據(jù)結(jié)構(gòu)，都是帶頭雙向循環(huán)鏈表。

另外這個(gè)結(jié)構(gòu)雖然結(jié)構(gòu)復(fù)雜，

但是使用代碼實(shí)現(xiàn)以后會(huì)發(fā)現(xiàn)結(jié)構(gòu)會(huì)帶來很多優(yōu)勢，實(shí)現(xiàn)反而簡單了

圖示：

不同點(diǎn)（方面）	順序表	鏈表
存儲(chǔ)空間上	物理上一定連續(xù)	邏輯上連續(xù)，但物理上不一定連續(xù)
隨機(jī)訪問	支持 -- O(1)	不支持 -- O(N)
任意位置插入或者刪除	可能需要搬移元素，效率低 -- O(N)	只需修改指針指向
插入時(shí)的容量（空間）	動(dòng)態(tài)順序表，空間不夠時(shí)需要擴(kuò)容	沒有容量的概念（分成一個(gè)個(gè)結(jié)點(diǎn)）
應(yīng)用場景	元素高效存儲(chǔ)+頻繁訪問	頻繁在任意位置插入和刪除
緩存利用率	高	低

? ? ? ? ?

~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

? ? ? ? ? ? ?

1 . 雙向鏈表的實(shí)現(xiàn) （帶頭+雙向+循環(huán) 鏈表）

（詳細(xì)解釋在圖片的注釋中，代碼分文件放最后） ? ? ? ? ? ? ? ? ??

實(shí)現(xiàn)具體功能前的準(zhǔn)備工作

包含之后會(huì)用到的頭函數(shù)
? ? ? ? ? ? ? ? ? ? ? ? ? ?

創(chuàng)建雙向鏈表數(shù)據(jù)類型?--?鏈表結(jié)點(diǎn)中數(shù)據(jù)域里存儲(chǔ)的數(shù)據(jù)的類型
? ? ? ? ? ? ?

創(chuàng)建雙向鏈表結(jié)點(diǎn)結(jié)構(gòu)體(類型) --?結(jié)點(diǎn)中應(yīng)有?數(shù)據(jù)域?和?指針域

圖示

? ? ? ? ? ??

? ? ? ? ? ??

---------------------------------------------------------------------------------------------

? ? ? ? ? ??

BuyLTNode函數(shù) --?創(chuàng)建雙向循環(huán)鏈表結(jié)點(diǎn)

為創(chuàng)建結(jié)點(diǎn)開辟動(dòng)態(tài)空間，并檢查是否開辟成功
? ? ? ? ? ? ? ? ? ? ??

開辟成功后，初始化結(jié)點(diǎn)數(shù)據(jù)域和指針域
? ? ? ? ? ? ? ?

最后返回開辟的空間地址

圖示

? ? ? ? ? ??

? ? ? ? ? ??

---------------------------------------------------------------------------------------------

? ? ? ? ? ??

LTInit函數(shù) --?帶頭雙向循環(huán)鏈表初始化函數(shù)

初始化時(shí)先使用BuyLTNode函數(shù)創(chuàng)建哨兵位
? ? ? ? ? ??

因?yàn)?span style="color:#fe2c24;">要實(shí)現(xiàn)循環(huán)，
所以讓哨兵位后繼指針next和前驅(qū)指針prev都指向自己
? ? ? ? ? ? ? ??

初始化后返回鏈表哨兵位

圖示

? ? ? ? ? ??

? ? ? ? ? ??

---------------------------------------------------------------------------------------------

? ? ? ? ? ??

LTPrint函數(shù) --?打印雙向鏈表各結(jié)點(diǎn)數(shù)據(jù)域數(shù)據(jù)

assert斷言頭指針（哨兵位地址）不為空
? ? ? ? ? ??

創(chuàng)建結(jié)點(diǎn)指針cur進(jìn)行遍歷
? ? ? ? ? ? ? ??

使用while循環(huán)進(jìn)行遍歷打印

圖示

測試 -- LTPrint函數(shù)

? ? ? ? ? ??

? ? ? ? ? ??

---------------------------------------------------------------------------------------------

? ? ? ? ? ??

LTPushBack函數(shù) --?向鏈表尾部插入一個(gè)結(jié)點(diǎn)（尾插）

assert斷言頭指針（哨兵位地址）不為空
? ? ? ? ? ??

通過哨兵位配合前驅(qū)指針prev獲得尾結(jié)點(diǎn)地址
? ? ? ? ? ? ? ??

調(diào)用BuyLTNode函數(shù)為尾插操作創(chuàng)建尾插結(jié)點(diǎn)newnode
? ? ? ? ? ? ? ? ?

將尾插結(jié)點(diǎn)和原尾部結(jié)點(diǎn)連接
? ? ? ? ? ? ? ? ?

將尾插結(jié)點(diǎn)和哨兵位進(jìn)行連接

圖示

測試 -- LTPushBack函數(shù)

? ? ? ? ? ??

? ? ? ? ? ??

---------------------------------------------------------------------------------------------

? ? ? ? ? ??

LTPopBack函數(shù) --?刪除鏈表尾部結(jié)點(diǎn)（尾刪）

assert斷言頭指針(哨兵位地址)不為空和雙向鏈表不為空鏈表
? ? ? ? ? ??

通過哨兵位的前驅(qū)指針prev獲得尾結(jié)點(diǎn)tail，
再通過尾結(jié)點(diǎn)tail獲得倒數(shù)第二個(gè)結(jié)點(diǎn)tailPrev
? ? ? ? ? ? ? ??

釋放（刪除）尾結(jié)點(diǎn)tail
? ? ? ? ? ? ? ? ?

讓倒數(shù)第二個(gè)結(jié)點(diǎn)tailPrev成為新的尾結(jié)點(diǎn)，
為保持循環(huán)，把tailPrev和哨兵位連接起來

圖示

測試 -- LTPopBack函數(shù)

? ? ? ? ? ??

? ? ? ? ? ??

---------------------------------------------------------------------------------------------

? ? ? ? ? ??

LTPushFront函數(shù) --?向鏈表頭部插入一個(gè)結(jié)點(diǎn)（頭插）

assert斷言頭指針（哨兵位地址）不為空
? ? ? ? ? ??

調(diào)用BuyLTNode函數(shù)為頭插操作創(chuàng)建頭插結(jié)點(diǎn)newnode
? ? ? ? ? ? ? ??

創(chuàng)建一個(gè)first指針保存原本第一個(gè)結(jié)點(diǎn)地址
? ? ? ? ? ? ? ? ?

哨兵位后繼指針next指向頭插結(jié)點(diǎn)newnode，
頭插結(jié)點(diǎn)newnode前驅(qū)指針prev指向哨兵位
? ? ? ? ? ? ? ? ?

頭插結(jié)點(diǎn)newnode后繼指針next指向原本頭結(jié)點(diǎn)first，
原本頭結(jié)點(diǎn)first前驅(qū)指針prev指向頭插結(jié)點(diǎn)newnode

圖示

測試 -- LTPushFront函數(shù)

? ? ? ? ? ??

? ? ? ? ? ??

---------------------------------------------------------------------------------------------

? ? ? ? ? ??

LTPopFront函數(shù) --?刪除鏈表頭部結(jié)點(diǎn)（頭刪）

assert斷言頭指針(哨兵位地址)不為空和雙向鏈表不為空鏈表
? ? ? ? ? ??

通過哨兵位后繼結(jié)點(diǎn)next獲得頭結(jié)點(diǎn)地址，
再通過first結(jié)點(diǎn)獲得第二個(gè)結(jié)點(diǎn)
? ? ? ? ? ? ? ??

釋放頭結(jié)點(diǎn)first
? ? ? ? ? ? ? ? ?

讓哨兵位后繼結(jié)點(diǎn)next指向第二個(gè)結(jié)點(diǎn)second，
第二個(gè)結(jié)點(diǎn)的前驅(qū)指針prev指向哨兵位

圖示

測試 -- LTPopFront函數(shù)

? ? ? ? ? ??

? ? ? ? ? ??

---------------------------------------------------------------------------------------------

? ? ? ? ? ??

LTSize函數(shù) --?求鏈表有效結(jié)點(diǎn)個(gè)數(shù)（求鏈表長度）

assert斷言頭指針（哨兵位地址）不為空
? ? ? ? ? ??

創(chuàng)建變量size存放鏈表長度，
創(chuàng)建結(jié)點(diǎn)指針cur進(jìn)行遍歷
? ? ? ? ? ? ? ??

使用while循環(huán)遍歷鏈表，計(jì)算鏈表長度
? ? ? ? ? ? ? ? ?

最后返回鏈表長度size

圖示

測試 -- LTSize函數(shù)

? ? ? ? ? ??

? ? ? ? ? ??

---------------------------------------------------------------------------------------------

? ? ? ? ? ??

LTFind函數(shù) --?在雙向鏈表中查找數(shù)據(jù)域數(shù)據(jù)為x的結(jié)點(diǎn)地址

assert斷言頭指針（哨兵位地址）不為空
? ? ? ? ? ??

創(chuàng)建遍歷指針cur，保存第一個(gè)結(jié)點(diǎn)地址
? ? ? ? ? ? ? ??

使用while循環(huán)進(jìn)行遍歷查找
? ? ? ? ? ? ? ? ?

未找到則返回空指針

圖示

測試 -- LTFind函數(shù)

? ? ? ? ? ??

? ? ? ? ? ??

---------------------------------------------------------------------------------------------

? ? ? ? ? ??

LTInsert函數(shù) --?在pos結(jié)點(diǎn)之前插入數(shù)據(jù)域數(shù)據(jù)為x的結(jié)點(diǎn)

assert斷言頭指針（哨兵位地址）不為空
? ? ? ? ? ??

通過pos結(jié)點(diǎn)獲得前一個(gè)結(jié)點(diǎn)posPrev地址
? ? ? ? ? ? ? ??

使用BuyLTNode函數(shù)為插入結(jié)點(diǎn)開辟空間
? ? ? ? ? ? ? ? ?

posPrev結(jié)點(diǎn)的后繼指針next指向newnode，
newnode前驅(qū)指針prev指向posPrev
? ? ? ? ? ? ? ? ?

newnode后繼指針next指向pos，
pos結(jié)點(diǎn)前驅(qū)指針prev指向newnode

圖示

測試 -- LTInsert函數(shù)

? ? ? ? ? ??

? ? ? ? ? ??

---------------------------------------------------------------------------------------------

? ? ? ? ? ??

LTErase函數(shù) --?刪除pos結(jié)點(diǎn)

assert斷言刪除位置結(jié)點(diǎn)pos不為空
? ? ? ? ? ??

保存要刪除結(jié)點(diǎn)pos的前一個(gè)結(jié)點(diǎn)posPrev地址，
保存要刪除結(jié)點(diǎn)pos的后一個(gè)結(jié)點(diǎn)posNext地址
? ? ? ? ? ? ? ??

釋放掉pos結(jié)點(diǎn)
? ? ? ? ? ? ? ? ?

將pos前結(jié)點(diǎn)posPrev的后繼指針指向posNext，
將pos后結(jié)點(diǎn)posNext的前驅(qū)指針指向posPrev

圖示

測試 -- LTErase函數(shù)

? ? ? ? ? ??

? ? ? ? ? ??

---------------------------------------------------------------------------------------------

? ? ? ? ? ??

LTDestroy函數(shù) --?銷毀鏈表

assert斷言頭指針（哨兵位地址）不為空
? ? ? ? ? ??

創(chuàng)建遍歷指針cur，保存第一個(gè)結(jié)點(diǎn)地址
? ? ? ? ? ? ? ??

使用while循環(huán)遍歷釋放有效結(jié)點(diǎn)
? ? ? ? ? ? ? ? ?

最后釋放哨兵位

圖示

? ? ? ? ?

~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

? ? ? ? ? ? ?

2 . 對應(yīng)代碼

List.h?-- 雙向鏈表頭文件

#pragma once

//雙向鏈表頭文件：

//包含之后需要用到的頭文件：
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>

//定義雙向鏈表數(shù)據(jù)域數(shù)據(jù)類型：
typedef int LTDataType;

//創(chuàng)建雙向鏈表結(jié)點(diǎn)類型：
typedef struct ListNode
{
	//數(shù)據(jù)域：
	LTDataType data;

	//雙向鏈表指針域：
	 //后繼指針--指向后一個(gè)結(jié)點(diǎn)：
	struct ListNode* next;
	 //前驅(qū)指針--指向前一個(gè)結(jié)點(diǎn)：
	struct ListNode* prev;

}LTNode; //類型簡稱LTNode



//函數(shù)聲明：

//創(chuàng)建鏈表結(jié)點(diǎn)--創(chuàng)建雙向循環(huán)鏈表結(jié)點(diǎn)
//接收要插入創(chuàng)建結(jié)點(diǎn)數(shù)據(jù)域的數(shù)據(jù)
//返回創(chuàng)建結(jié)點(diǎn)的地址
LTNode* BuyLTNode(LTDataType x);

//雙向鏈表初始化--帶頭雙向循環(huán)鏈表初始化函數(shù)
//返回初始化結(jié)點(diǎn)的地址
LTNode* LTInit();

//打印鏈表--打印雙向鏈表各結(jié)點(diǎn)數(shù)據(jù)域數(shù)據(jù)
//接收鏈表頭指針（phead）
LTNode* LTPrint(LTNode* phead);

//雙向鏈表尾插函數(shù)--向鏈表尾部插入一個(gè)結(jié)點(diǎn)（尾插）:
//接收鏈表頭指針（phead）、要尾插進(jìn)鏈表的值（x）
void LTPushBack(LTNode* phead, LTDataType x);

//雙向鏈表尾刪函數(shù)--刪除鏈表尾部結(jié)點(diǎn)（尾刪）
//接收鏈表頭指針（phead）
void LTPopBack(LTNode* phead);

//雙向鏈表頭插函數(shù)--向鏈表頭部插入一個(gè)結(jié)點(diǎn)（頭插）:
//接收鏈表頭指針（phead）、要頭插進(jìn)鏈表的值（x）
void LTPushFront(LTNode* phead, LTDataType x);

//雙向鏈表頭刪函數(shù)--刪除鏈表頭部結(jié)點(diǎn)（頭刪）
//接收鏈表頭指針（phead）
void LTPopFront(LTNode* phead);

//求鏈表結(jié)點(diǎn)個(gè)數(shù)函數(shù)--求鏈表有效結(jié)點(diǎn)個(gè)數(shù)（求鏈表長度）
//接收鏈表頭指針（phead）
int LTSize(LTNode* phead);

//雙向鏈表查找函數(shù)--在雙向鏈表中查找數(shù)據(jù)域數(shù)據(jù)為x的結(jié)點(diǎn)地址
//接收鏈表頭指針（phead）、要在鏈表中查找的值（x）
LTNode* LTFind(LTNode* phead, LTDataType x);

//雙向鏈表插入函數(shù)--在pos結(jié)點(diǎn)之前插入數(shù)據(jù)域數(shù)據(jù)為x的結(jié)點(diǎn)
//接收插入位置(pos)、要插入鏈表的值（x）
void LTInsert(LTNode* pos, LTDataType x);

//雙向鏈表刪除函數(shù)--刪除pos結(jié)點(diǎn)
//接收要?jiǎng)h除結(jié)點(diǎn)地址（pos）
void LTErase(LTNode* pos);

//雙向鏈表銷毀函數(shù)--銷毀鏈表
//接收要銷毀鏈表頭系欸但（phead）
void LTDestroy(LTNode* phead);

? ? ? ? ? ??

---------------------------------------------------------------------------------------------

? ? ? ? ? ? ? ??文章來源地址http://www.zghlxwxcb.cn/news/detail-716643.html

List.c?-- 雙向鏈表函數(shù)實(shí)現(xiàn)文件

#define _CRT_SECURE_NO_WARNINGS 1

//雙向鏈表函數(shù)實(shí)現(xiàn)文件：

//包含雙向鏈表頭文件：
#include "List.h"

//函數(shù)實(shí)現(xiàn)：

//創(chuàng)建鏈表結(jié)點(diǎn)--創(chuàng)建雙向循環(huán)鏈表結(jié)點(diǎn)
//接收要插入創(chuàng)建結(jié)點(diǎn)數(shù)據(jù)域的數(shù)據(jù)
LTNode* BuyLTNode(LTDataType x)
{
	//為創(chuàng)建結(jié)點(diǎn)開辟動(dòng)態(tài)空間：
	LTNode* node = (LTNode*)malloc(sizeof(LTNode));
	//檢查是否開辟失?。?	if (node == NULL)
		//返回NULL，開辟失敗
	{
		//打印錯(cuò)誤信息：
		perror("malloc fail");
		//終止程序：
		exit(-1);
	}

	//把x放入結(jié)點(diǎn)數(shù)據(jù)域：
	node->data = x;
	//設(shè)置雙向鏈表指針域：
	node->next = NULL;
	node->prev = NULL;
	
	//開辟成功則返回開辟空間地址
	return node;
}



//鏈表初始化--帶頭雙向循環(huán)鏈表初始化函數(shù)
//接收鏈表頭指針（phead）
LTNode* LTInit()
{
	//初始化時(shí)先使用BuyLTNode函數(shù)創(chuàng)建哨兵位：
	LTNode* phead = BuyLTNode(-1); //返回哨兵位指針

	//因?yàn)橐獙?shí)現(xiàn)循環(huán)，
	//所以讓哨兵位后繼指針next和前驅(qū)指針prev都指向自己：
	phead->next = phead;
	phead->prev = phead;
	//這樣即使鏈表為空，它也是有頭有尾的，即哨兵位phead

	//初始化后返回鏈表哨兵位：
	return phead;
}



//打印鏈表--打印雙向鏈表各結(jié)點(diǎn)數(shù)據(jù)域數(shù)據(jù)
//接收鏈表頭指針（phead）
LTNode* LTPrint(LTNode* phead)
{
	//assert斷言頭指針（哨兵位地址）不為空:
	assert(phead != NULL);

	//創(chuàng)建結(jié)點(diǎn)指針cur進(jìn)行遍歷：
	//指針cur應(yīng)該從哨兵位（頭指針）下一個(gè)結(jié)點(diǎn)開始
	LTNode* cur = phead->next;
	
	printf("phead <==> ");
	//因?yàn)槭茄h(huán)鏈表，不是以NULL空指針結(jié)尾
	//所以應(yīng)該是當(dāng)指針cur遍歷回到哨兵位就終止遍歷：
	while (cur != phead)
	//如果只用哨兵位，鏈表為空，
	//phead->next還是phead，不會(huì)進(jìn)行打印
	{
		//打印數(shù)據(jù)域內(nèi)容：
		printf("%d <=> ", cur->data);

		//打印完當(dāng)前結(jié)點(diǎn)數(shù)據(jù)域數(shù)據(jù)后cur移向下個(gè)結(jié)點(diǎn)：
		cur = cur->next;
	}

	//打印完一個(gè)鏈表后換行：
	printf("\n");
}



//向鏈表尾部插入一個(gè)結(jié)點(diǎn)（尾插）:
//接收結(jié)點(diǎn)頭指針（phead）、要尾插進(jìn)鏈表的值（x）
void LTPushBack(LTNode* phead, LTDataType x)
{
	//assert斷言頭指針（哨兵位地址）不為空:
	assert(phead != NULL);

	//通過哨兵位找到尾結(jié)點(diǎn)：
	//因?yàn)槭茄h(huán)鏈表：
	//所以哨兵位（帶頭鏈表）的前一個(gè)結(jié)點(diǎn)就是尾結(jié)點(diǎn)
	LTNode* tail = phead->prev; 
	//調(diào)用前驅(qū)指針獲得尾結(jié)點(diǎn)

	//調(diào)用BuyLTNode函數(shù)為尾插創(chuàng)建尾插結(jié)點(diǎn)newnode：
	LTNode* newnode = BuyLTNode(x);

	//尾插結(jié)點(diǎn)前驅(qū)指針prev指向原本的尾結(jié)點(diǎn)：
	newnode->prev = tail;
	//原本尾結(jié)點(diǎn)后繼指針next指向尾插結(jié)點(diǎn)：
	tail->next = newnode;

	//尾插結(jié)點(diǎn)后繼指針next指向頭結(jié)點(diǎn)：
	newnode->next = phead;
	//頭結(jié)點(diǎn)前驅(qū)指針指向尾插結(jié)點(diǎn)：
	phead->prev = newnode;

	//帶頭+雙向+循環(huán) 鏈表:
	//對比單鏈表，因?yàn)橛猩诒徊挥每紤]鏈表為空的情況，
	//且不需要二級指針，通過操縱哨兵位這個(gè)結(jié)構(gòu)體，
	//替換用二級指針操作頭指針的操作


	/*
	//第二種方法：復(fù)用LTInsert函數(shù)
	//在哨兵位前插入一個(gè)值x就是尾插了：
	LTInsert(phead, x);
	*/
}



//雙向鏈表尾刪函數(shù)--刪除鏈表尾部結(jié)點(diǎn)（尾刪）
//接收鏈表頭指針（phead）
void LTPopBack(LTNode* phead)
{
	//assert斷言頭指針（哨兵位地址）不為空:
	assert(phead != NULL);
	
	//assert斷言雙向鏈表不是空鏈表：
	assert(phead->next != phead);
	//如果哨兵位的下一個(gè)結(jié)點(diǎn)還是哨兵位說明是空鏈表

	//通過哨兵位的前驅(qū)指針prev獲得尾結(jié)點(diǎn)tail：
	LTNode* tail = phead->prev;

	//再通過尾結(jié)點(diǎn)tail獲得倒數(shù)第二個(gè)結(jié)點(diǎn)tailPrev：
	LTNode* tailPrev = tail->prev;

	//釋放（刪除）尾結(jié)點(diǎn)tail：
	free(tail);

	//這時(shí)就讓倒數(shù)第二個(gè)結(jié)點(diǎn)tailPrev成為新的尾結(jié)點(diǎn)
	//為保持循環(huán)，把tailPrev和哨兵位連接起來：
	tailPrev->next = phead; //tailPrev后繼指針指向哨兵位
	phead->prev = tailPrev; //哨兵位前驅(qū)指針指向tailPrev

	//帶頭+雙向+循環(huán) 鏈表:
	//對比單鏈表，這里雙向鏈表在尾刪時(shí)因?yàn)橛猩诒坏拇嬖?	//即使鏈表只剩一個(gè)結(jié)點(diǎn)，也不用進(jìn)行判斷單獨(dú)處理進(jìn)行置空
	//這一個(gè)結(jié)點(diǎn)刪掉后，還有哨兵位存在

	/*
	//第二種方法：復(fù)用LTErase函數(shù)
	//傳尾結(jié)點(diǎn)地址給LTErase函數(shù)即可：
	LTErase(phead->prev);
	*/
}



//雙向鏈表頭插函數(shù)--向鏈表頭部插入一個(gè)結(jié)點(diǎn)（頭插）：
//接收鏈表頭指針（phead）、要頭插進(jìn)鏈表的值（x）
void LTPushFront(LTNode* phead, LTDataType x)
{
	//第二種方法：多定義一個(gè)指針
	
	//assert斷言頭指針（哨兵位地址）不為空:
	assert(phead != NULL);

	//調(diào)用BuyLTNode函數(shù)為頭插創(chuàng)建頭插結(jié)點(diǎn)newnode：
	LTNode* newnode = BuyLTNode(x);

	//創(chuàng)建一個(gè)first指針保存原本第一個(gè)結(jié)點(diǎn)地址：
	LTNode* first = phead->next;

	//哨兵位后繼指針next指向頭插結(jié)點(diǎn)newnode：
	phead->next = newnode;

	//頭插結(jié)點(diǎn)newnode前驅(qū)指針prev指向哨兵位：
	newnode->prev = phead;

	//頭插結(jié)點(diǎn)newnode后繼指針next指向原本頭結(jié)點(diǎn)first:
	newnode->next = first;

	//原本頭結(jié)點(diǎn)first前驅(qū)指針prev指向頭插結(jié)點(diǎn)newnode：
	first->prev = newnode;


	/*
	//assert斷言頭指針（哨兵位地址）不為空:
	assert(phead != NULL);
	
	//第一種方法：需要注意連接的順序
	
	//調(diào)用BuyLTNode函數(shù)為頭插創(chuàng)建頭插結(jié)點(diǎn)newnode：
	LTNode* newnode = BuyLTNode(x);
	
	//先將頭插結(jié)點(diǎn)的后繼節(jié)點(diǎn)next連接上原本頭結(jié)點(diǎn)：
	newnode->next = phead->next;
	//哨兵位的后繼指針指向的就是頭結(jié)點(diǎn)
	
	//再將原本頭結(jié)點(diǎn)的前驅(qū)指針prev指向頭插結(jié)點(diǎn)newnode：
	phead->next->prev = newnode;
	
	//哨兵位連接上頭插節(jié)點(diǎn)newnode：
	phead->next = newnode;
	
	//頭插結(jié)點(diǎn)newnode的前驅(qū)指針指向哨兵位：
	newnode->prev = phead;
	*/


	/*
	//第三種方法：復(fù)用LTInsert函數(shù)
	//在哨兵位后一個(gè)結(jié)點(diǎn)前插入一個(gè)值x就是頭插了：
	LTInsert(phead->next, x);
	*/
}



//雙向鏈表頭刪函數(shù)--刪除鏈表頭部結(jié)點(diǎn)（頭刪）
//接收鏈表頭指針（phead）
void LTPopFront(LTNode* phead)
{
	//assert斷言頭指針（哨兵位地址）不為空:
	assert(phead != NULL);

	//assert斷言雙向鏈表不是空鏈表：
	assert(phead->next != phead);
	//如果哨兵位的下一個(gè)結(jié)點(diǎn)還是哨兵位說明是空鏈表

	//通過哨兵位后繼結(jié)點(diǎn)next獲得頭結(jié)點(diǎn)地址：
	LTNode* first = phead->next;

	//再通過first結(jié)點(diǎn)獲得第二個(gè)結(jié)點(diǎn)：
	LTNode* second = first->next;

	//釋放頭結(jié)點(diǎn)first：
	free(first);

	//讓哨兵位后繼結(jié)點(diǎn)next指向第二個(gè)結(jié)點(diǎn)second：
	phead->next = second;

	//第二個(gè)結(jié)點(diǎn)的前驅(qū)指針prev指向哨兵位：
	second->prev = phead;

	//帶頭+雙向+循環(huán) 鏈表:
	//對比單鏈表，這里雙向鏈表在頭刪時(shí)因?yàn)橛猩诒坏拇嬖?	//即使鏈表只剩一個(gè)結(jié)點(diǎn)，也不用進(jìn)行判斷單獨(dú)處理進(jìn)行置空
	//這一個(gè)結(jié)點(diǎn)刪掉后，還有哨兵位存在
	
	/*
	//第二種方法：復(fù)用LTErase函數(shù)
	//傳第一個(gè)結(jié)點(diǎn)地址給LTErase函數(shù)即可：
	LTErase(phead->next);
	*/
}



//求鏈表結(jié)點(diǎn)個(gè)數(shù)函數(shù)
//接收鏈表頭指針（phead）
int LTSize(LTNode* phead)
{
	//assert斷言頭指針（哨兵位地址）不為空:
	assert(phead != NULL);

	int size = 0; //存放鏈表長度

	//創(chuàng)建結(jié)點(diǎn)指針cur進(jìn)行遍歷：
	//指針cur應(yīng)該從哨兵位（頭指針）下一個(gè)結(jié)點(diǎn)開始
	LTNode* cur = phead->next;

	//因?yàn)槭茄h(huán)鏈表，不是以NULL空指針結(jié)尾
	//所以應(yīng)該是當(dāng)指針cur遍歷回到哨兵位就終止遍歷：
	while (cur != phead)
		//如果只有哨兵位，鏈表為空，
		//phead->next還是phead，不會(huì)進(jìn)行打印
	{
		++size; //遍歷一遍長度+1

		//cur移向下個(gè)結(jié)點(diǎn)：
		cur = cur->next;
	}

	//返回鏈表長度：
	return size;
}



//雙向鏈表查找函數(shù)--在雙向鏈表中查找數(shù)據(jù)域數(shù)據(jù)為x的結(jié)點(diǎn)地址
//接收鏈表頭指針（phead）、要在鏈表中查找的值（x）
LTNode* LTFind(LTNode* phead, LTDataType x)
{
	//assert斷言頭指針（哨兵位地址）不為空:
	assert(phead != NULL);

	//創(chuàng)建遍歷指針cur，從第一個(gè)結(jié)點(diǎn)開始：
	LTNode* cur = phead->next;

	//使用while循環(huán)進(jìn)行遍歷：
	while (cur != phead)
		//如果只有哨兵位，鏈表為空，
		//phead->next還是phead，不會(huì)進(jìn)行打印
	{
		if (cur->data == x)
			//找到要找的值了：
		{
			return cur; //返回該值結(jié)點(diǎn)
		}

		//調(diào)整指針：
		cur = cur->next;
	}

	//未找到則返回空指針：
	return NULL;
}



//雙向鏈表插入函數(shù)--在pos結(jié)點(diǎn)之前插入數(shù)據(jù)域數(shù)據(jù)為x的結(jié)點(diǎn)
//接收插入位置(pos)、要插入鏈表的值（x）
void LTInsert(LTNode* pos, LTDataType x)
{
	//assert斷言插入位置pos不為空：
	assert(pos != NULL);

	//通過pos結(jié)點(diǎn)獲得前一個(gè)結(jié)點(diǎn)posPrev地址：
	LTNode* posPrev = pos->prev;

	//使用BuyLTNode函數(shù)為插入結(jié)點(diǎn)開辟空間：
	LTNode* newnode = BuyLTNode(x);

	//posPrev結(jié)點(diǎn)的后繼指針next指向newnode：
	posPrev->next = newnode;

	//newnode前驅(qū)指針prev指向posPrev:
	newnode->prev = posPrev;

	//newnode后繼指針next指向pos：
	newnode->next = pos;

	//pos結(jié)點(diǎn)前驅(qū)指針prev指向newnode:
	pos->prev = newnode;
}



//雙向鏈表刪除函數(shù)--刪除pos結(jié)點(diǎn)
//接收要?jiǎng)h除結(jié)點(diǎn)地址（pos）
void LTErase(LTNode* pos)
{
	//assert斷言刪除位置結(jié)點(diǎn)pos不為空：
	assert(pos != NULL);

	//保存要?jiǎng)h除結(jié)點(diǎn)pos的前一個(gè)結(jié)點(diǎn)posPrev地址：
	LTNode* posPrev = pos->prev;

	//保存要?jiǎng)h除結(jié)點(diǎn)pos的后一個(gè)結(jié)點(diǎn)posNext地址：
	LTNode* posNext = pos->next;

	//釋放掉pos結(jié)點(diǎn)：
	free(pos);

	//將pos前結(jié)點(diǎn)posPrev的后繼指針指向posNext：
	posPrev->next = posNext;

	//將pos后結(jié)點(diǎn)posNext的前驅(qū)指針指向posPrev：
	posNext->prev = posPrev;
}



//雙向鏈表銷毀函數(shù)--銷毀鏈表
//接收要銷毀鏈表頭系欸但（phead）
void LTDestroy(LTNode* phead)
{
	//assert斷言頭指針（哨兵位地址）不為空:
	assert(phead != NULL);

	//創(chuàng)建遍歷指針cur，從第一個(gè)結(jié)點(diǎn)開始：
	LTNode* cur = phead->next;

	//使用while循環(huán)進(jìn)行遍歷釋放：
	while (cur != phead)
	{
		//釋放前先存儲(chǔ)下一個(gè)結(jié)點(diǎn)地址：
		LTNode* next = cur->next;

		//釋放當(dāng)前結(jié)點(diǎn)：
		free(cur);

		//調(diào)整指針：
		cur = next;
	}
	
	//刪除完有效結(jié)點(diǎn)后，最后再釋放哨兵位：
	free(phead);
}

? ? ? ? ? ??

---------------------------------------------------------------------------------------------

? ? ? ? ? ? ? ??

Test.c?-- 雙向鏈表測試文件

#define _CRT_SECURE_NO_WARNINGS 1

//雙向鏈表函數(shù)測試文件：

//包含雙向鏈表頭文件：
#include "List.h"

//測試函數(shù)--
//LTInit、LTPushBack、LTPrintf函數(shù)
void TestList1()
{
	//初始化一個(gè)雙向鏈表：
	LTNode* plist = LTInit();

	//初始化后使用尾插函數(shù)插入數(shù)據(jù)：
	LTPushBack(plist, 1);
	LTPushBack(plist, 2);
	LTPushBack(plist, 3);
	LTPushBack(plist, 4);
	LTPushBack(plist, 5);
	  
	//打印當(dāng)前雙向鏈表：
	LTPrint(plist);
}


//測試函數(shù)--LTPopBack函數(shù)
void TestList2()
{
	//初始化一個(gè)雙向鏈表：
	LTNode* plist = LTInit();
	//初始化后使用尾插函數(shù)插入數(shù)據(jù)：
	LTPushBack(plist, 1);
	LTPushBack(plist, 2);
	LTPushBack(plist, 3);
	//打印當(dāng)前雙向鏈表：
	LTPrint(plist);

	//進(jìn)行尾刪：
	LTPopBack(plist);
	//打印當(dāng)前雙向鏈表：
	LTPrint(plist);

	//進(jìn)行尾刪：
	LTPopBack(plist);
	//打印當(dāng)前雙向鏈表：
	LTPrint(plist);

	//進(jìn)行尾刪：
	LTPopBack(plist);
	//打印當(dāng)前雙向鏈表：
	LTPrint(plist);
}


//測試函數(shù)--LTPushFront函數(shù)
void TestList3()
{
	//初始化一個(gè)雙向鏈表：
	LTNode* plist = LTInit();
	//初始化后使用尾插函數(shù)插入數(shù)據(jù)：
	LTPushBack(plist, 1);
	LTPushBack(plist, 2);
	LTPushBack(plist, 3);
	//打印當(dāng)前雙向鏈表：
	LTPrint(plist);

	//進(jìn)行頭插：
	LTPushFront(plist, 1000);
	//打印當(dāng)前雙向鏈表：
	LTPrint(plist);
}


//測試函數(shù)--LTPopFront函數(shù)
void TestList4()
{
	//初始化一個(gè)雙向鏈表：
	LTNode* plist = LTInit();
	//初始化后使用尾插函數(shù)插入數(shù)據(jù)：
	LTPushBack(plist, 1);
	LTPushBack(plist, 2);
	LTPushBack(plist, 3);
	//打印當(dāng)前雙向鏈表：
	LTPrint(plist);

	//進(jìn)行頭刪：
	LTPopFront(plist);
	//打印當(dāng)前雙向鏈表：
	LTPrint(plist);
}


//測試函數(shù)--LTSize函數(shù)
void TestList5()
{
	//初始化一個(gè)雙向鏈表：
	LTNode* plist = LTInit();
	//初始化后使用尾插函數(shù)插入數(shù)據(jù)：
	LTPushBack(plist, 1);
	LTPushBack(plist, 2);
	LTPushBack(plist, 3);
	//打印當(dāng)前雙向鏈表：
	LTPrint(plist);

	//計(jì)算鏈表長度：
	int size = LTSize(plist);
	//打印當(dāng)前雙向鏈表：
	printf("鏈表長度為：%d", size);
}


//測試函數(shù)--LTFind函數(shù)
void TestList6()
{
	//初始化一個(gè)雙向鏈表：
	LTNode* plist = LTInit();
	//初始化后使用尾插函數(shù)插入數(shù)據(jù)：
	LTPushBack(plist, 1);
	LTPushBack(plist, 2);
	LTPushBack(plist, 3);
	//打印當(dāng)前雙向鏈表：
	LTPrint(plist);

	//使用查找函數(shù)：
	LTNode* find = LTFind(plist, 2);
	//打印找到的地址
	printf("0x%xn", find);
}


//測試函數(shù)--LTInsert函數(shù)
void TestList7()
{
	//初始化一個(gè)雙向鏈表：
	LTNode* plist = LTInit();
	//初始化后使用尾插函數(shù)插入數(shù)據(jù)：
	LTPushBack(plist, 1);
	LTPushBack(plist, 2);
	LTPushBack(plist, 3);
	//打印當(dāng)前雙向鏈表：
	LTPrint(plist);

	//使用插入函數(shù)：
	LTInsert(plist->next->next, 100);
	//打印當(dāng)前雙向鏈表：
	LTPrint(plist);
}


//測試函數(shù)--LTErase函數(shù)
void TestList8()
{
	//初始化一個(gè)雙向鏈表：
	LTNode* plist = LTInit();
	//初始化后使用尾插函數(shù)插入數(shù)據(jù)：
	LTPushBack(plist, 1);
	LTPushBack(plist, 2);
	LTPushBack(plist, 3);
	//打印當(dāng)前雙向鏈表：
	LTPrint(plist);

	//使用刪除函數(shù)：
	LTErase(plist->next->next);
	//打印當(dāng)前雙向鏈表：
	LTPrint(plist);
}

//主函數(shù)：
int main()
{
	//調(diào)用測試函數(shù)：
	//TestList1();
	//TestList2();
	//TestList3();
	//TestList4();
	//TestList5();
	//TestList6();
	//TestList7();
	TestList8();

	return 0;
}

到了這里，關(guān)于【數(shù)據(jù)結(jié)構(gòu)初階】四、線性表里的鏈表（帶頭+雙向+循環(huán) 鏈表 -- C語言實(shí)現(xiàn)）的文章就介紹完了。如果您還想了解更多內(nèi)容，請?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！