数据结构第1章绪论资料

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

2、构成数据的具有相同性质的基本单元数据对象（data object）是性质相同的数据元素的集合。 是数据的一个子集。 是一种运行时的概念。共四十五页基本概念数据结构(sh j ji u)数据结构（data structure）是相互之间存在一种或多种特定关系的数据元素(yun s)的集合数据结构的二元组表示：Data_Structure = (D, S)其中：D是数据元素的有限集，S是D上关系的有限集共四十五页基本概念数据结构(sh j ji u)例如一维数组是一种数据结构 Array = 数据元素的集合是D = a1, a2, , an数据元素关系(gun x)的集合是S = RR=| 1in

3、 其中为序偶共四十五页基本概念数据结构(sh j ji u)按照软件系统开发(kif)过程中的数据层次模型，数据之间存在两种结构关系数据的逻辑结构（位于逻辑层），反映数据元素之间的逻辑关系，由抽象数据类型来表达数据的物理结构（位于实现层），也称存储结构，考虑的是数据在计算机中是如何存储和组织的共四十五页基本概念数据结构(sh j ji u)数据元素之间的逻辑关系通常可分为4类基本的逻辑结构1. 集合结构中的数据元素之中同属一个集合2. 线性结构结构中的元素之间存在一个对一个的关系(gun x)3. 树型结构结构中的数据元素之间存在一个对多个的关系4. 图状结构或网状结构结构中的数据元素之间存在

4、多个对多个的关系共四十五页逻辑(lu j)结构例学生选课问题该问题可以用三张数据(shj)表来表示，每张表中每条记录为数据(shj)元素如表中数据元素是无序的，则数据表构成集合结构如表中数据元素是有序的，则数据表构成线性结构学生表课程表选课表学号姓名课程号课程名称学号课程号成绩S0001张三C0001数据结构S0001C000185S0002李四C0002操作系统S0001C000376S0005王五C0003编译原理S0002C000190C0004数据库原理S0002C000483S0003 C000292共四十五页逻辑(lu j)结构例三维实体造型问题左图的机械零件可以分解成三个基本的实

5、体模型通过(tnggu)布尔运算+和-操作得到右图构成了一个树型的数据结构，每一个节点为一个基本实体模型或通过布尔运算得到的复合实体模型共四十五页逻辑(lu j)结构例地图表示问题左图的地图经抽象可以得到(d do)右图的结构右图构成了图状的数据结构共四十五页数据的物理(wl)结构数据的存储结构 逻辑结构在存储器中的映象“数据元素”如何(rh)映象 ？“关系”如何映象 ？共四十五页数据(shj)的物理结构数据元素在计算机内部实际存储时，根据各数据元素之间相对的存储位置及相互之间的关系，存在着两种存储结构顺序存储结构在存储器中，数据元素是依次存放的，数据元素在物理存储器上的位置关系体现了它们在逻

6、辑(lu j)上的顺序关系链式存储结构在存储器中，数据元素是分散存放的，在一个数据元素中，必须有一个或若干专门的数据项来指示其他相关联的数据元素在存储器中的位置共四十五页数据(shj)的物理结构分别用顺序结构和链式结构来存储(cn ch)数列“10,20,30,40”数列的顺序存储结构数列的链式存储结构共四十五页数据的物理(wl)结构链式映象需要用一个附加信息指示下一元素(yun s)的存储位置共四十五页基本概念数据类型数据类型在用高级程序语言编写的程序中，必须对程序中出现的每个变量、常量(chngling)或表达式，明确说明它们所属的数据类型。共四十五页基本概念数据类型（C+为例）基本数据类

7、型字符（char）、整数（int）、浮点数（float/double）、指针（*）、引用（&）复杂数据类型数组（）、结构（struct）、枚举(mi j)（enum）、类（class）、联合（union）不同类型的变量，其所能取的值的范围不同， 所能进行的操作不同。共四十五页基本概念数据类型数据类型 是一个(y ) 值的集合和定义在此集合上 的一组操作的总称。共四十五页基本概念抽象数据类型在软件系统开发的全过程中，对客观现实中存在的事物，存在三个观察层面应用层是用户通过物理观察得到的客观事物的视图，是可以用自然语言描述的，或用图形、图像、音频、视频等物理量表达的在概念层次上的数据。逻辑(lu

8、j)层（抽象层）是从应用层次抽象出来的数据视图，利用抽象数据类型进行形式化描述。实现层明确地表示出了数据的组织与存储结构，并用某种具体的程序设计语言进行代码实现。共四十五页基本概念抽象数据类型抽象数据类型（ADT，Abstract Data Type）是与具体计算机内部(nib)表示和实现方式无关的数据类型是由一个逻辑上的数学模型以及定义在该模型上的一组操作构成可以用三元组定义 (D, S, P)D是数据对象S是D上的关系集P是对D的基本操作集抽象数据类型和数据类型实际上是一个概念共四十五页基本概念抽象数据类型ADT 有两个重要特征:一、数据抽象用ADT描述程序处理的实体(sht)时，强调的是

9、其本质的特征、其所能完成的功能以及它和外部用户的接口（即外界使用它的方法）。二、数据封装将实体的外部特性和其内部实现细节分离，并且对外部用户隐藏其内部实现细节。共四十五页抽象数据类型例 ADT Set/ 集合的抽象数据类型 数据对象：D ai | aiElemType, i= 1, 2, ., n, n 0 数据关系：R = aiaj | ai,ajD 基本操作：Init() 操作(cozu)结果：构造一个空的集合。Destroy()操作结果：销毁集合。IsEmpty() 操作结果：判断集合是否为空，如为空，则返回TRUE；否则返回FALSE。 Insert(e)操作结果：在集合中加入一个元素

10、。如元素已存在，返回FALSE；否则返回TRUE。 Remove(e) 操作结果：在集合中移除一个元素。如元素存在，则返回TRUE；否则返回FALSE。 IsMember(e) 操作结果：判断在集合中是否存在元素。FindFirst(&e)操作结果：找到集合中的第一个元素。如成功，返回TRUE；如果集合为空，返回FALSE共四十五页抽象数据类型例 FindFirst(&e)操作结果：找到集合中的第一个元素。如成功，返回TRUE；如果集合为空，返回FALSEFindNext(&e) 初始条件：已经执行过FindFirst或FindNext操作 操作结果：在上一次查找的前提下，找到集合中的下一个(

11、y )元素；如成功，返回TRUE；如上次查找已到最后一个元素，返回FALSE。 Union(s)操作结果：与另一个集合s做并运算，返回并集。Intersection(s)操作结果：与另一个集合s做交运算，返回交集。Difference(s)操作结果：与另一个集合s做差运算，返回差集。共四十五页二、算法(sun f)与算法(sun f)分析程序为计算机处理问题(wnt)编制一组指令集 算法处理问题的策略数据结构问题的数学模型Algorithm + Data Structures = Programs算法 + 数据结构 = 程序 - Niklaus Wirth共四十五页算法(sun f)算法（al

12、gorithm）解决某一特定问题的具体步骤的描述(mio sh)，是指令的有限序列算法的五个重要特征有穷性确定性可行性输入输出共四十五页算法(sun f)1有穷性 对于任意一组合法输入值，在执行有穷步骤之后一定能结束，即：算法中的每个步骤都能在有限时间内完成。2确定性 对于每种情况下所应执行的操作，在算法中都有确切的规定，使算法的执行者或阅读者都能明确(mngqu)其含义及如何执行。并且在任何条件下，算法都只有一条执行路径。共四十五页算法(sun f)3可行性 算法中的所有操作都必须足够基本，都可以通过已经实现的基本操作运算有限次实现之。4有输入 作为算法加工对象的量值，通常体现(txin)为

13、算法中的一组变量。有些输入量需要在算法执行过程中输入，而有的算法表面上可以没有输入，实际上已被嵌入算法之中。5有输出 它是一组与“输入”有确定关系的量值，是算法进行信息加工后得到的结果，这种确定关系即为算法的功能。共四十五页 算法(sun f)算法设计的原则(yunz)设计算法时，通常应考虑达到以下目标：1正确性2. 可读性3健壮性4高效率与低存储量需求共四十五页 算法的性能分析(fnx)与度量算法性能的度量方法事后测试可采用一些程序运行性能跟踪(gnzng)与测量工具（如Profiler）预先评做不考虑算法的实现语言、编译器、运行的硬件平台，只考虑在一定问题规模下算法运行的时间复杂度和空间复

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

15、）算法的执行时间 =原操作(i)的执行次数原操作(i)的执行时间共四十五页 算法(sun f)的性能分析与度量时间的复杂度从算法中选取对于(duy)所处理问题来说是关键步骤的程序语句作为基本操作，该基本操作重复执行的次数作为算法的时间量度。基本操作重复执行的次数一般为问题规模n的某个函数f(n)，因此时间的复杂度T(n)记作T (n) = O( f (n) )上式表示随着问题规模n的增长，算法执行时间T(n)和f(n)同比增长共四十五页时间(shjin)复杂度例 语句+x为三个算法的基本操作，问题规模(gum)为n三段程序中基本操作的执行次数分别为1、n和n2故三段程序的时间复杂度分别为O(1

16、)、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; 共四十五页时间(shjin)复杂度例 语句+x为算法的基本操作算法中基本操作的执行次数是0 + 1 + . + (n 2) = (n 1) (n 2) / 2上式中随着(su zhe)n的增长，增长率最快的项是n2 ，故该算法的时间复杂度分别为O (n2)/ 例4for (i = 2; i =

17、n; +i) for (j = 2; j = i - 1; +j) +x;/基本操作 s += x; 共四十五页时间(shjin)复杂度例 例: 两个矩阵相乘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基本操作: 乘法操作(cozu)时间复杂度: O(n3)共四十五页时间(shjin)复杂度例 例: 选择排序(pi x)void

18、 select_sort(int& a, int n) / 将 a 中整数序列重新排列成自小至大有序的整数序列。for ( i = 0; i n-1; +i ) j = i ;/ 选择第 i 个最小元素 for ( k = i+1; k n; +k ) if (ak aj ) j = k; if ( j != i ) aj ai / select_sort基本操作:比较(数据元素)操作时间复杂度: O(n2)共四十五页算法的性能分析(fnx)与度量共四十五页算法(sun f)的空间复杂度算法(sun f)的存储量包括:1输入数据所占空间2程序本身所占空间3辅助变量所占空间共四十五页算法(sun

19、 f)的空间复杂度 若输入数据所占空间只取决于问题本身，和算法无关，则只需要分析除输入和程序之外的辅助变量所占额外空间。 若所需额外空间相对(xingdu)于输入数据量来说是常数，则称此算法为原地工作。 若所需存储量依赖于特定的输入，则通常按最坏情况考虑。共四十五页算法(sun f)的空间复杂度空间的复杂度根据(gnj)问题规模n，算法执行所需要的额外存储空间大小的量度空间的复杂度S(n)记作S (n) = O( f (n) )共四十五页描述(mio sh)算法的语言。一个算法可以采用多种表述方式，比如，人类的自然语言可以用来表述算法，但在很多情况下，算法描述更多地采用一些形式化方法。程序流程

20、图就是一种形式化的算法描述，还可能采用判定表、判定树及状态转移图等多种方式。一种广泛使用的形式化算法描述方法，就是参照某种程序设计语言，设计出一种算法描述语言。算法描述语言和程序设计语言比较类似，但没有严格的语法规则，甚至可以在其中加入一些自然语言描述。有了用算法描述语言描述的算法，可以很容易地转换成实际(shj)可运行的程序。共四十五页描述算法(sun f)的语言选择C+语言描述算法 本教材另一个特点是将面向对象的方法引入到数据结构领域。面向对象技术不仅是一种(y zhn)程序设计方法学，而且是一种(y zhn)认识方法学，数据结构讨论的正是数据的描述与处理，与面向对象的认知方法具有天然的联系。面