教案 程序设计—数据结构 第一章绪论 目录 1.1什么是数据结构. 1.2基本概念和术语 1.3抽象数据类型的表示与实现 ......... 1.4算法和算法分析. ......3 1.4.1算法 3 14.2算法设计的原则 1.4.3算法性能分析 4 .4 1.4.4算法的存储空间需求 6 文档编号 完成时间 完成人张昱 修改时间2003-93 第0页
程序设计——数据结构 第一章 绪论 第 0 页 文档编号 完 成 人 张 昱 完成时间 修改时间 2003-9-3 目 录 1.1 什么是数据结构........................................................................................................1 1.2 基本概念和术语........................................................................................................1 1.3 抽象数据类型的表示与实现......................................................................................1 1.4 算法和算法分析........................................................................................................3 1.4.1 算法................................................................................................................3 1.4.2 算法设计的原则..............................................................................................4 1.4.3 算法性能分析..................................................................................................4 1.4.4 算法的存储空间需求.......................................................................................6
教案 程序设计—数据结构 第一章绪论 第1章绪论 1.1什么是数据结构 1.2基本概念和术语 1.3抽象数据类型的表示与实现 体函数结果状态代码 多 #define TRUE 1 #define FALSE 0 #define OK 1 #define ERroR 0 #define INFEASIBLE-1 #define OVERFLOW -2 体函数结果状态类型，其值为上述的状态代码 制 typedef int Status; 1、例1-3-1抽象数据类型复数的定义 ADT Complex{ 数据对象：D={el,e2|el,e2∈RealSet} 数据关系：R1={|el是复数的实数部分，e2是复数的虚数部分} 基本操作： InitComplex(&Z,v1,v2 操作结果：构造复数Z其实部和虚部分别被赋以参数V1和v2的值。 DestroyComplex(&Z) 操作结果：复数Z被销毁。 GetReal(Z,&realPart) 初始条件：复数已存在。 操作结果：用realPart返回复数Z的实部值。 Getlmag(Z.&ImagPart 初始条件：复数己存在。 操作结果：用ImagPart返回复数Z的虚部值。 Add(z1.z2.&sum 初始条件：z1,z2是复数。 操作结果：用sum返回两个复数zl、z2的和值。 }ADT Complex 2、例1-3-2抽象数据类型三元组的定义 ADT Triplet 数据对象：D={el,e2,e3|el,e2,e3∈ElemSet} 数据关系：R1={,} 基本操作： InitTriplet(&T.v1.v2.v3) 操作结果：构造三元组T,元素el,e2和e3分别被赋以参数vl,v2和v3的值。 DestroyTriplet(&T) 文档编号 完成时间 完成人张昱 修改时间2003-93 第1页
程序设计——数据结构 第一章 绪论 第 1 页 文档编号 完 成 人 张 昱 完成时间 修改时间 2003-9-3 第1章 绪论 1.1 什么是数据结构 1.2 基本概念和术语 1.3 抽象数据类型的表示与实现 /* 函数结果状态代码 */ #define TRUE 1 #define FALSE 0 #define OK 1 #define ERROR 0 #define INFEASIBLE -1 #define OVERFLOW -2 /* 函数结果状态类型，其值为上述的状态代码 */ typedef int Status; 1、例 1-3-1 抽象数据类型复数的定义 ADT Complex { 数据对象：D＝{e1,e2｜e1,e2∈RealSet } 数据关系：R1＝{ | e1 是复数的实数部分,e2 是复数的虚数部分 } 基本操作： InitComplex( &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 2、例 1-3-2 抽象数据类型三元组的定义 ADT Triplet { 数据对象：D＝{e1,e2,e3｜e1,e2,e3∈ElemSet } 数据关系：R1＝{ , } 基本操作： InitTriplet( &T, v1, v2, v3 ) 操作结果：构造三元组 T,元素 e1,e2 和 e3 分别被赋以参数 v1,v2 和 v3 的值。 DestroyTriplet( &T )
教案 程序设计— 数据结构 第一章绪论 操作结果：三元组T被销毁。 Get(T.i.&e) 初始条件： 三元组T已存在，1≤i≤3。 操作结果：用e返回T的第i元的值。 Put(&T,i,e) 初始条件：三元组T已存在，1≤i≤3。 操作结果：改变T的第i元的值为e。 IsAscending(T) 初始条件：三元组T已存在。 操作结果：如果T的三个元素按升序排列，则返回1，否则返回0。 IsDescending(T) 初始条件：三元组T己存在。 操作结果：如果T的三个元素按降序排列，则返回1，否则返回0。 Max(T,&e) 初始条件：三元组T已存在。 操作结果：用e返回T的三个元素中的最大值。 Min(T,&e)） 初始条件：三元组T己存在。 操作结果：用e返回T的三个元素中的最小值。 }ADT Triplet 3、例1-3-3ADT复数的C描述 typedef struct{ double realpart; double imagpart; }Complex; boolean assign(Complex *pSrc,Complex *pDes) { if (pSrc ==NULL Il pDes==NULL) return ERROR: pDes->realpart pSrc->realpart; pDes->imagpart=pSrc->imagpart; return TRUE; } Complex *add(Complex *pZ1,Complex *pZ2) { Complex *pSum=(Complex *)malloc(sizeof(Complex)); if(pSum=NULL return NULL: pSum->realpart=pZI->realpart +pZ2->realpart; pSum->imagpart=pZ1->imagpart +pZ2->imagpart; return pSum; } 4、例1-3-4ADT复数的C+描述 class Complex { 文档编号 完成时间 完成人张昱 修改时间2003-93 第2页
程序设计——数据结构 第一章 绪论 第 2 页 文档编号 完 成 人 张 昱 完成时间 修改时间 2003-9-3 操作结果：三元组 T 被销毁。 Get( T, i, &e ) 初始条件：三元组 T 已存在，1≤i≤3。 操作结果：用 e 返回 T 的第 i 元的值。 Put( &T, i ,e ) 初始条件：三元组 T 已存在，1≤i≤3。 操作结果：改变 T 的第 i 元的值为 e。 IsAscending( T ) 初始条件：三元组 T 已存在。 操作结果：如果 T 的三个元素按升序排列，则返回 1，否则返回 0。 IsDescending( T ) 初始条件：三元组 T 已存在。 操作结果：如果 T 的三个元素按降序排列，则返回 1，否则返回 0。 Max( T, &e ) 初始条件：三元组 T 已存在。 操作结果：用 e 返回 T 的三个元素中的最大值。 Min( T, &e ) 初始条件：三元组 T 已存在。 操作结果：用 e 返回 T 的三个元素中的最小值。 } ADT Triplet 3、例 1-3-3 ADT 复数的 C 描述 typedef struct { double realpart; double imagpart; }Complex; boolean assign(Complex *pSrc, Complex *pDes) { if (pSrc ==NULL || pDes==NULL ) return ERROR; pDes->realpart = pSrc->realpart; pDes->imagpart = pSrc->imagpart; return TRUE; } Complex *add(Complex *pZ1, Complex *pZ2) { Complex *pSum = (Complex *)malloc(sizeof(Complex)); if ( pSum==NULL ) return NULL; pSum->realpart = pZ1->realpart + pZ2->realpart; pSum->imagpart = pZ1->imagpart + pZ2->imagpart; return pSum; } 4、例 1-3-4 ADT 复数的 C++描述 class Complex {
教案 程序设计—数据结构 第一章绪论 ∥类的声明 protected: double realpart; double imagpart, public: Complex(); Complex(double realVal,double imagVal); Complex(Complex&z)assign(z);) -Complex(): void assign(Complex&z): double getReal(void)const return realpart; double getlmag(void)const return imagpart; friend Complex add(Complex&z1,Complex&z2); ∥类的实现部分 Complex::Complex(double realVal,double imag Val) realpart=realVal; imagpart=imag Val; } void Complex::assign(Complex&z) realpart=z.realpart; imagpart=z.imagpart; Complex add(Complex&z1,Complex&z2) Complex sum(z1): sum.realpart +=z2.realpart; sum.imagpart+=z2.imagpart: return sum; 1.4算法和算法分析 1.4.1算法 算法是为了解决某类问题而规定的一个有限长的操作序列。 一个算法必须满足以下五个重要特性： 1.有穷性对于任意一组合法输入值，在执行有穷步骤之后一定能结束，且算法中的每 一步骤都能在有限时间内完成； 2.确定性对于每种情况下所应执行的操作，在算法中都有确切的规定，使算法的执行 者或阅读者都能明确其含义及如何执行。即在任何条件下，算法都只有一条执行路径； 文档编号 完成时间 完成人张昱 修改时间2003-93 第3页
程序设计——数据结构 第一章 绪论 第 3 页 文档编号 完 成 人 张 昱 完成时间 修改时间 2003-9-3 // 类的声明 protected: double realpart; double imagpart; public: Complex( ); Complex(double realVal，double imagVal); Complex(Complex& z){assign(z) ;} ~Complex( ); void assign(Complex& z); double getReal(void) const { return realpart;} double getImag(void) const { return imagpart;} friend Complex add(Complex& z1, Complex& z2); }； // 类的实现部分 Complex::Complex(double realVal, double imagVal) { realpart = realVal; imagpart= imagVal; } void Complex::assign(Complex& z) { realpart = z.realpart; imagpart= z.imagpart; } Complex add(Complex& z1, Complex& z2) { Complex sum(z1); sum.realpart += z2.realpart； sum.imagpart += z2.imagpart； return sum; } 1.4 算法和算法分析 1.4.1 算法 算法是为了解决某类问题而规定的一个有限长的操作序列。 一个算法必须满足以下五个重要特性： 1． 有穷性 对于任意一组合法输入值，在执行有穷步骤之后一定能结束，且算法中的每 一步骤都能在有限时间内完成； 2． 确定性 对于每种情况下所应执行的操作，在算法中都有确切的规定，使算法的执行 者或阅读者都能明确其含义及如何执行。即在任何条件下，算法都只有一条执行路径；
教案 程序设计—数据结构 第一章绪论 3. 可行性算法中的所有操作都必须足够基本，都可以通过已经实现的基本操作运算有 限次实现之： 4. 有0个或多个输入作为算法加工对像的量值，通常体现为算法中的一组变量。有些 输入量需要在算法执行过程中输入，而有的算法表面上可以没有输入，实际上已被嵌 入算法之中； 5.有1个或多个输出它是一组与“输入”与确定关系的量值，是算法进行信息加工后 得到的结果，这种确定关系即为算法的功能。 1.4.2算法设计的原则 设计算法时，通常应考虑达到以下目标： 1、正确性 首先，算法应当满足以特定的“规格说明”方式给出的需求。 其次，对算法是否“正确”的理解可以有以下四个层次： a)程序中不含语法错误： b)程序对于几组输入数据能够得出满足要求的结果 c 程序对于精心选择的、典型、苛刻且带有刁难性的几组输入数据能够得出满足要求的 结果； d)程序对于一切合法的输入数据都能得出满足要求的结果； 通常以第c层意义的正确性作为衡量一个算法是否合格的标准。 2、可读性 算法主要是为了人的阅读与交流，其次才是为计算机执行。因此算法应该易于人的理解： 另一方面，晦涩难读的程序易于隐藏较多错误而难以调试； 3、健壮性 当输入的数据非法时，算法应当恰当地作出反映或进行相应处理，而不是产生莫名奇妙的 输出结果。并且，处理出错的方法不应是中断程序的执行，而应是返回一个表示错误或错误性 质的值，以便在更高的抽象层次上进行处理。 4、高效率与低存储量需求 通常，效率指的是算法执行时间；存储量指的是算法执行过程中所需的最大存储空间。两 者都与问题的规模有关。 1.4.3算法性能分析 1、事后统计法 缺点：1、必须执行程序 2、其它因素掩盖算法本质 文档编号 完成时间 完成人张昱 修改时间2003-93 第4页
程序设计——数据结构 第一章 绪论 第 4 页 文档编号 完 成 人 张 昱 完成时间 修改时间 2003-9-3 3． 可行性 算法中的所有操作都必须足够基本，都可以通过已经实现的基本操作运算有 限次实现之； 4． 有 0 个或多个输入 作为算法加工对象的量值，通常体现为算法中的一组变量。有些 输入量需要在算法执行过程中输入，而有的算法表面上可以没有输入，实际上已被嵌 入算法之中； 5． 有 1 个或多个输出 它是一组与“输入”与确定关系的量值，是算法进行信息加工后 得到的结果，这种确定关系即为算法的功能。 1.4.2 算法设计的原则 设计算法时，通常应考虑达到以下目标： 1、正确性 首先，算法应当满足以特定的“规格说明”方式给出的需求。 其次，对算法是否“正确”的理解可以有以下四个层次： a) 程序中不含语法错误； b) 程序对于几组输入数据能够得出满足要求的结果； c) 程序对于精心选择的、典型、苛刻且带有刁难性的几组输入数据能够得出满足要求的 结果； d) 程序对于一切合法的输入数据都能得出满足要求的结果； 通常以第 c 层意义的正确性作为衡量一个算法是否合格的标准。 2、可读性 算法主要是为了人的阅读与交流，其次才是为计算机执行。因此算法应该易于人的理解； 另一方面，晦涩难读的程序易于隐藏较多错误而难以调试； 3、健壮性 当输入的数据非法时，算法应当恰当地作出反映或进行相应处理，而不是产生莫名奇妙的 输出结果。并且，处理出错的方法不应是中断程序的执行，而应是返回一个表示错误或错误性 质的值，以便在更高的抽象层次上进行处理。 4、高效率与低存储量需求 通常，效率指的是算法执行时间；存储量指的是算法执行过程中所需的最大存储空间。两 者都与问题的规模有关。 1.4.3 算法性能分析 1、事后统计法 缺点：1、必须执行程序 2、其它因素掩盖算法本质
教案 程序设计—数据结构 第一章绪论 2、事前分析估算法 和算法执行时间相关的因素： 1）算法选用的策略 2)问题的规模 3)编写程序的语言 4)编译程序产生的机器代码的质量 5)计算机执行指令的速度 3、时间复杂度 1)定义 一个特定算法的“运行工作量”的大小，只依赖于问题的规模(（通常用整数量表示)， 或者说，它是问题规模的函数。 假如，随着问题规模的增长，算法执行时间的增长率和f(n)的增长率相同，则可记作： T(n)=O(f(n)) 称T()为算法的（渐近）时间复杂度 2)例子 例1-4-1如下为NXN矩阵相乘的算法，乘法运算是“矩阵相乘问题”的基本操作。整个 算法的执行时间与该基本操作（乘法）重复执行的次数m成正比，记作T)=O() for (i=1:i1 &change;--i){ change=FALSE: for(j-0;ja[j+1]){ aj]+→aj+l] change=TRUE; } 文档编号 完成时间 完成人张昱 修改时间2003-9-3 第5页
程序设计——数据结构 第一章 绪论 第 5 页 文档编号 完 成 人 张 昱 完成时间 修改时间 2003-9-3 2、事前分析估算法 和算法执行时间相关的因素： 1）算法选用的策略 2）问题的规模 3）编写程序的语言 4）编译程序产生的机器代码的质量 5）计算机执行指令的速度 3、时间复杂度 1) 定义 一个特定算法的“运行工作量”的大小，只依赖于问题的规模（通常用整数量 n 表示）， 或者说，它是问题规模的函数。 假如，随着问题规模 n 的增长，算法执行时间的增长率和 f(n)的增长率相同，则可记作： T (n) = O(f(n)) 称 T (n) 为算法的(渐近)时间复杂度 2) 例子 例 1-4-1 如下为 N×N 矩阵相乘的算法，乘法运算是“矩阵相乘问题”的基本操作。整个 算法的执行时间与该基本操作(乘法)重复执行的次数 n 3 成正比，记作 T(n) = O(n 3 ) for (i=1; i1 && change; --i ) { change = FALSE; for (j=0; j a[j+1]) { a[j] ←→ a[j+1]; change = TRUE; }
教案 程序设计—数据结构 第一章绪论 }l∥bubble sort 1.4.4算法的存储空间需求 算法的空间复杂度 S(n)=O(g(n)) 表示随着问题规模n的增大，算法运行所需存储量的增长率与g()的增长率相同。 算法的存储量包括：1)输入数据所占空间；2)程序本身所占空间；3)辅助变量所占空间。 若输入数据所占空间只取决与问题本身，和算法无关，则只需要分析除输入和程序之外的 额外空间。 若所需额外空间相对于输入数据量来说是常数，则称此算法为原地工作。 若所需存储量依赖于特定的输入，则通常按最坏情况考虑。 文档编号 完成时间 完成人张昱 修改时间2003-93 第6页
程序设计——数据结构 第一章 绪论 第 6 页 文档编号 完 成 人 张 昱 完成时间 修改时间 2003-9-3 } } // bubble_sort 1.4.4 算法的存储空间需求 算法的空间复杂度 S(n) = O(g(n)) 表示随着问题规模 n 的增大，算法运行所需存储量的增长率与 g(n)的增长率相同。 算法的存储量包括：1）输入数据所占空间；2）程序本身所占空间；3）辅助变量所占空间。 若输入数据所占空间只取决与问题本身，和算法无关，则只需要分析除输入和程序之外的 额外空间。 若所需额外空间相对于输入数据量来说是常数，则称此算法为原地工作。 若所需存储量依赖于特定的输入，则通常按最坏情况考虑