前面學習了順序表，在順序表中，雖然可以用動態內存開辟的方法來靈活改變空間大小，但順序表本身仍然存在著一些局限性：

• 頭插/尾插中，每插入一次數據，其它數據要提前挪動以空出空間。
• 開辟空間是以現有空間的倍數進行的，一般為2~3倍。

而隨之帶來空間和時間兩個方向上的問題：

• 數據頻繁地挪動需要占用時間和性能。
• 空間開辟后還是會不可避免的浪費。

---

鏈表

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

---

節點

節點組成部分：

1. 數據（實際往往是運用 / 保存指針）
2. 指向下一個節點的指針

定義鏈接的節點結構：

struct SlistNode     //single list node  單鏈表
{int data;struct SlistNode* next;
};

---

設計鏈表項目

文件有

• 源文件：Slist.c、test.c
• 頭文件：Slist.h

---

鏈表中的傳址調用

鏈表中，經常會出現函數傳值調用的錯誤。

如圖，想要改變鏈表plist，就要傳址操作。而其本身就是地址，因此函數的參數類型應該是二級指針。

鏈表的創建是下面這兩行代碼，創建數據和指向下一個節點的指針。數據要開辟空間，所以內容使用指針接收。

SN* Node1 = (SN*)malloc(sizeof(SN));
Node1->Data = 21;

---

檢查申請空間

在對鏈表進行操作（尤其是增刪）的時候，要先對空間進行檢查，防止內存溢出或者越界訪問。
此函數，申請成功返回新節點，失敗報錯。

SN* Creat_newlistNode(DataType i)
{SN* newNode = (SN*)malloc(sizeof(SN));if (newNode == NULL){perror("malloc");exit(1);}newNode->Data = i;newNode->next = NULL;return newNode;
}

此函數真正使用如下：

SN* newNold = Creat_newlistNode(i);//創建一個保存數據i的鏈表。

---

鏈表尾插

先考慮非空鏈表
鏈表尾插，遍歷鏈表找尾，將要插入的節點放到最后。
接著，要考慮無法遍歷的情況——空鏈表。
以上思路完成后，考慮將代碼更為嚴謹、完善。如指針的合法等。
最后進行最終的測試。（每完成一個功能，也就應該測試一次。）

void SNPushBack(SN** pphead, DataType i)
{assert(pphead);SN* new = Creat_newlistNode(i);assert(new);//空鏈表和非空鏈表if (*pphead==NULL){*pphead = new;}else{SN* ptail = *pphead;while (ptail->next){ptail = ptail->next;}ptail->next = new;}
}

---

鏈表頭插

現申請一個新的節點newnold。
將新節點和原有鏈表連接起來，并且新節點將作為頭結點使用。

void SNPushFront(SN** pphead, DataType i)
{assert(pphead);SN* newNold = Creat_newlistNode(i);newNold->next= *pphead;*pphead = newNold;//空鏈表、非空鏈表都需要考慮（此代碼兩者都已通過）
}

---

鏈表尾部刪除

鏈表的尾刪，分為兩個方向考慮：存在一個節點、存在多個節點。
判斷一個節點時，直接刪除
多個節點時，循環找到最后一個（并且保留前一個），然后刪除并將保留的那個指針指向置為空。

void SNPopBack(SN** pphead)
{assert(pphead && *pphead);//分為只有一個節點、多個節點if ((*pphead)->next == NULL)//  -> 優先級高于 *{free(*pphead);*pphead = NULL;}else{SN* ptail = *pphead;SN* prev = *pphead;while (ptail->next){prev = ptail;ptail = ptail->next;}free(ptail);ptail = NULL;prev->next = NULL;}}

---

鏈表頭部刪除

頭刪只需要將鏈表指向改為下一個（在更改指向前創建臨時變量保存），
后使用臨時變量釋放掉第一個節點的空間。
最后一步是測試，多個節點、一個節點是否有問題。

void SNPopFront(SN** pphead)
{assert(pphead&& *pphead);SN* tmp = (*pphead)->next;free(*pphead);*pphead = tmp;
}

---

鏈表的查找

鏈表的修改，只需遍歷尋找即可。
由于查找不涉及鏈表修改，因此函數參數的形參為一級指針。
往后遍歷直到找到即可：

SN* FindSN(SN* phead, DataType i)
{assert(phead);SN* tmp = phead;while (tmp){if (tmp->Data == i){return tmp;}tmp = tmp->next;}return NULL;
}

在此函數的使用時，不要給參數帶上 & 符號！！！（鏈表節名本身就是地址類型不可再亂加&）

void test3()
{SN* one = NULL;SNPushBack(&one, 99);SNPushBack(&one, 88);SNPushBack(&one, 77);SNPushBack(&one, 66);SNPushBack(&one, 55);SNPushBack(&one, 44);SNPrint(one);SN* find=FindSN(one, 66);//注意此時不涉及改變不需要使用 & 符號if (find==NULL){printf("找不到");}else{printf("可以找到%d", find->Data);}
}

---

指定位置：使用上面用于查找鏈表的函數，返回值即是這個位置

---

指定位置之前插入

首先考慮正常情況的多個節點。
鏈表中，只能由前找后，不能從后找到前。
因此確立分清三個節點：插入節點之前的節點，插入的節點，指點位置的節點。
創建插入的節點后，建立三個結點之間的聯系。
再考慮特殊情況（只有一個節點的時候）
此時插入原理就是頭插。
不需考慮無節點情況。

void SNInsert(SN** pphead, SN* pos, DataType i)//指定位置之前插入數據
{assert(*pphead);assert(pphead);SN* NewNold = Creat_newlistNode(i);//分為一個節點、多個節點if (*pphead == pos){SNPushFront(pphead,i);}else{SN* prev = *pphead;while (prev->next != pos){prev = prev->next;}prev->next = NewNold;NewNold->next = pos;}
}

---

指定位置之后插入數據

參數只需要指定的位置和數據即可。

void SNInsertAfter(SN* pos, DataType i)
{assert(pos);SN* NewNold = Creat_newlistNode(i);NewNold->next = pos->next;pos->next = NewNold;
}

需要特別提出來說明的是，這兩句代碼的順序問題。

NewNold->next = pos->next;  //1
pos->next = NewNold;        //2

如果順序顛倒，先進行

pos->next = NewNold;   //2

再進行

NewNold->next = pos->next;  //1

造成的結果等價于NewNold->next = NewNold，這個代碼將會自己指向自己。

---

刪除指定位置（節點）數據

指定位置刪除數據，先考慮正常多節點情況
依舊需要弄清楚：刪除位置之前的節點、刪除位置的節點、刪除位置之后的節點。
使用循環找到刪除位置之前的節點，然后與后面的節點建立連接。
此時鏈表之中已不存在要刪除的節點，但是空間沒有釋放一定要釋放空間。

我們會發現，如果是一個節點，我們要指定位置刪除。
代碼并不適用。
所以要分情況來執行代碼，使用 if 語句將兩種情況分開討論。
一個節點，指定位置刪除的操作其實就是頭刪。拷貝或調用函數都可以。

void SNErase(SN** pphead, SN* pos)//指定位置刪除數據
{assert(pphead && *pphead);assert(pos);if (pphead == pos){(*pphead)->next = NULL;      //或者頭刪函數也行//SNPopFront(pphead);}else{SN* prev = *pphead;while (prev->next != pos){prev = prev->next;}prev->next = pos->next;free(pos);pos = NULL;}
}

---

刪除指定位置（節點）之后的數據

刪除指定位置之后的數據，思路如下：

1. 保存這個數據（指定位置之后的數據的位置）
2. 鏈表重新建立連接（這一步完成后，鏈表中將不存在指定位置之后的>數據）
3. 根據預先保存的數據找到被刪除的數據，將其從內存中刪除。

void SNEraseAfter(SN* pos)
{assert(pos && pos->next);   //  -> 優先級大于 &&SN* del = pos->next;pos->next = del->next;free(del);del = NULL;
}

在測試時，出現了錯誤，記錄下來：

在測試指定位置刪除時，使用findSN函數找到位置find，然后刪除了這個位置的節點。后面又想測試指定位置之后刪除，可是find這個位置的節點已經被刪除，所以無法找到find，更無法找到find后面的節點了。

---

鏈表的銷毀

鏈表是一個一個創建的，銷毀也是一個一個的銷毀。
思路是：創建兩個指針，一個指針銷毀節點使用，一個指針保存下一個節點。循環直到鏈表結束。

void DestorySN(SN** pphead)
{assert(pphead && *pphead);SN* pcur = *pphead;while (pcur){SN* next = pcur->next;free(pcur);pcur = next;}*pphead = NULL;
}

以上就是我對于單鏈表的學習記錄了，單鏈表的理論到此結束。