C1.3-1.5抽象数据类型.doc

1.3 抽象数据类型 抽象数据类型(Abstract Data Type，ADT)是指一个数学模型以及定义在此数学模型上的一组操作。抽象数据类型由元素、关系及操作3种要素来定义。抽象数据类型用三元组来表示： (D、R、P) 其中：D是数据对象；R是D上的关系集；P是对D的基本操作集。抽象数据类型名称定义的一般形式为： ADT 抽象数据类型名称 数据对象： 数据关系： 操作集合： 操作名1; 操作名n; ADT抽象数据类型名称例如：线性表这样的抽象数据类型，其数学模型是数据元素的集合，该集合内的元素有这样的关系：除第一和最后一个外，每个元素都有唯一的前趋和后继。可以有这样的一些操作：插入一个元素、删除一个元素。那么线性表的抽象数据类型就可以定义为ADT list 数据对象：任意数据元素的集合数据关系：除第一个和最后一个外，每个元素都有唯一的直接前驱和直接后继 基本操作： ListInsert(&L,i,e); /元素的插入(前插操作。在线性表L中第i个元素之前插入一个新的元素e，使得线性表L变为长度为ListLength(L)+1) ListDelete(&L,i,e); /元素的删除 （删除操作。若1iListLength(L)），则删除线性表L中的第i个元素，使得线性表变为长度减去1. . ADT list 通过以上定义可以看出，抽象数据类型只是数学的抽象，在ADT的定义中根本没有涉及如何实现操作的集合。对于每个ADT并不存在什么法则来说明必须要有哪些操作：这只是一个设计决策。还会在后续的章节中讨论不同数据结构的ADT。1.4 算法1.4.1 算法概述算法(Algorithm)是解题的步骤，是指令的有限序列。一个算法应该具有以下特征： (1) 有穷性。对于任何合法的输入值，一个算法必须保证执行有限步之后结束。 (2) 确定性。算法的每一步必须有确切的含义，无二义性，并且在任何条件下，算法只有唯一的一条执行路径，即对相同的输入只能得出相同的输出。 (3) 输入。一个算法有0个或多个输入，以刻画运算对象的初始情况，所谓0个输入是指算法本身设定了初始条件。 (4) 输出。一个算法有一个或多个输出，以反映对输入数据加工后的结果。没有输出的算法是毫无意义的。 (5) 可行性。算法原则上能够精确地运行，即算法中描述的操作都是可以通过已经实现的基本运算执行有限次来实现。对算法的学习包括下面5个方面的内容： (1) 设计算法。设计一个好的算法，通常要考虑正确性、可读性、健壮性、高效性这几个方面的要求。(2) 描述算法。描述算法的方法有多种形式，例如自然语言和算法语言，各自有适用的环境和特点。(3) 确认算法。算法确认的目的是使人们确信这一算法能够正确无误地工作，即该算法具有可计算性。(4) 分析算法。算法分析是对一个算法需要多少计算时间和存储空间作定量分析。 (5) 验证算法。用计算机语言描述的算法是否可计算、有效合理，须对程序进行测试，测试程序的工作由调试和对算法运行所需时间和空间进行分析。1.4.2 算法与数据结构之间的关系著名的计算机科学家沃思(Nikiklaus Wirth)提出一个公式： 数据结构 + 算法 = 程序这个公式说明了算法与数据结构的重要性，也说明了算法与数据结构之间存在着相辅相成的关系。解决一个问题可以选择不同的数据结构，也可以选择不同的算法。数据结构的选择决定着算法执行时所需要的时间与空间，影响着算法的效率。反之，算法的优劣又决定着某个数据结构是否适合解决这个问题。1.4.3 算法的度量1. 算法的时间复杂度算法的时间复杂度是指运行算法时所需要消耗的时间资源。其定义是：如果一个问题的规模是n，解决这一问题的某一算法所需要的时间为T(n)，它是n的某一函数。T(n)就称为算法的时间复杂度。当输入量n逐渐增大时，时间复杂度的极限情形称为算法的渐近时间复杂度。2. 算法的空间复杂度 算法的空间复杂度是指算法在计算机内执行时所需存储空间的度量。存储空间具体是指编写程序时，程序的存储空间、变量占用空间、系统堆栈的使用空间等。1.5 算 法 分 析1.5.2 所需分析的问题 在进行分析时，要分析的最重要的资源一般来说就是运行时间。有一些因素影响着程序的运行时间，但是诸如所使用的编译器和计算机的性能这些因素不在考虑范围之内，只考虑所使用的算法以及对该算法的输入。 大多数情况下，把输入的大小作为主要考虑的因素。定义两个函数Tavg(N)和Tworst(N)，分别是输入量为N时算法所花费的平均运行时间和最坏情况下的运行时间。显然，Tavg(N)Tworst(N)。一般说来，如果没有明确指出，计算的时间复杂度为最坏情况下的运行时间。其原因之一是它对所有的输入提供了一个界限，包括特别坏的情况下的输入，而平均时间复杂度不具有这个界限；还有一个原因是平均时间复杂度的计算较为复杂。1.5.3 运行时间的计算计算运行时间要遵循下面的法则。 1. 法则1赋值语句的运行时间 每一条赋值语句的运行时间为1。 2. 法则2for循环的运行时间 一次for循环的运行时间至多是该for循环内语句(包括测试)的运行时间乘以迭代的次数。 3. 法则3嵌套for循环的运行时间 从里面到外面分析这些循环。每一层循环的运行时间等于该层的for循环语句的运行时间乘以该层循环内所有的for循环的运行时间。 4. 法则4顺序语句的运行时间 将各个语句的运行时间求和即可，根据1.5.1小节中的定理1中的(1)可知，总的运行时间为其中的最大值。5. 法则5IF/ELSE语句的运行时间 对于以下程序片段 if(condition) S1 else S2 它的运行时间不超过判断再加上S1与S2中运行时间的最长者。显然这种估计在有些情况下会过高，但是绝不会估计过低。6. 法则6递归函数的复杂度分析 递归函数的复杂度分析比较困难。 1.5.4 检验你的分析算法分析一旦结束，就需要对所分析得到的结果进行检查。一种可行的方法是编写程序并比较实际观察到的运行时间，与通过分析得到的描述时间