線性表——雙向鏈表

線性表——雙向鏈表

  • 1. 雙向鏈表的實現
    • 1.1 簡單圖例
    • 1.2 結點的定義
    • 1.3 新結點的創建
    • 1.4 鏈表的初始化
    • 1.5 結點的插入
      • 1.5.1 頭部插入(頭插)
      • 1.5.2 尾部插入(尾插)
      • 1.5.3 任意位置(前)插入
    • 1.6 結點的刪除
      • 1.6.1 頭部刪除(頭刪)
      • 1.6.2 尾部刪除(尾刪)
      • 1.6.3 任意位置刪除
    • 1.7 查找結點
    • 1.8 鏈表的打印
    • 1.9 鏈表的銷毀
  • 2. 功能綜合
  • 3. 誤區糾正
  • 4. 正確使用鏈表

??到目前為止,我們對順序表,鏈表都進行了初步是實現,其中僅完成了單鏈表。要知道,鏈表可不僅僅用是否有頭結點來區分,另外還有單向、雙向循環和非循環。將這些情況組合起來可以組成 8 種不同的鏈表,由于帶頭雙向循環鏈表的使用情況較多,本章就對帶頭雙向循環鏈表進行實現。

1. 雙向鏈表的實現

1.1 簡單圖例

帶頭雙向鏈表簡單圖例

1.2 結點的定義

typedef int LTDataType;
typedef struct ListNode
{LTDataType val;			//數據域struct ListNode* prev;	//指針域(存放前驅結點的地址)struct ListNode* next;	//指針域(存放后繼結點的地址)
}ListNode;

注意:雙向鏈表有 兩個 指針域,一個指向前驅 結點,一個指向后繼 結點。

1.3 新結點的創建

ListNode* CreateListNode(LTDataType x) {						//x為新結點的val部分(數據域)ListNode* newnode = (ListNode*)malloc(sizeof(ListNode));	//為新結點開辟新空間if (newnode == NULL) {perror("malloc fail!");return;}newnode->val = x;newnode->next = NULL;newnode->prev = NULL;return newnode;				//返回新結點的地址
}

1.4 鏈表的初始化

??這里鏈表的初始化只是針對于頭結點,相當于給頭結點一個初始的值。

ListNode* DListInit() {ListNode* phead = CreateListNode(-1);	//給頭結點的值賦為 -1phead->next = phead;phead->prev = phead;	//指針域全部指向本身(初始化)return phead;
}

測試時即可使用:

ListNode* Dlist=DListInit();

1.5 結點的插入

1.5.1 頭部插入(頭插)

注意:頭部插入不是在頭結點之前插入,而是在 頭結點后面第一個結點之前插入

void DListPushFront(ListNode* phead, LTDataType x) {assert(phead);ListNode* newnode = CreateListNode(x);ListNode* cur = phead->next;phead->next = newnode;newnode->prev = phead;newnode->next = cur;cur->prev = newnode;
}

圖解:
頭插

1.5.2 尾部插入(尾插)

void DListPushBack(ListNode* phead, LTDataType x) {assert(phead);ListNode* tail = phead->prev;ListNode* newnode = CreateListNode(x);tail->next = newnode;newnode->prev = tail;newnode->next = phead;phead->prev = newnode;}

圖解:
尾插

1.5.3 任意位置(前)插入

??在這部分功能上雙向鏈表就比單鏈表好實現得多,雙向鏈表自帶一個前驅結點的地址,不需要像單鏈表一樣從頭開始遍歷。

void DListInsert(ListNode* pos, LTDataType x) {assert(pos);	//判斷pos不為空ListNode* newnode = CreateListNode(x);ListNode* cur = pos->prev;cur->next = newnode;newnode->prev = cur;newnode->next = pos;pos->prev = newnode;}

此部分圖例可參考頭插(同原理)

1.6 結點的刪除

1.6.1 頭部刪除(頭刪)

void DListPopFront(ListNode* phead) {assert(phead);ListNode* front = phead->next;ListNode* back = front->next;phead->next = back;back->prev = phead;free(front);front = NULL;
}

圖解:
頭刪

1.6.2 尾部刪除(尾刪)

??刪除尾部結點只需要將倒數第二個的結點的位置找到,尾部結點的空間就可以直接釋放了,接下來就直接鏈接頭結點。

void DListPopBack(ListNode* phead) {assert(phead);ListNode* tail = phead->prev;ListNode* tail_prev = tail->prev;free(tail);tail = NULL;tail_prev->next = phead;phead->prev = tail_prev;}

圖解:
尾刪

1.6.3 任意位置刪除

void DListErase(ListNode* pos) {assert(pos);ListNode* cur = pos->prev;ListNode* back = pos->next;cur->next = back;back->prev = cur;free(pos);pos = NULL;
}

此處圖例可參考頭刪 尾刪(同原理)

1.7 查找結點

??在順序表中,當結點的位置被找到時,函數會返回順序表的下標。在鏈表中,返回的就是結點的地址。

ListNode* DListFind(ListNode* phead, LTDataType x) {assert(phead);ListNode* cur = phead->next;while (cur != phead) {if (cur->val == x) {return cur;}cur = cur->next;}return NULL;	//找不到對應的結點返回NULL
}

1.8 鏈表的打印

void DListPrint(ListNode* phead) {assert(phead);ListNode* cur = phead->next;printf("(頭結點)<->");while (cur!=phead) {printf("[%d]<->", cur->val);cur = cur->next;}printf("(頭結點)\n");
}

打印部分可自行美化

1.9 鏈表的銷毀

void DListDestory(ListNode* phead) {assert(phead);ListNode* cur = phead->next;while (cur != phead) {ListNode* Next = cur->next;		//先存儲下一個結點的地址free(cur);						//再釋放當前結點cur = Next;						//然后把Next給cur}free(phead);phead = NULL;
}

2. 功能綜合

??功能整合起來代碼較長,另外也可以通過接口的方式實現(層次分明),有不懂的可參考上文圖解自行消化,main部分可以自行調用函數進行測試。

#include<stdio.h>
#include<stdlib.h>
#include<assert.h>//創建新結點
ListNode* CreateListNode(LTDataType x) {						//x為新結點的val部分(數據域)ListNode* newnode = (ListNode*)malloc(sizeof(ListNode));	//為新結點開辟新空間if (newnode == NULL) {perror("malloc fail!");return;}newnode->val = x;newnode->next = NULL;newnode->prev = NULL;return newnode;				//返回新結點的地址
}//初始化頭結點
ListNode* DListInit() {ListNode* phead = CreateListNode(-1);	//給頭結點的值賦為 -1phead->next = phead;phead->prev = phead;	//指針域全部指向本身(初始化)return phead;
}//頭插
void DListPushFront(ListNode* phead, LTDataType x) {assert(phead);ListNode* newnode = CreateListNode(x);ListNode* cur = phead->next;phead->next = newnode;newnode->prev = phead;newnode->next = cur;cur->prev = newnode;
}//尾插
void DListPushBack(ListNode* phead, LTDataType x) {assert(phead);ListNode* tail = phead->prev;ListNode* newnode = CreateListNode(x);tail->next = newnode;newnode->prev = tail;newnode->next = phead;phead->prev = newnode;}//任意位置(前)插入
void DListInsert(ListNode* pos, LTDataType x) {assert(pos);	//判斷pos不為空ListNode* newnode = CreateListNode(x);ListNode* cur = pos->prev;cur->next = newnode;newnode->prev = cur;newnode->next = pos;pos->prev = newnode;}//頭刪
void DListPopFront(ListNode* phead) {assert(phead);ListNode* front = phead->next;ListNode* back = front->next;phead->next = back;back->prev = phead;free(front);front = NULL;
}//尾刪
void DListPopBack(ListNode* phead) {assert(phead);ListNode* tail = phead->prev;ListNode* tail_prev = tail->prev;free(tail);tail = NULL;tail_prev->next = phead;phead->prev = tail_prev;}//任意位置刪除
void DListErase(ListNode* pos) {assert(pos);ListNode* cur = pos->prev;ListNode* back = pos->next;cur->next = back;back->prev = cur;free(pos);pos = NULL;
}//查找結點
ListNode* DListFind(ListNode* phead, LTDataType x) {assert(phead);ListNode* cur = phead->next;while (cur != phead) {if (cur->val == x) {return cur;}cur = cur->next;}return NULL;	//找不到對應的結點返回NULL
}//打印鏈表
void DListPrint(ListNode* phead) {assert(phead);ListNode* cur = phead->next;printf("(頭結點)<->");while (cur!=phead) {printf("[%d]<->", cur->val);cur = cur->next;}printf("(頭結點)\n");
}//銷毀鏈表
void DListDestory(ListNode* phead) {assert(phead);ListNode* cur = phead->next;while (cur != phead) {ListNode* Next = cur->next;		//先存儲下一個結點的地址free(cur);						//再釋放當前結點cur = Next;						//然后把Next給cur}free(phead);phead = NULL;
}int main() {ListNode* Dlist = DListInit();  //初始化DListPushBack(Dlist, 1);DListPushBack(Dlist, 2);DListPushBack(Dlist, 3);DListPushBack(Dlist, 5);DListPushBack(Dlist, 4);		//尾插DListPrint(Dlist);				//打印DListPopBack(Dlist);			//尾刪DListPrint(Dlist);				//打印DListPushFront(Dlist, 99);DListPushFront(Dlist, 78);DListPushFront(Dlist, 666);		//頭插DListPrint(Dlist);				//打印DListPopFront(Dlist);			//頭刪DListPrint(Dlist);				//打印return 0;
}

運行結果:
運行結果

3. 誤區糾正

  1. 增刪查改的操作對象的主體不是頭結點,頭的增刪動的是 head->next
  2. 頭結點只是起輔助作用,判斷帶頭鏈表是否為空,要從頭結點->next開始判斷。
  3. 雙向鏈表不能完全替代單鏈表,單鏈表相對于雙向鏈表來說 內存使用少 ,比雙向鏈表少一個指針。

4. 正確使用鏈表

  • 理解 prevnext 的指向關系。
  • 根據實際情況判斷鏈表是否需要 頭結點循環雙向

本文來自互聯網用戶投稿,該文觀點僅代表作者本人,不代表本站立場。本站僅提供信息存儲空間服務,不擁有所有權,不承擔相關法律責任。
如若轉載,請注明出處:http://www.pswp.cn/bicheng/88019.shtml
繁體地址,請注明出處:http://hk.pswp.cn/bicheng/88019.shtml
英文地址,請注明出處:http://en.pswp.cn/bicheng/88019.shtml

如若內容造成侵權/違法違規/事實不符,請聯系多彩編程網進行投訴反饋email:809451989@qq.com,一經查實,立即刪除!

相關文章

Java后端技術博客匯總文檔

文章目錄 前言Java后端匯總鏈接Java基礎知識點數據結構算法&#xff08;Java實現&#xff09;算法知識點合集算法刷題算法競賽AcWing課程藍橋杯AB組輔導課合集&#xff08;更新中…&#xff09; 源碼分析redission 數據庫SQL ServerMySQLRedis -Canal JUC并發編程JVMNetty日志框…

QT 菜單欄設計使用方法

目錄 常用設置函數 多個QAction的單選設置 ???????菜單相關類 ??????? 系統菜單的生成和響應 使用代碼添加系統菜單 使用UI設計器設計系統菜單 使用Qt設計及界面時&#xff0c;常用的兩種方式添加菜單&#xff0c;第一使用UI界面添加&#xff0c;第二種 在…

AIGC領域AI藝術,打造個性化藝術作品

AIGC領域AI藝術,打造個性化藝術作品 關鍵詞:AIGC、AI藝術、生成對抗網絡、個性化創作、深度學習、藝術風格遷移、創意計算 摘要:本文深入探討了AIGC(人工智能生成內容)在藝術創作領域的應用,重點分析了如何利用AI技術打造個性化藝術作品。文章從技術原理出發,詳細解析了生…

基于Flask+Jinja2的快捷教務系統(后端鏈接到新版正方教務系統)

快捷教務系統&#xff08;Easy Educational Administration Management System, EasyEAMS&#xff09; 項目簡介 EasyEAMS 是一個基于 Flask Jinja2 的現代化教務系統 Web 應用。學生可通過網頁端登錄&#xff0c;在線查詢個人信息、成績、課表、學業生涯、通知、選課等。系…

EDM自動化與出海獨立開發實用教程

隨著互聯網全球化發展&#xff0c;越來越多的獨立開發者&#xff08;Indie Developer&#xff09;選擇將自己的產品推向海外市場。如何高效地獲客、激活用戶、提升轉化率&#xff0c;成為出海過程中必須解決的問題。EDM&#xff08;電子郵件營銷&#xff09;自動化&#xff0c;…

「日拱一碼」017 深度學習常用庫——TensorFlow

目錄 基礎操作 張量操作&#xff1a; tf.constant 用于創建常量張量 tf.Variable 用于創建可訓練的變量張量 tf.reshape 可改變張量的形狀 tf.concat 可將多個張量沿指定維度拼接 tf.split 則可將張量沿指定維度分割 數學運算&#xff1a; tf.add 張量的加運算 tf.su…

ARM DStream仿真器腳本常用命令

以下是ARM DStream仿真器腳本中常用的命令及其功能分類&#xff0c;結合調試流程和典型應用場景整理&#xff1a; ?? 一、連接與初始化命令 connect 建立與目標設備的連接&#xff0c;需指定接口類型&#xff08;如JTAG/SWD&#xff09;和處理器核心。 示例&#xff1a;conne…

vscode 調試unity

lanch.json { “version”: “0.2.0”, “configurations”: [ { “name”: “Attach to Unity”, “type”: “vstuc”, “request”: “attach” } ] }

金融IT入門知識點

銀行金融IT核心知識點全解析&#xff1a;架構、技術與實踐 一、金融IT的戰略地位與行業特性 金融IT作為銀行業務的核心支撐體系&#xff0c;其發展水平直接決定了銀行服務的效率、安全性與創新能力。截至 2025年&#xff0c;中國銀行業線上化業務占比已達97%&#xff0c;手機銀…

C++——手撕智能指針、單例模式、線程池、String

智能指針今天我們來學習一下C中的智能指針&#xff0c;如果有人不知道C中的智能指針的概念的話&#xff1a;C智能指針是一種基于RAII&#xff08;Resource Acquisition Is Initialization&#xff0c;資源獲取即初始化&#xff09;機制的高級內存管理工具&#xff0c;用于自動化…

Mybatis----留言板

基礎項目&#xff1a;留言板 截止到目前為止&#xff0c;我們已經學習了 Spring&#xff08;只學習了DI&#xff09;、Spring MVC、SpringBoot、Mybatis 這些知識了&#xff0c;已經滿足了做簡單項目的基本要求了&#xff0c;所以接下來我們就從0到1實現表白墻項目。 需求分析…

Web-API-day3 DOM事件進階

一、 事件流 1.事件冒泡 const fa document.querySelector(.father)const son document.querySelector(.son)document.addEventListener(click, function () {alert(我是爺爺)})fa.addEventListener(click, function () {alert(我是爸爸)})son.addEventListener(click, fun…

小波增強型KAN網絡 + SHAP可解釋性分析(Pytorch實現)

效果一覽一、傳統KAN網絡的痛點與突破 1. 傳統KAN的局限性 傳統Kolmogorov-Arnold網絡&#xff08;KAN&#xff09;雖在理論上有可靠的多變量函數逼近能力&#xff0c;但存在顯著瓶頸&#xff1a; 計算效率低&#xff1a;訓練速度慢于MLP&#xff0c;資源消耗大&#xff0c;尤其…

tomcat部署多個端口以及制定路徑部署-vue3

vue3項目tomcat部署記錄 使用hash路由 字符串拼接的圖片地址可以使用import.meta.env.BASE_URL 默認8080 如果部署地址為8080/xc 則設置 vite.config.js中設置base為’/xc/’ outDir設置為xc 打包產物直接拖到webapps目錄下 如果另開一個端口 如8081 設置根目錄訪問 conf/ser…

LeetCode三數之和-js題解

給你一個整數數組 nums &#xff0c;判斷是否存在三元組 [nums[i], nums[j], nums[k]] 滿足 i ! j、i ! k且 j ! k &#xff0c;同時還滿足 nums[i] nums[j] nums[k] 0 。請你返回所有和為 0 且不重復的三元組。 注意&#xff1a;答案中不可以包含重復的三元組。 示例 1&…

Flink SQLServer CDC 環境配置與驗證

一、SQL Server 數據庫核心配置 1. 啟用 CDC 功能&#xff08;Change Data Capture&#xff09; SQL Server CDC 依賴數據庫級別的 CDC 功能及表級別的捕獲配置&#xff0c;需按以下步驟啟用&#xff1a; 啟用數據庫 CDC -- 以管理員身份連接數據庫 USE master; GO-- 檢查數…

軟考(軟件設計師)存儲管理—設備管理,磁盤調度

I/O軟件的核心目標是管理硬件差異、提供統一接口、實現高效可靠的數據傳輸。 核心目標&#xff1a; 設備無關性&#xff1a; 應用程序無需關心具體硬件細節。錯誤處理&#xff1a; 處理硬件錯誤和傳輸異常。同步/異步傳輸&#xff1a; 支持阻塞&#xff08;等待完成&#xff09…

[C語言] C語言數學函數庫概覽

C語言數學函數庫概覽 文章目錄 C語言數學函數庫概覽一、概述二、基本數學函數詳解1. 平方根函數 sqrt(x)2. 冪函數 pow(x, y)3. 絕對值函數 fabs(x)4. 向上取整函數 ceil(x)5. 向下取整函數 floor(x) 三、三角函數與雙曲函數詳解1. 正弦函數 double sin(double x)2. 余弦函數 d…

【簡單三步】Stable diffusion Webai本地部署無法加載模型并報openai/clip-vit-large-patch14錯誤的解決方法

問題描述 Stable diffusion Webai本地部署成功后&#xff0c;手動加載本地模型checkpoint時&#xff0c;始終無法加載進去&#xff0c;確定模型存放位置無誤&#xff08;位于models\Stable-diffusion&#xff09;查看cmd窗口時&#xff0c;發現一個報錯提示&#xff1a;Can’t …

Java 命令行參數詳解:系統屬性、JVM 選項與應用配置

Java 命令行參數詳解&#xff1a;系統屬性、JVM 選項與應用配置 在 Java 應用啟動命令中&#xff0c;如&#xff1a; java -jar -Dserver.port8088 xdr-demo-1.0-SNAPSHOT-assembly.jar &-Dserver.port8088是一個 系統屬性&#xff08;System Property&#xff09; 設置。…