123抽象数据类型 抽象数据类型是与表示无关的数据类型,是一个数 据模型及定义在该模型上的一组运算。对一个抽象数据 类型进行定义时,必须给出它的名字及各运算的运算符 名,即函数名,并且规定这些函数的参数性质。一旦定 义了一个抽象数据类型及具体实现,程序设计中就可以 像使用基本数据类型那样,十分方便地使用抽象数据类 1.24抽象数据类型的描述和实现 抽象数据类型的描述包括给岀抽象数据类型的名称、 数据的集合、数据之间的关系和操作的集合等方面的描 述。抽象数据类型的设计者根据这些描述给岀操作的具 体实现,抽象数据类型的使用者依据这些描述使用抽象 数据类型
1.2.3抽象数据类型 抽象数据类型是与表示无关的数据类型，是一个数 据模型及定义在该模型上的一组运算。对一个抽象数据 类型进行定义时，必须给出它的名字及各运算的运算符 名，即函数名，并且规定这些函数的参数性质。一旦定 义了一个抽象数据类型及具体实现，程序设计中就可以 像使用基本数据类型那样，十分方便地使用抽象数据类 型。 1.2.4抽象数据类型的描述和实现 抽象数据类型的描述包括给出抽象数据类型的名称、 数据的集合、数据之间的关系和操作的集合等方面的描 述。抽象数据类型的设计者根据这些描述给出操作的具 体实现，抽象数据类型的使用者依据这些描述使用抽象 数据类型
抽象数据类型描述的一般形式如下 ADT抽象数据类型名称{ 数据对象 数据关系 操作集合 操作名1 操作名n }ADT抽象数据类型名称
抽象数据类型描述的一般形式如下： ADT 抽象数据类型名称 { 数据对象： …… 数据关系： …… 操作集合： 操作名1： …… …… 操作名n： }ADT抽象数据类型名称
13算法和算法分析 1.31算法 为了求解某问题,必须给出一系列的运算规则 这一系列的运算规则是有限的,表达了求解问题方 法和步骤,这就是一个算法。 个算法可以用自然语言描述,也可以用高级 程序设计语言描述,也可以用伪代码描述。本书采 用C语言对算法进行描述
1.3 算法和算法分析 1.3.1算法 为了求解某问题，必须给出一系列的运算规则， 这一系列的运算规则是有限的，表达了求解问题方 法和步骤，这就是一个算法。 一个算法可以用自然语言描述，也可以用高级 程序设计语言描述，也可以用伪代码描述。本书采 用C语言对算法进行描述
算法具有五个基本特征: ①有穷性,算法的执行必须在有限步内结束。 ②确定性,算法的每一个步骤必须是确定的无二义性 的 ③输入,算法可以有0个或多个输入 ④输出,算法一定有输出结果 ⑤可行性,算法中的运算都必须是可以实现的。 算法具有有穷性,程序不需要具备有穷性。一般 的程序都会在有限时间内终止,但有的程序却可以不 在有限时间内终止,如一个操作系统在正常情况下是 永远都不会终止的
算法具有五个基本特征： ①有穷性，算法的执行必须在有限步内结束。 ②确定性，算法的每一个步骤必须是确定的无二义性 的。 ③输入， 算法可以有0个或多个输入。 ④输出， 算法一定有输出结果 ⑤可行性，算法中的运算都必须是可以实现的。 算法具有有穷性，程序不需要具备有穷性。一般 的程序都会在有限时间内终止，但有的程序却可以不 在有限时间内终止，如一个操作系统在正常情况下是 永远都不会终止的
1.32算法的时间和空间复杂性 一个算法的优劣主要从算法的执行时间和所需 要占用的存储空间两个方面衡量,算法执行时间的度 量不是采用算法执行的绝对时间来计算的,因为 算法在不同的机器上执行所花的时间不一样,在不同 时刻也会由于计算机资源占用情况的不同,使得算法 在同一台计算机上执行的时间也不一样,所以对于算 法的时间复杂性,采用算法执行过程中其基本操作的 执行次数,称为计算量来度量。 算法中基本操作的执行次数一般是与问题规模 有关的,对于结点个数为n的数据处理问题,用T(n) 表示算法基本操作的执行次数
1.3.2算法的时间和空间复杂性 一个算法的优劣主要从算法的执行时间和所需 要占用的存储空间两个方面衡量，算法执行时间的度 量不是采用算法执行的绝对时间来计算的，因为一个 算法在不同的机器上执行所花的时间不一样，在不同 时刻也会由于计算机资源占用情况的不同，使得算法 在同一台计算机上执行的时间也不一样，所以对于算 法的时间复杂性，采用算法执行过程中其基本操作的 执行次数，称为计算量来度量。 算法中基本操作的执行次数一般是与问题规模 有关的，对于结点个数为n的数据处理问题，用T(n) 表示算法基本操作的执行次数