抽象数据结构

程序设计的基本法则之一是例程不应超过一页。这可以通过把程序分割为一些模块(module)来实现。每个模块是一个逻辑单位并执行某个特定的任务，它通过调用其他模块而使本身保持很小。模块化有几个优点。第一，调式小程序比调试大程序要容易得多。第二，多个人同时对一个模块化程序要更容易。第三，一个写得好的模块化程序把某些依赖关系只局限在一个例程中，这样使得修改起来更容易。全局变量和副作用是有害的观念也正是出于模块化是有益的想法。

抽象数据结构(Abstract Data Type, ADT)是一些操作的集合。抽象数据类型是数学的抽象，在 ADT 的定义中根本没涉及如何实现这些操作。这可以看作模块化设计的扩充。

我们的基本想法是，这些操作的实现只是在程序中编写一次，而程序中任何其他部分需要该 ADT 上运行其中的一种操作，都可以通过调用适当的函数来进行。如果由于某种原因需要改变操作的细节，通过只修改运行这些 ADT 操作的例程应该可以很容易实现。在理想情况下，这种改变对于程序的其余部分通常是完全透明的。

对于每种 ADT 并不存在什么法则来指导我们必须要有哪些操作，这是一个设计决策。错误处理和关系的重组（在适当的地方）一般也取决于程序设计者。

表 ADT

表的简单数组实现

对表的所有操作都可以使用数组来实现。虽然数组是动态指定的，但还是需要对表的大小的最大值进行估计。通常需要估计得大一些，而这会浪费大量的空间。这是严重的局限，特别是在存在许多未知大小的表的情况下。

因为插入和删除的运行时间非常慢并且表的大小还必须事先已知，所以简单数组一般不用来实现表这种结构。

链表

链表由一系列不必在内存中相连的结构组成。每一个结构均含有表元素和指向包含该元素后继元的结构的指针。我们称之为 Next 指针。最后一个单元的 Next 指针指向 NULL；该值由 C 定义并且不能与其他指针混淆。ANSI C 规定 NULL 为零。

为了访问链表组成的表，我们需要知道在哪里能够找到第一个单元。指针变量就用于这个目的。重要的是要记住，一个指针就是一个数。只要将一个指针传递到该表的第一个元素，然后用一些 Next 指针遍历该表即可。这种操作显然是线性时间的，虽然这个常数可能会比用数组实现时大。

删除命令可以通过修改一个指针来实现。

插入命令需要使用一次 malloc 调用从系统中得到一个新单元并在此后执行两次指针调整。

程序设计中常见的错误

最常遇到的错误是你的程序因来自系统的棘手的错误信息而崩溃，比如 “memory access violation” 或 “segmentation violation”，这种信息通常意味着有指针变量包含了伪地址。一个通常的原因是初始化变量失败。

第二种错误涉及如何使用或何时不使用 malloc 来获取一个新的单元。必须记住，声明指向一个结构的指针并不创建该结构，而只是给出足够的空间容纳结构可能会使用的地址。创建尚未被声明过的记录的唯一办法是使用 malloc 库函数。

当有些空间不再需要时，你可以用 free 命令通知系统来回收它。free(P) 的结果是： P 正在指向的地址没变，但在该地址处的数据此时已无定义了。

警告：malloc(sizeof(PtrToNode))是合法的。但是它并不给结构体分配足够的空间。它只给指针分配空间。

双链表

有时候以倒序扫面链表很方便。标准实现方法此时无能为力，然而解决办法却很简单。只要在数据结构上附加一个域，使它包含指向前一个单元的指针即可。其开销是一个附加的链，它增加了空间的需求，同时也使得插入和删除的开销增加一倍，因为有更多的指针需要定位。另外，它简化了删除操作，因为你不再被迫使用一个指向前驱元的指针来访问一个关键字，这个信息是现成的。

循环链表

让最后的单元反过来直指第一个单元是一种流行的做法。它可以有表头，也可以没有表头（若有表头，则最后的单元就指向它），并且还可以是双向链表（第一个单元的前驱元指针指向最后的单元）。

链表的游标实现

诸如 BASIC 和 FORTRAN 等许多语言都不支持指针。如果需要链表而又不能使用指针，那么就必须使用另外的实现方法。我们将描述这种方法称之为游标实现法。

在链表的指针实现中有两条重要的特性：

1. 数据存储在一组结构体中。每一个结构体包含数据以及指向下一个结构体的指针。
2. 一个新的结构体可以通过调用 malloc 而从系统全局内存（global memory）中得到，并可以通过调用 free 释放。