【2331】数据结构各章考试复习要点(打印版)

【2331】数据结构考试要点 概论- 基本概念和术语（一）

数据（Data）

数据 是信息的载体。它能够被计算机识别、存储和加工处理，是计算机程序加工的"原料"。

随着计算机应用领域的扩大，数据的范畴包括：整数、实数、字符串、图像和声音等。

数据元素（Data Element）

数据元素 是数据的基本单位。数据元素也称元素、结点、顶点、记录。一个数据元素可以由若干个 数据项 （也可称为字段、域、属性）组成。数据项是具有独立含义的最小标识单位。 数据结构（Data Structure）

数据结构 指的是数据之间的相互关系，即数据的组织形式。

1．数据结构一般包括以下三方面内容：

① 数据元素之间的逻辑关系，也称 数据的逻辑结构 （Logical Structure）； 数据的逻辑结构是从逻辑关系上描述数据，与数据的存储无关，是独立于计算机的。数据的逻辑结构可以看作是从具体问题抽象出来的数学 模型。

② 数据元素及其关系在计算机存储器内的表示，称为 数据的存储结构 （Storage Structure）；

数据的存储结构是逻辑结构用计算机语言的实现（亦称为映象），它依赖于计算机语言。对机器语言而言，存储结构是具体的。一般，只在 高级语言的层次上讨论存储结构。 ③ 数据的运算 ，即对数据施加的操作。

数据的运算定义在数据的逻辑结构上，每种逻辑结构都有一个运算的集合。最常用的检索、插入、删除、更新、排序等运算实际上只是在

在上面的学生成绩表中，可能要经常查看某一学生的成绩；当学生退学时要删除相应的结点；进来新学生时要增加结点。究竟如何进行查 找、删除、插入，这就是数据的运算问题。

搞清楚了上述三个问题，也就弄清了学生成绩表这个数据结构。

2 ．数据的逻辑结构分类

在不产生混淆的前提下，常将数据的逻辑结构简称为数据结构。数据的逻辑结构有两大类： （ 1）线性结构

线性结构的逻辑特征 是：若结构是非空集，则有且仅有一个开始结点和一个终端 结点，并且所有结点都最多只有一个直接前趋和一个直接后 继。 线性表是一个典型的线性结构。栈、队列、串等都是线性结构。 （ 2）非线性结构

非线性结构的逻辑特征 是：一个结点可能有多个直接前趋和直接后继。数组、广义表、树和图等数据结构都是非线性结构。

抽象的数据上所施加的一系列抽象的操作。所谓 抽象的操作 ，是指我们只知道这些操作是"做什么"，而无须考虑"如何做"。只有确定了 存储结构之后，才考虑如何具体实现这些运算。

为了增加对数据结构的感性认识，下面举例来说明有关数据结构的概念。 【例1．1】

学生成绩表，见下表。

概论- 基本概念和术语（二）

3 ．数据的四种基本存储方法

数据的存储结构可用以下四种基本存储方法得到： （ 1 ）顺序存储方法

该方法把逻辑上相邻的结点存储在物理位置上相邻的存储单元里，结点间的逻辑关系由存储单元的邻接关系来体现。

表中的每一行是一个数据元素（或记录、结点），它由学号、姓名、各科成绩及平均成绩等数据项组成。

表中数据元素之间的逻辑关系是：对表中任一个结点，与它相邻且在它前面的结点（亦称为直接前趋（Immediate Predecessor））最多只

有一个；与表中任一结点相邻且在其后的结点（亦称为直接后继（Immediate Successor））也最多只有一个。表中只有第一个结点没有直

接前趋，故称为开始结点；也只有最后一个结点没有直接后继。故称之为终端结点。例如，表中"马二"所在结点的直接前趋结点和直接后继

结点分别是"丁一"和"张三"所在的结点，上述结点间的关系构成了这张学生成绩表的逻辑结构。

（2）存储结构

该表的存储结构是指用计算机语言如何表示结点之间的这种关系，即表中的结点是顺序邻接地存储在一片连续的单元之中，还是用指针将 这些结点链接在一起？

（3）数据的运算

注意：在表中指出数据元素、数据项、开始结点和终端结点等概念

（1）逻辑结构

由此得到的存储表示称为顺序存储结构 （ Sequential Storage Structure ），通常借助程序语言的数组描述。

该方法主要应用于线性的数据结构。非线性的数据结构也可通过某种线性化的方法实现顺序存储。 （ 2 ）链接存储方法

该方法不要求逻辑上相邻的结点在物理位置上亦相邻，结点间的逻辑关系由附加的指针字段表示。由此得到的存储表示称为链式存储结构（ Linked Storage Structure ） , 通常借助于程序语言的指针类型描述。 （3） 索引存储方法

按"值"是否可分解，可将数据类型划分为两类：

该方法通常在储存结点信息的同时 ， 还建立附加的索引表。

① 原子类型 ：其值不可分解。通常是由语言直接提供。

索引表由若干索引项组成。若每个结点在索引表中都有一个索引项，则该索引表称之为稠密索引（ Dense Index ）。若一组结点在索引表中只

对应一个索引项，则该索引表称为稀疏索引 (Spare Index) 。 索引项的一般形式是：

( 关键字、地址 )

关键字是能唯一标识一个结点的那些数据项。稠密索引中索引项的地址指示结点所在的存储位置；稀疏索引中索引项的地址指示一组结点的起始 存储位置。 （4） 散列存储方法

该方法的基本思想是：根据结点的关键字直接计算出该结点的存储地址。 四种基本存储方法，既可单独使用，也可组合起来对数据结构进行存储映像。 同一逻辑结构采用不同的存储方法，可以得到不同的存储结构。选择何种存储结构来表示相应的逻辑结构，视具体要求而定，主要考虑运算方便 及算法的时空要求。 4 ．数据结构三方面的关系

数据的逻辑结构、数据的存储结构及数据的运算这三方面是一个整体。孤立地去理解一个方面，而不注意它们之间的联系是不可取的。

存储结构是数据结构不可缺少的一个方面：同一逻辑结构的不同存储结构可冠以不同的数据结构名称来标识。

【例】线性表是一种逻辑结构，若采用顺序方法的存储表示，可称其为顺序表；若采用链式存储方法，则可称其为链表；若采用散列存储方法， 则可称为散列表。

Postconditions:执行本操作后系统的状态//"系统"可看作某个数据结构

数据的运算也是数据结构不可分割的一个方面。在给定了数据的逻辑结构和存储结构之后，按定义的运算集合及其运算的性质不同，也可能导致 完全不同的数据结构。

【例】 若对线性表上的插入、删除运算限制在表的一端进行，则该线性表称之为栈；若对插入限制在表的一端进行，而删除限制在表的另一端

Operation2://操作2 …… }//ADT

【例】 C语言的整型、字符型等标准类型及指针等简单的导出类型； ② 结构类型 ：其值可分解为若干个成分（或称为分量）。是用户借助于语言提供的描述机制自己定义的，它通常是由标准类型派生的，故它 也是一种导出类型。

【例】 C的数组、结构等类型。

抽象数据类型（Abstract Type简称ADT）

ADT是指抽象数据的组织和与之相关的操作。可以看作是数据的逻辑结构及其在逻辑结构上定义的操作。 一个ADT可描述为： ADT ADT-Name{ Data://数据说明

数据元素之间逻辑关系的描述 Operations://操作说明

Operation1://操作1，它通常可用C或C﹢﹢的函数原型来描述 Input:对输入数据的说明

Preconditions:执行本操作前系统应满足的状态//可看作初始条件 Process:对数据执行的操作 Output:对返回数据的说明

进行，则该线性表称之为队列。更进一步，若线性表采用顺序表或链表作为存储结构，则对插入和删除运算做了上述限制之后，可分别得到顺序

栈或链栈，顺序队列或链队列。

数据类型（Data Type）

所谓数据类型是一个值的集合以及在这些值上定义的一组操作的总称。通常数据类型可以看作是程序设计语言中已实现的数据结构。

【例1．2】C语言的"整数类型"就定义了一个整数可取值的范围（其最大值INT-MAX依赖于具体机器）以及对整数可施加的加、减、乘、除和取模 等操作。

抽象数据类型可以看作是描述问题的模型，它独立于具体实现。它的优点是将数据和操作封装在一起，使得用户程序只能通过在ADT里定义的

某些操作来访问其中的数据，从而实现了信息隐藏。在C﹢﹢中，我们可以用类（包括模板类）的说明来表示ADT，用类的实现来实现ADT【参阅

[10]】。因此，C﹢﹢中实现的类相当于是数据的存储结构及其在存储结构上实现的对数据的操作。

ADT和类的概念实际上反映了程序或软件设计的两层抽象：ADT相当于是在概念层（或称为抽象层）上描述问题，而类相当于是在实现层上

描述问题。此外，C﹢﹢中的类只是一个由用户定义的普通类型，可用它来定义变量（称为对象或类的实例）。因此，在C﹢﹢中，最终是通过操

作对象来解决实际问题的，所以我们可将该层次看作是应用层。例如，main程序就可看作是用户的应用程序。

由于C语言中没有提供"类"这一数据类型，因此无法实现ADT，故我们不采用ADT的形式来描述数据结构，以节省篇幅。大家只要记住，它实 际上等价于我们定义的数据的逻辑结构以及在逻辑结构上定义的抽象操作。

void Error(char*message)

概论- 算法的描述和分析(一)

{

数据的运算通过算法(Algorithm)描述，讨论算法是数据结构课程的重要内容之一。 1．算法

非形式地说，算法是任意一个良定义的计算过程。它以一个或多个值作为输入，并产生一个或多个值作为输出。

（1）一个算法可以被认为是用来解决一个计算问题的工具。 （2）一个算法是一系列将输入转换为输出的计算步骤。

【例3．1】有这样一个排序问题：将一个数字序列排序为非降序。 该问题的形式定义由满足下述关系的输入输出序列构成： 输入：数字序列〈a 1 ,a 2 ,…,a n 〉。

输出：输出序列的一个枚举〈a 1 ',a 2 ',…，a n '〉使得a 1 '≤a 2 '≤…≤a 3 ' 对于一个输入实例〈31，41，59，26，41，58〉，排序算法应返回输出序列〈26，31，41，41，58，59〉。

（1）输入实例

输入实例：一个问题的输入实例是满足问题陈述中所给出的限制、为计算该问题的解所需要的所有输入构成的。

（2）正确的算法和不正确的算法

若一个算法对于每个输入实例均能终止并给出正确的结果，则称该算法是正确的。正确的算法解决了给定的计算问题。

一个不正确的算法是指对某些输入实例不终止，或者虽然终止但给出的结果不是所渴望得到的答案，一般只考虑正确的算法。

求解同一计算问题可能有许多不同的算法，究竟如何来评价这些算法的好坏以便从中选出较好的算法呢？

选用的算法首先应该是"正确"的。此外，主要考虑如下三点： ① 执行算法所耗费的时间；

② 执行算法所耗费的存储空间，其中主要考虑辅助存储空间； ③ 算法应易于理解，易于编码，易于调试等等。 2．算法性能选择

一个占存储空间小、运行时间短、其它性能也好的算法是很难做到的。原因是上述要求有时相互抵触：要节约算法的执行时间往往要以牺牲

更多的空间为代价；而为了节省空间可能要耗费更多的计算时间。因此我们只能根据具体情况有所侧重：

① 若该程序使用次数较少，则力求算法简明易懂； ② 对于反复多次使用的程序，应尽可能选用快速的算法； fprintf(stderr,"Error: % s \ n ", message) ; //输出错误信息 exit(1) ; //终止程序，返回1给操作系统

概论- 算法的描述和分析(二)

算法分析

1．评价算法好坏的标准

2．算法的描述

一个算法可以用自然语言、计算机程序语言或其它语言来说明，惟一的要求是该说明必须精确地描述计算过程。

一般而言，描述算法最合适的语言是介于自然语言和程序语言之间的伪语言。它的控制结构往往类似于Pascal、C等程序语言，但其中可使

用任何表达能力强的方法使算法表达更加清晰和简洁，而不至于陷入具体的程序语言的某些细节。

从易于上机验证算法和提高实际程序设计能力考虑，采用C语言描述算法。 【例3．2】定义一个输出错误信息后退出程序运行的错误处理函数，该函数将在后续的许多程序中用来简化处理代码。

# include <stdlib.h> //其中有exit的说明

# include <stdio.h> //其中有标准错误stderr的说明

③ 若待解决的问题数据量极大，机器的存储空间较小，则相应算法主要考虑如何节省空间。

3．算法的时间性能分析

【例3．5】一个图论问题的规模则是图中的顶点数或边数。

（1）算法耗费的时间和语句频度

一个算法所耗费的时间=算法中每条语句的执行时间之和

每条语句的执行时间=语句的执行次数(即频度(Frequency Count))×语句执行一次所需时间

算法转换为程序后，每条语句执行一次所需的时间取决于机器的指令性能、速度以及编译所产生的代码质量等难以确定的因素。

若要独立于机器的软、硬件系统来分析算法的时间耗费，则设每条语句执行一次所需的时间均是单位时间，一个算法的时间耗费就是该算法中所 有语句的频度之和。

)是算法MatrixMultiply的渐近时间复杂度。

【例3.3】求两个n阶方阵的乘积 C=A×B,其算法如下:

数学符号"O"的严格的数学定义：

# define n 100 // n 可根据需要定义,这里假定为100 void MatrixMultiply(int A[a]，int B [n][n]，int C[n][n]) { //右边列为各语句的频度 int i ,j ,k;

(1) for(i=0; i＜n;j++) n+1 (2) for (j=0;j＜n;j++) { n(n+1) (3) C[i][j]=0; n 2

(4) for (k=0; k＜n; k++) n 2 (n+1) (5) C[i][j]=C[i][j]+A[i][k]*B[k][j]; n 3 } }

该算法中所有语句的频度之和(即算法的时间耗费)为： T(n)=2n 3 +3n 2 +2n+1 (1.1) 分析：

语句(1)的循环控制变量i要增加到n，测试到i=n成立才会终止。故它的频度是n+1。但是它的循环体却只能执行n次。语句(2)作为语句(1)循

环体内的语句应该执行n次，但语句(2)本身要执行n+1次，所以语句(2)的频度是n(n+1)。同理可得语句(3)，(4)和(5)的频度分别是n 2 ，n 2 (n+1)和n 3 。

算法MatrixMultiply的时间耗费T(n)是矩阵阶数n的函数。

Temp=i;

（2）问题规模和算法的时间复杂度

杂度不予区分，而经常是将渐近时间复杂度T(n)=O(f(n))简称为时间复杂度，其中的f(n)一般是算法中频度最大的语句频度。

【例3．8】算法MatrixMultiply的时间复杂度一般为T(n)=O(n 3 )，f(n)=n 3 是该算法中语句(5)的频度。下面再举例说明如何求算法的时间复 杂度。

【例3．9】交换i和j的内容。

【例3．7】有两个算法A 1 和A 2 求解同一问题，时间复杂度分别是T 1 (n)=100n 2 ，T 2 (n)=5n 3 。

（1）当输入量n＜20时，有T 1 (n)＞T 2 (n)，后者花费的时间较少。 （2）随着问题规模n的增大，两个算法的时间开销之比5n 3 /100n 2 =n/20亦随着增大。即当问题规模较大时，算法A 1 比算法A 2 要有效地多

它们的渐近时间复杂度O(n 2 )和O(n 3 )从宏观上评价了这两个算法在时间方面的质量。在算法分析时，往往对算法的时间复杂度和渐近时间复

若T(n)和f(n)是定义在正整数集合上的两个函数，则T(n)=O(f(n))表示存在正的常数C和n0，使得当n≥n0时都满足0≤T(n)≤C·f(n)。

概论- 算法的描述和分析(三)

（3）渐进时间复杂度评价算法时间性能

主要用算法时间复杂度的数量级(即算法的渐近时间复杂度)评价一个算法的时间性能。

一个算法的时间复杂度(Time Complexity, 也称时间复杂性)T(n)是该算法的时间耗费，是该算法所求解问题规模n的函数。当问题的规模

n趋向无穷大时，时间复杂度T(n)的数量级(阶)称为算法的渐进时间复杂度。 【例3．6】算法MatrixMultidy的时间复杂度T(n)如(1.1)式所示，当n趋向无穷大时，显然有

这表明，当n充分大时，T(n)和n 3 之比是一个不等于零的常数。即T(n)和n 3 是同阶的，或者说T(n)和n 3 的数量级相同。记作T(n)=O(n 3 算法求解问题的输入量称为问题的规模(Size),一般用一个整数表示。 【例3．4】矩阵乘积问题的规模是矩阵的阶数。

i=j; j=temp;

以上三条单个语句的频度均为1，该程序段的执行时间是一个与问题规模n无关的常数。算法的时间复杂度为常数阶，记作T(n)=O(1)。

如果算法的执行时间不随着问题规模n的增加而增长，即使算法中有上千条语句，其执行时间也不过是一个较大的常数。此类算法的时间复杂度 是O(1)。

【例3．10】变量计数之一。 (1) x=0;y=0; (2) for(k-1;k<=n;k++) (3) x++;

(4) for(i=1;i<=n;i++) (5) for(j=1;j<=n;j++)

(6) y++;

一般情况下，对步进循环语句只需考虑循环体中语句的执行次数，忽略该语句中步长加1、终值判别、控制转移等成分。因此，以上程序段

中频度最大的语句是(6)，其频度为f(n)=n 2 ，所以该程序段的时间复杂度为T(n)=O(n 2 )。

当有若干个循环语句时，算法的时间复杂度是由嵌套层数最多的循环语句中最内层语句的频度f(n)决定的。 【例3．11】变量计数之二。 (1) x=1;

(2) for(i=1;i<=n;i++) (3) for(j=1;j<=i;j++) (4) for(k=1;k<=j;k++)

顺序表

(5) x++;

该程序段中频度最大的语句是(5)，内循环的执行次数虽然与问题规模n没有直接关系，但是却与外层循环的变量取值有关，而最外层循环的

次数直接与n有关，因此可以从内层循环向外层分析语句(5)的执行次数：

1． 顺序表的定义 (1) 顺序存储方法

即把线性表的结点按逻辑次序依次存放在一组地址连续的存储单元里的方法。

(2) 顺序表（Sequential List）

用顺序存储方法存储的线性表简称为顺序表（Sequential List）。

2． 结点ai 的存储地址

不失一般性，设线性表中所有结点的类型相同，则每个结点所占用存储空间大小亦相同。假设表中每个结点占用c个存储单元，其中第一个单元的存储地址则是该结点的存储地址，并设表中开始结点a1的存储地址（简称为基地址）是LOC（a1），那么结点ai的存储地址LOC（ai）可通过下式计算： LOC（ai）= LOC（a1）+（i-1）*c 1≤i≤n 注意：

在顺序表中，每个结点ai的存储地址是该结点在表中的位置i的线性函数。只要知道基地址和每个结点的大小，就可在相同时间内求出任一结点的存储地址。是一种随机存取结构。

顺序表

(1)i=n-1;

(2)while(i>=0&&(A[i]!=k)) (3) i--; (4)return i;

此算法中的语句(3)的频度不仅与问题规模n有关，还与输入实例中A的各元素取值及K的取值有关:

①若A中没有与K相等的元素，则语句(3)的频度f(n)=n； ②若A的最后一个元素等于K,则语句(3)的频度f(n)是常数0。 （5）最坏时间复杂度和平均时间复杂度

最坏情况下的时间复杂度称最坏时间复杂度。一般不特别说明，讨论的时间复杂度均是最坏情况下的时间复杂度。

这样做的原因是：最坏情况下的时间复杂度是算法在任何输入实例上运行时间的上界，这就保证了算法的运行时间不会比任何更长。

【例3．19】查找算法【例1·8】在最坏情况下的时间复杂度为T(n)=0(n)，它表示对于任何输入实例,该算法的运行时间不可能大于0(n)。

平均时间复杂度是指所有可能的输入实例均以等概率出现的情况下，算法的期望运行时间。

常见的时间复杂度按数量级递增排列依次为：常数0(1)、对数阶0(log 2 n)、线形阶0(n)、线形对数阶0(nlog 2 n)、平方阶0(n 2 )立方阶0(n

3 )、…、k次方阶0(n k )、指数阶0(2 n )。显然，时间复杂度为指数阶0(2 n )的算法效率极低，当n值稍大时就无法应用。

类似于时间复杂度的讨论，一个算法的空间复杂度(Space Complexity)S(n)定义为该算法所耗费的存储空间，它也是问题规模n的函数。渐近空

间复杂度也常常简称为空间复杂度。算法的时间复杂度和空间复杂度合称为算法的复杂度。

则该程序段的时间复杂度为T(n)=O(n 3 /6+低次项)=O(n 3 )。

（4）算法的时间复杂度不仅仅依赖于问题的规模，还与输入实例的初始状态有关。

【例3．12】在数值A[0..n-1]中查找给定值K的算法大致如下：

3．顺序表类型定义

#define ListSize 100 //表空间的大小可根据实际需要而定，这里假设为100 typedef int DataType; //DataType的类型可根据实际情况而定，这里假设为int typedef struct {

DataType data[ListSize]；//向量data用于存放表结点 int length；//当前的表长度 }SeqList； 注意：

① 用向量这种顺序存储的数组类型存储线性表的元素外，顺序表还应该用一个变量来表示线性表的长度属性，因此用结构类型来定义顺序表类型。

② 存放线性表结点的向量空间的大小ListSize应仔细选值，使其既能满足表结点的数目动态增加的需求，又不致于预先定义过大而浪费存储空间。 ③ 由于C语言中向量的下标从0开始，所以若L是SeqList类型的顺序表，则线性表的开始结点a1和终端结点an分别存储在L．data[0]和L．Data[L．length-1]中。

④ 若L是SeqList类型的指针变量，则a1和an分别存储在L-＞data[0]和L-＞data[L-＞length-1]中。

4．顺序表的特点

顺序表是用向量实现的线性表，向量的下标可以看作结点的相对地址。因此顺序表的的特点是逻辑上相邻的结点其物理位置亦相邻。

顺序表上实现的基本运算 顺序表上实现的基本运算

1.表的初始化

void InitList（SeqList *L）

{\\顺序表的初始化即将表的长度置为0 L-＞length=0； }

2.求表长

int ListLength（SeqList *L） { \\求表长只需返回L-＞length return L-＞length; }

3.取表中第i个结点

DataType GetNode（L，i）

{\\取表中第i个结点只需返回和L-＞data[i-1]即可 if (i<1||i> L-＞length-1)

Error("position error")； return L-＞data[i-1]； }

4.查找值为x的结点 【参见参考书】

5. 插入

（1） 插入运算的逻辑描述

线性表的插入运算是指在表的第i（1≤i≤n+1）个位置上，插入一个新结点x，使长度为n的线性表：

（a1，…，ai-1，ai，…an） 变成长度为n+1的线性表：

（a1，…，ai-1，x，ai，…an） 注意：

① 由于向量空间大小在声明时确定，当L-＞length≥ListSize时，表空间已满，不可再做插入操作

② 当插入位置i的值为i＞n或i＜1时为非法位置，不可做正常插入操作 （2） 顺序表插入操作过程

在顺序表中，结点的物理顺序必须和结点的逻辑顺序保持一致，因此必须将表中位置为n ，n-1，…，i上的结点，依次后移到位置n+1，n，…，i+1上，空出第i个位置，然后在该位置上插入新结点x。仅当插入位置i=n+1时，才无

须移动结点，直接将x插入表的末尾。 具体过程见【动画演示】

（3）具体算法描述

void InsertList(SeqList *L，DataType x，int i)

{//将新结点 x插入L所指的顺序表的第i个结点ai的位置上 int j;

if (i<1||i>L->length+1)

Error("position error");//非法位置，退出运行 if (L->length>=ListSize)

Error("overflow"); //表空间溢出，退出运行 for(j=L->length-1;j>=i-1;j--)

L->data[j+1]=L->data[j];//结点后移 L->data[i-1]=x; //插入x L->Length++; //表长加1 }

（4）算法分析 ① 问题的规模

表的长度L-＞length（设值为n）是问题的规模。 ② 移动结点的次数由表长n和插入位置i决定

算法的时间主要花费在for循环中的结点后移语句上。该语句的执行次数是n-i+1。

当i=n+1：移动结点次数为0，即算法在最好时间复杂度是0(1) 当i=1：移动结点次数为n，即算法在最坏情况下时间复杂度是0(n) ③ 移动结点的平均次数Eis(n) 其中：

在表中第i个位置插入一个结点的移动次数为n-i+1

pi表示在表中第i个位置上插入一个结点的概率。不失一般性，假设在表中任何合法位置（1≤i≤n+1）上的插入结点的机会是均等的，则 p1=p2=…=pn+1=1/(n+1)

因此，在等概率插入的情况下，

即在顺序表上进行插入运算，平均要移动一半结点

6． 删除

（1）删除运算的逻辑描述

线性表的删除运算是指将表的第i（1≤i≤n）个结点删去，使长度为n的线性表

（a1，…，ai-1，ai，ai+1，…，an） 变成长度为n-1的线性表

（a1，…，ai-1，ai+1，…，an） 注意：

当要删除元素的位置i不在表长范围（即i＜1或i＞L-＞length）时，为非法位置，不能做正常的删除操作

（2）顺序表删除操作过程

在顺序表上实现删除运算必须移动结点，才能反映出结点间的逻辑关系的变化。若i=n，则只要简单地删除终端结点，无须移动结点；若1≤i≤n-1，则必须将表中位置i+1，i+2，…，n的结点，依次前移到位置i，i+1，…，n-1上，以填补删除操作造成的空缺。其删除过程【参见动画演示】 （3）具体算法描述

void DeleteList(SeqList *L,int i)

{//从L所指的顺序表中删除第i个结点ai int j;

if(i<1||i>L->length)

Error("position error"); //非法位置 for(j=i;j<=L->length-1;j++)

L->data[j-1]=L->data[j]; //结点前移 L->length--; //表长减小 }

（4）算法分析

①结点的移动次数由表长n和位置i决定： i=n时，结点的移动次数为0，即为0(1)

i=1时，结点的移动次数为n-1，算法时间复杂度分别是0(n) ②移动结点的平均次数EDE(n)

其中：

删除表中第i个位置结点的移动次数为n-i

pi表示删除表中第i个位置上结点的概率。不失一般性，假设在表中任何合法位置（1≤i≤n）上的删除结点的机会是均等的，则 p1=p2=…=pn=1/n

因此，在等概率插入的情况下，

顺序表上做删除运算，平均要移动表中约一半的结点，平均时间复杂度也是0(n)。

单链表

单链表

1、链接存储方法

链接方式存储的线性表简称为链表（Linked List）。 链表的具体存储表示为：

① 用一组任意的存储单元来存放线性表的结点（这组存储单元既可以是连续的，也可以是不连续的）

② 链表中结点的逻辑次序和物理次序不一定相同。为了能正确表示结点间的逻辑关系，在存储每个结点值的同时，还必须存储指示其后继结点的地址（或位置）信息（称为指针（pointer）或链(link)） 注意：

链式存储是最常用的存储方式之一，它不仅可用来表示线性表，而且可用来表示各种非线性的数据结构。

2、链表的结点结构 ┌──┬──┐ │data│next│ └──┴──┘

data域--存放结点值的数据域

next域--存放结点的直接后继的地址（位置）的指针域（链域） 注意：

①链表通过每个结点的链域将线性表的n个结点按其逻辑顺序链接在一起的。

②每个结点只有一个链域的链表称为单链表（Single Linked List）。 【例】线性表（bat，cat，eat，fat，hat，jat，lat，mat）的单链表示如示意图

3、头指针head和终端结点指针域的表示

单链表中每个结点的存储地址是存放在其前趋结点next域中，而开始结点无前趋，故应设头指针head指向开始结点。 注意：

链表由头指针唯一确定，单链表可以用头指针的名字来命名。 【例】头指针名是head的链表可称为表head。

终端结点无后继，故终端结点的指针域为空，即NULL。

4、单链表的一般图示法

由于我们常常只注重结点间的逻辑顺序，不关心每个结点的实际位置，可以用箭头来表示链域中的指针，线性表（bat，cat，fat，hat，jat，lat，mat）的单链表就可以表示为下图形式。

单链表的运算 1、建立单链表

假设线性表中结点的数据类型是字符，我们逐个输入这些字符型的结点，并以换行符'\n'为输入条件结束标志符。动态地建立单链表 的常用方法有如下两种： （1） 头插法建表

5、单链表类型描述

typedef char DataType; //假设结点的数据域类型为字符 typedef struct node{ //结点类型定义 DataType data; //结点的数据域 struct node *next;//结点的指针域 }ListNode;

typedef ListNode *LinkList; ListNode *p; LinkList head; 注意：

①LinkList和ListNode *是不同名字的同一个指针类型（命名的不同是为了概念上更明确）

① 算法思路

从一个空表开始,重复读入数据,生成新结点,将读入数据存放在新结点的数据域中,然后将新结点插入到当前链表的表头上,直到读入结束标志为止。 具体方法【 参见动画演示 】 注意：

该方法生成的链表的结点次序与输入顺序相反。

┌────┬────────────┬─────────────┐

│ │ 指针变量 │ 结点变量 │ ├────┼────────────┼─────────────┤

│ 定义 │在变量说明部分显式定义 │在程序执行时，通过标准 │ │ │ │函数malloc生成 │ ├────┼────────────┼─────────────┤

│ 取值 │ 非空时，存放某类型结点 │实际存放结点各域内容 │ │ │的地址 │ │

├────┼────────────┼─────────────┤

│操作方式│ 通过指针变量名访问 │ 通过指针生成、访问和释放 │ └────┴────────────┴─────────────┘

①生成结点变量的标准函数

p=( ListNode *)malloc(sizeof(ListNode))；

//函数malloc分配一个类型为ListNode的结点变量的空间,并将其首地址放入指针变量p中

②释放结点变量空间的标准函数

free(p)；//释放p所指的结点变量空间 ③结点分量的访问

利用结点变量的名字*p访问结点分量 方法一：(*p).data和(*p).next 方法二：p-﹥data和p-﹥next

④指针变量p和结点变量*p的关系 指针变量p的值——结点地址 结点变量*p的值——结点内容

(*p).data的值——p指针所指结点的data域的值 (*p).next的值——*p后继结点的地址 *((*p).next)——*p后继结点 注意：

① 若指针变量p的值为空（NULL），则它不指向任何结点。此时，若通过*p来访问结点就意味着访问一个不存在的变量，从而引起程序的错误。 ② 有关指针类型的意义和说明方式的详细解释

线性表 - 链式存储结构- 单链表的运算（一）

②LinkList类型的指针变量head表示它是单链表的头指针 ③ListNode *类型的指针变量p表示它是指向某一结点的指针 6、指针变量和结点变量

② 具体算法实现 LinkList CreatListF(void) {//返回单链表的头指针 char ch;

LinkList head;//头指针 ListNode *s; //工作指针 head=NULL; //链表开始为空 ch=getchar(); //读入第1个字符 while(ch!='\n'){

s=(ListNode *)malloc(sizeof(ListNode));//生成新结点 s->data=ch; //将读入的数据放入新结点的数据域中 s->next=head; head=s;

ch=getchar(); //读入下一字符 }

return head; }

2） 尾插法建表 ① 算法思路

从一个空表开始,重复读入数据,生成新结点,将读入数据存放在新结点的数据域中,然后将新结点插入到当前链表的表尾上,直到读入结束标志为止。

ListNode *s,*r; //工作指针 head=NULL; //链表开始为空 r=NULL;//尾指针初值为空 ch=getchar(); //读入第1个字符 while(ch!='\n'){

s=(ListNode *)malloc(sizeof(ListNode));//生成新结点 s->data=ch; //将读入的数据放入新结点的数据域中 if (head!=NULL) head=s;//新结点插入空表 else

r->next=s;//将新结点插到*r之后 r=s;//尾指针指向新表尾 ch=getchar(); //读入下一字符 }//endwhile if (r!=NULL)

r->next=NULL;//对于非空表，将尾结点指针域置空head=s; return head; } 注意：

⒈开始结点插入的特殊处理

由于开始结点的位置是存放在头指针(指针变量)中,而其余结点的位置是在其前趋结点的指针域中，插入开始结点时要将头指针指向

具体方法【 参见动画演示 】 注意：

⒈采用尾插法建表，生成的链表中结点的次序和输入顺序一致 ⒉必须增加一个尾指针r,使其始终指向当前链表的尾结点

② 具体算法实现

（3） 尾插法建带头结点的单链表

LinkList CreatListR(void)

①头结点及作用

{//返回单链表的头指针

头结点是在链表的开始结点之前附加一个结点。它具有两个优点:

char ch;

LinkList head;//头指针

⒈由于开始结点的位置被存放在头结点的指针域中,所以在链表的第一个位置上的操作就和在表的其它位置上操作一致,无须进行 开始结点。

⒉空表和非空表的不同处理

若读入的第一个字符就是结束标志符,则链表head是空表,尾指针r亦为空,结点*r不存在;否则链表head非空,最后一个尾结点*r是终端结点,应将其指针域置空。

特殊处理;

⒉无论链表是否为空，其头指针都是指向头结点的非空指针（空表中头结点的指针域空），因此空表和非空表的处理也就统一了 。

②带头结点的单链表 注意：

头结点数据域的阴影表示该部分不存储信息。在有的应用中可用于存放表长等附加信息。

③尾插法建带头结点链表算法 LinkList CreatListR1(void) {//用尾插法建立带头结点的单链表 char ch;

LinkList head=(ListNode *)malloc(sizeof(ListNode));//生成头结点 ListNode *s,*r; //工作指针

r=head; // 尾指针初值也指向头结点 while((ch=getchar())!='\n'){

s=(ListNode *)malloc(sizeof(ListNode));//生成新结点 s->data=ch; //将读入的数据放入新结点的数据域中 r->next=s; r=s; }

r->next=NULL;//终端结点的指针域置空，或空表的头结点指针域置空 return head; } 注意：

上述算法里，动态申请新结点空间时未加错误处理，这对申请空间极少的程序而言不会出问题。但在实用程序里，尤其是对空间需求

较大的程序，凡是涉及动态申请空间，一定要加入错误处理以防系统无空间可供分配。

（4） 算法时间复杂度

（2） 按值查找

以上三个算法的时间复杂度均为0(n)。

①思想方法

2.单链表的查找运算 （1）按序号查找

从开始结点出发，顺着链逐个将结点的值和给定值key作比较，若有结点的值与key相等，则返回首次找到的其值为key的结点的存储

计数器j置为0后，扫描指针p指针从链表的头结点开始顺着链扫描。当p扫描下一个结点时，计数器j相应地加1。当j=i时，指针

p所指的结点就是要找的第i个结点。而当p指针指为null且j≠i时，则表示找不到第i个结点。 注意：

头结点可看做是第0个结点。 ③具体算法实现

ListNode* GetNode(LinkList head,int i)

{//在带头结点的单链表head中查找第i个结点，若找到（0≤i≤n）， //则返回该结点的存储位置，否则返回NULL。 int j; ListNode *p;

p=head;j=0;//从头结点开始扫描

while(p->next&&j<i){//顺指针向后扫描，直到p->next为NULL或i=j为止 p=p->next; j++; } if(i==j)

return p;//找到了第i个结点

else return NULL;//当i<0或i>0时，找不到第i个结点 }

④算法分析

算法中，while语句的终止条件是搜索到表尾或者满足j≥i，其频度最多为i，它和被寻找的位置有关。在等概率假设下，平均时间复杂度为： ① 链表不是随机存取结构

在链表中，即使知道被访问结点的序号i，也不能像顺序表中那样直接按序号i访问结点，而只能从链表的头指针出发，顺链域

next逐个结点往下搜索，直至搜索到第i个结点为止。因此，链表不是随机存取结构。

② 查找的思想方法

位置；否则返回NULL。 ②具体算法实现

ListNode* LocateNode (LinkList head,DataType key) {//在带头结点的单链表head中查找其值为key的结点

ListNode *p=head->next;//从开始结点比较。表非空，p初始值指向开始结点 while(p&&p->data!=key)//直到p为NULL或p->data为key为止 p=p->next;//扫描下一结点

return p;//若p=NULL，则查找失败，否则p指向值为key的结点 }

③算法分析

该算法的执行时间亦与输入实例中key的取值相关，其平均时间复杂度分析类似于按序号查找，为O(n)。

性表 - 链式存储结构- 单链表的运算（五）

}

（3）算法分析

算法的时间主要耗费在查找操作GetNode上，故时间复杂度亦为O(n)。 4.删除运算 （1）思想方法

3.插入运算

删除运算是将表的第i个结点删去。 具体步骤：

（1）找到a i-1 的存储位置p（因为在单链表中结点a i 的存储地址是在其直接前趋结点a i-1 的指针域next中）

（2）令p-＞next指向a i 的直接后继结点（即把a i 从链上摘下） （3）释放结点a i 的空间，将其归还给"存储池"。

具体操作过程【 参见动画演示 】

（1）思想方法

（2）具体算法实现

插入运算是将值为x的新结点插入到表的第i个结点的位置上，即插入到a i-1 与a i 之间。 具体步骤：

（1）找到a i-1 存储位置p

（2）生成一个数据域为x的新结点*s （3）令结点*p的指针域指向新结点

void DeleteList(LinkList head,int i)

{//删除带头结点的单链表head上的第i个结点 ListNode *p,*r;

p=GetNode(head,i-1);//找到第i-1个结点

if (p==NULL||p->next==NULL)//i<1或i>n时，删除位置错

（4）新结点的指针域指向结点a i 。

具体插入过程【 参见动画演示 】 （2）具体算法实现

void InsertList(LinkList head,DataType x,int i)

{//将值为x的新结点插入到带头结点的单链表head的第i个结点的位置上 ListNode *p;

p=GetNode(head,i-1);//寻找第i-1个结点 if (p==NULL)//i<1或i>n+1时插入位置i有错 Error("position error")；

s=(ListNode *)malloc(sizeof(ListNode)); s->data=x;s->next=p->next;p->next=s;

注意：

判断空链表的条件为rear==rear->next;

4、循环链表的特点

循环链表的特点是无须增加存储量，仅对表的链接方式稍作改变，即可使得表处理更加方便灵活。

【例】在链表上实现将两个线性表（a1，a2，…，an）和（b1，b2，…，bm）连接成一个线性表（a1，…，an，b1，…bm）

分析：若在单链表或头指针表示的单循环表上做这种链接操作，都需要遍历第一个链表，找到结点an，然后将结点b1链到an的后面，其执行时间是O(n)。若在尾指针表示的单循环链表上实现，则只需修改指针，无须遍历，其执行时间是O(1)。

相应的算法如下：

LinkList Connect(LinkList A,LinkList B) {//假设A，B为非空循环链表的尾指针

LinkList p=A->next;//①保存A表的头结点位置

A->next=B->next->next;//②B表的开始结点链接到A表尾 free(B->next);//③释放B表的头结点 B->next=p;//④

return B;//返回新循环链表的尾指针 } 注意：

①循环链表中没有NULL指针。涉及遍历操作时，其终止条件就不再是像非循环链表那样判别p或p-＞next是否为空，而是判别它们是否等于某一指定指针，如头指针或尾指针等。

②在单链表中，从一已知结点出发，只能访问到该结点及其后续结点，无法找到该结点之前的其它结点。而在单循环链表中，从任一结点出发都可访问到表中所有结点，这一优点使某些运算在单循环链表上易于实现。

双链表

http://www.77cn.com.cn 作者：不详 来源： 2006年8月25日 发表评论 进

入社区

双链表

1、双向链表（Double Linked List）

双（向）链表中有两条方向不同的链，即每个结点中除next域存放后继结点地址外，还增加一个指向其直接前趋的指针域prior。

注意：

①双链表由头指针head惟一确定的。

②带头结点的双链表的某些运算变得方便。

③将头结点和尾结点链接起来，为双（向）循环链表。 2、双向链表的结点结构和形式描述 ①结点结构(见上图a) ②形式描述

typedef struct dlistnode{ DataType data;

struct dlistnode *prior,*next; }DListNode;

typedef DListNode *DLinkList; DLinkList head;

3、双向链表的前插和删除本结点操作

由于双链表的对称性，在双链表能能方便地完成各种插入、删除操作。 ①双链表的前插操作

void DInsertBefore(DListNode *p,DataType x)

{//在带头结点的双链表中，将值为x的新结点插入*p之前，设p≠NULL

Error("position error");//退出程序运行 r=p->next;//使r指向被删除的结点a i p->next=r->next;//将a i 从链上摘下 free(r);//释放结点a i 的空间给存储池 } 注意：

设单链表的长度为n，则删去第i个结点仅当1≤i≤n时是合法的。 当i=n+1时，虽然被删结点不存在，但其前趋结点却存在，它是终端结点。因此被删结点的直接前趋*p存在并不意味着被删结点

就一定存在，仅当*p存在（即p！=NULL）且*p不是终端结点（即p-＞next！=NULL）时，才能确定被删结点存在。 （3）算法分析

算法的时间复杂度也是O（n）。

链表上实现的插入和删除运算，无须移动结点，仅需修改指针。

循环链表

http://www.77cn.com.cn 作者：不详 来源： 2006年8月25日 发表评论 进

入社区 循环链表（Circular Linked List） 循环链表是一种首尾相接的链表。

1、循环链表

（1）单循环链表——在单链表中，将终端结点的指针域NULL改为指向表头结点或开始结点即可。

（2）多重链的循环链表——将表中结点链在多个环上。

2、带头结点的单循环链表

注意：

判断空链表的条件是head==head->next;

3、仅设尾指针的单循环链表

用尾指针rear表示的单循环链表对开始结点a1和终端结点an查找时间都是O(1)。而表的操作常常是在表的首尾位置上进行，因此，实用中多采用尾指针表示单循环链表。带尾指针的单循环链表可见下图。

DListNode *s=malloc(sizeof(DListNode));//① s->data=x;//②

s->prior=p->prior;//③ s->next=p;//④

p->prior->next=s;//⑤ p->prior=s;//⑥ }

②双链表上删除结点*p自身的操作

void DDeleteNode(DListNode *p)

{//在带头结点的双链表中，删除结点*p，设*p为非终端结点 p->prior->next=p->next;//① p->next->prior=p->prior;//② free(p);//③ } 注意：

与单链表上的插入和删除操作不同的是，在双链表中插入和删除必须同时修改两个方向上的指针。

上述两个算法的时间复杂度均为O(1)。

顺序表和链表的比较

顺序表和链表的比较

顺序表和链表各有短长。在实际应用中究竟选用哪一种存储结构呢？这要根据具体问题的要求和性质来决定。通常有以下几方面的考虑： ┌───┬───────────────┬───────────────┐ │ │ 顺序表 │ 链表 │ ├─┬─┼───────────────┼───────────────┤

│基│分│静态分配。程序执行之前必须明确│动态分配只要内存空间尚有空闲，│

│于│配│规定存储规模。若线性表长度n变 │就不会产生溢出。因此，当线性表│

│空│方│化较大，则存储规模难于预先确定│的长度变化较大，难以估计其存储│

│间│式│估计过大将造成空间浪费，估计太│规模时，以采用动态链表作为存储│

│考│ │小又将使空间溢出机会增多。 │结构为好。 │ │虑├─┼───────────────┼───────────────┤

│ │存│为1。当线性表的长度变化不大， │<1 │ │ │储│易于事先确定其大小时，为了节约│ │ │ │密│存储空间，宜采用顺序表作为存储│ │ │ │度│结构。 │ │

├─┼─┼───────────────┼───────────────┤

│基│存│随机存取结构，对表中任一结点都│顺序存取结构，链表中的结点，需│

│于│取│可在O（1）时间内直接取得 │从头指针起顺着链扫描才能取得。│ │时│方│线性表的操作主要是进行查找，很│ │ │间│法│少做插入和删除操作时，采用顺序│ │ │考│ │表做存储结构为宜。 │ │ │虑├─┼───────────────┼───────────────┤

│ │插│在顺序表中进行插入和删除，平均│在链表中的任何位置上进行插入和│

│ │入│要移动表中近一半的结点，尤其是│删除，都只需要修改指针。对于频│

│ │删│当每个结点的信息量较大时，移动│繁进行插入和删除的线性表，宜采│

│ │除│结点的时间开销就相当可观。 │用链表做存储结构。若表的插入和│ │ │操│ │删除主要发生在表的首尾两端，则│ │ │作│ │采用尾指针表示的单循环链表为宜│ └─┴─┴───────────────┴───────────────┘

存储密度（Storage Density）是指结点数据本身所占的存储量和整个结点结构所占的存储量之比，即

存储密度=（结点数据本身所占的存储量）/（结点结构所占的存储总量）

栈和队列 - 栈 - 栈的定义及基本运算

栈和队列是两种特殊的线性表，它们的逻辑结构和线性表相同，只是其运算规则较线性表有更多的限制，故又称它们为运算受限 的线性表。栈和队列被广泛应用于各种程序设计中。

栈的定义及基本运算 1、栈的定义

栈（Stack）是限制仅在表的一端进行插入和删除运算的线性表。 (1)通常称插入、删除的这一端为 栈顶 （Top），另一端称为 栈底 （Bottom）。

(2)当表中没有元素时称为 空栈 。

(3)栈为后进先出（Last In First Out）的线性表，简称为 LIFO表 。 栈的修改是按后进先出的原则进行。每次删除（ 退栈 ）的总是当前栈中"最新"的元素，即最后插入（ 进栈 ）的元素，而最先 插入的是被放在栈的底部，要到最后才能删除。

【示例】元素是以a 1 ，a 2 ，…，a n 的顺序进栈，退栈的次序却是a n ，a n-1 ，…，a 1 。 2、栈的基本运算 （1）InitStack（S） 构造一个空栈S。 （2）StackEmpty（S）

判栈空。若S为空栈，则返回TRUE，否则返回FALSE。 （3）StackFull（S）

判栈满。若S为满栈，则返回TRUE，否则返回FALSE。 注意：

该运算只适用于栈的顺序存储结构。 （4）Push（S，x）

进栈。若栈S不满，则将元素x插入S的栈顶。 （5）Pop（S）

退栈。若栈S非空，则将S的栈顶元素删去，并返回该元素。 （6）StackTop（S）

取栈顶元素。若栈S非空，则返回栈顶元素，但不改变栈的状态 顺序栈

栈的顺序存储结构简称为顺序栈,它是运算受限的顺序表。 1、 顺序栈的类型定义

#define StackSize 100 //假定预分配的栈空间最多为100个元素 typedef char DataType;//假定栈元素的数据类型为字符 typedef struct{

DataType data[StackSize]; int top; }SeqStack; 注意：

①顺序栈中元素用向量存放

②栈底位置是固定不变的，可设置在向量两端的任意一个端点

③栈顶位置是随着进栈和退栈操作而变化的，用一个整型量top（通常称top为栈顶指针）来指示当前栈顶位置 2、 顺序栈的基本操作

}

前提条件：

（4） 进栈

设S是SeqStack类型的指针变量。若栈底位置在向量的低端，即S-＞data[0]是栈底元素。 （1） 进栈操作

进栈时，需要将S-＞top加1 注意：

①S-＞top==StackSize-1表示栈满

②" 上溢 "现象--当栈满时，再做进栈运算产生空间溢出的现象。

void Push（S，x） {

if (StackFull(S))

Error("Stack overflow"); //上溢，退出运行 S->data[++S->top]=x;//栈顶指针加1后将x入栈 上溢是一种出错状态，应设法避免。 （2） 退栈操作

退栈时，需将S-＞top减1 注意：

①S-＞top<0表示空栈

②" 下溢 "现象——当栈空时，做退栈运算产生的溢出现象。 下溢是正常现象，常用作程序控制转移的条件。

顺序栈在进栈和退栈操作时的具体变化情况【 参见动画演示 】 3、顺序栈的基本运算 （1） 置栈空

void InitStack（SeqStack *S） {//将顺序栈置空 S->top=-1; }

（2） 判栈空

int StackEmpty（SeqStack *S） {

return S->top==-1; }

（3） 判栈满

int StackFull（SeqStack *SS） {

return S->top==StackSize-1;

}

（5） 退栈 DataType Pop（S） {

if(StackEmpty(S))

链栈的类型说明如下：

Error("Stack underflow"); //下溢，退出运行

return S->data[S->top--];//栈顶元素返回后将栈顶指针减1 }

（6） 取栈顶元素 DataType StackTop（S） {

if(StackEmpty(S)) Error("Stack is empty"); return S->data[S->top];

①LinkStack结构类型的定义是为了方便在函数体中修改top指针本身

}

②若要记录栈中元素个数，可将元素个数属性放在LinkStack类型中定义。

4、两个栈共享同一存储空间

当程序中同时使用两个栈时，可以将两个栈的栈底设在向量空间的两端，让

2、链栈的基本运算 （1） 置栈空

Void InitStack(LinkStack *S) {

S->top=NULL; }

（2） 判栈空

int StackEmpty(LinkStack *S)

只有当整个向量空间被两个栈占满（即两个栈顶相遇）时，才会发生上溢。因此，两个栈共享一个长度为m的向量空间和两个栈分别

占用两个长度为 └ m/2┘ 和┌m/2┐的向量空间比较，前者发生上溢的概率比后者要小得多。

（3） 进栈

栈和队列 - 栈 - 链栈

void Push(LinkStack *S,DataType x)

{//将元素x插入链栈头部

StackNode *p=(StackNode *)malloc(sizeof(StackNode));

{

return S->top==NULL; }

typedef struct stacknode{ DataType data struct stacknode *next }StackNode; typedef struct{

StackNode *top; //栈顶指针 }LinkStack; 注意：

链栈

栈的链式存储结构称为链栈。

1、链栈的类型定义

链栈是没有附加头结点的运算受限的单链表。栈顶指针就是链表的头指针。

两个栈各自向中间延伸。当一个栈里的元素较多，超

过向量空间的一半时，只要另一个栈的元素不多，那么前者就可以占用后者的部分存储空间。

p->data=x;

p->next=S->top;//将新结点*p插入链栈头部 S->top=p;

}

（1）允许删除的一端称为 队头（Front） 。

（4） 退栈

（2）允许插入的一端称为 队尾（Rear） 。

DataType Pop(LinkStack *S)

（3）当队列中没有元素时称为 空队列 。

{

（4）队列亦称作先进先出（First In First Out）的线性表，简称为 FIFO表 。

DataType x;

StackNode *p=S->top;//保存栈顶指针 if(StackEmpty(S))

Error("Stack underflow."); //下溢 x=p->data; //保存栈顶结点数据

2 ，…，a n 。

S->top=p->next; //将栈顶结点从链上摘下

2、队列的基本逻辑运算

free(p);

（1）InitQueue（Q）

return x;

置空队。构造一个空队列Q。

}

（2）QueueEmpty（Q）

（5） 取栈顶元素

判队空。若队列Q为空，则返回真值，否则返回假值。

DataType StackTop(LinkStack *S)

（3） QueueFull（Q）

{

判队满。若队列Q为满，则返回真值，否则返回假值。

if(StackEmpty(S))

注意：

Error("Stack is empty.")

此操作只适用于队列的顺序存储结构。

return S->top->data;

（4） EnQueue（Q，x）

}

若队列Q非满，则将元素x插入Q的队尾。此操作简称 入队 。

注意：

（5） DeQueue（Q）

链栈中的结点是动态分配的，所以可以不考虑上溢，无须定义StackFull运算。

若队列Q非空，则删去Q的队头元素，并返回该元素。此操作简称 出队 。

栈和队列 - 队列 - 队列的定义及基本运算

（6） QueueFront（Q）

若队列Q非空，则返回队头元素，但不改变队列Q的状态。

1、定义

栈和队列 - 队列 - 顺序队列

队列（Queue）是只允许在一端进行插入，而在另一端进行删除的运算受限

的线性表

队列的修改是依先进先出的原则进行的。新来的成员总是加入队尾（即不允许"加塞"），每次离开的成员总是队列头上的（不允 许中途离队），即当前"最老的"成员离队。

【例】在队列中依次加入元素a 1 ，a 2 ，…，a n 之后，a 1 是队头元素，a n 是队尾元素。退出队列的次序只能是a 1 ，a

顺序队列

当队列满时，做进栈运算产生空间溢出的现象。“真上溢”是一种出错状态，应设法避免。 ③ "假上溢"现象

由于入队和出队操作中，头尾指针只增加不减小，致使被删元素的空间永远无法重新利用。当队列中实际的元素个数远远小于

向量空间的规模时，也可能由于尾指针已超越向量空间的上界而不能做入队操作。该现象称为"假上溢"现象。

【例】假设下述操作序列作用在初始为空的顺序队列上： EnQueue，DeQueue，EnQueue，DeQueue，…

尽管在任何时刻，队列元素的个数均不超过1，但是只要该序列足够长，事先定义的向量空间无论多大均会产生指针越界错误。

栈和队列 - 队列 - 链队列

1、顺序队列 （1）顺序队列的定义

队列的顺序存储结构称为顺序队列，顺序队列实际上是运算受限的顺序表。 （2） 顺序队列的表示

①和顺序表一样，顺序队列用一个向量空间来存放当前队列中的元素。 ②由于队列的队头和队尾的位置是变化的，设置两个指针front和rear分别指示队头元素和队尾元素在向量空间中的位置，它 们的初值在队列初始化时均应置为0。

（3） 顺序队列的基本操作

①入队时：将新元素插入rear所指的位置，然后将rear加1。

②出队时：删去front所指的元素，然后将front加1并返回被删元素。 注意：

①当头尾指针相等时，队列为空。

②在非空队列里，队头指针始终指向队头元素，尾指针始终指向队尾元素的下一位置。

顺序队列基本操作【 参见动画演示 】 （4）顺序队列中的溢出现象 ① "下溢"现象

当队列为空时，做出队运算产生的溢出现象。“下溢”是正常现象，常用作程序控制转移的条件。 ② "真上溢"现象

1、 链队列的定义

队列的链式存储结构简称为链队列。它是限制仅在表头删除和表尾插入的单链表。

2、 链队列的结构类型说明 注意：

增加指向链表上的最后一个结点的尾指针，便于在表尾做插入操作。 链队列示意图见上图，图中Q为LinkQueue型的指针。 3、 链队列的基本运算 （1） 置空队

void InitQueue(LinkQueue *Q) {

Q->front=Q->rear=NULL; }

（2） 判队空

intQueueEmpty(LinkQueue *Q) {

return Q->front==NULL&&Q->rear==Null; //实际上只须判断队头指针是否为空即可 }

（3） 入队

void EnQueue(LinkQueue *Q,DataType x) {//将元素x插入链队列尾部

QueueNode *p=(QueueNode *)malloc(sizeof(QueueNode));//申请新结点 p->data=x; p->next=NULL; if(QueueEmpty(Q))

Q->front=Q->rear=p; //将x插入空队列 else { //x插入非空队列的尾

指针，且删去此结点后队列变空。

Q->rear->next=p; //*p链到原队尾结点后 Q->rear=p; //队尾指针指向新的尾 } }

（4） 出队

串的基本概念

DataType DeQueue (LinkQueue *Q) {

DataType x; QueueNode *p; if(QueueEmpty(Q))

Error("Queue underflow");//下溢 p=Q->front; //指向对头结点 x=p->data; //保存对头结点的数据

Q->front=p->next; //将对头结点从链上摘下

if(Q->rear==p)//原队中只有一个结点，删去后队列变空，此时队头指针已为空 Q->rear=NULL;

free(p); //释放被删队头结点

1、串

串（String）是零个或多个字符组成的有限序列。一般记为 S="a1a2……an" 其中

①S是串名

②双引号括起的字符序列是串值；

将串值括起来的双引号本身不属于串,它的作用是避免串与常数或与标识符混淆。

【例】"123"是数字字符串，它不同于整常数123

【例】"xl"是长度为2的字符串，而xl通常表示一个标识符。 ③ai（1≤i≤n）可以是字母、数字或其它字符； ④串中所包含的字符个数称为该串的长度。

2、空串和空白串

长度为零的串称为空串（Empty String），它不包含任何字符。 仅由一个或多个空格组成的串称为空白串（Blank String）。 注意：

空串和空白串的不同。

【例】″ ″和″″分别表示长度为1的空白串和长度为0的空串。

3、子串和主串

串中任意个连续字符组成的子序列称为该串的子串。包含子串的串相应地称为主串。

通常将子串在主串中首次出现时，该子串首字符对应的主串中的序号定义为子串在主串中的序号（或位置）。 【例】设A和B分别为 A="This is a string"

③以上讨论的是无头结点链队列的基本运算。和单链表类似，为了简化边界条件的处理，在队头结点前也可附加一个头结点，增 加头结点的链队列的基本运算【参见练习】

串的基本概念

http://www.77cn.com.cn 作者：不详 来源：不详 2006年8月7日 发表评论

进入社区 return x; //返回原队头数据 }

（5） 取队头元素

DataType QueueFront(LinkQueue *Q) {

if(QueueEmpty(Q)) Error("Queue if empty."); return Q->front->data; } 注意：

①和链栈类似，无须考虑判队满的运算及上溢。

②在出队算法中，一般只需修改队头指针。但当原队中只有一个结点时，该结点既是队头也是队尾，故删去此结点时亦需修改尾

B="is"

则B是A的子串，B在A中出现了两次。其中首次出现对应的主串位置是3。因此称B在A中的序号（或位置）是3。 注意：

①空串是任意串的子串 ②任意串是其自身的子串。

4、串变量和串常量

通常在程序中使用的串可分为：串变量和串常量。 （1）串变量

串变量和其它类型的变量一样，其取值是可以改变的。

（2）串常量

串常量和整常数、实常数一样，在程序中只能被引用但不能改变其值。即只能读不能写。

①串常量由直接量来表示的：

【例】Error（"overflow"）中"overflow"是直接量。 ②串常量命名

有的语言允许对串常量命名，以使程序易读、易写。 【例】C++中，可定义串常量path const char path[]="dir/bin/appl";

串的基本运算

http://www.77cn.com.cn 作者：不详 来源： 2006年8月25日 发表评论 进

入社区

串的基本运算

对于串的基本运算，很多高级语言均提供了相应的运算符或标准的库函数来实现。

为叙述方便，先定义几个相关的变量：

char s1[20]="dir/bin/appl",s2[20]="file.asm",s3[30],*p; int result;

下面以C语言中串运算介绍串的基本运算 1、求串长

int strlen(char *s);//求串s的长度

【例】printf("%d",strlen(s1)); //输出s1的串长12

2、串复制

char *strcpy(char *to,*from)；//将from串复制到to串中，并返回to开始处指针

【例】strcpy(s3,s1); //s3="dir/bin/appl",s1串不变

3、联接

char *strcat(char *to,char *from);//将from串复制到to串的末尾， //并返回to串开始处的指针 【例】strcat(s3,"/"); //s3="dir/bin/appl/" strcat(s3,s2); //s3="dir/bin/appl/file.asm"

4、串比较

int strcmp(char *s1,char *s2);//比较s1和s2的大小，

//当s1<s2、s1>s2和s1=s2时，分别返回小于0、大于0和等于0的值 【例】result=strcmp("baker","Baker"); //result>0 result=strcmp("12","12"); //result=0 result=strcmp("Joe","joseph") //result<0

5、字符定位

char *strchr(char *s,char c);//找c在字符串s中第一次出现的位置， //若找到，则返回该位置，否则返回NULL 【例】p=strchr(s2,'.'); //p指向"file"之后的位置 if(p) strcpy(p,".cpp"); //s2="file.cpp"

注意：

①上述操作是最基本的，其中后 4个操作还有变种形式：strncpy，strncath和strnchr。

②其它的串操作见C的<string.h>。在不同的高级语言中，对串运算的种类

及符号都不尽相同

③其余的串操作一般可由这些基本操作组合而成 【例】求子串的操作可如下实现：

void substr(char *sub,char *s,int pos,int len){

//s和sub是字符数组，用sub返回串s的第pos个字符起长度为len的子串 //其中0<=pos<=strlen(s)-1,且数组sub至少可容纳len+1个字符。 if (pos<0||pos>strlen(s)-1||len<0) Error("parameter error!");

strncpy(sub,&s[pos],len);//从s[pos]起复制至多len个字符到sub }//substr

串的顺序存储

http://www.77cn.com.cn 作者：不详 来源： 2006年8月25日 发表评论 进

入社区 因为串是特殊的线性表，故其存储结构与线性表的存储结构类似。只不过由于组成串的结点是单个字符，所以存储时有一些特殊的技巧。 串的顺序存储

1 、顺序串

串的顺序存储结构简称为顺序串。

与顺序表类似，顺序串是用一组地址连续的存储单元来存储串中的字符序列。因此可用高级语言的字符数组来实现，按其存储分配的不同可将顺序串分为如下两类：

（1）静态存储分配的顺序串 （2）动态存储分配的顺序串

2、静态存储分配的顺序串

（1）直接使用定长的字符数组来定义 该种方法顺序串的具体描述：

#define MaxStrSize 256 //该值依赖于应用，由用户定义

typedef char SeqString[MaxStrSize]; //SeqString是顺序串类型 SeqString S; //S是一个可容纳255个字符的顺序串 注意：

①串值空间的大小在编译时刻就已确定，是静态的。难以适应插入、链接等操作

②直接使用定长的字符数组存放串内容外，一般可使用一个不会出现在串中的特殊字符放在串值的末尾来表示串的结束。所以串空间最大值为MaxStrSize时，最多只能放MaxStrSize-1个字符。

【例】C语言中以字符'\0'表示串值的终结。

（2）类似顺序表的定义

直接使用定长的字符数组存放串内容外，可用一个整数来表示串的长度。此时顺序串的类型定义完全和顺序表类似： typedef struct{

char ch[MaxStrSize]; //可容纳256个字符，并依次存储在ch[0..n]中 int length; }SeqString;

注意：

①串的长度减1的位置就是串值的最后一个字符的位置。 ②这种表示的优点是涉及串长的操作速度快。

3、动态存储分配的顺序串

顺序串的字符数组空间可使用C语言的malloc和free等动态存储管理函数，来根据实际需要动态地分配和释放。

这样定义的顺序串类型亦有两种形式。 （1）较简单的定义

typedef char *string; //C中的串库<string.h>相当于使用此类型定义串 （2）复杂定义 typedef struct{

char *ch;// 若串非空，则按实际的串长分配存储区，否则ch为NULL int length; }HString;

串的顺序存储操作【参见动画演示】

串的链式存储

http://www.77cn.com.cn 作者：不详 来源： 2006年8月25日 发表评论 进

入社区

串的链式存储

1、链串

用单链表方式存储串值，串的这种链式存储结构简称为链串。

2、链串的结构类型定义 typedef struct node{ char data;

struct node *next;

}LinkStrNode; //结点类型

typedef LinkStrNode *LinkString; //LinkString为链串类型 LinkString S; //S是链串的头指针

注意：

①链串和单链表的差异仅在于其结点数据域为单个字符： ②一个链串由头指针唯一确定。

3、 链串的结点大小

通常，将结点数据域存放的字符个数定义为结点的大小。结点的大小的值越大，存储密度越高。 （1）结点大小为1的链串

【例】串值为"abcdef"的结点大小为1的链串S如下图所示。

2、目标（串）和模式（串）

在串匹配中，一般将主串称为目标（串），子串称为模式（串）。 假设T 为目标串，P为模式串，且不妨设： T="t0t1t2…tn-1"

P="p0p1p2…pm-1"(0＜m≤n)

3、串匹配

串匹配就是对于合法的位置（又称合法的位移）0≤i≤n-m，依次将目标串中的子串"titi+1…ti+m-1"和模式串"p0p1p2…pm-1"进行比较：

①若"titi+1…ti+m-1"＝"p0p1p2…pm-1"，则称从位置i开始的匹配成功，或称i为有效位移。

②若"titi+1…ti+m-1"≠"p0p1p2…pm-1"，则称从位置i开始的匹配失败，或称i为无效位移。

因此，串匹配问题可简化为找出某给定模式串P在给定目标串T中首次出现的有效位移。 注意：

有些应用中要求求出P在T中所有出现的有效位移。

4、顺序串上的子串定位运算

（1）朴素的串匹配算法的基本思想

即用一个循环来依次检查n-m+1个合法的位移i（0≤i≤n-m）是否为有效位移。

具体过程【参见动画演示】

（2）顺序串上的串匹配算法

以下以第二种定长的顺序串类型作为存储结构。给出串匹配的算法： #define MaxStrSize 256 //该值依赖于应用，由用户定义 typedef struct{

char ch[MaxStrSize]; //可容纳256个字符，并依次存储在ch[0..n]中 int length; }SeqString;

int Naive StrMatch(SeqString T,SeqString P)

{//找模式P在目标T中首次出现的位置，成功返回第1个有效位移，否则返回-1

int i,j,k;

int m=P.length; //模式串长度 int n=T.length; //目标串长度

for(i=0;i<=n-m;i++){ //0<=i<=n-m是合法的位移

j=0;k=i; //下面用while循环判定i是否为有效位移 while(j<m&&T.ch[k]==P.ch[j]{ k++;j++; }

if(j==m) //既T[i..i+m-1]=P[0..m-1]

return i; //i为有效位移，否则查找下一个位移 }//endfor

return -1; //找不到有效位移，匹配失败 }//NaiveStrMatch

（3）算法分析 ①最坏时间复杂度

该算法最坏情况下的时间复杂度为O((n-m+1)m)。

分析：当目标串和模式串分别是"an-1b"和"am-1b"时，对所有n-m+1个合法的位移，均要比较m个字符才能确定该位移是否为有效位移，因此所需比较字符的总次数为（n-m+1）m。

②模式匹配算法的改进

朴素的串匹配算法虽然简单，但效率低。其原因是在检查位移i是否为有效位移时，没有利用检查位移i-1，i,…,0时的部分匹配结果。

若利用部分匹配结果，模式串右滑动的距离就不会是每次一位，而是每次使其向右滑动得尽可能远。这样可使串匹配算法的最坏时间控制在O（m+n）数量级上。具体可【参阅有关文献】。

5、链串上的子串定位运算

用结点大小为1的单链表做串的存储结构时，实现朴素的串匹配算法很简单。只是现在的位移shift是结点地址而非整数，且单链表中没有存储长度信息。若匹配成功，则返回有效位移所指的结点地址，否则返回指针。具体算法如下： LinkStrNode *LinkStrMatch(LinkString T,LinkString P) {//在链串上求模式P在目标T首次出现的位置 LinkStrNode * shift,*t,*p; shift=T; //shift表示位移

这种结构便于进行插入和删除运算，但存储空间利用率太低。 （2）结点大小>1的链串

【例】串值为"abcdef"的结点大小为4的链串S如下图所示。

注意：

①为了提高存储密度，可使每个结点存放多个字符。

②当结点大小大于1时，串的长度不一定正好是结点大小的整数倍，因此要用特殊字符来填充最后一个结点，以表示串的终结。

③虽然提高结点的大小使得存储密度增大，但是做插入、删除运算时，可能会引起大量字符的移动，给运算带来不便。

【例】上图中，在S的第3个字符后插入“xyz”时，要移动原来S中后面4个字符的位置，结果见下图。

串运算的实现

http://www.77cn.com.cn 作者：不详 来源： 2006年8月25日 发表评论 进

入社区 子串定位运算

串是特殊的线性表，故顺序串和链串上实现的运算分别与顺序表和单链表上进行的操作类似。

C语言的串库<string.h>里提供了丰富的串函数来实现各种基本运算，因此我们对各种串运算的实现不作讨论。利用串函数实现串的基本运算部分内容【参见练习】。

下面讨论在顺序串和链串上实现的子串定位运算。

1、子串定位运算

子串定位运算类似于串的基本运算中的字符定位运算。只不过是找子串而不是找字符在主串中首次出现的位置。此运算的应用非常广泛。

【例】在文本编辑中，我们经常要查找某一特定单词在文本中出现的位置。解此问题的有效算法能极大地提高文本编辑程序的响应性能。 子串定位运算又称串的模式匹配或串匹配。

本文来源：https://www.bwwdw.com/article/0bum.html