“希望就像星星，或許光芒微弱，但永不熄滅。”

博主的個人gitee：https://gitee.com/friend-a188881041351

---

一.概念與結構

鏈表是一種物理存儲上非連續、非順序的存儲結構，數據元素的順序邏輯是通過鏈表中的指針鏈接次序實現的。

單鏈表由一系列節點組成，每個節點包含兩部分：

1. 數據部分：存儲實際的數據。

2. 指針部分：存儲指向下一個節點的指針。

單鏈表的特點是：

• 每個節點通過指針連接到下一個節點。

• 除了最后一個節點外，每個節點都有一個后繼節點。

• 單鏈表的頭節點（頭指針）是鏈表的入口。

二.單鏈表的定義

1.鏈表的組成

鏈表是由節點構成的。鏈表中每個結點都是獨立申請的（即需要插入數據時才去申請?塊結點的空間），我們需要通過指針變量來保存下?個結點位置才能從當前結點找到下?個結點。

2.鏈表的性質

• 鏈式機構在邏輯上是連續的，在物理結構上不?定連續。
• 結點?般是從堆上申請的。
• 從堆上申請來的空間，是按照?定策略分配出來的，每次申請的空間可能連續，可能不連續。

3.單鏈表的定義

typedef int SLTDataType;
typedef struct SListNode 
{SLTDataType data;struct SListNode* next;//指向下一個結點的指針
}SLTNode;

當我們想要保存?個整型數據時，實際是向操作系統申請了一塊內存，這個內存不僅要保存整型數 據，也需要保存下一個結點的地址（當下?個結點為空時保存的地址為空）。

當我們想要從第?個結點走到最后?個結點時，只需要在當前結點拿上下一個結點的地址就可以了。

三.單鏈表的操作（增、刪、查、改）

先在"List.h"中：

//phead：頭（首）結點
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* phead, SLTDataType x);//在指定位置之前插?數據
void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x);//在指定位置之后插?數據
void SLTInsertAfter(SLTNode* pos, SLTDataType x);//刪除pos結點
void SLTErase(SLTNode** pphead, SLTNode* pos);//刪除pos之后的結點
void SLTEraseAfter(SLTNode* pos);//銷毀鏈表
void SListDestroy(SLTNode** pphead);

先寫前置函數方便接下來的代碼編寫：

//向操作系統申請一個新節點
SLTNode* SLTBuyNode(SLTDataType x)
{SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));if (newnode == NULL){perror("malloc fail!");exit(1);}newnode->data = x;newnode->next = NULL;return newnode;
}

1.單鏈表插入元素

a.頭插

void SLTPushFront(SLTNode** pphead, SLTDataType x)
{assert(pphead);SLTNode* newnode = SLTBuyNode(x);newnode->next = *pphead;*pphead = newnode;
}

b.尾插

void SLTPushBack(SLTNode** pphead, SLTDataType x)
{assert(pphead);SLTNode* newnode = SLTBuyNode(x);//鏈表為空，phead直接指向newnode結點if (*pphead == NULL){*pphead = newnode;}else {   //鏈表不為空，找尾結點，將尾結點和新節點連接起來SLTNode* ptail = *pphead;while (ptail->next)//等價于ptail->next != NULL{ptail = ptail->next;}ptail->next = newnode;}
}

c.在指定位置之前插入數據

void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x)
{assert(pphead && pos);//pos就是頭結點if (pos == *pphead){//頭插SLTPushFront(pphead, x);}else {SLTNode* newnode = SLTBuyNode(x);//pos在頭結點之后--->找pos前驅節點SLTNode* prev = *pphead;while (prev->next != pos){prev = prev->next;}//prev newnode  posnewnode->next = pos;prev->next = newnode;}
}

d.在指定位置之后插入數據

void SLTInsertAfter(SLTNode* pos, SLTDataType x)
{assert(pos);SLTNode* newnode = SLTBuyNode(x);newnode->next = pos->next;pos->next = newnode;
}

2.單鏈表刪除元素

a.尾刪

void SLTPopBack(SLTNode** pphead)
{assert(pphead && *pphead);//只有一個結點的情況if ((*pphead)->next == NULL){free(*pphead);*pphead = NULL;}else {SLTNode* prev = NULL;SLTNode* ptail = *pphead;while (ptail->next){prev = ptail;ptail = ptail->next;}//prev ptailprev->next = NULL;free(ptail);ptail = NULL;}
}

b.頭刪

void SLTPopFront(SLTNode** pphead)
{assert(pphead && *pphead);SLTNode* next = (*pphead)->next;free(*pphead);*pphead = next;
}

c.刪除指定位置的數據

void SLTErase(SLTNode** pphead, SLTNode* pos)
{assert(pphead && pos);//要刪除的結點剛好就是頭結點---頭刪if (pos == *pphead){SLTPopFront(pphead);}else {//prevSLTNode* prev = *pphead;while (prev->next != pos){prev = prev->next;}//prev pos pos->nextprev->next = pos->next;free(pos);pos = NULL;}
}

d.刪除指定位置之后的數據

void SLTEraseAfter(SLTNode* pos)
{assert(pos && pos->next);SLTNode* del = pos->next;pos->next = del->next;free(del);del = NULL;
}

3.單鏈表查找元素

SLTNode* SLTFind(SLTNode* phead, SLTDataType x)
{SLTNode* pcur = phead;while (pcur){if (pcur->data == x){return pcur;}pcur = pcur->next;}//未找到return NULL;
}

4.鏈表的銷毀

void SListDestroy(SLTNode** pphead)
{assert(pphead);SLTNode* pcur = *pphead;while (pcur){SLTNode* next = pcur->next;free(pcur);pcur = next;}*pphead = NULL;
}

---

如有錯誤，懇請指正.

?