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

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

第三章为算法与数据结构，本文为3.2 单向链表中的3.2.1 存值与存址和3.2.2 数据与p_next分离。

>>> 3.2.1 存值与存址

1、存值

在结构体中，虽然不能用"当前结构体类型"作为结构体成员的类型，但可以用"指向当前结构体类型的指针"作为结构体成员的类型。比如：

其中，slist 是single list 的缩写，表明该结点是单向链表结点。由于AMetal平台规定字母大小写不能混用，且类型名、变量名、函数名等只能使用小写字母，宏定义只能使用大写字母，因此为了与AMetal平台保持一致，类型名中的字母全部使用小写。

由于p_next是指针类型而不是结构体，它所指向的是同一种类型的结构体变量。事实上，编译器在确定结构体的长度之前就已经知道了指针的长度，因此这种类型的自引用是合法的。p_next不仅是struct _slist_node类型中的一员，而且又指向struct _slist_node类型的数据，接着开始为这个结构体创建类型名slist_node_t。即：

AMetal规定使用typedef定义的新类型名必须以"_t"结尾，为了与AMetal保持一致，后续的类型名结尾为"_t"。但一定要警惕下面这样的声明陷阱：

在声明p_next指针时，typedef还没有结束，slist_node_t还不能使用，所以编译器报告错误信息。当然，也可以在定义结构体前先用typedef，即可在声明p_next指针时，使用类型定义slist_node_t。比如：

最后也可以结合上述2种方法按照以下形式进行定义：

即定义了一个结构体类型，这种方法常用于链表（list）、树（tree）与许多其它的动态数据结构。p_next称为链（link），每个结构将通过p_next链接到后面的结构，详见图 3.1。其中，data用于存放结点中的数据，该数据是由调用者（应用程序）提供的，p_next用于存放指向链表中下一个结点的指针（地址）。其中的箭头表示链，p_next的值是下一个结点的地址，当p_next的值为NULL（0），表示链表已经结束。因此可以将链表想象为一系列连续的元素，元素与元素之间的链接关系只是为了确保所有的元素都可以被访问。如果错误地丢失了一个链接，则从这个位置开始往后的所有元素都无法访问。

图 3.1 链表示意图

通常需要定义一个指向链表头结点的指针p_head，便于从链表的头结点开始，顺序地访问链表中所有的结点。比如：

添加头结点p_head后，完整的链表示意图详见图3.2。

图3.2  添加指向链表头结点的指针

此时，只要获取p_head的值，即可依次遍历（访问）链表的所有结点。比如：

对于操作链表的函数，必须进行测试，以确保在操作空链表是也是正确的。如果直接使用p_head访问各个结点，当遍历结束后，则p_head的值为NULL，它不再指向第一个结点，从而丢失了整个链表，因此必须通过一个临时指针变量访问链表的各个结点。比如： 

接下来，考虑将结点添加到链表的尾部。在初始状态下，链表是一个不包含任何结点的空表，此时p_head为NULL，那么新增的结点就是头结点，直接修改p_head的值，使其从NULL变为指向新结点的指针，链表的变化详见图3.3。

图3.3  链表为空时新增结点

由于新结点添加在链表的尾部，因此新结点中p_next的值为NULL，详见程序清单3.6。

程序清单3.6  新增结点范例程序（链表为空）

现在我们来编写一个简单的示例，验证结点是否添加成功，详见程序清单3.7。

程序清单3.7  添加结点范例程序（1）

如果结点加入成功，则可以通过printf将数据1打印出来。遗憾的是，运行该程序后，什么现象都没有看到。当链表为空时，添加一个结点的核心工作是"修改p_head的值，使其从NULL变为指向新结点的指针"。在调用slist_add_tail()后，p_head被修改了吗？

当将指针传递给函数时，其传递的是值。如果想要修改原指针，而不是指针的副本，则需要传递指针的指针。p_head是在主程序中定义的，其后仅仅是将NULL值作为实参传递给了slist_add_tail()的形参。此后p_head与slist_add_tail()再无任何关联，因此slist_add_tail()根本不可能修改p_head。要想在调用时修改p_head，则必须将该指针的地址传递给slist_add_tail()，详见程序清单3.8。

程序清单3.8  链表为空时新增结点的范例程序

如程序清单3.9所示的测试程