【數據結構】單鏈表：數據結構中的舞者，穿梭于理論與實踐的舞池

?歡迎來到白劉的領域???Miracle_86.-CSDN博客

? ? ? ? ?系列專欄? ?數據結構與算法

先贊后看，已成習慣

? ?創作不易，多多支持！

一、鏈表的概念和結構

1.1 鏈表的概念

在上一篇文章中，我們了解了線性表(linear list)，并且學習了其中一種線性表——順序表(Sequence List)。鏈表也是線性表的一種，那么它是一種什么樣的結構呢？

鏈表，顧名思義，帶著鏈子的表。日常生活中，我們知道鏈子是用來鏈接兩個東西的，那么我們可以很容易理解，順序表是基于數組實現的，是一個元素一個元素挨著的，那鏈表我們就可以理解為每個元素用鏈子連接起來，這樣就形成了鏈表(Linked List)。

1.2?鏈表的結構

那么我們得到了兩個鏈表的組成的關鍵元素，一個是每個元素，我們管它叫節點(或結點)，另一個就是那個鏈子。而在C語言中，我們用結構體來實現節點，用指針來充當鏈，連接兩個節點。

在生活中鏈表類似于我們的火車的結構，在物理上它是一種存儲結構非順序非連續的結構。

節點的組成主要由兩個部分組成：一個是數值域，用來保存當前節點的數據，一個是指針域，用來保存下一個節點的地址(指針變量)。

如圖所示，指針變量plist保存的是第一個節點的地址，如果我們想讓plist指向第二個節點，我們只需要將plist保存的內容修改為0x0012FFD0。

為什么我們需要指針變量來保存下一個節點的位置？

因為之前我們說了，鏈表不同于順序表，它在內存中的地址不一定是連續的，它是獨立申請的(對其插入數據時才申請一個節點)。我們需要通過指針才能從當前節點找到下一個節點。

所以我們可以通過一個結構體來實現一個節點，它要有一個節點的數據以及一個指針變量來保存下一個節點的地址，代碼如下：

struct SListNode
{int data; //節點數據struct SListNode* next; //指針變量?保存下?個節點的地址
};

當然我們也可以用typedef來進行修改，方便我們后續操作。

typedef int SLTDataType;typedef struct SListNode
{SLTDataType data; //節點數據struct SListNode* next; //指針保存下?個節點的地址
}SLTNode;

我們如何將鏈表進行打印呢？

首先我們將節點傳到打印函數，然后我們創建了一個指向頭結點的結構體指針，利用循環從頭遍歷到尾，每次打印完成令pcur指向pcur的next節點。這里注意的就是結構體成員的訪問的問題，我們用到了->操作符，在前面的博客我們都介紹過。

武器大師——操作符詳解（下）-CSDN博客

代碼如下：

void SLTPrint(SLTNode* phead){SLTNode *cur = phead;while(cur){printf("%d ",cur->data);cur = cur->next;}printf("\n");
}

?二、單鏈表的實現

上面我們知道了什么是鏈表，那單鏈表又是什么呢？單鏈表(Singly Linked List)，一般所指的是“不帶頭單向不循環鏈表”。

我們實現的功能無非就四個“增、刪、查、改”。

2.1 增

2.1.1 尾插

尾插，顧名思義，在尾部插入，俗稱后入(bushi)。

首先我們要申請新的節點，我們可以寫一個申請節點的函數。

SLTNode* BuyNode(SLTDataType x) {SLTNode* node = (SLTNode*)malloc(sizeof(SLTNode));if (node == NULL) {perror("malloc fail!\n");exit(1);}node->data = x;node->next = NULL;return node;
}

首先我們用malloc函數動態申請一塊內存，然后將節點的數據賦進去。

void SLTPushBack(SLTNode** pphead, SLTDataType x) {assert(pphead);SLTNode* node = BuyNode(x);if (*pphead == NULL) {*pphead = node;return;}//找尾SLTNode* cur = *pphead;while (cur->next) {cur = cur->next;}cur->next = node;
}

接下來的代碼邏輯特別簡單，首先我們通過buynode函數創建了一個節點，然后我們判空，如果這個鏈表是空的，我們直接將指針變量pphead賦為node。如果不是空的，那我們就需要找到鏈表的尾部，我們可以通過循環來找到尾部，首先為了防止原來數據被破壞，我們創建一個指向第一個節點的指針變量cur，而不是直接遍歷pphead。

注意我們如何找尾，通過判斷該節點的下一個位置是否為空。

這里還有一個細節就是，我們傳入的是二級指針，因為我們要修改一個數據的話，需要傳地址，而那個數據如果是指針的話，我們就需要傳指針的地址，也就是二級指針。

2.1.2 頭插
void SLTPushFront(SLTNode** pphead, SLTDataType x) {assert(pphead);SLTNode* node = BuyNode(x);node->next = *pphead;*pphead = node;
}

這個代碼邏輯也很簡單，首先我們assert斷言防止訪問空指針，之后buynode函數申請節點，然后將結點接到頭部，也就是*pphead，之后別忘了將*pphead再指向node，形成新的頭。

2.2 刪

2.2.1 尾刪

尾刪也很簡單，仔細思考，我們只需要兩步就能完成，一個是找尾，一個是刪除。

首先我們來看找尾，我們可以用循環，再加上兩個指針，

   //找尾
//    SLTNode *cur = *pphead;
//    SLTNode *prev = NULL;
//    while(cur->next){
//        prev = cur;
//        cur = cur->next;
//    }
//    prev->next = NULL;
//    free(cur);
//    cur = NULL;

首先cur指向頭，prev指向空，cur用來找尾，prev用來保存上一個節點的地址。當cur的下一個位置為NULL時循環結束，意味著找到最后一個節點了，我們將它所指的位置free掉(因為是動態開辟出來的)，然后指針置空即可完成刪除。

還有一種方法可以用一個指針就解決，

  SLTNode* tail = *pphead;while (tail->next->next) {tail = tail->next;}free(tail->next);tail->next = NULL;

?我們判斷條件改成這樣，實際上我們找的tail是倒數第二個節點，所以最后的刪除需要改成tail的next為NULL。

2.2.2 頭刪

頭刪的邏輯就更加簡單了，我們只需要創建一個變量來保存原來的頭節點，方便我們后續刪除，然后讓原頭節點移到下一個結點成為新的頭結點，然后刪掉原來的。如果我們不保存，我們沒有辦法找到原來的頭結點。

代碼如下：

void SLTPopFront(SLTNode** pphead) {assert(pphead);assert(*pphead);SLTNode* first = *pphead;*pphead = (*pphead)->next;free(first);first = NULL;
}

2.3 查

這個實現也很簡單，就是遍歷，然后匹配。由于是查找，而不是對數據進行修改，所以傳一級指針即可。

SLTNode* SLTFind(SLTNode* phead, SLTDataType x) {assert(phead);SLTNode* cur = phead;while (cur) {if (cur->data == x) {return cur;}cur = cur->next;}return NULL;
}

2.4 改

2.4.1 在pos前插入

將圖畫出來我們就清晰明了了。我們如果想把node插入到pos前，我們只需要將node的next指向pos，然后將prev的next指向node，這樣就構成了插入操作。

試想一下，1和2的操作可以調換順序嗎？答案是不可以，這是因為如果我們先做2，這個時候我們就找不到pos了，也就不能執行1操作了。有人會問，我創建兩個變量來記錄這兩個點的位置不可以嗎？可以，但是沒必要。

之后我們來看代碼部分，首先我們要創建一個node節點，用buynode函數。正常情況，我們需要找pos的前一個節點prev，利用循環即可。如果只有一個節點怎么辦呢？這個時候直接頭插就可以了。

void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x) {assert(pphead);assert(pos);SLTNode* node = BuyNode(x);if (*pphead == pos) {//        node->next = pos;//        *pphead = node;SLTPushFront(pphead, x);return;}//找pos的前一個節點SLTNode* prev = *pphead;while (prev->next) {if (prev->next == pos) {break;}prev = prev->next;}node->next = pos;prev->next = node;
}
2.4.2 刪除pos

其實邏輯也是很簡單的，要刪除pos的話，我們需要找到pos前面的節點保存，否則就找不到了。

void SLTErase(SLTNode** pphead, SLTNode* pos) {assert(pphead);assert(pos);if (*pphead == pos) {//        SLTNode *del = *pphead;//        *pphead = (*pphead)->next;//        free(del);//        del = NULL;SLTPopFront(pphead);return;}//找pos的前一個節點SLTNode* prev = *pphead;while (prev->next) {if (prev->next == pos) {break;}prev = prev->next;}prev->next = pos->next;free(pos);//    pos = NULL;//沒有存在的必要
}

并且要注意連接好pos后面的節點后再刪除，不然也找不到。

2.4.3 在pos后插入

邏輯跟在pos前插入一樣，也要注意順序，只不過在pos之后插入不需要傳鏈表第一個節點了，只需要傳pos即可。

void SLTInsertAfter(SLTNode* pos, SLTDataType x) {assert(pos);SLTNode* node = BuyNode(x);node->next = pos->next;pos->next = node;
}
2.4.4 刪除pos后的節點
void SLTEraseAfter(SLTNode* pos){assert(pos);assert(pos->next);SLTNode *del = pos->next;pos->next = del->next;free(del);del = NULL;
}

其實看到這你就發現，對鏈表的操作無非就是保存節點，然后連接，同時畫圖操作也可以對我們學習數據結構有所幫助。

2.5 鏈表的銷毀

我們將鏈表每個節點通過循環遍歷free掉即可，唯一比較吃操作的就是創建一個用于保存下一個節點的位置的指針。

//銷毀鏈表
void SListDesTroy(SLTNode** pphead)
{assert(pphead && *pphead);SLTNode* pcur = *pphead;while (pcur){SLTNode* next = pcur->next;free(pcur);pcur = next;}*pphead = NULL;
}

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

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

相關文章

Spring——IOC創建對象方式

Spring——IOC創建對象方式

可參考官網：https://docs.spring.io/spring-framework/reference/core/beans/dependencies/factory-collaborators.htmlhttps://docs.spring.io/spring-framework/reference/core/beans/dependencies/factory-collaborators.html 1. 使用無參構造創建對象&#xff0…
閱讀更多...
數據庫性能優化系統設計

數據庫性能優化系統設計

設計一個數據庫性能優化系統，目標是監測、診斷并改善數據庫的運行效率，確保系統能夠高效穩定地處理大量數據請求。以下是一個概要設計，包括關鍵模塊、功能和實現思路： 1. 系統架構 分布式監控中心：采用分布式架構收集…
閱讀更多...
C++ STL 協程(Coroutines)

C++ STL 協程(Coroutines)

一：什么是協程(Coroutines)： 協程是輕量級線程，可以暫停和恢復執行，協程擁有自己的暫停點狀態，協程暫停時，將當前狀態保存起來，在恢復執行時會恢復之前保存的狀態。 二：例子： #include <coroutine> #include <iostream>void doTheWork() {std::cout <…
閱讀更多...
PHP寶藏神器多功能投票系統源碼小程序

PHP寶藏神器多功能投票系統源碼小程序

&#x1f389;發現寶藏神器&#xff01;一鍵解鎖“多功能投票小程序”的無限可能? &#x1f308; 開篇安利&#xff1a;告別繁瑣&#xff0c;擁抱高效&#xff01; Hey小伙伴們&#xff0c;是不是經常為組織活動、收集意見而頭疼不已&#xff1f;&#x1f92f; 今天就要給大…
閱讀更多...
【理解STL】

【理解STL】

目錄 一、STL的概念1、STL的定義2、STL的組成 二、容器1、容器的定義及作用2、string類&#xff08;非容器&#xff09;3、vector容器4、set容器5、queue容器6、priority_queue容器7、stack容器8、deque容器9、map容器10、pair容器11、bitset容器12、map和set的區別13、vector和…
閱讀更多...
Node 中基于 Koa 框架的 Web 服務搭建實戰

Node 中基于 Koa 框架的 Web 服務搭建實戰

前言 在《Node之Web服務 - 掘金 (juejin.cn)》一文中,我們使用 HTTP 模塊構建了后端接口,從而實現了后端服務的開發。可以對此進行進一步優化 http模塊代碼回顧 const http require("http");const server http.createServer((req, res) > {if (reqUrl.pathna…
閱讀更多...
Python前沿技術：機器學習與人工智能

Python前沿技術：機器學習與人工智能

Python前沿技術&#xff1a;機器學習與人工智能 一、引言 隨著科技的飛速發展&#xff0c;機器學習和人工智能&#xff08;AI&#xff09;已經成為了計算機科學領域的熱門話題。Python作為一門易學易用且功能強大的編程語言&#xff0c;已經成為了這兩個領域的首選語言之一。本…
閱讀更多...
【零基礎】學JS

【零基礎】學JS

喝下這碗雞湯 “知識就是力量。” - 弗朗西斯培根 1.三元運算符 目標:能利用三元運算符執行滿足條件的語句 使用場景:其實是比if雙分支更簡單的寫法&#xff0c;可以使用三元表達式 語法&#xff1a;條件 ? 滿足條件的執行代碼 : 不滿足條件執行的代碼 接下來用一個小案例來展…
閱讀更多...
C#實現求解函數導數和值

C#實現求解函數導數和值

using MathNet.Symbolics; using System; using System.IO; using System.Text;private string ConvertToLatex(string mathExpression) {return mathExpression.Replace(" * ", "").Replace("*", ""); }// 將函數定義為字符串 string…
閱讀更多...
AI語言處理的雙刃劍：Tokens令牌化技術解析

AI語言處理的雙刃劍：Tokens令牌化技術解析

生成式人工智能模型&#xff0c;如GPT-4o&#xff0c;采用基于Transformer架構的復雜處理方式&#xff0c;這與人類處理文本的方式存在明顯差異。這些模型依賴于一種稱為“令牌化”的過程&#xff0c;將文本分解為更小的片段&#xff0c;稱為“令牌”&#xff0c;以便更有效地處…
閱讀更多...
Kafka拋棄Zookeeper后如何啟動？

Kafka拋棄Zookeeper后如何啟動？

Kafaka如何下載 官網地址 目前Kafka最新的版本就是3.7.1 我們可以看到下面這兩個版本信息&#xff1f;什么意思呢&#xff1f; Scala 2.12 - kafka_2.12-3.7.1.tgz (asc, sha512)Scala 2.13 - kafka_2.13-3.7.1.tgz (asc, sha512) 我們應該知道&#xff0c;一個完整的Kafka實…
閱讀更多...
平安消保在行動 | 守護每一個舒心笑容 不負每一場雙向奔赴

平安消保在行動 | 守護每一個舒心笑容 不負每一場雙向奔赴

“要時刻記得以消費者為中心&#xff0c;把他們當做自己的朋友&#xff0c;站在他們的角度去思考才能更好地解決問題。” 談及如何成為一名合格的消費者權益維護工作人員&#xff0c;平安養老險深圳分公司負責咨訴工作的龐宏霄認為&#xff0c;除了要具備扎實的專業技能和溝通…
閱讀更多...
MySQL篇四：表的約束

MySQL篇四：表的約束

文章目錄 前言1. 空屬性2. 默認值3. 列描述4. zerofill5. 主鍵6. 自增長7. 唯一鍵8. 外鍵 前言 真正約束字段的是數據類型&#xff0c;但是數據類型約束很單一&#xff0c;需要有一些額外的約束&#xff0c;更好的保證數據的合法性&#xff0c;從業務邏輯角度保證數據的正確性。…
閱讀更多...
JAVA學習筆記-JAVA基礎語法-DAY24-Stream流、方法引用

JAVA學習筆記-JAVA基礎語法-DAY24-Stream流、方法引用

第一章 Stream流 說到Stream便容易想到I/O Stream&#xff0c;而實際上&#xff0c;誰規定“流”就一定是“IO流”呢&#xff1f;在Java 8中&#xff0c;得益于Lambda所帶來的函數式編程&#xff0c;引入了一個全新的Stream概念&#xff0c;用于解決已有集合類庫既有的弊端。 …
閱讀更多...
python 高級技巧 0708

python 高級技巧 0708

python 33個高級用法技巧 使用裝飾器計時函數 裝飾器是一種允許在一個函數或方法調用前后運行額外代碼的結構。 import timedef timer(func):"""裝飾器函數&#xff0c;用于計算函數執行時間并打印。參數:func (function): 被裝飾的函數返回:function: 包裝后…
閱讀更多...
軟件架構之開發方法

軟件架構之開發方法

軟件架構之開發方法 第6章&#xff1a;開發方法6.1 軟件生命周期6.2 軟件開發模型6.2.1 瀑布模型6.2.2 演化模型6.2.3 螺旋模型6.2.4 增量模型6.2.5 構件組裝模型 6.3 統一過程6.4 敏捷方法6.4.1 極限編程6.4.2 特征驅動開發6.4.3 Scrum6.4.4 水晶方法6.4.5 其他敏捷方法 6.5 軟…
閱讀更多...
vmware lun回收引起的IO問題

vmware lun回收引起的IO問題

起初并沒人關注的小問題，正常不過的虛機存儲遷移操作，引起的延遲卻引發一連串的變化。 環境 vsphere 6.7 + 華為集中式存儲 開始 下午5:17 業務反饋，存在數據超時，頻繁在1秒鐘以內，正常在200ms。需運維排查虛機的狀態與IO情況等硬件使用情況。下午5:30 隨手翻開zabbix 打開…
閱讀更多...
vue在線預覽excel、pdf、word文件

vue在線預覽excel、pdf、word文件

安裝 //docx文檔預覽組件 npm install vue-office/docx vue-demi//excel文檔預覽組件 npm install vue-office/excel vue-demi//pdf文檔預覽組件 npm install vue-office/pdf vue-demi使用示例 docx文檔的預覽 <template><vue-office-docx :src"src" ren…
閱讀更多...
【嵌入式Linux】＜知識點＞ 虛擬地址空間

【嵌入式Linux】＜知識點＞ 虛擬地址空間

前言 在Linux中&#xff0c;新創建的進程都擁有獨立的虛擬地址空間。為深入多進程多線程的理解&#xff0c;了解虛擬地址空間分區十分有必要。 一、概念 虛擬地址空間分為4G空間&#xff0c;其中1G為內核區&#xff0c;3G為用戶區。虛擬地址空間的地址從0開始&#xff0c;且該…
閱讀更多...
20240708 視覺大模型

20240708 視覺大模型

參考網站&#xff1a; 萬字長文帶你全面解讀視覺大模型 - 知乎 一.DINO 1."YOLO"&#xff08;You Only Look Once&#xff09;和"DINO"&#xff08;DIstillation of knowledge&#xff09;是兩種不同的模型&#xff0c;針對不同的任務和學習目標。以下是…
閱讀更多...
最新文章

Copyright @ 2022~2023