国产 无码 综合区,色欲AV无码国产永久播放,无码天堂亚洲国产AV,国产日韩欧美女同一区二区

【數(shù)據(jù)結(jié)構(gòu)】雙向鏈表 超詳細 (含:何時用一級指針或二級指針;指針域的指針是否要釋放)

這篇具有很好參考價值的文章主要介紹了【數(shù)據(jù)結(jié)構(gòu)】雙向鏈表 超詳細 (含:何時用一級指針或二級指針;指針域的指針是否要釋放)。希望對大家有所幫助。如果存在錯誤或未考慮完全的地方,請大家不吝賜教,您也可以點擊"舉報違法"按鈕提交疑問。

目錄

一、簡介

二. 雙鏈表的實現(xiàn)

1.準備工作及其注意事項

1.1 先創(chuàng)建三個文件

1.2 注意事項:幫助高效記憶

1.3? ?關(guān)于什么時候 用 一級指針接收,什么時候用 二級指針接收?

1.4 釋放節(jié)點時,要將節(jié)點地址 置為NULL,難道 節(jié)點內(nèi)部的 指針域的指針 就不用置為 NULL嗎??

2.雙鏈表的基本功能接口

2.1?初始化哨兵位

?2.2 鏈表的創(chuàng)建新節(jié)點接口

2.3?打印

3. 插入 接口

3.1 尾插法

3.2 頭插法

3.3?在 pos 位置之后插入數(shù)據(jù)

4. 查找

5.刪除? 接口

5.1 尾刪法

5.2?頭刪法

5.3??刪除 pos 位置的數(shù)據(jù)

6. 銷毀鏈表 接口

6.1?二級指針版?

6.2?一級指針版

7. 總代碼概覽

List.h

List.c

test.c

三. 順序表和雙向鏈表的優(yōu)缺點分析


二級指針和雙向鏈表,c語言,visualstudio,數(shù)據(jù)結(jié)構(gòu),鏈表


一、簡介

? ? ? ? 單向鏈表在解決那些需要大量查找前趨節(jié)點的問題時,效率較為低下,因為單向鏈表適合“從前往后”查找,并不適合“從后往前”查找。

(若想要看 單鏈表,可以點擊跳轉(zhuǎn):【數(shù)據(jù)結(jié)構(gòu)】單向鏈表實現(xiàn) 超詳細)

如果要提高鏈表的查找效率,那??雙向鏈表(雙鏈表)無疑是首選。

雙向鏈表:即為 字面上的意思是“雙向”的鏈表,如下圖所示。

二級指針和雙向鏈表,c語言,visualstudio,數(shù)據(jù)結(jié)構(gòu),鏈表?
? ? ? ?

  • 雙向 指各個節(jié)點之間的邏輯關(guān)系是 雙向的,該鏈表通常 有一個頭節(jié)點 -- 稱為 哨兵位
  • 概念:?當鏈表中只有哨兵位節(jié)點的時候,我們稱該鏈表為空鏈表,即哨兵位是不能刪除的
  • 從上圖還可以看出,雙向鏈表中每個節(jié)點包括一下3個部分,分別是:
  • 指針域(前驅(qū)節(jié)點 prev )、
  • 數(shù)據(jù)域(用于存儲數(shù)據(jù)元素 data)
  • 指針域(后繼節(jié)點 next)。

二. 雙鏈表的實現(xiàn)

1.準備工作及其注意事項

1.1 先創(chuàng)建三個文件

二級指針和雙向鏈表,c語言,visualstudio,數(shù)據(jù)結(jié)構(gòu),鏈表?

?解釋這三個文件的作用
?1、頭文件List.h ?是來聲明接口函數(shù),定義鏈表,將幾個公共用到的庫函數(shù)集合起來
?2、源文件List.c ?是用來具體實現(xiàn)接口
?3、源文件test.c ?用于接口的測試工作 ,即具體的使用場景

1.2 注意事項:幫助高效記憶

1.?傳遞指針,都要斷言 不能為 NULL ,指針不能為空:assert(phead);
2. 存在?關(guān)系到? 前趨節(jié)點prev 或 后繼節(jié)點next? 的 情況,

? ? 可以 直接定義變量 Prev = .... Next = ....? ?便于 理清思路,不易亂
3. 所有的 刪除接口 都需要 斷言鏈表不能只有 哨兵位: assert(phead->next != phead);?
4. 尾刪法: 記得雙鏈表的找尾 不像 單鏈表需要循環(huán)去找尾??!ptail = phead->prev;

5. 初始化創(chuàng)建頭節(jié)點:推薦使用 調(diào)用 創(chuàng)建節(jié)點接口? 的 方法
5. 銷毀接口:推薦使用 傳一級指針的方法

1.3? ?關(guān)于什么時候 用 一級指針接收,什么時候用 二級指針接收?(不看水話,可以直接 看下面?總結(jié) 部分

(有點水話,實在不明白思路的可以看一下詳細解說的 ”水話“)

? ? ? ? ?在 單向鏈表 中,有一個指向 第一個節(jié)點的指針 plist,由于 頭插法等操作,可能會改變 第一個節(jié)點,則 plist 要對應進行 更新,而 要想直接改變一個變量(plist是指針變量)的值,需要傳地址,plist 的 &plist 是 一級指針的地址,就要用 二級指針 來接收

? ? ? ? ?在 雙向鏈表 中,存在 頭節(jié)點 head ,即 哨兵位,哨兵是 不用進行 改變本身這個節(jié)點的 地址的??!

那就有鐵鐵要問了,不是還要改變?頭節(jié)點 head(?哨兵位 ) 的指向,要指向 第一個 節(jié)點 或 尾節(jié)點 嗎??

回答:因為 我們 要改變的 是 雙鏈表節(jié)點 結(jié)構(gòu)?中 的 結(jié)構(gòu)體成員變量prev 和 next ,改變 結(jié)構(gòu)體的成員變量?只需要利用 結(jié)構(gòu)體指針 p->prev = .... 或 p->next? ?= .... 就達到 修改 雙鏈表節(jié)點指向 問題了,而你本身并不需要改變 一個節(jié)點的地址 p

總結(jié)?

總結(jié):修改?雙鏈表節(jié)點 的指向,是通過? 修改節(jié)點結(jié)構(gòu)體內(nèi)部的 兩個成員變量 來實現(xiàn)的只需要用到 結(jié)構(gòu)體指針(即該節(jié)點的地址 p),找到? 兩個成員變量,即可完成修改,因而傳遞 一級指針就好,不用像 單鏈表那樣還要 傳遞 一級指針的 地址

1.4 釋放節(jié)點時,要將節(jié)點地址 置為NULL,難道 節(jié)點內(nèi)部的 指針域的指針 就不用置為 NULL嗎??

回答:不用 因為節(jié)點的空間已經(jīng)還給操作系統(tǒng)了 那個指針域的指針所占據(jù)的空間也還回去了 操作系統(tǒng)后續(xù)分配內(nèi)存就會把那塊空間覆蓋掉 就不會又啥影響

2.雙鏈表的基本功能接口

2.1?初始化哨兵位

初始化哨兵位 第一種方法:傳入 指針,進行"加工" 成 哨兵位

// 初始化一個哨兵位:
void LTInit(LTNode** pphead)
{
	*pphead = (LTNode*)malloc(sizeof(LTNode));
	// 開辟空間是否成功的判斷:一般malloc不會失敗,失敗證明內(nèi)存不夠了,寫下面的證明算是好習慣,不寫一般沒問題
	if (*pphead == NULL) {
		perror("malloc fail!");
		exit(1);
	}
	(*pphead)->data = -1;
	(*pphead)->next = (*pphead)->prev = *pphead; // 哨兵位初識化,兩個指針都指向自己
}

初始化哨兵位第二種方法:直接一個函數(shù)生成一個哨兵位,返回哨兵位就好,不用傳指針

LTNode* LTInit()
{
	LTNode* phead = (LTNode*)malloc(sizeof(LTNode));
	// 開辟空間是否成功的判斷
	if (phead == NULL) {
		perror("malloc fail!");
		exit(1);
	}
	phead->data = -1; // data 隨便定,反正哨兵位data無效
	phead->next = phead->prev = phead;
	return phead;
}

初始化哨兵位 第二種方法的2.0 版本:因為哨兵位的初始化 和 2.2 創(chuàng)建新新節(jié)點的方法一樣,可以合并調(diào)用


LTNode* LTInit_2()
{
	LTNode* phead = LTCreatNode(-1);
	return phead;
}

?2.2 鏈表的創(chuàng)建新節(jié)點接口

// 創(chuàng)建新節(jié)點
LTNode* LTCreatNode(LTDataType x)
{
	LTNode* newNode = (LTNode*)malloc(sizeof (LTNode));
	if (newNode == NULL)
	{
		perror("malloc fail!");
		exit(1);
	}
	newNode->data = x;
	newNode->prev = newNode->next = newNode; // 都是 指向自己
	return newNode;
}

2.3?打印

雙鏈表的打印
和 單鏈表打印一樣,都需要循環(huán),但是結(jié)束條件不一樣
單鏈表以 pcur = NULL 為結(jié)束條件,雙鏈表是 一種循環(huán)鏈表,頭尾相連,不會有 ?pcur = NULL 的情況
正解:既然 哨兵位無有效數(shù)據(jù),同時 循環(huán)一輪 還是 回到頭(哨兵位),干脆:while (pcur != phead)


void LTPrint(LTNode* phead)
{
	assert(phead);// 哨兵位不能為空
	LTNode* pcur = phead->next;
	while (pcur != phead)
	{
		printf("%d -> ", pcur->data);
		pcur = pcur->next;
	}
	printf("\n");
}

3. 插入 接口

前言:

// 不需要改變哨兵位,則不需要傳二級指針
// 如果需要修改哨兵位的話,則傳二級指針

3.1 尾插法

二級指針和雙向鏈表,c語言,visualstudio,數(shù)據(jù)結(jié)構(gòu),鏈表?二級指針和雙向鏈表,c語言,visualstudio,數(shù)據(jù)結(jié)構(gòu),鏈表?

雙鏈表的 尾插法
雙向鏈表尾插需不需要找尾的操作 ?

不需要 :ptail = head->prev; ?注意這個 等價關(guān)系,便于理解下面的代碼
尾插法 也稱作 在哨兵位之前插入節(jié)點/最后一個有效節(jié)點之后插入數(shù)據(jù)

void LTPushBack(LTNode* phead, LTDataType x)
{
	assert(phead);// 哨兵位不能為空
	LTNode* newNode = LTCreatNode(x); 
	LTNode* ptail = phead->prev;
	// 三者關(guān)系:phead->prev(即ptail)    newNode      phead
	// 處理順序:先 newNode,  再 phead->prev(即ptail) ,最后  phead:否則會亂套
	// 先 newNode
	newNode->next = phead;
	newNode->prev = ptail; // 就是  phead->prev
	// 再尾節(jié)點 ptail = head->prev  ;   ptail  -> next = head-> prev -> next;
	ptail->next = newNode;
	// 最后頭節(jié)點 
	phead->prev = newNode; 
}

3.2 頭插法

雙鏈表的 頭插法
注意:頭插 是在第一個有效位置進行插入,不是在哨兵位 前面,由于 雙鏈表的循環(huán)成環(huán)狀的特性,若在哨兵位前面,就是尾插了

二級指針和雙向鏈表,c語言,visualstudio,數(shù)據(jù)結(jié)構(gòu),鏈表二級指針和雙向鏈表,c語言,visualstudio,數(shù)據(jù)結(jié)構(gòu),鏈表?

void LTPushFront(LTNode* phead, LTDataType x)
{
	assert(phead);
	LTNode* newNode = LTCreatNode(x);
	// 三者關(guān)系:phead   newNode   phead->next (即 第一個 有效節(jié)點,命名為Next) ;
	// 處理順序:先 newNode,  再 phead->next(即 第一個 有效節(jié)點,命名為Next) ,最后  phead:否則會亂套
	LTNode* Next = phead->next; // 這里就是定義了個變量,便于梳理
	// 先 newNode
	newNode->next = Next;
	newNode->prev = phead;
	// 再 phead->next(即 第一個 有效節(jié)點) 
	Next->prev = newNode;
	// 最后頭節(jié)點 
	phead->next = newNode;
}

3.3?在 pos 位置之后插入數(shù)據(jù)

在 pos 位置之后插入數(shù)據(jù):要配合? ?4.查找? ?接口實現(xiàn)

和 頭插法思路一樣:只是將 哨兵的帶頭作用 換成了 pos

pos 是通過  4.查找  的接口找的

void LTInsert(LTNode* pos, LTDataType x)
{
	assert(pos);
	// 先創(chuàng)建新節(jié)點
	LTNode* newNode = LTCreatNode(x);
	// 關(guān)系三個節(jié)點:pos     newNode    pos->next
	// 先處理newNode,后 pos->next , 最后 pos 
	// 注意三者的執(zhí)行順序 不能換!! 
	LTNode* Next = pos->next; // 這里將 pos 的下一個節(jié)點(pos->next) 命名成 Next (避免和 next 混淆)
	newNode->next = Next;
	newNode->prev = pos;
	Next->prev = newNode;
	pos->next = newNode;
}

4. 查找

LTNode* LTFind(LTNode* phead, LTDataType x)
{
	assert(phead);
	// 下面是遍歷 雙鏈表的模板操作
	LTNode* pcur = phead->next;
	while (pcur != phead)
	{
		if (pcur->data == x)
		{
			return pcur;
		}
		pcur = pcur->next;
	}
	return NULL;
}

5.刪除? 接口

5.1 尾刪法

// 思路:讓 倒數(shù)第二個 節(jié)點 next 指向 head ,head 指向 倒數(shù)第二個節(jié)點,最后 free 掉 ptail
// 尾節(jié)點前一個節(jié)點:ptail->prev = phead->prev->prev
// 尾節(jié)點:ptail = phead->prev
// "尾節(jié)點前一個節(jié)點" 指向 head哨兵位:ptail->prev->next = phead;
// head哨兵位 指向 "尾節(jié)點前一個節(jié)點" :phead->prev = ptail->prev;
// 最后 free 掉 ptail

二級指針和雙向鏈表,c語言,visualstudio,數(shù)據(jù)結(jié)構(gòu),鏈表?二級指針和雙向鏈表,c語言,visualstudio,數(shù)據(jù)結(jié)構(gòu),鏈表

// 尾刪
void LTPopBack(LTNode* phead)
{
	assert(phead);
	//鏈表為空:只有一個哨兵位節(jié)點
	assert(phead->next != phead);
	
	LTNode* ptail = phead->prev;
	ptail->prev->next = phead;
	phead->prev = ptail->prev; 
	free(ptail);
	ptail = NULL;
}

5.2?頭刪法

? ? //? 被刪除的 第一個有效節(jié)點:pFirst = phead->next;?

? ? // ?下一個節(jié)點 pSecond = pFirst->next;
?? ?//? 先 下一個節(jié)點 指向 head : pSecond->prev = phead;
?? ?//? 后 head 指向 下一個節(jié)點 :phead->next = pSecond;?
?? ?//? 注意:因為對于循環(huán)鏈表來說, 第一個節(jié)點的下個節(jié)點 也可以是 哨兵位,所以 只存在一個有效節(jié)點,也是可以直接刪除第一個節(jié)點的、

二級指針和雙向鏈表,c語言,visualstudio,數(shù)據(jù)結(jié)構(gòu),鏈表

二級指針和雙向鏈表,c語言,visualstudio,數(shù)據(jù)結(jié)構(gòu),鏈表

// 頭刪
// 刪除的是 第一個有效節(jié)點
void LTPopFront(LTNode* phead)
{
	assert(phead); // 地址不能為NULL
	assert(phead->next != phead); // 鏈表不能只有 哨兵位

	LTNode* pFirst = phead->next;  // 要被刪除的 第一個節(jié)點
	LTNode* pSecond = pFirst->next;
	pSecond->prev = phead;
	phead->next = pSecond;
	free(pFirst);
	pFirst = NULL;
}

5.3??刪除 pos 位置的數(shù)據(jù)

刪除 pos 位置的數(shù)據(jù):要配合? ?4.查找? ?接口實現(xiàn)

void LTErase(LTNode* pos)
{
?? ?assert(pos);
?? ?// 關(guān)系三個節(jié)點: pos->prev ? ? ?pos ? ? pos->next ? ??
?? ?LTNode* Prev = pos->prev; // ?pos 的前一個?
?? ?LTNode* Next = pos->next; // ?pos 的下一個
?? ?Next->prev = Prev;
?? ?Prev->next = Next;
?? ?free(pos);
?? ?pos = NULL;
}

6. 銷毀鏈表 接口

更推薦 一級指針版:手動置為NULL

為了保持 接口的一致性:不然前面接口都是 一級指針,到這里突然 二級指針,當程序交給用戶時,會增加記憶的成本

6.1?二級指針版?

// 思路:先將 有效節(jié)點刪除,后刪除哨兵位
// 刪除有效節(jié)點, 要將下個節(jié)點保存起來,不然找不到
// 注意:這里 最后需要 ? 改變 ?哨兵位 為NULL ,因而要傳遞地址,用二級指針接收
// 否則,傳值 只會影響 形參,哨兵位 需要手動 置為NULL


void LTDestory(LTNode** pphead) 
{
	assert(pphead);// 指針本身不能為 空
	assert(*pphead); // 哨兵位 不能為 空
	LTNode* pcur = (*pphead)->next; // *pphead = phead 即哨兵位 ;還有記得 加括號
	while (pcur != *pphead)
	{
		LTNode* next = pcur->next;
		free(pcur);
		pcur = next;
	}
	// 最后刪除 哨兵位
	free(*pphead);
	*pphead = NULL;
}

6.2?一級指針版

// 雙鏈表的 銷毀:一級指針版:哨兵位 需要 手動額外 置為空

void LTDestory(LTNode* phead)
{
?? ?assert(phead);// 哨兵位 不能為 空
?? ?LTNode* pcur = (phead)->next; // *pphead = phead 即哨兵位 ;還有記得 加括號
?? ?while (pcur != phead)
?? ?{
?? ??? ?LTNode* next = pcur->next;
?? ??? ?free(pcur);
?? ??? ?pcur = next;
?? ?}
?? ?// 最后釋放掉 形參的指針:這里不是釋放 哨兵位
?? ?free(phead);
?? ?phead = NULL;
}

7. 總代碼概覽

List.h

#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>

// 創(chuàng)建新節(jié)點
typedef int  LTDataType;
typedef struct LTistNode
{
	LTDataType data;
	struct LTistNode* prev;
	struct LTistNode* next;
}LTNode;

// 創(chuàng)建新節(jié)點
LTNode* LTCreatNode(LTDataType x);

// 初始化:生成哨兵位
LTNode* LTInit();

// 打印函數(shù)
void LTPrint(LTNode* phead);

// 尾插法
void LTPushBack(LTNode* phead, LTDataType x);

// 頭插法
void LTPushFront(LTNode* phead, LTDataType x);

// 在 pos 之后插入數(shù)據(jù)
void LTInsert(LTNode* pos, LTDataType x);

// 尾刪法
void LTPopBack(LTNode* phead);

// 頭刪法
void LTPopFront(LTNode* phead);

// 刪除 pos 位置節(jié)點
void LTErase(LTNode* pos);

// 查找
LTNode* LTFind(LTNode* phead, LTDataType x);

// 銷毀
void LTDestory(LTNode* phead);

List.c

#include"List.h"

// 創(chuàng)建新節(jié)點
LTNode* LTCreatNode(LTDataType x)
{
	LTNode* newNode = (LTNode*)malloc(sizeof(LTNode));
	if (newNode == NULL)
	{
		perror("malloc fail!");
		exit(1);
	}
	newNode->data = x;
	newNode->prev = newNode->next = newNode;
	return newNode;
}

// 初始化:生成哨兵位
LTNode* LTInit()
{
	LTNode* head = LTCreatNode(-1);
	return head;
}

// 打印函數(shù)
void LTPrint(LTNode* phead)
{
	assert(phead);
	LTNode* pcur = phead->next;
	while (pcur != phead)
	{
		printf("%d -> ", pcur->data);
		pcur = pcur->next;
	}
	printf("\n");
}

// 尾插法
void LTPushBack(LTNode* phead, LTDataType x)
{
	assert(phead);
	// 創(chuàng)建新節(jié)點
	LTNode* newNode = LTCreatNode(x);
	LTNode* ptail = phead->prev;
	// 三者關(guān)系:ptail   newNode   phead
	newNode->next = phead;
	newNode->prev = ptail;
	ptail->next = newNode;
	phead->prev = newNode;
}

// 頭插法
void LTPushFront(LTNode* phead, LTDataType x)
{
	assert(phead);
	// 創(chuàng)建新節(jié)點
	LTNode* newNode = LTCreatNode(x);
	// 三者關(guān)系:phead   newNode   phead->next (定為Next);
	LTNode* Next = phead->next; // 這里就是定義了個變量,便于梳理
	newNode->next = Next;
	newNode->prev = phead;
	Next->prev = newNode;
	phead->next = newNode;
}

// 查找
LTNode* LTFind(LTNode* phead, LTDataType x)
{
	assert(phead);
	LTNode* pcur = phead->next;
	while (pcur != phead)
	{
		if (pcur->data == x) return pcur;
		pcur = pcur->next;
	}
	return NULL;
}

// 在 pos 之后插入數(shù)據(jù):頭插法實現(xiàn)邏輯一樣
void LTInsert(LTNode* pos, LTDataType x)
{
	assert(pos);
	// 創(chuàng)建新節(jié)點
	LTNode* newNode = LTCreatNode(x);
	// 三者關(guān)系:pos   newNode   pso->next (定為Next);
	LTNode* Next = pos->next;
	newNode->next = Next;
	newNode->prev = pos;
	Next->prev = newNode;
	pos->next = newNode;
}

// 尾刪法:記得雙鏈表的找尾 不像 單鏈表需要循環(huán)去找尾
void LTPopBack(LTNode* phead)
{
	assert(phead);
	assert(phead->next != phead);// 鏈表不能只有 哨兵位 (刪除的接口 都要斷言這條)
	// 三者關(guān)系:ptail->prev   ptail   head
	LTNode* ptail = phead->prev;
	ptail->prev->next = phead;
	phead->prev = ptail->prev;
	free(ptail);
	ptail = NULL;

}

// 頭刪法
void LTPopFront(LTNode* phead)
{
	assert(phead);
	assert(phead->next != phead); // 鏈表不能只有 哨兵位 (刪除的接口 都要斷言這條)
	// 三者關(guān)系:phead    phead->next    phead->next->next(命名為pSecond)
	LTNode* pFirst = phead->next;  // 要被刪除的 第一個節(jié)點  一定要先保存下來!!
	LTNode* pSecond = pFirst->next;
	pSecond->prev = phead;
	phead->next = pSecond;
	free(pFirst);
	pFirst = NULL;
}

// 刪除 pos 位置節(jié)點
void LTErase(LTNode* pos)
{
	assert(pos);
	// 關(guān)系三個節(jié)點:pos->prev    pos     pos->next
	LTNode* Prev = pos->prev; //  pos 的前一個 
	LTNode* Next = pos->next; //  pos 的下一個
	Next->prev = Prev;
	Prev->next = Next;
	free(pos);
	pos = NULL;
}


// 銷毀
void LTDestory(LTNode* phead)
{
	assert(phead);
	// 先全部刪除有效節(jié)點,后刪除頭節(jié)點
	LTNode* pcur = phead->next;
	while (pcur != phead)
	{
		LTNode* Next = pcur->next;
		free(pcur);
		pcur = Next;
	}
	// 最后釋放掉 形參的指針:這里不是釋放 哨兵位
	free(phead);
	phead = NULL;
}

test.c

#include"List.h"

void LTTest()
{
	// 創(chuàng)建哨兵位
	LTNode* head = LTInit();  // 這里直接用 head 代表哨兵位:更直觀一點,和 前面講解用的 plist 是一樣的

	// 尾插法
	LTPushBack(head, 1);
	LTPushBack(head, 2);
	LTPushBack(head, 3);
	LTPushBack(head, 4); // 1 -> 2 -> 3 -> 4 ->
	printf("測試尾插:");
	LTPrint(head);

	// 頭插法
	LTPushFront(head, 5);
	LTPushFront(head, 6);// 6 -> 5 -> 1 -> 2 -> 3 -> 4 ->
	printf("測試頭插:");
	LTPrint(head);

	// 查找
	//LTFind(head, 1);

	// 在 pos 之后插入數(shù)據(jù):頭插法實現(xiàn)邏輯一樣
	LTNode* FindRet1 = LTFind(head, 1);
	LTInsert(FindRet1, 100);
	LTNode* FindRet2 = LTFind(head, 2);
	LTInsert(FindRet2, 200); // 6 -> 5 -> 1 -> 100 -> 2 -> 200 -> 3 -> 4 ->
	printf("測試pos 之后插入:");
	LTPrint(head);

	// 頭刪法
	LTPopFront(head);
	LTPopFront(head); // 1 -> 100 -> 2 -> 200 -> 3 -> 4 ->
	printf("測試頭刪:");
	LTPrint(head);

	// 尾刪法:記得雙鏈表的找尾 不像 單鏈表需要循環(huán)去找尾
	LTPopBack(head);
	LTPopBack(head); // 1 -> 100 -> 2 -> 200 ->
	printf("測試尾刪:");
	LTPrint(head);

	// 刪除 pos 位置節(jié)點
	LTNode* FindRet3 = LTFind(head, 1);
	LTErase(FindRet3); // 100 -> 2 -> 200 ->
	printf("測試刪除 pos 位置節(jié)點:");
	LTPrint(head);

	// 雙鏈表的 銷毀:這里就不演示銷毀了
	//LTDesTroy(head);
	//head= NULL;  //哨兵位 需要手動 置為NULL
}
int main()
{
	LTTest();
	return 0;
}

三. 順序表和雙向鏈表的優(yōu)缺點分析

不同點

順序表

鏈表(單鏈表)

存儲空間

物理上?定連續(xù)

邏輯連續(xù),但物理上不?定連續(xù)

機訪問

支持O(1)

不支持:O(N)

任意位置插?或者刪除

可能要搬移素,率低O(N)

指針指向

插入

動態(tài)順序表,空間夠時要擴容

沒有容的概念

應用場景

素高存儲+頻繁訪問

任意位置插?和刪除頻繁

完。

若上述文章有什么錯誤,歡迎各位大佬及時指出,我們共同進步!文章來源地址http://www.zghlxwxcb.cn/news/detail-829173.html

到了這里,關(guān)于【數(shù)據(jù)結(jié)構(gòu)】雙向鏈表 超詳細 (含:何時用一級指針或二級指針;指針域的指針是否要釋放)的文章就介紹完了。如果您還想了解更多內(nèi)容,請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章,希望大家以后多多支持TOY模板網(wǎng)!

本文來自互聯(lián)網(wǎng)用戶投稿,該文觀點僅代表作者本人,不代表本站立場。本站僅提供信息存儲空間服務,不擁有所有權(quán),不承擔相關(guān)法律責任。如若轉(zhuǎn)載,請注明出處: 如若內(nèi)容造成侵權(quán)/違法違規(guī)/事實不符,請點擊違法舉報進行投訴反饋,一經(jīng)查實,立即刪除!

領(lǐng)支付寶紅包贊助服務器費用

相關(guān)文章

  • 【數(shù)據(jù)結(jié)構(gòu)與算法】 - 雙向鏈表 - 詳細實現(xiàn)思路及代碼

    【數(shù)據(jù)結(jié)構(gòu)與算法】 - 雙向鏈表 - 詳細實現(xiàn)思路及代碼

    前幾篇文章介紹了怎樣去實現(xiàn)單鏈表、單循環(huán)鏈表, 這篇文章主要介紹 雙向鏈表 以及實現(xiàn)雙向鏈表的步驟,最后提供我自己根據(jù)理解實現(xiàn)雙向鏈表的C語言代碼 。跟著后面實現(xiàn)思路看下去,應該可以看懂代碼,看懂代碼后,就對雙向鏈表有了比較抽象的理解了,最后自己再

    2024年02月01日
    瀏覽(28)
  • 數(shù)據(jù)結(jié)構(gòu)-鏈表結(jié)構(gòu)-雙向鏈表

    數(shù)據(jù)結(jié)構(gòu)-鏈表結(jié)構(gòu)-雙向鏈表

    雙向鏈表也叫雙鏈表,與單向鏈表不同的是,每一個節(jié)點有三個區(qū)域組成:兩個指針域,一個數(shù)據(jù)域 前一個指針域:存儲前驅(qū)節(jié)點的內(nèi)存地址 后一個指針域:存儲后繼節(jié)點的內(nèi)存地址 數(shù)據(jù)域:存儲節(jié)點數(shù)據(jù) 以下就是雙向鏈表的最基本單位 節(jié)點的前指針域指向前驅(qū),后指針

    2024年02月04日
    瀏覽(31)
  • 【數(shù)據(jù)結(jié)構(gòu)】雙向奔赴的愛戀 --- 雙向鏈表

    【數(shù)據(jù)結(jié)構(gòu)】雙向奔赴的愛戀 --- 雙向鏈表

    關(guān)注小莊 頓頓解饞????? 引言:上回我們講解了單鏈表(單向不循環(huán)不帶頭鏈表),我們可以發(fā)現(xiàn)他是存在一定缺陷的,比如尾刪的時候需要遍歷一遍鏈表,這會大大降低我們的性能,再比如對于鏈表中的一個結(jié)點我們是無法直接訪問它的上一個結(jié)點,那有什么解決方法呢

    2024年04月08日
    瀏覽(27)
  • 數(shù)據(jù)結(jié)構(gòu) - 雙向鏈表

    數(shù)據(jù)結(jié)構(gòu) - 雙向鏈表

    文章目錄 目錄 文章目錄 前言 一、什么是雙向鏈表? 雙向鏈表有什么優(yōu)勢? 二、雙向鏈表的設計和實現(xiàn) 1.設計思想 尾增 : 在鏈表的末尾添加新的元素 ?頭插 : 在鏈表頭部插入節(jié)點 ?刪除 : 根據(jù)val的值刪除節(jié)點 ?查找 : 根據(jù)索引的值查找并返回節(jié)點 總結(jié) 大家好,今天給大家講解

    2024年02月09日
    瀏覽(28)
  • 數(shù)據(jù)結(jié)構(gòu)---雙向鏈表

    單向鏈表:一塊內(nèi)存指向下一個內(nèi)存。 單鏈表存在一些缺陷: 1.查找速度慢。 2.不能從后往前找。 3.找不到前驅(qū)。 鏈表的結(jié)構(gòu)分為8種: 1.單向和雙向 2.帶頭和不帶頭 帶頭的鏈表有一個帶哨兵位的頭結(jié)點,這個節(jié)點不存儲有效數(shù)據(jù)。 好處 :尾插更方便,不需要二級指針了,

    2024年02月02日
    瀏覽(25)
  • 數(shù)據(jù)結(jié)構(gòu)雙向鏈表

    數(shù)據(jù)結(jié)構(gòu)雙向鏈表

    Hello,好久不見,今天我們講鏈表的雙向鏈表,這是一個很厲害的鏈表,帶頭雙向且循環(huán),學了這個鏈表,你會發(fā)現(xiàn)順序表的頭插頭刪不再是一個麻煩問題,單鏈表的尾插尾刪也變得簡單起來了,那廢話不多說,讓我們開始我們的學習吧! 首先我們要了解它的物理和邏輯結(jié)構(gòu)

    2024年02月11日
    瀏覽(25)
  • 數(shù)據(jù)結(jié)構(gòu)-雙向鏈表

    數(shù)據(jù)結(jié)構(gòu)-雙向鏈表

    在單鏈表那一篇博客中介紹了單鏈表和雙向鏈表的優(yōu)缺點,所以此篇博客直接分享怎樣實現(xiàn)一個帶頭雙向循環(huán)鏈表。 單鏈表博客: 首先我們需要寫一個結(jié)構(gòu)體,雙向帶頭鏈表的話需要一個前驅(qū)指針prev和一個后驅(qū)指針next,前驅(qū)指針的作用是方便找尾節(jié)點,因為頭節(jié)點的prev指

    2024年02月05日
    瀏覽(44)
  • 數(shù)據(jù)結(jié)構(gòu)—雙向鏈表

    數(shù)據(jù)結(jié)構(gòu)—雙向鏈表

    目錄 1.? 鏈表的種類 2.? 最實用的兩種鏈表類型 3.? 實現(xiàn)雙向帶頭循環(huán)鏈表 ? ? ? ? ? ? ? ? ? 3.1 創(chuàng)建頭節(jié)點 ????????3.2 實現(xiàn)雙向循環(huán)功能—返回頭指針 ????????3.3? 尾插?? ????????3.4 頭插 ????????3.5 尾刪 ????????3.6 頭刪 4.? 實現(xiàn)兩個重要接口函數(shù) ?

    2023年04月23日
    瀏覽(28)
  • 數(shù)據(jù)結(jié)構(gòu)——雙向鏈表

    數(shù)據(jù)結(jié)構(gòu)——雙向鏈表

    ??系列專欄:??數(shù)據(jù)結(jié)構(gòu) ?? ?歡迎關(guān)注:??點贊??收藏??留言 ?? 博客主頁:??_麥麥_的博客_CSDN博客-領(lǐng)域博主 ??如果我們都不能夠擁有黑夜,又該怎樣去仰望星空? ? 目錄 一、前言 二、正文——雙向鏈表的實現(xiàn) 2.1模塊化 2.2 數(shù)據(jù)類型與結(jié)構(gòu)體定義 ?2.3鏈表的初始化

    2024年02月02日
    瀏覽(27)
  • 數(shù)據(jù)結(jié)構(gòu)——實現(xiàn)雙向鏈表

    數(shù)據(jù)結(jié)構(gòu)——實現(xiàn)雙向鏈表

    怎么說呢?光乍一聽名字好像很難的樣子是吧,那如果你這樣認為的話,可就要讓你大跌眼鏡了哦,其實雙向帶頭循環(huán)鏈表從操作和理解上來說都是要易于單項不帶頭不循環(huán)鏈表(俗稱單鏈表)的。 咱們就來見識見識吧!希望真的能讓你們“大跌眼鏡”哈! 雙向帶頭循環(huán)鏈

    2024年02月07日
    瀏覽(22)

覺得文章有用就打賞一下文章作者

支付寶掃一掃打賞

博客贊助

微信掃一掃打賞

請作者喝杯咖啡吧~博客贊助

支付寶掃一掃領(lǐng)取紅包,優(yōu)惠每天領(lǐng)

二維碼1

領(lǐng)取紅包

二維碼2

領(lǐng)紅包