第二课：抽象数据类型的表示与实现
时间：2010-09-21 来源：yuxinlen
第二课
本课主题： 抽象数据类型的表示与实现
教学目的： 了解抽象数据类型的定义、表示和实现方法
教学重点： 抽象数据类型表示法、类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 |
|
|||
|
2、数据结构的存储结构 |
typedef ElemType first; |
|
|||
|
3、基本操作的算法 |
函数类型 函数名（函数参数表）{ |
|
|||
|
4、赋值语句 |
简单赋值： |
变量名=表达式； |
|
||
|
串联赋值： |
变量名1=变量名2=...=变量名k=表达式； |
|
|||
|
成组赋值: |
（变量名1，...,变量名k）=（表达式1，...,表达式k); |
||||
|
交换赋值： |
变量名<-->变量名； |
|
|
||
|
条件赋值： |
变量名=条件表达式？表达式？表达式T：表达式F |
|
|
||
|
5、选择语句 |
1、if（表达式） 语句；
...
... |
|
|
||
|
6、循环语句 |
for（赋初值表达式；条件；修改表达式序列）语句； |
|
|
||
|
7、结束语句 |
return [表达式]； |
|
|
||
|
8、输入和输出语句 |
scanf（[格式串]，变量1，...,变量n）； |
|
|
||
|
9、注释 |
//文字序列 |
|
|
||
|
10、基本函数 |
max（表达式1，...，表达式n） |
|
|
||
|
11、逻辑运算 |
&&与运算；||或运算 |
|
|
||
例：线性表的实现：
ADT List{
数据对象: D={ai| ai(-ElemSet,i=1,2,...,n,n>=0}
数据关系: R1={<ai-1,ai>| ai-1,ai(- D,i=2,...,n}
基本操作：
InitList(&L)
DestroyList(&L)
ListInsert(&L,i,e)
ListDelete(&L,i,&e)
}ADT List
ListInsert(List &L,int i,ElemType e)
{if(i<1||i>L.length+) return ERROR;
q=&(L.elem[i-1]);
for(p=&(L.elem[L.length-1]);p>=q;--p) *(p+1)=*p;
*q=e;
++L.length;
return OK;
}
下面是
相关阅读 更多 +
