算法与数据结构——接口

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

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

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

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

程序清单3.26  查找尾结点

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

程序清单3.27  查找尾结点

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

图3.14  删除结点示意图

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

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

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

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

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

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

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

程序清单3.30  综合范例程序

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

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

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

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

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

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

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

程序清单3.32  综合程序范例

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