数据结构与算法----教学课件.ppt

第 * 页 抽象数据类型  ⑴由用户定义，用以表示实际应 用问题的数据模型。 ⑵由基本的数据类型组成, 并包 括一组相关的服务（或称操作）。 第 * 页 抽象数据类型的描述方法: ⑴抽象数据类型从形式上可用（D，R，O）三元组表示。其中：D是数据对象，R是D上的关系集，O是对D的基本操作集 。 一般采用如下格式描述 ADT 抽象数据类型名 { 数据对象：〈数据对象的定义〉 数据关系：〈数据关系的定义〉 基本操作：〈基本操作的定义〉 } ADT 抽象数据类型名 第 * 页 ADT基本操作的定义格式 基本操作名（参数表） 初始条件：〈初始条件描述〉 操作结果：〈操作结果描述〉 ⑴参数：赋值参数只为操作提供输入值;引用参数以 打头，除可提供输入值外，还将返回操作结果。 ⑵初始条件：描述操作执行之前数据结构和参数应 满足的条件，若不满足，则操作失败，并返回相 应出错信息。若初始条件为空,则省略之。 ⑶操作结果：说明操作正常完成之后，数据结构的 变化状况和应返回的结果。 第 * 页 例如，抽象数据类型“复数”的定义： 数据对象： D＝{e1,e2｜e1,e2∈RealSet } 数据关系： R1＝{e1,e2 | e1是复数的实数部分， e2 是复数的虚数部分 } ADT Complex { 第 * 页 基本操作： AssignComplex( Z, v1, v2 ) 操作结果：构造一个复数 Z，其实部和虚部分别被赋以参数v1和v2的值。 DestroyComplex( Z) 操作结果：复数Z被销毁。 GetReal( Z, realPart ) 初始条件：复数已存在。 操作结果：用realPart返回复数Z的实部值。 第 * 页 GetImag( Z, ImagPart ) 初始条件：复数已存在。 操作结果：用ImagPart返回复数Z的虚部值。 Add( z1,z2, sum ) 初始条件：z1, z2是复数。 操作结果：用sum返回两个复数z1, z2的和值。 } ADT Complex 第 * 页 抽象数据类型的实现 抽象数据类型描述的是抽象的数据模型及其操作，需要通过固有数据类型(高级编程语言中已实现的数据类型)来实现。 引入抽象数据类型的意义 通常研究一个数据结构的实现问题可以从研究其抽象数据类型着手，例如通过对抽象数据类型的加工来用C++类实现该数据结构：类的数据成员对应于ADT所描述的数据结构，类的方法对应于ADT所描述的操作。 第 * 页 二、算法 第 * 页 关于算法 算法是为了解决某类问题而设计的一个有限长的操作序列。 算法特性 有穷性、确定性、可行性、 有输入、有输出 第 * 页 有穷性：对于任意一组合法输入值，在执行有穷步骤之后一定能结束，即：算法中的每个步骤都能在有限时间内完成。 确定性：对于每种情况下所应执行的操作，在算法中都有确切的规定，使算法的执行者或阅读者都能明确其含义及如何执行；并且在任何条件下，算法都只有一条执行路径。 可行性：算法中的所有操作都必须足够基本，都可以通过已经实现的基本操作运算有限次实现之。 第 * 页 有输入： ①作为算法加工对象的量值，通常体现为算法中 的一组变量。 ②有些输入量需要在算法执行过程中输入，而有 的算法表面上可以没有输入，实际上输入已被 嵌入算法之中。 有输出： ①它是一组与“输入”有确定关系的量值，是算 法进行信息加工后得到的结果。 ②这种确定关系即为算法的功能。 第 * 页 ⑴用自然语言描述算法：用我们日常生活中的自然语言也可以描述算法。 算法描述方法 ⑵用流程图描述算法：一个算法可以用流程图的方式来描述，输入输出、判断、处理分别用不同的框图表示，用箭头表示流程的流向。这是一种描述算法的较好方法，目前在一些高级语言程序设计中仍然采用。 ⑷用其它方式描述算法：我们还可以用数学语言或约定的符号语言（如伪代码）来描述算法。 ⑶用C++描述算法：在本课程中，我们将采用C++来描述算法，所有算法的描述都用C++中的函数形式。 第 * 页 算法和程序的关系 ⑴算法≠程序！ ①算法着重体现思路和方法，程序着重 体现计算机的实现。 ②程序不一定满足有穷性（例如死循环 情形）；另外，程序中的指令必须是机 器可执行的，算法中的指令无此限制。 ③算法用计算机语言来书写时才是程序。 第 * 页 算法设计原则 正确性 可读性 健壮性 高效率 低需求 算法评价标准时间特性：时间复杂度T(n)空间特性：空间复杂度S(n) 算法设计原则与评价标准 第 * 页 ⑴ 一个特定算法的