单向链表中的存值与存址、数据与p_next分离问题

假设存储在struct _student结构体学生记录中的数据就是用户数据，那么只要将存储学生记录的结构体变量的地址传递给链表结点的数据域就行了，即p-> 假设存储在struct _student结构体学生记录中的数据就是用户数据，那么只要将存储学生记录的结构体变量的地址传递给链表结点的数据域就行了，即p->data指向用户数据的结构体存储空间，详见图 3.9。如果void *指针指向的不是结构体或者字符串，而是int型之类的简单类型，那么只要在使用时进行强制类型转换即可。

图 3.9 data指向用户数据

如果为了使链表数据与学生记录结构体关联，则必须先定义一个学生记录，然后将链表结点中的void *指针指向该学生记录。与之前直接将学生结构体作为链表结点的数据成员的链表相比，每个结点都会多耗费一个void *指针的空间。虽然一个结点耗费的空间并不多，但如果结点很多，其浪费的内存还是相当可观的，特别是在一些内存资源本身就很紧张的嵌入式系统中。

显然，要想节省内存空间，则不能定义void *类型指针，必须将数据（比如，学生记录）和链表结点的p_next放在一起，但这样做则无法做到重用链表程序。

分析当前链表结点的定义，其主要包含两个部分：链表关心的p_next指针和用户关心的data数据。回顾如程序清单3.12所示的slist_add_tail()函数，没有出现任何访问data的代码，从而说明data与链表无关。既然如此，是否可以将它们分离呢？

>>> 3.2.2 数据与p_next分离

由于链表只关心p_next指针，因此完全没有必要在链表结点中定义数据域，那么只保留p_next指针就好了。链表结点的数据结构（slist.h）定义如下：

由于结点中没有任何数据，因此节省了内存空间，其示意图详见图3.10。

图3.10  链表示意图

当用户需要使用链表管理数据时，仅需关联数据和链表结点，最简单的方式是将数据和链表结点打包在一起。以int类型数据为例，首先将链表结点作为它的一个成员，再添加与用户相关的int类型数据，该结构体定义如下：

由此可见，无论是什么数据，链表结点只是用户数据记录的一个成员。当调用链表接口时，仅需将node的地址作为链表接口参数即可。在定义链表结点的数据结构时，由于仅删除了data成员，因此还是可以直接使用原来的slist_add_tail()函数，管理int型数据的范例程序详见程序清单3.14。

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

由于用户需要初始化head为NULL，且遍历时需要操作各个结点的p_next指针。而将数据和p_next分离的目的就是使各自的功能职责分离，链表只需要关心p_next的处理，用户只关心数据的处理。因此，对于用户来说，链表结点的定义就是一个"黑盒子"，只能通过链表提供的接口访问链表，不应该访问链表结点的具体成员。

为了完成头结点的初始赋值，应该提供一个初始化函数，其本质上就是将头结点中的p_next成员设置为NULL。链表初始化函数原型为：

由于头结点的类型与其它普通结点的类型一样，因此很容易让用户误以为，这是初始化所有结点的函数。实际上，头结点与普通结点的含义是不一样的，由于只要获取头结点就可以遍历整个链表，因此头结点往往是被链表的拥有者持有，而普通结点仅仅代表单一的一个结点。为了避免用户将头结点和其它结点混淆，需要再定义一个头结点类型（slist.h）：

基于此，将链表初始化函数原型（slist.h）修改为：

其中，p_head指向待初始化的链表头结点，slist_init()函数的实现详见程序清单3.15。

程序清单3.15  链表初始化函数

在向链表添加结点前，需要初始化头结点。即：

由于重新定义了头结点的类型，因此添加结点的函数原型也应该进行相应的修改。即：

其中，p_head指向链表头结点，p_node为新增的结点，slist_add_tail()函数的实现详见程序清单3.16。

程序清单3.16  新增结点范例程序

同理，当前链表的遍历采用的还是直接访问结点成员的方式，其核心代码如下：

这里主要对链表作了三个操作：（1）得到第一个用户结点；（2）得到当前结点的下一个结点；（3）判断链表是否结束，与结束标记（NULL）比较。

基于此，将分别提供三个对应的接口来实现这些功能，避免用户直接访问结点成员。它们的函数原型为（slist.h）：

其实现代码详见程序清单3.17。

程序清单3.17  遍历相关函数实现

程序中获取的第一个用户结点，其实质上就是头结点的下一个结点，因此可以直接调用slist_next_get()实现。尽管slist_next_get()在实现时并没有用到参数p_head，但还是将p_head参数传进来了，因为实现其它的功能时将会用到p_head参数，比如，判断p_pos是否在链表中。当有了