本课主题： 抽象数据类型的表示与实现

教学目的： 了解抽象数据类型的定义、表示和实现方法

教学重点： 抽象数据类型表示法、类C语言语法

教学难点： 抽象数据类型表示法

授课内容：

一、抽象数据类型定义（ADT）

作用：抽象数据类型可以使我们更容易描述现实世界。例：用线性表描述学生成绩表，用树或图描述遗传关系。

定义：一个数学模型以及定义在该模型上的一组操作。

关键：使用它的人可以只关心它的逻辑特征，不需要了解它的存储方式。定义它的人同样不必要关心它如何存储。

例：线性表这样的抽象数据类型，其数学模型是：数据元素的集合，该集合内的元素有这样的关系：除第一个和最后一个外，每个元素有唯一的前趋和唯一的后继。可以有这样一些操作：插入一个元素、删除一个元素等。

抽象数据类型分类

原子类型 值不可分解，如int 固定聚合类型 值由确定数目的成分按某种结构组成，如复数 可变聚合类型 值的成分数目不确定如学生基本情况

抽象数据类型表示法：

一、

三元组表示：（D，S，P）

其中D是数据对象，S是D上的关系集，P是对D的基本操作集。

二、书中的定义格式：

ADT 抽象数据类型名{

数据对象：<数据对象的定义>

数据关系：<数据关系的定义>

基本操作：<基本操作的定义>

}ADT 抽象数据类型名

例：线性表的表示

名称 线性表 数据对象 D={ai| ai(-ElemSet,i=1,2,...,n,n>=0} 任意数据元素的集合 数据关系 R1={<ai-1,ai>| ai-1,ai(- D,i=2,...,n} 除第一个和最后一个外，每个元素有唯一的直接前趋和唯一的直接后继 基本操作 ListInsert(&L,i,e) L为线性表，i为位置，e为数据元素。 ListDelete(&L,i,e) ...

二、类C语言语法

类C语言语法示例

1、预定义常量和类型 #define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define INFEASIBLE -1
#define OVERFLOW -2
typedef in Status; //Status是函数的类型，其值是函数结果状态代码。 2、数据结构的存储结构 typedef ElemType first; 3、基本操作的算法

函数类型 函数名（函数参数表）{
//算法说明
语句序列
}//函数名

4、赋值语句 简单赋值： 变量名=表达式； 串联赋值： 变量名1=变量名2=...=变量名k=表达式； 成组赋值: （变量名1，...,变量名k）=（表达式1，...,表达式k);
结构名=结构名；
结构名=（值1，...，值k);
变量名[]=表达式；
变量名[起始下标..终止下标]=变量名[起始下标..终止下标]；
交换赋值： 变量名<-->变量名； 条件赋值： 变量名=条件表达式？表达式？表达式T：表达式F 5、选择语句

1、if（表达式） 语句；
2、if（表达式） 语句；
else 语句；
3、switch(表达式）{
case 值1：语句序列1；break;

...
case 值n：语句序列n；break;
default:语句序列n 1；break;
}
4、switch{
case 条件1：语句序列1；break;

...
case 条件n：语句序列n；break;
default:语句序列n 1；break;
}

6、循环语句 for（赋初值表达式；条件；修改表达式序列）语句；
while（条件）语句；
do{ 语句序列}while（条件）； 7、结束语句

return [表达式]；
return; //函数结束语句
break; //case结束语句
exit(异常代码); //异常结束语句

8、输入和输出语句 scanf（[格式串]，变量1，...,变量n）； 9、注释 //文字序列 10、基本函数 max（表达式1，...，表达式n）
min,abs,floor,ceil,eof,eoln 11、逻辑运算 &&与运算；||或运算

例：线性表的实现：
ADT List{

数据对象: D={ai| ai(-ElemSet,i=1,2,...,n,n>=0}
 

本文章更多内容：1 - 2 - 下一页>>