上一篇【數(shù)據(jù)結(jié)構(gòu)】順序表-CSDN博客??我們了解了順序表，但是呢順序表涉及到了一些問(wèn)題，比如，中間/頭部的插入/刪除，時(shí)間復(fù)雜度為O(N);增容申請(qǐng)空間、拷貝、釋放舊空間會(huì)有不小的消耗；增容所浪費(fèi)的空間... 我們?nèi)绾稳ソ鉀Q這些問(wèn)題？本篇介紹另一個(gè)數(shù)據(jù)結(jié)構(gòu)——鏈表

1. 鏈表的概念及結(jié)構(gòu)

鏈表：是一種物理存儲(chǔ)結(jié)構(gòu)上非連續(xù)、非順序的存儲(chǔ)結(jié)構(gòu)，數(shù)據(jù)元素的邏輯順序是通過(guò)鏈表中的指針連接次序?qū)崿F(xiàn)的，鏈表也是線性表的一種

鏈表大概是什么樣的呢？看下圖

鏈表是由一個(gè)一個(gè)的節(jié)點(diǎn)組成，再順序表中，數(shù)據(jù)是連續(xù)存放的，我們想找到下一個(gè)數(shù)據(jù)順著前一個(gè)數(shù)據(jù)找就行了，而鏈表中數(shù)據(jù)存放空間是不連續(xù)的，所以我們就需要一個(gè)指針來(lái)保存下一個(gè)節(jié)點(diǎn)的地址，所以，我們?nèi)绻x鏈表，只需要定義鏈表的節(jié)點(diǎn)結(jié)構(gòu)就行了

(在【C語(yǔ)言】結(jié)構(gòu)體詳解-CSDN博客?的1.3 結(jié)構(gòu)體的自引用 中介紹過(guò))

struct SListNode
{int data;//數(shù)據(jù)struct SListNode* next;//下一個(gè)數(shù)據(jù)的地址
};

和上一篇一樣，創(chuàng)建一個(gè)頭文件，兩個(gè)源文件

?也是一樣，在頭文件SList.h中定義單鏈表的結(jié)構(gòu)，并對(duì)類(lèi)型和結(jié)構(gòu)體改名

#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
typedef int Type; 
//定義節(jié)點(diǎn)結(jié)構(gòu)
typedef struct SListNode
{Type data;struct SListNode* next;
}SLNode;

我們先創(chuàng)建幾個(gè)節(jié)點(diǎn)，在test.c中實(shí)現(xiàn)

#include "SList.h" //包含頭文件
void SListtest1()
{SLNode* node1 = (SLNode*)malloc(sizeof(SLNode));//創(chuàng)建節(jié)點(diǎn)1node1->data = 1;//賦值SLNode* node2 = (SLNode*)malloc(sizeof(SLNode));//創(chuàng)建節(jié)點(diǎn)2node2->data = 2;//賦值SLNode* node3 = (SLNode*)malloc(sizeof(SLNode));//創(chuàng)建節(jié)點(diǎn)3node3->data = 3;//賦值SLNode* node4 = (SLNode*)malloc(sizeof(SLNode));//創(chuàng)建節(jié)點(diǎn)4node4->data = 4;//賦值
}
int main()
{SListtest1();return 0;
}

雖然我們創(chuàng)建好了節(jié)點(diǎn)，但是這幾個(gè)節(jié)點(diǎn)現(xiàn)在還不能互相找到，所以我們接下來(lái)要將這幾個(gè)節(jié)點(diǎn)連接起來(lái)，怎么連接？存下一個(gè)節(jié)點(diǎn)的地址

void SListtest1()
{SLNode* node1 = (SLNode*)malloc(sizeof(SLNode));//創(chuàng)建節(jié)點(diǎn)1node1->data = 1;//賦值SLNode* node2 = (SLNode*)malloc(sizeof(SLNode));//創(chuàng)建節(jié)點(diǎn)2node2->data = 2;//賦值SLNode* node3 = (SLNode*)malloc(sizeof(SLNode));//創(chuàng)建節(jié)點(diǎn)3node3->data = 3;//賦值SLNode* node4 = (SLNode*)malloc(sizeof(SLNode));//創(chuàng)建節(jié)點(diǎn)4node4->data = 4;//賦值//將四個(gè)節(jié)點(diǎn)連接起來(lái)node1->next = node2;node2->next = node3;node3->next = node4;node4->next = NULL;
}

現(xiàn)在就構(gòu)成了一個(gè)鏈表，有了這個(gè)簡(jiǎn)單的鏈表，我們來(lái)寫(xiě)一個(gè)函數(shù)打印一下里面的數(shù)據(jù)

鏈表的打印

在SList.h中進(jìn)行函數(shù)的聲明

void SLPrint(SLNode* ps);//打印

參數(shù)是鏈表的節(jié)點(diǎn)的地址?

在SList.c中進(jìn)行函數(shù)的實(shí)現(xiàn)

#include "SList.h"
void SLPrint(SLNode* ps) //打印
{SLNode* pcur = ps;//pcur指向當(dāng)前鏈表的第一個(gè)節(jié)點(diǎn)
}

要打印當(dāng)然就要循環(huán)遍歷，寫(xiě)一個(gè)while循環(huán)，判斷條件為pcur，不為NULL進(jìn)入循環(huán)?

void SLPrint(SLNode* ps) //打印
{SLNode* pcur = ps;//pcur指向當(dāng)前鏈表的第一個(gè)節(jié)點(diǎn)while (pcur) //判斷第一個(gè)節(jié)點(diǎn)是否為NULL{//....}
}

?進(jìn)入循環(huán)后打印內(nèi)容

void SLPrint(SLNode* ps) //打印
{SLNode* pcur = ps;//pcur指向當(dāng)前鏈表的第一個(gè)節(jié)點(diǎn)while (pcur){printf("%d->", pcur->data);//打印內(nèi)容}
}

打印完一個(gè)數(shù)據(jù)后，要把下一個(gè)節(jié)點(diǎn)值部分的地址給pcur ，也就是pcur要存node2中2的地址，此時(shí)pcur不再指向node1，指向了node2

void SLPrint(SLNode* ps) //打印
{SLNode* pcur = ps;//pcur指向當(dāng)前鏈表的第一個(gè)節(jié)點(diǎn)while (pcur){printf("%d->", pcur->data);//打印內(nèi)容pcur = pcur->next;//指向下一個(gè)節(jié)點(diǎn)}printf("NULL\n");
}

在test.c中測(cè)試

測(cè)試時(shí)我們不直接傳鏈表的第一個(gè)節(jié)點(diǎn)node1，而是再定義一個(gè)結(jié)構(gòu)體指針plist去指向node1，讓plist作為參數(shù)傳過(guò)去

    SLNode* plist = node1;SLPrint(plist);

雖然有點(diǎn)多此一舉，但這樣會(huì)讓我們的代碼更完善?

運(yùn)行結(jié)果

?2.鏈表的插入

實(shí)際使用鏈表的時(shí)候我們不會(huì)像上面那樣一個(gè)一個(gè)創(chuàng)建，初始時(shí)候是一個(gè)空鏈表，會(huì)跟順序表類(lèi)似進(jìn)行空間開(kāi)辟然后插入數(shù)據(jù)

2.1空間申請(qǐng)創(chuàng)建節(jié)點(diǎn)

插入數(shù)據(jù)前依舊是要判斷空間夠不夠

在SList.h中進(jìn)行函數(shù)的聲明

SLNode* SLBuyNode(Type x);//申請(qǐng)空間創(chuàng)建節(jié)點(diǎn)

返回值是節(jié)點(diǎn)的地址，參數(shù)就是要插入的數(shù)據(jù)

在SList.c中進(jìn)行函數(shù)的實(shí)現(xiàn)

SLNode* SLBuyNode(Type x)//申請(qǐng)空間創(chuàng)建節(jié)點(diǎn)
{SLNode* newnode = (SLNode*)malloc(sizeof(SLNode));if (newnode == NULL) //空間申請(qǐng)失敗{perror("malloc");return 1;}newnode->data = x;newnode->next = NULL;return newnode;
}

2.2?尾插

在SList.h中進(jìn)行函數(shù)的聲明

void SLPushBack(SLNode** ps, Type x);//尾插

參數(shù)是鏈表的節(jié)點(diǎn)地址，是一個(gè)二級(jí)指針，和要插入的數(shù)據(jù)

我們要給函數(shù)傳地址，這樣形參的改變才能影響實(shí)參，對(duì)參數(shù)的理解如下，這很重要，這里提前展示將要在test.c中測(cè)試用的部分代碼?

在SList.c中進(jìn)行函數(shù)的實(shí)現(xiàn)

尾插要先找到尾節(jié)點(diǎn)，再將尾節(jié)點(diǎn)和新節(jié)點(diǎn)連接起來(lái)?，此時(shí)node4的地址部分就不再是NULL 而是新節(jié)點(diǎn)的地址

代碼如何實(shí)現(xiàn)呢 ？先找尾節(jié)點(diǎn)

void SLPushBack(SLNode* ps, Type x)//尾插
{SLNode* ptail = ps;//定義尾節(jié)點(diǎn)，開(kāi)始時(shí)指向頭節(jié)點(diǎn)while (ptail->next != NULL)//遍歷鏈表數(shù)據(jù)，找尾節(jié)點(diǎn){ptail = ptail->next;}//跳出循環(huán)后ptail指向尾節(jié)點(diǎn)
}

然后我們直接調(diào)用創(chuàng)建節(jié)點(diǎn)的函數(shù)，放在找尾節(jié)點(diǎn)前面，最后賦值

void SLPushBack(SLNode* ps, Type x)//尾插
{SLNode* newnode = SLBuyNode(x);//申請(qǐng)空間創(chuàng)建節(jié)點(diǎn)SLNode* ptail = ps;//定義尾節(jié)點(diǎn)，開(kāi)始時(shí)指向頭節(jié)點(diǎn)while (ptail->next != NULL)//遍歷鏈表數(shù)據(jù)，找尾節(jié)點(diǎn){ptail = ptail->next;}//跳出循環(huán)后ptail指向尾節(jié)點(diǎn)ptail->next = newnode;//直接賦值
}

?但是呢，鏈表在沒(méi)有賦值的時(shí)候是空鏈表，所以我們要討論空鏈表的情況，如果是空鏈表，直接讓ps指向新節(jié)點(diǎn)newnode，所以最終的代碼如下

void SLPushBack(SLNode** pps, Type x)//尾插
{assert(pps);//pps不可以為NULLSLNode* newnode = SLBuyNode(x);//申請(qǐng)空間創(chuàng)建節(jié)點(diǎn)if (*pps == NULL) //*pps可以為NULL，表示空鏈表{*pps = newnode;}else //非空鏈表{SLNode* ptail = *pps;//定義尾節(jié)點(diǎn)，開(kāi)始時(shí)指向頭節(jié)點(diǎn)while (ptail->next)//遍歷鏈表數(shù)據(jù)，找尾節(jié)點(diǎn){ptail = ptail->next;}//跳出循環(huán)后ptail指向尾節(jié)點(diǎn)ptail->next = newnode;//直接賦值}
}

我們?cè)賮?lái)看test.c中測(cè)試的代碼

void SListtest2()
{SLNode* plist = NULL;//空鏈表SLPushBack(&plist, 1);//尾插SLPushBack(&plist, 2);SLPushBack(&plist, 3);SLPushBack(&plist, 4);SLPrint(plist);//打印
}
int main()
{//SListtest1();SListtest2();return 0;
}

多插入幾個(gè)數(shù)據(jù)，運(yùn)行看結(jié)果，插入成功

2.3 頭插

?在SList.h中進(jìn)行函數(shù)的聲明

void SLPushHead(SLNode** pps, Type x);//頭插

同樣的，參數(shù)也是一個(gè)二級(jí)指針，還有要插入的數(shù)據(jù)

在SList.c中進(jìn)行函數(shù)的實(shí)現(xiàn)

我們需要做兩件事，一個(gè)是將newnode和原本的首節(jié)點(diǎn)連接在一起，另一件事是*pps要指向新的首節(jié)點(diǎn)?

?鏈表不為NULL時(shí)，代碼如下

void SLPushHead(SLNode** pps, Type x)//頭插
{assert(pps);//pps不能為NULLSLNode* newnode = SLBuyNode(x);//申請(qǐng)空間創(chuàng)建節(jié)點(diǎn)newnode->next = *pps;*pps = newnode;
}

當(dāng)鏈表為NULL時(shí)，分析一下

當(dāng)前代碼也可以實(shí)現(xiàn)

在test.c中測(cè)試

void SListtest2()
{SLNode* plist = NULL;//空鏈表SLPushBack(&plist, 1);//尾插SLPushBack(&plist, 2);SLPushBack(&plist, 3);SLPushBack(&plist, 4);SLPrint(plist);//打印SLPushHead(&plist, 6);//頭插SLPushHead(&plist, 7);SLPushHead(&plist, 8);SLPrint(plist);//打印
}

看一下運(yùn)行結(jié)果

3.鏈表的刪除

刪除數(shù)據(jù)，鏈表就不能為空，不然刪啥呢?

?3.1 尾刪

在SList.h中進(jìn)行函數(shù)的聲明

void SLPopBack(SLNode** pps);//尾刪

在SList.c中進(jìn)行函數(shù)的實(shí)現(xiàn)

很顯然，首先就是找尾節(jié)點(diǎn)，找到尾節(jié)點(diǎn)之后直接釋放嗎？node4釋放后node3->next里面依然存放著node4的地址，但此時(shí)指向的空間已經(jīng)沒(méi)了，此時(shí)的指針就成了一個(gè)野指針 ，所以我們還要將被釋放節(jié)點(diǎn)的前一個(gè)節(jié)點(diǎn)的指針置空

所以我們還要找尾節(jié)點(diǎn)的前一個(gè)節(jié)點(diǎn)

void SLPopBack(SLNode** pps)//尾刪
{assert(pps && *pps);//pps和鏈表都不能為空SLNode* prev = *pps;//定義尾節(jié)點(diǎn)前一個(gè)節(jié)點(diǎn)SLNode* ptail = *pps;//定義尾節(jié)點(diǎn)while (ptail->next){prev = ptail;ptail = ptail->next;}//此時(shí)找到了尾節(jié)點(diǎn)和尾節(jié)點(diǎn)前一個(gè)節(jié)點(diǎn)free(ptail);//釋放尾節(jié)點(diǎn)ptail = NULL;//置空prev->next = NULL;//置空尾節(jié)點(diǎn)前一個(gè)節(jié)點(diǎn)
}

如果這個(gè)鏈表只有一個(gè)節(jié)點(diǎn)呢，這個(gè)代碼可行嗎？來(lái)分析一下

我們把節(jié)點(diǎn)釋放并置空后，prev->next就不存在了，函數(shù)最后一句代碼就不能實(shí)現(xiàn)，所以，當(dāng)鏈表里只有一個(gè)節(jié)點(diǎn)時(shí)，直接釋放就行了

void SLPopBack(SLNode** pps)//尾刪
{assert(pps && *pps);//pps和鏈表都不能為空if ((*pps)->next == NULL)//鏈表只有一個(gè)節(jié)點(diǎn){free(*pps);//釋放節(jié)點(diǎn)*pps = NULL;//置空}else //鏈表不止一個(gè)節(jié)點(diǎn){SLNode* prev = *pps;//定義尾節(jié)點(diǎn)前一個(gè)節(jié)點(diǎn)SLNode* ptail = *pps;//定義尾節(jié)點(diǎn)while (ptail->next){prev = ptail;ptail = ptail->next;}//此時(shí)找到了尾節(jié)點(diǎn)和尾節(jié)點(diǎn)前一個(gè)節(jié)點(diǎn)free(ptail);//釋放尾節(jié)點(diǎn)ptail = NULL;//置空prev->next = NULL;//置空尾節(jié)點(diǎn)前一個(gè)節(jié)點(diǎn)}
}

在test.c中測(cè)試

void SListtest2()
{SLNode* plist = NULL;//空鏈表SLPushBack(&plist, 1);//尾插SLPushBack(&plist, 2);SLPrint(plist);//打印SLPushHead(&plist, 6);//頭插SLPushHead(&plist, 7);SLPrint(plist);//打印SLPopBack(&plist);//尾刪SLPrint(plist);//打印
}

看下結(jié)果，尾刪成功

3.2 頭刪

在SList.h中進(jìn)行函數(shù)的聲明

void SLPopHead(SLNode** pps);//頭刪

在SList.c中進(jìn)行函數(shù)的實(shí)現(xiàn)

我們要?jiǎng)h除頭節(jié)點(diǎn)，跟刪除尾節(jié)點(diǎn)不一樣，如果我們把首節(jié)點(diǎn)釋放掉，還能找到首節(jié)點(diǎn)里的next嗎？不能，不能的話就找不到第二個(gè)節(jié)點(diǎn)以及剩下的節(jié)點(diǎn)

我們應(yīng)該先把下一個(gè)節(jié)點(diǎn)的信息存儲(chǔ)起來(lái)

SLNode* Next = (*pps)->next;//存節(jié)點(diǎn)

?然后把原頭節(jié)點(diǎn)釋放

free(*pps);

最后讓*pps指向新的頭節(jié)點(diǎn)

*pps = Next;

所以代碼如下

void SLPopHead(SLNode** pps)//頭刪
{assert(pps && *pps);//pps和鏈表都不能為空SLNode* Next = (*pps)->next;//存節(jié)點(diǎn)free(*pps);*pps = Next;
}

當(dāng)鏈表只有一個(gè)節(jié)點(diǎn)時(shí)，分析一下，上面的代碼也是可以完成的

我們?cè)?span style="color:#ed7976;">test.c中測(cè)試一下

void SListtest2()
{SLNode* plist = NULL;//空鏈表SLPushBack(&plist, 1);//尾插SLPushBack(&plist, 2);SLPrint(plist);//打印SLPushHead(&plist, 6);//頭插SLPushHead(&plist, 7);SLPrint(plist);//打印SLPopBack(&plist);//尾刪SLPrint(plist);//打印SLPopHead(&plist);//頭刪SLPrint(plist);//打印
}

下篇我們?cè)倮^續(xù)介紹更多內(nèi)容，拜拜~