单项链接的接口问题

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

>>>>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;

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

修改程序清单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;

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

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

程序清单3.23  管理int型数