算法与数据结构——接口

周立功教授数年之心血之作《程序设计与数据结构》以及《面向AMetal框架与接口的编程（上）》，书本内容公开后，在电子行业掀起一片学习热潮。经周立功教授授权，本公众号特对《程序设计与数据结构》一书内容进行连载，愿共勉之。

第三章为算法与数据结构，本文为3.2.3 接口。

>>> 3.2.3 接口

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

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

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

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

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

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

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

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

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

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

将node3添加到链表头部，查看修改后的最终输出结果发生了什么变化？

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

其中，p_head指向链表头结点，p_pos指向的结点表明查找结点的位置，返回值即为p_pos指向结点的