数据结构2-抽象数据类型的表示与实现.ppt

数 据 结 构  第二课 抽象数据类型的表示与实现 第二课 抽象数据类型的表示与实现 本课主题： 抽象数据类型的表示与实现 教学目的： 了解抽象数据类型的定义、表示和实现方法 教学重点： 抽象数据类型表示法、类C语言语法 教学难点： 抽象数据类型表示法 授课内容： 一、抽象数据类型定义（ADT） 抽象数据类型:是指一个数学模型以及定义在该模型上的一组操作。抽象数据类型和数据类型实质上是一个概念，它仅取决于数据类型的逻辑性，而与其在计算机内部如何表示和实现是无关的。 抽象数据类型的定义由一个值域和定义在该值域上的一组操作组成。 抽象数据类型实例—线性表 该集合内的元素有 关系：除第一个和最后一个外，每个元素有唯一的前趋和唯一的后继。 操作：插入一个元素、删除一个元素等。 抽象数据类型分类(按其值的不同特性 ) 抽象数据类型表示法(1) 一、三元组表示：（D，S，P） 其中D是数据对象，S是D上的关系集，P是对D的基本操作。 二、书中的定义格式： ADT 抽象数据类型名 {数据对象：数据对象的定义 数据关系：数据关系的定义 基本操作：基本操作的定义 }ADT 抽象数据类型名 抽象数据类型表示法(2) 数据对象和数据关系的定义用伪码描述。 数据基本操作的定义格式： 基本操作名（参数表） 初始条件：〈初始条件描述〉 操作结果：〈操作结果描述〉 抽象数据类型三元组表示法实例 ADT Triplet{ 数据对象：D={e1，e2,e3 |e1,e2,e3∈Elemset(定义了关系运算的某个集合)} 数据关系：R1={〈e1,e2,e2,e3〉 基本操作： InitTriplet(T,v1,v2,v3) DestroyTriplet（T） Get（T,i,e） Put(T,i,e) IsAscending(T) IsDescending(T) Max(T,e) Min(T,e) }ADT Triplet ADT 抽象数据类型实例—线性表 抽象数据类型的实现 抽象数据类型可通过固有数据类型来表示和实现，即利用处理器中已存在的数据类型来说明新的结构，用已经实现的操作来组合新的操作。 二、类C语言语法 (1) 1、预定义常量和类型 #define TRUE 1 #define FALSE 0 #define OK 1 #define ERROR 0 #define INFEASIBLE -1 #define OVERFLOW -2 typedef int Status; //Status是函数的类型，其值是函数结果状态代码。 二、类C语言语法 (2) 2、数据结构的存储结构 typedef ElemType first; 3、基本操作的算法 函数类型 函数名（函数参数表） { //算法说明 语句序列 }//函数名 4、赋值语句 简单赋值： 变量名=表达式； 串联赋值： 变量名1=变量名2=...=变量名k=表达式 二、类C语言语法 (3) 成组赋值: （变量名1，...,变量名k）=（表达式1，...,表达式k); 结构名=结构名； 结构名=（值1，...，值k); 变量名[ ]=表达式； 变量名[起始下标..终止下标]=变量名[起始下标..终止下标]； 交换赋值：变量名--变量名； 条件赋值：变量名=条件表达式？表达式？表达式T：表达式F 二、类C语言语法 (4) 5、选择语句 5.1 if（表达式） 语句； 5.2 if（表达式） 语句； else 语句； 5.3 switch(表达式）{ case 值1：语句序列1；break; ... case 值n：语句序列n；break; default:语句序列n+1；break; } 二、类C语言语法 (5) 6、循环语句 for（赋初值表达式；条件；修改表达式序列）语句； while（条件）语句； do{ 语句序列}whil