單鏈表復習 (C語言版)

一.順序表與鏈表的區別

二.鏈表概念

三.單鏈表

1.單鏈表的開始與初始化

2.單鏈表的打印

3.單鏈表的尾插

重難點：單鏈表實現時的指針詳解

4.單鏈表的頭插

5.單鏈表的尾刪

6.單鏈表的頭刪

小結：

7.單鏈表的查找

8.在指定位置前插入數據

9.在指定位置后插入數據

10.刪除pos結點

11.刪除pos結點之后的結點

12.刪除鏈表

13.可能存在的疑惑解答

?14.全部用于測試的代碼

四.文章鏈接

一.順序表與鏈表的區別

順序表的問題及思考：

中間/頭部插入刪除，涉及到移動數據，時間復雜度為o(n)
增容需要申請新空間，拷貝數據，釋放舊空間，會有損耗。（realloc）
增容一般呈2倍的增長，當前容量為100，增加到200，只存放5字節，浪費了95字節
順序表中間頭部插入效率低下，增容造成運行效率降低
鏈表解決了上述問題

順序表相關文章鏈接：順序表復習(C語言版)

?上圖就形象地表示了線性表與鏈表的區別，鏈表存儲位置不連續，是用指針相連；線性表（SeqList）在內存中是連續存放的

二.鏈表概念

線性表是一類相同元素的集合，例如蘋果和香蕉（都是水果）

邏輯結構：一定線性

物理結構：不一定線性（因為在內存中的存放位置是不連續的）

int a =10；float f =0.1 變量a和f的物理空間不一定連續，即存放位置不一定連續

鏈表和火車很相似

通過一個鉤子連在一起，地址空間是鏈接在一起的，車頭也是車廂，因為它也可以裝人

旺季：增加車廂

淡季：減少車廂

鏈表是由一個一個節點組成，結點可以看成車廂

?plist位置稱之為頭結點，頭結點指向的結點叫做首元結點，最后一個指針域指向NULL的結點叫做尾元結點

結點和節點：同一個東西，隨便用哪個

結點由什么組成的呢？

有兩個組成部分

1.數據域? --->在該域內存儲了數據

2.指針域? --->存儲了指向下一個結點的指針

三.單鏈表

1.單鏈表的開始與初始化

鏈表就是在定義鏈表的結點結構

struct?SListNode single list node{int?data; ?????????????????????????//int a =10；//int* pa =&astruct?SListNode* next; ???????????//指向下一個節點的指針}SLTNode;typedef?int?SLTTDataType;

上述代碼就是在對鏈表進行初始化，定義了一個結構體，并在里面定義了一個data還有一個指針next（next指向下一個結點）

void?SListTest01(){//創建節點SLTNode* node1 = (SLTNode*)malloc(sizeof(SLTNode));node1->data = 1;SLTNode* node2 = (SLTNode*)malloc(sizeof(SLTNode));node2->data = 2;SLTNode* node3 = (SLTNode*)malloc(sizeof(SLTNode));node3->data = 3;SLTNode* node4 = (SLTNode*)malloc(sizeof(SLTNode));node4->data = 4;//將四個節點連接起來node1->next = node2;node2->next = node3;node3->next = node4;node4->next = NULL;//調用鏈表的打印SLTNode* plist = node1;void?SLTPrint(plist); //為了讓代碼邏輯更加清晰}

上述代碼依舊是對鏈表的初始化，將四個結點進行創建，然后相連接；在初始化代碼寫完以后，直接跟了一個鏈表打印函數

2.單鏈表的打印

緊接上文代碼，上文中 SLTNode* plist = node1就是在說明，plist是個指針，且與node1一樣都是一級指針；因此它指向node1所在的這塊空間，這就可以看成讓node1和plist兩個指針指向同一塊空間，且這塊空間在早些時候已經通過node1指針初始化完畢了；因此如果創建一個pcur，讓他等于plist，那么pcur依舊指向node1所指向的空間，這就可以看出三個指針指向同一塊空間

先是打印pcur所指向空間的data，然后讓pcur里指向下一個結點的指針覆蓋pcur這個結點，pcur就自然而然向后移動了

重復上述操作，先打印所指向空間的data值，然后再讓其指向的下一個結點地址將現在這個結點地址覆蓋

由上圖可知，當pcur指向的空間為NULL時，打印操作完成；由上四圖，不難得出下述代碼：

void?SLTPrint(SLTNode* phead) //傳的是首元結點{SLTNode* pcur = phead;while?(pcur) ?//pcur != NULL{printf("%d->", pcur->data);pcur = pcur->next;}printf("NULL\n");}

3.單鏈表的尾插

因為在此以后我們需要多次進行單鏈表的增刪查改操作，因此我們可以專門寫一個函數，這個函數是專門用來創建新結點的，在順序表那篇文章中已經講解過，故在此省略

	SLTNode* SLTBuyNode(SLTDataType x){SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode*));if (newnode == NULL){perror("malloc fail!");exit(-1);}newnode->data = x;newnode->next = NULL; //此處指向空指針是為了方便后續操作}

接下來就要開始進行尾插操作

	void SLTPushBack(SLTNode** pphead, SLTDataType x){SLTNode* newnode = SLTBuyNode(x);//空鏈表的情況if (*pphead == NULL){*pphead = newnode; //newnode的data有了，next指向空指針，將pphead地址覆蓋，指向新的newnode空間，完成尾插}//非空鏈表的情況else{//找尾SLTNode* ptail = *pphead; //不想讓*pphead變動位置（變動了就需要使用二級指針了），因此又定義了一個變量ptail指針while (ptail->next){ptail = ptail->next;}//退出循環就說明已經找到尾了，此時ptail指向空指針ptail->next = newnode; //讓ptail指向新結點}
}

上述代碼指針部分較難理解，因此筆者將在下文進行詳細解釋

重難點：單鏈表實現時的指針詳解

上述代碼中，為什么使用二級指針？
在函數中，想要通過形參改變實參的值（即對其進行某些操作，且這些操作是針對該參數而言的，而不是該參數針對別的變量而言的），就必須在傳參時傳地址。

即使實際參數是一個指針，我們也需要通過指針的地址來改變該指針本身。（如下圖所示）

所以，我們在函數傳參時，傳的是指針的地址，因此需要函數用二級指針來接收。

但請注意，只有二級指針類型的形式參數，在進行了一次解引用操作狀態下的改變，才需要用到二級指針類型的形式參數。

此處我們可以類比一級指針和整型變量。要通過形式參數改變實際參數，那么需要形式參數是一個指向需改變變量的指針，然后才可以通過形式參數改變該變量；而想要改變一級指針變量，那么就需要通過二級變量來改變。（前者是結點里的指針域、數據域的內容的改變，后者是結點本身的改變）

所以，如果需要改變結點，就用二級指針；如果只需要改變某個結點指針域、數據域內容，那就傳一級指針，此時就沒有必要傳二級指針了。

上述代碼中，為什么有些地方需要解引用，而有些地方不需要呢？

解引用（即*操作符）可以看作是把指針降級（文章鏈接部分有指針其他內容復習），把二級指針變成一級指針，把一級指針變成指針指向的內容；所以上述代碼中，部分地方使用了一次解引用操作，即從指向結點的指針地址變為了指向結點的指針（也可以看成是結點本身）。

為什么單鏈表的打印不需要二級指針，而單鏈表的尾插就需要呢？

因為單鏈表的打印并沒有改變鏈表的首元結點本身，只是完成了打印操作，所以不需要通過形式參數來改變實際參數；而尾插操作需要改變鏈表的首元結點本身（從NULL變成了newnode），因此需要通過形參來改變實參。

SLTNode* 和 * 的區別是？

SLTNode* 是在告訴編譯器，這個變量是個指針，指向了SLTNode這個類型的數據，而并不是在對變量進行解引用操作；*是解引用操作符，在上文已經講解完畢；而在函數當中，對二級指針進行解引用，其本質上還是個二級指針，因為形式參數依然還是二級指針。

?	實參	形參(前面的*是指函數中使用的解引用操作符個數）
第一個結點的內容	*plist（即xxx）	ptail?-> xxx (即一般情況下的**pphead，此處只是因為是結構體指針，所以需要用結構體指針的解引用方式）
指向第一個結點的指針	plist	*pphead
指向第一個結點的指針的地址	&plist	pphead

	SLTNode* plist = NULL; //代碼1SLTNode* plist1 = node1; //代碼2SLTPushBack(&plist1, 1); //代碼3SLTPrint(plist1); //代碼4plist1->next = NULL; //代碼5

代碼1：結點為空

代碼2：一個有效結點

代碼3：傳輸有效結點的地址

代碼4：傳輸有效結點

代碼5：對有效結點解引用，結構體里套了一個指向結構體類型（即為其本身）的指針變量，讓該變量指向空，這一操作即是讓該結點的下一個結點為空

4.單鏈表的頭插

	void SLTPushFront(SLTNode** pphead, SLTDataType x){assert(pphead);SLTNode* newnode = SLTBuyNode(x); newnode->next = *pphead; //newnode指向首元結點*pphead = newnode; //將頭指針指向新創建的結點}

5.單鏈表的尾刪

	void SLTPopBack(SLTNode** pphead) {assert(pphead && *pphead) //指向鏈表結點的指針不能為空，鏈表也不能為空SLTNode* prev = *pphead; //為防止野指針，要讓尾元結點的next指針指向空，因此需要再創建一個指針，來完成這一操作SLTNode* ptail = *pphead;while (ptail->next){prev = ptail; //prev需要指向尾元結點的前一個結點，因此需要跟著ptail變動ptail = ptail->next; //ptail指向尾元結點}free(ptail); //釋放ptail所指向的空間，就能達到尾刪的目的ptail = NULL; //動態內存開辟內容，下文有鏈接prev->next = NULL; //要讓prev里的next指針從指向野指針到指向空指針}

當只有一個結點的時候，循環直接跳過，ptail和prev指向同一個結點，在將ptail空間釋放并變成空指針以后，又一次對prev（即ptail的同一結點）進行了解引用操作，這樣代碼會報錯（對空指針解引用）

因此當鏈表只有一個節點時，代碼如下所示：

	//鏈表只有一個結點if ((*pphead)->next = NULL) //加括號是因為 -> 優先級高于 *{free(*pphead);*pphead = NULL;}

尾刪的全部代碼：

	void SLTPopBack(SLTNode** pphead) {assert(pphead && *pphead) //鏈表不能為空，指向鏈表結點的指針也不能為空//鏈表只有一個結點if ((*pphead)->next = NULL) //加括號是因為 -> 優先級高于 *{free(*pphead);*pphead = NULL;}else{SLTNode* prev = *pphead; //為防止野指針，要讓尾元結點的next指針指向空，因此需要再創建一個指針，來完成這一操作SLTNode* ptail = *pphead;while (ptail->next){prev = ptail; //prev需要指向尾元結點的前一個結點，因此需要跟著ptail變動ptail = ptail->next; //ptail指向尾元結點}free(ptail); //釋放ptail所指向的空間，就能達到尾刪的目的ptail = NULL; //動態內存開辟內容，下文有鏈接prev->next = NULL; //要讓prev里的next指針從指向野指針到指向空指針}}

6.單鏈表的頭刪

先要保存好頭刪前的鏈表第二個節點，頭刪以后把*pphead指針指向新的節點

void SLTPopFront(SLTNode** pphead)
{assert(pphead && *pphead);SLTNode* next = (*pphead)->next;free(*pphead);*pphead = next;
}
//只有一個結點的情況上述代碼也能夠解決

小結：

上述的插入、刪除代碼中，因為四種代碼所以必須使用二級指針：
1.free(*pphead);

2.*pphead = NULL;

3.*pphead = newnode;

4.*pphead = next;

即對一級指針類型的參數本身進行了某些操作

7.單鏈表的查找

在使用查找函數以后，要分為找到了和沒找到兩種情況，那么我們可以通過如下代碼來區分(此處的3是指數據域為3的結點）：

SLTNode* find = SLTFind(plist, 3);
if (find == NULL)
{printf("沒有找到")；
}
else
{printf("找到了");
}

上述代碼中，plist即為首元結點的指針

不需要傳輸首元結點指針的地址，這是因為并不需要通過查找函數來改變鏈表的首元結點。?

SLTNode* SLTFind(SLTNode* phead, SLTDataType x)
{SLTNode* pcur = phead; //不想形式參數是個二級指針，因此可以在函數中定義一個指針變量while (pcur){if (pcur->data == x){return pcur;}pcur = pcur->next;}return NULL;
}

8.在指定位置前插入數據

該函數必須要有三個參數，分別是鏈表的首元結點（SLTNode** pphead)、在鏈表的哪個結點前插入（SLTNode* pos)、所需要插入的數據（x)。如下所示：

void SLTInsert(SLTNode** pphead,SLTNode* pos,SLTDataType x)

一個參數使用二級指針，一個參數使用一級指針的原因：

前一個二級指針類型是鏈表的首元結點地址，是需要通過形式參數來改變首元結點的；下一個一級指針類型是鏈表指定位置的結點，可以直接通過解引用，對結點的指針域、數據域進行操作。

如果要在第3個結點前插入數據，就需要先創建一個結點，然后把這個結點和第3個結點相連接，然后斷開第2個結點和第3個結點的連接，讓第2個結點和第3個結點相連。而第2個結點就需要通過遍歷獲得，循環語句的退出條件是：prev->next != pos (prev為函數中定義的指針變量，遍歷以前，prev == *pphead）

如果是在鏈表的首元結點之前插入數據，那么prev的next就不可能會等于pos，因此我們在代碼實現里要考慮到一般情況和在首元結點之前插入數據兩張情況。并且在首元結點前插入數據可以通過頭插的函數來實現（這種情況也是函數需要使用二級指針的原因，因為函數需要傳一個二級指針)。

void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x)
{assert(*pphead && pphead); //鏈表不能為空，因為為空了，就無法確定“某一位置”了assert(pos);SLTNode* newnode = SLTBuyNode(x);if (pos == *pphead) //在首元結點之前插入{SLTPushFront(pphead, x);}else //一般情況{//找到pos結點的前一個結點SLTNode* prev = *pphead;while (prev->next != pos){prev = prev->next; //沒有找到就找下一個}newnode->next = pos; //完成上文的操作prev->next = newnode;}
}//pos指針即為上文查找部分出現的find

9.在指定位置后插入數據

在指定位置后插入數據，不需要再創建一個指針，直接通過"指定位置"結點的next以及該結點next的next來插入即可

第一種：先紅色，再綠色

第二種：先綠色，再紅色

以上兩種方式是否相同？

//第一種方式的代碼
newnode->next = pos->next;
pos->next = newnode;

//第二種方式的代碼
pos->next = newnode;
newnode->next = pos->next;

第一種方式可以完成我們需要的操作，即先讓新節點指向鏈表的指定節點的下一個結點（next），然后再讓指定節點指向新結點

第二種方式讓指定節點指向新節點，此時指定結點的下一個結點即為新節點，因此讓新節點指向指定的下一個結點時，即為新節點本身，無法完成需要的操作（如上圖所示）

void SLTInsertAfter(SLTNode* pos, SLTDataType x)
{assert(pos);SLTNode* newnode = SLTBuyNode(x);newnode->next = pos->next;pos->next = newnode;
}//pos指針即為上文查找部分出現的find

10.刪除pos結點

刪除pos結點需要我們將pos結點的前一個結點和pos的后一個結點相接，因此還需要有個prev指針去保存pos結點的前一個結點，如下圖所示?

首元結點、尾元結點的刪除請讀者自行判斷

void SLTErase(SLTNode** pphead, SLTNode* pos)
{assert(pphead && *pphead);assert(pos);//pos是首元結點if (pos == *pphead){//頭刪SLTPopFront(pphead);}else{SLTNode* prev = *pphead;while (prev->next != pos){prev = prev->next;}prev->next = pos->next;}
}//pos指針即為上文查找部分出現的find
//在使用完find指針以后，需要在函數外進行free、置空操作

11.刪除pos結點之后的結點

刪除pos->next，讓pos結點和pos->next->next相連即能完成操作，如下圖所示：?

void SLTEraseAfter(SLTNode* pos)
{assert(pos && pos->next);SLTNode* del = pos->next; //保存pos的下一個結點pos->next = del->next;  //讓pos的下一個結點（即del）和pos的下一個結點（即del）的下一個節點相鏈接free(del);del = NULL;
}

12.刪除鏈表

傳入首元結點，然后保存好首元結點的下一個結點（next指針），然后free掉pcur以后，讓next指針和pcur指針都往后走一個結點，循環退出條件為pcur為空指針。（如上圖所示）

void SListDesTroy(SLTNode** pphead)
{assert(pphead && *pphead);SLTNode* pcur = *pphead;while (pcur){SLTNode* next = pcur->next; free(pcur);pcur = next;}*pphead = NULL; //已經釋放完所有的內容了，將pphead置為空
}

13.可能存在的疑惑解答

**pphead作為形參出現那么多次，那么他到底對應哪個結點呢？

他既可以對應空指針（鏈表完全沒有結點，對應了插入等的情況），同時也可以對應首元結點（頭刪和尾刪等的情況）

為什么在部分函數里有時候free不需要二級指針？

例如free(ptail），在尾刪板塊出現。這是因為ptail是在函數里創建、使用的，無需通過函數來改變任何一個實參（它也沒有對應的實參、因為它并不是一個形式參數）。在出了函數以后，ptail指針就沒有作用了，如果在函數內沒有進行free、置空操作，就會變成一個野指針。?

單鏈表的開始和初始化必須要像1那樣寫嗎？
并不是，其實完全可以通過尾插、頭插等等方式進行鏈表的初始化的。

所有函數都必須要傳二級指針嗎？

有些一定需要傳，例如*pphead=newnode（在頭插板塊），因為這條代碼如果不寫在函數里，就完成不了頭插操作；在某些情況下不一定需要傳，例如free(*pphead)，放到函數實現外的部分，可以通過free(plist)完成操作，不寫在函數里也不會影響函數的功能實現。

如果打印函數里使用形參進行打印，不創建變量了，是否可以？
其實是可以的，因為形參是一級指針，不會影響實參。

在函數中，定義一個變量pcur = *pphead了以后，為什么影響了pcur就能影響整個鏈表了？

在函數當中，實際上pcur能直接看成pphead解引用了一次，即可以把所有的pcur看成是（*pphead），這就像是定義宏一樣；這就像是傳入了一個一級指針? int *a，然后在函數了假設變量int b = *a ，然后通過b的改變來改變傳入進來的*a一樣。而我們會在函數里使用到pcur = *pphead有兩個原因，其一就是為了代碼的可讀性，其二就是為了讓pphead指針一直指向首元結點。

?14.全部用于測試的代碼

請注意，以下代碼有些是不兼容的，就比如plist指針一會是NULL，一會是首元結點；同時有些功能，例如單鏈表的查找，不能鏈表是空的，需要有前提條件。因此請讀者對函數進行一一嘗試，需嘗試的功能直接取消注釋即可。

int main()
{//SListTest01(); //對于開始和初始化//SLTNode* plist = NULL; //從沒有鏈表開始對于尾插//SLTPushBack(&plist, 1);//SLTPrintf(plist); //此處plist又變成了首元結點,在使用完該操作以后，plist由于//SLTPushBack(&plist, 2);//SLTPrintf(plist);//SLTPushBack(&plist, 3);//SLTPrintf(plist);//SLTPushBack(&plist, 4);//SLTPrintf(plist);對于頭插（尾插、頭插寫一塊了）//SLTPushFront(&plist, 6);//SLTPrintf(plist);//SLTPushFront(&plist, 2);//SLTPrintf(plist);//SLTPushFront(&plist, 3);//SLTPrintf(plist);//SLTPushFront(&plist, 4);//SLTPrintf(plist);尾刪、頭刪（先決條件:不為空）//SLTPopBack(&plist);//SLTPrint(plist);//SLTFrontBack(&plist);//SLTPrint(plist);查找（先決條件：不為空）//SLTNode* find = SLTFind(plist, 3);//if (find == NULL)//{//	printf("沒有找到")；//}//else//{//	printf("找到了");//}指定位置的插入刪除（先決條件：不為空+有具體指定位置）//SLTNode* find = SLTFind(plist, 3); //find即為具體指定位置//SLTInsert(&plist, find, 10);//SLTPrint(plist);//SLTInsertAfter(find, 10);//SLTPrint(plist);//SLTErase(&plist, find);//SLTPrintf(plist);//SLTEraseAfter(find);//SLTPrintf(plist);//銷毀//SListDesTroy(&plist);//SLTPrintf(plist);
}
//以上代碼是在vscode2022中進行的

四.文章鏈接

指針講解：指針復習

動態內存開辟講解：動態內存開辟復習