第1章 绪论.docx

1、第1章 绪论第一章 绪论教学目的：1、 培养学生实际动手和抽象的思维能力。2、 培养学生实际使用抽象数据类型解决问题的能力。教学要求：1、 了解数据结构的发展过程，数据结构的定义。2、 掌握数据结构中所用的相关术语。3、 掌握抽象数据类型的表示和实现。4、 掌握算法和算法分析的方法。教学重点：抽象数据类型的定义。教学难点：抽象数据定义及算法的分析方法。课时安排：本章总课时为5课时，其中理论课时3节，上机课时2节教学手段：使用计算机多媒体设备进行教学。教学过程：“ 数据结构 ” 学科形成和发展的背景自 1946 年第一台计算机问世以来，计算机产业的飞速发展已远远超出人们对它的预料。如今，计算机已

2、深入到人类社会的各个领域。计算机的应用已不再局限于科学计算，而更多地用于控制、管理及数据处理等非数值计算的处理工作。与此相应，计算机加工处理的 对象 由纯粹的数值发展到字符、表格和图象等各种具有一定结构的数据，这就给程序设计带来一些新的问题。为了编写一些 “ 好 ” 的程序，必须分析待处理对象的特性以及各处理对象间的关系。这就是 “ 数据结构 ” 这门学科形成和发展的背景。 数据结构的研究目的和研究内容 数据结构的研究目的是寻求有效的组织和处理非数值数据的理论技术和方法 , 这类数据具有量大且具有一定内在逻辑关系的特点。数据结构的主要研究内容包括三个方面 : 数据的逻辑结构 , 存储结构以及相

3、应的基本操作运算的定义和实现。 1.1 什么是数据结构 1.2 基本概念和术语 1.3 抽象数据类型的表示与实现 1.4 算法与算法分析 什么是数据结构（ 1 学时） 一般来说，用计算机解决一个具体问题时，大致需要经过下列几个步骤： 首先要从具体问题抽象出一个适当的数学模型； 然后设计一个解此数学模型的算法； 最后编出程序、进行测试、调整直至得到最终解答。 寻求数学模型的实质是分析问题，从中提取操作的对象，并找出这些操作对象之间含有的关系，然后用数学的语言加以描述。例如，求解梁架结构中应力的数学模型为线性方程组；预报人口增长情况的数学模型为微分方程。然而，更多的非数值计算问题无法用数学方程加以

4、描述。下面请看三个例子： 图书馆书目的自动化检索问题 由此，在书目检索系统中可以建立一张按登录号顺序排列的书目文件和三张分别按书名、作者名和分类号顺序排列的索引表，如图 1.1 所示。 001 高等数学 樊映川 S01 002 理论力学 罗远祥 L01 003 高等数学 华罗庚 S01 004 线形代数 栾汝书 S02 高等数学 001,003,. 理论力学 002,. 线性代数 004,. . . 樊映川 001,. 华罗庚 003,. 栾汝书 004,. . . L 002,. S 001,003,. . . 图 1.1 图书自动检索数学模型 由这四张表构成的文件便是书目自动检索的数学模型

5、，计算机的主要操作便是按照某个特定要求（如给定书名 ) 对书目文件进行查询。诸如此类的还有查号系统自动化、仓库账目管理等等。 在这类文档管理的数学模型中，表中的一行作为一个数据元素，各个数据元素按照顺序排列，形成数据元素之间的线性序列，即表中的数据元素除第一个数据元素和最后一个数据元素外，其他任何一个数据元素与前后数据元素有一一对应关系，称这类数学模型为 线性的数据结构 。 例 1-2 计算机和人对奕问题 在对奕问题中，计算机操作的对象是对奕过程中可能出现的棋盘状态 称为格局。例如下图 (a) 所示为井字棋的一个格局，一个格局就是一个数据元素，而格局之间的关系是由比赛规则决定的。通常，这个关系

6、不是线性的，因为从一个棋盘格局可以派生出几个格局，例如从下图 (a) 所示的格局可以派生出五个格局，如下图所示，而从每一个新的格局又可派生出四个可能出现的格局，如图 .2 所示。 图 1.2 人机对奕数学模型 因此，若将从对奕开始到结束的过程中所有可能出现的格局都画在一张图上，则可得到一棵倒长的 “ 树 ” 。 “ 树根 ” 是对奕开始之前的棋盘格局，而所有的 “ 叶子 ” 就是可能出现的结局，对奕的过程就是从树根沿树叉到某个叶子的过程。 “ 树 ” 可以是某些非数值计算问题的数学模型，它也是一种数据结构。例 1-3 多叉路口交通灯的管理问题 通常，在十字交叉路口只需设红、绿两色的交通灯便可保

7、持正常的交通秩序，而在多交叉路口需设几种颜色的交通灯才 能使车辆相互之间不碰撞，又能达到车辆的最大流通。 假设有一个如图 1 3(a) 所示的五叉路口，其中 C 和 E 为单行道。在路口有 13 条可行的通路，其中有的可以同时通行，如 AB 和 EC ，而有的不能同时通行，如 EB 和 AD 。那末，在路口应如何设置交通灯进行车辆的管理呢 ? 通常，这类交通、道路问题的数学模型是一种称谓 “ 图 ” 的数据结构。例如在此例题中，可以用图中一个顶点表示一条通路，而通路之间互相矛盾的关系以两个顶点之间的连线表示。设置交通灯的问题等价为对图的顶点的染色问题，要求对图上的每个顶点染一种颜色，并且要求有

8、线相连的两个顶点不能具有相同颜色，而总的颜色种类应尽可能地少。 综上三个例子可见，描述这类非数值问题的数学模型不再是数学方程，而是诸如表、树和图之类的数据结构。因此简单说来，数据结构是一门研究非数值计算的程序设计问题中计算机的操作对象以及它们之间的关系和操作等等的学科。 1.2 基本概念和术语 (1 学时） 数据 (Data) 是对客观事物的符号表示，在计算机科学中是指所有能输入到计算机中并被计算机程序处理的符号的总称。它是计算机程序加工的 “ 原料 ” 。 例如 ，一个利用数值分析方法解代数方程的程序，其处理对象是整数和实数；一个编译程序或文字处理程序的处理对象是字符串。因此，对计算机科学而

9、言，数据的含义极为广泛，如图象、声音等都可以通过编码而归之于数据的范畴。 数据元素 (DataElement) 是数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理。 例如 ，例 1-1 中的表中的一行作为一个数据元素，例 1-2 中的 “ 树 ” 中的一个棋盘格局作为一个数据元素，例 1-3 中的 “ 图 ” 中的一个圆圈都被称为一个数据元素。有时，一个数据元素可由若干个 数据项 (Data Item) 组成， 例如 ，例 1-1 中一本书的书目信息为一个数据元素，而书目信息中的每一项 ( 如书名、作者名等 ) 为一个数据项。数据项是数据的不可分割的最小单位。 数据对象 (Data

10、 Object) 是性质相同的数据元素的集合，是数据的一个子集。 例如 ，整数数据对象是集合 N=0 ， 1 ， 2 ， ，字母字符数据对象是集合 C=A ， B ， ， Z 。 数据结构 (Data Structure) 是相互之间存在一种或多种特定关系的数据元素的集合。从 1.1 节中三个例子可以看到，在任何问题中，数据元素都不是孤立存在的，而是在它们之间存在着某种关系，这种数据元素相互之间的关系称为结构 (Structure) 。 根据数据元素之间关系的不同特性，通常有下列四类基本结构： (1) 集合 结构中的数据元素之间除了 “ 同属于一个集合 ” 的关系外，别无其它关系； (2) 线

11、性结构 结构中的数据元素之间存在一对一的关系； (3) 树形结构 结构中的数据元素之间存在一对多的关系； (4) 图状结构或网状结构 结构中的数据元素之间存在多对多的关系。 数据结构的形式定义为： 数据结构是一个二元组 Data_Structure=(D ， S)(1-1) 其中： D 是数据元素的有限集， S 是 D 上关系的有限集。 例 1-4 在计算机科学中，复数可取如下定义：复数是一种数据结构 Complex=(C ， R)(1-2) 其中： C 是含两个实数的集合 c 1 ， c 2 ； R=P ，而 P 是定义在集合 C 上的一种关系 ，其中有序偶 表示 c 1 是复数的实部， c

12、 2 是复数的虚部。 例 1-5 假设我们需要编制一个学校科学研究的事务管理的程序，管理学校科学研究课题小组的各项事务，则首先要为程序的操作对象 课题小组设计一个数据结构。假设每个小组由一位教师、一至三名研究生及一至六名本科生组成，小组成员之间的关系是：教师指导研究生，而由每位研究生指导一至两名本科生。则可以如下定义数据结构： Group = (P ， R)(13) 其中 : P = T ， G 1 ， ， G n ， S 11 S nm 1=n=3 ， 1=m=2 ， R = R 1 , R 2 R 1 = | 1=i=n, 1=n=3 R 2 = | 1=i=n, 1=j=m, 1=n=3

13、, 1=m=2 数据结构包括逻辑结构和物理结构两个方面（或层次）： 逻辑结构 是对数据元素之间的逻辑关系的描述，它用一个数据元素的集合和定义在此集合上的若干关系来描述； 逻辑结构在计算机中的表示 ( 又称映象 ) 称为数据的 物理结构 ，又称 存储结构 。它包括数据元素的表示和关系的表示。在计算机中表示信息的最小单位是二进制数的一位，叫做位 (bit) 。在计算机中，我们可以用一个由若干位组合起来形成的一个位串表示一个数据元素 ( 如用一个字长的位串表示一个整数，用八位二进制数表示一个字符等 ) ，通常称这个位串为 元素 (Element) 或结点 (Node) 。当数据元素由若干数据项组成时

14、，位串中对应于各个数据项的子位串称为 数据域 (DataField) 。因此，元素或结点可看成是数据元素在计算机中的映象。 数据元素之间的关系在计算机中有两种不同的表示方法： 顺序映象 和 非顺序映象 ，并由此得到两种不同的存储结构： 顺序存储结构 和 链式存储结构 。 顺序映象的特点是借助元素在存储器中的相邻位置来表示数据元素之间的逻辑关系。例如，假设用两个字长的位串表示一个实数，则可以用地址相邻的四个字长的位串表示一个复数。 非顺序映象的特点是借助指示元素存储地址的指针 (Pointer) 表示数据元素之间的逻辑关系。 数据的逻辑结构和物理结构是密切相关的两个方面，在后面的课程中我们会看到

15、，任何一个算法的设计取决于选定的数据 ( 逻辑 ) 结构，而算法的实现依赖于所采用的存储结构。如何描述存储结构呢？ 我们可以借用高级程序语言中提供的 “ 数据类型 ” 来描述它，例如可以用所有高级程序语言中都有的 “ 一维数组 ” 类型来描述顺序存储结构，以 C 语言提供的 “ 指针 ” 来描述链式存储结构。 假如 , 我们把 C 语言看成是一个执行 C 指令和 C 数据类型的虚拟处理器，那么讨论的存储结构是数据结构在 C 虚拟处理器中的表示，不妨称它为 虚拟存储结构 。 数据类型 (DataType) 是和数据结构密切相关的一个概念，它最早出现在高级程序语言中，用以刻画 ( 程序 ) 操作对

16、象的特性。在用高级程序语言编写的程序中，每个变量、常量或表达式都有一个它所属的确定的数据类型。类型明显或隐含地规定了在程序执行期间变量或表达式所有可能取值的范围，以及在这些值上允许进行的操作。因此 数据类型 是一个值的 集合 和定义在这个值集上的 一组操作 的总称。 例如 ， C 语言中的整型变量，其值集为某个区间上的整数 ( 区间大小依赖于不同的机器 ) ，定义在其上的操作为：加、减、乘、除和取模等算术运算。 按 “ 值 ” 的不同特性，高级程序语言中的数据类型可分为两类： 一类是非结构的 原子类型 。原子类型的值是不可分解的。 例如， C 语言中的基本类型 ( 整型、实型、字符型和枚举类型

17、 ) 、指针类型和空类型。 另一类是 结构类型 。结构类型的值是由若干成分按某种结构组成的，因此是可以分解的，并且它的成分可以是非结构的，也可以是结构的。 例如 , 数组的值由若干分量组成，每个分量可以是整数，也可以是数组等。在某种意义上，数据结构可以看成是 “ 一组具有相同结构的值 ” ，则结构类型可以看成由一种数据结构和定义在其上的一组操作组成。 抽象数据类型 (Abstract Data Type ， 简称 ADT) 是指一个数学模型以及定义在该模型上的一组操作，面向逻辑层次。抽象数据类型的定义仅取决于它的一组逻辑特性，而与其在计算机内部如何表示和实现无关，即不论其内部结构如何变化，只要

18、它的数学特性不变，都不影响其外部的使用。 抽象数据类型和数据类型实质上是一个概念。 例如 ，各个计算机都拥有的 “ 整数 ” 类型是一个抽象数据类型，尽管它们在不同处理器上实现的方法可以不同，但由于其定义的数学特性相同，在用户看来都是相同的。因此， “ 抽象 ” 的意义在于数据类型的数学抽象特性。 另一方面，抽象数据类型的范畴更广，它不再局限于前述各处理器中已定义并实现的数据类型 ( 也可称这类数据类型为固有数据类型 ) ，还包括用户在设计软件系统时自己定义的数据类型。为了提高软件的复用率，在近代程序设计方法学中指出，一个软件系统的框架应建立在数据之上，而不是建立在操作之上 ( 后者是传统的软

19、件设计方法所为 ) 。即在构成软件系统的每个相对独立的模块上，定义一组数据和施于这些数据上的一组操作，并在模块内部给出这些数据的表示及其操作的细节，而在模块外部使用的只是抽象的数据和抽象的操作。显然，所定义的数据类型的抽象层次越高，含有该抽象数据类型的软件模块的复用程度也就越高。 如前所述，抽象数据类型的定义由一个值域和定义在该值域上的一组操作组成。 例如，在 C 语言中，整型数据表达式 3/2 的值为 1 ，而实型数据表达式 3.0/2 的值为 1.5 。原因在于 3 和 3.0 是不同的数据类型，即在不同值域和定义在该值域上的一组操作所引起的。 若按其值的不同特性，可细分为下列三种类型：

20、1) 原子类型 (Atomic Data Type) 属原子类型的变量的值是不可分解的。这类抽象数据类型较少，因为一般情况下，已有的固有数据类型足以满足需求。但有时也有必要定义新的原子数据类型，例如，数位为 100 的整数。 2) 固定聚合类型 (Fixed-aggregate Data Type) 属该类型的变量，其值由确定数目的成分按某种结构组成。例如，复数是由两个实数依确定的次序关系构成。 3) 可变聚合类型 (Variable-Aggregate Data Type) 和固定聚合类型相比较，构成可变聚合类型 “ 值 ” 的成分的数目不确定。例如，可定义一个 “ 有序整数序列 ” 的抽象

21、数据类型，其中序列的长度是可变的。 显然，后两种类型可统称为结构类型。 和数据结构的形式定义相对应，抽象数据类型可用三元组表示。 (D ， S ， P)(14) 其中， D 是数据对象， S 是 D 上的关系集， P 是对 D 的基本操作集。 抽象数据类型页可以使用如下格式来描述： ADT 抽象数据类型名 数据对象： 数据关系： 基本操作： ADT 抽象数据类型名 其中，数据对象和数据关系的定义用伪码描述，基本操作的定义格式为： 基本操作名 ( 参数表 ) 初始条件： 操作结果： 1.3 抽象数据类型的表示与实现 (1 学时） 抽象数据类型 可通过固有数据类型来表示和实现，即利用处理器中已存在

22、的数据类型来说明新的结构，用已经实现的操作来组合新的操作。 我们采用介于伪码和 C 语言之间的类 C 语言作为描述工具，简要说明如下： (1) 预定义常量和类型： / 函数结果状态代码 #define TRUE 1 #define FALSE 0 #define OK 1 #define ERROR 0 #define INFEASIBLE -1 #define OVERFLOW -2 /Status 是函数的类型，其值是函数结果状态代码 typedef int Status ； (2) 数据结构的表示 ( 存储结构 ) 用类型定义 (typedef) 描述。数据元素类型约定为 ElemTyp

23、e ，由用户在使用该数据类型时自行定义。 (3) 基本操作的算法都用以下形式的函数描述： 函数类型函数名 ( 函数参数表 )/ 算法说明 语句序列 / 函数名 除了函数的参数需要说明类型外，算法中使用的辅助变量可以不作变量说明，必要时对其作用给予注释。一般而言， a 、 b 、 c 、 d 、 e 等用作数据元素名， i 、 k 、 1 、 m 、 n 等用作整型变量名， p 、 q 、 r 等用作指针变量名。当函数返回值为函数结果状态代码时，函数定义为 Status 类型。为了便于算法描述，除了值调用方式外，增添了 C+ 语言的引用调用的参数传递方式。在形参表中，以 & 打头的参数即为引用参

24、数。 (4) 赋值语句有 简单赋值 变量名 = 表达式； 串联赋值 变量名 1 = 变量名 2 = = 变量名 k = 表达式； 成组赋值 ( 变量名 1 ， ，变量名 k) = ( 表达式 1 ， ，表达式 k) ； 结构名 = 结构名； 结构名 = ( 值 1 ， ，值 k) ； 变量名 = 表达式； 变量名 起始下标 . 终止下标 = 变量名 起始下标 . 终止下标 交换赋值 变量名 变量名； 条件赋值 变量名 = 条件表达式？ 表达式 T : 表达式 F (5) 选择语句有 条件语句 1 if( 表达式 ) 语句； 条件语句 2 if( 表达式 ) 语句； else 语句； 开关语句

25、1 switch( 表达式 ) case 值 1 ： 语句序列 1 ； break; case 值 n ： 语句序列 n ； break ： default ： 语句序列 n+1 ； 开关语句 2 switch( 表达式 ) case 值 1 ： 语句序列 1 ； break; case 值 n ： 语句序列 n ； break ： default ： 语句序列 n+1 ； (6) 循环语句有 for 语句 for( 赋初值表达式序列 ；条件；修改表达式序列）语句； while 语句 while( 条件 ) 语句； do-while 语句 do 语句序列； while( 条件 ) ； (7)

26、结束语句有 函数结束浯句 return 表达式 return ； case 结束语句 break ； 异常结束语句 exit( 异常代码 ) ; (8) 输入和输出语句有 输入语句 scanf ( 格式串 ，变量 1 ， ，变量 n) ； 或 cin 变量 1 变量 n; 输出语句 printf( 格式串 ，表达式 1 ， ，表达式 n); 或 cout 表达式 1 表达式 n; 通常省略格式串。 (9) 注释 单行注释 / 文字序列 (10) 基本函数有 求最大值 max ( 表达式 l ， ，表达式 n) 求最小值 min ( 表达式 1 ， ，表达式 n) 求绝对值 abs ( 表达式

27、) 求不足整数值 floor( 表达式 ) 求进位整数值 ceil( 表达式 ) 判定文结束 eof( 文件变量 ) 或 eof 判定行结束 eoln( 文件变量 ) 或 eoln (11) 逻辑运算约定 与运算 & 对于 A&B ，当 A 的值为 0 时，不再对 B 求值。 或运算 | 对于 A|B ，当 A 的值为非 0 时，不再对 B 求值。 例 17 抽象数据类型三元组（ Trip1et ）的表示和实现。 / 采用动态分配的顺序存储结构 Typedef ElemType *Triplet ； / 基本操作的函数原型说明 Status InitTriplet (Triplet &T ， ElemType vl ， ElemType v2 ， ElemType v3) ； / 操作结果：构造了三元组