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

序可以验证添加结点是否成功，首先初始化链表为空，接着传递p_head的地址，然后从头结点开始，依次访问各个结点。

程序清单3.9  添加结点范例程序（2）

当链表不为空时，假定已经存在一个值为data1的结点，再添加一个值为data2的结点，链表的变化详见图3.4。

图3.4  链表非空时新增结点

其实现的过程仅需要修改原链表尾结点p_next的值，使其从NULL指针变为指向新结点的指针，详见程序清单3.10。

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

现在可以在程序清单3.9的基础上，添加更多的结点作为测试程序，详见程序清单3.11。

程序清单3.11  添加结点范例程序（3）

通过该程序可以验证结点添加成功，但仔细观察程序清单3.10可以发现，新增一个结点时，需要判定当前链表是否为空，然后再根据实际情况作出相应的处理。产生条件判断的原因是链表可能为空，没有一个有效结点。如果链表初始时就存在一个结点head： 

由于这是一个实际的结点，不再是指向头结点的指针，因此链表不可能为空，链表示意图详见图 3.5。

 图 3.5 链表示意图

对于这种类型的链表，始终存在一个无需有效数据的头结点，对于空链表，其至少包含该头结点，空链表示意图详见图3.6。由于在初始化时不包含其它任何结点，因此p_next的值为NULL。

图3.6  空链表示意图

当需要添加一个新的结点时，则从头结点开始寻找尾结点。当找到尾结点时，则修改尾结点的p_next值，使其从NULL指针变为指向新结点的指针，详见程序清单3.12。

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

注意，这里的p_head始终指向存在的头结点，与程序清单3.6中的p_head意义不同，可以使用如程序清单3.13所示的测试程序对其进行测试，由于初始化时无后继结点，因此p_next域的值为NULL。

程序清单3.13  添加结点范例程序（4）

虽然如程序清单3.12所示的程序不再使用判断语句，但又带来了新的问题，头结点的data被闲置，仅使用了p_next，则势必浪费内存。当然，对于当前示例来讲data是int类型数据，仅占用4个字节，浪费4个字节或许还能接受，如果data是其它类型呢？

如果链表的元素是学生记录中的数据，由于学生记录中的数据分别为不同类型的数据，因此结构体是最好的选择。而作为范例程序无法面面俱到，所以仅以几个典型的数据为例作为结构体的成员。基于此，专门为学生记录中的数据定义一个结构体类型与新的结构体类型名。其数据类型定义如下： 

即可用此结构体存储学生记录中的数据，其成员在内存中的存储关系详见图 3.7。如果将element_type_t声明与student_t相同的类型，则链表数据结构为：

图 3.7

即与应用程序相关的数据data的类型为另一个结构体类型student_t。

此时只要定义一个slist_node_t类型的变量node，即可引用结构体的成员：

那么该链表各成员在内存中的存储关系就确定下来了，详见图 3.8。如果使用表达式

图 3.8

即可通过node变量引用slist_node_t结构体的成员data。此时，只要将node.data看作一个student_t类型变量，即可使用表达式

引用student_t结构体成员data的成员name（学生记录中的数据）。

当链表中的数据从int类型变为student_t时，浪费的空间将是student_t类型的大小。这里仅仅是一个示例，学生记录可能包含更多其它的信息，比如，学号、年级、血型、宿舍号等，则头结点浪费的空间将会更大。

同时，这里也隐含了一个问题，数据类型的改变将导致程序行为的改变，使得该程序无法做到通用，必须在编译前确定好数据类型，则程序不能以通用库的形式发布。如果要使代码通用，就要使用能接受任意数据类型的void *。

2、存址

为了通用还是在链表中存放void *类型的元素，即可用链表存储用户传入的任意指针类型数据，则链表结点的数据结构定义如下：

其中，结点的数据域类型为void *类型指针，data指向用户数据，结点中的数据是由调用者（应用程序）提供的用户数据。

虽然void *看起来是一个指针，其本质上则是一个整数，因为在大多数编译器中指针与int占用的存储空间大小一样，所以通用链表是一个结点数据域类型为int型的链表，只不过结点的数据域中存储的是与应用程序关联的用户数据的地址。

假设存储在struct _student结构体学生记录中的数据就是用户数据，那么只要将存储学生记录的结构体变量的地址传递给链表结点的数据域就行了，即p-> 假设存储在struct _student结构体学生记录中的数据就是用户数据，那么只要将存储学生记录的结构体变量的地址传递给链表结点的数据域就行了，即p->data指向用户数据的结构体存储空间