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

本文是小編鞏固自身而作，如有錯誤，歡迎指出！

1.鏈表的概念

概念：鏈表是?種物理存儲結構上?連續、?順序的存儲結構，數據元素的邏輯順序是通過鏈表中的 指針鏈接次序實現的。

和之前的順序表不同，順序一般通過數組實現，每個儲存的元素都是相鄰的，而鏈表不一樣，鏈表的每一個節點并不相連，而是通過鏈表內的指針進行相連，每一個節點可以分為兩個部分，儲存的數據和指向下一個節點的地址。

2.鏈表的性質

1、鏈式機構在邏輯上是連續的，在物理結構上不?定連續

?2、結點?般是從堆上申請的

?3、從堆上申請來的空間，是按照?定策略分配出來的，每次申請的空間可能連續，可能不連續

?

我們在此用結構體創建鏈表的原型

//定義鏈表結構
typedef int sldatatype;
struct slistnode
{sldatatype data;//儲存的數據struct slistnode* next;//指向下一個節點
};
typedef struct slistnode SLTNODE;

?然后我們創建一個簡單的鏈表

void test01()
{SLTNODE* node1 = (SLTNODE*)malloc(sizeof(SLTNODE));SLTNODE* node2 = (SLTNODE*)malloc(sizeof(SLTNODE));SLTNODE* node3 = (SLTNODE*)malloc(sizeof(SLTNODE));SLTNODE* node4 = (SLTNODE*)malloc(sizeof(SLTNODE));node1->data = 1;node2->data = 2;node3->data = 3;node4->data = 4;node1->next = node2;node2->next = node3;node3->next = node4;node4->next = NULL;
}

3.鏈表的打印?

我們現在看看鏈表的打印是怎么實現的

先前我們學習順序表時我們打印時可以直接將指向元素的地址向后挪，而鏈表每一個節點之間是相互獨立的，因此我們只能過通過指針之間的鏈接進行打印

void sltprint(SLTNODE* phead)
{SLTNODE* pcur = phead;while (pcur){printf("%d -> ", pcur->data);pcur = pcur->next;}printf("NULL\n");
}

在這個代碼中，我們將每一個節點通過指針的方式進行鏈式訪問。

4.鏈表的頭插尾插

4.1鏈表的節點創建

要想要在鏈表中插入數值，就不能跟循序表一樣進行數據的移動完成，而要通過創立新的節點

SLTNODE* sltbuynode(sldatatype x)
{//創建新的節點SLTNODE* newnode = (SLTNODE*)malloc(sizeof(SLTNODE));if (newnode == NULL){perror("malloc fail");exit(1);}newnode->data = x;newnode->next = NULL;return newnode;
}

4.2鏈表的尾插

其中的思路就是在鏈表尾部加入一個新的節點

oid sltpushback(SLTNODE** pphead, sldatatype x)
{SLTNODE* newnode= sltbuynode(x);if (*pphead == NULL)//鏈表為空{*pphead = newnode;}else{SLTNODE* ptail = *pphead;while (ptail->next){ptail = ptail->next;}ptail->next = newnode;}}

?其中一個要注意的點當鏈表為空時，就直接將其作為頭節點即可，還有一個值得思考的問題即為什么這里使用了二級指針？

其原因在于如果傳過去的是節點，其中形參的改變并不會影響實參，即整個函數運行結束后，仍不會改變原來的節點

4.3鏈表的頭插?

void sltpushfrond(SLTNODE** pphead, sldatatype x)
{assert(*pphead);SLTNODE* newnode = sltbuynode(x);newnode->next = *pphead;*pphead = newnode;//讓指向第一個節點的位置變化
}

不如尾插還需要遍歷，頭插只需要將 創建的新節點指向的位置改為之前的頭結點即可

5.鏈表的頭刪與尾刪

5.1尾刪

void sltpopback(SLTNODE** pphead)
{assert(pphead && *pphead);//只有一個節點if ((*pphead)->next == NULL){free(*pphead);*pphead = NULL;}else {SLTNODE* prev = NULL;SLTNODE* ptail = *pphead;while (ptail->next){prev = ptail;ptail = ptail->next;}prev->next = NULL;free(ptail);ptail = NULL;}
}

?思路與尾插相同，把尾部的最后一個節點釋放，并將其前一個節點的指向位置改為空指針即可

就是要考慮到一開始就只有一個節點的情況

5.2頭刪

void sltpopfront(SLTNODE** pphead)
{assert(pphead && *pphead);SLTNODE* next = (*pphead)->next;free(*pphead);*pphead=next;
}

直接將第一個節點釋放?，并將頭節點的地址改為第二個節點的地址

6.單鏈表的查找

SLTNODE* sltfind(SLTNODE* phead, sldatatype x)
{SLTNODE* pcur = phead;while (pcur){if (pcur->data == x){return pcur;}pcur = pcur->next;}return NULL;
}

?其主要思路就是將整個鏈表遍歷找出值相同的節點，找到了就返回節點地址，沒找到就返回NULL

7.鏈表的在任意節點的插值

7.1在位置前插值

void sltinsert(SLTNODE** pphead, SLTNODE* pos, sldatatype x)
{assert(pphead && pos);//指向第一個節點時if (pos == *pphead){sltpushfrond(*pphead,x);}SLTNODE* newnode = sltbuynode(x);SLTNODE* prev = *pphead;while (prev->next != pos){prev = prev->next;}prev->next = newnode;newnode->next = pos;
}

先遍歷鏈表找到插值位置的前一個節點，?并將其指向的節點改變成插入的節點，并將插入的節點指向的位置設置為下一個節點

7.2在位置后插值

void sltinsertafter(SLTNODE* pos, sldatatype x)
{assert(pos);SLTNODE* newnode = sltbuynode(x);newnode->next = pos->next;pos->next = newnode;
}

直接改變兩個指向地址即可

8.鏈表的刪除

8.1指定位置的刪除

void slterase(SLTNODE** pphead, SLTNODE* pos)
{assert(pphead && pos);//pos頭結點if (pos == *pphead){sltpopfront(*pphead);}else {SLTNODE* prev = *pphead;while (prev->next != pos){prev = prev->next;}prev->next = pos->next;free(pos);pos = NULL;}
}

?其思路與插入相似，即將上一個節點的指向位置指向下一個節點即可，然后將原本的節點釋放

8.2指定位置后一個數的刪除

void slteraseafter(SLTNODE* pos)
{assert(pos&&pos->next);SLTNODE* del = pos->next;pos->next = del->next;free(del);del = NULL;
}

不需要遍歷，直接改變本身的指向位置即可?


9.鏈表的銷毀

void slistdestory(SLTNODE** pphead)
{SLTNODE* pcur = *pphead;while (pcur){SLTNODE* next = pcur->next;free(pcur);pcur = next;}*pphead = NULL;
}

利用循環將每一個節點依次釋放，并將首節點置空即可。

10.完整代碼實現

頭文件

#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>//定義鏈表結構
typedef int sldatatype;
struct slistnode
{sldatatype data;//儲存的數據struct slistnode* next;//指向下一個節點
};
typedef struct slistnode SLTNODE;
void sltprint(SLTNODE* phead);//打印鏈表
void sltpushback(SLTNODE** pphead, sldatatype x);//尾插
SLTNODE* sltbuynode(sldatatype x);//創建新的節點
void sltpushfrond(SLTNODE** pphead, sldatatype x);//頭插
void sltpopback(SLTNODE** pphead);//尾刪
void sltpopfront(SLTNODE** pphead);//頭刪
SLTNODE* sltfind(SLTNODE* phead, sldatatype x);//查找
void sltinsert(SLTNODE** pphead, SLTNODE* pos, sldatatype x);//在指定數據前插入數據
void sltinsertafter( SLTNODE* pos, sldatatype x);//在指定數據后插入數據
void slterase(SLTNODE** pphead, SLTNODE* pos);//刪除pos節點
void slteraseafter(SLTNODE* pos);//刪除pos的下一個節點
void slistdestory(SLTNODE** pphead);//銷毀鏈表

源文件

#define _CRT_SECURE_NO_WARNINGS
#include"single_list.h"void sltprint(SLTNODE* phead)
{SLTNODE* pcur = phead;while (pcur){printf("%d -> ", pcur->data);pcur = pcur->next;}printf("NULL\n");
}
SLTNODE* sltbuynode(sldatatype x)
{//創建新的節點SLTNODE* newnode = (SLTNODE*)malloc(sizeof(SLTNODE));if (newnode == NULL){perror("malloc fail");exit(1);}newnode->data = x;newnode->next = NULL;return newnode;
}
void sltpushback(SLTNODE** pphead, sldatatype x)
{SLTNODE* newnode= sltbuynode(x);if (*pphead == NULL)//鏈表為空{*pphead = newnode;}else{SLTNODE* ptail = *pphead;while (ptail->next){ptail = ptail->next;}ptail->next = newnode;}}
void sltpushfrond(SLTNODE** pphead, sldatatype x)
{assert(*pphead);SLTNODE* newnode = sltbuynode(x);newnode->next = *pphead;*pphead = newnode;//讓指向第一個節點的位置變化
}
void sltpopback(SLTNODE** pphead)
{assert(pphead && *pphead);//只有一個節點if ((*pphead)->next == NULL){free(*pphead);*pphead = NULL;}else {SLTNODE* prev = NULL;SLTNODE* ptail = *pphead;while (ptail->next){prev = ptail;ptail = ptail->next;}prev->next = NULL;free(ptail);ptail = NULL;}
}
void sltpopfront(SLTNODE** pphead)
{assert(pphead && *pphead);SLTNODE* next = (*pphead)->next;free(*pphead);*pphead=next;
}
SLTNODE* sltfind(SLTNODE* phead, sldatatype x)
{SLTNODE* pcur = phead;while (pcur){if (pcur->data == x){return pcur;}pcur = pcur->next;}return NULL;
}
void sltinsert(SLTNODE** pphead, SLTNODE* pos, sldatatype x)
{assert(pphead && pos);//指向第一個節點時if (pos == *pphead){sltpushfrond(*pphead,x);}SLTNODE* newnode = sltbuynode(x);SLTNODE* prev = *pphead;while (prev->next != pos){prev = prev->next;}prev->next = newnode;newnode->next = pos;
}
void sltinsertafter(SLTNODE* pos, sldatatype x)
{assert(pos);SLTNODE* newnode = sltbuynode(x);newnode->next = pos->next;pos->next = newnode;
}
void slterase(SLTNODE** pphead, SLTNODE* pos)
{assert(pphead && pos);//pos頭結點if (pos == *pphead){sltpopfront(*pphead);}else {SLTNODE* prev = *pphead;while (prev->next != pos){prev = prev->next;}prev->next = pos->next;free(pos);pos = NULL;}
}
void slteraseafter(SLTNODE* pos)
{assert(pos&&pos->next);SLTNODE* del = pos->next;pos->next = del->next;free(del);del = NULL;
}
void slistdestory(SLTNODE** pphead)
{SLTNODE* pcur = *pphead;while (pcur){SLTNODE* next = pcur->next;free(pcur);pcur = next;}*pphead = NULL;
}

測試文件

#define _CRT_SECURE_NO_WARNINGS
#include"single_list.h"
void test01()
{SLTNODE* node1 = (SLTNODE*)malloc(sizeof(SLTNODE));SLTNODE* node2 = (SLTNODE*)malloc(sizeof(SLTNODE));SLTNODE* node3 = (SLTNODE*)malloc(sizeof(SLTNODE));SLTNODE* node4 = (SLTNODE*)malloc(sizeof(SLTNODE));node1->data = 1;node2->data = 2;node3->data = 3;node4->data = 4;node1->next = node2;node2->next = node3;node3->next = node4;node4->next = NULL;SLTNODE* plist = node1;sltprint(plist);}
void test02()
{SLTNODE* plist = NULL;//創建空鏈表sltpushback(&plist, 1);sltpushback(&plist, 1);sltpushback(&plist, 2);sltpushback(&plist, 4);sltpushback(&plist, 3);sltpushfrond(&plist, 5);sltpopfront(&plist);sltpopback(&plist);sltprint(plist);SLTNODE* find= sltfind(plist, 4);/*if (find){printf("找到了\n");}else{printf("未找到\n");}*//*sltinsert(&plist, find, 100);*/sltinsertafter(find, 50);//slterase(&plist, find);/*slteraseafter(find);*/slistdestory(&plist);sltprint(plist);
}
int main()
{test01();/*test02();*/return 0;
}

本次分享就到這里，后續會繼續更新，感謝閱讀！

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

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

相關文章

LeetCode 1128.等價多米諾骨牌對的數量：計數

LeetCode 1128.等價多米諾骨牌對的數量：計數

【LetMeFly】1128.等價多米諾骨牌對的數量&#xff1a;計數 力扣題目鏈接&#xff1a;https://leetcode.cn/problems/number-of-equivalent-domino-pairs/ 給你一組多米諾骨牌 dominoes 。 形式上&#xff0c;dominoes[i] [a, b] 與 dominoes[j] [c, d] 等價 當且僅當 (a …
閱讀更多...
以太坊智能合約開發框架：Hardhat v2 核心功能從入門到基礎教程

以太坊智能合約開發框架：Hardhat v2 核心功能從入門到基礎教程

一、設置項目 Hardhat 項目是安裝了 hardhat 包并包含 hardhat.config.js 文件的 Node.js 項目。 操作步驟&#xff1a; ①初始化 npm npm init -y②安裝 Hardhat npm install --save-dev hardhat③創建 Hardhat 項目 npx hardhat init如果選擇 Create an empty hardhat.…
閱讀更多...
安卓基礎（無障礙點擊）

安卓基礎（無障礙點擊）

無障礙點擊核心代碼 // 自定義無障礙服務類&#xff0c;繼承自Android系統的AccessibilityService public class MyAccessibilityService extends AccessibilityService {// 當系統產生無障礙事件時的回調方法&#xff08;如界面變化、焦點切換等&#xff09;Overridepublic v…
閱讀更多...
阿里云服務遷移實戰: 05-OSS遷移

阿里云服務遷移實戰: 05-OSS遷移

概述 Bucket 復制分為兩種&#xff0c;同區域復制和跨區域復制 同賬號復制比較簡單&#xff0c;根據提示填寫信息即可&#xff0c;本文主要介紹跨賬號復制。 同區域復制 授權角色選擇 “AliyunOSSRole”, 創建方法見 “跨區域復制”。然后點擊確定即可。 跨區域復制 假設我…
閱讀更多...
Qt 的信號與槽機制依賴元對象系統（Meta-Object System）實現

Qt 的信號與槽機制依賴元對象系統（Meta-Object System）實現

內部數據結構 在 Qt 中，信號和槽之間的連接主要通過 QObject 類及其相關的私有類進行管理。每個 QObject 實例都維護著一個指向其 QMetaObject 的指針，該對象包含了有關類的所有元信息，包括信號、槽等。此外，還有一個關鍵的數據結構用于存儲信號與槽之間的連接信息，即 Co…
閱讀更多...
前端面試寶典---性能優化

前端面試寶典---性能優化

一、加載優化 1. 第三方模塊放在CDN 例如 leaflet通過cdn引入&#xff0c;這樣就不會占用打包體積了 2. prefetch 預加載 例如&#xff0c;之后馬上有個場景需要一個圖片&#xff0c;我們就可以通過link 的 prefetch 對資源進行預先加載 再例如&#xff0c;我們公司是無網絡開…
閱讀更多...
從零開始：Android Studio開發購物車（第二個實戰項目）

從零開始：Android Studio開發購物車（第二個實戰項目）

一年經驗的全棧程序員&#xff0c;目前頭發健在&#xff0c;但不知道能撐多久。 文章目錄 前言 一、頁面編寫 1. 頂部標簽欄title_shopping.xml 2. 商品展現列表activity_shopping_channel.xml 3. 商品詳情頁面activity_shopping_detail.xml 4. 購物車頁面activity_shopping…
閱讀更多...
PostgteSQL for Everybody基礎部分筆記

PostgteSQL for Everybody基礎部分筆記

筆記分享內容參考密歇根大學 Charles Russell Severance 開設的PostgreSQL課程&#xff1a;postgresql-for-everybody&#xff0c;網址為&#xff1a;https://www.coursera.org/specializations/postgresql-for-everybody#courses&#xff0c;在B站等也有相關視頻分享。 我分享…
閱讀更多...
Python項目源碼63：病歷管理系統1.0（tkinter+sqlite3+matplotlib）

Python項目源碼63：病歷管理系統1.0（tkinter+sqlite3+matplotlib）

1.病歷管理系統包含以下主要功能&#xff1a; 核心功能&#xff1a;病歷信息錄入&#xff08;患者姓名、年齡、性別、診斷結果、主治醫生&#xff09;&#xff0c;自動記錄就診時間&#xff0c;病歷信息展示&#xff08;使用Treeview表格&#xff09;&#xff0c;病歷信息查詢…
閱讀更多...
MCP底層協議完整通信過程

MCP底層協議完整通信過程

2025 年是智能體的元年， 也注定是智能體集中爆發的一年！ 兩個互聯領域的重大挑戰： 第一、 Agent 與 Tools （工具）的交互 Agent 需要調用外部工具和 API
閱讀更多...
docker:制作鏡像+上傳鏡像+拉取鏡像

docker:制作鏡像+上傳鏡像+拉取鏡像

1.dockerfile制作鏡像 示例內容&#xff1a; 1.創建一個index.js的文件 console.log("hello world")2.在相同目錄下創建名為dockerfile的文件 FROM node:alpine COPY index.js /index.js CMD node /index.js3.構建鏡像 docker build -t minterra/hello-docker . …
閱讀更多...
docker制作python大模型鏡像(miniconda環境)，工程改造記錄

docker制作python大模型鏡像(miniconda環境)，工程改造記錄

**環境說明&#xff1a;**從系統鏡像開始打造python大模型鏡像&#xff0c;之前是人工手動裝的方式&#xff0c;并且模型和依賴在公網中&#xff0c;對于離線交付環境不太友好&#xff0c;所以打造的離線化交付版本 Dockerfile: FROM centos:7.9 ENV PYTHONIOENCODINGutf-8 E…
閱讀更多...
Rust中避免過度使用鎖導致性能問題的策略

Rust中避免過度使用鎖導致性能問題的策略

一、引言 在 Rust 多線程編程中&#xff0c;鎖是實現線程同步的重要工具&#xff0c;它可以防止多個線程同時訪問和修改共享數據&#xff0c;從而避免數據競爭和不一致的問題。然而&#xff0c;過度使用鎖會帶來嚴重的性能問題&#xff0c;如鎖競爭導致的線程阻塞、上下文切換…
閱讀更多...
數據結構每日一題day15（鏈表）★★★★★

數據結構每日一題day15（鏈表）★★★★★

題目描述&#xff1a;將一個帶頭結點的單鏈表A分解為兩個帶頭結點的單鏈表A和 B,使得A表中含有原表中序號為奇數的元素,而B表中含有原表中序號為偶數的元素,且保持相對順不變&#xff0c;最后返回 B 表。 算法思想&#xff1a; 1.初始化&#xff1a; 創建新鏈表 B 的頭結點。…
閱讀更多...
【雜談】-探索 NVIDIA Dynamo 的高性能架構

【雜談】-探索 NVIDIA Dynamo 的高性能架構

探索 NVIDIA Dynamo 的高性能架構 文章目錄 探索 NVIDIA Dynamo 的高性能架構1. 大規模人工智能推理的日益嚴峻的挑戰2. 使用 NVIDIA Dynamo 優化 AI 推理3. 實際應用和行業影響4. 競爭優勢&#xff1a;Dynamo 與其他方案對比5. 總結 隨著人工智能&#xff08;AI&#xff09;技…
閱讀更多...
postgresql數據庫基本操作

postgresql數據庫基本操作

1. 連接 PostgreSQL 數據庫 首先&#xff0c;使用 psql 命令行工具連接到數據庫。如果是本地連接&#xff0c;命令格式如下&#xff1a; psql -U postgres -d <數據庫名稱> -h <主機地址>其中&#xff1a; -U postgres&#xff1a;表示以 postgres 用戶身份登錄…
閱讀更多...
工業大模型：從設備診斷到工藝重構

工業大模型：從設備診斷到工藝重構

引言 工業大模型正在引發制造業認知革命。據埃森哲研究，到2026年全球工業大模型市場規模將突破280億美元，其中工藝優化應用占比達42%。本文將系統解析工業大模型的"預訓練-領域適配-應用落地"技術路徑，并通過設備健康診斷與工藝參數生成的實踐案例，展示如何構建…
閱讀更多...
PyQt5基本介紹

PyQt5基本介紹

PyQt5是基于Digia公司強大圖形框架Qt5的python接口&#xff0c;由一組python模塊構成。是一個用于創建桌面應用程序的Python庫&#xff0c;它是Qt圖形用戶界面工具包的Python綁定。 Qt是一個跨平臺的C庫&#xff0c;提供了一套豐富的工具和功能&#xff0c;用于開發圖形用戶界…
閱讀更多...
Tire 樹（字典樹/前綴樹）

Tire 樹（字典樹/前綴樹）

一、定義與結構 用來快速存儲查找字符串集合的一種數據結構 將字符串按順序連接根節點上&#xff0c;并在字符串結束的地方打上標記并計數。 二、模板題 acwing 835 Trie 樹的字符串統計 題目&#xff1a; 維護一個字符串集合&#xff0c;支持兩種操作&#xff1a; I x 向…
閱讀更多...
【時時三省】(C語言基礎)怎樣定義和引用一維數組

【時時三省】(C語言基礎)怎樣定義和引用一維數組

山不在高&#xff0c;有仙則名。水不在深&#xff0c;有龍則靈。 ----CSDN 時時三省 一維數組是數組中最簡單的&#xff0c;它的元素只需要用數組名加一個下標&#xff0c;就能唯一地確定。如上面介紹的學生成績數組s就是一維數組。有的數組&#xff0c;其元素要指定兩個下標才…
閱讀更多...
最新文章

Copyright @ 2022~2023