数据结构(绪论)第1章

1、数 据 结 构 第1章 绪论一、 基本概念 利用计算机处理的问题类型 数值计算问题，主要用不同的数学方程来描述 例1 利用有限元计算方法进行结构静力分析计算 例2 利用环流模式方程进行天气预报计算 非数值计算问题，主要用不同的数据结构来描述 例1 图书馆书目检索 例 2 计算机和人对奕问题 例 3 交通灯的控制系统基本概念数据、数据对象等 数据（data） 是对客观事物的符号化表示，是信息、概念与知识的载体 数据项（data item） 是构成数据的相对独立的分项，它反映客观事物的某种特性 数据元素（data element） 是构成数据的具有相同性质的基本单元 数据对象（data objec

2、t） 是性质相同的数据元素的集合。 是数据的一个子集。 是一种运行时的概念。基本概念数据结构 数据结构（data structure） 是相互之间存在一种或多种特定关系的数据元素的集合数据结构的二元组表示：Data_Structure = (D, S)其中：D是数据元素的有限集，S是D上关系的有限集基本概念数据结构 例如一维数组是一种线性的数据结构，由n 个元素有序排列而成，表示为： Array = 数据元素的集合是D = a1, a2, , an 数据元素关系的集合是S = RR=| 1in 其中为序偶基本概念数据结构 按照软件系统开发过程中的数据层次模型，数据之间存在两种结构关系 数据的逻

3、辑结构（位于逻辑层），反映数据元素之间的逻辑关系，由抽象数据类型来表达 数据的物理结构（位于实现层），也称存储结构，考虑的是数据在计算机中是如何存储和组织的基本概念数据结构 数据元素之间的逻辑关系通常可分为4类基本的逻辑结构 1. 集合 结构中的数据元素同属一个集合 2. 线性结构 结构中的元素之间存在一个对一个的关系 3. 树型结构 结构中的数据元素之间存在一个对多个的关系 4. 图状结构或网状结构 结构中的数据元素之间存在多个对多个的关系逻辑结构例 学生选课问题 该问题可以用三张数据表来表示，每张表中每条记录为数据元素 如表中数据元素是无序的，则数据表构成集合结构 如表中数据元素是有序的，

4、则数据表构成线性结构学生表课程表选课表学号姓名课程号课程名称学号课程号成绩S0001张三C0001数据结构S0001C000185S0002李四C0002操作系统S0001C000376S0005王五C0003编译原理S0002C000190C0004数据库原理S0002C000483S0003 C000292逻辑结构例 三维实体造型问题 左图的机械零件可以分解成三个基本的实体模型通过布尔运算+和-操作得到 右图构成了一个树型的数据结构，每一个节点为一个基本实体模型或通过布尔运算得到的复合实体模型逻辑结构例 地图表示问题 左图的地图经抽象可以得到右图的结构 右图构成了图状的数据结构数据的物理结

5、构 数据的存储结构 逻辑结构在存储器中的映象 “数据元素”如何映象 ？ “关系”如何映象 ？数据的物理结构 数据元素在计算机内部实际存储时，根据各数据元素之间相对的存储位置及相互之间的关系，存在着两种存储结构 顺序存储结构 在存储器中，数据元素是依次存放的依次存放的，数据元素在物理存储器上的位置关系体现了它们在逻辑上的顺序关系 链式存储结构 在存储器中，数据元素是分散存放的分散存放的，在一个数据元素中，必须有一个或若干专门的数据项来指示其他相关联的数据元素在存储器中的位置数据的物理结构 分别用顺序结构和链式结构来存储数列“10,20,30,40”数列的顺序存储结构数列的链式存储结构数据的物理结

6、构 链式映象需要用一个附加信息指示下一元素的存储位置基本概念数据类型 数据类型在用高级程序语言编写的程序中，必须对程序中出现的每个变量、常量或表达式，明确说明它们所属的数据类型。基本概念数据类型（C+为例） 基本数据类型 字符（char）、整数（int）、浮点数（float/double）、指针（*）、引用（&） 复杂数据类型 数组（）、结构（struct）、枚举（enum）、类（class）、联合（union） 不同类型的变量，其所能取的值的范围不同， 所能进行的操作不同。基本概念数据类型 数据类型 是一个 值的集合和定义在此集合上 的一组操作的总称。 软件开发系统中，仅有基本数据类

7、型是远远不够的，软件开发人员可以利用基本数据类型来构造新的数据类型。新数据类型的引入，丰富了程序的语义表达功能。如C语言中的结构体（struct类型）。基本概念抽象数据类型 在软件系统开发的全过程中，对客观现实中存在的事物，存在三个观察层面 应用层是用户通过物理观察得到的客观事物的视图，是可以用自然语言描述的，或用图形、图像、音频、视频等物理量表达的在概念层次上的数据。 逻辑层（抽象层）是从应用层次抽象出来的数据视图，利用抽象数据类型进行形式化描述。 实现层明确地表示出了数据的组织与存储结构，并用某种具体的程序设计语言进行代码实现。基本概念抽象数据类型 抽象数据类型（ADT，Abstract

8、Data Type） 是与具体计算机内部表示和实现方式无关的数据类型 是由一个逻辑上的数学模型以及定义在该模型上的一组操作构成 可以用三元组定义 (D, S, P) D是数据对象 S是D上的关系集 P是对D的基本操作集 抽象数据类型和数据类型实际上是一个概念基本概念抽象数据类型 ADT 有两个重要特征:一、数据抽象 用ADT描述程序处理的实体时，强调的是其本质的特征、其所能完成的功能以及它和外部用户的接口（即外界使用它的方法）。二、数据封装 将实体的外部特性和其内部实现细节分离，并且对外部用户隐藏其内部实现细节。抽象数据类型例 ADT Set/ 集合的抽象数据类型 数据对象：D ai | ai

9、ElemType, i= 1, 2, ., n, n 0 数据关系：R = aiaj | ai,ajD 基本操作：Init() 操作结果：构造一个空的集合。Destroy()操作结果：销毁集合。IsEmpty() 操作结果：判断集合是否为空，如为空，则返回TRUE；否则返回FALSE。 Insert(e)操作结果：在集合中加入一个元素。如元素已存在，返回FALSE；否则返回TRUE。 Remove(e) 操作结果：在集合中移除一个元素。如元素存在，则返回TRUE；否则返回FALSE。 IsMember(e) 操作结果：判断在集合中是否存在元素。抽象数据类型例 FindFirst(&e)

10、操作结果：找到集合中的第一个元素。如成功，返回TRUE；如果集合为空，返回FALSEFindNext(&e) 初始条件：已经执行过FindFirst或FindNext操作 操作结果：在上一次查找的前提下，找到集合中的下一个元素；如成功，返回TRUE；如上次查找已到最后一个元素，返回FALSE。 Union(s)操作结果：与另一个集合s做并运算，返回并集。Intersection(s)操作结果：与另一个集合s做交运算，返回交集。Difference(s)操作结果：与另一个集合s做差运算，返回差集。二、算法与算法分析 程序 为计算机处理问题编制一组指令集 算法 处理问题的策略 数据结构 问

11、题的数学模型Algorithm + Data Structures = Programs算法 + 数据结构 = 程序 - Niklaus Wirth算法 算法（algorithm） 解决某一特定问题的具体步骤的描述，是指令的有限序列 算法的五个重要特征 有穷性 确定性 有效性 输入 输出算法 1有穷性 对于任意一组合法输入值，在执行有穷步骤之后一定能结束，即：算法中的每个步骤都能在有限时间内完成。 2确定性 对于每种情况下所应执行的操作，在算法中都有确切的规定，使算法的执行者或阅读者都能明确其含义及如何执行。并且在任何条件下，算法都只有一条执行路径。算法 3有效性 算法中的所有操作都必须足够基

12、本，都可以通过已经实现的基本操作运算有限次实现之。 4有输入 作为算法加工对象的量值，通常体现为算法中的一组变量。有些输入量需要在算法执行过程中输入，而有的算法表面上可以没有输入，实际上已被嵌入算法之中。 5有输出 它是一组与“输入”有确定关系的量值，是算法进行信息加工后得到的结果，这种确定关系即为算法的功能。 算法 算法设计的原则： 设计算法时，通常应考虑达到以下目标： 1正确性 2. 可读性 3健壮性 4高效率与低存储量需求 算法的性能分析与度量 算法性能的度量方法 事后测试 可采用一些程序运行性能跟踪与测量工具（如Profiler） 预先评做 不考虑算法的实现语言、编译器、运行的硬件平台

13、，只考虑在一定问题规模下算法运行的时间复杂度和空间复杂度 性能度量 时间复杂度 按某种算法设计的程序在计算机上执行时花费的CPU时间的度量 空间复杂度 按某种算法设计的程序在计算机上执行时需要使用的存储空间的度量 算法的性能分析与度量 和算法执行时间相关的因素： 1算法选用的策略 2问题的规模 3编写程序的语言 4编译程序产生的机器代码的质量 5计算机执行指令的速度 算法的性能分析与度量 一个特定算法的“运行工作量”的大小，只依赖于问题的规模（通常用整数量n表示），或者说，它是问题规模的函数。 算法 = 控制结构 + 原操作 （固有数据类型的操作） 算法的执行时间 = 原操作(i)的执行次数原

14、操作(i)的执行时间 算法的性能分析与度量 时间复杂度 从算法中选取对于所处理问题来说是关键步骤的程序语句作为基本操作，该基本操作重复执行的次数作为算法的时间量度。 基本操作重复执行的次数一般为问题规模n的某个函数f(n)，因此时间的复杂度T(n)记作T (n) = O( f (n) ) 上式表示随着问题规模n的增长，算法执行时间T(n)和f(n)同比增长注：注：通常不需要精确计算基本操作的执行次数，而只是关注f(n)中阶数最高的项，同时忽略掉低阶项的系数以及其他低阶的项。时间复杂度例 语句+x为三个算法的基本操作，问题规模为n 三段程序中基本操作的执行次数分别为1、n和n2 故三段程序的时间

15、复杂度分别为O(1)、O (n)和O (n2)，称为常量阶、线性阶和平方阶/ 例1 +x;/基本操作 s = 0;/ 例2for (i = 0; i n; +i) +x;/基本操作 s += x;/ 例3for (i = 0; i n; +i) for (j = 0; j n; +j) +x;/基本操作 s += x; 时间复杂度例 语句+x为算法的基本操作 算法中基本操作的执行次数是0 + 1 + . + (n 2) = (n 1) (n 2) / 2 上式中随着n的增长，增长率最快的项是n2 ，故该算法的时间复杂度分别为O (n2)/ 例4for (i = 2; i = n; +i) fo

16、r (j = 2; j = i - 1; +j) +x;/基本操作 s += x; 时间复杂度例 例例: 两个矩阵相乘两个矩阵相乘void mult(int a, int b, int& c ) / 以二维数组存储矩阵元素，c 为 a 和 b 的乘积 for (i=1; i=n; +i) for (j=1; j=n; +j) ci,j = 0; for (k=1; k=n; +k) ci,j += ai,k*bk,j; /for /mult基本操作: 乘法乘法操作时间复杂度: O(n3)时间复杂度例 例例: 选择排序选择排序void select_sort(int& a, in

17、t n) / 将将 a 中整数序列重新排列成自小至大有序的整数序列中整数序列重新排列成自小至大有序的整数序列。for ( i = 0; i n-1; +i ) j = i ;/ 选择第选择第 i i 个最小元素个最小元素 for ( k = i+1; k n; +k ) if (ak aj ) j = k; if ( j != i ) aj ai / select_sort基本操作:比较比较(数据元素)操作操作时间复杂度: O(n2)算法的性能分析与度量算法的空间复杂度 空间的复杂度 根据问题规模n，算法执行所需要的额外存储空间大小的量度 空间的复杂度S(n)记作S (n) = O( f (n

18、) )算法的空间复杂度 算法的存储量包括: 1输入数据所占空间 2程序本身所占空间 3辅助变量所占空间算法的空间复杂度 若输入数据所占空间只取决于问题本身，和算法无关，则只需要分析除输入和程序之外的辅助变量所占额外空间。 若所需额外空间相对于输入数据量来说是常数，则称此算法为原地工作。 若所需存储量依赖于特定的输入，则通常按最坏情况考虑。描述算法的语言 一个算法可以采用多种表述方式，比如，人类的自然语言可以用来表述算法，但在很多情况下，算法描述更多地采用一些形式化方法形式化方法。程序流程图程序流程图就是一种形式化的算法描述，还可能采用判定表、判定树及状态转移图判定表、判定树及状态转移图等多种方式。一种广泛使用的形式化算法描述方法，就是参照某种程序设计语言，设计出一种算法描述语言。算法描述语言和程序设计语言比较类似，但没有严格的语法规则，甚至可以在其中加入一些自然语言描述。有了用算法描述语言描述的算法，可以很容易地转换成实际可运行的程序。描述算法的语言 选择选择C+语言描述算法语言描述算法 本教材另一个特点是将面向对象的方法引入到数据结构领域。面向对象技术不仅是一种程序设计方法学，而且是一种认识方法学，数据结构讨论的正是数据的描述与处理，与面向对象的认知方法具有天然的联系。面向对象程序设计语言提供的封装、继承、多态和泛型