上一篇【數(shù)據(jù)結構】順序表-CSDN博客??我們了解了順序表，但是呢順序表涉及到了一些問題，比如，中間/頭部的插入/刪除，時間復雜度為O(N);增容申請空間、拷貝、釋放舊空間會有不小的消耗；增容所浪費的空間... 我們如何去解決這些問題？本篇介紹另一個數(shù)據(jù)結構——鏈表

1. 鏈表的概念及結構

鏈表：是一種物理存儲結構上非連續(xù)、非順序的存儲結構，數(shù)據(jù)元素的邏輯順序是通過鏈表中的指針連接次序實現(xiàn)的，鏈表也是線性表的一種

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

鏈表是由一個一個的節(jié)點組成，再順序表中，數(shù)據(jù)是連續(xù)存放的，我們想找到下一個數(shù)據(jù)順著前一個數(shù)據(jù)找就行了，而鏈表中數(shù)據(jù)存放空間是不連續(xù)的，所以我們就需要一個指針來保存下一個節(jié)點的地址，所以，我們如果要定義鏈表，只需要定義鏈表的節(jié)點結構就行了

(在【C語言】結構體詳解-CSDN博客?的1.3 結構體的自引用 中介紹過)

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

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

?也是一樣，在頭文件SList.h中定義單鏈表的結構，并對類型和結構體改名

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

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

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

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

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

現(xiàn)在就構成了一個鏈表，有了這個簡單的鏈表，我們來寫一個函數(shù)打印一下里面的數(shù)據(jù)

鏈表的打印

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

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

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

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

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

要打印當然就要循環(huán)遍歷，寫一個while循環(huán)，判斷條件為pcur，不為NULL進入循環(huán)?

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

?進入循環(huán)后打印內容

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

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

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

在test.c中測試

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

    SLNode* plist = node1;SLPrint(plist);

雖然有點多此一舉，但這樣會讓我們的代碼更完善?

運行結果

?2.鏈表的插入

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

2.1空間申請創(chuàng)建節(jié)點

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

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

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

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

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

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

2.2?尾插

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

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

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

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

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

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

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

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

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

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

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

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

我們再來看test.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;
}

多插入幾個數(shù)據(jù)，運行看結果，插入成功

2.3 頭插

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

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

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

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

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

?鏈表不為NULL時，代碼如下

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

當鏈表為NULL時，分析一下

當前代碼也可以實現(xiàn)

在test.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);//打印
}

看一下運行結果

3.鏈表的刪除

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

?3.1 尾刪

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

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

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

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

所以我們還要找尾節(jié)點的前一個節(jié)點

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

如果這個鏈表只有一個節(jié)點呢，這個代碼可行嗎？來分析一下

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

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

在test.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);//打印
}

看下結果，尾刪成功

3.2 頭刪

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

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

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

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

我們應該先把下一個節(jié)點的信息存儲起來

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

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

free(*pps);

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

*pps = Next;

所以代碼如下

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

當鏈表只有一個節(jié)點時，分析一下，上面的代碼也是可以完成的

我們在test.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);//打印
}

下篇我們再繼續(xù)介紹更多內容，拜拜~