数据结构教程第二课抽象数据类型的表示与实现

文章作者 100test 发表时间 2007:03:10 18:25:35
来源 100Test.Com百考试题网

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

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

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

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

授课内容：

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

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

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

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

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

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

抽象数据类型表示法：

一、

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

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

二、书中的定义格式：

ADT 抽象数据类型名{

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

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

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

}ADT 抽象数据类型名

例：线性表的表示

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