数据结构第1章绪论(作业)

1、第 1章 绪 论 第第1章章 绪论绪论 1.1 基本概念和术语基本概念和术语1.2 数据结构的内容数据结构的内容1.3 算法算法1.4 算法效率的度量算法效率的度量第 1章 绪 论 1.1 基本概念和术语基本概念和术语 1. 数据（数据（Data） 数据是客观事物的符号表示数据是客观事物的符号表示(信息的载体信息的载体),是描述客观事物是描述客观事物的数、字符以及所有能输入到计算机中，被计算机程序识别和的数、字符以及所有能输入到计算机中，被计算机程序识别和处理的符号的集合处理的符号的集合。u 数值性数据数值性数据u 非数值性数据非数值性数据 第 1章 绪 论 例；对例；对C源程序，数据概念不仅

2、是源程序所处理的数据。源程序，数据概念不仅是源程序所处理的数据。C编译程序相对于源程序是一个处理程序，编译程序相对于源程序是一个处理程序， 它加工的数据是字符它加工的数据是字符流的源程序（流的源程序（.c），）， 输出的结果是目标程序输出的结果是目标程序(.obj)； 对于链接程对于链接程序来说，它加工的数据是目标程序序来说，它加工的数据是目标程序(.obj)， 输出的结果是可执输出的结果是可执行程序行程序(.exe)，如图，如图 1.1 所示。所示。 图图1.1 编译程序示意图编译程序示意图 源程序源程序目标程序目标程序可执行程序可执行程序C编译程序编译程序C链接程序链接程序第 1章 绪 论

3、 2. 数据元素（数据元素（Data Element） 数据元素是组成数据的基本单位数据元素是组成数据的基本单位，是数据集合的个体，可，是数据集合的个体，可由若干个数据项组成由若干个数据项组成。 表表1-1 学学 籍籍 表表 学号学号姓名姓名性别性别籍贯籍贯出生年月出生年月住址住址101赵红玲赵红玲女女河北河北1983.11北京北京 数据项数据项记记录录学号学号姓名姓名性别性别籍贯籍贯出生年月出生年月住址住址101赵红玲赵红玲女女河北河北1983.11北京北京 数据项数据项第 1章 绪 论 3. 数据对象（数据对象（Data Object） 数据对象是性质相同的数据元素的集合，是数据的一个子数

4、据对象是性质相同的数据元素的集合，是数据的一个子集。集。例如：整数数据对象例如：整数数据对象N=0， 1， 2， ，字母字符数，字母字符数据对象据对象C=A，B，Z，表，表1-1所示的学籍表也可看所示的学籍表也可看作一个数据对象。作一个数据对象。 结论结论：不论数据元素集合是无限集（如整数集）、有限集：不论数据元素集合是无限集（如整数集）、有限集（如字符集），还是由多个数据项组成的复合数据元素（如学（如字符集），还是由多个数据项组成的复合数据元素（如学籍表），只籍表），只要性质相同，要性质相同， 都是同一个数据对象。都是同一个数据对象。 第 1章 绪 论 综上综上13所述，再分析数据概念：所述

5、，再分析数据概念： 第 1章 绪 论 4. 数据结构（数据结构（Data Structure） 相互之间存在一种或多种特定关系的数据元素集合。相互之间存在一种或多种特定关系的数据元素集合。 类似于树这样的数据结构可以描述类似于树这样的数据结构可以描述家族的家谱、企事业单位家族的家谱、企事业单位中的人事关系中的人事关系，甚至可用树来反映，甚至可用树来反映人机下棋的动态过程人机下棋的动态过程等。等。学校组织结构层次学校组织结构层次第 1章 绪 论 例例: 在在n个城市之间建立通信网络，要求在其中任意个城市之间建立通信网络，要求在其中任意两个城市之间都有直接的或间接的通信线路，在已两个城市之间都有直

6、接的或间接的通信线路，在已知某些城市之间直接通信线路预算造价的情况下，知某些城市之间直接通信线路预算造价的情况下，使网络的造价最低。使网络的造价最低。第 1章 绪 论 我们可以用图描述的关系来说明：图中的小圆圈表示一个城我们可以用图描述的关系来说明：图中的小圆圈表示一个城市，两个圆圈之间的连线表示对应城市间的通信线路，连线市，两个圆圈之间的连线表示对应城市间的通信线路，连线上的数值表示该通信线路的造价。此描述结构为图状结构，上的数值表示该通信线路的造价。此描述结构为图状结构，利用计算机可以求出满足要求的通信网络。利用计算机可以求出满足要求的通信网络。第 1章 绪 论 集合集合 线性表线性表 树

7、树 图图第 1章 绪 论 5. 数据类型数据类型(Data Type) 数据类型是一组性质相同的值集合以及定义在这个值集数据类型是一组性质相同的值集合以及定义在这个值集合上的一组操作的总称合上的一组操作的总称。数据类型中定义了两个集合，即该数据类型中定义了两个集合，即该类型的取值范围，以及该类型中可允许使用的一组运算。例类型的取值范围，以及该类型中可允许使用的一组运算。例如高级语言中的数据类型就是已经实现的数据结构的实例。如高级语言中的数据类型就是已经实现的数据结构的实例。 从这个意义上讲，数据类型是高级语言中允许的变量种类，从这个意义上讲，数据类型是高级语言中允许的变量种类， 是程序语言中已

8、经实现的数据结构（即程序中允许出现的数是程序语言中已经实现的数据结构（即程序中允许出现的数据形式）。在高级语言中，整型类型可能的取值范围是据形式）。在高级语言中，整型类型可能的取值范围是-32 768+32767， 可用的运算符集合为加可用的运算符集合为加、 减、减、 乘、乘、 除、除、 乘方、乘方、 取模（如取模（如C语言中语言中+， -， *， /， %）。）。 第 1章 绪 论 6. 数据抽象与抽象数据类型数据抽象与抽象数据类型 1) 数据的抽象数据的抽象 计算机中使用的是二进制数，汇编语言中则可给出各种数计算机中使用的是二进制数，汇编语言中则可给出各种数据的十进制表示，如据的十进制表示

9、，如98.65、 9.6E3等等, 它们是二进制数据的抽象它们是二进制数据的抽象; 使用者在编程时可以直接使用使用者在编程时可以直接使用, 不必考虑实现细节。在高级语言不必考虑实现细节。在高级语言中，则给出更高一级的数据抽象，出现了数据类型，中，则给出更高一级的数据抽象，出现了数据类型， 如整型、如整型、 实型、字符型等。实型、字符型等。第 1章 绪 论 2) 抽象数据类型抽象数据类型 (Abstract Data Type) 抽象数据类型（简称抽象数据类型（简称ADT）是指一个数学模型以及定义）是指一个数学模型以及定义在该模型上的一组操作。在该模型上的一组操作。从某种意义上讲，抽象数据类型和

10、数从某种意义上讲，抽象数据类型和数据类型实质上是一个概念。据类型实质上是一个概念。整数类型就是一个简单的抽象数据整数类型就是一个简单的抽象数据类型实例。类型实例。“抽象抽象”的意义在于数学特性的抽象。的意义在于数学特性的抽象。 一个一个ADT定义了一个数据对象，数据对象中各元素间的定义了一个数据对象，数据对象中各元素间的结构关系，以及一组处理数据的操作。结构关系，以及一组处理数据的操作。ADT 通常是指由用户通常是指由用户定义且用定义且用以表示应用问题的数据模型，通常由基本的数据类型以表示应用问题的数据模型，通常由基本的数据类型组成，并包括一组相关服务操作。组成，并包括一组相关服务操作。 第

11、1章 绪 论 抽象数据类型是近年来计算机科学中提出的最重要的概念抽象数据类型是近年来计算机科学中提出的最重要的概念之一之一。 一个抽象数据类型确定了一个模型，但将模型的一个抽象数据类型确定了一个模型，但将模型的实现细节隐藏起来；它定义了一组运算，但将运算的实现细节隐藏起来；它定义了一组运算，但将运算的实现过程隐藏起来。实现过程隐藏起来。 可以这样看，高级语言中提供整型、实型、字符、记录、可以这样看，高级语言中提供整型、实型、字符、记录、文件、指针等多种数据类型，可以利用这些类型构造出像栈、文件、指针等多种数据类型，可以利用这些类型构造出像栈、队列、树、图等复杂的抽象数据类型。队列、树、图等复杂

12、的抽象数据类型。 第 1章 绪 论 3) ADT的表示与实现的表示与实现 ADT的定义的定义(定义格式不唯一定义格式不唯一, 我们采用下述格式定义一个我们采用下述格式定义一个ADT)ADT 抽象数据类型名抽象数据类型名 数据对象数据对象: 数据关系数据关系: 基本操作基本操作: ADT 抽象数据类型名抽象数据类型名 第 1章 绪 论 其中数据对象和数据关系的定义采用数学符号和自然语言描其中数据对象和数据关系的定义采用数学符号和自然语言描述，而基本操作的定义格式为述，而基本操作的定义格式为: (参数表参数表) 操作前提操作前提: 操作结果操作结果: 第 1章 绪 论 基本操作主要有以下几种基本操

13、作主要有以下几种： (1) 插入：插入： 在数据结构中的指定位置上增添新的数据元素；在数据结构中的指定位置上增添新的数据元素； (2) 删除：删除： 删去数据结构中某个指定数据元素；删去数据结构中某个指定数据元素； (3) 更新：改变数据结构中某个元素的值，更新：改变数据结构中某个元素的值， 在概念上等价于在概念上等价于删除和插入操作的组合；删除和插入操作的组合； (4) 查找：在数据结构中寻找满足某个特定要求的数据元素查找：在数据结构中寻找满足某个特定要求的数据元素（的位置和值（的位置和值)； (5) 排序：（在线性结构中）重新安排数据元素之间的逻辑排序：（在线性结构中）重新安排数据元素之间

14、的逻辑顺序关系，使数据元素按值由小到大或由大到小的次序排列。顺序关系，使数据元素按值由小到大或由大到小的次序排列。 第 1章 绪 论 1.2 数据结构的内容数据结构的内容 1. 逻辑结构逻辑结构 反映数据元素反映数据元素之间逻辑关系之间逻辑关系的数据结构。的数据结构。图图1.5 四类基本数据结构示意四类基本数据结构示意 集合集合 线性表线性表 树树 图图第 1章 绪 论 (1) 集合结构集合结构：结构中的数据元素之间除了同属于一个集：结构中的数据元素之间除了同属于一个集合的关系外，无任何其它关系。合的关系外，无任何其它关系。 (2) 线性结构线性结构：结构中的数据元素之间存在着一对一的线：结构

15、中的数据元素之间存在着一对一的线性关系。性关系。 (3) 树形结构树形结构：结构中的数据元素之间存在着一对多的层：结构中的数据元素之间存在着一对多的层次关系。次关系。 (4) 图状结构或网状结构图状结构或网状结构：结构中的数据元素之间存在着：结构中的数据元素之间存在着多对多的任意关系多对多的任意关系。 逻辑结构逻辑结构 线性结构线性结构线性表、栈、队、字符串、数组、广义表线性表、栈、队、字符串、数组、广义表非线性结构非线性结构树、树、 图图 第 1章 绪 论 2. 存储结构存储结构 存储结构（又称物理结构）是逻辑结构在计算机中的存存储结构（又称物理结构）是逻辑结构在计算机中的存储表示（又称映像

16、），是逻辑结构在计算机中的存放形式，储表示（又称映像），是逻辑结构在计算机中的存放形式，它包括数据元素的表示和关系的表示。它包括数据元素的表示和关系的表示。 第 1章 绪 论 逻辑结构与存储结构的关系为逻辑结构与存储结构的关系为：逻辑结构是数据结构的抽：逻辑结构是数据结构的抽象，存储结构是数据结构的实现，两者综合起来建立了数据元象，存储结构是数据结构的实现，两者综合起来建立了数据元素之间的结素之间的结构关系。构关系。 顺序映象顺序映象 （顺序存储结构）（顺序存储结构） 非顺序映象（非顺序存储结构）非顺序映象（非顺序存储结构） 第 1章 绪 论 3. 运算集合运算集合 -工工 资资 表表 第 1

17、章 绪 论 数据结构的内容可归纳为三个部分：数据结构的内容可归纳为三个部分：逻辑结构、存储逻辑结构、存储结构和运算集合结构和运算集合。按某种逻辑关系组织起来的一批数据，。按某种逻辑关系组织起来的一批数据，按一定的映象方式把它存放在计算机的存储器中，并在这按一定的映象方式把它存放在计算机的存储器中，并在这些些数据上定义了一个运算的集合，数据上定义了一个运算的集合， 就叫做数据结构。就叫做数据结构。 第 1章 绪 论 1.3 算算 法法 1. 算法（算法（Algorithm）的定义）的定义 算法是对特定问题求解步骤的一种描述，是指令的有算法是对特定问题求解步骤的一种描述，是指令的有限序列。限序列。

18、 第 1章 绪 论 2. 算法的特性算法的特性 (1) 有穷性有穷性：有限步骤之内正常结束，有限步骤之内正常结束， 不能形成无穷循环。不能形成无穷循环。 (2) 确定性确定性： 算法中的每一个步骤必须有确定含义，算法中的每一个步骤必须有确定含义， 无无二义性。二义性。 (3) 可行性可行性： 算法中描述的操作可通过已实现的基本运算算法中描述的操作可通过已实现的基本运算执行有限次而完成。执行有限次而完成。 (4) 输入输入： 有多个或有多个或0个输入个输入。 (5) 输出输出： 至少有一个或多个输出。至少有一个或多个输出。 第 1章 绪 论 3. 算法设计的要求算法设计的要求 1) 算法的正确性

19、算法的正确性 (1) 所设计的程序没有语法错误；所设计的程序没有语法错误； (2) 所设计的程序对于几组输入数据能够得出满足要求的所设计的程序对于几组输入数据能够得出满足要求的结果；结果； (3) 所设计的程序对于精心选择的典型、所设计的程序对于精心选择的典型、 苛刻而带有刁难苛刻而带有刁难性的几组输入数据能够得到满足要求的结果。性的几组输入数据能够得到满足要求的结果。 (4) 程序对于一切合法的输入数据都能产生满足要求的结程序对于一切合法的输入数据都能产生满足要求的结果。果。 第 1章 绪 论 例如：例如： 要求要求n个数的最大值问题，个数的最大值问题， 给出示意算法如下：给出示意算法如下：

20、 max=0; for（i=1； imax) max=x; 第 1章 绪 论 2） 可读性可读性：应有助于人对算法的理解应有助于人对算法的理解3） 健壮性健壮性：当输入数据非法时，算法应作出反应和作出处理当输入数据非法时，算法应作出反应和作出处理 4） 高效率和低存储量高效率和低存储量：同一个问题如果有多种算法，执行同一个问题如果有多种算法，执行时间短的算法效率高时间短的算法效率高 第 1章 绪 论 1.5 算法效率的度量算法效率的度量 1. 性能评价性能评价 对问题规模和该算法在运行时所占的空间对问题规模和该算法在运行时所占的空间S与所耗费的与所耗费的时间时间T给出一个数量关系的评价。给出一

21、个数量关系的评价。 第 1章 绪 论 2. 有关数量关系的计算有关数量关系的计算 数量关系评价体现在数量关系评价体现在时间时间算法算法编程后在机器中所耗费编程后在机器中所耗费的时间。的时间。 数量关系评价体现在数量关系评价体现在空间空间算法算法编程后在机器中所占的编程后在机器中所占的存储量。存储量。 1） 关于算法执行时间关于算法执行时间 一个算法的执行时间大致上等于其所有语句执行时间的总一个算法的执行时间大致上等于其所有语句执行时间的总和，和， 对于语句的执行时间是指该条语句的执行次数和执行一次对于语句的执行时间是指该条语句的执行次数和执行一次所需时间的乘积。所需时间的乘积。 第 1章 绪

22、论 2） 语句频度语句频度语句频度是指该语句在一个算法中重复执行的次数。语句频度是指该语句在一个算法中重复执行的次数。 例例1-1 两个两个nn阶矩阵相乘。阶矩阵相乘。 第 1章 绪 论 3） 算法的时间复杂度算法的时间复杂度 算法中语句总的执行次数T(n) ，为所有语句的频度之和。不必精确计算，求出数量级即可。在这里， 我们用“O”来表示数量级，这样我们可以给出算法的时间复杂度概念。 所谓算所谓算法的时间复杂度，法的时间复杂度， 即是算法的时间量度，即是算法的时间量度，记作： T(n)=O(f(n) 它表示随问题规模它表示随问题规模n的增大，算法的执行时间的增长率和的增大，算法的执行时间的增长率和f(n)的的增长率相同，称作算法的增长率相同，称作算法的渐进时间复杂度，简称时间复杂度渐进时间复杂度，简称时间复杂度。第 1章 绪 论 一般情况下，一般情况下， 随随n的增