數據結構篇：線性表的另一表達—鏈表之單鏈表(下篇)

1.前言

2.是否使用二級指針

3.插入/刪除

? ? ? ? 3.1 pos位置前/后插入

3.2 查找函數

3.3 pos位置刪除

3.4 pos位置后面刪除

3.5 函數的銷毀?

4.斷言問題

? ? ? ? 4.1 斷言pphead

? ? ? ? 4.2 斷言*pphead

5.三個文件的代碼?

5.1 頭文件

5.2 具體函數實現

5.3 測試用例

1.前言

????????之前是講述了單鏈表的頭插尾插，頭刪尾刪函數部分，并且揭示了鏈表相對于順序表的優勢性。更重要的是對于next的理解和對二級指針的理解，為什么在單鏈表中用一級指針報錯而要用二級指針，其實簡單的說就是看會不會改變指針指向。

2.是否使用二級指針

? ? ? ? 在單鏈表中，無論是尾插還是尾刪。尾插的時候，在第一次插入元素的時候，沒有節點，頭節點是一個指向為空。實參那里一開始的鏈表初始化為空，是一個NULL。要尾插的時候，通過函數來改變外部的這個phead的指向，這個實參plist是一個一級指針，如果要通過函數來改變這個一級指針的指向，就是要傳二級指針，也就是一級指針的地址。

????????頭插的時候，傳的是二級指針，因為和尾插一樣，每次頭插都要改變頭節點的指向。

????????尾刪的時候，刪到最后一個節點，它就會改變頭節點的指向，仔細想，刪除最后一個節點刪沒了，頭節點這個時候指向應該指向空，所以也是要二級指針才能改變。

? ? ? ? 結論就是看這個頭節點會不會變，如果會變的話，就用二級指針，如果不變，那就不用傳二級指針。

3.插入/刪除

? ? ? ? 3.1 pos位置前/后插入

? ? ? ? 和順序表一樣?，鏈表也是可以在中間某個位置pos前/后插入的，而且在特殊位置，比如在第一個位置前插入，那等同于頭插。那么就可以把頭插的函數復用就可以了。思路是：定義一個前指針這里用former，找到pos的前一個位置，怎么找呢，有next這個節點，只要former的next不是pos的地址，就一直遍歷，直至找到。然后former的next指向新節點，新節點的next再指向pos。(相當于把former和pos之間的指針斷開了，重新進行了指向)，這是pos位置前插入的思路圖：

測試用例如下：找到3的位置，然后在3的位置前插入7

?????????當然也可以有頭插的效果，在判斷該位置是否是頭節點后，如果是，就復用頭插函數。

void SLTinsert(SLTnode** pphead,SLTnode*pos, Sltdatatype x)
{assert(pos);assert(pphead);//如果pos是第一個，就等于頭插if (pos == *pphead){//復用頭插函數SLTpushfront(pphead,x);}
}

????????測試當然也是成功的：

? ? ? ? pos位置后面插入，也是同理，先查找，是否有該位置存在，有就給出一個返回值。然后進行插入，那么既然在第一個位置前插入數據等同于頭插，那在最后一個位置后插入，是什么，應該是尾插吧。

????????思路就是找到pos后，先用一個next的指針保存原來pos的next，然后pos的next指向newnode，也就是新節點，最后新節點的next再指向保存原來pos的next的那個next指針。有點小繞，但畫個圖就明白了。保存是為了更方便點。這是順序的從左到右依次連接。

? ? ? ? 或者不那么繞，前者是pos->newnode->pos的下一個，形成了中間插入。也可以newnode->posd的next，pos->newnode。從后往前連接，就可以不用定義指針去保存pos的下一個節點。代碼會少一兩行。這里我選用第二種方法

void SLTinsert_afterpos(SLTnode** pphead,SLTnode *pos, Sltdatatype x)
{assert(pphead);assert(pos);SLTnode* newnode = insertSLTnode(x);newnode->next = pos->next;pos->next = newnode;
}

3.2 查找函數

? ? ? ? 在上文中，我們要在pos位置插入，和順序表一樣，也是需要先找到該位置才能進行插入，需要有個返回值，然后再調用插入函數。而查找函數思路也很簡單，只需要遍歷鏈表，找到是否有data等于x的值就可以，沒有就返回NULL。

SLTnode* SLTfind(SLTnode* pphead, Sltdatatype x)
{//遍歷SLTnode* cur = pphead;while (cur){if (cur->data==x){return cur;}cur = cur->next;}return NULL;
}

3.3 pos位置刪除

? ? ? ? 經過pos位置的前后插入練習，其實pos位置的刪除，pos位置后的刪除思路也是很明確了。正確掌握好鏈表的位置關系，以及對next的理解，就基本沒什么問題。刪除pos位置，也就是意味著要把pos的前后連起來，并且釋放掉pos位置。那么就需要有一個former指針，該指針的next指向pos的next，就可以了。思路圖如下：

????????特殊情況：如果要刪除的位置是頭節點，也就是頭刪，同樣復用頭刪函數。

void SLTErase(SLTnode** pphead, SLTnode* pos)
{assert(pphead);assert(*pphead);if (pos == *pphead){SLTpopfront(pphead);}else{SLTnode* former = *pphead;while (former->next != pos){former = former->next;}former->next = pos->next;free(pos);}
}

3.4 pos位置后面刪除

????????緊接著來看pos位置后刪除，這里同pos位置后插入一樣，有兩種寫法，一種是pos的next指向pos的next的next，就是跳過了中間的數據，因為中間的數據是要被刪除的。最后釋放掉pos后面的位置就行。

或者用一個有意義的名字定義個指針，該指針把要刪除的數據保存下來，pos的next和該指針的下一個連接起來就可以。兩者其實沒有本質區別的。?

void SLTerase_afterpos(SLTnode** pphead, SLTnode* pos)
{assert(pos->next);SLTnode* erase = pos->next;pos->next = pos->next->next;free(erase);erase = NULL;}

?之前的案例是在3的后面插入一個7，那么這次把7刪掉，就是可以用到pos后面刪除數據。

3.5 函數的銷毀?

? ? ? ? 由于我們申請的空間都是malloc出來，在堆上申請的，那根據malloc的特質，我們需要需要把它銷毀掉并且置空，防止內存泄露的問題出現。

????????銷毀的思路就是，把鏈表存放到一個指針中（cur）（這里不需要改變指針的指向，只是改變結構體的內容，所以只需要一級指針），用另一個指針next去保存當前節點的下一個，先釋放保存鏈表數據的cur指針，然后指針內容更新為節點的下一個，循環到鏈表為空。這里沒有進行置空，是因為函數的形參不改變實參，所以里面置空不影響外部函數鏈表的結果，一級指針改變不了一級指針的內容，如果要在里面更改就要傳遞二級指針。所以我傳的是一級指針，在外部置空。

void SLTdestory(SLTnode * phead)
{SLTnode* cur = phead;while (cur){SLTnode* next = cur->next;free(cur);cur=next;}
}

4.斷言問題

? ? ? ? 在寫單鏈表的過程中，每個函數是否要斷言，斷言哪些地方，是需要考慮的，不能一刀切，結合實際情況實際考慮的。

? ? ? ? 4.1 斷言pphead

????????首先斷言的情況是pphead傳入的是鏈表地址，鏈表的地址傳錯了的話是NULL會發生報錯，那么我們要斷言的情況，就是防止有空的誤傳進來（比如沒有取地址）。所以鏈表地址一定不為空。

? ? ? ? 4.2 斷言*pphead

? ? ? ? *pphead，是鏈表的內容，看*pphead有沒有可能為空，如果這個值在某個情況下不應該是空，那么我們就可以斷言，因為不可能為空的，一定有數值的傳進來，結果你斷言后報錯了，說明傳進來的有問題啊。如果這個函數允許有空的存在，那么不需要斷言，因為斷言了不就傳不進來，就與初衷有悖。

????????舉個例子，插入的時候，*pphead有沒有可能為空，空鏈表能插入，說明可以為空，為空你加assert(*pphead)，那不是鐵鐵報錯嗎。空鏈表能打印，能插入，不用斷言。空鏈表不能尾刪，不能頭刪，要斷言，為空還刪什么。但是pphead要斷言，它是鏈表的地址，它一定鐵定不為空。所以一定要*pphead斷言。

????????結論是：??所以有個思維就是如果這個值絕對不為空，那么我們就可以斷言。而且斷言會直接報錯，告訴你錯在哪里，根據場景去靈活變通，發現基本錯誤，調試的成本，花費的時間要遠比斷言來的高。在這里pphead一定不為空，*pphead看場景。具體情況具體分析。

5.三個文件的代碼?

? ? ? ? 這里展示頭文件，具體函數和測試用例的全部代碼。

5.1 頭文件

#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
typedef int Sltdatatype;
typedef struct SListnode
{Sltdatatype data;struct SListnode* next;
}SLTnode;
void SLTprint(SLTnode *phead);
SLTnode* insertSLTnode(Sltdatatype x);
void SLTpushback(SLTnode** pphead, Sltdatatype x);
void SLTpopback(SLTnode** pphead);
void SLTpushfront(SLTnode** pphead, Sltdatatype x);
void SLTpopfront(SLTnode** pphead);
SLTnode* SLTfind(SLTnode* pphead, Sltdatatype x);
//pos之前插入
void SLTinsert(SLTnode **pphead,SLTnode*pos,Sltdatatype x);
//pos位置刪除
void SLTErase(SLTnode** pphead, SLTnode* pos);
//pos后面插入
void SLTinsert_afterpos(SLTnode**phead,SLTnode* pos,Sltdatatype x);
//pos后面刪除
void SLTerase_afterpos(SLTnode** pphead, SLTnode* pos);
//鏈表銷毀
void SLTdestory(plist);

5.2 具體函數實現

#define _CRT_SECURE_NO_WARNINGS 1
#include"Slist.h"
SLTnode* insertSLTnode(Sltdatatype x)
{//申請一塊空間給新的節點SLTnode* newnode = (SLTnode*)malloc(sizeof(SLTnode));if (newnode == NULL){perror("fail malloc");return 0;}newnode->data = x;newnode->next = NULL;return newnode;
}
//尾插
void SLTpushback(SLTnode **pphead,Sltdatatype x)
{assert(pphead);SLTnode* newnode = insertSLTnode(x);if (*pphead==NULL){*pphead = newnode;}//找尾else{//定義尾變量SLTnode* tail = *pphead;while (tail->next!=NULL){tail = tail->next;}//tail->next這個指針指向新節點tail->next= newnode;}
}//尾刪
void SLTpopback(SLTnode** pphead)
{//檢查assert(pphead);assert(*pphead);//一個節點if ((*pphead)->next==NULL){free(*pphead);*pphead = NULL;}//多個節點else{// 找尾SLTnode* former = NULL;SLTnode* tail = *pphead;while (tail->next != NULL){former = tail;tail = tail->next;}free(tail);tail = NULL;former->next = NULL;}
}
void SLTprint(SLTnode* phead)
{SLTnode* cur = phead;while (cur){printf("%d ",cur->data);cur=cur->next;}printf("NULL\n");
}//頭插
void SLTpushfront(SLTnode** pphead, Sltdatatype x)
{assert(pphead);SLTnode* newnode = insertSLTnode(x);//把newnode的下一個給pilstnewnode->next = *pphead;//鏈表指針指向新節點，變成新的頭部*pphead =newnode;
}
//頭刪
void SLTpopfront(SLTnode** pphead)
{assert(pphead);assert(*pphead);if ((*pphead)->next == NULL){free(*pphead);*pphead = NULL;}//第一個節點的地址，給到first這個指針SLTnode* first = *pphead;//plist指向first的下一個地址，就是第二個節點*pphead = first->next;free(first);//刪除第一個first = NULL;
}
SLTnode* SLTfind(SLTnode* pphead, Sltdatatype x)
{//遍歷SLTnode* cur = pphead;while (cur){if (cur->data==x){return cur;}cur = cur->next;}return NULL;
}
void SLTinsert(SLTnode** pphead,SLTnode*pos, Sltdatatype x)
{assert(pos);assert(pphead);//如果pos是第一個，就等于頭插if (pos == *pphead){//復用頭插函數SLTpushfront(pphead,x);}else{SLTnode* former = *pphead;if (former->next!=pos){former = former->next;}SLTnode* newnode = insertSLTnode(x);former->next = newnode;newnode->next = pos;}
}
void SLTErase(SLTnode** pphead, SLTnode* pos)
{assert(pphead);assert(*pphead);if (pos == *pphead){SLTpopfront(pphead);}else{SLTnode* former = *pphead;while (former->next != pos){former = former->next;}former->next = pos->next;free(pos);}}
void SLTinsert_afterpos(SLTnode** pphead,SLTnode *pos, Sltdatatype x)
{assert(pphead);assert(pos);SLTnode* newnode = insertSLTnode(x);newnode->next = pos->next;pos->next = newnode;
}void SLTerase_afterpos(SLTnode** pphead, SLTnode* pos)
{assert(pos->next);SLTnode* erase = pos->next;
pos->next = pos->next->next;free(erase);erase = NULL;}void SLTdestory(SLTnode * phead)
{SLTnode* cur = phead;while (cur){SLTnode* next = cur->next;free(cur);cur=next;}
}

5.3 測試用例


void test7()
{SLTnode* plist = NULL;SLTpushback(&plist, 1);SLTpushback(&plist, 2);SLTpushback(&plist, 3);SLTpushback(&plist, 4);SLTpushback(&plist, 5);SLTprint(plist);SLTnode* ret = SLTfind(plist, 3);SLTinsert_afterpos(&plist,ret,7);SLTprint(plist);SLTerase_afterpos(&plist, ret);SLTprint(plist);SLTdestory(plist);plist = NULL;
}
int main()
{test7();return 0;
}

? ? ? ? 單鏈表的復習和講解就到這里了?，單鏈表一開始學習還是比較晦澀難懂的，但是寫多了，錯誤多了，坑踩多了，就會熟悉里面的內容了。還是要多理解，多做題，后面也會講解一些單鏈表的O經典J題來加強印象。多做題也是熟悉鏈表的一個很好的方式！