單鏈表學(xué)習(xí)的超詳細(xì)說(shuō)明（二）

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

一、單鏈表的遍歷：

1、什么叫遍歷？

遍歷就是把單鏈表中的各個(gè)節(jié)點(diǎn)挨個(gè)拿出來(lái)，就叫遍歷。

2、如何來(lái)遍歷單鏈表？

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

3、注意事項(xiàng)：

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

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

1 ＃include ＜stdio．h＞

2 ＃include ＜strings．h＞

3 ＃include ＜stdlib．h＞

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

5struct node

6 ｛

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

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

9 ｝；

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

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

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 ／／ 清理申請(qǐng)到的堆內(nèi)存

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

22 ／／ 填充節(jié)點(diǎn)

23 p－＞data ＝ data；

24 p－＞pNext ＝ NULL；

25 return p；

26｝

27／／ 計(jì)算添加了新的節(jié)點(diǎn)后總共有多少個(gè)節(jié)點(diǎn)，然后把這個(gè)數(shù)寫(xiě)進(jìn)頭節(jié)點(diǎn)中。

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

29｛

30 int cnt ＝ 0；

31 ／／ 分兩步來(lái)完成插入

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

33 struct node ＊p ＝ pH；

34 while （NULL ！＝ p－＞pNext）

35 ｛

36 p ＝ p－＞pNext； ／／ 往后走一個(gè)節(jié)點(diǎn)

37 cnt＋＋；

38 ｝

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

40 p－＞pNext ＝ new；

41 pH－＞data ＝ cnt ＋ 1；

42 ｝

43 void insert＿h(yuǎn)ead（struct node ＊pH， struct node ＊new）

44 ｛

45 ／／ 第1步： 新節(jié)點(diǎn)的next指向原來(lái)的第一個(gè)節(jié)點(diǎn)

46 new－＞pNext ＝ pH－＞pNext；

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

48 pH－＞pNext ＝ new；

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

50 pH－＞data ＋＝ 1；

51 ｝

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

53 void bianli（struct node＊pH）

54 ｛

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

56 ／／struct node ＊p ＝ pH； ／／ 錯(cuò)誤，因?yàn)轭^指針后面是頭節(jié)點(diǎn)

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

58 printf（＂－－－－－－－－－－－開(kāi)始遍歷－－－－－－－－－－－n＂）；

59 ／／ 是不是最后一個(gè)節(jié)點(diǎn)

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

61 ｛

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

63 p ＝ p－＞pNext；

64 ／／ 走到下一個(gè)節(jié)點(diǎn)，也就是循環(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會(huì)段錯(cuò)誤。

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

75 insert＿h(yuǎn)ead（pHeader， create＿node（11））；

76 insert＿h(yuǎn)ead（pHeader， create＿node（12））；

77 insert＿h(yuǎn)ead（pHeader， create＿node（13））；

78 ／／ 訪問(wèn)鏈表頭節(jié)點(diǎn)的有效數(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－－－－－－－－－－開(kāi)始遍歷－－－－－－－－－－－

5node data： 13．

6node data： 12．

7node data： 11．

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

二、單鏈表的刪除

1、如何找到要?jiǎng)h除的節(jié)點(diǎn)？

通過(guò)遍歷來(lái)查找節(jié)點(diǎn)。從頭指針＋頭節(jié)點(diǎn)開(kāi)始，順著鏈表依次將各個(gè)節(jié)點(diǎn)拿出來(lái)，按照一定的方法比對(duì)，找到我們要?jiǎng)h除的那個(gè)節(jié)點(diǎn)。

2、如何來(lái)刪除一個(gè)節(jié)點(diǎn)？

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

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

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

1 ＃include ＜stdio．h＞

2 ＃include ＜strings．h＞

3 ＃include ＜stdlib．h＞

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

5struct node

6 ｛

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

8 struct node ＊pNext；

9 ／／ 指向下一個(gè)節(jié)點(diǎn)的指針

10 ｝；

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

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

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 ／／ 清理申請(qǐng)到的堆內(nèi)存

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

23 ／／ 填充節(jié)點(diǎn)

24 p－＞data ＝ data；

25 p－＞pNext ＝ NULL；

26 return p；

27｝

28／／ 計(jì)算添加了新的節(jié)點(diǎn)后總共有多少個(gè)節(jié)點(diǎn)，然后把這個(gè)數(shù)寫(xiě)進(jìn)頭節(jié)點(diǎn)中。

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

30｛

31 int cnt ＝ 0；

32 ／／ 分兩步來(lái)完成插入

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

34 struct node ＊p ＝ pH；

35 while （NULL ！＝ p－＞pNext）

36 ｛

37 p ＝ p－＞pNext； ／／ 往后走一個(gè)節(jié)點(diǎn)

38 cnt＋＋；

39 ｝

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

41 p－＞pNext ＝ new；

42 pH－＞data ＝ cnt ＋ 1；

43 ｝

44 void insert＿h(yuǎn)ead（struct node ＊pH， struct node ＊new）

45 ｛

46 ／／ 第1步： 新節(jié)點(diǎn)的next指向原來(lái)的第一個(gè)節(jié)點(diǎn)

47 new－＞pNext ＝ pH－＞pNext；

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

49 pH－＞pNext ＝ new；

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

51 pH－＞data ＋＝ 1；

52 ｝

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

54 void bianli（struct node＊pH）

55 ｛

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

57 ／／struct node ＊p ＝ pH； ／／ 錯(cuò)誤，因?yàn)轭^指針后面是頭節(jié)點(diǎn)

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

59 printf（＂－－－－－－－－－－－開(kāi)始遍歷－－－－－－－－－－－n＂）；

60 ／／ 是不是最后一個(gè)節(jié)點(diǎn)

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

62 ｛

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

64 p ＝ p－＞pNext；

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

66 ｝

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

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

69 ｝

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

71 ／／ 返回值：當(dāng)找到并且成功刪除了節(jié)點(diǎn)則返回0，當(dāng)未找到節(jié)點(diǎn)時(shí)返回－1

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

73 ｛

74／／ 找到這個(gè)待刪除的節(jié)點(diǎn)，通過(guò)遍歷鏈表來(lái)查找

75struct node ＊p ＝ pH； ／／ 用來(lái)指向當(dāng)前節(jié)點(diǎn)

76struct node ＊pPrev ＝ NULL；／／ 用來(lái)指向當(dāng)前節(jié)點(diǎn)的前一個(gè)點(diǎn)

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

78｛

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

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

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

82 if （p－＞data ＝＝ data）

83 ｛

84 ／／ 找到了節(jié)點(diǎn)，處理這個(gè)節(jié)點(diǎn)

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

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

87 ／／ 后p指向了這個(gè)節(jié)點(diǎn)，但是要?jiǎng)h除這個(gè)節(jié)點(diǎn)關(guān)鍵要操作前一個(gè)節(jié)點(diǎn)，但是這

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

89 ／／ 一個(gè)指針指向當(dāng)前節(jié)點(diǎn)的前一個(gè)節(jié)點(diǎn)

90 if （NULL ＝＝ p－＞pNext）

91 ｛

92 ／／ 尾節(jié)點(diǎn)

93 pPrev－＞pNext ＝ NULL； ／／ 原來(lái)尾節(jié)點(diǎn)的前一個(gè)節(jié)點(diǎn)變成新尾節(jié)點(diǎn)

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

95 ｝

96 else

97 ｛

98 ／／ 普通節(jié)點(diǎn)

99 pPrev－＞pNext ＝ p－＞pNext；

100／／ 要?jiǎng)h除的節(jié)點(diǎn)的前一個(gè)節(jié)點(diǎn)和它的后一個(gè)節(jié)點(diǎn)相連，這樣就把要?jiǎng)h除的節(jié)點(diǎn)給摘出來(lái)了

101 free（p）；

102 ｝

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

104 return 0；

105 ｝

106｝

107／／ 到這里還沒(méi)找到，說(shuō)明鏈表中沒(méi)有我們想要的節(jié)點(diǎn)

108printf（＂沒(méi)找到這個(gè)節(jié)點(diǎn)．n＂）；

109return －1；

110｝

111int main（void）

112｛

113 ／／ 定義頭指針

114 ／／struct node ＊pHeader ＝ NULL；

115 ／／ 這樣直接insert＿tail會(huì)段錯(cuò)誤。

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

117 insert＿h(yuǎn)ead（pHeader， create＿node（11））；

118 insert＿h(yuǎn)ead（pHeader， create＿node（12））；

119 insert＿h(yuǎn)ead（pHeader， create＿node（13））；

120 ／／ 訪問(wèn)鏈表頭節(jié)點(diǎn)的有效數(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－－－－－－－－－－－開(kāi)始遍歷－－－－－－－－－－－

5node data： 13．

6node data： 12．

7node data： 11．

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

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

10－－－－－－－－－－－開(kāi)始遍歷－－－－－－－－－－－

11node data： 13．

12node data： 11．

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

三、鏈表的逆序：

1、什么叫鏈表的逆序？

鏈表的逆序又叫反向，意思就是把鏈表中所有的有效節(jié)點(diǎn)在鏈表中的順序給反過(guò)來(lái)。

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

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

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

1 ＃include ＜stdio．h＞

2 ＃include ＜strings．h＞

3 ＃include ＜stdlib．h＞

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

5struct node

6 ｛

7 int data；

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

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

10 ｝；

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

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

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 ／／ 清理申請(qǐng)到的堆內(nèi)存

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

24 ／／ 填充節(jié)點(diǎn)

25 p－＞data ＝ data；

26 p－＞pNext ＝ NULL；

27 return p；

28｝

29／／ 計(jì)算添加了新的節(jié)點(diǎn)后總共有多少個(gè)節(jié)點(diǎn)，然后把這個(gè)數(shù)寫(xiě)進(jìn)頭節(jié)點(diǎn)中。

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

31｛

32 int cnt ＝ 0；

33 ／／ 分兩步來(lái)完成插入

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

35 struct node ＊p ＝ pH；

36 while （NULL ！＝ p－＞pNext）

37 ｛

38 p ＝ p－＞pNext； ／／ 往后走一個(gè)節(jié)點(diǎn)

39 cnt＋＋；

40 ｝

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

42 p－＞pNext ＝ new；

43 pH－＞data ＝ cnt ＋ 1；

44 ｝

45 void insert＿h(yuǎn)ead（struct node ＊pH， struct node ＊new）

46 ｛

47 ／／ 第1步： 新節(jié)點(diǎn)的next指向原來(lái)的第一個(gè)節(jié)點(diǎn)

48 new－＞pNext ＝ pH－＞pNext；

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

50 pH－＞pNext ＝ new；

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

52 pH－＞data ＋＝ 1；

53 ｝

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

55 void bianli（struct node＊pH）

56 ｛

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

58 ／／struct node ＊p ＝ pH； ／／ 錯(cuò)誤，因?yàn)轭^指針后面是頭節(jié)點(diǎn)

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

60 printf（＂－－－－－－－－－－－開(kāi)始遍歷－－－－－－－－－－－n＂）；

61 ／／ 是不是最后一個(gè)節(jié)點(diǎn)

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

63 ｛

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

65 p ＝ p－＞pNext；

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

67 ｝

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

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

70 ｝

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

72／／ 返回值：當(dāng)找到并且成功刪除了節(jié)點(diǎn)則返回0，當(dāng)未找到節(jié)點(diǎn)時(shí)返回－1

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

74｛

75／／ 找到這個(gè)待刪除的節(jié)點(diǎn)，通過(guò)遍歷鏈表來(lái)查找

76struct node ＊p ＝ pH；

77 ／／ 用來(lái)指向當(dāng)前節(jié)點(diǎn)

78struct node ＊pPrev ＝ NULL；

79／／ 用來(lái)指向當(dāng)前節(jié)點(diǎn)的前一個(gè)節(jié)點(diǎn)

80while （NULL ?。?p－＞pNext） ／／ 是不是最后一個(gè)節(jié)點(diǎn)

81｛

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

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

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

85 if （p－＞data ＝＝ data）

86 ｛

87 ／／ 找到了節(jié)點(diǎn)，處理這個(gè)節(jié)點(diǎn)

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

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

90 ／／ 后p指向了這個(gè)節(jié)點(diǎn)，但是要?jiǎng)h除這個(gè)節(jié)點(diǎn)關(guān)鍵要操作前一個(gè)節(jié)點(diǎn)，但是這

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

92 ／／ 一個(gè)指針指向當(dāng)前節(jié)點(diǎn)的前一個(gè)節(jié)點(diǎn)

93 if （NULL ＝＝ p－＞pNext）

94 ｛

95 ／／ 尾節(jié)點(diǎn)

96 pPrev－＞pNext ＝ NULL； ／／ 原來(lái)尾節(jié)點(diǎn)的前一個(gè)節(jié)點(diǎn)變成新尾節(jié)點(diǎn)

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

98 ｝

99 else

100 ｛

101 ／／ 普通節(jié)點(diǎn)

102 pPrev－＞pNext ＝ p－＞pNext；

103 ／／ 要?jiǎng)h除的節(jié)點(diǎn)的前一個(gè)節(jié)點(diǎn)和它的后一個(gè)節(jié)點(diǎn)相連，這樣就把要?jiǎng)h除的節(jié)點(diǎn)給摘出來(lái)了

104 free（p）；

105 ｝

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

107 return 0；

108 ｝

109｝

110／／ 到這里還沒(méi)找到，說(shuō)明鏈表中沒(méi)有我們想要的節(jié)點(diǎn)

111printf（＂沒(méi)找到這個(gè)節(jié)點(diǎn)．n＂）；

112return －1；

113｝

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

115 void reverse＿linkedlist（struct node ＊pH）

116 ｛

117struct node ＊p ＝ pH－＞pNext；

118 ／／ pH指向頭節(jié)點(diǎn)，p指向第1個(gè)有效節(jié)點(diǎn)

119struct node ＊pBack；

120 ／／ 保存當(dāng)前節(jié)點(diǎn)的后一個(gè)節(jié)點(diǎn)地址

121／／ 當(dāng)鏈表沒(méi)有有效節(jié)點(diǎn)或者只有一個(gè)有效節(jié)點(diǎn)時(shí)，逆序不用做任何操作

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

123 return；

124／／ 當(dāng)鏈表有2個(gè)及2個(gè)以上節(jié)點(diǎn)時(shí)才需要真正進(jìn)行逆序操作

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

126｛

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

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

129 if （p ＝＝ pH－＞pNext）

130 ｛

131 ／／ 原鏈表第一個(gè)有效節(jié)點(diǎn)

132 p－＞pNext ＝ NULL；

133 ｝

134 else

135 ｛

136 ／／ 原鏈表的非第1個(gè)有效節(jié)點(diǎn)

137 p－＞pNext ＝ pH－＞pNext；

138 ｝

139 pH－＞pNext ＝ p；

140 ／／p ＝ p－＞pNext； ／／ 這樣已經(jīng)不行了，因?yàn)閜－＞pNext已經(jīng)被改過(guò)了

141 p ＝ pBack； ／／ 走到下一個(gè)節(jié)點(diǎn)

142｝

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

144insert＿h(yuǎn)ead（pH， p）；

145｝

146int main（void）

147｛

148 ／／ 定義頭指針

149 ／／struct node ＊pHeader ＝ NULL；

150 ／／ 這樣直接insert＿tail會(huì)段錯(cuò)誤。

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

152 insert＿h(yuǎn)ead（pHeader， create＿node（11））；

153 insert＿h(yuǎn)ead（pHeader， create＿node（12））；

154 insert＿h(yuǎn)ead（pHeader， create＿node（13））；

155 ／／ 訪問(wèn)鏈表頭節(jié)點(diǎn)的有效數(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 －－－－－－－－－－－開(kāi)始遍歷－－－－－－－－－－－

7 node data： 13．

8 node data： 12．

9 node data： 11．

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

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

12 －－－－－－－－－－－開(kāi)始遍歷－－－－－－－－－－－

13 node data： 11．

14 node data： 12．

15 node data： 13．

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

四、總結(jié)：

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

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