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

一、單鏈表的遍歷：

1、什么叫遍歷？

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

2、如何來遍歷單鏈表？

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

3、注意事項：

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

4、實戰代碼演示：

1 ＃include ＜stdio．h＞

2 ＃include ＜strings．h＞

3 ＃include ＜stdlib．h＞

4／／ 構建一個鏈表的節點

5struct node

6 ｛

7 int data； ／／ 有效數據

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

9 ｝；

10 ／／ 作用：創建一個鏈表節點

11 ／／ 返回值：指針，指針指向我們本函數新創建的一個節點的首地址

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 ／／ 清理申請到的堆內存

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

22 ／／ 填充節點

23 p－＞data ＝ data；

24 p－＞pNext ＝ NULL；

25 return p；

26｝

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

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

29｛

30 int cnt ＝ 0；

31 ／／ 分兩步來完成插入

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

33 struct node ＊p ＝ pH；

34 while （NULL ！＝ p－＞pNext）

35 ｛

36 p ＝ p－＞pNext； ／／ 往后走一個節點

37 cnt＋＋；

38 ｝

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

40 p－＞pNext ＝ new；

41 pH－＞data ＝ cnt ＋ 1；

42 ｝

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

44 ｛

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

46 new－＞pNext ＝ pH－＞pNext；

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

48 pH－＞pNext ＝ new；

49 ／／ 第3步： 頭節點中的計數要加1

50 pH－＞data ＋＝ 1；

51 ｝

52 ／／ 遍歷單鏈表，pH為指向單鏈表的頭指針，遍歷的節點數據打印出來

53 void bianli（struct node＊pH）

54 ｛

55 ／／pH－＞data ／／ 頭節點數據，不是鏈表的常規數據，不要算進去了

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

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

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

59 ／／ 是不是最后一個節點

60 while （NULL ！＝ p－＞pNext）

61 ｛

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

63 p ＝ p－＞pNext；

64 ／／ 走到下一個節點，也就是循環增量

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 ／／ 訪問鏈表頭節點的有效數據

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

80 bianli（pHeader）；

81 return 0；

82 ｝

編譯結果；

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、如何找到要刪除的節點？

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

2、如何來刪除一個節點？

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

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

3、實戰代碼演示：

1 ＃include ＜stdio．h＞

2 ＃include ＜strings．h＞

3 ＃include ＜stdlib．h＞

4／／ 構建一個鏈表的節點

5struct node

6 ｛

7 int data； ／／ 有效數據

8 struct node ＊pNext；

9 ／／ 指向下一個節點的指針

10 ｝；

11 ／／ 作用：創建一個鏈表節點

12 ／／ 返回值：指針，指針指向我們本函數新創建的一個節點的首地址

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 ／／ 清理申請到的堆內存

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

23 ／／ 填充節點

24 p－＞data ＝ data；

25 p－＞pNext ＝ NULL；

26 return p；

27｝

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

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

30｛

31 int cnt ＝ 0；

32 ／／ 分兩步來完成插入

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

34 struct node ＊p ＝ pH；

35 while （NULL ！＝ p－＞pNext）

36 ｛

37 p ＝ p－＞pNext； ／／ 往后走一個節點

38 cnt＋＋；

39 ｝

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

41 p－＞pNext ＝ new；

42 pH－＞data ＝ cnt ＋ 1；

43 ｝

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

45 ｛

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

47 new－＞pNext ＝ pH－＞pNext；

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

49 pH－＞pNext ＝ new；

50 ／／ 第3步： 頭節點中的計數要加1

51 pH－＞data ＋＝ 1；

52 ｝

53 ／／ 遍歷單鏈表，pH為指向單鏈表的頭指針，遍歷的節點數據打印出來

54 void bianli（struct node＊pH）

55 ｛

56 ／／pH－＞data ／／ 頭節點數據，不是鏈表的常規數據，不要算進去了

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

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

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

60 ／／ 是不是最后一個節點

61 while （NULL ！＝ p－＞pNext）

62 ｛

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

64 p ＝ p－＞pNext；

65 ／／ 走到下一個節點，也就是循環增量

66 ｝

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

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

69 ｝

70 ／／ 從鏈表pH中刪除節點，待刪除的節點的特征是數據區等于data

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

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

73 ｛

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

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

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

77while （NULL ！＝ p－＞pNext）／／ 是不是最后一個節點

78｛

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

80 p ＝ p－＞pNext； ／／ 走到下一個節點，也就是循環增量

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

82 if （p－＞data ＝＝ data）

83 ｛

84 ／／ 找到了節點，處理這個節點

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

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

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

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

89 ／／ 一個指針指向當前節點的前一個節點

90 if （NULL ＝＝ p－＞pNext）

91 ｛

92 ／／ 尾節點

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

94 free（p）； ／／ 釋放原來的尾節點的內存

95 ｝

96 else

97 ｛

98 ／／ 普通節點

99 pPrev－＞pNext ＝ p－＞pNext；

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

101 free（p）；

102 ｝

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

104 return 0；

105 ｝

106｝

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

108printf（＂沒找到這個節點．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 ／／ 訪問鏈表頭節點的有效數據

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

122 bianli（pHeader）；

123delete＿node（pHeader， 12）；

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

125bianli（pHeader）；

126 return 0；

127 ｝

編譯結果：

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、什么叫鏈表的逆序？

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

2、怎樣實現鏈表的逆序？

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

3、實戰代碼演示：

1 ＃include ＜stdio．h＞

2 ＃include ＜strings．h＞

3 ＃include ＜stdlib．h＞

4／／ 構建一個鏈表的節點

5struct node

6 ｛

7 int data；

8 ／／ 有效數據

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

10 ｝；

11 ／／ 作用：創建一個鏈表節點

12 ／／ 返回值：指針，指針指向我們本函數新創建的一個節點的首地址

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 ／／ 清理申請到的堆內存

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

24 ／／ 填充節點

25 p－＞data ＝ data；

26 p－＞pNext ＝ NULL；

27 return p；

28｝

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

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

31｛

32 int cnt ＝ 0；

33 ／／ 分兩步來完成插入

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

35 struct node ＊p ＝ pH；

36 while （NULL ！＝ p－＞pNext）

37 ｛

38 p ＝ p－＞pNext； ／／ 往后走一個節點

39 cnt＋＋；

40 ｝

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

42 p－＞pNext ＝ new；

43 pH－＞data ＝ cnt ＋ 1；

44 ｝

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

46 ｛

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

48 new－＞pNext ＝ pH－＞pNext；

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

50 pH－＞pNext ＝ new；

51 ／／ 第3步： 頭節點中的計數要加1

52 pH－＞data ＋＝ 1；

53 ｝

54 ／／ 遍歷單鏈表，pH為指向單鏈表的頭指針，遍歷的節點數據打印出來

55 void bianli（struct node＊pH）

56 ｛

57 ／／pH－＞data ／／ 頭節點數據，不是鏈表的常規數據，不要算進去了

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

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

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

61 ／／ 是不是最后一個節點

62 while （NULL ！＝ p－＞pNext）

63 ｛

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

65 p ＝ p－＞pNext；

66 ／／ 走到下一個節點，也就是循環增量

67 ｝

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

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

70 ｝

71 ／／ 從鏈表pH中刪除節點，待刪除的節點的特征是數據區等于data

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

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

74｛

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

76struct node ＊p ＝ pH；

77 ／／ 用來指向當前節點

78struct node ＊pPrev ＝ NULL；

79／／ 用來指向當前節點的前一個節點

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

81｛

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

83 p ＝ p－＞pNext； ／／ 走到下一個節點，也就是循環增量

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

85 if （p－＞data ＝＝ data）

86 ｛

87 ／／ 找到了節點，處理這個節點

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

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

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

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

92 ／／ 一個指針指向當前節點的前一個節點

93 if （NULL ＝＝ p－＞pNext）

94 ｛

95 ／／ 尾節點

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

97 free（p）； ／／ 釋放原來的尾節點的內存

98 ｝

99 else

100 ｛

101 ／／ 普通節點

102 pPrev－＞pNext ＝ p－＞pNext；

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

104 free（p）；

105 ｝

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

107 return 0；

108 ｝

109｝

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

111printf（＂沒找到這個節點．n＂）；

112return －1；

113｝

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

115 void reverse＿linkedlist（struct node ＊pH）

116 ｛

117struct node ＊p ＝ pH－＞pNext；

118 ／／ pH指向頭節點，p指向第1個有效節點

119struct node ＊pBack；

120 ／／ 保存當前節點的后一個節點地址

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

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

123 return；

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

125while （NULL ！＝ p－＞pNext） ／／ 是不是最后一個節點

126｛

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

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

129 if （p ＝＝ pH－＞pNext）

130 ｛

131 ／／ 原鏈表第一個有效節點

132 p－＞pNext ＝ NULL；

133 ｝

134 else

135 ｛

136 ／／ 原鏈表的非第1個有效節點

137 p－＞pNext ＝ pH－＞pNext；

138 ｝

139 pH－＞pNext ＝ p；

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

141 p ＝ pBack； ／／ 走到下一個節點

142｝

143／／ 循環結束后，最后一個節點仍然缺失

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 ／／ 訪問鏈表頭節點的有效數據

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

157 bianli（pHeader）；

158reverse＿linkedlist（pHeader）；

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

160bianli（pHeader）；

161 return 0；

162 ｝

編譯結果：

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 －－－－－－－－－－－－－完了－－－－－－－－－－－－－

四、總結：

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

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