動態單鏈表的傳統存儲方式和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函數來消除回車帶來的影響。