单链表学习的超详细说明（二）

昨天跟大家分享了单链表的一些基本用法，今天接着继续和大家分享单链表的用法，今天分享完，单链表的操作就暂告一段落了，后面接着分享双链表的学习和实战！

一、单链表的遍历：

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

四、总结：

通过两天的单链表学习，让自己理解更加深刻，不过学的东西还是最后能够用到实战当中去，这样才是最后的学习方法！

每天学一点，日积月累就有质的提升！如果您觉得好，可以给关注哦，这是对我的最大鼓励哦；我会继续努力加油的