单项链接的接口问题

UtFs_Zlgmcu7890 2017-09-26 4720

电子说

1.3w人已加入

描述

近日周立功教授公开了数年的心血之作《程序设计与数据结构》，电子版已无偿性分享到电子工程师与高校群体下载，经周立功教授授权，特对本书内容进行连载。

>>>>1.1.1 接口

在实际使用中，仅有添加到链表尾部、遍历链表这些接口函数是不够的。如在结点添加函数中，当前只是按照人们的习惯，将结点添加到链表尾部，使后添加的结点处在先添加的结点后面。而在编写函数时知道，将一个结点添加至尾部的实现过程，需要修改原链表尾结点中p_next值，将其从NULL修改为指向新结点的指针。

虽然操作简单，但执行该操作的前提是要找到添加结点前链表的尾结点，则需要从指向头结点的p_head指针开始，依次遍历每个结点，直到找到结点中p_next值为NULL（尾结点）时为止。可想而知，添加一个结点的效率将随着链表长度的增加逐渐降低，如果链表很长，则效率将变得十分低下，因为每次添加结点前都要遍历一次链表。

既然将结点添加到链表尾部会由于需要寻找尾结点而导致效率低下，何不换个思路，将结点添加到链表头部。由于链表存在一个p_head指针指向头结点，头结点可以拿来就用，根本不要寻找，则效率将大大提高。将一个结点添加至链表头部时，链表的变化详见图 3.11。

周立功

图 3.11添加一个结点至链表头部

在其实现过程中，需要完成两个指针的修改：（1）修改新结点中的p_next，使其指向头结点中p_next指向的结点；（2）修改头结点的p_next，使其指向新的结点。

与添加结点至链表尾部的过程进行对比发现，其不再需要寻找尾结点的过程，无论链表多长，都可以通过这两步完成结点的添加。加结点到链表头部的函数原型（slist.h）为：

int slist_add_head (slist_head_t *p_head, slist_node_t *p_node);

其中，p_head指向链表头结点，p_node为待添加的结点，其实现详见程序清单3.21。

程序清单3.21 新增结点至链表头部的范例程序

1 int slist_add_head (slist_head_t *p_head, slist_node_t *p_node)

2 {

3 p_node->p_next = p_head->p_next;

4 p_head->p_next = p_node;

5 return 0;

6 }

由此可见，插入结点至链表头部的程序非常简单，无需查找且效率高，因此在实际使用时，若对位置没有要求，则优先选择将结点添加至链表头部。

修改程序清单3.20中的一行代码作为测试，比如，将第26行改为：

26 slist_add_head(&head, &(node3.node));

既然可以将结点添加至头部和尾部，何不更加灵活一点，提供一个将结点至任意位置的接口函数呢？当结点添加至p_pos指向的结点之后，则链表的变化详见图 3.12。

周立功

图 3.12 添加结点至任意位置示意图

在其实现过程中，需要修改两个指针：（1）修改新结点中的p_next，使其指向p_pos指向结点的下一个结点；（2）修改p_pos指向结点的p_next，使其指向新结点。通过这两步即可添加结点，添加结点至链表任意位置的函数原型（slist.h）为：

int slist_add (slist_head_t *p_head, slist_node_t *p_pos, slist_node_t *p_node);

其中，p_head指向链表头结点，p_node指向待添加的结点，p_pos指向的结点表明新结点添加的位置，新结点即添加在p_pos指向的结点后面，其实现详见程序清单3.22。

程序清单3.22 新增结点至链表任意位置的范例程序

1 int slist_add (slist_head_t *p_head, slist_node_t *p_pos, slist_node_t *p_node)

2 {

3 p_node->p_next = p_pos->p_next;

4 p_pos->p_next = p_node;

5 return 0;

6 }

尽管此函数在实现时没有用到参数p_head，但还是将p_head参数传进来了，因为实现其它功能时将会用到p_head参数，比如，判断p_pos是否在链表中。

通过前面的介绍已经知道，直接将结点添加至链表尾部的效率很低，有了该新增结点至任意位置的函数后，如果每次都将结点添加到上一次添加的结点后面，同样可以实现将结点添加至链表尾部。详见程序清单3.23。

程序清单3.23 管理int型数据的范例程序

1 #include

2 #include "slist.h"

4 typedef struct _slist_int{

5 slist_node_t node; // 包含链表结点

6 int data; // int类型数据

7 } slist_int_t;

9 int list_node_process (void *p_arg, slist_node_t *p_node)

10 {

11 printf("%d ", ((slist_int_t *)p_node)->data);

12 return 0;

13 }

15 int main (void)

16 {

17 slist_node_t head;

18 slist_int_t node1, node2, node3;

19 slist_init(&head);

20 node1.data = 1;

21 slist_add(&head, &head, &node1.node); // 添加 node1 至头结点之后

22 node2.data = 2;

23 slist_add(&head, &node1.node, &node2.node); // 添加 node2至node1之后

24 node3.data = 3;

25 slist_add(&head, &node2.node, &node3.node); // 添加 node3至node2之后

26 slist_foreach(&head, list_node_process, NULL); // 遍历链表，用户参数为NULL

27 return 0;

28 }

显然，添加结点至链表头部和尾部，仅仅是添加结点至任意位置的特殊情况：

● 添加结点至链表头部，即添加结点至头结点之后；

● 添加结点至链表尾部，即添加结点至链表尾结点之后。

slist_add_head()函数和slist_add_tail()函数的实现详见程序清单3.24。

程序清单3.24 基于slist_add()实现添加结点至头部和尾部

1 int slist_add_tail (slist_head_t *p_head, slist_node_t *p_node)

2 {

3 slist_node_t *p_tmp = p_head; // 指向头结点

4 while (p_tmp->p_next != NULL) { // 找到链表尾结点（直到结点的p_next的值为NULL）

5 p_tmp = p_tmp->p_next;

6 }

7 return slist_add(p_head, p_tmp, p_node); // 添加结点至尾结点之后

8 }

10 int slist_add_head (slist_head_t *p_head, slist_node_t *p_node)

11 {

12 return slist_add(p_head, p_head, p_node); // 添加结点至头结点之后

13 }

如果要将一个结点添加至某一结点之前呢？实际上，添加结点至某一结点之前同样也只是添加结点至某一结点之后的一种变形，即添加至该结点前一个结点的后面，详见图3.13。

周立功

图3.13 添加结点至任意位置前示意图

显然，只要获得某一结点的前驱，即可使用slist_add()函数添加结点至某一结点前面。为此，需要提供一个获得某一结点前驱的函数，其函数原型（slist.h）为：

slist_node_t *slist_prev_get (slist_head_t *p_head, slist_node_t *p_pos);

其中，p_head指向链表头结点，p_pos指向的结点表明查找结点的位置，返回值即为p_pos指向结点的前一个结点。由于在单向链表的结点中没有指向其上一个结点的指针，因此，只有从头结点开始遍历链表，当某一结点的p_next指向当前结点时，表明其为当前结点的上一个结点，函数实现详见程序清单3.25。

程序清单3.25 获取某一结点前驱的范例程序

1 slist_node_t *slist_prev_get (slist_head_t *p_head, slist_node_t *p_pos)

2 {

3 slist_node_t *p_tmp = p_head; // 指向头结点

4 while ((p_tmp != NULL) && (p_tmp->p_next != p_pos)) { // 找到p_pos指向的结点

5 p_tmp = p_tmp->p_next;

6 }

7 return p_tmp;

8 }

由此可见，若p_pos的值为NULL，则当某一结点的p_next为NULL时就会返回，此时返回的结点实际上就是尾结点。为了便于用户理解，可以简单封装一个查找尾结点的函数，其函数原型为：

slist_node_t *slist_tail_get (slist_head_t *p_head) ;

其函数实现详见程序清单3.26。

程序清单3.26 查找尾结点

1 slist_node_t *slist_tail_get (slist_head_t *p_head)

2 {

3 return slist_prev_get(p_head, NULL);

4 }

由于可以直接通过该函数得到尾结点，因此当需要将结添加点至链表尾部时，也就无需再自行查找尾结点了，修改slist_add_tail()函数的实现详见程序清单3.27。

程序清单3.27 查找尾结点

1 int slist_add_tail (slist_head_t *p_head, slist_node_t *p_node)

2 {

3 slist_node_t *p_tmp = slist_tail_get(p_head); // 找到尾结点

4 return slist_add(p_head, p_tmp, p_node); // 添加结点至尾结点之后

5 }

与添加一个结点对应，也可以从链表中删除某一结点。假定链表中已经存在3个结点，现在要删除中间的结点，则删除前后的链表变化详见图3.14。

周立功

图3.14 删除结点示意图

显然，删除一个结点也需要修改两个指针的值：既要修改其上一个结点的p_next，使其指向待删除结点的下一个结点，还要将删除结点的p_next设置为NULL。

删除结点的函数原型（slist.h）为：

int slist_del (slist_head_t *p_head, slist_node_t *p_node);

其中，p_head指向链表头结点，p_node为待删除的结点，slist_del()函数的实现详见程序清单3.28。

程序清单3.28 删除结点范例程序

1 int slist_del (slist_head_t *p_head, slist_node_t *p_node)

2 {

3 slist_node_t *p_prev = slist_prev_get(p_head, p_node);// 找到待删除结点的上一个结点

4 if (p_prev) {

5 p_prev->p_next = p_node->p_next;

6 p_node->p_next = NULL;

7 return 0;

8 }

9 return -1;

10 }

为便于查阅，如程序清单3.29所示展示了slist.h文件的内容。

程序清单3.29 slist.h文件内容

1 #pragma once

3 typedef struct _slist_node {

4 struct _slist_node *p_next; // 指向下一个结点的指针

5 } slist_node_t;

7 typedef slist_node_t slist_head_t; // 头结点类型定义

8 typedef int (*slist_node_process_t) (void *p_arg, slist_node_t *p_node); // 遍历链表的回调函数类型

10 int slist_init (slist_head_t *p_head); // 链表初始化

12 int slist_add (slist_head_t *p_head, slist_node_t *p_pos, slist_node_t *p_node); // 添加一个结点

13 int slist_add_tail (slist_head_t *p_head, slist_node_t *p_node); // 添加一个结点至链表尾部

14 int slist_add_head (slist_head_t *p_head, slist_node_t *p_node); // 添加一个结点至链表头部

15 int slist_del (slist_head_t *p_head, slist_node_t *p_node); // 删除一个结点

17 slist_node_t *slist_prev_get (slist_head_t *p_head, slist_node_t *p_pos); // 寻找某一结点的前一结点

18 slist_node_t *slist_next_get (slist_head_t *p_head, slist_node_t *p_pos); // 寻找某一结点的后一结点

19 slist_node_t *slist_tail_get (slist_head_t *p_head); // 获取尾结点

20 slist_node_t *slist_begin_get (slist_head_t *p_head); // 获取开始位置，第一个用户结点

21 slist_node_t *slist_end_get (slist_head_t *p_head); // 获取结束位置，尾结点下一个结点的位置

23 int slist_foreach(slist_head_t *p_head, // 遍历链表

24 slist_node_process_t pfn_node_process,

25 void *p_arg);

综合范例程序详见程序清单3.30。

程序清单3.30 综合范例程序

1 #include

2 #include "slist.h"

4 typedef struct _slist_int {

5 slist_node_t node; // 包含链表结点

6 int data; // int类型数据

7 }slist_int_t;

9 int list_node_process (void *p_arg, slist_node_t *p_node)

10 {

11 printf("%d ", ((slist_int_t *)p_node)->data);

12 return 0;

13 }

15 int main(void)

16 {

17 slist_head_t head; // 定义链表头结点

18 slist_int_t nodel, node2, node3;

19 slist_init(&head);

21 node1.data = 1;

22 slist_add_tail(&head, &(node1.node));

23 node2.data = 2;

24 slist_add_tail(&head, &(node2.node));

25 node3.data = 3;

26 slist_add_head(&head, &(node3.node));

27 slist_del(&head, &(node2.node)); // 删除node2结点

28 slist_foreach(&head, list_node_process, NULL); // 遍历链表，用户参数为NULL

29 return 0;

30 }

程序中所有的结点都是按照静态内存分配的方式定义的，即程序在运行前，各个结点占用的内存就已经被分配好了，而不同的是动态内存分配需要在运行时使用malloc()等函数完成内存的分配。

由于静态内存不会出现内存泄漏，且在编译完成后，各个结点的内存就已经分配好了，不需要再花时间去分配内存，也不需要添加额外的对内存分配失败的处理代码。因此，在嵌入式系统中，往往多使用静态内存分配的方式。但其致命的缺点是不能释放内存，有时候用户希望在删除链表的结点时，释放掉其占用内存，这就需要使用动态内存分配。

实际上，链表的核心代码只是负责完成链表的操作，仅需传递结点的地址（p_node）即可，链表程序并不关心结点的内存从何而来。基于此，若要实现动态内存分配，只要在应用中使用malloc()等动态内存分配函数即可，详见程序清单3.31。

程序清单3.31 综合范例程序（使用动态内存）

1 #include

2 #include "slist.h"

3 #include

5 typedef struct _slist_int{

6 slist_node_t node; // 包含链表结点

7 int data; // int类型数据

8 } slist_int_t;

10 int list_node_process(void *p_arg, slist_node_t *p_node)

11 {

12 printf("%d ", ((slist_int_t *)p_node)->data);

13 return 0;

14 }

16 int my_list_add(slist_head_t *p_head, int data) // 插入一个数据

17 {

18 slist_int_t *p_node = (slist_int_t *)malloc(sizeof(slist_int_t));

19 if (p_node == NULL) {

20 printf("The malloc memory failed!");

21 return -1;

22 }

23 p_node->data = data;

24 slist_add_head(p_head, &(p_node->node)); // 将结点加入链表中

25 return 0;

26 }

28 int my_list_del (slist_head_t *p_head, int data) // 删除一条数据

29 {

30 slist_node_t *p_node = slist_begin_get(p_head);

31 slist_node_t *p_end = slist_end_get(p_head);

32 while (p_node != p_end){

33 if (((slist_int_t *)p_node)->data == data){

34 printf(" delete the data %d :", data);

35 slist_del(p_head, p_node); // 删除结点

36 free(p_node);

37 break;

38 }

39 p_node = slist_next_get(p_head, p_node);

40 }

41 slist_foreach(p_head, list_node_process, NULL); // 删除结点后，再打印出所有结点的数据信息

42 return 0;

43 }

45 int main(void)

46 {

47 slist_head_t *p_head = (slist_head_t *)malloc(sizeof(slist_head_t));

48 slist_init(p_head);

50 my_list_add(p_head, 1);

51 my_list_add(p_head, 2);

52 my_list_add(p_head, 3);

53 slist_foreach(p_head, list_node_process, NULL); // 打印出所有结点的数据信息

54 my_list_del(p_head, 1);

55 my_list_del(p_head, 2);

56 my_list_del(p_head, 3);

57 free(p_head);

58 return 0;

59 }

如果按照int型数据的示例，使用链表管理学生记录，则需要在学生记录中添加一个链表结点数据。比如：

typedef struct _student{

slist_node_t node; // 包含链表结点

char name[10]; // 姓名为字符串

char sex; // 性别为字符型

float height, weight; // 身高、体重为实型

}student_t;

虽然这样定义使得学生信息可以使用链表来管理，但却存在一个很严重的问题，因为修改了学生记录类型的定义，就会影响所有使用该记录结构体类型的程序模块。在实际的应用上，学生记录可以用链表管理，也可以用数组管理，当使用数组管理时，则又要重新修改学生记录的类型。而node仅仅是链表的结点，与学生记录没有任何关系。不能将node直接放在学生记录结构体中，应该使它们分离。基于此，需要定义一个新的结构体类型，将学生记录和node关联起来，使得可以用链表来管理学生记录。比如：

typedef struct _slist_student{

slist_node_t node; // 包含链表结点

student_t student; // 学生记录

}slist_student_t;

使用范例详见程序清单3.32。

程序清单3.32 综合程序范例

1 #include

2 #include "slist.h"

3 #include

5 typedef struct _student{

6 char name[10]; // 姓名为字符串

7 char sex; // 性别为字符型

8 float height, weight; // 身高、体重为实型

9 }student_t;

11 typedef struct _slist_student{

12 slist_node_t node; // 包含链表结点

13 student_t student; // 学生记录

14 }slist_student_t;

16 int student_info_read (student_t *p_student) // 读取学生记录，随机产生，仅供测试

17 {

18 int i;

20 for (i = 0; i < 9; i++) { // 随机名字，由 'a' ~ 'z' 组成

21 p_student->name[i] = (rand() % ('z' - 'a')) + 'a';

22 }

23 p_student->name[i]= ''; // 字符串结束符

24 p_student->sex = (rand() & 0x01) ? 'F' : 'M'; // 随机性别

25 p_student->height = (float)rand() / rand();

26 p_student->weight = (float)rand() / rand();

27 return 0;

28 }

30 int list_node_process (void *p_arg, slist_node_t *p_node)

31 {

32 student_t *p_s = &(((slist_student_t *)p_node)->student);

33 printf("%s : %c %.2f %.2f ", p_s->name, p_s->sex, p_s->height, p_s->weight);

34 return 0;

35 }

37 int main(int argc, char *argv[])

38 {

39 slist_head_t head;

40 slist_student_t s1, s2, s3, s4, s5;

41 srand(time(NULL));

42 slist_init(&head);

44 student_info_read(&s1.student);

45 student_info_read(&s2.student);

46 student_info_read(&s3.student);

47 student_info_read(&s4.student);

48 student_info_read(&s5.student);

50 slist_add_head(&head, &s1.node);

51 slist_add_head(&head, &s2.node);

52 slist_add_head(&head, &s3.node);

53 slist_add_head(&head, &s4.node);

54 slist_add_head(&head, &s5.node);

56 slist_foreach(&head, list_node_process, NULL); // 遍历链表，用户参数为NULL

57 return 0;

58 }

综上所述，虽然链表比数组更灵活，很容易在链表中插入和删除结点，但也失去了数组的“随机访问”能力。如果结点距离链表的开始处很近，那么访问它就会很快；如果结点靠近链表的结尾处，则访问它就会很慢。但单向链表也存在不能“回溯”的缺点，即在向链表中插入结点时，必须知道插入结点前面的结点；从链表中删除结点时，必须知道被删除结点前面的结点；很难逆向遍历链表。如果是双向链表，就可以解决这些问题。

在公众号后台回复关键字“程序设计”，即可在线阅读《程序设计与数据结构》；回复关键字“编程”，即可在线阅读《面向AMetal框架与接口的编程（上）》。

打开APP阅读更多精彩内容