數據結構——鏈表2

1.2 實現單鏈表

在上一篇文章中，單鏈表的實現只有一少部分，這一篇接著來了解單鏈表剩下的接口實現。

SList.h

#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>//定義單鏈表就是定義節點，因為單鏈表是由節點組成的，所以定義單鏈表就是定義節點
typedef int SLTDataType;
//定義鏈表節點的結構
typedef struct SListNode
{SLTDataType  data;struct SListNode* next;
}SLTNode;//單鏈表的打印
void SLTPrint(SLTNode* phead);//單鏈表的尾插
void SLTPushBack(SLTNode** pphead, SLTDataType x);//單鏈表的頭插
void SLTPushFront(SLTNode** pphead, SLTDataType x);//單鏈表的尾刪
void SLTPopBack(SLTNode** pphead);//單鏈表的頭刪
void SLTPopFront(SLTNode** pphead);//單鏈表查找
SLTNode* SLTFind(SLTNode* phead, SLTDataType x);//在指定位置之前插入數據
void* SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x);//在指定位置之后插入數據
void* SLTInsertAfter(SLTNode** pphead, SLTNode* pos, SLTDataType x);//刪除pos節點
void* SLTErase(SLTNode** pphead, SLTNode* pos);//刪除pos之后的節點
void SLTEraseAfter(SLTNode* pos);//銷毀鏈表
void SLTDesTroy(SLTNode** pphead);//申請新的節點
SLTNode* SLTBuyNode(SLTDataType x);

SList.c
#include"SList.h"//單鏈表的打印
void SLTPrint(SLTNode* phead) {SLTNode* pcur = phead;while (pcur != NULL){printf("%d -> ", pcur->data);pcur = pcur->next;}printf("NULL\n");
}//新節點的申請
SLTNode* SLTBuyNode(SLTDataType x)
{SLTNode* node = (SLTNode*)malloc(sizeof(SLTNode));//申請新節點這里傳的應該是節點類型而不是數據類型//單鏈表：每次插入一個節點時，需要分配一個節點（結構體）的內存，因此使用 `sizeof(節點類型)`。//順序表：在擴容時，需要為多個數據元素分配一塊連續的內存（即數組），因此使用 `元素個數 * sizeof(數據類型)`。if (node == NULL){perror("malloc fail!\n");exit(1);}node->data = x;node->next = NULL;return node;
}//單鏈表的尾插
void SLTPushBack(SLTNode** pphead, SLTDataType x) {//單鏈表為空assert(pphead);//SLTNode* Tail = *pphead; 不能在這里定義Tail 因為這里的Tail為空，后面循環中的Tail->next 就會報錯，不會進入循環當中SLTNode* newnode = SLTBuyNode(x);if (*pphead == NULL){*pphead = newnode;}else {//單鏈表不為空，找尾節點，插入新節點SLTNode* Tail = *pphead;while (Tail->next != NULL){Tail = Tail->next;}//跳出循環，插入新節點Tail->next = newnode;//newnode->next = NULL; 不需要寫是因為，newnode在初始化的時候就已經置為NULL了}
}//單鏈表的頭插
void SLTPushFront(SLTNode** pphead, SLTDataType x)
{assert(pphead &&*pphead);//pphead 不能插入空的數據//*pphead 不能對空表進行插入SLTNode* newnode = SLTBuyNode(x);newnode->next = *pphead;*pphead = newnode;//將新的節點作為插入后鏈表的頭結點
}//單鏈表尾刪
void SLTPopBack(SLTNode** pphead)
{assert(pphead&&*pphead);//pphead--空鏈表不可以進行刪除操作// *pphead--不為空的鏈表--循環遍歷 --遍歷到尾節點的前一個節點，將此節點的next置為NULL；//只有一個節點的情況，是不能遍歷的，因為他的next->next為NULLif ((*pphead)->next == NULL) // -> 的優先級大于 * 的優先級{free(*pphead);*pphead = NULL;}else {SLTNode* Tail = *pphead;SLTNode* prev = NULL;while (Tail->next){prev = Tail;Tail = Tail->next;}//跳出循環prev->next = NULL;free(Tail);Tail = NULL;}}//單鏈表的頭刪
void SLTPopFront(SLTNode** pphead) 
{assert(pphead&&*pphead);SLTNode* next = (*pphead)->next;free(*pphead);*pphead = next;
}//單鏈表查找
SLTNode* SLTFind(SLTNode* phead, SLTDataType x) 
{SLTNode* pcur = phead;while (pcur){if (pcur->data == x){return pcur;}pcur = pcur->next;}//跳出循環return NULL;}//在指定位置之前插入數據
void* SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x) {assert(pphead && pos);//下標pos從1開始的if (pos == *pphead){//頭插SLTPushFront(pphead,x);}else {SLTNode* newnode = SLTBuyNode(x);SLTNode* prev = *pphead;while (prev->next != pos){//找到prevprev=prev->next;}newnode->next = pos;prev->next = newnode;}}//在指定位置之后插入數據
void* SLTInsertAfter(SLTNode** pphead, SLTNode* pos, SLTDataType x) {assert(pos);SLTNode* newnode = SLTBuyNode(x);newnode->next = pos->next;pos->next = newnode;//不用考慮pos->next為不為空的情況，因為assert只限制了pos//所以也不用單獨考慮當pos->next=NULL時尾插的情況，上述的//代碼包含這種情況}//刪除pos節點
void* SLTErase(SLTNode** pphead, SLTNode* pos) {assert(pphead && pos);//pos為頭結點if (pos == *pphead){//頭刪操作SLTPopFront(pphead);}//pos非頭結點else{SLTNode* prev = *pphead;while (prev->next != pos){prev = prev->next;}prev->next = pos->next;free(pos);pos = NULL;}}//刪除pos之后的節點
void SLTEraseAfter(SLTNode* pos)
{assert(pos && pos->next);SLTNode* del = pos->next;pos->next = del->next;free(del);del = NULL;
}//銷毀鏈表
void SLTDesTroy(SLTNode** pphead) {SLTNode* pcur = *pphead;while (pcur){SLTNode* next = pcur->next;free(pcur);pcur = next;}*pphead = NULL;
}

1.3 鏈表的分類

鏈表的結構多樣，有8種鏈表結構：

鏈表的具體分類：

雖然鏈表的種類有很多，但是最常用的就兩種：單鏈表和雙鏈表。

單鏈表：單向不帶頭不循環的鏈表。結構簡單，一般不會單獨用來存儲數據；實際中更多的是作為其他數據結構的子結構。

雙鏈表：雙向帶頭循環的鏈表?。結構最復雜，一般用在單獨存儲數據；實際中使用的鏈表數據結構，都是帶頭雙向循環鏈表，雖然這個結構復雜，但是在寫代碼的時候會發現結構會帶來很多優勢，實現反而會變得更加簡單。

2??雙鏈表

2.1 概念與結構

雙鏈表全稱：帶頭雙向循環鏈表

注意：

我們這里提到的 "帶頭" 跟我們前面說的 "頭結點" 是兩個概念，前面在單鏈表中的稱呼是不嚴謹的，是為了更好的理解。

而在帶頭鏈表里的頭結點，實際是 "哨兵位"，哨兵位節點不存儲任何的有效元素，只是站在這里 “放哨的”

2.2 實現雙向鏈表

List.c

#include "List.h"LTNode* buyNode(LTDataType x)
{LTNode* node=(LTNode*)malloc(sizeof(LTNode));node->data = x;node->next = node->prev = node;return node;
}//初始化雙向鏈表  --- 接口一致性
LTNode* LTInit()
{////創建頭結點//LTNode* phead = (LTNode*)malloc(sizeof(LTNode));//phead->data = -1;    //頭結點是無效的數據，隨便存放一數值就ok//phead->next = phead->prev = phead;   //指向自己代表是雙向的LTNode* phead = buyNode(-1);return phead;}//void LTInit(LTNode** pphead)
//{
//	assert(pphead);
//	*pphead = (LTNode*)malloc(sizeof(LTNode));
//	(*pphead)->data = -1;
//	(*pphead)->next = (*pphead)->prev = *pphead;
//}//銷毀
void LTDesTroy(LTNode* phead)
{LTNode* pcur = phead->next;while (pcur != phead){LTNode* next = pcur->next;free(pcur);pcur = next;}free(phead);phead = NULL;}//打印
void LTPrint(LTNode* 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);LTNode* newnode = buyNode(x);//phead phead->prev newnodenewnode->prev = phead->prev;newnode->next = phead;phead->prev->next = newnode;phead->prev = newnode;
}//頭插
void LTPushFront(LTNode* phead, LTDataType x)
{assert(phead);//phead newnode phead->nextLTNode* newnode = buyNode(x);phead->next->prev = newnode;newnode->next = phead->next;phead->next = newnode;newnode->prev = phead;}//判空
bool LTEmpty(LTNode* phead)
{assert(phead);return phead->next == phead;//等于     true   為空//不等于   false  不為空}//尾刪
void LTPopBack(LTNode* phead)
{assert(!LTEmpty(phead));//為空    true  ---  ！true=false 報錯//不為空  false ---  ！false=true 繼續執行LTNode* del = phead->prev;//phead phead->prev->prev phead->prevdel->prev->next = phead;phead->prev = del->prev;free(del);del = NULL;
}
//頭刪 刪除的是頭結點的下一個結點
void LTPopFront(LTNode* phead)
{assert(!LTEmpty(phead));//phead phead->next phead->next->nextLTNode* next = phead->next;next->next->prev = phead;phead->next = next->next;free(next);next = NULL;}//查找指定元素
LTNode* LTFind(LTNode* phead, LTDataType x)
{LTNode* pcur = phead->next;while (pcur != phead){if (pcur->data == x){return pcur;}pcur = pcur->next;}return NULL;
}
//在pos之后插入數據
void LTInsert(LTNode* pos, LTDataType x)
{assert(pos);//pos為空就是在雙向鏈表中沒有找到x，就不能進行插入操作LTNode* newnode = buyNode(x);//pos newnode pos->nextpos->next->prev = newnode;newnode->next = pos->next;pos->next = newnode;newnode->prev = pos;}
//刪除在pos位置的數據
void LTErase(LTNode* pos)
{assert(pos);//pos 為空不可刪除 為空找不到該元素//pos->prev pos pos->nextpos->prev->next = pos->next;pos->next->prev = pos->prev;free(pos);pos = NULL;
}

3. 順序表與鏈表的分析

不同點順序表鏈表（單鏈表）
存儲空間物理上一定連續邏輯上連續，但物理上不一定連續
隨機訪問支持：O(1)不支持：O(N)
任意位置插入或者刪除元素可能需要搬移元素，效率低：O(N)只需要修改指針指向
插入動態順序表，空間不夠是需要擴容和空間浪費沒有容量的概念，按需申請釋放，不存在空間浪費
應用場景元素高效存儲+頻繁訪問任意位置高效插入和刪除

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

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

相關文章

Windows和Linux應急響應以及IP封堵

Windows和Linux應急響應以及IP封堵

目錄 1、Windows入侵排查思路 1.1 檢查系統賬號安全 1.2 檢查異常端口、進程 1.3 檢查啟動項、計劃任務、服務 1.4 檢查系統相關信息 1.5 自動化查殺 1.6 日志分析 系統日志分析 Web 訪問日志 2、Linux 入侵排查思路 2.1 賬號安全 2.1.1、基本使用 2.1.2、入侵排查…
閱讀更多...
MIT成果登上Nature！液態神經網絡YYDS

MIT成果登上Nature！液態神經網絡YYDS

2025深度學習發論文&模型漲點之——液態神經網絡液態神經網絡&#xff08;Liquid Neural Networks&#xff0c;LNN&#xff09;是一種受生物神經系統啟發的連續時間遞歸神經網絡&#xff08;RNN&#xff09;&#xff0c;其核心創新在于將靜態神經網絡轉化為由微分方程驅動的…
閱讀更多...
AI 對話高效輸入指令攻略（四）：AI+Apache ECharts：生成各種專業圖表

AI 對話高效輸入指令攻略（四）：AI+Apache ECharts：生成各種專業圖表

- **AI與數據可視化的革命性結合**：介紹AI如何降低數據可視化門檻，提升效率。 - **Apache ECharts：專業可視化的利器**：使用表格對比展示ECharts的特點、優勢和適用場景。 - **四步實現AI驅動圖表生成**：通過分步指南講解從環境準備到圖表優化的全流程，包含多個代碼示例及…
閱讀更多...
vue2 基礎學習 day04 （結構/樣式/邏輯、組件通信、進階語法）下

vue2 基礎學習 day04 （結構/樣式/邏輯、組件通信、進階語法）下

一、非父子通信-event bus 事件總線1.作用非父子組件之間&#xff0c;進行簡易消息傳遞。(復雜場景→ Vuex)2.步驟創建一個都能訪問的事件總線 &#xff08;空Vue實例&#xff09;import Vue from vue const Bus new Vue() export default BusA組件&#xff08;接受方&#xf…
閱讀更多...
ubuntu 20.04 C和C++的標準頭文件都放在哪個目錄？

ubuntu 20.04 C和C++的標準頭文件都放在哪個目錄？

在 Ubuntu 20.04 中&#xff0c;C 和 C 標準頭文件的存放目錄主要由編譯器&#xff08;如 GCC&#xff09;的安裝路徑決定&#xff0c;通常分為以下兩類&#xff1a;?1. C 標準頭文件?C 語言的標準頭文件&#xff08;如 <stdio.h>、<stdlib.h> 等&#xff09;默認…
閱讀更多...
change和watch

change和watch

是的&#xff0c;你理解得很對&#xff01; change 與 v-model 的結合&#xff1a;change 事件通常用于監聽 表單元素的變化&#xff0c;但它并不一定意味著值發生了變化。它主要是當 用戶與輸入框交互時&#xff08;如點擊選項、選擇文本框內容、提交表單等&#xff09;觸發的…
閱讀更多...
分布式微服務--GateWay(1)

分布式微服務--GateWay(1)

一、什么是微服務網關&#xff08;API Gateway&#xff09; 定義&#xff1a;微服務網關是整個系統請求的統一入口&#xff0c;負責請求轉發、過濾處理、安全校驗等。 作用&#xff1a; 請求路由 日志記錄 權限控制 參數校驗 解決跨域問題 黑白名單控制 限流、熔斷、降級…
閱讀更多...
大文件斷點續傳（vue+springboot+mysql）

大文件斷點續傳（vue+springboot+mysql）

斷點續傳vue前端代碼后端代碼controller 層service層持久層主表&#xff0c;初始化單次上傳文件表&#xff0c;單次上傳所有的文件記錄文件分塊表科普信息參考其他博主 流程圖 vue前端代碼 這里是只做了demo示例&#xff0c;主線測試沒什么問題&#xff0c;前端同學可參考修…
閱讀更多...
Nodejs》》MySql

Nodejs》》MySql

Node.js 操作MySQL數據庫 文檔 # 項目要先安裝mysql包npm i mysqlxx // 安裝指定版本npm i mysql // 默認安裝最新版本 # 連接 mysq// 使用連接池連接const mysql require(mysql)# 建立連接const db mysql.createPool({host:, // 數據庫的IP地址user:ro…
閱讀更多...
金倉數據庫常見問題（持續更新）

金倉數據庫常見問題（持續更新）

目錄 1.查看大小是否敏感寫參數&#xff0c;提示&#xff1a;未認可的配置參數 "case_sensitive" 2.sys_backup.sh init時提示can not connect the primary node 3.設置邏輯備份運行腳本時提示錯誤are not allowed to use this program (crontab) 4.修改表字段類…
閱讀更多...
Docker Buildx最佳實踐：多架構鏡像構建指南

Docker Buildx最佳實踐：多架構鏡像構建指南

文章目錄為什么需要 Docker Buildx安裝與啟用 Docker Buildx創建多架構構建器實例構建多架構鏡像優化構建性能調試多架構構建實戰案例&#xff1a;構建 Go 應用多架構鏡像總結Docker Buildx 是 Docker 官方推出的擴展工具&#xff0c;用于支持多平臺鏡像構建&#xff0c;簡化跨…
閱讀更多...
你用的是什么鍵盤？

你用的是什么鍵盤？

在電競行業飛速發展的當下&#xff0c;游戲鍵盤作為玩家操作的核心載體&#xff0c;其性能表現直接影響著游戲體驗與競技結果。而賽卓電子推出的磁軸鍵盤專用芯片 SC4823&#xff0c;憑借一系列突破性的技術特性&#xff0c;正成為游戲鍵盤領域的性能革新者。?對于游戲玩家而言…
閱讀更多...
Activiti 中各種 startProcessInstance 接口之間的區別

Activiti 中各種 startProcessInstance 接口之間的區別

前言在用 RuntimeService 接口啟動流程實例時&#xff0c;總是分不清楚不同 startProcessInstanceXXX 接口之間的區別&#xff0c;這篇文章基于 Activiti 7.0.0.GA 版本&#xff0c;對這一類接口進行一個梳理和歸類。詳解接口列表RuntimeService 接口中以 startProcessInstance…
閱讀更多...
新手BUG：函數中 static 變量的賦值語句只會執行一次

新手BUG：函數中 static 變量的賦值語句只會執行一次

在 C 函數中使用 static 變量時&#xff0c;很多新手會陷入一個認知誤區&#xff1a;認為變量的初始化語句會在每次函數調用時執行。比如在bool funcA() { // Q&#xff1a;多次調用funcA&#xff0c;funcB會被執行幾次&#xff1f;// A&#xff1a;1次static bool value func…
閱讀更多...
Python 基礎詳解：數據類型（Data Types）—— 程序的“數據基石”

Python 基礎詳解：數據類型（Data Types）—— 程序的“數據基石”

一、引言&#xff1a;為什么數據類型如此重要&#xff1f;在 Python 編程中&#xff0c;數據類型決定了&#xff1a;數據的存儲方式可以對數據執行的操作數據的取值范圍不同類型之間的運算規則理解數據類型是編寫正確、高效程序的基礎。Python 是動態類型語言&#xff0c;雖然你…
閱讀更多...
WindowsLinux系統 安裝 CUDA 和 cuDNN

WindowsLinux系統 安裝 CUDA 和 cuDNN

Windows安裝前的準備工作 檢查硬件兼容性&#xff1a;確認電腦顯卡為 NVIDIA GPU。通過快捷鍵 Win R 喚出“運行”&#xff0c;輸入“control /name Microsoft.DeviceManager”喚出“設備管理器”&#xff0c;點擊“顯示適配器”查看是否有 NVIDIA 字樣。 驗證 CUDA 支持性&a…
閱讀更多...
工業數采引擎-通信鏈路SOCKET

工業數采引擎-通信鏈路SOCKET

通信庫&#xff1a;DotNetty 封裝實現&#xff1a;TcpServer、TcpClient、Udp TCP協議特性&#xff1a;面向連接協議&#xff1b;每個新連接都會創建獨立的ChannelHandler實例&#xff1b;TcpHandler構造函數在每次客戶端連接時觸發 UDP協議特性&#xff1a;無連接協議&#…
閱讀更多...
PHP小白零基礎入門（附視頻教程）

PHP小白零基礎入門（附視頻教程）

概述 PHP是一種通用開源腳本語言&#xff0c;常用于服務器端Web開發&#xff0c;具有語法簡單、上手快等特點。視頻教程&#xff1a;https://pan.quark.cn/s/8f214c23301b 搭建開發環境&#xff1a; 選擇集成工具&#xff1a;可選擇XAMPP&#xff08;支持Windows/Mac/Linux…
閱讀更多...
驗證碼等待時間技術在酒店自助入住、美容自助與社區場景中的應用必要性研究—仙盟創夢IDE

驗證碼等待時間技術在酒店自助入住、美容自助與社區場景中的應用必要性研究—仙盟創夢IDE

代碼 代碼 完整<!DOCTYPE html> <html lang"zh-CN"> <head><meta charset"UTF-8"><meta name"viewport" content"widthdevice-width, initial-scale1.0"><title>驗證碼倒計時</title><s…
閱讀更多...
Flask從入門到實戰：基礎、進階、項目架構與接口測試

Flask從入門到實戰：基礎、進階、項目架構與接口測試

本文將帶你從零開始掌握Flask框架&#xff0c;涵蓋基礎使用、進階技巧、項目架構設計&#xff0c;并提供完整的接口測試客戶端代碼。 目錄一、Flask基礎入門1.1 Flask簡介與安裝1.2 第一個Flask應用1.3 路由與請求處理1.4 請求與響應處理二、Flask進階使用2.1 模板引擎Jinja22.…
閱讀更多...
最新文章

Copyright @ 2022~2023