????????不可否認的是，前幾節(jié)我們講解的順序表存在一下幾點問題：
????????1. 中間、頭部的插入和刪除，需要移動一整串數(shù)據(jù)，時間復雜度O(N)
????????2. 增容需要申請新空間，拷貝數(shù)據(jù)，釋放舊空間。會有不小的消耗
????????3. 增容一般是2倍的增長，這勢必會造成空間的浪費
????????那如何解決這些問題呢，此時，鏈表出現(xiàn)了
1. 鏈表的概念和結構
????????我們之前說過，線性表的特點就是邏輯上是連續(xù)的，物理上不一定連續(xù)。順序表是邏輯上是連續(xù)的，物理上也是連續(xù)的。而今天的鏈表就是邏輯上是連續(xù)的，但是物理上是不連續(xù)的
????????最簡單的鏈表是由節(jié)點們串在一起組成的，每個節(jié)點包含了兩個內容：
????????????????1. 要存入的有效數(shù)據(jù)
????????????????2. 下一個節(jié)點的地址
? ? ? ? 可以看出，每個節(jié)點在物理上都是獨立的，不連續(xù)的。但是每個節(jié)點在邏輯上又有關聯(lián)，每個節(jié)點都知道下一個節(jié)點的指針，要找到下一個節(jié)點就訪問那個指針就好了
? ? ? ? 具體來講就是把 plist 當成一個鑰匙，最開始保存的是第一個節(jié)點的地址，用完第一個節(jié)點的數(shù)據(jù)之后，把第一個節(jié)點中存儲的地址再給到plist，這樣plist就可以開第二個節(jié)點了，以此類推···
????????下面我們依照上面的圖片做一個簡單的節(jié)點結構
????????????????????????????????
? ? ? ? 到這里，鏈表的地基就學會了，下面我們嘗試實現(xiàn)一下
2. 單鏈表(Single linked list)的實現(xiàn)
? ? ? ? 跟順序表一樣，先是把準備工作，三個文件準備好
????????????????????????????????
? ? ? ? 再把鏈表節(jié)點寫出來
????????????????????????? ? ? ? ???????
? ? ? ? 在這里我要重點聲明一下，接下來如果從主函數(shù)前去訪問鏈表時用的都是plist參數(shù)，從主函數(shù)中給子函數(shù)傳參也是plist，就像這樣
??????????????????????????????????????????????
? ? ? ? 然后就正式進入鏈表實現(xiàn)啦，大家伙坐穩(wěn)嘍
2.1 鏈表的打印
? ? ? ? 打印的邏輯就是先拿到第一個節(jié)點的地址 pcur，把這個地址訪問到 data 打印出來，然后將pcur的內容變成下一個要打印的節(jié)點的地址，直到pcur的內容是NULL為止
??????????????????????????????????????
2.2 鏈表的插入
? ? ? ? 因為插入就一定需要申請一個新的節(jié)點，所以我們先把這個功能封裝好
? ? ? ? 向堆區(qū)申請一塊空間用來存放節(jié)點，記錄這個節(jié)點的地址
? ? ? ? 當然，如果你想把newnode的類型改成 SLTNode 也可以，不過后面要用到節(jié)點地址的時候就要取地址一下，很麻煩，所以我們干脆直接返回節(jié)點的地址
2.2.1 尾插
? ? ? ? 在鏈表的尾端插入一個數(shù)據(jù)。
????????因為如果鏈表為空(沒有節(jié)點)的時候要修改 plist 的內容，讓它指向我們新添加的第一個節(jié)點，所以我們傳參的時候要傳 &plist ，因此函數(shù)參數(shù)要用二級指針來接收這個可能會被修改的plist
? ? ? ? 如果鏈表不為空，就去找尾節(jié)點，把為節(jié)點的next成員內容從NULL變成我們新添加的節(jié)點地址，可以這么理解：
? ? ? ? 這個圖里有一點不恰當，就是這個 pphead 要解引用一次 (*pphead) 才能找到第一個節(jié)點的地址
???????????????
????????接下來我們運行一下看看效果
2.2.2 頭插
? ? ? ? 頭插比尾插好理解一點，直接上思路圖(畫的太丑了QAQ)
????????
? ? ? ? 很明顯，鏈表是否為空對于需要的操作是沒有影響的，上代碼：
????????
? ? ? ? 最后運行一下看結果：
????????
? ? ? ? 因為每次都是把節(jié)點插到最前面，所以反著打出來是對的
2.3 鏈表的刪除
2.3.1 尾刪
? ? ? ? 尾刪的邏輯就是找到最后一個節(jié)點 ptail 和倒數(shù)第二個節(jié)點 prev ，把倒數(shù)第二個節(jié)點的next成員置為空指針，釋放掉最后一個節(jié)點。當然，如果鏈表為空，也就是說沒有節(jié)點的話就不能執(zhí)行刪除操作，用assert斷言報錯
??????????????????????????????????????
? ? ? ? 上代碼：
????????
2.3.2 頭刪
? ? ? ? 頭刪也是需要兩個指針控制，要注意的就是要先釋放掉*pphead也就是第一個節(jié)點，然后再把*pphead的內容改成第二個節(jié)點的地址，接上第二個節(jié)點
????????????????????? ? ? ??????????
? ? ? ? 代碼如下：
???????????????????????
2.4 查找
? ? ? ? 鏈表的查找很簡單，就是遍歷鏈表，找到了就返回節(jié)點地址，沒找到就返回空指針
????????
2.5?在任意位置插入數(shù)據(jù)
2.5.1?在指定位置前插入數(shù)據(jù)
? ? ? ? 可以用SLTFind找到要被前插的節(jié)點的地址pos，在這個節(jié)點前面插入節(jié)點，還需要直到它前面那個節(jié)點的地址prev
??????????????????????????????????????
? ? ? ? 在實現(xiàn)這個功能的時候我們要注意，當pos是頭節(jié)點的情況：
????????
? ? ? ? 下面使用一下
????????
2.5.2?在指定位置后插入數(shù)據(jù)
? ? ? ? 這個比較簡單，但是要注意給地址的順序，要先把后面那個節(jié)點的地址給到新節(jié)點，再把指定位置pos節(jié)點的地址成員改成新節(jié)點的地址，否則就會導致后面那個節(jié)點地址的丟失，沒辦法接到新節(jié)點后面了
? ? ? ? 還有就是我們不需要知道鏈表的頭節(jié)點是什么了，只需要關注pos就行了
??????????????????????????????????????
????????
2.6?在任意位置刪除節(jié)點
2.6.1?刪除pos節(jié)點
? ? ? ? 刪除pos節(jié)點要先知道它前面的那個節(jié)點prev，然后把prev跟pos后面那個節(jié)點先連起來，最后再把pos釋放掉。還有要注意的一點就是當pos就是鏈表頭節(jié)點的時候要特殊處理一下
????????????????????????????????????????
????????
2.6.2?刪除pos后面的一個節(jié)點
? ? ? ? 這個功能也是只需要關注pos后面的內容就行，所以只需要傳pos一個參數(shù)。還要注意一點就是pos不能是鏈表中的最后一個節(jié)點，否則它后面沒有節(jié)點了還刪什么
???????????????????????
???????????????????????
2.7 鏈表的銷毀
? ? ? ? 兩個變量，pcur記錄當前要準備銷毀的節(jié)點地址，next記錄下一個節(jié)點地址，防止銷毀上一個節(jié)點之后找不到下一個節(jié)點了。然后兩個變量一直循環(huán)向后掃描銷毀，直到pcur指向NULL
??????????????????????????????????????
????????????????????????
3. 鏈表的分類
????????鏈表按帶頭或不帶頭，單向或雙向，循環(huán)或不循環(huán)，排列組合有8種
????????我們剛剛學的單鏈表全稱就是：不帶頭單向不循環(huán)鏈表
????????帶頭不帶頭是說鏈表有沒有一個不存儲有效數(shù)據(jù)的節(jié)點，放在第一個存放有效數(shù)據(jù)節(jié)點之前
??????????????????????????????????????
????????單向雙向是說鏈表能通過后一項找到前一項就是雙向的，如果只能根據(jù)前一項找到后一項鏈表就是單項的?；蛘哒f雙向鏈表的節(jié)點中的兩個存放地址的成員中，一個存下一個節(jié)點的地址，一個存上一個節(jié)點的地址。
??????????????????????????????????????
????????循環(huán)不循環(huán)是說最后一個節(jié)點指向第一個節(jié)點就是循環(huán)鏈表，要是最后一個節(jié)點指向NULL就是不循環(huán)鏈表
????????????????????????
????????雖然鏈表的種類很多，但是常用的只有兩種：
????????????????1.單鏈表(不帶頭單向不循環(huán)鏈表)
? ? ? ? 單鏈表結構簡單，一般不會單獨用來存貯數(shù)據(jù)，它一般作為其他數(shù)據(jù)結構的子結構出現(xiàn)
????????????????2.雙向鏈表(帶頭雙向循環(huán)鏈表)
? ? ? ? 雙向鏈表結構最復雜，一般用來單獨存儲數(shù)據(jù)。它雖然復雜，但是之后實現(xiàn)它的實際就會發(fā)現(xiàn)它有很多優(yōu)勢，致使實現(xiàn)它反而變得簡單了，后面會有實現(xiàn)它的章節(jié)的。
4. 本節(jié)代碼
? ? ? ? SList.h文章來源：http://www.zghlxwxcb.cn/news/detail-824254.html
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
//鏈表是由節(jié)點構成的
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** pphead, SLTDataType x);
//在任意位置插入數(shù)據(jù)
//在指定位置前插入數(shù)據(jù)
void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x);
//在指定位置后插入數(shù)據(jù)
void SLTInsertAfter(SLTNode* pos, SLTDataType x);
//在任意位置刪除節(jié)點
//刪除pos節(jié)點
void SLTErase(SLTNode** pphead, SLTNode* pos);
//刪除pos后面的一個節(jié)點
void SLTEraseAfter(SLTNode* pos);
//銷毀鏈表
void SLTDestory(SLTNode** pphead);? ? ? ? SList.c文章來源地址http://www.zghlxwxcb.cn/news/detail-824254.html
#include"SList.h"
//鏈表的打印
void SLTPrint(SLTNode* phead)
{
SLTNode* pcur = phead;
while (pcur)
{
printf("%d -> ", pcur->data);
pcur = pcur->next;
}
printf("NULL\n");
}
//申請一個新節(jié)點
SLTNode* SLTBuyNode(SLTDataType x)
{
SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));
newnode->data = x;
newnode->next = NULL;
return newnode;
}
//鏈表的插入
//尾插
void SLTPushBack(SLTNode** pphead, SLTDataType x)
{
assert(pphead);
//申請一個新節(jié)點
SLTNode* newnode = SLTBuyNode(x);
//鏈表為空，新節(jié)點作為頭
if (*pphead == NULL)
{
*pphead = newnode;
return;
}
//鏈表不為空，找尾節(jié)點
SLTNode* ptail = *pphead;
while (ptail->next)
{
ptail = ptail->next;
}
//找到尾節(jié)點了
ptail->next = newnode;
}
//頭插
void SLTPushFront(SLTNode** pphead, SLTDataType x)
{
assert(pphead);
//申請一個新節(jié)點
SLTNode* newnode = SLTBuyNode(x);
//鏈表為不為空，操作都一樣
//斬斷第一個連接，再把新節(jié)點接進去
newnode->next = *pphead;
*pphead = newnode;
}
//鏈表的頭刪和尾刪
//尾刪
void SLTPopBack(SLTNode** pphead)
{
assert(pphead);
//鏈表不能為空
assert(*pphead);
//鏈表不為空
//鏈表只有一個節(jié)點
if ((*pphead)->next == NULL)
{
free(*pphead);
*pphead = NULL;
return;
}
//鏈表有多個節(jié)點
SLTNode* ptail = *pphead;
SLTNode* prev = NULL;
//找到尾節(jié)點
while (ptail->next)
{
prev = ptail;
ptail = ptail->next;
}
prev->next = NULL;
free(ptail);
ptail = NULL;
}
//頭刪
void SLTPopFront(SLTNode** pphead)
{
assert(pphead);
//鏈表不能為空
assert(*pphead);
//讓第二個節(jié)點變成新的頭節(jié)點
//釋放舊的頭節(jié)點
SLTNode* sec = (*pphead)->next;
free(*pphead);
*pphead = sec;
}
//查找
SLTNode* SLTFind(SLTNode** pphead, SLTDataType x)
{
assert(pphead);
//遍歷鏈表
SLTNode* pcur = *pphead;
while (pcur)
{
if (pcur->data == x)
{
return pcur;
}
pcur = pcur->next;
}
return NULL;
}
//在任意位置插入數(shù)據(jù)
//在指定位置前插入數(shù)據(jù)
void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x)
{
assert(pphead);
assert(pos);
//這里斷言*pphead不能為空
//因為指定節(jié)點的地址pos不能為空，所以這個鏈表也不能為空
assert(*pphead);
//當pos是頭節(jié)點,執(zhí)行頭插
if (pos == *pphead)
{
SLTPushFront(pphead, x);
return;
}
//當pos不是頭節(jié)點
//申請一個新節(jié)點
SLTNode* newnode = SLTBuyNode(x);
SLTNode* prev = *pphead;
while (prev->next != pos)
{
prev = prev->next;
}
prev->next = newnode;
newnode->next = pos;
}
//在指定位置后插入數(shù)據(jù)
void SLTInsertAfter(SLTNode* pos, SLTDataType x)
{
assert(pos);
//申請一個新節(jié)點
SLTNode* newnode = SLTBuyNode(x);
newnode->next = pos->next;
pos->next = newnode;
}
//在任意位置刪除節(jié)點
//刪除pos節(jié)點
void SLTErase(SLTNode** pphead, SLTNode* pos)
{
assert(pphead);
assert(pos);
assert(*pphead);
//如果pos指向頭節(jié)點，執(zhí)行頭刪
if (*pphead == pos)
{
SLTPopFront(pphead);
return;
}
SLTNode* prev = *pphead;
while (prev->next != pos)
{
prev = prev->next;
}
prev->next = pos->next;
free(pos);
pos = NULL;
}
//刪除pos后面的一個節(jié)點
void SLTEraseAfter(SLTNode* pos)
{
assert(pos);
//pos->next不能為空
//就是說pos不能是最后一個節(jié)點
assert(pos->next);
SLTNode* del = pos->next;
pos->next = pos->next->next;
free(del);
del = NULL;
}
//銷毀鏈表
void SLTDestory(SLTNode** pphead)
{
assert(pphead);
assert(*pphead);
SLTNode* pcur = *pphead;
SLTNode* next = NULL;
while (pcur)
{
next = pcur->next;
free(pcur);
pcur = next;
}
*pphead = NULL;
}
到了這里，關于數(shù)據(jù)結構·單鏈表的文章就介紹完了。如果您還想了解更多內容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關文章，希望大家以后多多支持TOY模板網(wǎng)！
