2.C語言--鏈表-頭插、頭刪、尾插、尾刪、查找、插入和刪除

文章目錄

  • 簡介
    • 動態順序表結構體
    • 1.頭插功能
    • 2.頭刪功能
    • 3.尾插功能
    • 4.尾刪功能
    • 5.查找功能
    • 6.插入功能
      • 6.1 指定位置之（前）去插入一個節點
      • 6.2 指定位置之（后）去插入一個節點
    • 7.刪除功能
      • 7.1 刪除指定位置的數據-時間復雜度O(N)
      • 7.2 刪除指定位置后一個位置的數據-時間復雜度O(1)
    • 8. 釋放鏈表緩存
    • 9. 打印鏈表的值
    • 10.此程序共包含3個文件，2個.c文件和1個.h文件
      • 10.1 SList.h文件
      • 10.2 SList.c文件
      • 10.3 test.c文件

簡介

	本文主要介紹鏈表的頭插、頭刪、尾插、尾刪、查找、插入和刪除，提供全部的.c和.h文件，確保使用者直接復制粘貼到編譯器上即可直接運行程序。

動態順序表結構體

typedef int SLTDateType;typedef struct SListNode
{SLTDateType data;struct SListNode* next;
}SLTNode;

1.頭插功能

	思路是將節點的首地址賦值到新申請節點的next中。

/*插入數據-頭插*/
void SListPushFront(SLTNode** ppHead, SLTDateType x)
{assert(ppHead != NULL);SLTNode* newNode = CreatListNode(x);newNode->next = *ppHead;*ppHead = newNode;return;
}

	開辟一個新的節點，并將要插入的值放心節點對應的data中。

/*創建節點*/
SLTNode* CreatListNode(SLTDateType x)
{SLTNode* newNode = (SLTNode*)malloc(sizeof(SLTNode));if (NULL == newNode){printf("CreatListNode malloc fail\n");exit(-1);}newNode->data = x;newNode->next = NULL;return newNode;
}

2.頭刪功能

	思路是將下一個節點的地址賦值到頭節點地址上，將當前節點free掉。

/*頭刪*/
void SListPopFront(SLTNode** ppHead)
{assert(ppHead != NULL);SLTNode* next = (*ppHead)->next;free(*ppHead);*ppHead = next;return;
}

3.尾插功能

	思路是先檢查輸入*ppHead是否為空，不為空就找到鏈表的尾節點進行新節點的插入。

/*插入數據-尾插*/
void SListPushBack(SLTNode** ppHead, SLTDateType x)
{assert(ppHead != NULL);/*新結點申請空間*/SLTNode* newNode = CreatListNode(x);if (*ppHead == NULL){*ppHead = newNode;}else{/*找到尾結點*/SLTNode* tail = *ppHead;while (tail->next != NULL){tail = tail->next;}tail->next = newNode;}return;
}

4.尾刪功能

	思路是釋放節點時，要將下一個節點的地址保存好再釋放當前節點。

/*尾刪*/
void SListPopBack(SLTNode** ppHead)
{assert(ppHead != NULL);/*如果只有一個節點時，直接釋放此節點*/if ((*ppHead)->next == NULL){free(*ppHead);*ppHead = NULL;}else/*存在2個及2個以上節點的處理方式*/{SLTNode* tail = *ppHead;SLTNode* pre = NULL;while (tail->next != NULL){pre = tail;tail = tail->next;}pre->next = NULL;free(tail);tail = NULL;}return;
}

5.查找功能

	思路是遍歷，找到節點后返回當前節點的地址，找不到就返回NULL。

/*查找*/
SLTNode* SListFind(SLTNode* pHead, SLTDateType x)
{assert(pHead != NULL);SLTNode* cur = pHead;while (cur){if (cur->data == x){return cur;}else{cur = cur->next;}}return NULL;
}

6.插入功能

6.1 指定位置之（前）去插入一個節點

	此方法是比較笨的方法，為了節約資源應該將數據往指定位置的后邊插入。

/*指定位置插入數據-在pos位置之前去插入一個節點--時間復雜度O(N)*/
SLTNode* SListInsert(SLTNode** ppHead, SLTNode* pos, SLTDateType x)
{assert(ppHead != NULL);assert(pos != NULL);SLTNode* newNode = CreatListNode(x);if (*ppHead == pos)/*pos的位置在第一個位置時*/{newNode->next = *ppHead;*ppHead = newNode;}else{/*找到pos位置的前一個位置*/SLTNode* posPrev = *ppHead;while (posPrev->next != pos){posPrev = posPrev->next;}posPrev->next = newNode;newNode->next = pos;}return NULL;
}

6.2 指定位置之（后）去插入一個節點

	此方法是常用的插入方式，時間復雜度是O(1)。

/*指定位置插入數據-在pos位置之后去插入一個節點--時間復雜度O(1)*/
SLTNode* SListInsertAfter(SLTNode* pos, SLTDateType x)
{assert(pos != NULL);SLTNode* newNode = CreatListNode(x);newNode->next = pos->next;pos->next = newNode;return NULL;
}

7.刪除功能

7.1 刪除指定位置的數據-時間復雜度O(N)

	此方法需要記住當前節點前一個的節點地址，會多耗費時間資源，時間復雜度O(N)。

SLTNode* SListErase(SLTNode** ppHead, SLTNode* pos)
{assert(ppHead != NULL);assert(pos != NULL);/*如果刪除的數據是頭*/if (*ppHead == pos){SListPopFront(ppHead);}else{SLTNode* prev = *ppHead;while (prev->next != pos)/*找到pos前一個節點*/{prev = prev->next;}prev->next = pos->next;free(pos);pos = NULL;}return NULL;
}

7.2 刪除指定位置后一個位置的數據-時間復雜度O(1)

	此方法需要記住當前節點前一個的節點地址，會多耗費時間資源，時間復雜度O(1)。

/*刪除指定位置后一個位置的數據*/
SLTNode* SListEraseAfter(SLTNode* pos)
{assert(pos->next != NULL);SLTNode* next = pos->next;pos->next = next->next;free(next);next = NULL;return NULL;
}

8. 釋放鏈表緩存

	思路將下一個節點的地址先記住，然后釋放當前節點。再將保存的地址賦值到當前節點循環釋放緩存。

/*釋放鏈表緩存*/
SLTNode* SListDestory(SLTNode** ppHead)
{assert(ppHead != NULL);SLTNode* cur = *ppHead;while (cur){SLTNode* next = cur->next;free(cur);cur = next;}*ppHead = NULL;return NULL;
}

9. 打印鏈表的值

/*打印鏈表的值*/
void SListTPrint(SLTNode* pHead)
{SLTNode* cur = pHead;while (cur != NULL){printf("%d->", cur->data);cur = cur->next;}return;
}

10.此程序共包含3個文件，2個.c文件和1個.h文件

10.1 SList.h文件

	文件中包含了函數功能的頭文件以及對應的結構體。

#pragma once
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>typedef int SLTDateType;typedef struct SListNode
{SLTDateType data;struct SListNode* next;
}SLTNode;void SListTPrint(SLTNode *pHead);							/*打印鏈表的值*/
void SListPushBack(SLTNode** ppHead, SLTDateType x);		/*插入數據-尾插*/
void SListPushFront(SLTNode** ppHead, SLTDateType x);		/*插入數據-頭插*/void SListPopBack(SLTNode** ppHead);						/*尾刪*/
void SListPopFront(SLTNode** ppHead);						/*頭刪*/SLTNode* SListFind(SLTNode* pHead, SLTDateType x);				    /*查找*/
SLTNode* SListInsert(SLTNode** ppHead, SLTNode* pos, SLTDateType x);/*指定位置插入數據-在pos位置之前去插入一個節點*/
SLTNode* SListInsertAfter(SLTNode* pos, SLTDateType x);				/*指定位置插入數據-在pos位置之后去插入一個節點*/
SLTNode* SListErase(SLTNode** ppHead, SLTNode* pos);				/*刪除指定位置的數據*/
SLTNode* SListEraseAfter(SLTNode* pos);								/*刪除指定位置后一個位置的數據*/
SLTNode* SListDestory(SLTNode** ppHead);							/*釋放鏈表緩存*/SLTNode* CreatListNode(SLTDateType x);								/*創建一個新的節點*/

10.2 SList.c文件

	文件中包含了功能函數的具體實現方式。

#define _CRT_SECURE_NO_WARNINGS
#include "SList.h"/*插入數據-尾插*/
void SListPushBack(SLTNode** ppHead, SLTDateType x)
{assert(ppHead != NULL);/*新結點申請空間*/SLTNode* newNode = CreatListNode(x);if (*ppHead == NULL){*ppHead = newNode;}else{/*找到尾結點*/SLTNode* tail = *ppHead;while (tail->next != NULL){tail = tail->next;}tail->next = newNode;}return;
}/*插入數據-頭插*/
void SListPushFront(SLTNode** ppHead, SLTDateType x)
{assert(ppHead != NULL);SLTNode* newNode = CreatListNode(x);newNode->next = *ppHead;*ppHead = newNode;return;
}/*創建節點*/
SLTNode* CreatListNode(SLTDateType x)
{SLTNode* newNode = (SLTNode*)malloc(sizeof(SLTNode));if (NULL == newNode){printf("CreatListNode malloc fail\n");exit(-1);}newNode->data = x;newNode->next = NULL;return newNode;
}/*尾刪*/
void SListPopBack(SLTNode** ppHead)
{assert(ppHead != NULL);/*如果只有一個節點時，直接釋放此節點*/if ((*ppHead)->next == NULL){free(*ppHead);*ppHead = NULL;}else/*存在2個及2個以上節點的處理方式*/{SLTNode* tail = *ppHead;SLTNode* pre = NULL;while (tail->next != NULL){pre = tail;tail = tail->next;}pre->next = NULL;free(tail);tail = NULL;}return;
}/*頭刪*/
void SListPopFront(SLTNode** ppHead)
{assert(ppHead != NULL);SLTNode* next = (*ppHead)->next;free(*ppHead);*ppHead = next;return;
}/*查找*/
SLTNode* SListFind(SLTNode* pHead, SLTDateType x)
{assert(pHead != NULL);SLTNode* cur = pHead;while (cur){if (cur->data == x){return cur;}else{cur = cur->next;}}return NULL;
}/*指定位置插入數據-在pos位置之前去插入一個節點--時間復雜度O(N)*/
SLTNode* SListInsert(SLTNode** ppHead, SLTNode* pos, SLTDateType x)
{assert(ppHead != NULL);assert(pos != NULL);SLTNode* newNode = CreatListNode(x);if (*ppHead == pos)/*pos的位置在第一個位置時*/{newNode->next = *ppHead;*ppHead = newNode;}else{/*找到pos位置的前一個位置*/SLTNode* posPrev = *ppHead;while (posPrev->next != pos){posPrev = posPrev->next;}posPrev->next = newNode;newNode->next = pos;}return NULL;
}/*指定位置插入數據-在pos位置之后去插入一個節點--時間復雜度O(1)*/
SLTNode* SListInsertAfter(SLTNode* pos, SLTDateType x)
{assert(pos != NULL);SLTNode* newNode = CreatListNode(x);newNode->next = pos->next;pos->next = newNode;return NULL;
}/*刪除指定位置的數據--時間復雜度O(N)*/
SLTNode* SListErase(SLTNode** ppHead, SLTNode* pos)
{assert(ppHead != NULL);assert(pos != NULL);/*如果刪除的數據是頭*/if (*ppHead == pos){SListPopFront(ppHead);}else{SLTNode* prev = *ppHead;while (prev->next != pos)/*找到pos前一個節點*/{prev = prev->next;}prev->next = pos->next;free(pos);pos = NULL;}return NULL;
}/*刪除指定位置后一個位置的數據*/
SLTNode* SListEraseAfter(SLTNode* pos)
{assert(pos->next != NULL);SLTNode* next = pos->next;pos->next = next->next;free(next);next = NULL;return NULL;
}/*釋放鏈表緩存*/
SLTNode* SListDestory(SLTNode** ppHead)
{assert(ppHead != NULL);SLTNode* cur = *ppHead;while (cur){SLTNode* next = cur->next;free(cur);cur = next;}*ppHead = NULL;return NULL;
}/*打印鏈表的值*/
void SListTPrint(SLTNode* pHead)
{SLTNode* cur = pHead;while (cur != NULL){printf("%d->", cur->data);cur = cur->next;}return;
}

10.3 test.c文件

	用來進行相應功能的測試，分別測試尾插、尾刪和頭插、頭刪等功能。

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include "SList.h"void Test1()
{SLTNode* SList = NULL;/*尾插*/SListPushBack(&SList, 1);SListPushBack(&SList, 2);SListPushBack(&SList, 3);SListPushBack(&SList, 4);/*尾刪*/SListPopBack(&SList);/*打印鏈表*/SListTPrint(SList);printf("NULL\n");return;
}void Test2()
{SLTNode* SList = NULL;/*頭插*/SListPushFront(&SList, 1);SListPushFront(&SList, 2);SListPushFront(&SList, 3);/*頭刪*/SListPopFront(&SList);/*打印*/SListTPrint(SList);printf("NULL");return;
}void Test3()
{SLTNode* SList = NULL;SLTNode* pos = NULL;int i = 1;/*尾插*/SListPushBack(&SList, 1);SListPushBack(&SList, 5);SListPushBack(&SList, 2);SListPushBack(&SList, 3);SListPushBack(&SList, 2);/*查找數字的位置*/pos = SListFind(SList, 2);while (pos)/*查找到數據為2的節點的地址*/{printf("第%d個pos節點的:%p->%d\n", i++, pos->next, pos->data);if (pos->next){pos = SListFind(pos->next, 2);}else/*為空指針時，直接跳出循環*/{break;}}/*改變對應節點位置的數據,將5位置前邊的位置添加個20*/pos = SListFind(SList, 5);if (pos)/*在5的位置之前插入20*/{SListInsert(&SList, pos, 20);}pos = SListFind(SList, 5);if (pos)/*在5的位置之后插入100*/{SListInsertAfter(pos, 100);}/*打印*/SListTPrint(SList);printf("NULL");return;
}int main()
{Test1();/*尾插+尾刪*///Test2();/*頭插+頭刪*///Test3(); /*指定位置前插入、后插入、尋找指定數據節點的位置*/return 0;
}

	這里代碼大家可以自己拷貝到VS編譯器中，Test1()，Test2()，Test3()，分別打開注釋看一下效果，本人親測過，可以直接運行出結果的。

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

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

相關文章

配置hikari數據庫連接池時多數據源不生效

配置hikari數據庫連接池時多數據源不生效

1.原始配置&#xff0c;改造前&#xff1a; spring:# 配置數據源信息datasource:dynamic:#設置默認的數據源或者數據源組,默認值即為masterprimary: masterstrict: truedatasource:#這里采用了配置文件取值的方式&#xff0c;可以直接替換為數據庫連接master:url: jdbc:postgr…
閱讀更多...
【LLS-Player】音視頻幀的回調過程

【LLS-Player】音視頻幀的回調過程

RtdSinkInterface 實現者用于從SDK獲取音視頻幀 class RtdSinkInterface {public:virtual ~RtdSinkInterface() = default;virtual void OnAudioFrame(const RtdAudioFrame& fra
閱讀更多...
電子學會C/C++編程等級考試2023年03月（一級）真題解析

電子學會C/C++編程等級考試2023年03月（一級）真題解析

C/C++等級考試（1~8級）全部真題?點這里 第1題：字符長方形 給定一個字符，用它構造一個長為4個字符，寬為3個字符的長方形，可以參考樣例輸出。 時間限制：1000 內存限制：65536輸入 輸入只有一行， 包含一個字符。輸出 該字符構成的長方形，長4個字符，寬3個字符。樣例輸入…
閱讀更多...
如何使用Fiddler進行弱網測試

如何使用Fiddler進行弱網測試

測試APP、web經常需要用到弱網測試&#xff0c;也就是在信號差、網絡慢的情況下進行測試。我們自己平常在使用手機APP時&#xff0c;在地鐵、電梯、車庫等場景經常會遇到會話中斷、超時等情況&#xff0c;這種就屬于弱網。 普通的弱網測試可以選擇第三方工具對帶寬、丟包、延時…
閱讀更多...
python數據類型之字典、元組

python數據類型之字典、元組

一、字典 1、定義字典 字典是 有序&#xff08;3.6以前無序&#xff09;、鍵不重復 且 元素只能是鍵值對的可變的 個 容器。鍵不重復&#xff0c;重復則會被覆蓋 如下定義一個字典 # 使用大括號 {} 來創建空字典 test_dic1 {} # 使用內建函數 dict() 創建字典&#xff1a;…
閱讀更多...
【華為OD題庫-032】數字游戲-java

【華為OD題庫-032】數字游戲-java

題目 小明玩一個游戲。系統發1n張牌&#xff0c;每張牌上有一個整數。第一張給小明&#xff0c;后n張按照發牌順序排成連續的一行。需要小明判斷&#xff0c;后n張牌中&#xff0c;是否存在連續的若干張牌&#xff0c;其和可以整除小明手中牌上的數字. 輸入描述: 輸入數據有多組…
閱讀更多...
嵌入式基礎知識學習：Flash、EEPROM、RAM、ROM

嵌入式基礎知識學習：Flash、EEPROM、RAM、ROM

https://blog.csdn.net/y673533511/article/details/87913989 FLASH存儲器又稱閃存&#xff0c;它結合了ROM和RAM的長處&#xff0c;不僅具備電子可擦出可編程(EEPROM) 的性能&#xff0c;還不會斷電丟失數據同時可以快速讀取數據 (NVRAM 的優勢)&#xff0c;U 盤和MP3 里用的…
閱讀更多...
[論文筆記]MatchPyramid

[論文筆記]MatchPyramid

引言 又一篇文本匹配論文Text Matching as Image Recognition，論文題目是 文本匹配當成圖像識別。 挺有意思的一篇工作，我們來看它是如何實現的。 作者受到卷積神經網絡在圖像識別中成功應用的啟發，其中神經元可以捕獲很多復雜的模式，作者提出將文本匹配看作是圖像識別任…
閱讀更多...
DDD落地：從網易新聞APP重構，看DDD的巨大價值

DDD落地：從網易新聞APP重構，看DDD的巨大價值

尼恩說在前面 在40歲老架構師 尼恩的讀者交流群(50)中&#xff0c;最近有小伙伴拿到了一線互聯網企業如阿里、滴滴、極兔、有贊、希音、百度、網易、美團的面試資格&#xff0c;遇到很多很重要的面試題&#xff1a; 談談你的DDD落地經驗&#xff1f; 談談你對DDD的理解&#x…
閱讀更多...
GEE：梯度提升樹（Gradient Boosting Tree）分類教程（樣本制作、特征添加、訓練、精度、參數優化、貢獻度、統計面積）

GEE：梯度提升樹（Gradient Boosting Tree）分類教程（樣本制作、特征添加、訓練、精度、參數優化、貢獻度、統計面積）

作者：CSDN @ _養樂多_ 本文將介紹在Google Earth Engine （GEE）平臺上進行梯度提升樹（Gradient Boosting Tree）分類的方法和代碼，其中包括制作樣本點教程（本地、在線和本地在線混合制作樣本點，合并樣本點等），加入特征變量(各種指數、紋理特征、時間序列特征、物候特征…
閱讀更多...
OpenStack云計算平臺-啟動一個實例

OpenStack云計算平臺-啟動一個實例

目錄 一、創建虛擬網絡 ?二、創建m1.nano規格的主機 三、生成一個鍵值對 四、增加安全組規則 ?五、啟動一個實例 1、確定實例選項 2、創建實例 3、使用虛擬控制臺訪問實例 4、驗證能否遠程訪問實例 一、創建虛擬網絡 下面的說明和框圖使用示例IP 地址范圍。你必須依…
閱讀更多...
Altium Designer學習筆記12

Altium Designer學習筆記12

把幾個層理解下&#xff1a; layer名稱功能說明信息Toplayer信號層銅箔層&#xff0c;電氣連接的層Bottomlayer信號層銅箔層&#xff0c;電氣連接的層Internal Planes內層連接地和電源上&#xff0c;一般情況下不布線&#xff0c;是由整片銅膜組成的Mechanical 1機械層電路板機…
閱讀更多...
String 、StringBuffer 和 StringBuilder 的區別？

String 、StringBuffer 和 StringBuilder 的區別？

String 使用 String 聲明一個字符串的時候&#xff0c;該字符串會存放在堆中的字符串常量池中。因為在java中所有的String 都是以常量表示&#xff0c;且由 final 修飾&#xff0c;因此在線程池中它的線程是安全的 且 不可變的 。每個 String 在被創建后就不再發生任何變化。 …
閱讀更多...
mysql按年、季度、月，統計

mysql按年、季度、月，統計

以下是按年、按季度和按月統計SQL查詢語句&#xff1a; 按年統計&#xff1a; SELECTds.checker,YEAR(ds.create_time) AS settleYear,SUM(ds.quantity) AS quantity,SUM(ds.approval_price) AS approvalPrice FROMdata_settle ds WHEREds.delete_flag 0AND ds.approval_sta…
閱讀更多...
漏洞盒子公益SRC

漏洞盒子公益SRC

漏洞盒子公益SRC&#xff0c;小小地記錄一下第一個月的成果
閱讀更多...
數據中臺建設方法論

數據中臺建設方法論

1、數倉的概念和了解--業務的痛點 產生的痛點&#xff1a;數據資產比較模糊、數據的質量比較低、重復建設、代碼的耦合性比較強。 2、數據倉庫中的常見的模型&#xff1a; 1、心型模型&#xff1a;中間是一張事實表&#xff0c;周圍都是維度表。 對于心型模型的主要的特點&a…
閱讀更多...
面向未來的自動化：擁抱機器人即服務（RaaS）

面向未來的自動化：擁抱機器人即服務（RaaS）

01. RaaS是什么&#xff1f; 對于希望實現業務流程自動化的公司來說&#xff0c;機器人通常是一筆巨大的資本支出。由于機器人非常昂貴&#xff0c;公司可能需要等待數年才能看到投資回報。正是由于這一現實&#xff0c;許多較小的組織無法投資機器人。 但一些機器人公司正在采…
閱讀更多...
算法通關村第十二關-青銅挑戰字符串

算法通關村第十二關-青銅挑戰字符串

大家好我是蘇麟 , 今天帶來字符串專題 . 轉換成小寫字母 描述 : 給你一個字符串 s &#xff0c;將該字符串中的大寫字母轉換成相同的小寫字母&#xff0c;返回新的字符串。 題目 : LeetCode 709.轉換成小寫字母 : 709. 轉換成小寫字母 分析 : 這個題可以先遍歷整個字符串…
閱讀更多...
Mybatis和MybatisPlus：數據庫操作工具的對比

Mybatis和MybatisPlus：數據庫操作工具的對比

目錄 什么是mybatis 什么是mybatisplus MyBatis-Plus&#xff1a;為簡化數據庫操作而生的強大工具 一、MyBatis-Plus的背景和概述 二、MyBatis-Plus的主要特點 三、如何使用MyBatis-Plus mybatis-Plus的優勢 什么是Hibernate Hibernate&#xff1a;Java開發者的數據持久…
閱讀更多...
光譜圖像超分 Benchmark

光譜圖像超分 Benchmark

光譜圖像超分 Benchmark 文章目錄 光譜圖像超分 Benchmark0. pioneer工作及綜述基于深度學習的高光譜多光譜融合&#xff08;updating&#xff09;1. 空間光譜圖像超分 &#xff08;to be updated&#xff09;2. 高分辨率多光譜圖像超分&#xff08;to be updated&#xff09;3…
閱讀更多...
最新文章

Copyright @ 2022~2023