前言

上一章，我們講了數(shù)據(jù)結(jié)構(gòu)--動(dòng)態(tài)順序表，我們會(huì)發(fā)現(xiàn)有以下問(wèn)題：

1.當(dāng)我們要頭部或者插入或刪除時(shí)，都需要進(jìn)行位置挪動(dòng)，騰出某一個(gè)位置，時(shí)間復(fù)雜度為0(N)；

2.增容需要申請(qǐng)新空間，拷貝數(shù)據(jù)，釋放舊空間。會(huì)有不小的消耗。

3.增容會(huì)有一定的浪費(fèi)空間；例如當(dāng)前容量為100，滿了以后增容到200，我們?cè)倮^續(xù)插入了5個(gè)數(shù)據(jù)，后面沒(méi)有數(shù)據(jù)插入了，那么就浪費(fèi)了95個(gè)數(shù)據(jù)空間。

下面我們來(lái)看看單鏈表這種線性結(jié)構(gòu)；

---

鏈表

概念與結(jié)構(gòu)

鏈表是一種常見(jiàn)的數(shù)據(jù)結(jié)構(gòu)，用于存儲(chǔ)和組織數(shù)據(jù)。它由一系列節(jié)點(diǎn)組成，每個(gè)節(jié)點(diǎn)包含兩部分：數(shù)據(jù)和指向下一個(gè)節(jié)點(diǎn)的指針。

鏈表中的節(jié)點(diǎn)在內(nèi)存中可以分布在任意位置，不像數(shù)組那樣需要連續(xù)的存儲(chǔ)空間。每個(gè)節(jié)點(diǎn)都包含了存儲(chǔ)的數(shù)據(jù)以及指向下一個(gè)節(jié)點(diǎn)的指針。通過(guò)這種方式，鏈表可以靈活地分配和管理內(nèi)存空間。就像一節(jié)節(jié)連動(dòng)的火車車廂；

?在數(shù)據(jù)結(jié)構(gòu)中，呈現(xiàn)：

?邏輯圖中，呈現(xiàn)：

?在邏輯圖中，鏈?zhǔn)浇Y(jié)構(gòu)是連續(xù)性的，但實(shí)際上不一樣連續(xù)；從數(shù)據(jù)結(jié)構(gòu)中看出，鏈表是通過(guò)地址來(lái)聯(lián)系在一起的，不需要地址的連續(xù)性；在我們要解決鏈表相關(guān)問(wèn)題時(shí)，只需要畫(huà)出邏輯圖即可；

?注意：

結(jié)點(diǎn)的空間在堆區(qū)中開(kāi)辟；堆區(qū)中申請(qǐng)出的空間，會(huì)按照一定的策略進(jìn)行分配，兩次申請(qǐng)的空間可能連續(xù)，可能不連續(xù)；

鏈表的分類

實(shí)際中鏈表的結(jié)構(gòu)非常多樣，以下情況組合起來(lái)就有8種鏈表結(jié)構(gòu)：

1. 單向或者雙向

2. 帶頭或者不帶頭
?

3. 循環(huán)或者非循環(huán)
?

可以通過(guò)一定的組合達(dá)成不同種類的鏈表；

這里我們比較常用的是有兩種結(jié)構(gòu)：

?

?在這里，我們將先實(shí)現(xiàn)無(wú)頭單向非循環(huán)鏈表，這是鏈表中結(jié)構(gòu)最為簡(jiǎn)單的；簡(jiǎn)稱單鏈表。

---

單鏈表的接口實(shí)現(xiàn)

先寫(xiě)一下它的結(jié)構(gòu)：

#include<stdio.h>
#include<assert.h>
#include<stdlib.h>typedef int SLTDataType;
typedef struct SLTNode
{SLTDataType data;struct SListNode* next;}SLTNode;

結(jié)構(gòu)體中放入一個(gè)數(shù)據(jù)存儲(chǔ)類型和一個(gè)結(jié)構(gòu)體指針；結(jié)構(gòu)體指針存放下一個(gè)結(jié)點(diǎn)的地址；

單鏈表打印

void SLTrint(SLTNode* phead)
{SLTNode* cur = phead;while (cur){printf("%d->", cur->data);cur = cur->next;}printf("NULL\n");
}

將鏈表從頭到尾遍歷一遍，用一個(gè)cur指針來(lái)進(jìn)行移動(dòng)，在while循環(huán)中不斷遍歷打印出結(jié)果；打印完就進(jìn)入下一個(gè)結(jié)點(diǎn)；

增加鏈表結(jié)點(diǎn)

SLTNode* BuySListNode(SLTDataType x)
{SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));if (newnode == NULL){perror("mallco fail");exit(-1);}newnode->data = x;newnode->next = NULL;return newnode;
}

用動(dòng)態(tài)內(nèi)存分配進(jìn)行擴(kuò)容，同時(shí)對(duì)data和next進(jìn)行初始化；最后返回結(jié)點(diǎn)；

?

尾插

void SLPushBack(SLTNode** pphead, SLTDataType x)
{assert(pphead);SLTNode* newnode = BuySListNode(x);if (* pphead == NULL){* pphead = newnode;}else{SLTNode* tail = * pphead;while (tail->next != NULL){tail = tail->next;}tail->next = newnode;}}

這里要注意，我們的形參用到了二級(jí)指針，因?yàn)?strong>當(dāng)結(jié)構(gòu)體指針為空時(shí)，我們就需要對(duì)結(jié)構(gòu)體指針進(jìn)行改變，用二級(jí)指針接收結(jié)構(gòu)體指針的地址，能夠有效的訪問(wèn)，否則將會(huì)報(bào)錯(cuò)；當(dāng)結(jié)構(gòu)體指針不為空時(shí)，就利用結(jié)構(gòu)體指針通過(guò)循環(huán)訪問(wèn)到尾結(jié)點(diǎn)，然后在尾結(jié)點(diǎn)進(jìn)行連接；

?

驗(yàn)證：

void Test3()
{SLTNode* plist = NULL;SLPushBack(&plist, 1);SLPushBack(&plist, 2);SLPushBack(&plist, 3);SLPushBack(&plist, 4);SLTrint(plist);}
int main()
{Test3();return 0;
}

?尾刪

void SLPopBack(SLTNode** pphead)
{assert(pphead);//判空assert(*pphead);//一個(gè)節(jié)點(diǎn)if ((*pphead)->next == NULL){free(*pphead);*pphead = NULL;}//其他else{SLTNode* tailPrev = NULL;SLTNode* tail = *pphead;while (tail->next){tailPrev = tail;tail = tail->next;}free(tail);tailPrev->next = NULL;}
}

當(dāng)刪除的是第一個(gè)結(jié)點(diǎn)，將會(huì)改變結(jié)構(gòu)體指針的地址，所以形參要引用二級(jí)指針；其他情況就先找到尾結(jié)點(diǎn)，然后進(jìn)行刪除；

?

驗(yàn)證：

void Test3()
{SLTNode* plist = NULL;SLPushBack(&plist, 1);SLPushBack(&plist, 2);SLPushBack(&plist, 3);SLPushBack(&plist, 4);SLTrint(plist);SLPopBack(&plist);SLTrint(plist);}
int main()
{Test3();return 0;
}

?頭插頭刪

void SLPushFront(SLTNode** pphead, SLTDataType x)
{assert(pphead);SLTNode* newnode = BuySListNode(x);newnode->next = *pphead;*pphead = newnode;}void SLPopFront(SLTNode** pphead)
{	assert(pphead);//判空assert(*pphead);//其他SLTNode* newhead = (*pphead)->next;free(*pphead);*pphead = newhead;
}

頭插相對(duì)尾插來(lái)說(shuō)比較容易，因?yàn)橛蓄^指針，所以不用遍歷循環(huán)來(lái)找到尾結(jié)點(diǎn)；并且無(wú)論頭節(jié)點(diǎn)是否為空，操作程序都保持一致；

頭刪只要找到頭結(jié)點(diǎn)的下一個(gè)結(jié)點(diǎn)，那么就可以刪除了；

?

驗(yàn)證：

void Test2()
{SLTNode* plist = NULL;SLPushBack(&plist, 1);SLPushBack(&plist, 2);SLPushBack(&plist, 3);SLPushBack(&plist, 4);SLPushBack(&plist, 5);SLTrint(plist);SLPushFront(&plist, 6);SLPushFront(&plist, 7);SLPushFront(&plist, 8);SLPushFront(&plist, 9);SLTrint(plist);SLPopFront(&plist);SLTrint(plist);}int main()
{Test2();return 0;
}

?查找與插入

SLTNode* SLFind(SLTNode* phead, SLTDataType x)
{//判空assert(phead);SLTNode* cur = phead;while (cur){if (cur->data == x){return cur;}cur = cur->next;}return NULL;
}void SLTInsertAfter(SLTNode* pos, SLTDataType x)
{assert(pos);SLTNode* newnode = BuySListNode(x);newnode->next = pos->next;pos->next = newnode;}

查找：在循環(huán)里面通過(guò)結(jié)點(diǎn)的data與x進(jìn)行匹配，找到就返回該結(jié)點(diǎn)，找不到返回空；如果有多個(gè)結(jié)點(diǎn)的data與x一致，返回鏈表最接近頭指針的；

插入：是在pos后面進(jìn)行插入，這樣插入比較方便，不用考慮頭指針是否為空的問(wèn)題；

?

驗(yàn)證：

void Test3()
{SLTNode* plist = NULL;SLPushBack(&plist, 1);SLPushBack(&plist, 2);SLPushBack(&plist, 3);SLPushBack(&plist, 4);SLTrint(plist);SLTNode* pos = SLFind(plist, 3);SLTInsertAfter(pos, 88);SLTrint(plist);}
int main()
{Test3();return 0;
}

刪除pos結(jié)點(diǎn)

void SLTErase(SLTNode** pphead, SLTNode* pos)
{assert(pos);if (pos == *pphead){SLPopFront(pphead);}else{SLTNode* perv = *pphead;while (perv->next != pos){perv = perv->next;}perv->next = pos->next;free(pos);}
}void SLTEraseAfter(SLTNode* pos)
{assert(pos);//檢查尾節(jié)點(diǎn)assert(pos->next);SLTNode* posNext = pos->next;pos->next = posNext->next;free(posNext);}

第一種刪除是刪除pos結(jié)點(diǎn)，但需要判斷該結(jié)點(diǎn)是否為首結(jié)點(diǎn)；而且需要遍歷找到pos結(jié)點(diǎn)的前一個(gè)結(jié)點(diǎn)；比較麻煩；

第二種刪除是刪除pos結(jié)點(diǎn)后一個(gè)結(jié)點(diǎn)，只需要通過(guò)pos結(jié)點(diǎn)連接到下下一個(gè)結(jié)點(diǎn)即可，最后free掉pos的下一個(gè)結(jié)點(diǎn)；

驗(yàn)證：

void Test3()
{SLTNode* plist = NULL;SLPushBack(&plist, 1);SLPushBack(&plist, 2);SLPushBack(&plist, 3);SLPushBack(&plist, 4);SLTrint(plist);SLTNode* pos = SLFind(plist, 3);SLTInsertAfter(pos, 88);SLTrint(plist);SLTErase(&plist, pos);SLTrint(plist);}
int main()
{Test3();return 0;
}

?

void Test3()
{SLTNode* plist = NULL;SLPushBack(&plist, 1);SLPushBack(&plist, 2);SLPushBack(&plist, 3);SLPushBack(&plist, 4);SLTrint(plist);SLTNode* pos = SLFind(plist, 3);SLTInsertAfter(pos, 88);SLTrint(plist);SLTEraseAfter(pos);SLTrint(plist);}
int main()
{Test3();return 0;
}

?摧毀

void SLTDestroy(SLTNode** pphead)
{assert(pphead);SLTNode* cur = *pphead;while (cur){SLTNode* prev = cur;cur = cur->next;free(prev);}*pphead = NULL;
}

通過(guò)記住頭結(jié)點(diǎn)的下一個(gè)結(jié)點(diǎn)，free掉頭節(jié)點(diǎn)，然后頭節(jié)點(diǎn)的下一個(gè)結(jié)點(diǎn)成為新的頭節(jié)點(diǎn)；

驗(yàn)證：

void Test3()
{SLTNode* plist = NULL;SLPushBack(&plist, 1);SLPushBack(&plist, 2);SLPushBack(&plist, 3);SLPushBack(&plist, 4);SLTrint(plist);SLTNode* pos = SLFind(plist, 3);SLTInsertAfter(pos, 88);SLTrint(plist);SLTDestroy(&plist);SLTrint(plist);
}
int main()
{Test3();return 0;
}

?完整代碼

slist.h

#pragma once
#include<stdio.h>
#include<assert.h>
#include<stdlib.h>typedef int SLTDataType;
typedef struct SLTNode
{SLTDataType data;struct SListNode* next;}SLTNode;void SLTrint(SLTNode* phead);
SLTNode* BuySListNode(SLTDataType x);
void SLPushBack(SLTNode** pphead, SLTDataType x);
void SLPushFront(SLTNode** pphead, SLTDataType x);
void SLPopBack(SLTNode** pphead);
void SLPopFront(SLTNode** pphead);
SLTNode* SLFind(SLTNode* phead, SLTDataType x);
void SLTInsertAfter(SLTNode* pos, SLTDataType x);
void SLTErase(SLTNode** pphead, SLTNode* pos);
void SLTEraseAfter(SLTNode* pos);
void SLTDestroy(SLTNode** phead);

slist.c

#define  _CRT_SECURE_NO_WARNINGS 1
#include"Slist.h"void SLTrint(SLTNode* phead)
{SLTNode* cur = phead;while (cur){printf("%d->", cur->data);cur = cur->next;}printf("NULL\n");
}SLTNode* BuySListNode(SLTDataType x)
{SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));if (newnode == NULL){perror("mallco fail");exit(-1);}newnode->data = x;newnode->next = NULL;return newnode;
}void SLPushBack(SLTNode** pphead, SLTDataType x)
{assert(pphead);SLTNode* newnode = BuySListNode(x);if (* pphead == NULL){* pphead = newnode;}else{SLTNode* tail = * pphead;while (tail->next != NULL){tail = tail->next;}tail->next = newnode;}}void SLPushFront(SLTNode** pphead, SLTDataType x)
{assert(pphead);SLTNode* newnode = BuySListNode(x);newnode->next = *pphead;*pphead = newnode;}void SLPopBack(SLTNode** pphead)
{assert(pphead);//判空assert(*pphead);//一個(gè)節(jié)點(diǎn)if ((*pphead)->next == NULL){free(*pphead);*pphead = NULL;}//其他else{SLTNode* tailPrev = NULL;SLTNode* tail = *pphead;while (tail->next){tailPrev = tail;tail = tail->next;}free(tail);tailPrev->next = NULL;}
}
void SLPopFront(SLTNode** pphead)
{	assert(pphead);//判空assert(*pphead);//其他SLTNode* newhead = (*pphead)->next;free(*pphead);*pphead = newhead;
}SLTNode* SLFind(SLTNode* phead, SLTDataType x)
{//判空assert(phead);SLTNode* cur = phead;while (cur){if (cur->data == x){return cur;}cur = cur->next;}return NULL;
}void SLTInsertAfter(SLTNode* pos, SLTDataType x)
{assert(pos);SLTNode* newnode = BuySListNode(x);newnode->next = pos->next;pos->next = newnode;}void SLTErase(SLTNode** pphead, SLTNode* pos)
{assert(pos);if (pos == *pphead){SLPopFront(pphead);}else{SLTNode* perv = *pphead;while (perv->next != pos){perv = perv->next;}perv->next = pos->next;free(pos);}
}void SLTEraseAfter(SLTNode* pos)
{assert(pos);//檢查尾節(jié)點(diǎn)assert(pos->next);SLTNode* posNext = pos->next;pos->next = posNext->next;free(posNext);}void SLTDestroy(SLTNode** pphead)
{assert(pphead);SLTNode* cur = *pphead;while (cur){SLTNode* prev = cur;cur = cur->next;free(prev);}*pphead = NULL;
}

test.c

#define  _CRT_SECURE_NO_WARNINGS 1
#include"Slist.h"void Test1()
{int n;SLTNode* plist = NULL;printf("請(qǐng)輸入鏈表長(zhǎng)度");scanf("%d", &n);printf("請(qǐng)輸入值");for (int i = 0; i < n; i++){int val;scanf("%d", &val);SLTNode* newnode = BuySListNode(val);newnode->next = plist;plist = newnode;}SLTrint(plist);
}void Test2()
{SLTNode* plist = NULL;SLPushBack(&plist, 1);SLPushBack(&plist, 2);SLPushBack(&plist, 3);SLPushBack(&plist, 4);SLPushBack(&plist, 5);SLTrint(plist);SLPushFront(&plist, 6);SLPushFront(&plist, 7);SLPushFront(&plist, 8);SLPushFront(&plist, 9);SLTrint(plist);SLPopFront(&plist);SLTrint(plist);}void Test3()
{SLTNode* plist = NULL;SLPushBack(&plist, 1);SLPushBack(&plist, 2);SLPushBack(&plist, 3);SLPushBack(&plist, 4);SLTrint(plist);SLTNode* pos = SLFind(plist, 3);SLTInsertAfter(pos, 88);SLTrint(plist);SLTDestroy(&plist);SLTrint(plist);
}
int main()
{Test3();return 0;
}