動態單鏈表的傳統存儲方式和10種常見操作-C語言實現
順序線性表的優點：方便存取（隨機的），特點是物理位置和邏輯為主都是連續的（相鄰）。但是也有不足，比如；前面的插入和刪除算法，需要移動大量元素，浪費時間，那麼鏈式線性表 (簡稱鏈表) 就能解決這個問題。
一般鏈表的存儲方法
一組物理位置任意的存儲單元來存放線性表的數據元素，當然物理位置可以連續，也可以不連續，或者離散的分配到內存中的任意位置上都是可以的。故鏈表的邏輯順序和物理順序不一定一樣。
因為，鏈表的邏輯關系和物理關系沒有必然聯系，那麼表示數據元素之間的邏輯映象就要使用指針，每一個存儲數據元素的邏輯單元叫結點（node）。
結點裡有兩個部分，前面存儲數據元素內容，叫數據域，後面部分存儲結點的直接後繼在內存的物理位置，叫指針域。那麼就可以實現用指針（也叫鏈）把若干個結點的存儲映象鏈接為表，就是鏈式線性表。
上面開始介紹的是最簡單的鏈表，因為結點裡只有一個指針域，也就是俗稱的單鏈表（也叫線性鏈表）。
單鏈表可以由一個叫頭指針的東東唯一確定，這個指針指向了鏈表（也就是直接指向第一個結點）。因此單鏈表可以用頭指針的名字來命名。且最後一個結點指針指向NULL。
鏈表類別
1、實現的角度：動態鏈表，靜態鏈表（類似順序表的動態和靜態存儲）
2、鏈接方式的角度：單鏈表，雙向鏈表，循環鏈表
單鏈表
單鏈表的頭結點
一般是使用單鏈表的頭指針指向鏈表的第一個結點，有的人還這樣做，在第一個結點之前再加一個結點（不保存任何數據信息，只保存第一個結點的地址，有時也保存一些表的附加信息，如表長等），叫頭結點（頭結點是頭結點，第一個結點是第一個結點）。那麼此時，頭指針指向了頭結點。並且有無頭結點都是可以的。鏈表還是那個鏈表，只不過表達有差異。
那麼問題來了！為什麼還要使用頭結點？
作用是對鏈表進行操作時，可以對空表、非空表的情況以及對首元結點進行統一處理，編程更方便。
描述動態單鏈表
有兩種做法，一種是傳統的動態鏈表結構，暨只定義結點的存儲結構，使用4個字節的指針變量表示線性表。還有一種是直接采用結構體變量（類似順序表）來表示線性表。
顧名思義，肯定是第二種方法比較方便。
先看傳統存儲動態單鏈表結構的操作
1 /************************************************************************/
2 /* 文件名稱：ADT.h
3 /* 文件功能：動態單鏈表傳統存儲結構和常見操作
4 /* 作 者：dashuai
5 /* 備 注：以下算法，並沒有考證是否全部都是最佳優化的，關於算法的優化後續研究
6 /************************************************************************/
7 #include <stdio.h>
8 #include <stdlib.h>
9
10 //傳統的單鏈表動態存儲結構（帶頭指針）
11 typedef struct Node//Node標記可以省略，但如結構裡聲明了指向結構的指針，那麼不能省略！
12 {
13 char data;//數據域
14 struct Node *next;//指針域
15 } Node, *LinkList;//LinkList是指向Node結構類型的指
16
17 /*
18 1、查找（按值）算法
19 找到第一個值等於value的結點，找到則返回存儲位置
20 */
21 LinkList getElemByValue(LinkList L, char value);
22
23 /*
24 2、查找（按序號）算法
25 查找第i個元素，並用變量value返回值，否則返回提示，即使知道了序號，也必須使用指針順次查訪
26 */
27 void getElemByNum(LinkList L, int num, char *value);
28
29 /*
30 3、刪除結點
31 刪除元素，並用value返回值
32 */
33 void deleteList(LinkList L, int i, char *value);
34
35 /*
36 4、插入結點
37 在第i個位置之前插入結點e
38 */
39 void insertList(LinkList L, int i, char value);
40
41 /*
42 5、頭插法建立單鏈表（逆序建表）
43 從一個空結點開始，逐個把 n 個結點插入到當前鏈表的表頭
44 */
45 void createListByHead(LinkList *L, int n);
46
47 /*
48 6、尾插法建立單鏈表（順序建表）
49 從一個空結點開始，逐個把 n 個結點插入到當前鏈表的表尾
50 */
51 void createListByTail(LinkList *L, int n);
52
53 /*
54 7、尾插法建立有序單鏈表（歸並鏈表）
55 把兩個有序（非遞減）鏈表LA LB合並為一個新的有序（非遞減）鏈表LC(空表)
56 要求：不需要額外申請結點空間來完成
57 */
58 void mergeListsByTail(LinkList LA, LinkList LB, LinkList LC);
59
60 /*
61 8、銷毀單鏈表
62 */
63 void destoryLinkList(LinkList *L);
64
65 /*
66 9、求表長，長度保存到頭結點
67 */
68 void getLength(LinkList L);
69
70 /*
71 10、遍歷單鏈表
72 */
73 void traversalList(LinkList L);
復制代碼
C變量的隨用隨定義，可以確定C99之後新增加的，和c++一樣，貌似一些編譯器還不支持
復制代碼
1 #include "ADT.h"
2
3 /*
4 1、查找（按值）算法
5 找到第一個值等於value的結點，找到則返回存儲位置
6 */
7 LinkList getElemByValue(LinkList L, char value)
8 {
9 //定義指示指針指向L第一個結點
10 LinkList p = L->next;//L開始指向了頭結點，L->next指向的就是第一個結點
11
12 while (p && p->data != value)
13 {
14 //p++;顯然錯誤，離散存儲，非隨機結構
15 p = p->next;//指針順鏈移動，直到找到或者結束循環
16 }
17 //當找不到，則p最終指向NULL，循環結束
18 return p;//返回存儲位置或NULL
19 }
復制代碼
算法執行時間和value有關，時間復雜度為0（n），n表長
復制代碼
1 /*
2 2、查找（按序號）算法
3 查找第i個元素，並用變量value返回值，否則返回提示，即使知道了序號，也必須使用指針順次查訪
4 */
5 void getElemByNum(LinkList L, int num, char *value)
6 {
7 int count = 1;
8 LinkList p = L->next;
9 //控制指針p指向第num個結點
10 while (p && count < num)//num若為0或者負數直接跳出循環，若超出表長則遍歷完畢，跳出循環，找到了元素也跳出循環
11 {
12 p = p->next;//p指向第num個結點，count此時為num值
13 count++;
14 }
15 //如果num大於表長，則count值增加到表長度時，p恰好指向表尾結點，遍歷完整個鏈表也找不到結點，此時再循環一次
16 //p指向null，count = 表長 + 1，循環結束，這裡也隱含說明了num大於 表長 的不合法情況
17 if (!p || count > num)//說明num至少比 表長 大
18 {
19 //num <= 0或者num大於表長時，跳出while循環，來到if語句，判斷不合法
20 puts("num值非法！");
21 }
22 else
23 {
24 *value = p->data;
25 printf("找到第%d個元素的值 = %c\n", num, *value);
26 }
27 }
復制代碼
//時間復雜度0（n），n為表長
復制代碼
1 /*
2 3、刪除結點
3 刪除第i個元素，並用value返回值
4 */
5
6 void deleteList(LinkList L, int i, char *value)
7 {
8 LinkList p = L;//頭腦一定要清晰！這裡p應該指向頭結點
9 LinkList temp;
10 int j = 0;//對應著頭結點的序號0
11
12 /*while (p && j < i)
13 {
14 p = p->next;此時，p指向的是i元素位置，要刪除i元素，需要知道i的前驅！
15 j++;
16 }*/
17
18 while (p->next && j < i - 1)//i - 1可以保證指向其前驅 ，j=0需要注意，刪除是從1-n都可以
19 {
20 p = p->next;//指向i元素前驅（i-1）
21 j++;
22 }
23 //必須想到判斷合法性
24 if (!(p->next) || j > i - 1)//同樣判斷i的下邊界，和上邊界
25 {
26 puts("i值不合法！");
27 }
28 else
29 {
30 //找到了前驅p
31 temp = p->next;//temp指針指向i元素
32 //p->next = p->next->next;等價於
33 p->next = temp->next;//鏈表刪除結點的關鍵邏輯
34 *value = temp->data;
35 free(temp);//釋放temp指向的結點的內存空間
36 temp = NULL;
37 puts("刪除成功！");
38 }
39 }
復制代碼
時間復雜度，雖然沒有移動任何元素，還是0（n），因為最壞時核心語句頻度為n（表長）
為什麼不是p？
//判斷表為非空，因為不止一次刪除操作！總會刪空，則p還是指向的頭結點！如果依然是while（p &&……），表空時，按道理函數不應該再執行核心語句，提前判斷出錯，但此時卻還要執行循環體，循環結束才能到if（！p），而使用while(p->next && ……），表空就直接跳出循環，到if語句，提示錯誤。這是刪除算法總是需要注意的細節，插入算法則是如果內存有限，或者是順序的表，或者靜態鏈表，那麼總是要注意存儲空間滿足大小的問題
復制代碼
1 /*
2 4、插入結點
3 在第i個位置之前插入結點e，換句話說就是在第i-1個位置之後插入，類似前面的刪除操作思想
4 */
5 void insertList(LinkList L, int i, char value)
6 {
7 LinkList p = L;
8 LinkList s;
9 int j = 0;
10 //和刪除不同，插入操作不用注意表空的情況
11 while (p && j < i - 1)
12 {
13 p = p->next;
14 j++;
15 }
16
17 if (!p || j > i - 1)//i小於1或者大於表長+1不合法
18 {
19 puts("i不合法！");
20 }
21 else
22 {
23 //先分配結點存儲空間
24 s = (LinkList)malloc(sizeof(Node));
25 //依次傳入插入的元素內容和修改邏輯鏈接
26 s->data = value;
27 //鏈表插入算法的關鍵邏輯
28 s->next = p->next;
29 p->next = s;//順序不可顛倒，原則是指針在修改前，先保留再修改，不能先修改再保留
30 puts("插入成功！");
31 }
32 }
復制代碼
插入算法時間復雜度分析：0(n)，最壞情況下頻度是n
/插入和刪除算法，還有一個思路，就是既然需要每次都找前驅，那麼為什麼不弄兩個指針呢？一個指向當前位置，一個緊隨其後指向前，個人其實感覺是脫褲子放屁……
復制代碼
1 //以刪除為例
2 void deleteList(LinkList L, int i, char *value)
3 {
4 LinkList prePoint = L;//前驅指針初始化指向頭結點
5 LinkList point = L->next;//當前指針初始化指向第一個結點
6 LinkList temp = NULL;
7 int j = 1;
8 //i要>0,且小於等於表長
9 while (point && j < i)//如果表非空，找到要刪除的元素位置
10 {
11 point = point->next;
12 prePoint = prePoint->next;//分別順次後移
13 j++;
14 }
15
16 if (!point || j > i)
17 {
18 puts("i不合法！");
19 }
20 else
21 {
22 temp = point;
23 prePoint->next = point->next;
24 *value = temp->data;
25 free(temp);
26 temp = NULL;
27 puts("刪除成功！");
28 }
29 }
復制代碼
時間復雜度依然是O(n)
復制代碼
1 /*
2 5、頭插法建立單鏈表（逆序建表）
3 從一個空結點開始，逐個把 n 個結點插入到當前鏈表的表頭
4 */
5
6 //開始就空表，則肯定先分配結點（帶頭結點）
7 void createListByHead(LinkList *L, int n)
8 {
9 LinkList p = NULL;
10 int i = 0;
11 *L = (LinkList)malloc(sizeof(Node));//L指向頭結點
12 (*L)->next = NULL;//空表建立
13 //頭插法
14 for (i = 1; i <= n; i++)
15 {
16 p = (LinkList)malloc(sizeof(Node));//先創建要插入的結點
17 scanf("%c", &(p->data));//給結點數據域賦值 再次驗證 -> 優先級高於取地址 &
18
19 while (getchar() != '\n')
20 {
21 continue;
22 }
23
24 p->next = (*L)->next;//再讓插入的結點的next指針指向後繼（鏈接的過程），注意後繼不能為空（除去第一次插入）
25 //p->next = NULL;//錯誤
26 (*L)->next = p;//最後保證插入結點是第一個結點，把頭結點和第一個結點鏈接起來。
27 }
28
29 printf("頭插法建表成功\n");
30 }
復制代碼
時間復雜度：必然是O（n），插入了n個元素
鏈表和順序表存儲結構不同，動態,整個可用內存空間可以被多個鏈表共享，每個鏈表無需事先分配存儲容量，由系統應要求自動申請。建立鏈表是動態的過程。
//如a b c d，依次頭插法（頭插 總是在第一個結點前插入，暨插入的結點總是作為第一個結點）到空鏈表裡，那麼完成之後是
//d c b a
下面是正序的尾插法，如圖
復制代碼
1 /*
2 6、尾插法建立單鏈表（順序建表）
3 //對 5 算法的改進
4 */
5 //頭插法算法簡單，但生成的鏈表結點次序和輸入的順序相反。有時不太方便。
6 //若希望二者次序一致，可采用尾插法建表。該方法是將新結點順次的插入到當前鏈表的表尾上，為此必須增加一個尾指針tail，
7 //使其始終指向當前鏈表的尾結點。
8 void createListByTail(LinkList *L, int n)
9 {
10 LinkList tail = NULL;//尾指針
11 int i = 0;
12 LinkList p = NULL;//代表前驅
13 *L = (LinkList)malloc(sizeof(Node));
14 (*L)->next = NULL;
15 tail = *L;
16
17 for (i = 1; i <= n; i++)
18 {
19 p = (LinkList)malloc(sizeof(Node));
20 //_CRTIMP int __cdecl scanf(_In_z_ _Scanf_format_string_ const char * _Format, ...);返回int，傳入的參數個數
21 /*如果被成功讀入，返回值為參數個數
22 如果都未被成功讀入，返回值為0
23 如果遇到錯誤或遇到end of file，返回值為EOF*/
24 scanf("%c", &(p->data));
25 //清空輸入隊列的剩余的所有字符
26 while (getchar() != '\n')
27 {
28 continue;
29 }
30 //尾插操作，後繼總是空的
31 p->next = NULL;
32 //鏈接前驅
33 tail->next = p;//萬萬不能寫成*L->next = p;
34 //保證尾指針tail總是指向最後一個結點
35 tail = p;
36 }
37
38 printf("尾插法建表成功！ \n");
39 }
復制代碼
這樣操作，輸入的序列和輸出的序列是正序的，且時間復雜度為O（n）
復制代碼
1 /*
2 7、尾插法建立有序單鏈表（歸並鏈表）
3 把兩個有序（非遞減）鏈表LA LB合並為一個新的有序（非遞減）鏈表LC(空表)
4 要求：不需要額外申請結點空間來完成
5 */
6
7 //1、比較數據域，保證有序
8 //2、尾插法思想
9 //3、不需要額外申請結點空間來完成！
10 //使用現有的內存空間，完成操作，那麼可以想到用LC的頭指針去指向其中某個表的頭結點，內存共享
11
12 void mergeListsByTail(LinkList LA, LinkList LB, LinkList LC)
13 {
14 //因為要比較數據大小，需要兩個標記指針，分別初始化為標記AB的第一個結點
15 LinkList listA = LA->next;
16 LinkList listB = LB->next;
17 //還要不開辟內存，那麼內存共享，需要把表C讓其他表去表示
18 LinkList listC;//聲明一個標記C的指針
19 LC = LA;//比如表A。C表的頭指針指向A表的頭結點，做自己的頭結點
20 listC = LA;//C表的標記指針需要初始化，指向A的頭結點，待命
21 //接下來比較AB表數據，標記指針會順次後移，早晚有一個先指向末尾之後的NULL，故判斷是哪一個表的
22 while (listA && listB)
23 {
24 //判斷數據大小,非遞減
25 if (listA->data <= listB->data)
26 {
27 //則A的結點插入到C表（尾插）,單鏈表不可使用頭指針做遍歷
28 listC->next = listA;//先把A的結點鏈到C表
29 listC = listA;//listC等價於尾指針
30 //A指針後移,繼續循環比較
31 listA = listA->next;
32 }
33 else
34 {
35 //把B的結點插入到C（尾插）
36 listC->next = listB;
37 listC = listB;
38 listB = listB->next;
39 }//end of if
40 }//end of while
41 //循環結束，只需要把剩下的某個表的結點一次性鏈接到C表尾
42 if (listA)
43 {
44 //說明B空
45 listC->next = listA;
46 }
47
48 if (listB)
49 {
50 //A空
51 listC->next = listB;
52 }
53 //最後AB表比較之前一定有一個表都被遍歷了（也就是鏈接到了C），剩下的結點比如屬於某個表的，最後也都鏈接到C尾部
54 //那麼，此時就還有一個結點，那就是B表的頭結點！勿忘把B表頭結點釋放，這才是完全的兩個歸並為一個
55 free(LB);
56 LB = NULL;//杜絕野指針
57 }
復制代碼
算法時間復雜度，和頭插法比較的話，還是O（n）,其實順序表的有序歸並也是這個時間復雜度O（A.length + B.length），但是鏈表的尾插法歸並沒有移動元素，只是解除和重建鏈接的操作，也沒有額外開辟內存空間。空間復雜度不同。
復制代碼
1 /*
2 8、銷毀單鏈表
3 */
4 void destoryLinkList(LinkList *L)
5 {
6 LinkList p = NULL;
7
8 while (*L)
9 {
10 p = (*L)->next;
11 free(*L);//free不能對指向NULL的指針使用多次！
12 *L = p;
13 //徹底搞掉指針本身，free（L）僅僅是銷毀指針指向的內存，故還要連頭結點一起干掉，不過while循環裡隱形的包含了
14 }
15
16 *L = NULL;
17 puts("鏈表L已經銷毀，不存在！");
18 }
復制代碼
函數內部有動態分配內存的情形，應該把參數設定為指向指針的指針，當然還有別的方法，我習慣而已。
記得說：值傳遞函數，是把實參的一個拷貝送到函數體，函數體修改的是那份傳入的拷貝，不是函數跑到main裡去給它修改。
且形參和傳入的拷貝，還有函數體內的變量（棧中分配的內存），都是是代碼塊內的自動存儲類型的變量，也就是局部變量，函數執行完畢，變量自動銷毀，改變就不起作用。
指針形參可以改變實參，但是如果是針對函數內動態分配了內存的情況，把堆分配的內存地址賦給了指針參數，改變的是指針指向的內容，而指針變量（形參）本身的內存地址沒有改變，故根本句不會成功修改實參。
指向指針的指針，存放的是指向實參內存地址A的指針的地址B，修改B地址，改變了B指向的內容，而B指向的內容恰恰就是一級指針A本身，一級指針A的修改，使得實參被改變，對實參（指針變量C），需要取出指針C自己的的地址，傳入函數。達到間接修改實參的目的。
復制代碼
1 /*
2 9、求表長，長度保存在頭結點
3 */
4 void getLength(LinkList L)
5 {
6 int length = 0;
7 LinkList p = NULL;
8
9 if (L)
10 {
11 p = L->next;
12
13 while (p)
14 {
15 p = p->next;
16 length++;
17 }
18
19 L->data = length;
20 printf("%d\n", L->data);
21 }
22 else
23 {
24 puts("表已經銷毀！無法計算長度了……");
25 }
26 }
復制代碼
復制代碼
1 /*
2 10、遍歷鏈表
3 */
4 void traversalList(LinkList L)
5 {
6 int i = 0;
7 int length = 0;
8 LinkList p = L->next;
9 length = L->data;//遍歷之前，務必先求表長！
10 puts("遍歷之前，務必先求表長！");
11
12 for (; i < length; i++)
13 {
14 putchar(p->data);
15 p = p->next;
16 }
17 putchar('\n');
18 }
復制代碼
測試
復制代碼
1 #include <stdio.h>
2 #include <stdlib.h>
3 #include <assert.h>
4 #include "ADT.h"
5
6 int main(void)
7 {
8 LinkList L = NULL;//完全的空表，連頭結點都沒有
9 LinkList LTwo = NULL;
10 LinkList val = NULL;
11 int i = 0;
12 char value = '0';
13
14 puts("請輸入5個字符變量（一行一個）：");
15 puts("使用尾插法建立單鏈表L，5個結點，一個頭結點");
16 //輸入 12345
17 createListByTail(&L, 5);//尾插法建表
18
19 //12345正確的存入到了5個結點裡，尾插法創建了一個單鏈表L
20
21 //先求長度
22 puts("L長度為");
23 getLength(L);
24
25 //遍歷 12345
26 puts("遍歷這個鏈表結點元素");
27 traversalList(L);
28
29 //用完必須銷毀
30 puts("把鏈表L銷毀，L = NULL;");
31 destoryLinkList(&L);
32
33 //頭插法 abcde
34 //void createListByHead(<wo, 5);//報錯;語法錯誤 : 缺少“;”(在“類型”的前面)
35 puts("使用頭插法建立新的單鏈表LTwo，5個結點，一個頭結點");
36 createListByHead(<wo, 5);
37
38 //求長度
39 getLength(LTwo);
40
41 //遍歷 edcba
42 puts("遍歷表中結點元素");
43 traversalList(LTwo);
44
45 //按值查找
46 puts("查找LTwo表的結點數據 = ‘2’的結點");
47 val = getElemByValue(LTwo, '2');
48
49 if (val)
50 {
51 printf("找到了val，地址 = %p \n", &val);
52 }
53
54 puts("‘2’在表 LTwo 裡沒找到！");
55
56 //插入結點
57 puts("在位置 1 之後插入一個結點，裡面數據是 ‘p’");
58 insertList(LTwo, 1, 'p');
59
60 //遍歷 pedcba
61 puts("開始遍歷表LTwo");
62 traversalList(LTwo);
63
64 //按序查找
65 puts("查找位置=2的結點，並打印出它的數據內容");
66 getElemByNum(LTwo, 2, &value);
67
68
69 //刪除結點
70 puts("刪除位置 1 的結點，並打印出刪除結點的數據");
71 deleteList(LTwo, 1, &value);
72 printf("%c\n", value);
73
74 //遍歷 pedcba
75 puts("再次遍歷鏈表LTwo");
76 traversalList(LTwo);
77
78 //求鏈表長度，把長度保存的頭結點
79 puts("計算鏈表長度，並把長度保存到了LTwo的頭結點");
80 getLength(LTwo);
81 printf("%d\n", LTwo->data);
82
83 //必須有銷毀
84 puts("動態存儲的結構用完一定要銷毀");
85 destoryLinkList(<wo);
86
87 //此時銷毀的表長規定是0
88 puts("銷毀之後，鏈表長度：");
89 getLength(LTwo);
90
91 system("pause");
92 return 0;
93 }
復制代碼
scanf函數的特點是接受單詞，而不是字符串，字符串一般是gets函數，單個字符接收是getchar函數，因為scanf函數遇到空白字符（tab，空格，回車，制表符等）就不再讀取輸入，那字符串怎麼能方便輸入？
但是輸入隊列裡如果還有字符，那麼會留到緩存內，需要在定義裡使用getchar函數來消除回車帶來的影響。
