[计算机软件及应用]数据结构第1章 绪论ppt课件

1、11.1 什么是数据构造什么是数据构造1.2 根本概念和术语根本概念和术语1.4 算法和算法分析算法和算法分析1.3 抽象数据类型的表示与实现抽象数据类型的表示与实现121.1 什么是数据构造用计算机解决详细问题的步骤用计算机解决详细问题的步骤 ：1. 抽象出一个抽象出一个数学模型数学模型；2. 设计一个解此数学模型的设计一个解此数学模型的算法算法；3. 编程、测试、调整。编程、测试、调整。寻求数学模型：寻求数学模型：分析分析问题问题、提取、提取操作操作的的对象对象及其及其对象之间的对象之间的关系关系并进展描绘。并进展描绘。非数值计算非数值计算操作对象操作对象关系和操作关系和操作231.2 根

2、本概念数据数据：指所有能被输入到计算机中，且能被计算指所有能被输入到计算机中，且能被计算机处理的机处理的。是计算机操作的是计算机操作的。数据元素数据元素: :是数据构造中讨论的是数据构造中讨论的单位。单位。在计算机程序中作为一个在计算机程序中作为一个“进展考进展考虑。虑。一一. . 数据和数据构造数据和数据构造34数据项：数据项：是数据构造中讨论的是数据构造中讨论的的的单位。单位。数据对象数据对象: :是是的数据元素的集合，如的数据元素的集合，如:一个班级一个班级的成绩表可以看作一个数据对象。它是的成绩表可以看作一个数据对象。它是数据数据的一个的一个子集子集。数据构造：数据构造：假设在特性一样

3、的数据元素假设在特性一样的数据元素集合集合中的中的数据元素数据元素之间之间存在一种或多种存在一种或多种特定的关系特定的关系，那么称该数据元素的，那么称该数据元素的集合为集合为“数据构造数据构造“。数据构造数据构造是带是带“构造构造的的数据元素数据元素的集合。的集合。 45数据构造是一个二元组是一个二元组 Data_Structures = D, S其中其中: D 是是数据元素的有限集数据元素的有限集， S 是是 D上关系的有限集。上关系的有限集。56二二. . 数据类型数据类型在用高级程序语言编写的程序中，必须对程序中出现在用高级程序语言编写的程序中，必须对程序中出现的每个的每个变量、常量或表

4、达式变量、常量或表达式，明确说明它们，明确说明它们所属的数所属的数据类型据类型。 【例例】C/C+语言中提供的根本数据类型有语言中提供的根本数据类型有:整整 型型 int浮浮 点点 型型 float字符型字符型 char逻辑型逻辑型 bool C+语言语言双精度型双精度型 double1.2 根本概念6778三三. . 抽象数据类型抽象数据类型 Abstract Data Type , ADT抽象数据类型：抽象数据类型：是指一个是指一个数学模型数学模型以及定义在此数以及定义在此数学模型上的学模型上的一组操作一组操作。即：即：ADT的定义由一个的定义由一个值域值域和定义在该值域上的一和定义在该值

5、域上的一组组操作操作组成。组成。ADT的定义仅取决于的定义仅取决于数据模型数据模型的的逻辑特征逻辑特征。ADT和和数据类型数据类型本质上是一个概念。本质上是一个概念。与其在与其在计算机内部计算机内部的表示和实现无关。的表示和实现无关。“抽象抽象的意义在于数据类型的的意义在于数据类型的数学抽象特性数学抽象特性。不管内部构造如何变化，都不管内部构造如何变化，都不会影响外部使用不会影响外部使用。89例：线性表这样的抽象数据类型。例：线性表这样的抽象数据类型。数学模型数学模型：数据元素的集合；：数据元素的集合；该集合内的元素的该集合内的元素的关系关系：除第一个和最后：除第一个和最后一个外，每个元素有唯

6、一的前趋和唯一的一个外，每个元素有唯一的前趋和唯一的后继；后继；操作操作：插入一个元素、删除一个元素等。：插入一个元素、删除一个元素等。 910抽象数据类型不仅仅局限于抽象数据类型不仅仅局限于固有数据类型固有数据类型，也包括，也包括用用户自定义的户自定义的数据类型。数据类型。ADT 按照其值的不同特性，分为按照其值的不同特性，分为4种类型：种类型：原原 子子 类类 型型：其值其值不可分解的类型；如：不可分解的类型；如：int固定聚合类型固定聚合类型：其值由确定数目的成分按某种构造组成；如：其值由确定数目的成分按某种构造组成；如：复数；复数；可变聚合类型可变聚合类型：其值由不固定数目的成分按某种

7、构造组成；其值由不固定数目的成分按某种构造组成；如：学生根本情况，有序整数序列；如：学生根本情况，有序整数序列；多形数据类型多形数据类型：其值的成分不确定的数据类型；元素之间其值的成分不确定的数据类型；元素之间的关系一样，根本操作也一样的关系一样，根本操作也一样 10112. 数据封装：数据封装：将实体的将实体的外部特性外部特性和其内部和其内部实现细节实现细节别离，并且对外部用户隐藏其内部实现细节。别离，并且对外部用户隐藏其内部实现细节。1. 数据抽象：数据抽象：用用ADT描绘程序处理的实体时，强调描绘程序处理的实体时，强调的是其的是其本质的特征本质的特征、其所能完成的、其所能完成的功能功能以

8、及它和外以及它和外部用户的部用户的接口接口即外界使用它的方法。即外界使用它的方法。抽象数据类型抽象数据类型的定义由一个的定义由一个值域值域和定义在该值域上和定义在该值域上的一组的一组操作操作组成。组成。1112抽象数据类型可用三元组表示抽象数据类型可用三元组表示:ADT =D，S，P其中：其中：D 是是数据对象数据对象； S 是是 D 上的上的关系关系集；集； P 是是对对 D 的的根本操作根本操作集集。 1213数据构造是一个二元组是一个二元组 Data_Structures = D, S其中其中: D 是是数据元素的有限集数据元素的有限集， S 是是 D上关系的有限集。上关系的有限集。13

9、14ADT 抽象数据类型名抽象数据类型名 数据对象：数据对象：数据对象的定义数据对象的定义-D 数据关系：数据关系：数据关系的定义数据关系的定义-S 根本操作：根本操作：根本操作的定义根本操作的定义-P ADT抽象数据类型名抽象数据类型名根本操作根本操作的定义格式为的定义格式为:根本操作名根本操作名参数表参数表 初始条件初始条件：初始条件描绘初始条件描绘 操作结果操作结果：操作结果描绘操作结果描绘 其中，数据对象和数据关系的其中，数据对象和数据关系的定义用定义用伪码描绘伪码描绘14151.1.参数表：参数表：赋值参数赋值参数: : 只为操作提供只为操作提供输入值输入值。引用参数引用参数: :

10、以以& &打头，除可提供打头，除可提供输入值输入值外，还将外，还将返回操作结果返回操作结果。2. 2. 初始条件初始条件: : 描绘了操作描绘了操作执行之前执行之前数据构造和参数数据构造和参数应满足的条件应满足的条件，假设不满足，那么操作失败，并返回，假设不满足，那么操作失败，并返回相应出错信息。假设初始条件为空，那么省略之。相应出错信息。假设初始条件为空，那么省略之。3. 3. 操作结果操作结果: : 说明了操作说明了操作正常完成之后正常完成之后，数据构造的，数据构造的变化状况变化状况和和应返回的结果应返回的结果。1516【例例】抽象数据类型抽象数据类型 复数复数 的定义：的

11、定义：数据对象：数据对象：De1, e2e1,e2RealSet 数据关系：数据关系：R1 | e1是复数的实数部分，是复数的实数部分， | e2 是复数的虚数部分是复数的虚数部分 ADT Complex 1617根本操作：根本操作：AssignComplex &Z, v1, v2 操作结果：操作结果：构造复数构造复数 Z,其实部和虚部分别被其实部和虚部分别被赋以参数赋以参数 v1 和和 v2 的值。的值。DestroyComplex &Z操作结果：复数操作结果：复数Z被被销毁销毁。 GetReal Z, &realPart 初始条件：复数已存在。初始条件：复数已存在。

12、操作结果：用操作结果：用realPart返回复数返回复数Z的实部值的实部值。1718GetImag Z, &ImagPart 初始条件：复数已存在。初始条件：复数已存在。操作结果：用操作结果：用ImagPart返回复数返回复数Z的虚部值的虚部值。Add z1,z2, &sum 初始条件：初始条件：z1, z2是复数。是复数。操作结果：用操作结果：用sum返回两个复数返回两个复数z1, z2 的的和值和值。 ADT Complex假设假设:z1和和z2是上述定义的复数是上述定义的复数那么那么 Addz1, z2, z3 操作的结果即为用户需要的操作的结果即为用户需要的结果结果z3

13、 = z2 + z11819抽象数据类型抽象数据类型需要通过需要通过固有数据类型固有数据类型高级编程语高级编程语言中已实现的数据类型言中已实现的数据类型来实现。来实现。【例例】利用利用C+语言实现的语言实现的复数复数类型如下描绘：类型如下描绘：1920typedef struct float realpart； float imagpart； complex；/ -存储构造的定义存储构造的定义/ -根本操作的函数原型说明根本操作的函数原型说明void Assign complex &Z, float realval, float imagval ；/ 构造复数构造复数 Z,其实部和虚部

14、分别被赋以参数其实部和虚部分别被赋以参数/ realval 和和 imagval 的值的值2021float GetReal cpmplex Z ； / 返回复数返回复数 Z 的实部值的实部值float Getimag cpmplex Z ； / 返回复数返回复数 Z 的虚部值的虚部值void add complex z1, complex z2, complex &sum ； / 以以 sum 返回两个复数返回两个复数 z1, z2 的和的和2122/ -根本操作的实现根本操作的实现void add complex z1, complex z2, complex &sum /

15、 以以 sum 返回两个复数返回两个复数 z1, z2 的和的和 sum.realpart = z1.realpart + z2.realpart; sum.imagpart = z1.imagpart + z2.imagpart; 其它省略其它省略 22231.3 算法和算法的衡量一一. 算法算法算法算法: :算法是对算法是对特定问题特定问题求解步骤求解步骤的一种描绘的一种描绘, , 是指是指令的令的有限序列有限序列，其中每一条指令表示一个或多个操作。，其中每一条指令表示一个或多个操作。一个算法必须满足以下五个重要一个算法必须满足以下五个重要特性特性：1有穷性有穷性 2确定性确定性 3可行性

16、可行性4有输入有输入 5有输出有输出23241 1有穷性有穷性: : 对于任意一组合法输入值，在执行对于任意一组合法输入值，在执行有穷有穷步骤步骤之后一定能完毕，且每一步骤都能在之后一定能完毕，且每一步骤都能在有限时间有限时间内完成。内完成。2 2确定性确定性: : 对于对于每种情况每种情况下所应执行的操作，在算下所应执行的操作，在算法中都有法中都有确切确切的规定，使算法的执行者或阅读者都的规定，使算法的执行者或阅读者都能明确其含义及如何执行。并且在任何条件下，算能明确其含义及如何执行。并且在任何条件下，算法都只有一条执行途径。法都只有一条执行途径。3 3可行性可行性: : 算法中描绘的操作都

17、是可以通过算法中描绘的操作都是可以通过已经实已经实现现的的根本运算根本运算执行有限次来实现。执行有限次来实现。24254 4有输入：有输入：零个或多个的输入。零个或多个的输入。作为算法加工对象作为算法加工对象的量值，通常表达为算法中的一组变量。有些输入的量值，通常表达为算法中的一组变量。有些输入量需要在算法执行过程中输入，而有的算法外表上量需要在算法执行过程中输入，而有的算法外表上可以没有输入，实际上已被嵌入算法之中。可以没有输入，实际上已被嵌入算法之中。5 5有输出：有输出：一个或多个的输出。一个或多个的输出。它是一组与它是一组与“输输入入有确定关系的量值，是算法进展信息加工后得有确定关系的

18、量值，是算法进展信息加工后得到的结果，这种确定关系即为算法的功能。到的结果，这种确定关系即为算法的功能。2526有穷性？有穷性？不是一个算法！不是一个算法！ 2627二二. 算法设计的原那么算法设计的原那么设计算法时，通常应考虑到达以下目的：设计算法时，通常应考虑到达以下目的：1正确性正确性2. 可读性可读性3强健性强健性4高效率与低存储量需求高效率与低存储量需求27281 1正确性正确性算法应当满足以特定的算法应当满足以特定的“规格说明规格说明方式给出的方式给出的需求需求。对算法是否对算法是否“正确正确的理解可以有以下四个层次：的理解可以有以下四个层次：a程序中不含程序中不含语法错误语法错误

19、；b程序对于程序对于几组输入数据几组输入数据可以得出满足要求的可以得出满足要求的结果；结果； c程序对于程序对于精心选择的、典型、苛刻且带有刁难精心选择的、典型、苛刻且带有刁难性的性的几组输入数据可以得出满足要求的结果；几组输入数据可以得出满足要求的结果； d程序对于程序对于一切合法的输入数据一切合法的输入数据都能得出满足要都能得出满足要求的结果；求的结果；通常以第通常以第 c 层意义的正确性作为衡量标准。层意义的正确性作为衡量标准。28292. 2. 可读性可读性算法主要是为了人的阅读与交流，其次才是为计算算法主要是为了人的阅读与交流，其次才是为计算机执行，因此算法应该机执行，因此算法应该易

20、于人的理解易于人的理解；另一方面，难读的程序易于另一方面，难读的程序易于隐藏较多错误隐藏较多错误而难以调而难以调试。试。3 3强健性强健性当输入的当输入的数据非法数据非法时，算法应当恰当地作出反映时，算法应当恰当地作出反映或进展相应处理，而不是产生或进展相应处理，而不是产生莫名奇妙的输出结果莫名奇妙的输出结果处理出错的方法不应是中断程序的执行，而应是处理出错的方法不应是中断程序的执行，而应是返回一个返回一个表示错误或错误性质的值表示错误或错误性质的值，以便进展处理，以便进展处理29304 4高效率与低存储量需求高效率与低存储量需求通常，效率指的是算法通常，效率指的是算法执行时间执行时间；存储量

21、指的是算；存储量指的是算法执行过程中所需的法执行过程中所需的最大存储空间最大存储空间，两者都与问题，两者都与问题的规模有关。的规模有关。3031算法与程序的区别算法与程序的区别算法算法是解决问题的一种方法或一个过程，考虑是解决问题的一种方法或一个过程，考虑如何将输入转换成输出，一个问题可以有如何将输入转换成输出，一个问题可以有多个多个算法。算法。程序程序是用某种程序设计语言对是用某种程序设计语言对算法的详细实现。算法的详细实现。主要区别：主要区别：有穷性、正确性和描绘方法有穷性、正确性和描绘方法程序可以是程序可以是无穷无穷的，例如的，例如OS，算法是，算法是有穷有穷的；的；程序可以是程序可以是

22、错误错误的，而算法必须是的，而算法必须是正确正确的；的；程序是用程序是用程序设计语言描绘程序设计语言描绘的，在机器上可以的，在机器上可以执行，算法还可以用执行，算法还可以用自然语言、框图、高级程自然语言、框图、高级程序语言序语言等方式描绘。等方式描绘。3132三三. 算法效率的衡量方法和准那么算法效率的衡量方法和准那么 事后统计事后统计缺点：缺点：1必须执行程序必须执行程序 2其它因素掩盖算法本质其它因素掩盖算法本质3233和算法执行时间相关的和算法执行时间相关的因素因素： 算法选用的策略算法选用的策略 问题的规模问题的规模 编写程序的语言编写程序的语言 编译程序产生的机器代码的质量编译程序产

23、生的机器代码的质量 计算机执行指令的速度计算机执行指令的速度事前分析事前分析3334343535363637算法算法 = 控制构造控制构造 + 原操作原操作固有数据类型的操作固有数据类型的操作算法的执行时间算法的执行时间 = （原操作（原操作(i)的的执行次数执行次数原操作原操作(i)的的执行时间执行时间）算法的执行时间算法的执行时间 与与 原操作执行次数原操作执行次数之和之和 成正比成正比 通常，从算法中选取通常，从算法中选取一种一种对于所研究的问题来说对于所研究的问题来说是是 根本操作根本操作 的原操作，以该的原操作，以该根本操作根本操作 在算法中重在算法中重复执行的次数复执行的次数 作为

24、算法运行时间的作为算法运行时间的衡量准那么衡量准那么。3738例:求以下程序段各语句的频度频度。 1 1forfori=1; i=n;i+i=1; i=n;i+ n+1 n+1 x+; n x+; n2 2 forforj=1;j=n;j+j=1;j=n;j+ n n+1+1 for fork=1;k=n;k+k=1;k=n;k+ n n* *n n+1+1 x+; n x+; n* *n n 38391i=1; k=0;while i=n-1 k+=10*i; i+;语句频度语句频度Tni=1; k=0;do k+=10*i; i+; while i=n-12语句频度语句频度Tn=n-1=n

25、-139403k=0;fori=1;i=n;i+ forj=i;j=n;j+ k+;i=1时；时；j循环循环n次次i=2时；时；j循环循环n-1次次i=n时；时；j循环循环1次次语句频度语句频度Tn =n+n-1+1=n-1+1*n+1/24041【例例】两个两个NN矩阵相乘矩阵相乘void multint a, int b, int& c / 以二维数组存储矩阵元素，以二维数组存储矩阵元素，c 为为 a 和和 b 的乘积的乘积 for i=1; i=n; +i / n+1 for j=1; j=n; +j /n*n+1 ci,j = 0; /n*n for k=1; k1 & change; - -i /n-1次次change = FALSE; / change 为元素进展交换标志为元素进展交换标志 for j=0; j aj+1 aj aj+1; change = TRUE