数据结构

数据的逻辑结构和物理结构是密切相关的两个方面，以后读者会看到，任何一个算法的设计取决于选定的数据（逻辑）结构，而算法的实现依赖于采用的存储结构。

“正确”一词的含义在通常的用法中有很大差别，大体可分为以下4个层次：a.程序不含语法错误；b.程序对于几组输入数据能够得出满足规格说明要求的结果；c.程序对于精心选择的典型、苛刻而带有刁难性的几组输入数据能够得出满足规格说明要求的结果；d.程序对于一切合法的输入数据都能产生满足规格说明要求的结果。显然，达到第d层意义下的正确是极为困难的，所有不同输人数据的数量大得惊人，逐一验证的方法是不现实的。对于大型软件需要进行专业测试，而一般情况下，通常以第c层意义的正确性作为衡量一个程序是否合格的标准。

换句话说，以元素在计算机内“物理位置相邻”来表示线性表中数据元素之间的逻辑关系。每一个数据元素的存储位置都和线性表的起始位置相差一个和数据元素在线性表中的位序成正比的常数（见图2.2）。由此，只要确定了存储线性表的起始位置，线性表中任一数据元素都可随机存取，所以线性表的顺序存储结构是一种随机存取的存储结构。

由于高级程序设计语言中的数组类型也有随机存取的特性，因此，通常都用数组来描述数据结构中的顺序存储结构。在此，由于线性表的长度可变，且所需最大存储空间随问题不同而不同，则在C语言中可用动态分配的一维数组，如下描述。

在这种存储结构中，容易实现线性表的某些操作，如随机存取第ⅰ个数据元素等。只是要特别注意的是，C语言中数组的下标从“0”开始，因此，若L是SqList类型的顺序表，则表中第i个数据元素是L.elem[i-1]。

的线性链表存储结构，整个链表的存取必须从头指针开始进行，头指针指示链表中第一个结点（即第一个数据元素的存储映像）的存储位置。同时，由于最后人个数据元素没有直接后继，则线性链表中最后一个结点的指针为“空”（NULL)

用线性链表表示线性表时，数据元素之间的逻辑关系是由结点中的指针指示的。换句话说，指针为数据元素之间的逻辑关系的映像，则逻辑上相邻的两个数据元素其存储的物理位置不要求紧邻，由此，这种存储结构为非顺序映像或链式映像。

有时，我们在单链表的第一个结点之前附设一个结点，称之为头结点。头结点的数据域可以不存储任何信息，也可存储如线性表的长度等类的附加信息，头结点的指针域存储指向第一个结点的指针（即第一个元素结点的存储位置）。

这种描述方法便于在不设“指针”类型的高级程序设计语言中使用链表结构。在如上描述的链表中，数组的一个分量表示一个结点，同时用游标（指示器cur）代替指针指示结点在数组中的相对位置。数组的第零分量可看成头结点，其指针域指示链表的第一个结点……这种存储结构仍需要预先分配一个较大的空间，但在作线性表的插人和删除操作时不需移动元素，仅需修改指针，故仍具有链式存储结构的主要优点……为了和指针型描述的线性链表相区别，我们给这种用数组描述的链表起名叫静态链表。

类似地可写出在静态链表中实现插入和删除操作的算法……所不同的是，需由用户自己实现malloc和free这两个函数。为了辨明数组中哪些分量未被使用，解决的办法是将所有未被使用过以及被删除的分量用游标链成一个备用的链表，每当进行插入时便可从备用链表上取得第一个结点作为待插入的新结点；反之，在删除时将从链表中删除下来的结点链接到备用链表上。

循环链表（circular linked list）是另一种形式的链式存储结构。它的特点是表中最后一个结点的指针域指向头结点，整个链表形成一个环。由此，从表中任一结点出发均可找到表中其他结点，如图2.12所示为单链的循环链表。类似地，还可以有多重链的循环链表。

循环链表的操作和线性链表基本一致，差别仅在于算法中的循环条件不p或p->next是否为空，而是它们是否等于头指针。但有的时候，若在循环链表中设立尾指针而不设头指针（如图2.13（a）所示），可使某些操作简化。例如将两个线性表合并成一个表时，仅需将一个表的表尾和另一个表的表头相接。当线性表以图2。13（a）的循环链表作存储结构时，这个操作仅需改变两个指针值即可，运算时间为O（1）。合并后的表如图2。13（b）所示。

以上讨论的链式存储结构的结点中只有一个指示直接后继的指针域，由此，从某个结点出发只能顺指针往后寻查其他结点。若要寻查结点的直接前趋，则需从表头指针出发。换句话说，在单链表中，NextElem的执行时间为O（1），而PriorElem的执行时间为O（n）。为克服单链表这种单向性的缺点，可利用双向链表（double linked list）。

称top为栈顶指针，其初值指向栈底，即top=base可作为栈空的标记，每当插入新的栈顶元素时，指针top增1；删除栈顶元素时，指针top减1，因此，非空栈中的栈顶指针始终在栈顶元素的下一个位置上。

可见，这个处理过程恰与栈的特点相吻合。由此，在算法中设置一个栈，每读入一个括号，若是右括号，则或者使置于栈顶的最急迫的期待得以消解，或者是不合法的情况；若是左括号，则作为一个新的更急迫的期待压入栈中，自然使原有的在栈中的所有未消解的期待的急迫性都降了一级。另外，在算法的开始和结束时，栈都应该是空的。此算法将留给读者作为习题完成。

队列在程序设计中也经常出现。一个最典型的例子就操作系统中的作业排队。在允许多道程序运行的计算机系统中，同时有几个作业运行。如果运行的结果都需要通过通道输出，那就要按请求输出的先后次序排队。每当通道传输完毕可以接受新的输出任务时，队头的作业先从队列中退出作输出操作。凡是申请输出的作业都从队尾进入队列。

用链表表示的队列简称为链队列，如图3.10所示。一个链队列显然需要两个分别指示队头和队尾的指针（分别称为头指针和尾指针）才能惟一确定。这里，和线性表的单链表一样，为了操作方便起见，我们也给链队列添加一个头结点，并令头指针指向头结点。由此，空的链队列的判决条件为头指针和尾指针均指向头结点

在上述模块的算法描述中，请读者注意删除队列头元素算法中的特殊情况。一般情况下，删除队列头元素时仅需修改头结点中的指针，但当队列中最后一个元素被删后，队列尾指针也丢失了，因此需对队尾指针重新赋值（指向头结点）。

和顺序栈相类似，在队列的顺序存储结构中，除了用一组地址连续的存储单元依次存放从队列头到队列尾的元素之外，尚需附设两个指针front和rear分别指示队列头元素及队列尾元素的位置。为了在C语言中描述方便起见，在此我们约定：初始化建空队列时，令front=rear=0，每当插入新的队列尾元素时，“尾指针增1”；每当删除队列头元素时，“头指针增1”。因此，在非空队列中，头指针始终指向队列头元素，而尾指针始终指向队列尾元素的下一个位置，如图3.12所示。

假设当前为队列分配的最大空间为6，则当队列处于图3.12（d）的状态时不可再继续插入新的队尾元素，否则会因数组越界而遭致程序代码被破坏。然而此时又不宜如顺序栈那样，进行存储再分配扩大数组空间，因为队列的实际可用空间并未占满。一个较巧妙的办法是将顺序队列億造为一个环状的空间，如图3.13所示，称之为循环队列。

只凭等式Q.front=Q.rear无法判别（循环）队列空间是“空”还是“满”。可有两种处理方法：其一是另设一个标志位以区别队列是“空”还是“满”；其二是少用一个元素空间，约定以“队列头指针在队列尾指针的下一位置（指环状的下一位置）上”作为队列呈“满”状态的标志。

串的逻辑结构和线性表极为相似，区别仅在于串的数据对象约束为字符集。然而，串的基本操作和线性表有很大差别。在线性表的基本操作中，大多以“单个元素”作为操作对象，例如在线性表中查找某个元素、求取某个元素、在某个位置上插入一个元素和删除一个元素等；而在串的基本操作中，通常以“串的整体”作为操作对象，例如在串中查找某个子串、求取一个子串、在串的某个位置上插入一个子串以及删除一个子串等。

在上述抽象数据类型定义的13种操作中，串赋值StrAssign、串比较StrCompare、求串长StrLength、串联接Concat以及求子串SubString 5种操作构成串类型的最小操作子集。即这些操作不可能利用其他串操作来实现，反之，其他串操作（除串清除ClearString和串销毁DestroyString外）均可在这个最小操作子集上实现。

类似于线性表的顺序存储结构，用一组地址连续的存储单元存储串值的字符序列。在串的定长顺序存储结构中，按照预定义的大小，为每个定义的串变量分配一个固定长度的存储区，则可用定长数组如下描述之。

串的实际长度可在这预定义长度的范围内随意，超过预定义长度的串值则被舍去，称之为“截断”。对串长有两种表示方法：一是如上述定义描述的那样，以下标为0的数组分量存放串的实际长度，如PASCAL语言中的串类型采用这种表示方法；二是在串值后面加一个不计入串长的结束标记字符，如在有的C语言中以“0”表示串值的终结。此时的串长为隐含值，显然不便于进行某些串操作。

堆分配表示: 这种存储表示的特点是，仍以一组地址连续的存储单元存放串值字符序列，但它们的存储空间是在程序执行过程中动态分配而得。在C语言中，存在一个称之为“堆”的自由存储区，并由C语言的动态分配函数malloc（）和free（）来管理。利用函数malloc（）为每个新产生的串分配一块实际串长所需的存储空间，若分配成功，则返回一个指向起始地址的指针，作为串的基址，同时，为了以后处理方便，约定串长也作为存储结构的一部分。

和线性表的链式存储结构相类似，也可采用链表方式存储串值。由于串结构的特殊性——结构中的每个数据元素是一个字符，则用链表存储串值时，存在一个“结点大小”的问题，即每个结点可以存放一个字符，也可以存放多个字符。例如，图4.2（a）是结点大小为4（即每个结点存放4个字符）的链表，图4.2（b）是结点大小为1的链表。当结点大小大于1时，由于串长不一定是结点大小的整倍数，则链表中的最后一个结点不一定全被串值占满，此时通常补上“#”或其他的非串值字符（通常“#”不属于串的字符集，是一个特殊的符号）。

显然，存储密度小（如结点大小为1时），运算处理方便，然而，存储占用量大。如果在串处理过程中需进行内、外存交换的话，则会因为内外存交换操作过多而影响处理的总效率。应该看到，串的字符集的大小也是一个重要因素。一般地，字符集小，则字符的机内编码就短，这也影响串值的存储方式的选取。

因为在主串中可能存在多个和模式串“部分匹配”的子串，因而引起指针i的多次回溯。

此算法（KMP）可以在O（n+m）的时间数量级上完成串的模式匹配操作。其改进在于：每当一趟匹配过程中出现字符比较不等时，不需回溯i指针，而是利用已经得到的“部分匹配”的结果将模式向右“滑动”尽可能远的一段距离后，继续进行比较。