侵权投诉
订阅
纠错
加入自媒体

超详细的单链表学习(二)

2020-07-24 14:14
TXP嵌入式
关注

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

一、单链表的遍历

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

四、总结:

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

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

声明: 本文由入驻维科号的作者撰写,观点仅代表作者本人,不代表OFweek立场。如有侵权或其他问题,请联系举报。

发表评论

0条评论,0人参与

请输入评论内容...

请输入评论/评论长度6~500个字

您提交的评论过于频繁,请输入验证码继续

暂无评论

暂无评论

文章纠错
x
*文字标题:
*纠错内容:
联系邮箱:
*验 证 码:

粤公网安备 44030502002758号