????????????????????????????????????????????????????????歡迎光顧我的homepage

前言????????

????????鏈表和順序表都是線性表的一種，但是順序表在物理結構和邏輯結構上都是連續的，但鏈表在邏輯結構上是連續的，而在物理結構上不一定連續；來看以下圖片來認識鏈表與順序表的差別

這里以動態順序表為例，和鏈表中的單鏈表對比一下

動態順序表

單鏈表

? ? ? ? 這里就可以很清晰的看到順序表的底層其實就是一個數組，數據的是連續存儲的（順序表物理結構連續）；而鏈表它每一個數據都不是連續的（鏈表物理結構上不一定連續）。

鏈表節點

? ? ? ? 通過觀察上圖，我們會發現鏈表每一個節點都存放在數據和下一個節點的地址。

????????那么來想一下，為了鏈表每一個節點都統一起來，都存儲有效數據和下一個節點的地址，我們就需要創建應該結構體，來存儲有效數據和下一個節點的指針；
注：這里只是單鏈表

typedef int SLType;
typedef struct SLTNode
{SLType data;struct SLTNode* next;
}SLT;

創建好鏈表節點，接下來就來實習單鏈表存儲數據的這些功能。

單鏈表實現

先來看一下單鏈表都實現都哪些功能

//輸出鏈表
void SLTPrint(SLT* phead);
//創建節點
SLT* SLTCreat(SLType x);
//單鏈表頭插
void SLTPushFront(SLT** pphead, SLType x);
//單鏈表尾插
void SLTPushBack(SLT** pphead, SLType x);
//單鏈表頭刪
void SLTPopFront(SLT** pphead);
//單鏈表尾刪
void SLTPopBack(SLT** pphead);
//查找數據
SLT* SLTFind(SLT* phead, SLType x);
//指定位置之前插入
void SLTInsert(SLT** pphead, SLT* pos, SLType x);
//指定位置之后插入
void SLTInsertAfter(SLT* pos, SLType x);
//刪除指定節點
void SLTErase(SLT** pphead, SLT* pos);
//刪除指定位置后一個節點
void SLTEraseAfter(SLT* pos);

創建節點

? ? ? ? 這里創建節點，還是使用動態內存來創建，創建完成后，將數據存儲進去，并把新節點的下一個節點置為NULL

代碼如下：

//創建節點
SLT* SLTCreat(SLType x)
{SLT* newnode = (SLT*)malloc(sizeof(SLT));assert(newnode);newnode->data = x;newnode->next = NULL;return newnode;
}

? ? ? ? 測試一下代碼是否正確

可以看到代碼沒有問題。

輸出鏈表

? ? ? ? 由于這里實現單鏈表，存儲的是整型數據，就以整型的方式輸出，若存儲其他類型的數據，就以存儲類型的方式輸出。

輸出鏈表，首先就要遍歷鏈表，因為鏈表最后一個節點里存儲的下一個節點的地址為空（即最后一個節點? ->next 為空）所以，遍歷鏈表結束的條件就是ptail?==NULL，沒輸出一個就讓ptail指向下一個節點，直到為空，遍歷結束。

? ? ? ? 來寫代碼實現：

//輸出鏈表
void SLTPrint(SLT* phead)
{SLT* ptail = phead;while (ptail!= NULL)//也可以直接寫成 ptail{printf("%d -> ", ptail->data);ptail = ptail->next;}printf("NULL\n");
}

這里先創建兩個節點并存儲數據輸出看一下結果

int main()
{SLT* plist = SLTCreat(1);plist->next = SLTCreat(2);SLTPrint(plist);return 0;
}

? ? ? ? 這里也成功輸出插入的兩個數據。（最后一個節點的next指向空）

單鏈表頭插

? ? ? ? 在鏈表頭部插入數據，不用像順序表那樣去移動所以的有效數據，鏈表只需要改變一個指針的指向即可

假設現在鏈表中已經存在兩個數據，再進行頭插，這時就只需要改變plist的指向即可，當然新節點的next指針也要指向下一個節點(plist指向的節點)。

代碼如下：

//單鏈表頭插
void SLTPushFront(SLT** pphead, SLType x)
{assert(pphead);SLT* newnode = SLTCreat(x);newnode->next = *pphead;*pphead = newnode;
}

還有一種情況，如果現在鏈表中沒有數據，再進行頭插，這里代碼也能實現鏈表沒有數據時的頭插

單鏈表尾插

? ? ? ? 鏈表的尾插，因為指針傳的是指向頭節點的指針的地址，所以，我們需要先遍歷鏈表，找到鏈表的尾部，再修改尾節點的next指針指向。

假設現在鏈表中已經存在兩個數據，再進行尾插，此時我們只需要找到鏈表的尾部，修改尾節點next指針指向即可，代碼如下

//單鏈表尾插
void SLTPushBack(SLT** pphead, SLType x)
{assert(pphead);SLT* newnode = SLTCreat(x);SLT* ptail = *pphead;//遍歷鏈表while (ptail->next){ptail = ptail->next;}ptail->next = newnode;
}

????????考慮了這種情況，再來看以下鏈表為空的情況，如果鏈表為空，這里ptail->next就對空指針進行解引用操作了；所以，我們需要判斷鏈表是否為空？如果為空，插入的新節點就是頭節點，直接讓plist（即*pphead)指向新節點即可；如果不為空就正常進行尾插。

最終代碼如下：

//單鏈表尾插
void SLTPushBack(SLT** pphead, SLType x)
{	assert(pphead);SLT* newnode = SLTCreat(x);if (*pphead == NULL) //判斷鏈表是否為空{*pphead = newnode;}else {SLT* ptail = *pphead;//遍歷鏈表while (ptail->next){ptail = ptail->next;}ptail->next = newnode;}
}

這里代碼可以正常進行尾插。

單鏈表頭刪

? ? ? ? 鏈表頭刪，首先我們要判斷鏈表是否為空，如果為空（空鏈表沒有數據該如何刪除呢）

鏈表頭刪，我們需要修改plist（*pphead）指向鏈表的下一個節點即頭節點的next指針。

? ? ? ? 此外：因為我們的節點都是動態申請的內存，所以在刪除時，需要把它釋放掉。

思路很簡單，寫一下代碼：
?

//單鏈表頭刪
void SLTPopFront(SLT** pphead)
{assert(pphead && *pphead);SLT* del = (*pphead);*pphead = (*pphead)->next;free(del);del = NULL;
}

再來看一個如果鏈表為空，又是啥結果呢？

現在鏈表已經為空，在執行一次頭刪代碼

這里assert斷言報錯。

單鏈表尾刪

? ? ? ? 首先尾刪與頭刪一樣，鏈表不能為空。

? ? ? ? 尾刪與尾插也有共同之處，就是遍歷鏈表，找到鏈表的尾節點。找到尾節點，刪除尾節點；然后修改尾節點上一個節點的next指針為NULL；所以在遍歷鏈表時就要多記錄一個節點。

//單鏈表尾刪
void SLTPopBack(SLT** pphead)
{assert(pphead && *pphead);SLT* ptail = *pphead;SLT* pcur = *pphead;//遍歷鏈表while (ptail->next){pcur = ptail;ptail = ptail->next;}pcur->next = NULL;free(ptail);ptail  = NULL;
}

????????在測試的時候我們會發現一個問題，如果鏈表只有一個節點，刪除之后我們的plist指針并沒有置為空，而我們的空間已經釋放掉了，這是很危險的；所以這里我們先判斷一下鏈表是否只有一個節點，如果是，我們釋放完空間以后，將(*pphead)置為空，以免出現野指針的情況。

完善后代碼：

//單鏈表尾刪
void SLTPopBack(SLT** pphead)
{assert(pphead && *pphead);if ((*pphead)->next== NULL){free(*pphead);*pphead = NULL;}else {SLT* ptail = *pphead;SLT* pcur = *pphead;//遍歷鏈表while (ptail->next){pcur = ptail;ptail = ptail->next;}free(ptail);ptail = NULL;pcur->next = NULL;}
}

測試沒有問題，代碼能夠完成尾刪這個功能。

查找數據

? ? ? ? 查找數據，遍歷鏈表查找數據，如果找到就返回數據所在節點的地址，如果沒有找到就返回NULL;

//查找數據
SLT* SLTFind(SLT* phead, SLType x)
{SLT* ptail = phead;while (ptail){if (ptail->data == x){return ptail;}ptail = ptail->next;}return NULL;
}

這里測試以下：

數據存在時

數據不存在時

指定節點之前插入

? ? ? ? 在鏈表指定節點之前插入數據，我們還需要知道指定節點的前一個節點，所以仍然需要遍歷鏈表，尋找指定節點pos前一個節點。

//指定位置之前插入
void SLTInsert(SLT** pphead, SLT* pos, SLType x)
{assert(pphead && *pphead);SLT* ptail = *pphead;if (ptail == pos)//頭插{SLTPushFront(pphead, x);}else{SLT* newnode = SLTCreat(x);while (ptail->next != pos)//找到pos位置{ptail = ptail->next;}newnode->next = pos;ptail->next = newnode;}
}

當然，這里如果故意傳NULL給pos，（這就沒啥意義了）這里也可以寫以下assert斷言pos。

指定節點之后插入

? ? ? ? 在指定節點之后插入數據，就不需要再進行遍歷鏈表，這里直接插入即可。

//指定位置之后插入
void SLTInsertAfter(SLT* pos, SLType x)
{assert(pos);SLT* newnode = SLTCreat(x);newnode->next = pos->next;pos->next = newnode;
}

刪除指定節點

? ? ? ? 刪除鏈表中的指定節點，我們需要這個節點的上一個節點，所以又需要遍歷鏈表，找到pos上一個節點，修改pos->next指針指向。

代碼如下：

//刪除指定節點
void SLTErase(SLT** pphead, SLT* pos)
{//找到pos上一個節點SLT* ptail = *pphead;while (ptail->next != pos){ptail = ptail->next;}SLT* p = pos->next;free(pos);pos = NULL;ptail->next = p;
}

刪除指定節點后一個節點

? ? ? ? 刪除鏈表指定節點后一個節點，因為pos就是刪除節點的上一個節點，所以不需要遍歷鏈表，直接刪除即可。

//刪除指定位置后一個節點
void SLTEraseAfter(SLT* pos)
{assert(pos->next);SLT* del = pos->next;pos->next = pos->next->next;free(del);del = NULL;
}

這里如果傳過來的就是鏈表的尾節點，那刪除后一個節點，所以斷言pos->next；

代碼總覽

#include"SList.h"
//創建節點
SLT* SLTCreat(SLType x)
{SLT* newnode = (SLT*)malloc(sizeof(SLT));assert(newnode);newnode->data = x;newnode->next = NULL;return newnode;
}
//輸出鏈表
void SLTPrint(SLT* phead)
{SLT* ptail = phead;while (ptail != NULL)//也可以直接寫成 ptail{printf("%d -> ", ptail->data);ptail = ptail->next;}printf("NULL\n");
}
//單鏈表頭插
void SLTPushFront(SLT** pphead, SLType x)
{assert(pphead);SLT* newnode = SLTCreat(x);newnode->next = *pphead;*pphead = newnode;
}
//單鏈表尾插
void SLTPushBack(SLT** pphead, SLType x)
{	assert(pphead);SLT* newnode = SLTCreat(x);if (*pphead == NULL) //判斷鏈表是否為空{*pphead = newnode;}else {SLT* ptail = *pphead;//遍歷鏈表while (ptail->next){ptail = ptail->next;}ptail->next = newnode;}
}
//單鏈表頭刪
void SLTPopFront(SLT** pphead)
{assert(pphead && *pphead);SLT* del = (*pphead);*pphead = (*pphead)->next;free(del);del = NULL;
}
//單鏈表尾刪
void SLTPopBack(SLT** pphead)
{assert(pphead && *pphead);if ((*pphead)->next== NULL){free(*pphead);*pphead = NULL;}else {SLT* ptail = *pphead;SLT* pcur = *pphead;//遍歷鏈表while (ptail->next){pcur = ptail;ptail = ptail->next;}free(ptail);ptail = NULL;pcur->next = NULL;}
}
//查找數據
SLT* SLTFind(SLT* phead, SLType x)
{SLT* ptail = phead;while (ptail){if (ptail->data == x){return ptail;}ptail = ptail->next;}return NULL;
}
//指定位置之前插入
void SLTInsert(SLT** pphead, SLT* pos, SLType x)
{assert(pphead && *pphead);SLT* ptail = *pphead;if (ptail == pos)//頭插{SLTPushFront(pphead, x);}else{SLT* newnode = SLTCreat(x);while (ptail->next != pos)//找到pos位置{ptail = ptail->next;}newnode->next = pos;ptail->next = newnode;}
}
//指定位置之后插入
void SLTInsertAfter(SLT* pos, SLType x)
{assert(pos);SLT* newnode = SLTCreat(x);newnode->next = pos->next;pos->next = newnode;
}
//刪除指定節點
void SLTErase(SLT** pphead, SLT* pos)
{//找到pos上一個節點SLT* ptail = *pphead;while (ptail->next != pos){ptail = ptail->next;}SLT* p = pos->next;free(pos);pos = NULL;ptail->next = p;
}
//刪除指定位置后一個節點
void SLTEraseAfter(SLT* pos)
{assert(pos->next);SLT* del = pos->next;pos->next = pos->next->next;free(del);del = NULL;
}

感謝各位大佬支持并指出問題，

如果本篇內容對你有幫助，可以一鍵三連支持以下，感謝支持！！！