数据结构 - 单链表 - C 语言

通过组合使用结构和指针创建强大的数据结构。

链表 (linked list) 是一些包含数据的独立数据结构 (通常称为节点) 的集合。链表中的每个节点通过链或指针连接在一起。程序通过指针访问链表中的节点。通常节点是动态分配的，但有时你也能看到由节点数组构建的链表。即使在这种情况下，程序也是通过指针来遍历链表的。

1. 单链表

在单链表中，每个节点包含一个指向链表下一节点的指针。链表最后一个节点的指针字段的值为 NULL，提示链表后面不再有其他节点。在你找到链表的第 1 个节点后，指针就可以带你访问剩余的所有节点。为了记住链表的起始位置，可以使用一个根指针 (root pointer)。根指针指向链表的第 1 个节点。注意根指针只是一个指针，它不包含任何数据。

单链表图示

//============================================================================
// Name        : typedef - struct
// Author      : Yongqiang Cheng
// Version     : Version 1.0.0
// Copyright   : Copyright (c) 2019 Yongqiang Cheng
// Description : Hello World in C++, Ansi-style
//============================================================================

typedef struct structure_name
{
	data_type member_name1;
	data_type member_name2;
	data_type member_name3;
	data_type member_name4;
} type_name;

struct structure_name
{
	data_type member_name1;
	data_type member_name2;
	data_type member_name3;
	data_type member_name4;
} object_names;

声明创建结构

//============================================================================
// Name        : typedef - struct
// Author      : Yongqiang Cheng
// Version     : Version 1.0.0
// Copyright   : Copyright (c) 2019 Yongqiang Cheng
// Description : Hello World in C++, Ansi-style
//============================================================================

typedef struct NODE
{
	struct NODE *1ink;
	int value;
} Node;

存储于每个节点的数据是一个整型值。这个链表包含三个节点。如果你从根指针开始，随着指针到达第 1 个节点，你可以访问存储于那个节点的数据。随着第 1 个节点的指针可以到达第 2 个节点，你可以访问存储在那里的数据。最后，第 2 个节点的指针带你来到最后一个节点。零值提示它是一个 NULL 指针，在这里它表示链表中不再有更多的节点 。

在上面的图中，这些节点相邻在一起，这是为了显示链表所提供的逻辑顺序。链表中的节点可能分布于内存中的各个地方。对于一个处理链表的程序而言，各节点在物理上是否相邻并没有什么区别，因为程序始终用链 (指针) 从一个节点移动到另一个节点。

单链表可以通过链从开始位置遍历链表直到结束位置，但链表无法从相反的方向进行遍历。当你的程序到达链表的最后一个节点时，如果你想回到其他任何节点，你只能利用根指针从头开始。当然，程序在移动到下一个节点前可以保存一个指向当前位置的指针，甚至可以保存指向前面几个位置的指针。链表是动态分配的，可能增长到几百或几千个节点，所以要保存所有指向前面位置的节点的指针是不可行的。

在这个特定的链表中，节点根据数据的值按升序链接在一起。对于有些应用程序而言，这种顺序非常重要，比如根据一天的时间安排约会。对于那些不要求排序的应用程序，当然也可以创建无序的链表。

1.1 在单链表中插入

假定我们有一个新值，比如 12，想把它插入到前面那个链表中。从概念上说，这个任务非常简单：从链表的起始位置开始，跟随指针直到找到第 1 个值大于 12 的节点，然后把这个新值插入到那个节点之前的位置。

我们按顺序访问链表，当到达内容为 15 的节点 (第 1 个值大于 12 的节点) 时就停下来。我们知道这个新值应该添加到这个节点之前，但前一个节点的指针字段必须进行修改以实现这个插入。但是，我们已经越过了这个节点，无法返回去。解决这个问题的方法就是始终保存一个指向链表当前节点之前的那个节点的指针。

把一个节点插入到一个有序的单链表中，函数的参数是一个指向链表第 1 个节点的指针以及需要插入的值。

//============================================================================
// Name        : typedef - struct
// Author      : Yongqiang Cheng
// Version     : Version 1.0.0
// Copyright   : Copyright (c) 2019 Yongqiang Cheng
// Description : Hello World in C++, Ansi-style
//============================================================================

/*
 ** Insert into an ordered, singly linked list. The arguments are
 ** a pointer to the first node in the list, and the value to insert.
 */

#include <stdlib.h>
#include <stdio.h>

#define	FALSE	1
#define	TRUE	0

typedef struct NODE
{
	struct NODE *link;
	int value;
} Node;

int sll_insert(Node *current, int new_value)
{
	Node *previous;
	Node *new_node;

	/*
	 ** Look for the right place by walking down the list
	 ** until we reach a node whose value is greater than or equal to the new value.
	 */
	while (current->value < new_value)
	{
		previous = current;
		current = current->link;
	}

	/*
	 ** Allocate a new node and store the new value into it.
	 ** In this event, we return FALSE.
	 */
	new_node = (Node *) malloc(sizeof(Node));
	if (NULL == new_node)
	{
		return FALSE;
	}

	new_node->value = new_value;

	/*
	 ** Insert the new node into the list, and return TRUE.
	 */
	new_node->link = current;
	previous->link = new_node;

	return TRUE;
}

我们用下面这种方法调用这个函数：

result = sll_insert(root, 12);

让我们仔细跟踪代码的执行过程，看看它是否把新值 12 正确地插入到链表中。首先，传递给函数的参数是 root 变量的值，它是指向链表第 1 个节点的指针。当函数刚开始执行时，链表的状态如下：

这张图并没有显示 root 变量，因为函数不能访问它。它的值的一份拷贝作为形参 current 传递给函数，但函数不能访问 root。现在 current->value 是 5，它小于 12，所以循环体再次执行。当我们回到循环的顶部时，current 和 previous 指针都向前移动了一个节点。

现在，current->value 的值为 10，因此循环体还将继续执行，结果如下：

现在，current->value 的值大于 12，所以退出循环。

此时，重要的是 previous 指针，因为它指向我们必须加以修改以插入新值的那个节点。但首先，我们必须得到一个新节点，用于容纳新值。下面这张图显示了新值被复制到新节点之后链表的状态。

把这个新节点链接到链表中需要两个步骤。首先，

new_node->link = current;

使新节点指向将成为链表下一个节点的节点，也就是我们所找到的第 1 个值大于 12 的那个节点。在这个步骤之后，链表的内容如下所示：

第二个步骤是让 previous 指针所指向的节点 (也就是最后一个值小于 12 的那个节点) 指向这个新节点。下面这条语句用于执行这项任务。

previous->link = new_node;

这个步骤之后，链表的状态如下：

然后函数返回，链表的最终样子如下：

从根指针开始，随各个节点的 link 字段逐个访问链表，我们可以发现这个新节点己被正确地插入到链表中。

不幸的是，这个插入函数是不正确的。

试试把 20 这个值插入到链表中，你就会发现一个问题：while 循环越过链表的尾部，并对一个 NULL 指针执行间接访问操作。为了解决这个问题，我们必须对 current 的值进行测试，在执行表达式 current->value 之前确保它不是一个 NULL 指针：

while ((NULL != current) && (current->value < new_value))

为了在链表的起始位置插入一个节点，函数必须修改根指针。但是，函数不能访问变量 root。修正这个问题最容易的方法是把 root 声明为全局变量，这样插入函数就能修改它。不幸的是，这是最坏的一种问题解决方法。因为这样一来，函数只对这个链表起作用。

稍好的解决方法是把一个指向 root 的指针作为参数传递给函数。然后，使用间接访问，函数不仅可以获得 root (指向链表第 1 个节点的指针，也就是根指针) 的值，也可以向它存储一个新的指针值。root 是一个指向 Node 的指针，所以参数的类型应该是 Node **，也就是一个指向 Node 的指针的指针。

result = sll_insert(&root, 12);

//============================================================================
// Name        : typedef - struct
// Author      : Yongqiang Cheng
// Version     : Version 1.0.0
// Copyright   : Copyright (c) 2019 Yongqiang Cheng
// Description : Hello World in C++, Ansi-style
//============================================================================

/*
 ** Insert into an ordered, singly linked list. The arguments are
 ** a pointer to the first node in the list, and the value to insert.
 */

#include <stdlib.h>
#include <stdio.h>

#define	FALSE	1
#define	TRUE	0

typedef struct NODE
{
	struct NODE *link;
	int value;
} Node;

int sll_insert(Node **rootp, int new_value)
{
	Node *current;
	Node *previous;
	Node *new_node;

	if (NULL == rootp)
	{
		return FALSE;
	}

	/*
	 ** Get the pointer to the first node.
	 */
	current = *rootp;
	previous = NULL;

	/*
	 ** Look for the right place by walking down the list
	 ** until we reach a node whose value is greater than or equal to the new value.
	 */
	while ((NULL != current) && (current->value < new_value))
	{
		previous = current;
		current = current->link;
	}

	/*
	 ** Allocate a new node and store the new value into it.
	 ** In this event, we return FALSE.
	 */
	new_node = (Node *) malloc(sizeof(Node));
	if (NULL == new_node)
	{
		return FALSE;
	}
	new_node->value = new_value;

	/*
	 ** Insert the new node into the list, and return TRUE.
	 */
	new_node->link = current;
	if (NULL == previous)
	{
		*rootp = new_node;
	}
	else
	{
		previous->link = new_node;
	}

	return TRUE;
}

这第 2 个版本包含了另外一些语句。

previous = NULL;

我们需要这条语旬，这样我们在以后就可以检查新值是否应为链表的第 1 个节点。

current = *rootp ;

这条语句对根指针参数执行间接访问操作，得到的结果是 root 的值，也就是指向链表第 1 个节点的指针。

	/*
	 ** Insert the new node into the list, and return TRUE.
	 */
	new_node->link = current;
	if (NULL == previous)
	{
		*rootp = new_node;
	}
	else
	{
		previous->link = new_node;
	}

这条语句被添加到函数的最后。它用于检查新值是否应该被添加到链表的起始位置。如果是，我们使用间接访问修改根指针，使它指向新节点。

这个函数可以正确完成任务，而且在许多语言中，这是你能够获得的最佳方案。我们还可以做得更好一些，因为 C 允许我们获得现存对象的地址 (即指向该对象的指针)。

消除特殊情况使这个函数更为简单。这个改进之所以可行是由于两方面的因素。第 1 个因素是我们正确解释问题的能力。除非你可以在看上去不同的操作中总结出共性，不然你只能编写额外的代码来处理特殊情况。通常，这种知识只有在你学习了一阵数据结构并对其有进一步的理解之后才能获得。第 2 个因素是 C 语言提供了正确的工具帮助你归纳问题的共性。

这个改进的函数依赖于 C 能够取得现存对象的地址这一能力。和许多 C 语言特性一样，这个能力既成力巨大，又暗伏凶险。防止错误诸如越界引用数组元素或产生一种类型的指针但实际上指向另一种类型的对象。

C 的指针限制要少得多，这也是我们能改进插入函数的原因所在。C 程序员在使用指针时必须加倍小心，以避免产生错误。Pascal 语言的指针哲学有点类似下面这样的说法：使用锤子可能会伤着你自己，所以我们不给你锤子。C 语言的指针哲学则是：给你锤子，实际上你可以使用好几种锤子，祝你好运！有了这个能力之后，C 程序员较之 Pascal 程序员更容易陷入麻烦，但优秀的 C 程序员可以比他们的 Pascal 和 Modula 同行产生体积更小、效率更高、可维护性更佳的代码。这也是 C 语言在业界为何如此流行以及经验丰富的 C 程序员为何如此受青昧的原因之一。