第1章 绪论 本章主要内容 1.1 什么是数据结构 1.2 基本概念和术语 1.3 数据类型和抽象数据类型 1.4 算法描述与算法评价

1.1 什么是数据结构 自从1946年第一台计算机问世以来，计算机技术的发展目新月异，其应用已不再发展局限于科学计算，而是更多地用于控制、管理及数据处理等非数值计算的处理工作，与此同相应，计算机加工处理的对象由纯粹的数值发展到字符、表格和图像等各种有一定结构的数据，数据结构就是研究非数值计算的程序设计问题中计算机的操作对象以及它们之间的关系和操作等的学科。

从课程性质上说，“数据结构”是一门专业技术基础课。它的教学要求是： “数据结构”是计算机程序设计的重要理论基础课，而且已成为其它理工专业的热门选修课。是信息类或计算机方向考研的必考科目。 从课程性质上说，“数据结构”是一门专业技术基础课。它的教学要求是： （1）学会分析和研究计算机加工的数据结构的特性，以便为应用涉及的数据选择适当的逻辑结构、存储结构及其相应的算法；

（2）初步掌握算法的时间分析和空间分析技术； （3）本课程的学习过程也是复杂程序设计的训练过程，要求学生编写的程序结构清楚和正确易读，符合软件工程的规范。

2．徐孝凯编著:《数据结构实用教程（第二版）》.清华大学出版社. 2006年8月。 推荐参考书： 1. 严蔚敏，吴伟民，米宁编著：《数据结构题集（C语言版）》，清华大学出版社，2005年11月。 2．徐孝凯编著:《数据结构实用教程（第二版）》.清华大学出版社. 2006年8月。 3．徐孝凯编著：《数据结构实用教程（第二版）习题参考解答》，清华大学出版社，2006年8月。 4．李春葆编著：《数据结构习题与解析——A级（第3版）》，清华大学出版社，2006年9月。 5．宁正元编著：《算法与数据结构 》，清华大学出版社，2006年5月 。

线性的数据结构 在文档管理的数学模型中，计算机处理的对象之间通常存在着的是一种最简单的线性关系，这类数学模型称为线性的数据结构。

例1-1 图书馆的书目检索系统自动化问题 （数据之间关系如图1-1） 001 高等数学 樊映川 S01 … 002 理论力学 罗远志 L01 003 华罗庚 004 线性代数 奕汝书 S02 ... …. 高等数学 001,003,… 理论力学 002,… 线性代数 004,… … 樊映川 001,… 华罗庚 003,… 奕汝书 004,… … L 002,… S 001,003,… … ,… 图1.1 图书目录文件示例

“树”型的数据结构 数据元素之间存在一个对多个的关系，这种类型的数据结构称为“树”型结构(例1-2中) 。

例1-2 计算机和人对弈问题。 （数据关系如图1-2） 例1-2 计算机和人对弈问题。 （数据关系如图1-2） X X (b) (a) 图1-2 井字棋对弈“树” (a) 棋盘格局示例 （b）对弈树的局部

“图”状的数据结构 交通图所示的元素之间的关系是多个对多外的关系，这种类型的数据结构称为图状结构或网状结构（如例1-3）。

例1-3 一个交通网的管理问题 （数据间关系如图1-3） 例1-3 一个交通网的管理问题 （数据间关系如图1-3）

1.2 基本概念和术语 1. 数据 ——数据是指信息的载体，是对客观事物的符号表示，是对有效地输入到计算机中并能被计算机程序处理的符号的总称。如声音、图形、图像。 ——数据元素是数据的基本单位，数据项是数据的不可分割的最小单位。有时也称之为结点、元素、顶点、记录等。一个数据元素可由若干个数据项组成，如上面图书信息中的每本书名就是一个数据元素，而每本书的信息包括编号、书名、作者、出版社、单价等，这每一个项目就属于数据项。 2. 数据元素

3. 数据对象——数据对象是性质相同的数据元素的集合，是数据的一个子集。 4. 数据类型——数据类型是对在计算机中表示的同一数据对象及其在该数据对象上的一组操作的总称。 数据类型有时还分为原子数据类型和结构数据类型。

5. 数据结构—— 数据结构指的是数据及数据之间的相互关系。一般地，数据结构包括以下三个方面的内容： （1）数据元素之间的逻辑关系，有时也称为数据的逻辑结构。 （2）数据元素及其关系在计算机内存中的表示（又称为映象），称之为数据的物理结构，又称为数据的存储结构，它包括数据元素的表示和数据元素之间关系的表示。 （3）数据的运算及实现，即对数据元素可以施加的操作及其这些操作在相应的存储结构上的实现。

数据结构可表示为 数据的逻辑结构 + 数据的存储结构 + 运算。 操作算法 抽象的数学模型 计算机中的存储

（1）线性结构：结构中的数据元素存在一个对一个的关系，即所谓的线性关系。 数据的逻辑结构： 数据的逻辑结构是从逻辑关系上描述数据，可以看作是从具体问题抽象出来的数学模型。如上例中的图书信息表。根据数据元素之间的不同特性，通常有下列四类基本逻辑结构： （1）线性结构：结构中的数据元素存在一个对一个的关系，即所谓的线性关系。 （2）树型结构：结构中的数据元素之间存在一个对多个的关系，是结点之间有分支、并具有层次关系的结构，它非常类似于自然界中的树。如对弈关系图就是一个树型结构。

（3）图或网状结构：该结构中的数据元素之间的关系存在多个对多个的关系，如交通网络图就是一个图状结构。 数据的逻辑结构： （3）图或网状结构：该结构中的数据元素之间的关系存在多个对多个的关系，如交通网络图就是一个图状结构。 （4）集合：结构中的数据元素之间除了“同属于一个集合”的相互关系外，别无其它关系。 有时将树形结构、集合和图或网状结构称为非线性结构，此时数据逻辑结构就可分为线性结构和非线性结构两类。

数据的逻辑结构 ——形式上用一个二元组来定义： B=(K,R） 其中：B表示一个结构，k表示结点的有限集合；R是关系的有限集合。 简单地说，数据结构定义了一组按某种关系结合在一起的数据元素。

数间关系，尖括号< >表示有序偶 例1 复数的数据结构定义 数集 Comploe=(C,R)=({C1,C2},{<C1,C2>}) R是数间关系 C是数集 例2 科研课题小组成员的数据结构定义 Group=(P,R)=({T,G1…Gn,S11…Snm},{R1,R2}) P是成员集 R是成员间关系 T：表示导师；Gi：表示研究生；Sij：表示本科生。 R1={<T,Gi>}, R2={<Gi,Sij>}

画出这个逻辑结构的示意图,并确定相对关系R,哪些结点是开始结点,哪些结点是终端结点? 例3 设有数据逻辑结构为: B=(K,R) K={k1,k2,…,k9} R={<k1,k3>,<k1,k8>,<k2,k3>,<k2,k4>,<k2,k5>,<k3,k9>,<k5,k6>,<k8,k9>,<k9,k7>,<k4,k7>,<k4,k6>} 其中,尖括号<>表示有序数对. 画出这个逻辑结构的示意图,并确定相对关系R,哪些结点是开始结点,哪些结点是终端结点? k3 k2 k1 k4 k5 k8 k6 k7 k9 开始结点(无前驱):k1,k2; 终端结点(无后继):k6,k7; 该逻辑结构是非线性结构中的图形结构.

例4 设有如图所示的逻辑结构图示,给出它的逻辑结构. k1 k2 k3 k6 k4 k8 k7 k5 k9 B=(K,R) K={k1,k2,…,k9} R={<k1,k2>,<k1,k3>,<k3,k4>,<k3,k6>,<k6,k8>,<k4,k5>,<k6,k7>,<k8,k9>} 该逻辑结构是一个树形结构,其树根为k1,叶子结点为k2,k5,k7,k9.

例5 设有逻辑结构 C=(K,R) K={1,2,3,4,5,6} R={r} 例5 设有逻辑结构 C=(K,R) K={1,2,3,4,5,6} R={r} r={(1,2),(2,3),(2,4),(3,4),(3,5),(3,6),(4,5),(4,6)} 其中,圆括号（）表示两结点关系是双向的. 画出它的逻辑结构示意图. 1 2 5 3 4 6

数据的存储结构： 存储结构依赖于计算机，由于计算机的存储器由有限多个存 单元组成，每个存储单元有唯一的地址，各存储单元地址连续编码。要使结点集合K中每个结点与存储区域M中的每个单元建立映象，即对于每一个 ，都有唯一的 ,使得有映象S(k)=Z。通常有两种不同的（表示）存储映象方法： （1）顺序存储方法——是把逻辑上相邻的结点存储在物理位置上相邻的存储单元中，结点间的逻辑关系由存储单元的相邻关系而体现。由此得到的存储表示称为顺序存储结构，通常可借助计算机语言的数组来描述。

（2）链接存储方法——不要求逻辑上相邻的结点在物理位置上也相邻，数据元素可以存储在任意位置。为了实现数据元素之间逻辑关系的存储，必须通过一些附加的手段来存储这种相互关系，由此得到的存储表示称为链状存储结构。一般可以用指针来实现，通常可借助计算机程序语言的指针类型或者游标来来描述。

数据的运算： 数据的运算是指定义在数据的逻辑结构上的一组操作的集合。例如，检索（查找）、插入、删除、定位、修改、排序等。要注意的是，这些运算实际上是在逻辑结构上对抽象数据所施加的一系列抽象的操作，运算的实现依赖于所选取的存储结构，是依赖于不同的计算机程序设计语言的。

1.3 数据类型和抽象数据类型 即：数据类型= {值集} + {操作集} 数据类型是具有相同性质的计算机数据的集合及在这个数据集合上的一组运算。 即：数据类型= {值集} + {操作集} 在高级程序语言中，数据类型可以分为原子类型和结构类型。原子类型即值不可分解的类型，如C语言中的整型、字符型、实型、指针类型等；而结构类型则指的是其值可由若干成分按某种结构组成的类型，是可以分解的，如C语言中提供的结构体。 抽象数据类型（ADT）是指一个数学模型及定义在该数学模型上的一组操作（与固有数据类型是一个概念，但范围更广）。抽象数据模型的定义取决于它的一组逻辑特性，与其在计算机内部如何表示和实现无关。

抽象数据类型（简称ADT）： 抽象数据类型由三元组表示 （D，S，P） 本书采用如下格式定义抽象数据类型： ADT 抽象数据类型名 { P是对D的基本操作集 D是数据对象 S是D上的关系 本书采用如下格式定义抽象数据类型： ADT 抽象数据类型名 { 数据对象：（数据对象的定义） 数据关系：（数据关系的定义） 基本操作： （基本操作的定义） } ADT抽象数据类型名 用伪代码描述

基本操作名（参数表） 基本操作的原型定义格式 初始条件: (初始条件定义) 操作结果: (操作结果描述) 例 1-6 抽象数据类型三元组定义（见P9）。 此三元组中给出了8个基本操作函数的原型说明。 例 1-7 抽象数据类型Triplet的表示和实现（见P12）。 此例中不仅给出了8 个操作函数的原型说明，并用类C语言描述了基本操作的实现方法，若上机实现，只须将类C语言描述转换成C或C++程序。 实际就是一个函数

1.4 算法描述与算法评价 1.4.1 算法描述 （1）输入：一个算法必须具有零个或多个的外界输入。 算法是对特定问题求解方法和步骤的一种描述，它是指令的一组有限序列。一个算法必须具备以下五个重要特性： （1）输入：一个算法必须具有零个或多个的外界输入。 （2）输出：一个算法必须有一个或多个的输出。 （3）有穷性：一个算法对任何合法的输入值必须总是在执行有穷步之后结束，并且每步都必须在有穷时间内完成。利用这一点，我们可以区别算法与程序。

（4）确定性：算法中每一条指令必须有确切的含义，不会产生二义性。 （5）可行性：算法中描述的操作都必须可以通过已经实现的基本运算有限次执行来实现，而且算法必须在有限时间内完成。 一个算法可以用自然语言、数学语言或约定的符号来描述，也可用计算机高级程序语言来描述，如PASCAl语言、C语言、C＋＋、Java或伪代码等。本书选用C语言作为描述算法的工具。

1.4.2 算法的设计要求 设计一个好的算法可以从以下几个方面考虑： （1）正确性。算法是为了针对解决具体问题而提出的，算法的正确与否必须满足解决实际问题的需要，要经得起一切可能的输入数据的考验。 （2）可读性。算法要让人阅读得懂，程序要尽可能地简单通俗，当然也必须有效。 （3）健壮性。当输入数据非法时，算法应能适当地作出反应或进行处理。 （4）高效率。要求算法的执行时间要尽可能地短，对于存储空间要尽可能地少，即做到既省时又节省空间。 要设计一个好的算法，必须对这几个方面综合考虑，才可以设计出较好较优的算法。

算法的时间复杂度计算方法： （1）一个语句的频度指该语句重复执行的次数。 （2）一个算法的运行时间（即算法的时间复杂度）是该算法中所有语句的频度之和。 例6 分析以下程序段的时间复杂度。 for(i=1;i<n;i++) { y=y+1; for(j=0;j<=2*n;j++) x++; } (语句1) 的频度为：n-1 (语句2) 的频度为：n-1 (语句3) 的频度为: (n-1)(2n+1) (语句4) 的频度为：(n-1)(2n+1) 该段程序的时间复杂度为：T(n)=2(n-1)+2(n-1)(2n+1)

1.4.3 算法的评价 考虑算法的效率应从下几个方面考虑： （1）时间效率。考虑算法所耗费的运行时间。 （2）空间效率。考虑运行算法需要耗费的存储空间，其中主要考虑算法所需的辅助存储空间。 （3）算法应尽可能地简单，易于理解，易于编码和调试并能得出正确结果。 一个算法的运行时间是指一个算法在计算机上运行所耗费的时间。它可以认为是算法中每条语句的执行时间之和。

上述算法的时间耗费T(n)为(各时间之和)： 例如，两个n×n矩阵相乘的算法： for（i=1；i<=n；i++） /* n+1次 */ for（j=1；j<=n；j++） /* n（n+1）次*/ { c[i] [j] = 0； /* n×n次 */ for（k=1；k<=n；k++） /* 次*/ c[i] [j] = c[i] [j] + [i] [k] * b [k] [j]；/* 次*/ } 上述算法的时间耗费T(n)为(各时间之和)：

之和式中： 当n→∞时，T(n)/ →2，表示当n充分大时，T(n)与 是同阶或者说同数量级，它是矩阵的阶数n的函数。 若引入大“O”记号，则T(n)可记作：T(n)= O( ) ，此时称T(n)= O( )是求解矩阵相乘这个特定问题的渐近时间复杂度。有时将一个算法的渐近时间复杂度O(n)=O(f(n))认为就是时间复杂度。 常见的时间复杂度按数量级递增排列，依次为：常数阶O(1)，对数阶O( )，线性阶O(n)，线性对数阶O( )，平方阶O( )，立方阶O( )，指数阶O( )等等。

有时，可以依据算法转化为程序时各个语句的特点，利用一些简单的程序分析法则进行简单算法分析： （1）对于一些简单的输入、输出语句或赋值语句，它们执行时，近似认为需要O(1)时间； （2）对于顺序结构，需要依次执行一系列语句所用的时间可采用大O下的“求和法则”进行估计； （3）对于选择结构，如如果语句，它的主要时间耗费是在执行然后子句或别的子句所花费的时间，但须注意检验条件也还需要用O(1)的时间；

（4）对于循环结构，循环语句的运行时间主要体现在多次迭代中执行循环体以及检验循环条件的时间耗费，一般地可用大O下的“乘法法则”进行估计；

衡量一个算法好坏的另一个因素是程序运行时所占用的存贮空间大小。 度量一个算法在运行或执行过程中所占用的存储空间的大小类似于时间复杂度，可以用空间复杂度来度量。算法的空间复杂度一般也以相对于问题规模的数量级的形式给出，如O(1)，O(n)等。

例7 分析以下程序段的时间复杂度。 i=1; while(i<=n) i=i*2; (语句1) 的频度为：1 (语句2) 的频度设为：f(n) (2行)的频度为f(n)，则有： 注意：一般不必精确计算出算法的时间复杂度，只要大致计算出相应的数量级。

解：T(m,n)=O(m*n)=n+2(m*n) 例8 分析以下程序段的时间复杂度。 for(i=0;i<n;i++) for(j=0;j<m;j++) A[i][j]=0; 解：T(m,n)=O(m*n)=n+2(m*n) 例9 两个矩阵乘积C=A*B算法的时间复杂度是多少？ { for(i=1;i<=n;i++) (1) {for(j=1;j<=n;j++) (2) {x=0; (3) for(k=1;k<=n;k++) (4) x+=a[i][k]*b[k][j]; (5) C[i][j]=x; (6) } (1)=n

练习： 分析以下程序的时间复杂度： a=0;b=1; for(i=2;i<=n;i++) { s=a+b; b=a; a=s; } 2. 下面是两种二元组表示的数据结构，画出它们分别对应的逻辑图形表示，并指出它们分别属于何种结构。 （1）A=(K,R),其中 K=(a,b,c,d,e,f,g) R={r} r={<a,b>,<b,c>,<c,d>,<d,e>,<e,f>,<f,g>,<g,h>} （2）B=(K.R),其中 K={a,b,c,d,e,f,g,h} R={r} r={<d,b>,<d,g>,<d,a>,<b,c>,<g,e>,<g,h>,<e,f>}