?作者簡介：大家好，我是橘橙黃又青，一個想要與大家共同進步的男人😉😉
🍎個人主頁：橘橙黃又青-CSDN博客
前面我們學習了順序表，今天我們來學習與順序表類似的單鏈表
1.🍎什么是鏈表
概念：鏈表是?種物理存儲結構上?連續、?順序的存儲結構，數據元素的邏輯順序是通過鏈表
中的指針鏈接次序實現的 。
鏈表的結構跟???廂相似，淡季時?次的?廂會相應減少，旺季時?次的?廂會額外增加?節。只需要將???的某節?廂去掉/加上，不會影響其他?廂，每節?廂都是獨?存在的。
?廂是獨?存在的，且每節?廂都有??。想象?下這樣的場景，假設每節?廂的??都是鎖上的狀 態，需要不同的鑰匙才能解鎖，每次只能攜帶?把鑰匙的情況下如何從?頭?到?尾？
最簡單的做法：每節?廂?都放?把下?節?廂的鑰匙。
那在在鏈表?，每節“?廂”是什么樣的呢？
與順序表不同的是，鏈表?的每節"?廂"都是獨?申請下來的空間，我們稱之為“結點/節點”
節點的組成主要有兩個部分： 當前節點要保存的數據和保存下?個節點的地址（指針變量）。
圖中指針變量 plist保存的是第?個節點的地址，我們稱plist此時“指向”第?個節點，如果我們希
望plist“指向”第?個節點時，只需要修改plist保存的內容為0x0012FFA0。
?
結合前?學到的結構體知識，我們可以給出每個節點對應的結構體代碼：
假設當前保存的節點為整形：
代碼：
struct SListNode
{int data; //節點數據struct SListNode* next; //指針變量?保存下?個節點的地址
}; 當我們想要保存?個整型數據時，實際是向操作系統申請了?塊內存，這個內存不僅要保存整型數
據，也需要保存下?個節點的地址（當下?個節點為空時保存的地址為空）。
當我們想要從第?個節點?到最后?個節點時，只需要在前?個節點拿上下?個節點的地址（下?個 節點的鑰匙）就可以了。
?2. 🍎鏈表的打印
那給定的鏈表結構中，如何實現節點從頭到尾的打印？
看圖：
代碼：
//打印
void SLTPrint(SLTNode* phead) {SLTNode* pcur = phead;while (pcur){printf("%d->", pcur->data);pcur = pcur->next;}printf("NULL\n");
}
//開辟空間
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、鏈式機構在邏輯上是連續的，在物理結構上不?定連續2、節點?般是從堆上申請的3、從堆上申請來的空間，是按照?定策略分配出來的，每次申請的空間可能連續，可能不連續
?前面簡單學習打印，接下來我們進入單鏈表的增，刪，查。
3，🍎單鏈表的基礎應用
?這里我們介紹一下我的單鏈表代碼：
typedef int SLTDataType;
//鏈表是由節點組成
typedef struct SListNode
{SLTDataType data;struct SListNode* next;
}SLTNode;
創建一個這樣的空間鏈表：?
3.1🍎鏈表的尾插
代碼展示：
void SLTPushBack(SLTNode** pphead, SLTDataType x) {assert(pphead);SLTNode* newnode = SLTBuyNode(x);//鏈表為空，新節點作為pheadif (*pphead == NULL) {*pphead = newnode;return;}//鏈表不為空，找尾節點//創建代跑變量SLTNode* ptail = *pphead;while (ptail->next){ptail = ptail->next;}//ptail就是尾節點ptail->next = newnode;
}?圖片展示：
值得注意的是開辟的空間next是指向nuLL的?
?
3.2🍎鏈表的頭插
代碼展示：
void SLTPushFront(SLTNode** pphead, SLTDataType x) {assert(pphead);SLTNode* newnode = SLTBuyNode(x);//newnode *ppheadnewnode->next = *pphead;*pphead = newnode;
}圖片展示：?
3.3🍎鏈表的頭刪
代碼：
void SLTPopFront(SLTNode** pphead) {assert(pphead);//鏈表不能為空assert(*pphead);//讓第二個節點成為新的頭//把舊的頭結點釋放掉SLTNode* next = (*pphead)->next;free(*pphead);*pphead = next;
}思路：
3.4🍎鏈表的尾刪
代碼：
void SLTPopBack(SLTNode** pphead) {assert(pphead);//鏈表不能為空assert(*pphead);//鏈表不為空//鏈表只有一個節點，有多個節點if ((*pphead)->next == NULL) {free(*pphead);*pphead = NULL;return;}SLTNode* ptail = *pphead;SLTNode* prev = NULL;while (ptail->next)//找尾節點{prev = ptail;ptail = ptail->next;}prev->next = NULL;//銷毀尾結點free(ptail);ptail = NULL;
}?把尾節點釋放掉，置為空
3.5🍎鏈表的查找
代碼:
//查找
SLTNode* SLTFind(SLTNode** pphead, SLTDataType x) {assert(pphead);//遍歷鏈表SLTNode* pcur = *pphead;while (pcur) //等價于pcur != NULL{if (pcur->data == x) {return pcur;}pcur = pcur->next;}//沒有找到return NULL;
}這個也是很簡單，遍歷鏈表，有就返回，無返回空。?
3.6🍎鏈表在指定位置之前插入數據
代碼：
//在指定位置之前插入數據
void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x) {assert(pphead);assert(pos);//要加上鏈表不能為空assert(*pphead);SLTNode* newnode = SLTBuyNode(x);//pos剛好是頭結點if (pos == *pphead) {//頭插SLTPushFront(pphead, x);return;}//pos不是頭結點的情況SLTNode* prev = *pphead;while (prev->next != pos){prev = prev->next;}//prev -> newnode -> posprev->next = newnode;newnode->next = pos;
}思路：
?
插入代碼就在上面啦。?
?
3.7🍎鏈表在指定位置之后插入數據
代碼：
//在指定位置之后插入數據
void SLTInsertAfter(SLTNode* pos, SLTDataType x) {assert(pos);SLTNode* newnode = SLTBuyNode(x);//pos newnode pos->nextnewnode->next = pos->next;pos->next = newnode;
}但是這里要注意了：
思路：
?
3.8🍎刪除pos節點
?代碼：
//刪除pos節點
void SLTErase(SLTNode** pphead, SLTNode* pos) {assert(pphead);assert(*pphead);assert(pos);//pos剛好是頭結點，沒有前驅節點，執行頭刪if (*pphead == pos) {//頭刪SLTPopFront(pphead);return;}SLTNode* prev = *pphead;while (prev->next != pos){prev = prev->next;}//prev pos pos->nextprev->next = pos->next;free(pos);pos = NULL;
}?思路：
3.9🍎刪除pos之后的節點
代碼：
//刪除pos之后的節點
void SLTEraseAfter(SLTNode* pos) {assert(pos);//pos->next不能為空assert(pos->next);//pos pos->next pos->next->nextSLTNode* del = pos->next;pos->next = pos->next->next;free(del);del = NULL;
}思路：
?
3.10🍎銷毀鏈表
堆銷毀很重要，創建鏈表也要學會銷毀鏈表
?代碼：
//銷毀鏈表
void SListDesTroy(SLTNode** pphead) {assert(pphead);assert(*pphead);SLTNode* pcur = *pphead;while (pcur){SLTNode* next = pcur->next;free(pcur);pcur = next;}*pphead = NULL;
}解釋：
創建帶跑指針，把下一個節點地址記錄下來，釋放原來第一個節點空間，再把下一個節點地址給帶跑指針。
好啦，我們今天就講到這里，喜歡就點一個贊吧，感謝觀看。
