單鏈表學習的超詳細說明（二）

昨天跟大家分享了單鏈表的一些基本用法，今天接著繼續(xù)和大家分享單鏈表的用法，今天分享完，單鏈表的操作就暫告一段落了，后面接著分享雙鏈表的學習和實戰(zhàn)！

一、單鏈表的遍歷：

1、什么叫遍歷？

遍歷就是把單鏈表中的各個節(jié)點挨個拿出來，就叫遍歷。

2、如何來遍歷單鏈表？

從頭指針＋頭節(jié)點開始，順著鏈表掛接指針依次訪問鏈表的各個節(jié)點，取出這個節(jié)點的數(shù)據(jù)，然后再往下一個節(jié)點，直到最后一個節(jié)點，結(jié)束訪問。

3、注意事項：

一是不能遺漏元素，二是不能重復、追求效率

4、實戰(zhàn)代碼演示：

1 ＃include ＜stdio．h＞

2 ＃include ＜strings．h＞

3 ＃include ＜stdlib．h＞

4／／ 構(gòu)建一個鏈表的節(jié)點

5struct node

6 ｛

7 int data； ／／ 有效數(shù)據(jù)

8 struct node ＊pNext； ／／ 指向下一個節(jié)點的指針

9 ｝；

10 ／／ 作用：創(chuàng)建一個鏈表節(jié)點

11 ／／ 返回值：指針，指針指向我們本函數(shù)新創(chuàng)建的一個節(jié)點的首地址

12 struct node ＊ create＿node（int data）

13 ｛

14 struct node ＊p ＝ （struct node ＊）malloc（sizeof（struct node））；

15 if （NULL ＝＝ p）

16 ｛

17 printf（＂malloc error．n＂）；

18 return NULL；

19 ｝

20 ／／ 清理申請到的堆內(nèi)存

21 bzero（p， sizeof（struct node））；

22 ／／ 填充節(jié)點

23 p－＞data ＝ data；

24 p－＞pNext ＝ NULL；

25 return p；

26｝

27／／ 計算添加了新的節(jié)點后總共有多少個節(jié)點，然后把這個數(shù)寫進頭節(jié)點中。

28void insert＿tail（struct node ＊pH， struct node ＊new）

29｛

30 int cnt ＝ 0；

31 ／／ 分兩步來完成插入

32 ／／ 第一步，先找到鏈表中最后一個節(jié)點

33 struct node ＊p ＝ pH；

34 while （NULL ?。?p－＞pNext）

35 ｛

36 p ＝ p－＞pNext； ／／ 往后走一個節(jié)點

37 cnt＋＋；

38 ｝

39 ／／ 第二步，將新節(jié)點插入到最后一個節(jié)點尾部

40 p－＞pNext ＝ new；

41 pH－＞data ＝ cnt ＋ 1；

42 ｝

43 void insert＿head（struct node ＊pH， struct node ＊new）

44 ｛

45 ／／ 第1步： 新節(jié)點的next指向原來的第一個節(jié)點

46 new－＞pNext ＝ pH－＞pNext；

47 ／／ 第2步： 頭節(jié)點的next指向新節(jié)點的地址

48 pH－＞pNext ＝ new；

49 ／／ 第3步： 頭節(jié)點中的計數(shù)要加1

50 pH－＞data ＋＝ 1；

51 ｝

52 ／／ 遍歷單鏈表，pH為指向單鏈表的頭指針，遍歷的節(jié)點數(shù)據(jù)打印出來

53 void bianli（struct node＊pH）

54 ｛

55 ／／pH－＞data ／／ 頭節(jié)點數(shù)據(jù)，不是鏈表的常規(guī)數(shù)據(jù)，不要算進去了

56 ／／struct node ＊p ＝ pH； ／／ 錯誤，因為頭指針后面是頭節(jié)點

57 struct node ＊p ＝ pH－＞pNext； ／／ p直接走到第一個節(jié)點

58 printf（＂－－－－－－－－－－－開始遍歷－－－－－－－－－－－n＂）；

59 ／／ 是不是最后一個節(jié)點

60 while （NULL ！＝ p－＞pNext）

61 ｛

62 printf（＂node data： ％d．n＂， p－＞data）；

63 p ＝ p－＞pNext；

64 ／／ 走到下一個節(jié)點，也就是循環(huán)增量

65 ｝

66 printf（＂node data： ％d．n＂， p－＞data）；

67 printf（＂－－－－－－－－－－－－－完了－－－－－－－－－－－－－n＂）；

68 ｝

69int main（void）

70｛

71 ／／ 定義頭指針

72 ／／struct node ＊pHeader ＝ NULL；

73 ／／ 這樣直接insert＿tail會段錯誤。

74 struct node ＊pHeader ＝ create＿node（0）；

75 insert＿head（pHeader， create＿node（11））；

76 insert＿head（pHeader， create＿node（12））；

77 insert＿head（pHeader， create＿node（13））；

78 ／／ 訪問鏈表頭節(jié)點的有效數(shù)據(jù)

79 printf（＂beader node data： ％d．n＂， pHeader－＞data）；

80 bianli（pHeader）；

81 return 0；

82 ｝

編譯結(jié)果；

1root＠ubuntu－virtual－machine：／mnt／hgfs／day＃ gcc flie1．c

2root＠ubuntu－virtual－machine：／mnt／hgfs／day＃ ．／a．out

3beader node data： 3．

4－－－－－－－－－－開始遍歷－－－－－－－－－－－

5node data： 13．

6node data： 12．

7node data： 11．

8 －－－－－－－－－－－－－完了－－－－－－－－－－－－－

二、單鏈表的刪除

1、如何找到要刪除的節(jié)點？

通過遍歷來查找節(jié)點。從頭指針＋頭節(jié)點開始，順著鏈表依次將各個節(jié)點拿出來，按照一定的方法比對，找到我們要刪除的那個節(jié)點。

2、如何來刪除一個節(jié)點？

（1）待刪除的節(jié)點不是尾節(jié)點的情況：首先把待刪除的節(jié)點的前一個節(jié)點的pNext指針指向待刪除的節(jié)點的后一個節(jié)點的首地址（這樣就把這個節(jié)點從鏈表中摘出來了），然后再將這個摘出來的節(jié)點free掉接口。

（2）待刪除的節(jié)點是尾節(jié)點的情況：首先把待刪除的尾節(jié)點的前一個節(jié)點的pNext指針指向null（這時候就相當于原來尾節(jié)點前面的一個節(jié)點變成了新的尾節(jié)點），然后將摘出來的節(jié)點free掉。

3、實戰(zhàn)代碼演示：

1 ＃include ＜stdio．h＞

2 ＃include ＜strings．h＞

3 ＃include ＜stdlib．h＞

4／／ 構(gòu)建一個鏈表的節(jié)點

5struct node

6 ｛

7 int data； ／／ 有效數(shù)據(jù)

8 struct node ＊pNext；

9 ／／ 指向下一個節(jié)點的指針

10 ｝；

11 ／／ 作用：創(chuàng)建一個鏈表節(jié)點

12 ／／ 返回值：指針，指針指向我們本函數(shù)新創(chuàng)建的一個節(jié)點的首地址

13 struct node ＊ create＿node（int data）

14 ｛

15 struct node ＊p ＝ （struct node ＊）malloc（sizeof（struct node））；

16 if （NULL ＝＝ p）

17 ｛

18 printf（＂malloc error．n＂）；

19 return NULL；

20 ｝

21 ／／ 清理申請到的堆內(nèi)存

22 bzero（p， sizeof（struct node））；

23 ／／ 填充節(jié)點

24 p－＞data ＝ data；

25 p－＞pNext ＝ NULL；

26 return p；

27｝

28／／ 計算添加了新的節(jié)點后總共有多少個節(jié)點，然后把這個數(shù)寫進頭節(jié)點中。

29void insert＿tail（struct node ＊pH， struct node ＊new）

30｛

31 int cnt ＝ 0；

32 ／／ 分兩步來完成插入

33 ／／ 第一步，先找到鏈表中最后一個節(jié)點

34 struct node ＊p ＝ pH；

35 while （NULL ?。?p－＞pNext）

36 ｛

37 p ＝ p－＞pNext； ／／ 往后走一個節(jié)點

38 cnt＋＋；

39 ｝

40 ／／ 第二步，將新節(jié)點插入到最后一個節(jié)點尾部

41 p－＞pNext ＝ new；

42 pH－＞data ＝ cnt ＋ 1；

43 ｝

44 void insert＿head（struct node ＊pH， struct node ＊new）

45 ｛

46 ／／ 第1步： 新節(jié)點的next指向原來的第一個節(jié)點

47 new－＞pNext ＝ pH－＞pNext；

48 ／／ 第2步： 頭節(jié)點的next指向新節(jié)點的地址

49 pH－＞pNext ＝ new；

50 ／／ 第3步： 頭節(jié)點中的計數(shù)要加1

51 pH－＞data ＋＝ 1；

52 ｝

53 ／／ 遍歷單鏈表，pH為指向單鏈表的頭指針，遍歷的節(jié)點數(shù)據(jù)打印出來

54 void bianli（struct node＊pH）

55 ｛

56 ／／pH－＞data ／／ 頭節(jié)點數(shù)據(jù)，不是鏈表的常規(guī)數(shù)據(jù)，不要算進去了

57 ／／struct node ＊p ＝ pH； ／／ 錯誤，因為頭指針后面是頭節(jié)點

58 struct node ＊p ＝ pH－＞pNext； ／／ p直接走到第一個節(jié)點

59 printf（＂－－－－－－－－－－－開始遍歷－－－－－－－－－－－n＂）；

60 ／／ 是不是最后一個節(jié)點

61 while （NULL ?。?p－＞pNext）

62 ｛

63 printf（＂node data： ％d．n＂， p－＞data）；

64 p ＝ p－＞pNext；

65 ／／ 走到下一個節(jié)點，也就是循環(huán)增量

66 ｝

67 printf（＂node data： ％d．n＂， p－＞data）；

68 printf（＂－－－－－－－－－－－－－完了－－－－－－－－－－－－－n＂）；

69 ｝

70 ／／ 從鏈表pH中刪除節(jié)點，待刪除的節(jié)點的特征是數(shù)據(jù)區(qū)等于data

71 ／／ 返回值：當找到并且成功刪除了節(jié)點則返回0，當未找到節(jié)點時返回－1

72 int delete＿node（struct node＊pH， int data）

73 ｛

74／／ 找到這個待刪除的節(jié)點，通過遍歷鏈表來查找

75struct node ＊p ＝ pH； ／／ 用來指向當前節(jié)點

76struct node ＊pPrev ＝ NULL；／／ 用來指向當前節(jié)點的前一個點

77while （NULL ?。?p－＞pNext）／／ 是不是最后一個節(jié)點

78｛

79 pPrev ＝ p； ／／ 在p走向下一個節(jié)點前先將其保存

80 p ＝ p－＞pNext； ／／ 走到下一個節(jié)點，也就是循環(huán)增量

81 ／／ 判斷這個節(jié)點是不是我們要找的那個節(jié)點

82 if （p－＞data ＝＝ data）

83 ｛

84 ／／ 找到了節(jié)點，處理這個節(jié)點

85 ／／ 分為2種情況，一個是找到的是普通節(jié)點，另一個是找到的是尾節(jié)點

86 ／／ 刪除節(jié)點的困難點在于：通過鏈表的遍歷依次訪問各個節(jié)點，找到這個節(jié)點

87 ／／ 后p指向了這個節(jié)點，但是要刪除這個節(jié)點關鍵要操作前一個節(jié)點，但是這

88 ／／ 時候已經(jīng)沒有指針指向前一個節(jié)點了，所以沒法操作。解決方案就是增加

89 ／／ 一個指針指向當前節(jié)點的前一個節(jié)點

90 if （NULL ＝＝ p－＞pNext）

91 ｛

92 ／／ 尾節(jié)點

93 pPrev－＞pNext ＝ NULL； ／／ 原來尾節(jié)點的前一個節(jié)點變成新尾節(jié)點

94 free（p）； ／／ 釋放原來的尾節(jié)點的內(nèi)存

95 ｝

96 else

97 ｛

98 ／／ 普通節(jié)點

99 pPrev－＞pNext ＝ p－＞pNext；

100／／ 要刪除的節(jié)點的前一個節(jié)點和它的后一個節(jié)點相連，這樣就把要刪除的節(jié)點給摘出來了

101 free（p）；

102 ｝

103 ／／ 處理完成之后退出程序

104 return 0；

105 ｝

106｝

107／／ 到這里還沒找到，說明鏈表中沒有我們想要的節(jié)點

108printf（＂沒找到這個節(jié)點．n＂）；

109return －1；

110｝

111int main（void）

112｛

113 ／／ 定義頭指針

114 ／／struct node ＊pHeader ＝ NULL；

115 ／／ 這樣直接insert＿tail會段錯誤。

116 struct node ＊pHeader ＝ create＿node（0）；

117 insert＿head（pHeader， create＿node（11））；

118 insert＿head（pHeader， create＿node（12））；

119 insert＿head（pHeader， create＿node（13））；

120 ／／ 訪問鏈表頭節(jié)點的有效數(shù)據(jù)

121 printf（＂beader node data： ％d．n＂， pHeader－＞data）；

122 bianli（pHeader）；

123delete＿node（pHeader， 12）；

124printf（＂－－－－－－－－－－－－－－－－－－刪除后－－－－－－－－－－－－－n＂）；

125bianli（pHeader）；

126 return 0；

127 ｝

編譯結(jié)果：

1root＠ubuntu－virtual－machine：／mnt／hgfs／day＃ gcc flie1．c

2root＠ubuntu－virtual－machine：／mnt／hgfs／day＃ ．／a．out

3beader node data： 3．

4－－－－－－－－－－－開始遍歷－－－－－－－－－－－

5node data： 13．

6node data： 12．

7node data： 11．

8－－－－－－－－－－－－完了－－－－－－－－－－－－－

9－－－－－－－－－－－－－－－－－－刪除后－－－－－－－－－－－－－

10－－－－－－－－－－－開始遍歷－－－－－－－－－－－

11node data： 13．

12node data： 11．

13－－－－－－－－－－－－－完了－－－－－－－－－－－－－

三、鏈表的逆序：

1、什么叫鏈表的逆序？

鏈表的逆序又叫反向，意思就是把鏈表中所有的有效節(jié)點在鏈表中的順序給反過來。

2、怎樣實現(xiàn)鏈表的逆序？

首先遍歷原鏈表，然后將原鏈表中的頭指針和頭節(jié)點作為新鏈表的頭指針和頭節(jié)點，原鏈表中的有效節(jié)點挨個依次取出來，采用頭插入的方法插入新鏈表中即可。

3、實戰(zhàn)代碼演示：

1 ＃include ＜stdio．h＞

2 ＃include ＜strings．h＞

3 ＃include ＜stdlib．h＞

4／／ 構(gòu)建一個鏈表的節(jié)點

5struct node

6 ｛

7 int data；

8 ／／ 有效數(shù)據(jù)

9 struct node ＊pNext； ／／ 指向下一個節(jié)點的指針

10 ｝；

11 ／／ 作用：創(chuàng)建一個鏈表節(jié)點

12 ／／ 返回值：指針，指針指向我們本函數(shù)新創(chuàng)建的一個節(jié)點的首地址

13 struct node ＊ create＿node（int data）

14 ｛

15 struct node ＊p ＝ （struct node

16 ＊）malloc（sizeof（struct node））；

17 if （NULL ＝＝ p）

18 ｛

19 printf（＂malloc error．n＂）；

20 return NULL；

21 ｝

22 ／／ 清理申請到的堆內(nèi)存

23 bzero（p， sizeof（struct node））；

24 ／／ 填充節(jié)點

25 p－＞data ＝ data；

26 p－＞pNext ＝ NULL；

27 return p；

28｝

29／／ 計算添加了新的節(jié)點后總共有多少個節(jié)點，然后把這個數(shù)寫進頭節(jié)點中。

30 void insert＿tail（struct node ＊pH， struct node ＊new）

31｛

32 int cnt ＝ 0；

33 ／／ 分兩步來完成插入

34 ／／ 第一步，先找到鏈表中最后一個節(jié)點

35 struct node ＊p ＝ pH；

36 while （NULL ！＝ p－＞pNext）

37 ｛

38 p ＝ p－＞pNext； ／／ 往后走一個節(jié)點

39 cnt＋＋；

40 ｝

41 ／／ 第二步，將新節(jié)點插入到最后一個節(jié)點尾部

42 p－＞pNext ＝ new；

43 pH－＞data ＝ cnt ＋ 1；

44 ｝

45 void insert＿head（struct node ＊pH， struct node ＊new）

46 ｛

47 ／／ 第1步： 新節(jié)點的next指向原來的第一個節(jié)點

48 new－＞pNext ＝ pH－＞pNext；

49 ／／ 第2步： 頭節(jié)點的next指向新節(jié)點的地址

50 pH－＞pNext ＝ new；

51 ／／ 第3步： 頭節(jié)點中的計數(shù)要加1

52 pH－＞data ＋＝ 1；

53 ｝

54 ／／ 遍歷單鏈表，pH為指向單鏈表的頭指針，遍歷的節(jié)點數(shù)據(jù)打印出來

55 void bianli（struct node＊pH）

56 ｛

57 ／／pH－＞data ／／ 頭節(jié)點數(shù)據(jù)，不是鏈表的常規(guī)數(shù)據(jù)，不要算進去了

58 ／／struct node ＊p ＝ pH； ／／ 錯誤，因為頭指針后面是頭節(jié)點

59 struct node ＊p ＝ pH－＞pNext； ／／ p直接走到第一個節(jié)點

60 printf（＂－－－－－－－－－－－開始遍歷－－－－－－－－－－－n＂）；

61 ／／ 是不是最后一個節(jié)點

62 while （NULL ！＝ p－＞pNext）

63 ｛

64 printf（＂node data： ％d．n＂， p－＞data）；

65 p ＝ p－＞pNext；

66 ／／ 走到下一個節(jié)點，也就是循環(huán)增量

67 ｝

68 printf（＂node data： ％d．n＂， p－＞data）；

69 printf（＂－－－－－－－－－－－－－完了－－－－－－－－－－－－－n＂）；

70 ｝

71 ／／ 從鏈表pH中刪除節(jié)點，待刪除的節(jié)點的特征是數(shù)據(jù)區(qū)等于data

72／／ 返回值：當找到并且成功刪除了節(jié)點則返回0，當未找到節(jié)點時返回－1

73int delete＿node（struct node＊pH， int data）

74｛

75／／ 找到這個待刪除的節(jié)點，通過遍歷鏈表來查找

76struct node ＊p ＝ pH；

77 ／／ 用來指向當前節(jié)點

78struct node ＊pPrev ＝ NULL；

79／／ 用來指向當前節(jié)點的前一個節(jié)點

80while （NULL ！＝ p－＞pNext） ／／ 是不是最后一個節(jié)點

81｛

82 pPrev ＝ p； ／／ 在p走向下一個節(jié)點前先將其保存

83 p ＝ p－＞pNext； ／／ 走到下一個節(jié)點，也就是循環(huán)增量

84 ／／ 判斷這個節(jié)點是不是我們要找的那個節(jié)點

85 if （p－＞data ＝＝ data）

86 ｛

87 ／／ 找到了節(jié)點，處理這個節(jié)點

88 ／／ 分為2種情況，一個是找到的是普通節(jié)點，另一個是找到的是尾節(jié)點

89 ／／ 刪除節(jié)點的困難點在于：通過鏈表的遍歷依次訪問各個節(jié)點，找到這個節(jié)點

90 ／／ 后p指向了這個節(jié)點，但是要刪除這個節(jié)點關鍵要操作前一個節(jié)點，但是這

91 ／／ 時候已經(jīng)沒有指針指向前一個節(jié)點了，所以沒法操作。解決方案就是增加

92 ／／ 一個指針指向當前節(jié)點的前一個節(jié)點

93 if （NULL ＝＝ p－＞pNext）

94 ｛

95 ／／ 尾節(jié)點

96 pPrev－＞pNext ＝ NULL； ／／ 原來尾節(jié)點的前一個節(jié)點變成新尾節(jié)點

97 free（p）； ／／ 釋放原來的尾節(jié)點的內(nèi)存

98 ｝

99 else

100 ｛

101 ／／ 普通節(jié)點

102 pPrev－＞pNext ＝ p－＞pNext；

103 ／／ 要刪除的節(jié)點的前一個節(jié)點和它的后一個節(jié)點相連，這樣就把要刪除的節(jié)點給摘出來了

104 free（p）；

105 ｝

106 ／／ 處理完成之后退出程序

107 return 0；

108 ｝

109｝

110／／ 到這里還沒找到，說明鏈表中沒有我們想要的節(jié)點

111printf（＂沒找到這個節(jié)點．n＂）；

112return －1；

113｝

114 ／／ 將pH指向的鏈表逆序

115 void reverse＿linkedlist（struct node ＊pH）

116 ｛

117struct node ＊p ＝ pH－＞pNext；

118 ／／ pH指向頭節(jié)點，p指向第1個有效節(jié)點

119struct node ＊pBack；

120 ／／ 保存當前節(jié)點的后一個節(jié)點地址

121／／ 當鏈表沒有有效節(jié)點或者只有一個有效節(jié)點時，逆序不用做任何操作

122if （（NULL ＝＝p） ｜｜ （NULL ＝＝ p－＞pNext））

123 return；

124／／ 當鏈表有2個及2個以上節(jié)點時才需要真正進行逆序操作

125while （NULL ?。?p－＞pNext） ／／ 是不是最后一個節(jié)點

126｛

127 ／／ 原鏈表中第一個有效節(jié)點將是逆序后新鏈表的尾節(jié)點，尾節(jié)點的pNext指向NULL

128 pBack ＝ p－＞pNext； ／／ 保存p節(jié)點后面一個節(jié)點地址

129 if （p ＝＝ pH－＞pNext）

130 ｛

131 ／／ 原鏈表第一個有效節(jié)點

132 p－＞pNext ＝ NULL；

133 ｝

134 else

135 ｛

136 ／／ 原鏈表的非第1個有效節(jié)點

137 p－＞pNext ＝ pH－＞pNext；

138 ｝

139 pH－＞pNext ＝ p；

140 ／／p ＝ p－＞pNext； ／／ 這樣已經(jīng)不行了，因為p－＞pNext已經(jīng)被改過了

141 p ＝ pBack； ／／ 走到下一個節(jié)點

142｝

143／／ 循環(huán)結(jié)束后，最后一個節(jié)點仍然缺失

144insert＿head（pH， p）；

145｝

146int main（void）

147｛

148 ／／ 定義頭指針

149 ／／struct node ＊pHeader ＝ NULL；

150 ／／ 這樣直接insert＿tail會段錯誤。

151 struct node ＊pHeader ＝ create＿node（0）；

152 insert＿head（pHeader， create＿node（11））；

153 insert＿head（pHeader， create＿node（12））；

154 insert＿head（pHeader， create＿node（13））；

155 ／／ 訪問鏈表頭節(jié)點的有效數(shù)據(jù)

156 printf（＂beader node data： ％d．n＂， pHeader－＞data）；

157 bianli（pHeader）；

158reverse＿linkedlist（pHeader）；

159printf（＂－－－－－－－－－－－－－－－－－－逆序后－－－－－－－－－－－－－n＂）；

160bianli（pHeader）；

161 return 0；

162 ｝

編譯結(jié)果：

1root＠ubuntu－virtual－machine：／mnt／hgfs／day＃ gcc

2 flie1．c

3root＠ubuntu－virtual－machine：／mnt／hgfs／day＃

4．／a．out

5 beader node data： 3．

6 －－－－－－－－－－－開始遍歷－－－－－－－－－－－

7 node data： 13．

8 node data： 12．

9 node data： 11．

10 －－－－－－－－－－－－－完了－－－－－－－－－－－－－

11 －－－－－－－－－－－－－－－－－－逆序后－－－－－－－－－－－－－

12 －－－－－－－－－－－開始遍歷－－－－－－－－－－－

13 node data： 11．

14 node data： 12．

15 node data： 13．

16 －－－－－－－－－－－－－完了－－－－－－－－－－－－－

四、總結(jié)：

通過兩天的單鏈表學習，讓自己理解更加深刻，不過學的東西還是最后能夠用到實戰(zhàn)當中去，這樣才是最后的學習方法！

每天學一點，日積月累就有質(zhì)的提升！如果您覺得好，可以給關注哦，這是對我的最大鼓勵哦；我會繼續(xù)努力加油的