算法是指为了达到某种目的而操作数据的方式。算法通常适用于具体的问题,以复杂的方式来处理简单的数据。例如,编译器把简单的字符串和字符翻译成可以在特定机器上执行的二进制代码。编译器的内部工作原理是:通过相互影响的诸多算法按顺序将源代码字符转换为中间表示。这些表示都是通过其他算法将它们自身翻译成目标代码,这些代码与原始的字符和字符串(指源代码)具有极少的相似之处。尽管程序不像编译器那样有雄心壮志,但它们也同样极大地依赖于算法,以一种可预见的方式来处理数据。因此,在不了解操作数据的基本例程的情况下,不可能深入地讨论算法。那些希望通晓如何使用算法的开发人员首先要学习如何操作数据。而后,他们可以根据自己的需要应用算法技术来表示数据。 通过算法操作数据主要涉及的是在内存中表示数据的技术。怎样存储、访问数据以及怎样转换数据以便最高效地解决给定的问题?大多数问题都要求开发人员能够熟练地使用某些基本的数据结构(data structure)。这些数据结构是存储或处理数据的形式。最简单的数据结构包括:数组(array)、链表(linked list)、栈(stack)和队列(queue)。 出于本书的目的,假定你已经熟悉C语言中的数组。无论它们是字符数组(如字符串)、整数数组,还是结构体数组,操作的原理是相同的。如果您不熟悉这些操作,可以在学习下面的内容之前先参考一下关于C语言的初级教材。本章将详细探讨链表、栈和队列。第3章将再次探讨链表,其中相当深入地讨论了散列表;第6章将探讨错综复杂的二叉树。 21链表 C语言(以及其他许多语言)中的数组必须在编写程序时定义。也就是说,在C语言中定义一个数组时,还必须定义它的大小。甚至对于在全局级别(即在任何函数之外)声明或定义的数组,例如: 也必须在某个位置指定数组的具体大小,一般使用malloc()函数或者某种类似的机制来执行该任务。 无论是否使用malloc()函数,在使用数组之前都必须先指定其大小。这就带来了一个问题:当事先无法知道需要创建多少个元素时,怎样分配必要的空间。 例如,假设你需要编写一个程序,它从一个输入文件中读取城市的名称及其气温信息。最后需要按气温对城市进行排序,并确定中间的气温(也就是说,在该气温的两边,更冷和更热的气温数量相同)。对于这个问题,使用一个简单的数组不是一个好的选择。因为不知道应该创建多大的数组才合适。或许可以声明一个比你预期所需空间大得多的数组,然后希望输入文件永远不会超过这个大小。不过,这种方法不仅浪费空间,而且如果输入文件突然超过预期的大小,则很有可能导致程序失败。 一种解决方案是读取文件两遍,第一遍用来确定数组的大小并且为它分配空间,第二遍则进行实际的数据处理。不过,这种解决方案的效率很低。因为磁盘I/O的速度非常慢(甚至在RAM磁盘上也是如此)——事实上,它几乎总是任何程序中最慢的部分,一般要慢一个数量级,因此只要有可能,就应避免读取两遍数据。 一种更巧妙的解决方案是使用链表,它按接收到数据的方式来存储它们。链表和前一种方法一样精确,但效率要高得多。链表由一连串元素(称为节点)构成。每个节点包含要存储的数据项以及一个指针,它指向链表中的下一个节点。当程序读取每个数据项时,将创建一个新的节点(使用malloc()函数),并将其添加在链表的尾部。在输入结束时,计算机内存中将维持一个节点列表,其中每个节点都包含数据项(例如城市名称和气温信息)以及指向下一个节点的指针。最后一个节点中的指针的值为NULL,在ANSI C中将该值定义为不指向任何地方的指针。当通过遍历链表来查找中间气温时,如果遇到NULL指针,则说明已经到达了链表尾部。每个节点中的指针称为链(link),因此将这种数据结构称为链表(linked list)。每个链表都以一个简单的指针开始,它指向链表中的第一个数据项,这个指针称为头指针(head)。一个简短的链表如图21所示。图21具有三个节点的链表在C语言中,可以将图21中所示的链表表示如下: 创建typedef是为了增强代码的可读性。可以预见,“链”是指向“节点”的指针。我们定义的第一个“链”是“头指针”,当链表为空时它是NULL,否则它指向第一个节点。 初始化一个这种类型的新链表只需要简单地初始化合适的变量: 整型NodeCount将在以后处理链表时用到。一旦添加了第一个节点,头指针将指向它。添加节点可能很容易或者是乏味的。如果在添加节点时无需考虑它们在链表(无序链表)中所占据的位置,可以简单地将节点添加在链表头部。当为每个节点都分配了空间时,它的“链”将指向当前“头指针”,然后更新“头指针”以指向新的“节点”,如图22所示。图22向链表中无序地添加节点向其元素具有某种顺序的链表(有序链表)中添加节点需要做更多的工作。首先,需要提供一种方式来比较两个节点的数据,并且确定哪个节点在链表中处于更高或更低的位置。此外,还必须确定当新节点与现有节点重复时应该如何处理:是应该添加新节点、丢弃新节点,还是应该修改现有节点的数据?在程序清单21中,分别通过以下两个函数来执行这些任务:NodeCmp()和DuplicateNode()。在定义了这些函数之后,就可以执行添加节点的实际工作。 在遍历链表时,仅当经过插入点或者已经到达链表尾部时,才能知道已经找到了添加节点的位置。因此,将需要保存前一个被检查的节点地址(程序清单21中的函数AddNodeAscend()中的prev)。插入发生在当前被检查的节点(curr)和前一个节点之间。如果pn指向你正试图添加的节点,那么这个过程如下: 需要考虑几种特殊情况:向一个空链表中添加节点、在第一个节点之前添加节点以及在链表的尾部添加节点。在函数AddNodeAscend()中显示了一种用于简洁地处理所有这些情况的方法。我们将不会测试所有的特殊情况,而是创建一个虚拟节点,并使当前链表从该节点延续下来。这样,我们就知道我们的链表永远不会为空,并且我们的实现逻辑也将大大简化。程序清单21(citytempc)从数据文件中读取城市和气温信息,将记录插入到一个链表中(按气温和城市名称的升序进行排序),丢弃重复的记录,然后打印该有序链表,并指示位于中间的条目。数据记录是文本文件中简单的行,它以前三个字符表示气温,其后接着最多124个字符表示城市名称。 注意:如果不使用像链表这样的动态结构,在不读取数据两遍的情况下,将不可能确定出中间气温。最后一个循环用于打印链表中的记录,它显示了遍历链表有多简单。程序清单21打印城市和气温的有序链表 用于该程序的一个示例数据文件可能如下所示: 来自该文件的输出将如下所示: 程序清单21显示了如何创建以及遍历链表、按顺序添加节点,以及比较两个节点。它还包括有函数DeleteNode(),该函数展示了如何删除一个节点(尽管在主程序中没有用到该函数)。删除节点需要遍历链表,直至找到要删除的节点为止。一旦找到该节点,则使前一个节点中的指针指向链表中的下一个节点,这样,链表现在将完全绕过当前节点。然后程序将通过free()函数把当前节点占用的内存返回给系统。 注意:为了使前一个节点准备好指向下一个节点,必须在遍历链表时维护一个单独的指针(称为prev),以便跟踪哪个节点位于应该删除的节点之前。这种需求暗示了迄今为止讨论的链表的主要缺点之一:如果不做特殊处理,将不知道哪个节点指向当前节点。节点本身只能告诉你下一个节点是什么,而不能告诉你前一个节点是什么。 当无法避免对该信息的需求时,将当前指针与前一个指针作为一个指针(即prev)来维护是可能的。我们通过curr=prev>Next来加以实现,因此在用到curr的任何地方,我们改用prev>Next。 一种更巧妙的技术是:不将prev维护为指向链表节点的指针,而是维护为指向前一个节点的Next元素的指针。为此,我们将prev定义为Link *prev。第5章中给出了使用这种技术的一个示例(程序清单516(linsertc))。当你希望处理链表的一个子集而又不允许从主链表中删除该子集时,这种技术的价值尤为突出。在第5章中实现链表的快速排序算法时,广泛采用了这种技术(程序清单517(lquick1c)和程序清单51(lquick2c))。拥有指向前一个节点的Next元素的指针的好处是:可以轻松地对链表的子集执行任何想要的修改,而又不会影响原来的那个更大的包含链表。 无论使用哪种技术,都要设法解决链表只有一个链的主要缺点:即无法说明当前节点的前一个节点是什么。解决方案是使链表中的每个节点具有两个链:一个指向前一个链,另一个指向后一个链。这样的链表称为双向链表(doubly linked list)。 注意:在程序清单21中,直接操纵链表的函数是通用的。在编码时,将其设计为与节点中所包含的具体数据无关。唯一的要求是:将指向下一个节点的链称为Next。实际上,其中的两个函数必须与数据相关,这两个函数是:NodeCmp()和DuplicateNode(),前者用于比较两个节点中的数据以确定插入顺序,后者用于处理当插入的节点所具有的数据与现有节点相同时的情况。链表的所有通用实现都至少要求将这两个函数设计成适合于将要处理的具体数据。在程序清单21中,函数DuplicateNode( )实际上并没有涉及数据,但是在其他程序中(比如第3章介绍的那些程序中),这个相同的函数可能需要操作数据。 在把程序清单21中的例程用于自己的目的时,可以根据需要定义Node,并且小心保持将链命名为Next。然后重新编写函数DuplicateNode()和NodeCmp()的代码,并且准备好运行它们。 程序清单21中展示的函数介绍了链表的基本操作。它们适合于快速而又随性的应用程序,但它们不能处理可能出现在复杂程序中的需求。例如,假设你需要维护多个具有不同数据类型的链表,这些函数将不足以处理这项任务。下面一节将详细描述怎样解决这样的问题,以及如何处理阻止快速而又随性的链表真正变得健壮的其他微妙问题。