在他一生中，從來沒有人能夠像你們這樣，以他的視角看待這個世界。
?????????????????????????????????????????????????????????????????????????????????????????????????????????????---------《尋找天堂》? ??
目錄
文章目錄
一、什么是鏈表？
二、為什么要使用鏈表？
三、 單鏈表介紹與使用
? ? ? ? 3.1 單鏈表
? ? ? ? ?3.1.1 創建單鏈表節點
????????3.1.2?單鏈表的頭插、尾插
? ? ? ? ?單鏈表的尾插
? ? ? ? ?單鏈表的頭插
3.1.3? 單鏈表的頭刪、尾刪
?????????單鏈表的尾刪?編輯
?????????單鏈表的頭刪
?3.1.4?鏈表節點的查找
3.1.5?在指定位置插入數據
????????在指定位置前插入數據
?????????在指定位置之后插入數據
?3.1.6?刪除pos之后的節點
3.1.7?銷毀鏈表
?四、完整代碼
SList.h
SList.c
一、什么是鏈表？
????????鏈表是一種物理存儲上非連續，數據元素的邏輯順序通過鏈表中的指針鏈接次序，實現的一種線性存儲結構。鏈表由一系列節點（鏈表中每一個元素稱為節點）組成，節點在運行時動態生成 （malloc），每個節點包括兩個部分：
- ? ? ?一個是存儲數據元素的數據域
- ? ? ?另一個是存儲下一個節點地址的指針域
二、為什么要使用鏈表？
? ? ? ? ?使用鏈表用于解決動態數量的數據存儲。比如說，我們要管理一堆票據，可能有一張，但也可能有一億張。怎么辦呢？申請一個幾十G的大數組存儲著嗎？萬一用戶只有一百張票據要處理呢？內存較小拒絕運行？可申請少了又不夠用啊……
????????而且，用數組的話，刪除然后添加票據，是每次刪除讓后面五百萬張往前移一格呢、還是每次添加從頭搜索空閑格子？如何區分空閑格子和值為0的數據？要進行區分的話是多占用空間呢還是占用數據值域？占用了值域會不會使得數據處理變得格外復雜？會不會一不小心就和正常數據混淆？萬一拿來區分的字段在某個版本后廢棄不用、或者擴充值域了呢？
????????那么，鏈表這種東西就是個很有效的數據結構，可以很有效的管理這類不定量的數據。
三、 單鏈表介紹與使用
? ? ? ? 3.1 單鏈表
????????單鏈表的每個節點除了存放數據元素外，還要存儲指向下一個節點的指針。與順序表進行對比：
| 優點 | 缺點 | |
| 順序表 | 可隨機存儲，存儲密度較高 | 要求大片連續空間，改變容量不方便 |
| 單鏈表 | 不要求大片連續空間，改變容量方便 | 不可隨機存取，要耗費一定空間存放指針 |
? ? ? ? ?3.1.1 創建單鏈表節點
typedef int SLTDataType;
//鏈表是由節點構成
//邏輯結構：一定連續；物理結構：不一定連續
//不會造成空間的浪費，由獨立的節點構成
typedef struct SListNode { //SList : single linked list 單鏈表SLTDataType data; // ?一個是存儲數據元素的數據域struct SListNode* next; //? ?另一個是存儲下一個節點地址的指針域
}SLTNode;
? ? ? ? 上面的結構體僅是單鏈表節點的定義，要創建一新的節點需要對里面的數據進行初始化：插入數值，節點指向的下一個節點為空
//創建一個節點
struct SListNode* SLTBuyNode(SLTDataType x) {SLTNode* newnode = (struct SListNode*)malloc(sizeof(struct SListNode));newnode->data = x;newnode->next = NULL;return newnode;
}
????????3.1.2?單鏈表的頭插、尾插
? ? ? ? ?單鏈表的尾插
? ? ? ? 這里傳遞的鏈表節點的參數，為什么是二級指針呢？
????????在初始化過程中，需要修改頭指針，因此要用到二級指針傳遞頭指針的地址，這樣才能修改頭指針。這與普通變量類似，當需要修改普通變量的值，需傳遞其地址。使用二級指針，很方便就修改了傳入的結點一級指針的值。 如果用一級指針，則只能通過指針修改指針所指內容，卻無法修改指針的值，也就是指針所指的內存塊。
//鏈表的尾插
void SLTPushBack(SLTNode** pphead, SLTDataType x) { //一級指針傳遞的為結構體變量地址的值，二級指針接收的是指向結構體變量的指針的地址assert(pphead);SLTNode* newnode = SLTBuyNode(x);//鏈表為空，新節點作為ppheadif (*pphead == NULL) {*pphead = newnode;return;}//鏈表不為空，鏈表的尾指向新節點SLTNode* ptail = *pphead;while (ptail->next) {ptail = ptail->next;}ptail->next = newnode;
}? ? ? ? ?單鏈表的頭插
void SLTPushFront(SLTNode** pphead, SLTDataType x) {assert(pphead);//鏈表為空，新節點指向pphead，pphead再指向新節點；鏈表不為空，新節點指向pphead，pphead再指向新節點SLTNode* newnode = SLTBuyNode(x);newnode->next = *pphead;*pphead = newnode;
}
? ? ? ? ?插入完數據后，想要打印以一下鏈表的數據，通過從頭開始一個一個節點地訪問數據，并打印，便實現了鏈表數據的打印。然后看看插入的情況；
//打印鏈表
void SLTPrint(SLTNode* phead) {SLTNode* pcur = phead;while (pcur) {printf("%d->", pcur->data);pcur = pcur->next;}printf("NULL\n");
}? ? ? ? ?尾插部分數據，觀察打印的結果是否符合預期結果；發現運行結果與預期相符，所以鏈表的插入操作是沒什么大問題的
3.1.3? 單鏈表的頭刪、尾刪
????????如果鏈表為空，不需要刪除；如果刪除的是第一個結點，則需要將保存鏈表首地址的指針保存第一個結點的下一個結點的 地址 如果刪除的是中間結點，則找到中間結點的前一個結點，讓前一個結點的指針域保存這個結 點的后一個結點的地址即可?
?????????單鏈表的尾刪
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;
}?????????單鏈表的頭刪
void SLTPopFront(SLTNode** pphead) {assert(pphead);//鏈表為空，不刪除assert(*pphead);//鏈表不為空，釋放最后一個節點，其前驅節點指向空SLTNode* pcur = *pphead;*pphead = pcur->next;pcur->next = NULL;free(pcur);pcur = NULL;
}?3.1.4?鏈表節點的查找
?????????先對比第一個結點的數據域是否是想要的數據，如果是就直接返回，如果不是則繼續查找下 一個結點，如果到達最后一個結點的時候都沒有匹配的數據，說明要查找數據不存在
//查找
SLTNode* STLFind(SLTNode** pphead, SLTDataType x) {assert(pphead);SLTNode* pcur = *pphead;while (pcur) {if (pcur->data == x) {return pcur;}pcur = pcur->next;}return NULL;
}3.1.5?在指定位置插入數據
????????在指定位置前插入數據
//在指定位置前插入數據
void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x) {assert(pphead);assert(pos);//頭節點不能為空assert(*pphead);SLTNode* newnode = SLTBuyNode(x);//當pos節點指向 頭節點時,進行頭插if (*pphead == pos) {SLTPushFront(pphead, x);return;}//pos pphead不指向同一節點SLTNode* prev = *pphead;while (prev->next != pos) { //找到pos節點的前驅prev = prev->next;}newnode->next = pos;prev->next = newnode;
}?????????在指定位置之后插入數據
//在指定位置之后插入數據
void SLTInsertAfter(SLTNode* pos, SLTDataType x) {assert(pos);SLTNode* newnode = SLTBuyNode(x);newnode->next = pos->next;pos->next = newnode;
}?3.1.6?刪除pos之后的節點
//刪除pos之后的節點
void SLTEraseAfter(SLTNode* pos) {assert(pos);assert(pos->next);//pos后不為空SLTNode* del = pos->next;pos->next = pos->next->next;free(del);del = NULL;
}3.1.7?銷毀鏈表
????????重新定義一個指針next，保存pcur指向節點的地址，然后next后移保存下一個節點的地址，然后釋放pcur對應的節點，以此類推，直到pcur為NULL為止?
//銷毀鏈表,由獨立的節點構成，需要一個個銷毀
void SListDestroy(SLTNode** pphead) {assert(pphead);assert(*pphead);SLTNode* pcur = *pphead;while (pcur) {SLTNode* next = pcur->next;free(pcur);pcur = next;}*pphead = NULL;
}?四、完整代碼
SList.h
?
#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>//順序表存在的一定的問題：
//1.順序表的中間/頭部的插入需要挪動數據
//2.擴容存在性能的消耗
//3.會有空間的浪費typedef int SLTDataType;
//鏈表是由節點構成
//邏輯結構：一定連續；物理結構：不一定連續
//不會造成空間的浪費，由獨立的節點構成
typedef struct SListNode { //SList : single linked list 單鏈表SLTDataType data;struct SListNode* next;
}SLTNode;//鏈表的頭插、尾插
void SLTPushBack(SLTNode** pphead, SLTDataType x);
void SLTPushFront(struct SListNode** pphead, SLTDataType x);//鏈表的頭刪、尾刪
void SLTPopBack(SLTNode** pphead);
void SLTPopFront(SLTNode** pphead);//打印鏈表
void SLTPrint(SLTNode* phead);//查找
SLTNode* STLFind(SLTNode** phead, SLTDataType x);//在指定位置前插入數據
void SLTInsert(SLTNode** phead, SLTNode* pos,SLTDataType x);//刪除pos節點
void SLTErase(SLTNode** phead, SLTNode* pos);
//在指定位置之后插入數據
void SLTInsertAfter(SLTNode* pos, SLTDataType x);
//刪除pos之后的節點
void SLTEraseAfter(SLTNode* pos);
//銷毀鏈表
void SListDestroy(SLTNode** phead);SList.c
#include"SList.h"//創建一個節點
struct SListNode* SLTBuyNode(SLTDataType x) {SLTNode* newnode = (struct SListNode*)malloc(sizeof(struct SListNode));newnode->data = x;newnode->next = NULL;return newnode;
}//打印鏈表
void SLTPrint(SLTNode* phead) {SLTNode* pcur = phead;while (pcur) {printf("%d->", pcur->data);pcur = pcur->next;}printf("NULL\n");
}//鏈表的頭插、尾插
void SLTPushBack(SLTNode** pphead, SLTDataType x) { //一級指針傳遞的為結構體變量地址的值，二級指針接收的是指向結構體變量的指針的地址assert(pphead);SLTNode* newnode = SLTBuyNode(x);//鏈表為空，新節點作為ppheadif (*pphead == NULL) {*pphead = newnode;return;}//鏈表不為空，鏈表的尾指向新節點SLTNode* ptail = *pphead;while (ptail->next) {ptail = ptail->next;}ptail->next = newnode;
}void SLTPushFront(SLTNode** pphead, SLTDataType x) {assert(pphead);//鏈表為空，新節點指向pphead，pphead再指向新節點；鏈表不為空，新節點指向pphead，pphead再指向新節點SLTNode* newnode = SLTBuyNode(x);newnode->next = *pphead;*pphead = newnode;
}//鏈表的頭刪、尾刪
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;
}
void SLTPopFront(SLTNode** pphead) {assert(pphead);//鏈表為空，不刪除assert(*pphead);//鏈表不為空，釋放最后一個節點，其前驅節點指向空SLTNode* pcur = *pphead;*pphead = pcur->next;pcur->next = NULL;free(pcur);pcur = NULL;
}//查找
SLTNode* STLFind(SLTNode** pphead, SLTDataType x) {assert(pphead);SLTNode* pcur = *pphead;while (pcur) {if (pcur->data == x) {return pcur;}pcur = pcur->next;}return NULL;
}//在指定位置前插入數據
void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x) {assert(pphead);assert(pos);//頭節點不能為空assert(*pphead);SLTNode* newnode = SLTBuyNode(x);//當pos節點指向 頭節點時,進行頭插if (*pphead == pos) {SLTPushFront(pphead, x);return;}//pos pphead不指向同一節點SLTNode* prev = *pphead;while (prev->next != pos) { //找到pos節點的前驅prev = prev->next;}newnode->next = pos;prev->next = newnode;
}//刪除pos節點
void SLTErase(SLTNode** pphead, SLTNode* pos) {assert(pphead);assert(pos);//當pos節點指向 頭節點時,進行頭刪if (*pphead == pos) {SLTPopFront(pphead);return;}//pos pphead不指向同一節點SLTNode* prev = *pphead;while (prev->next != pos) { //找到pos節點的前驅prev = prev->next;}prev->next = pos->next;free(pos);pos = NULL;
}//在指定位置之后插入數據
void SLTInsertAfter(SLTNode* pos, SLTDataType x) {assert(pos);SLTNode* newnode = SLTBuyNode(x);newnode->next = pos->next;pos->next = newnode;
}//刪除pos之后的節點
void SLTEraseAfter(SLTNode* pos) {assert(pos);assert(pos->next);//pos后不為空SLTNode* del = pos->next;pos->next = pos->next->next;//pos->next = del->next;free(del);del = NULL;
}//銷毀鏈表,由獨立的節點構成，需要一個個銷毀
void SListDestroy(SLTNode** pphead) {assert(pphead);assert(*pphead);SLTNode* pcur = *pphead;while (pcur) {SLTNode* next = pcur->next;free(pcur);pcur = next;}*pphead = NULL;
}
的安裝和使用)
