计算机数据结构教程

第一章绪论

计算机科学是一门研究数据表示和数据处理的科学。数据是计算机化的信息，它是计算

机可以直接处理的最基本和最重要的对象。无论是进行科学计算或数据处理、过程控制以及

对文件的存储和检索及数据库技术等计算机应用领域中，都是对数据进行加工处理的过程。

因此，要设计出一个结构好效率高的程序，必须研究数据的特性及数据间的相互关系及其对

应的存储表示，并利用这些特性和关系设计出相应的算法和程序。

数据结构是计算机科学与技术专业的专业基础课，是十分重要的核心课程。所有的计算

机系统软件和应用软件都要用到各种类型的数据结构。因此，要想更好地运用计算机来解决

实际问题，仅掌握几种计算机程序设计语言是难以应付众多复杂的课题的。要想有效地使用

计算机、充分发挥计算机的性能，还必须学习和掌握好数据结构的有关知识。打好“数据结

构”这门课程的扎实基础，对于学习计算机专业的其他课程，如操作系统、编译原理、数据

库管理系统、软件工程、人工智能等都是十分有益的。

1.1数据结构的定义

在计算机发展的初期，人们使用计算机的目的主要是处理数值计算问题。当我们使用计

算机来解决一个具体问题时，一般需要经过下列几个步骤：首先要从该具体问题抽象出一个

适当的数学模型，然后设计或选择一个解此数学模型的算法，最后编出程序进行调试、测试,

直至得到最终的解答。例如，求解梁架结构中应力的数学模型的线性方程组，该方程组可以

使用迭代算法来求解。

由于当时所涉及的运算对象是简单的整型、实型或布尔类型数据，所以程序设计者的

主要精力是集中于程序设计的技巧上，而无须重视数据结构。随着计算机应用领域的扩大和

软、硬件的发展，非数值计算问题越来越显得重要。据统计，当今处理非数值计算性问题占

用了90%以上的机器时间。这类问题涉及到的数据结构更为复杂，数据元素之间的相互关

系一般无法用数学方程式加以描述。因此，解决这类问题的关键不再是数学分析和计算方法,

而是要设计出合适的数据结构，才能有效地解决问题。下面所列举的就是属于这一类的具体

问题。

例如学生信息检索系统。当我们需要查找某个学生的有关情况的时候；或者想查询某

个专业或年级的学生的有关情况的时候，只要我们建立了相关的数据结构，按照某种算法编

写了相关程序，就可以实现计算机自动检索。由此，可以在学生信息检索系统中建立一张按

学号顺序排列的学生信息表和分别按姓名、专业、年级顺序排列的索引表，如图1.1所示。

由这四张表构成的文件便是学生信息检索的数学模型，计算机的主要操作便是按照某个特定

要求（如给定姓名）对学生信息文件进行查询。

诸如此类的还有电话自动查号系统、考试查分系统、仓库库存管理系统等。在这类文档

管理的数学模型中，计算机处理的对象之间通常存在着的是一种简单的线性关系，这类数学

模型可称为线性的数据结构。

[例1]学生信息检索系统。当我们需要查找某个学生的有关情况的时候；或者想查询某个

专业或年级的学生的有关情况的时候，只要我们建立了相关的数据结构，按照某种算法编写

了相关程序，就可以实现计算机自动检索。由此，可以在学生信息检索系统中建立一张按学

号顺序排列的学生信息表和分别按姓名、专业、年级顺序排列的索引表，如图1.1所示。由

这四张表构成的文件便是学生信息检索的数学模型，计算机的主要操作便是按照某个特定要

求（如给定姓名）对学生信息文件进行查询。

诸如此类的还有电话自动查号系统、考试查分系统、仓库库存管理系统等。在这类文档

管理的数学模型中，计算机处理的对象之间通常存在着的是一种简单的线性关系，这类数学

模型可称为线性的数据结构

学号姓名性别专业年级

980001吴承志男计算机科学与技术98级

980002李淑芳女信息与计算科学98级

990301刘丽女数学与应用数学99级

990302张会友男信息与计算科学99级

990303石宝国男计算机科学与技术99级

000801何文颖女计算机科学与技术2000级

000802赵胜利男数学与应用数学2000级

000803崔文靖男信息与计算科学2000级

010601刘丽女计算机科学与技术2001级

010602魏永鸣男数学与应用数学2001级

(a)学生信息表

崔文靖8计算机科学与技术1,5,6,9

何文颖6信息与计算科学2,4,8

李淑芳2数学与应用数学3,7,10

刘丽3,9

(c)专业索引表

石宝国5

魏永鸣102000级6,7,8

吴承志12001级9,10

赵胜利798级1,2,3

张会有499级4,5

(b)姓名索引表(d)年级索引表

图1』学生信息杳询系统中的数据结构

[例2]八皇后问题。在八皇后问题中，处理过程不是根据某种确定的计算法则，而是利用

试探和回溯的探索技术求解。为了求得合理布局，在计算机中要存储布局的当前状态。从最

初的布局状态开始，一步步地进行试探，每试探一步形成一个新的状态，整个试探过程形成

了一棵隐含的状态树。如图1.2所示(为了描述方便，将八皇后问题简化为四皇后问题)。

回溯法求解过程实质上就是一个遍历状态树的过程。在这个问题中所出现的树也是一种数据

结构，它可以应用在许多非数值计算的问题中。

[例3]计划编排问题。一个教学计划包含许多课程，在教学计划包含的许多课程之间，有

些必须按规定的先后次序进行，有些则没有次序要求。即有些课程之间有先修和后续的关系，

有些课程可以任意安排次序。这种各个课程之间的次序关系可用个称作图的数据结构来表

示，如图1.3所示。有向图中的每个顶点表示•门课程，如果从顶点垮到为之间存在有向边

<M，Vj>,则表示课程i必须先于课程j进行。

由以上三个例子可见，描述这类非数值计算问题的数学模型不再是数学方程，而是诸如

表、树、图之类的数据结构。因此，可以说数据结构课程主要是研究非数值计算的程序设计

问题中所出现的计算机操作对象以及它们之间的关系和操作的学科。

图1.2四皇后问题中隐含的状态树

课程编号课程名称先修课程

计算机导论无

数据结构

汇编语言

C程序设计语言C,

计算机图形学

接口技术

数据库原理

编译原理

操作系统

结构课程的内容

数据结构与数学、计算机硬件和软件有十分密切的关系。数据结构是介于数学、计算机

硬件和计算机软件之间的一门计算机科学与技术专业的核心课程，是高级程序设计语言、编

译原理、操作系统、数据库、人工智能等课程的基础。同时:数据结构技术也广泛应用于信

息科学、系统工程、应用数学以及各种工程技术领域。

数据结构课程集中讨论软件开发过程中的设计阶段、同时设计编码和分析阶段的若干基

本问题。此外，为了构造出好的数据结构及其实现，还需考虑数据结构及其实现的评价与选

择。因此，数据结构的内容包括三个层次的五个“要素”，如图1.5所示。

方面

数据表示数据处理

层次

抽象逻辑结构基本运算

实现存储结构算法

评价不同数据结构的比较及算法分析

图1.5数据结构课程内容体系

数据结构的核心技术是分解与抽象。通过分解可以划分出数据的三个层次;再通过抽象,

舍弃数据元素的具体内容，就得到逻辑结构。类似地，通过分解将处理要求划分成各种功能,

再通过抽象舍弃实现细节，就得到运算的定义。上述两个方面的结合使我们将问题变换为数

据结构。这是一个从具体（即具体问题）到抽象（即数据结构）的过程。然后，通过增加对

实现细节的考虑进一步得到存储结构和实现运算，从而完成设计任务。这是一个从抽象（即

数据结构）到具体（即具体实现）的过程。熟练地掌握这两个过程是数据结构课程在专业技

能培养方面的基本目标。

数据结构作为一门独立的课程在国外是从1968年才开始的，但在此之前其有关内容已

散见于编译原理及操作系统之中。20世纪60年代中期，美国的一些大学开始设立有关课程,

但当时的课程名称并不叫数据结构。1968年美国唐.欧.克努特教授开创了数据结构的最初体

系，他所著的《计算机程序设计技巧》第一卷《基本算法》是第•本较系统地阐述数据的逻

辑结构和存储结构及其操作的著作。从20世纪60年代末到70年代初，出现了大型程序，

软件也相对独立，结构程序设计成为程序设计方法学的主要内容，人们越来越重视数据结构。

从70年代中期到80年代，各种版本的数据结构著作相继出现。目前，数据结构的发展并未

终结，一方面，面向各专门领域中特殊问题的数据结构得到研究和发展，如多维图形数据结

构等；另一方面，从抽象数据类型和面向对象的观点来讨论数据结构已成为一种新的趋势,

越来越被人们所重视。

1.3数据结构的基本概念

1.1.2基本术语

1.数据（data）

数据是指能够输入到计算机中，并被计算机识别和处理的符号的集合。

例如：数字、字母、汉字、图形、图像、声音都称为数据。

2.数据元素（dataelement）

数据元素是组成数据的基本单位。

数据元素是一个数据整体中相对独立的单位。但它还可以分割成若干个具有不同属性的项

（字段），故不是组成数据的最小单位。

3.数据对象（dataobject）

是性质相同的数据元素组成的集合，是数据的一个子集。

例如，整数数据对象的集合可表示为N={O,±1,+2….…},字母字符数据对象的集合可

表示为C={4A,,,B,,...,Z,}o

4.数据结构（datastructures）

数据结构定义1;是相互.之间存在-种或多种特定关系的数据元素的集合。

形式化定义：数据结构是一个二元组

Data_Structure=（D,R）

其中，D是数据元素的有限集合，R是D上关系的集合

数据结构定义2：按某种逻辑关系组织起来的一批数据（或称带结构的数据元素的集

合）应用计算机语言并按一定的存储表示方式把它们存储在计算机的存储器中，并在其上

定义了一个运算的集合。具体来说，数据结构包含三个方面的内容，即数据的逻辑结构，数

据的存贮结构和对数据所施加的运算（操作）。

这三个方面的关系为：

（1）数据的逻辑结构独立于计算机，是数据本身所固有的。

（2）存贮结构是逻辑结构在计算机存贮器中的映像，必须依赖于计算机。

（3）运算是指所施加的一组操作总称。运算的定义直接依赖于逻辑结构，但运算的实现必

须依赖于存贮结构。

逻辑结构一划分方法

一、集合结构中的数据元素除了同属于一种类型外，别无其它关系。

二、线性结构结构中的数据元素之间存在一对一的关系。

®----------->®------->.............>©

图2/线性表逻辑结构示意图

三、树型结构结构中的数据元素之间存在一对多的关系。

四、图状结构或网状结构

结构中的数据元素之间存在多对多的关系。

图图形结构逻辑示意图

存储结构（StorgeStructure）:数据结构在计算机中的表示（或称映象）称为数据的存储

结构，又称为物理结构。

四种基本的存储方法：

（1）顺序存储方法（顺序存储结构）

（2）链接存储方法（链式存储结构）

（3）索引存储方法

（4）散列存储方法

同一种逻辑结构可采用不同的存储方法（以上四种之一或组合），这主要考虑的是运算方便

及算法的时空要求。

•顺序存储结构:用数据元素在存储器中的相对位置来表示数据元素之间的逻辑关系。

•链式存储结构：在每一个数据元素中增加一个存放地址的指针，用此指针来表示数据元素

之间的逻辑关系。

索引存储方法：使用该方法存放元素的同时，还建立附加的索引表，索引表的每一项称为索

引项，索引项的一般形式是：（关键字，地址），其中的关键字是能惟一标识一个结点的数据

项。

散列存储方法：通过构造散列函数，用函数的值来确定元素存放的地址。

5.数据类型

是一组性质相同的值的集合及定义于这个值集合上的一组操作的总称。是和数据结构

密切相关的一个概念。它最早出现在高级程序设计语言中，用以刻划程序中操作对象的特性。

在用高级语言编写的程序中，每个变量、常量或表达式都有一个它所属的确定的数据类型。

类型显式地或隐含地规定了在程序执行期间变量或表达式所有可能的取值范围，以及在这些

值上允许进行的操作。

CH提供的基本数据类型有：整型、实型、字符型、逻辑型

例如，高级语言中用到的整数数据类型，是指由一32768到32767中值构成的集合及「

组操作（加、减、乘、除、乘方等）的总称。

注：数据类型与数据结构的区别，数据结构强调数据元素之间的逻辑关系。

6.抽象数据类型（Abstractdatatype）

抽象数据类型（AbstructDataType,简称ADT）是指一个数学模型以及定义在该模型

上的一组操作。抽象数据类型的定义取决于它的•组逻辑特性，而与其在计算机内部如何表

示和实现无关。即不论其内部结构如何变化，只要它的数学特性不变，都不影响其外部的使

用。

抽象数据类型和数据类型实质上是一个概念。例如，各种计算机都拥有的整数类型就是

一个抽象数据类型，尽管它们在不同处理器上的实现方法可以不同，但由于其定义的数学特

性相同，在用户看来都是相同的。因此，“抽象”的意义在于数据类型的数学抽象特性。

但在另一方面，抽象数据类型的范畴更广，它不再局限于前述各处理器中已定义并实现

的数据类型，还包括用户在设计软件系统时自己定义的数据类型。为了提高软件的重用性，

在近代程序设计方法学中，要求在构成软件系统的每个相对独立的模块上，定义组数据和

施于这些数据上的一组操作，并在模块的内部给出这些数据的表示及其操作的细节，而在模

块的外部使用的只是抽象的数据及抽象的操作。这也就是面向对象的程序设计方法。

抽象数据类型的定义可以由一种数据结构和定义在其上的•组操作组成,而数据结构又

包括数据元素及元素间的关系，因此抽象数据类型•般可以由元素、关系及操作三种要素来

定义。

抽象数据类型的特征是使用与实现相分离，实行封装和信息隐蔽。就是说，在抽象数据

类型设计时，把类型的定义与其实现分离开来。

格式：ADT＜抽象数据类型名〉is

Data:〈数据描述〉

Operation:〈操作声明〉

END

例如:给出自然数的抽象数据类型定义.

ADTNaturalNumberis

Data:一个整数的有序子集合，它开始于0,终止于机器能表示的最大整数（MAXINT）。

Operation:

对于所有x,yNaturalNumber,定义如下操作：

add（x,y）求x+y

sub（x,y）求x-y

mul（x,y）求x*y

div（x,y）求x/y

end

1.2算法的描述

1.2.1算法的概念

1.算法（algorithm）

通俗地讲，算法就是一种解题的方法。更严格地说，算法是由若干条指令组成的有穷序

列，它必须满足下述条件（也称为算法的五大特性）：

（1）输入：具有0个或多个输入的外界量（算法开始前的初始量）

（2）输出：至少产生一个输出，它们是算法执行完后的结果。

（3有穷性：每条指令的执行次数必须是有限的。

（4）确定性：每条指令的含义都必须明确，无二义性。

（5）可行性：每条指令的执行时间都是有限的。

2.算法和程序的关系

算法的含义与程序十分相似，但二者是有区别的。一个程序不一定满足有穷性（死循

环），另外，程序中的指令必须是机器可执行的，而算法中的指令则无此限制。一个算法若

用计算机语言来书写，则它就可以是一个程序。

算法与数据结构是相辅相承的。解决某一特定类型问题的算法可以选定不同的数据结

构，而且选择恰当与否直接影响算法的效率。反之，-种数据结构的优劣由各种算法的执行

来体现。

要设计一个好的算法通常要考虑以下的要求。

⑴正确。算法的执行结果应当满足预先规定的功能和性能要求。

⑵可读。一个算法应当思路清晰、层次分明、简单明了、易读易懂。

⑶健壮。当输入不合法数据时，应能作适当处理，不至引起严重后果。

⑷高效。有效使用存储空间和有较高的时间效率。

1.2.2算法描述

算法可以使用各种不同的方法来描述。

最简单的方法是使用自然语言。用自然语言来描述算法的优点是简单且便于人们对算法

的阅读。缺点是不够严谨。

可以使用程序流程图、N-S图等算法描述工具。其特点是描述过程简洁、明了。

用以上两种方法描述的算法不能够直接在计算机上执行，若要将它转换成可执行的程序

还有一个编程的问题。可以直接使用某种程序设计语言来描述算法，不过直接使用程序设计

语言并不容易，而且不太直观，常常需要借助于注释才能使人看明白。

用C++描述算法

在本教材中，我们将采用C++或类C++来描述算法。并且用C++描述算法遵循如下规则：

(I)所有算法的描述都用C++中的函数形式

函数类型函数名(形参及类型说明)

{函数语句部分

return(表达式值)；

}

(2)函数中的形式参数有两种传值方式

若为一般变量名，则为单向传值，若在变量前面增加“&”符号，则为双向传地址。

例如有一个函数为

Voidswap(&i,&j,k)则i,j为双向传地址参数，k为单向传值参数。

(3)函数的说明部分可函数的实现部分分离

在C++中，用函数来描述算法时，为使之与面象对象的程序设计相匹配，一般将函数的说

明部分与函数的实现部分分离开来。

(4)输入函数

C++中的输入函数调用为:cin>>变量名。

(5)输出函数

C++中的输出函数调用为:cout<<变量名。

(6)C++中的类

CH对于面向对象程序设计的支持，核心部分就是类的定义。类的定义体现了抽象数据

类型的思想，可以支持说明与实现的分离，将抽象数据类型的实现封装在类的内部，使之达

到信息隐蔽的目的。

1.3算法分析与度量

我们可以从•个算法的时间复杂度与空间复杂度来评价算法的优劣。

当我们将一个算法转换成程序并在计算机上执行时，其运行所需要的时间取决于下列因

素：

⑴硬件的速度。例如使用486机还是使用586机。

⑵书写程序的语言。实现语言的级别越高，其执行效率就越低。

⑶编译程序所生成目标代码的质量。对于代码优化较好的编译程序其所生成的程序质量

较高。

⑷问题的规模。例如，求100以内的素数与求1000以内的素数其执行时间必然是不同

的。

显然，在各种因素都不能确定的情况下，很难比较出算法的执行时间。也就是说，使用

执行算法的绝对时间来衡量算法的效率是不合适的。为此，可以将上述各种与计算机相关的

软、硬件因素都确定下来,这样一个特定算法的运行工作量的大小就只依赖于问题的规模(通

常用正整数n表示)，或者说它是问题规模的函数。

1.时间复杂度

•个程序的时间复杂度(Timecomplexity)是指程序运行从开始到结束所需要的时间。

一个算法是由控制结构和原操作构成的，其执行时间取决于两者的综合效果。为了便于

比较同问题的不同的算法，通常的做法是：从算法中选取•种对于所研究的问题来说是基

本运算的原操作，以该原操作重复执行的次数作为算法的时间度量。一般情况下，算法中原

操作重复执行的次数是规模n的某个函数T(n)。

许多时候要精确地计算T(n)是困难的,我们引入渐进时间复杂度在数量上估计一个算法

的执行时间，也能够达到分析算法的目的。

定义(大。记号)：如果存在两个正常数c和n0,使得对所有的n,n>n0,有：

f(n)Wcg(n)

则有:

f(n)=0(g(n))

例如，一个程序的实际执行时间为T(n)=2.7n3+3.8n2+5.3»则T(n)=0(/)。

使用大。记号表示的算法的时间复杂度，称为算法的渐进时间复杂度(Asymptotic

CompIexity)o

通常用0(1)表示常数计算时间。常见的渐进时间复杂度有：

23n

0(1)<0(log2n)<o(n)<O(nlog2n)<0(n)<0(n)<0(2)

在各种不同算法中，若算法中语句执行次数为一个常数，则时间复杂度为0(1),另外，在时

间频度不相同时，时间复杂度有可能相同，如T(n)=n2+3n+4与T(n)=4n2+2n+l它们的频度

不同，但时间复杂度相同，都为0(/)。

例分析以下程序段的时间复杂度

fbr(i=l;i<n;i++)

{y=y+i;

for(j=0;j<=(2*n);j++)

X-H-；

常见函数的时间复杂度按数量递增排列及增长率。

常数阶0(1)

对数阶O(log2n)

线性阶0(n)

线性对数阶O(nlog2n)

平方阶0(n2)

立方阶0(n3)

k次方阶O(nk)

指数阶O(2n)

2.空间复杂度

与时间复杂度类似，空间复杂度是指程序运行从开始到结束所需的存储量。即算法在计算

机内执行时所需存储空间的度量。记作：

S(n)=O(f(n))

我们一般所讨论的是除正常占用内存开销外的辅助存储单元规模。讨论方法与时间复杂

度类似，不再赘述。

•本章小结

数据、数据结构等基本概念

数据结构的三个方面的内容

抽象数据类型的概念

线性和非线性结构的逻辑特征

数据存储的四种基本方法

算法、算法的时间复杂度

第一章概论自测题

一、填空题

1.数据结构是门研究非数值计算的程序设计问题中计算机的以及它们

之间的和运算等的学科。

2.数据结构被形式地定义为（D,R）,其中D是的有限集合,R是D上的有

限集合。

3.数据结构包括数据的、数据的和数据的这三

个方面的内容。

4.数据结构按逻辑结构可分为两大类，它们分别是和。

5.线性结构中元素之间存在__________关系，树形结构中元素之间存在__________关系,

图形结构中元素之间存在___________________关系。

6.在线性结构中，第一个结点前驱结点，其余每个结点有且只有1个前驱结点；最

后一个结

点后续结点，其余每个结点有且只有1个后续结点。

7.在树形结构中，树根结点没有结点，其余每个结点有且只有个前驱结

点；叶子结点没有结点，其余每个结点的后续结点数可以。

8.在图形结构中，每个结点的前驱结点数和后续结点数可以。

9.数据的存储结构可用四种基本的存储方法表示，它们分别

是O

10.数据的运算最常用的有5种，它们分别

是o

11.一个算法的效率可分为效率和效率。

二、单项选择题

（）1.非线性结构是数据元素之间存在一种：

A）一对多关系B）多对多关系C）多对一关系D）一对

一关系

（）2.数据结构中，与所使用的计算机无关的是数据的结构；

A）存储B）物理C）逻辑D）物理和存储

()3.算法分析的目的是：

A）找出数据结构的合理性B）研究算法中的输入和输出的关系

C）分析算法的效率以求改进D）分析算法的易懂性和文档性

()4.算法分析的两个主要方面是：

A）空间复杂性和时间复杂性B）正确性和简明性

C）可读性和文档性D）数据复杂性和程序复杂性

()5.计算机算法指的是：

A)计算方法B)排序方法C)解决问题的有限运算序列D)调

度方法

()6.计算机算法必须具备输入、输出和一等5个特性。

A)可行性、可移植性和可扩充性B)可行性、确定性和有穷性

C)确定性、有穷性和稳定性D)易读性、稳定性和安全性

三、简答题

1.数据结构和数据类型两个概念之间有区别吗？

2.简述线性结构与非线性结构的不同点。

四、分析下而各程序段的时间复杂度

1.for(i=0;i<n;i++)

2.s=0;

for(j=0;j<m;j++)

for(i=0;i<n;i++)

A[i]U]=0;

for(j=0;j<n;j++)

s+=B[i]U];

sum=s;

3.x=0;

4.i=l;

for(i=l;i<n;i++)

while(i<=n)

for(j=l;j<=n-i;j++)

i=i*3;

x++:

五、设有数据逻辑结构S=(D,R),试按各小题所给条件画出这些逻辑结构的图

示，并确定相对于关系R，哪些结点是开始结点，哪些结点是终端结点？

1.D={dl,d2,d3,d4}R={(dl,d2),(d2,d3),(d3,d4))

2»D={dl,d2,…,d9}

R={(dl,d2),(d1,d3),(d3,d4),(d3,d6),(d6,d8),(d4,d5),(d6,d7),(d8,d9)}

3。D={dl,d2,…,d9}

R={(dl,d3),(dl,d8),(d2,d3),(d2,d4),(d2,d5),(d3,d9),(d5,d6),(d8,d9),(d9,d7),(d4,d7),(d4,d6)}

第2章线性表

线性表是我们要介绍的数据结构中的第一种数据结构，也是比较简单的数据结构，对于

线性表的操作是动态的还是静态的在后续的章节里要用到，是学习数据结构的基础。首先看

一下什么是线性表。

2.1线性表的定义及其运算

2.1.1线性表的定义

1.线性表的定义

线性表(linearlist)是具有相同属性的数据兀素的一个有限序列。

用二元组表示为：

linear_list=(A,R)

其中A={aili<n,n20,aiCelemtype}

R={<ai,ai+1>UWiWnT}

A表示属性相同的数据元素，R代表关系，<ai,ai+l>表示有序，也叫有序偶。有了

这种关系就表示线性表的数据元素之间是一个有限序列。Elemtype表示一种具体的已知数据

类型。为线性表中的数据元素所有可能的数据类型的一个抽象名称。

例如：Ll=(A,R)

A={5,38,12,49,63,200,470)

R=某校1971至1977年拥有的计算机的数量

Ll=(5,38,12,49,63,200,470)

L2=(A,R)

A={“王一”，“王兰”，“王心”，“王小白”，“王小红”}

口=父子关系

新生报到入学，一个班级有30个学生，这30个学生只能形成一个集合，如果加上一

个关系，把学生按学号来编，这个集合由于有了学号这样的一个关系就成为了一个线性表。

所以线性表的关键在于关系。

2.线性结构的基本特性：-对一的关系。

必有唯一一个元素无前驱，必有唯一一个元素元后继，除此之外任何元素都有唯一的前

驱和唯一的后继。

有了这种一对一的关系，就称为线性结构或线性表。由以上知道了什么样的关系是线性

表，但是我们考虑的不是判断什么样的关系是线性表，什么样的关系不是线性表，而是前提

已知一个线性表，那么怎样在计算机里如何存储，如何处理是要研究的问题。下面要介绍几

个概念。

1。如果已经是一个线性表，用园括可如下来表示。

线性表的一般形式：

L=(al.-ai-l.ai.-an)n是线性表的元素的个数即线性表的长度,n=0是空表。

这个图表示在逻辑关系上每个元素的前驱和后继的关系。以上是线性表的逻辑结构。

2。物理存储

线性表的物理存储也就是物理结构的表示，线性表已经存在，对这个线性表进行如下的

一些操作，用什么方法，在计算机里如何存储，它的操作怎样来实现。例如，有一种结构整

型可以进行四则、求余、求模、运算等。这些运算就是整型可以实现的操作。对于线性表也

是一种数据类型，这种结构也可以实现很多操作。

线性表作为抽象数据类型可能实现的基本操作：

2.1.2线性表的运算

常见线性表的运算有：

1.置空表SETNULL(&L)将线性表L置成空表

2.求长度LENGTH(L)求给定线性表L的长度

3.取元素GET(L,i)若IWiWlength(L),则取第i个位置上的元素，否则取得的

元素为NULL»

4.求直接前趋PRIOR(L,X)求线性表L中元素值为X的直接前趋，若X为第个元素，

前驱为NULL

5.求直接后继NEXT(L,X)求线性表L中元素值为X直接后继，若X为最后一个元

素，后继为NULL。

6.定位函数LOCATE(L,X)在线性表L中查找值为X的元素位置，若有多个值为X,

则以第一个为准，若没有，位置为0。

7.插入INSERT(&L,X,i)在线性表L中第i个位置上插入值为X的元素。

8.删除DELETE(&L,i)删除线性表L中第i个位置上的元素。

注意：初始条件、返回值、操作功能是编写一个函数的依据。

引用类型&：给变量起别名。&x=y程序对x进行的任何操作，同时对y也进行操作，反

之亦然。因为x,y指向同一存储单元即两个变量使用同一个存储单元。可以用其中的任何一

个名字对存储单元进行操作。形参中用&将L的值带回到主要函数。

例：假设线性表L=(23,56,89,76,18),i=3,x=56,y=88,则对L的一组操作及结果如下:

Length(L);〃所得结果为5

Get(L,i)〃所得结果为89

Prior(L,x)〃所得结果为23

Next(L,x)//所得结果为89

Locate(L,x)〃所得结果为2

Insert(&L,y,i)〃所得结果为(23,56,88,89,76,18)

Delete(&L,i+1)〃所得结果为(23,56,88,76,18)

以上了解了线性表、线性表的关系以及基本操作。这些基本操作的实现是要有存储作为

前提的，线性表在里存储为什么样子，是动态的还是静态的，只有确定了这些才能实现操作

，也就是说存储是实现操作的依据。卜面介绍两种存储方法。

2.2线性表的顺序存储结构

一、顺序表结构

顺序存储的特点：逻辑关系相邻(ai和ai+1是相邻的)

物理位置也相邻｛存完ai一定要存ai+1)

线性表的顺序存储指的是用一组地址连续的存储单元依次存储线性表的数据元素。这种

存储结构的线性表也称为顺序表。它的特点为表中相邻的元素赋以相邻的存储位置。换句话

说，以元素在计算机内“物理位置相邻”来表示线性表数据元素之间的逻辑关系。

假设线性表中元素为(al,a2,an),设第一个元素al的内存地址为LOC(al)(基地址),

而每个元素在计算机内占d个存贮单元，则第i个元素ai的地址为

LOC(ai)=LOC(al)+(i-l)Xd(其中IWiWn)

由于高级语言中的数组类型具有如下的特点：数组中的元素间的地址是连续的，数组中

所有元素的数据类型是相同的。而这与线性表的存储空间结构是类似的。因此，通常都用数

组来描述数据结构中的顺序存储结构。存储的时候即要存储数据元素又要存储数据关系，

那么数组把数据元素存储在list,也就存储了关系。用数组存放以后，线性表的长度是数组

空间中变化的，用len来表示线性表的长度，并事先预计分配一个足够大的空间maxsize,

用一个霭来定义.

constinimaxsize-maxlen：〃maxlen及示线性表允许的最大长度

structsequenlist

｛elemtypea[maxsize];〃表示线性表(al,a2,,an)

intlen;〃:len表示当前线性表的实际长度(可以变化)

｝；

如何来使用？

使用方法：首先定义sequenlistL;intn=7;

结构体有两个域：L.a[l]=al;

L.a[2]=a2;

L.len;

注：结构体类型定义的是一种样子，没有实际的内容。结构体变量是系统实际分配一个空间

o变量定义之后，才用实际的空间可以使用。才可以对其两个域进行访问、进行操作。

二、顺序表操作的实现

1.求顺序表的长度length(L)

intlength(sequenlistL)

returnL.len;

}

2.置空表setnull(&L)

voidsetnul1(sequenlist&L)

{L.len=0;}

3.遍历线性表：traverlist(&L)

依次访问(输出)表中的元素，且只访问一次。

voidtraverllist(&L)

(

for(i=l;i<=L.len;i++)

cout<<L,a[i];

cout<<endl;

}

4.删除运算Delete(&L,i)

voidDelete(sequenlist&L,inti)

{intj;

if((i<l)||(i>Llen))

cout<<J,positionisnotcorrect!<<endl;

else{for(j=i+l;j<=L.len;j++)

L.a[j-l]=L.a[j];〃元素前移

L.len—;〃表长度减1

})

5.插入运算Insert(&L,x,i)

voidInsert(sequenlist&L,elemtypex,inti)

{intj;

if(L.len>=maxsize-l)

cout<<"overflow”<<endl;

elseif((i<l)||(i>L.len+l)

coutw“positionisnotcorrect!5,«endl;

else{for(j=L.len;j>=i;j—)

L.a[j+l>L.a[j];〃元素后移

L.a[i]=x;〃插入元素

L.len++;〃表长度增加1

}}注意逻辑关系的变化

5.定位算法(查找)Locate(L,x)

intLocate(sequenlistL,elemtypex)

{intj=l;

while(j<=L.len)&&(L.a[j]!=x)

j++；

if(j<=L.len)returnj;

elsereturn0;

)

6.取元素Get(L,i)

elemtypeGet(sequenlistL,inti)

{if(i<l)||(i>L.len)returnNULL;

elsereturnL.a[i];}

2.3线性表的链式存贮结构

静态存储的特点是用数组的方法来处理，事先定义一个足够大的空间，插入和删除的操

作需要不断地移动。效率比较低。

线性表的链式存储结构的特点是用一组地址任意的存储单元（可以是连续的，也可以是

不连续的）存储线性表的数据元素。因此，为了表示每个数据元素与其直接后继之间的逻辑

关系的有序性，除了存储其本身的信息之外，还需存储一个指示其直接后继的信息（即存储

位置）。这两部分信息组成数据元素的存储映象，称为结点。

数据元素

+指针（指示后继元素存储位置）

=结点

以“结点的序列”表示线性表一链表。

就是将数据元素存放在结点中，按照前驱和后继的关系用链子将其串起来。

在定义的链表中，若只含有一个指针域来存放下一个元素地址，称这样的链表为单链表或线

性链表。线性链表中的结点结构可描述为：

其中data域用来存放结点本身信息，next域用来存放下一个元素地址。

单链变T用C++描述为：

structlink

{elemtypedata;//数据域

link*next;〃指针域

head_a,头IAEt_>|a2-|—>

（a）不带头结点的单链表

（b）带头结点的单链表

图2-7不带头结点和带头结点的单链表

单链表运算

1.头插法建立单链表(从左边插入结点)

link*hcreat()

{link*s,*p;inti;

cin»i;〃输入结点数值，为0时算法结束

p=NULL;

while(i)

{s=newlink;s->data=i;

s->next=p;p=s;

cin»i;}

returnp;

}

2.尾插法建立单链表(从右边插入结点)

link*rcreat()

{link*s,*r,*p;inti;

p=r=newlink;p->next=NULL;

cin>>i;

while(i)

{s=newlink;s->data=i;

r->next=s;r=s;

cin>>i;}

r->next=NULL;

returnp;}

3.单链表上的查找运算

(1)按值查找Locate(head,x)

在单链表head中，查找值为x的结点，若找到，返回它的地址，否则返回NULL。

Link*Locate(link*head,elemtypex)

{link*p;

p=head->next;

while((p!=NULL)&&(p->data!=x))

p=p->next;

returnp;

)

(2)按序号查找get(head,i)

在单链表head中查找第i个位置上的元素，若找到，则返回它的地址，否则返回NULL。

Link*get(link*head,inti)

{intj;link*p;

j=l;p=head->next;

while((j<i)&&(p!=NULL)

{j++；

p=p->next;}

returnp;}

4.单链表上的插入运算

voidinsert(link*head,elemtypex,elemtypey)

〃在头指针head所指单链表中，在值为y的结点之后插入值为x的结点

{link*p,*s;

s=newlink;s->data=x;

if(head->next=NULL)〃链表为空

{head->next=s;s->next=NULL;}

p=Locate(head,y)〃调用查找算法

if(p==NULL)cout«>,插入位置非法”；

else{s->next=p->next;

p->next=s;}}

5.单链表上的删除运算

voiddelete(link*head,elemtypex)

〃在head为头指针的单链表中,删除值为x的结点

{link*p,*q;

q=head;p=head->next;

while(p!=NULL)&&(p->data!=x)

{q=P；p=p->next;}

if(p=NULL)cout«”要删除的结点不存在”；

else{q->next=p->next;delete(p);

})

6.输出单链表

若需将单链表按逻辑顺序输出(见图2-10),则必须从头到尾访问单链表中每一个结点，

voidprint(link*head)

{link*p;

p=head->next;

while(p->next!=NULL)

{cout«p->data<<>,->w;〃输出表中非最后一个元素

p=p->next;}

cout«p->data;〃输出表中最后一个元素

cout«endl;}

讲解这些基本操作如何实现。无论介绍静态结构的还是动态结构的，都是要在线性表存在的

基础之上，用什么方法对它存储，存储之后，基本操作应该如何实现。操作的实现都是一些

函数，掌握数据结构的关键能不能把算法的思路掌握，它的解决方式，以及如何编写。数据

结构要掌握的就是要编写算法。主要思路：静态的就是数组，把握的就是数组的操作；动态

的就是单链表、指针，指针如何移动、变化。掌握了主要思路，其它基本操作的算法都是类

似的。任何一个算法都是有一个很深的依据的，这个依据就是数据结构。

2.3.3循环链表结构

单链表上的访问是一种顺序访问，从其中某一个结点出发，可以找到它的直接后继，但

无法找到它的直接前驱。因此，我们可以考虑建立这样的链表，具有单链表的特征，但又不

需要增加额外的存贮空间，仅对表的链接方式稍作改变，使得对表的处理更加方便灵活。从

单链表可知，最后•个结点的指针域为NULL表示单链表已经结束。如果将单链表最后一个结

点的指针域改为存放链表中头结点(或第一个结点)的地址，就使得整个链表构成一个环，又

没有增加额外的存贮空间，称这们的链表为单循环链表。

循环链表上的运算与单链表上运算基本一致，区别只在于最后一个结点的判断(即循环

的条件不同)，但利用循环链表实现某些运算较单链表方便(从某个结点出发能求出它的直接

前驱，而单链表是不行的，只能从头出发)。

(a)空循环表

I~~~~>•…一•!~~>1

(b)非空循环表

图2-11带头结的单循环链表示意图

2.3.4双向链表结构

1.双向链表基本概念

在单链表中，从某个结点出发可以直接找到它的直接后继，时间复杂度为0(1)，但无法直

接找到它的直接前驱；在单循环链表中，从某个结点出发可以直接找到它的直接后继，时间

复杂仍为0(1),直接找到它的直接前驱，时间复杂为0(n)。有时，希望能快速找到一个结点

的直接前驱，这时，可以在单链表中的结点中增加一个指针域指向它的直接前驱，这样的链

表，就称为双向链表(一个结点中含有两个指针)。

structdulink

{elemtypedata;〃结点的数据域

dulink*next,*prior;〃指向直接后继和直接前驱的指针

)

2.双向链表插入运算duinsert(head,x,y)

voidduinsert(dulink^head,elemtypex,elemtypey)

{dulink*p,*s;

s=newdulink;〃申请待插入的结点

s->data=x;p=head;

while(p!=NULL)&&(p->data!=y)〃用循环查找值为y的结点

p=p->next;

if(p!=NULL)〃已找到插入位置

{s->next=p->next;p->next->prior=s;

s->prior=p;p->next=s;}

elsecout<<>,插入位置不存在”；}

3o双向链表的删除运算dudelete(head,x)

voiddudelete(dulink*head,intx)

{dulink*p;p=head;

whi1e(p!=NULL)&&(p->data!=x)〃用循环查找值为x的结点

p=p->next;

if(p!=NULL)〃已找到该结点

{p->prior->next=p->next;

p->next->prior=p->prior;

deletep;}〃删除后的结点空间回收

elsecout«"没找到，不能删除”；}

第三章栈和队列

栈和队列是在软件设计中常用的两种数据结构。从数据结构角度看，栈和队列也是线性

表，它们的逻辑结构和线性表相同，是操作上受限制的线性表。但从数据类型角度看，栈和

队列是和线性表大不相同的两类重要的抽象数据类型。栈按“后进先出”的规则进行操作；，

队按“先进先出”的规则进行操作，故称操作受限制的线性表。本章除了讨论栈和队列的定

义、表示方法和实现外，还将给出一些应用的例子。

3.1栈

3.1.1栈的定义

栈(Stack)是限制在表尾进行插入和删除操作的线性表。因此，对栈来说，表尾端有

其特殊含义，表尾端称为栈顶，表头端称为栈底。当表中没有元素时称为空栈。如图3.1.1

所示栈中有三个元素，进栈的顺序是a(>a2,a3,当需要出栈时其顺序为a3>a2,a］，所以

栈又称为后进先出的线性表(LastInFirstOut),简称LIFO表。

入栈、7出栈

top

----a3

一2

ai

图3.1栈示意图

在日常生活中，有很多后进先出的例子。如仓库货物的存放，先从底层往上面堆，再

从上往下拿，是典型的栈。在程序设计中，常常需要栈这样的数据结构，使得与保存数据

时相反顺序来使用这些数据，这时就需要用一个栈来实现。

3.1.2栈的运算

对于栈，常做的基本运算有：

1.初始化栈：INISTACK(&S)

初始条件：栈s不存在

操作结果：构造了一个空栈。

2.进栈：PUSH(&S,X)

初始条件：栈s已存在

操作结果：在栈s的顶部插入一个新元素X,x成为新的栈顶元素，也称为“入栈”、“插

入”、“压入”。

3.出栈：POP(&S)

初始条件：栈s存在且非空

操作结果：栈s的顶部元素从栈中删除，栈中少了•个元素。栈发生变化，也称为“退栈”、

“删除”、“弹出”。

4.取栈顶元素：GETTOP(S)

初始条件：栈s存在且非空

操作结果：栈顶元素作为结果返回，栈不变化。

5.判栈空：EMPTY(S)

初始条件：栈