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); //元素的删除 （删除操作。若1≤i≤ListLength(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 所需分析的问题 在进行分析时，要分析的最重要的资源一般来说就是运行时间。有一些因素影响着程序的运行时间，但是诸如所使用的编译器和计