數據結構---單鏈表的增刪查改

前言：

經過了幾個月的漫長歲月，回頭時年邁的小編發現，數據結構的內容還沒有寫博客，于是小編趕緊停下手頭的活動，補上博客以洗清身上的罪孽

目錄

前言

? ? ? ? ? ?概念：

單鏈表的結構

我們設定一個哨兵位頭節點給鏈表

單鏈表的基本操作

插入：

單鏈表的頭插：

單鏈表的尾插：

單鏈表的遍歷打印：從頭節點開始，逐個訪問鏈表中的每個節點，直到達到鏈表的末尾。

單鏈表的刪除：刪除鏈表中的指定節點，需要修改前一個節點的指針域以繞過被刪除的節點。

單鏈表的頭刪：

單鏈表的尾刪：

單鏈表元素的查找：根據給定的值或位置查找鏈表中的節點。

單鏈表的鏈表銷毀：

驗證：? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?

完整代碼：

slist.h

slist.c

test.c

總結：

概念：

? ? ? ?單鏈表是一種鏈式存取的數據結構，用一組地址任意的存儲單元存放線性表中的數據元素。鏈表中的數據是以結點來表示的，每個結點的構成：元素 (數據元素的映象) + 指針 (指示后繼元素存儲位置)，元素就是存儲數據的存儲單元，指針就是連接每個結點的地址數據。單鏈表不要求邏輯上相鄰的兩個元素在物理位置上也相鄰，因此不需要連續的存儲空間。單鏈表是非隨機的存儲結構，即不能直接找到表中某個特定的結點。查找某個特定的結點時，需要從表頭開始遍歷，依次查找。?

單鏈表的結構

? ? ? ?在單鏈表中，每個節點由一個數據元素和一個指針構成。數據元素可以是任何類型，而指針則指向鏈表中的下一個節點。如果一個節點的指針為空（NULL），則表示它是鏈表的最后一個節點。單鏈表通常通過一個頭指針來訪問，頭指針指向鏈表的第一個節點。

一個典型的單鏈表節點的結構可以用以下C語言代碼表示：

typedef struct SListNode
{SLTDateType data;//數據域struct SListNode* next;// 指針域，指向下一個節點
}SListNode;
我們設定一個哨兵位頭節點給鏈表
 SListNode* head = NULL;
單鏈表的基本操作

單鏈表的基本操作包括初始化、遍歷、插入、刪除和查找等。

單鏈表的初始化：創建一個空鏈表，通常是通過創建一個頭節點，其指針域為空。

插入：

在鏈表的指定位置插入一個新節點，需要修改前一個節點的指針域。

單鏈表的頭插：

? ? ? 斷言確保頭指針地址有效，先去動態申請一個新節點，然后將新節點的下一個節點指向頭節點，將該新節點變為頭節點，（不需要判斷是否為空）


// 單鏈表的頭插
void SListPushFront(SListNode** pplist, SLTDateType x) {assert(pplist);SListNode* newnode = BuySListNode(x);//SListNode* start = *pplist;newnode->next = *pplist;*pplist = newnode;}
單鏈表的尾插：

? ? ? 斷言確保頭指針地址有效，再申請一個新節點，分兩種情況，當鏈表為空時，直接新節點就是頭節點，鏈表不為空時，從頭節點遍歷到最后一個節點，將新節點設為最后一個節點的下一個節點

// 單鏈表尾插
void SListPushBack(SListNode** pplist, SLTDateType x) {assert(pplist);SListNode* newnode = BuySListNode(x);SListNode* end = *pplist;if (*pplist != NULL) //鏈表非空{while (end->next != NULL)end = end->next;end->next = newnode;}else //鏈表為空{*pplist = newnode;}
}

? ? ?動態創建一個SListNode大小的節點，然后看看是否創建成功，成功后將數據放入該節點，并將該節點的下一個位置，置為空；


// 動態申請一個節點
SListNode* BuySListNode(SLTDateType x) {SListNode* newnode = (SListNode*)malloc(sizeof(SListNode));if (newnode == NULL) {perror("malloc fail");return NULL;}// 初始化數據域和指針域newnode->data = x;newnode->next = NULL;return newnode;
}
單鏈表的遍歷打印：從頭節點開始，逐個訪問鏈表中的每個節點，直到達到鏈表的末尾。

? 創建一個頭指針，遍歷一遍鏈表，每遍歷一個節點，將這個節點的數據打印出來；

// 單鏈表打印
void SListPrint(SListNode* plist) {SListNode* head = plist;while (head != NULL) // 遍歷鏈表直到NULL{printf("%d->", head->data);head = head->next;}printf("NULL\n");}

單鏈表的刪除：刪除鏈表中的指定節點，需要修改前一個節點的指針域以繞過被刪除的節點。
單鏈表的頭刪：

? ? ? 斷言確保頭指針地址有效，以及頭指針不為空，將頭指針保存好，然后將頭指針置為頭指針的下一個位置，再將保存的指針釋放，并置為空

// 單鏈表頭刪
void SListPopFront(SListNode** pplist) {assert(pplist);assert(*pplist);SListNode* start = *pplist;*pplist = (*pplist)->next;free(start);start = NULL;}
單鏈表的尾刪：

斷言確保頭指針地址有效，以及頭指針不為空，分兩種情況，

一種是頭指針下一個節點為空，直接將其釋放并置為空；

另外一種情況呢，就是設兩個指針，找尾和尾的前驅節點，然后將尾節點釋放并置為空，再將尾的前驅節點的下一個置為空

// 單鏈表的尾刪
void SListPopBack(SListNode** pplist) {assert(pplist);assert(*pplist);//暴力檢查是否為空鏈表，空鏈表不能刪數據SListNode* end = *pplist;if ((*pplist)->next== NULL) {free(*pplist);*pplist = NULL;}else{//找尾SListNode* prev = *pplist;SListNode* tail = *pplist;while (tail->next != NULL){prev = tail;tail = tail->next;}free(tail);tail = NULL;prev->next = NULL;//假如只有一個節點這里就會非法訪問}}
單鏈表元素的查找：根據給定的值或位置查找鏈表中的節點。

? ? ? ? 創建一個節點start將頭節點指針復制一個副本，然后再指針不為空時不斷將其指向下一個的同時，看看該節點的值與所要查找的值是否相等，相等返回該節點的結構體指針，當遍歷完鏈表還沒有找到，返回NULL；

// 單鏈表查找
SListNode* SListFind(SListNode* plist, SLTDateType x) {SListNode* start = plist;while (start != NULL) {if (start->data == x)return start;start = start->next;}return NULL;
}

單鏈表的鏈表銷毀：

? ? ? ?先判斷頭指針是否為空，為空直接返回，不為空時創建一個start頭指針儲存頭節點，再通過start遍歷整個鏈表，在遍歷過程中，將每一個節點釋放掉，最后再將頭節點釋放，置為空；

//銷毀鏈表
void SLTDestroy(SListNode** pphead) {if (*pphead == NULL) {return;}else {SListNode* start = *pphead;while (start != NULL) {SListNode* ne = start->next;free(start);start = ne;}free(*pphead);*pphead = NULL;}
}
驗證：

我們再創建一個main的測試函數測試一下我們實現的單鏈表的各個功能有沒有問題：

完整代碼：
slist.h
#pragma once
// slist.h
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<stdbool.h>
#include<assert.h>
typedef int SLTDateType;
typedef struct SListNode
{SLTDateType data;struct SListNode* next;
}SListNode;// 動態申請一個節點
SListNode* BuySListNode(SLTDateType x);
// 單鏈表打印
void SListPrint(SListNode* plist);
// 單鏈表尾插
void SListPushBack(SListNode** pplist, SLTDateType x);
// 單鏈表的頭插
void SListPushFront(SListNode** pplist, SLTDateType x);
// 單鏈表的尾刪
void SListPopBack(SListNode** pplist);
// 單鏈表頭刪
void SListPopFront(SListNode** pplist);
// 單鏈表查找
SListNode* SListFind(SListNode* plist, SLTDateType x);
// 單鏈表在pos位置之后插入x
// 分析思考為什么不在pos位置之前插入
void SListInsertAfter(SListNode* pos, SLTDateType x);
// 單鏈表刪除pos位置之后的值
// 分析思考為什么不刪除pos位置？
void SListEraseAfter(SListNode* pos);// 在pos的前面插入
void SLTInsert(SListNode** pphead, SListNode* pos, SLTDateType x);
// 刪除pos位置
void SLTErase(SListNode** pphead, SListNode* pos);
void SLTDestroy(SListNode** pphead);
slist.c
#include "slist.h"
// 動態申請一個節點
SListNode* BuySListNode(SLTDateType x) {SListNode* newnode = (SListNode*)malloc(sizeof(SListNode));if (newnode == NULL) {perror("malloc fail");return NULL;}newnode->data = x;newnode->next = NULL;return newnode;
}
// 單鏈表打印
void SListPrint(SListNode* plist) {SListNode* head = plist;while (head != NULL) {printf("%d->", head->data);head = head->next;}printf("NULL\n");}
// 單鏈表尾插
void SListPushBack(SListNode** pplist, SLTDateType x) {assert(pplist);SListNode* newnode = BuySListNode(x);SListNode* end = *pplist;if (*pplist != NULL) {while (end->next != NULL)end = end->next;end->next = newnode;}else {*pplist = newnode;}
}
// 單鏈表的頭插
void SListPushFront(SListNode** pplist, SLTDateType x) {assert(pplist);SListNode* newnode = BuySListNode(x);//SListNode* start = *pplist;newnode->next = *pplist;*pplist = newnode;}
// 單鏈表的尾刪
void SListPopBack(SListNode** pplist) {assert(pplist);assert(*pplist);//暴力檢查是否為空鏈表，空鏈表不能刪數據SListNode* end = *pplist;if ((*pplist)->next== NULL) {free(*pplist);*pplist = NULL;}else{//找尾SListNode* prev = *pplist;SListNode* tail = *pplist;while (tail->next != NULL){prev = tail;tail = tail->next;}free(tail);tail = NULL;prev->next = NULL;//假如只有一個節點這里就會非法訪問}}
// 單鏈表頭刪
void SListPopFront(SListNode** pplist) {assert(pplist);assert(*pplist);SListNode* start = *pplist;*pplist = (*pplist)->next;free(start);start = NULL;}
// 單鏈表查找
SListNode* SListFind(SListNode* plist, SLTDateType x) {SListNode* start = plist;while (start != NULL) {if (start->data == x)return start;start = start->next;}return NULL;
}
// 單鏈表在pos位置之后插入xvoid SListInsertAfter(SListNode* pos, SLTDateType x) {assert(pos);/*SListNode* pre = pos;*/SListNode* newnode = BuySListNode(x);SListNode* ne = pos->next;pos->next = newnode;newnode->next = ne;}
// 單鏈表刪除pos位置之后的值void SListEraseAfter(SListNode* pos) {assert(pos);assert(pos->next);SListNode* pre = pos;SListNode* ne = pos->next->next;free(pos->next);pos->next = ne;
}// 在pos的前面插入
void SLTInsert(SListNode** pphead, SListNode* pos, SLTDateType x) {assert(pphead);assert(*pphead);assert(pos);if (*pphead == pos)SListPushFront(pphead, x);else {SListNode* ne = pos;SListNode* newnode = BuySListNode(x);SListNode* start = *pphead;while (start->next != pos) {start = start->next;if (start == NULL) {assert(0);return;}}start->next = newnode;newnode->next = ne;}}
// 刪除pos位置
void SLTErase(SListNode** pphead, SListNode* pos) {assert(pphead);assert(*pphead);assert(pos);if (pos == *pphead)SListPopFront(pphead);else {SListNode* start = *pphead;while (start->next != pos) {start = start->next;if (start == NULL) {assert(0);return;}}start->next = pos ->next;free(pos);pos = NULL;}
}
void SLTDestroy(SListNode** pphead) {if (*pphead == NULL) {free(pphead); pphead = NULL;}else {SListNode* start = *pphead;while (start != NULL) {SListNode* ne = start->next;free(start);start = ne;}*pphead = NULL;}
}
test.c
#include "slist.h"int main() {SListNode* head = NULL; // 尾插SListPushBack(&head, 1);SListPushBack(&head, 2);SListPushBack(&head, 3);printf("鏈表內容（尾插入后）：");SListPrint(head);// 頭插SListPushFront(&head, 0);printf("鏈表內容（頭插入后）：");SListPrint(head);// 查找SListNode* found = SListFind(head, 2);if (found) {printf("找到節點：%d\n", found->data);}else {printf("未找到節點\n");}// 頭刪SListPopFront(&head);printf("鏈表內容（頭刪后）：");SListPrint(head);// 尾刪SListPopBack(&head);printf("鏈表內容（尾刪后）：");SListPrint(head);// pos插入SListInsertAfter(head, 4); printf("鏈表內容（插入4后）：");SListPrint(head);// pos刪除SLTErase(&head, head->next);printf("鏈表內容（刪除第二個節點后）：");SListPrint(head);// 銷毀SLTDestroy(&head);//destroy后不能再訪問// printf("鏈表內容（銷毀后）：");//SListPrint(head); return 0;
}
總結：

? ? ? ?本篇關于單鏈表的講解到這里就結束啦，后續小編會帶來更多精彩實用的內容，對你有幫助的可以點個贊，歡迎各位隊列交流學習

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

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

相關文章

XSS靶場實戰（工作wuwuwu）

XSS靶場實戰（工作wuwuwu）

knoxss knoxss Single Reflection Using QUERY of URL ——01 測試標簽 <script>alert(666666)</script>——02: " <h1>test</h1>沒有反應&#xff0c;查看源碼 現在需要閉合雙引號&#xff0c;我計劃還是先搞標簽 "><h1>tes…
閱讀更多...
基于 BERT 微調一個意圖識別（Intent Classification）模型

基于 BERT 微調一個意圖識別（Intent Classification）模型

基于 BERT 微調一個意圖識別&#xff08;Intent Classification&#xff09;模型&#xff0c;你的意圖類別包括&#xff1a; 查詢天氣獲取新聞咨詢想聽音樂想添加備忘查詢備忘獲取家政服務結束對話增加音量減小音量其他 具體實現步驟&#xff08;詳細版&#xff09; 1. 準備你…
閱讀更多...
SSM書籍管理（環境搭建）

SSM書籍管理（環境搭建）

整合SSM&#xff1a;SpringSpringMVCMybatis 環境要求&#xff1a;IDEA、MySQL5、Tomcat9、Maven3 數據庫搭建 數據庫準備以下數據用于后續實驗&#xff1a;創建一個ssmbuild數據庫&#xff0c;表books&#xff0c;該表有4個字段&#xff0c;并且插入3條數據用于后續。 CRE…
閱讀更多...
API文檔生成與測試工具推薦

API文檔生成與測試工具推薦

在API開發過程中&#xff0c;文檔的編寫和維護是一項重要但繁瑣的工作。為了提高效率&#xff0c;許多開發者會選擇使用API文檔自動生成工具或具備API文檔生成功能的API門戶產品。選擇能導入API文檔的工具生成測試腳本, 本文將全面梳理市面上符合OpenAPI 3.0規范的文檔生成工具…
閱讀更多...
linux修改環境變量

linux修改環境變量

添加環境變量注意事項。 vim ~/.bashrc 添加環境變量時&#xff0c;需要source ~/.bashrc后才能有效。同時只對當前shell窗口有效&#xff0c;當打開另外的shell窗口時&#xff0c;需要重新source才能起效。 1.修改bashrc文件后 2.source后打開另一個shell窗口則無效&#xff…
閱讀更多...
springboot項目中，MySQL數據庫轉達夢數據庫

springboot項目中，MySQL數據庫轉達夢數據庫

前言 前段時間&#xff0c;公司要求要把某幾個項目的數據庫換成達夢數據庫&#xff0c;說是為了國產化。我就挺無語的&#xff0c;三四年的項目了&#xff0c;現在說要換數據庫。我一開始以為這個達夢數據庫應該是和TIDB差不多的。 我之前做的好幾個項目部署到測試服、正式服…
閱讀更多...
【Quest開發】透視環境下摳出身體并能遮擋身體上的服裝

【Quest開發】透視環境下摳出身體并能遮擋身體上的服裝

軟件&#xff1a;Unity 2022.3.51f1c1、vscode、Meta XR All in One SDK V72 硬件&#xff1a;Meta Quest3 僅針對urp管線 博主搞這個主要是想做現實里的人的變身功能&#xff0c;最后效果如下 可以看到雖然身體是半透明的&#xff0c;但是裙子依舊被完全遮擋了 原理是參考…
閱讀更多...
前端安全中的XSS（跨站腳本攻擊）

前端安全中的XSS（跨站腳本攻擊）

XSS 類型 存儲型 XSS 特征&#xff1a;惡意腳本存儲在服務器&#xff08;如數據庫&#xff09;&#xff0c;用戶訪問受感染頁面時觸發。場景&#xff1a;用戶評論、論壇帖子等持久化內容。影響范圍&#xff1a;所有訪問該頁面的用戶。 反射型 XSS 特征&#xff1a;惡意腳本通過…
閱讀更多...
（第三篇）Springcloud之Ribbon負載均衡

（第三篇）Springcloud之Ribbon負載均衡

一、簡介 1、介紹 Spring Cloud Ribbon是Netflix發布的開源項目&#xff0c;是基于Netflix Ribbon實現的一套客戶端負載均衡的工具。主要功能是提供客戶端的軟件負載均衡算法&#xff0c;將Netflix的中間層服務連接在一起。Ribbon客戶端組件提供一系列完善的配置項如連接超時&…
閱讀更多...
大模型——使用coze搭建基于DeepSeek大模型的智能體實現智能客服問答

大模型——使用coze搭建基于DeepSeek大模型的智能體實現智能客服問答

大模型——使用coze搭建基于DeepSeek大模型的智能體實現智能客服問答 本章實驗完全依托于coze在線平臺，不需要本地部署任何應用。 實驗介紹 1.coze介紹 扣子（coze）是新一代 AI 應用開發平臺。無論你是否有編程基礎，都可以在扣子上快速搭建基于大模型的各類 AI 應用，并…
閱讀更多...
【計算機視覺】目標檢測：深度解析YOLOv9：下一代實時目標檢測架構的創新與實戰

【計算機視覺】目標檢測：深度解析YOLOv9：下一代實時目標檢測架構的創新與實戰

深度解析YOLOv9&#xff1a;下一代實時目標檢測架構的創新與實戰 架構演進與技術創新YOLOv9的設計哲學核心創新解析1. 可編程梯度信息&#xff08;PGI&#xff09;2. 廣義高效層聚合網絡&#xff08;GELAN&#xff09;3. 輕量級設計 環境配置與快速開始硬件需求建議詳細安裝步驟…
閱讀更多...
【SpringBoot】基于MybatisPlus的博客管理系統（1）

【SpringBoot】基于MybatisPlus的博客管理系統（1）

1.準備工作 1.1數據庫 -- 建表SQL create database if not exists java_blog_spring charset utf8mb4;use java_blog_spring; -- 用戶表 DROP TABLE IF EXISTS java_blog_spring.user_info; CREATE TABLE java_blog_spring.user_info(id INT NOT NULL AUTO_INCREMENT,user_na…
閱讀更多...
貴族運動項目有哪些·棒球1號位

貴族運動項目有哪些·棒球1號位

10個具有代表性的貴族運動&#xff1a; 高爾夫 馬術 網球 帆船 擊劍 斯諾克 冰球 私人飛機駕駛 深海潛水 馬球 貴族運動通常指具有較高參與成本、歷史底蘊或社交屬性的運動&#xff0c;而棒球作為一項大眾化團隊運動&#xff0c;與典型貴族運動的結合較為罕見。從以下幾個角度探…
閱讀更多...
【Tauri2】035——sql和sqlx

【Tauri2】035——sql和sqlx

前言 這篇就來看看插件sql SQL | Taurihttps://tauri.app/plugin/sql/ 正文 準備 添加依賴 tauri-plugin-sql {version "2.2.0",features ["sqlite"]} features可以是mysql、sqlite、postsql 進去features看看 sqlite ["sqlx/sqlite&quo…
閱讀更多...
全鏈路自動化AIGC內容工廠：構建企業級智能內容生產系統

全鏈路自動化AIGC內容工廠：構建企業級智能內容生產系統

一、工業化AIGC系統架構 1.1 生產流程設計 [需求輸入] → [創意生成] → [多模態生產] → [質量審核] → [多平臺分發] ↑ ↓ ↑ [用戶反饋] ← [效果分析] ← [數據埋點] ← [內容投放] 1.2 技術指標要求 指標 標準值 實現方案 單日產能 1,000,000 分布式推理集群 內容合規率…
閱讀更多...
是否想要一個桌面哆啦A夢的寵物

是否想要一個桌面哆啦A夢的寵物

是否想擁有一個在指定時間喊你的桌面寵物呢&#xff08;手動狗頭&#xff09; 如果你有更好的想法&#xff0c;歡迎提出你的想法。 是否考慮過跟開發者一對一&#xff0c;提出你的建議&#xff08;狗頭&#xff09;。 https://wwxc.lanzouo.com/idKnJ2uvq11c 密碼:bbkm
閱讀更多...
Unity AI-使用Ollama本地大語言模型運行框架運行本地Deepseek等模型實現聊天對話（二）

Unity AI-使用Ollama本地大語言模型運行框架運行本地Deepseek等模型實現聊天對話（二）

一、使用介紹 官方網頁&#xff1a;Ollama官方網址 中文文檔參考&#xff1a;Ollama中文文檔 相關教程&#xff1a;Ollama教程 使用版本&#xff1a;Unity 2022.3.53f1c1、Ollama 0.6.2 示例模型&#xff1a;llama3.2 二、運行示例 三、使用步驟 1、創建Canvas面板 具體…
閱讀更多...
從 BERT 到 GPT：Encoder 的 “全局視野” 如何喂飽 Decoder 的 “逐詞糾結”

從 BERT 到 GPT：Encoder 的 “全局視野” 如何喂飽 Decoder 的 “逐詞糾結”

當 Encoder 學會 “左顧右盼”&#xff1a;Decoder 如何憑 “單向記憶” 生成絲滑文本&#xff1f; 目錄 當 Encoder 學會 “左顧右盼”&#xff1a;Decoder 如何憑 “單向記憶” 生成絲滑文本&#xff1f;引言一、Encoder vs Decoder&#xff1a;核心功能與基礎架構對比1.1 本…
閱讀更多...
數據結構入門：詳解順序表的實現與操作

數據結構入門：詳解順序表的實現與操作

目錄 1.線性表 2.順序表 2.1概念與結構 2.2分類 2.2.1靜態順序表 2.2.2動態順序表 3.動態順序表的實現 3.1.SeqList.h 3.2.SeqList.c 3.2.1初始化 3.2.2銷毀 3.2.3打印 3.2.4順序表擴容 3.2.5尾部插入及尾部刪除 3.2.6頭部插入及頭部刪除 3.2.7特定位置插入…
閱讀更多...
LeetCode熱題100--53.最大子數組和--中等

LeetCode熱題100--53.最大子數組和--中等

1. 題目 給你一個整數數組 nums &#xff0c;請你找出一個具有最大和的連續子數組&#xff08;子數組最少包含一個元素&#xff09;&#xff0c;返回其最大和。 子數組是數組中的一個連續部分。 示例 1&#xff1a; 輸入&#xff1a;nums [-2,1,-3,4,-1,2,1,-5,4] 輸出&…
閱讀更多...
最新文章

Copyright @ 2022~2023