数据结构课件CH1绪论li幻灯片.PPT

四、算法的存储空间需求 算法的空间复杂度定义为: 表示随着问题规模 n 的增大， 算法运行所需存储量的增长率 与 f(n) 的增长率相同。 S(n) = O(f(n)) 算法的存储量包括: 1．输入数据所占空间 2．程序本身所占空间 3．辅助变量所占空间 若输入数据所占空间只取决于问题 本身，和算法无关，则只需要分析除 输入和程序之外的辅助变量所占额外 空间。 若所需额外空间相对于输入数据量 来说是常数，则称此算法为原地工作。 若所需存储量依赖于特定的输入， 则通常按最坏情况考虑。 1.1 什么是数据结构 1.2 基本概念 1.3 算法和算法的度量 第一章内容到此结束… 作 业 作业一 1，如图1所示逻辑结构图，试给出其数据结构的表示 2，计算下列程序段的时间复杂度 （1）int s=0; for (i=1;in-1;i++) for(j=n;j=i;j--) s++; T(n)=O(n*n) (2) x=0; for(i=1;i=n;i++) for(j=i+1;j=n;j++) x++; (3) x=0; for(i=1;in;i++) for(j=1;j=n-i;j++) x++; GetImag( Z, ImagPart ) 初始条件：复数已存在。 操作结果：用ImagPart返回复数Z的虚部值。 Add( z1,z2, sum ) 初始条件：z1, z2是复数。 操作结果：用sum返回两个复数z1, z2 的 和值。 } ADT Complex 假设:z1和z2是上述定义的复数 则 Add(z1, z2, z3) 操作的结果 z3 = z1 + z2 即为： ADT 有两个重要特征: 数据抽象 用ADT描述程序处理的实体时，强调的是其本质的特征、其所能完成的功能以及它和外部用户的接口（即外界使用它的方法）； 数据封装 将实体的外部特性和其内部实现细节分离，并且对外部用户隐藏其内部实现细节。 抽象数据类型的描述方法 抽象数据类型可用（D，S，P）三元组表示 其中，D 是数据对象， S 是 D 上的关系集， P 是对 D 的基本操作集。 ADT 抽象数据类型名 { 数据对象：〈数据对象的定义〉 数据关系：〈数据关系的定义〉 基本操作：〈基本操作的定义〉 } ADT 抽象数据类型名 其中基本操作的定义格式为: 基本操作名（参数表） 初始条件：〈初始条件描述〉 操作结果：〈操作结果描述〉 赋值参数 只为操作提供输入值；数值传递仅将数值传递给形参，而不返回结果. 引用参数 以打头，除可提供输入值外，还将返回操作结果;引用传递把实参(主函数中的)的地址传递给形参(子函数中的)，实参和形参其实都是同一变量,在被调用函数通过改变变量的值返回给调用函数,从而把结果带回. 在参数传递过程中，通过在参数上加上，表示引用参数。如果参数前没有，表示数值传递. 初始条件 描述了操作执行之前数据结构和参数应满足的条件，若不满足，则操作失败，并返回相应出错信息。 操作结果 说明了操作正常完成之后，数据结构的变化状况和应返回的结果。若初始条件为空，则省略之。 抽象数据类型的表示和实现 抽象数据类型需要通过固有数据类型(高级编程语言中已实现的数据类型)来实现。 例如，对以上定义的复数 typedef struct { float realpart； float imagpart； }complex； // -----存储结构的定义 // -----基本操作的函数原型说明 void Assign( complex Z, float realval, float imagval )； // 构造复数 Z,其实部和虚部分别被赋以参数 // realval 和 imagval 的值 float GetReal( cpmplex Z )； // 返回复数 Z 的实部值 float Getimag( cpmplex Z )； // 返回复数 Z 的虚部值 void add( complex z1, complex z2, complex sum )； // 以 sum 返回两个复数 z1, z2 的和 // -----基本