抽象数据类型的表示与实现.ppt

第一章 绪论,1.1 什么是数据结构,1.2 基本概念和术语,1.4 算法和算法分析,1.3 抽象数据类型的表示与实现,抽象数据类型需要通过固有数据类型(高级编程语言中已实现的数据类型)来实现。,1.3 抽象数据类型的表示与实现,由于我们在高级程序设计语言的虚拟层次上讨论抽象数据类型的表现和实现，并且讨论的数据结构及其算法主要是便于理解，故采用伪码和C语言之间的类C语言作为描述的工具，有时也采用伪码描述一些只含抽象操作的抽象算法。这使得数据结构和算法的描述和讨论简明清晰，不拘泥于C语言的细节，又能容易转换成C或C+程序。,1）预定义常量和类型：/函数结果状态代码#define TRUE 1#define FALSE 0#define OK 1#define ERROR 0#define INFEASIBLE-1#define OVERFLOW-2/Status 是函数的类型，其值是函数结果状态代码 typedef int Status;,2）数据结构的表示（存储结构）用类型定义（typedef）描述。数据元素类型约定为ElemType，由用户在使用该数据类型时自行定义。,3）基本操作的算法都用以下形式的函数描述：函数类型 函数名（函数参数表）/算法说明 语句序列/函数名 除了函数的参数需要说明类型外，算法中使用的辅助变量可以不作变量说明，必要时对其作用给予注释。,4）赋值语句：简单赋值 变量名表达式；串联赋值 变量名1变量名2变量名k表达式；成组赋值（变量名1,变量名k）（表达式1,表达式k）结构名结构名；结构名（值1,值k）；变量名 表达式；变量名起始下标终止下标变量名起始下标终止下标；交换赋值 变量名 变量名；条件赋值 变量名条件表达式？表达式T：表达式F；,5）选择语句：条件语句1 if（表达式）语句；条件语句2 if（表达式）语句；else语句；开关语句1 switch（表达式）case值1：语句序列1；break；case值n：语句序列n；break；default：语句序列n1；开关语句2 switchcase条件1：语句序列1；break；case条件n：语句序列n：break；default：语句序列n1；,6）循环语句：for语句 for（赋初值表达式序列；条件；修改表达式序列）语句；while语句 while（条件）语句；do-while语句 do 语句序列；while（条件）；,7）结束语句：函数结束语句return表达式；return；case结束语句break；异常结束语句exit（异常代码）；,8）输入和输出语句：输入语句scanf（格式串，变量1，变量n）；输出语句printf（格式串，表达式1，表达式n）；,9）注释单行注释/文字序列,10）基本函数：求最大值max（表达式1，表达式n）求最小值min（表达式1，表达式n）求绝对值abs（表达式）求不足整数值 floor（表达式）求进位整数值ceil（表达式）判定文件结束eof（文件变量）或eof 判定行结束eoln（文件变量）或eoln,11）逻辑运算约定 与运算&：对于A&B，当A的值为0时，不再对B求值。或运算|：对于A|B，当A的值为非0时，不再对B求值。,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 的和,/-基本操作的实现,void add(complex z1,complex z2,complex,其它省略,