链表结点的数据结构该如何定义

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

>>>1.1.1 数据与p_next分离

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

1    typedef struct _slist_node{ 

2         struct _slist_node  *p_next;                    // 指向下一个结点的指针

3    }slist_node_t;

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

图3.10  链表示意图

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

1    typedef struct _slist_int{ 

2         slist_node_t  node;                                // 包含链表结点

3         int          data;                            // int类型数据

4    }slist_int_t; 

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

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

1        #include

2        typedef struct _slist_int{ 

3              slist_node_t  node; 

4          int          data;

5         }slist_int_t; 

6

7    int main (void)

8    { 

9         slist_node_t  head = {NULL};

10        slist_int_t    node1, node2, node3; 

11        slist_node_t *p_tmp;

12

13        node1.data = 1;

14        slist_add_tail(&head, &node1.node);

15        node2.data = 2;

16        slist_add_tail(&head, &node2.node);

17        node3.data = 3;

18        slist_add_tail(&head, &node3.node);

19        p_tmp = head.p_next; 

20        while (p_tmp != NULL){

21             printf("%d  ", ((slist_int_t *)p_tmp)->data);

22             p_tmp = p_tmp->p_next;

23        }

24        return 0;

25  }

由于用户需要初始化head为NULL，且遍历