数据结构详细教案——数据结构绪论解析.docVIP

数据结构教案 第一章 绪论 目 录 1.1 什么是数据结构 1 1.2 基本概念和术语 1 1.3 抽象数据类型的表示与实现 1 1.4 算法和算法分析 4 1.4.1 算法 4 1.4.2 算法设计的原则 4 1.4.3 算法性能分析 5 1.4.4 算法的存储空间需求 7 绪论 什么是数据结构 基本概念和术语 抽象数据类型的表示与实现 /* 函数结果状态代码 */ #define TRUE 1 #define FALSE 0 #define OK 1 #define ERROR 0 #define INFEASIBLE -1 #define OVERFLOW -2 /* 函数结果状态类型，其值为上述的状态代码 */ typedef int Status; 例1-3-1 抽象数据类型复数的定义 ADT Complex { 数据对象：D＝{e1,e2｜e1,e2∈RealSet } 数据关系：R1＝{e1,e2 | 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 例1-3-2 抽象数据类型三元组的定义 ADT Triplet { 数据对象：D＝{e1,e2,e3｜e1,e2,e3∈ElemSet } 数据关系：R1＝{e1,e2 , e2,e3} 基本操作： 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 例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; ret