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

本课主题:抽象数据类型的表示和实现

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

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

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

教学内容:

I抽象数据类型定义(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 (-d，I = 2，...
二、类C语言语法

c类语言语法示例
1、预定义的常量和类型# defineu 1
# define fal 0
# define k1
# define error 0
# define effective-1
# define ever flow-。//Status是函数的类型，其值是函数结果状态码。
2。数据结构的存储结构首先是typedef ElemType
3。基本运算算法函数类型函数名(函数参数表){
//算法描述
语句序列
}//函数名
4 .赋值语句的简单赋值:变量名=表达式；
串行赋值:变量名1=变量名2=...=变量名k=表达式；

组赋值:(变量名1，...，变量名k)=(表达式1，...，表情k)；
结构名=结构名；
结构名=(值1，...，值k)；
变量名[] =表达式；
变量名[开始下标..结束下标] =变量名[开始下标..end下标]；

交换赋值:变量名变量名；
条件赋值:变量名=条件表达式？表情？t:表达式F
5，选择语句1和if(表达式)语句；
2。if(表达式)语句；
else语句；
3、switch(表达式){
case值1:语句序列1；打破；

...
case值n:语句序列n；打破；
默认值:语句序列n+1；打破；
}
4、switch{
case条件1:语句序列1；打破；

...
case条件n:语句序列n；打破；
默认值:语句序列n+1；打破；
}

6。(赋值初始值表达式的循环语句；条件；修改表达式序列)语句；
while(条件)语句；
do { statement sequence } while(条件)；
7。End语句返回[表达式]；
退货；//函数语句结束
break；//case end语句
exit(异常代码)；//异常结束语句

8、输入输出语句scanf([格式字符串]，变量1，...，变量n)；
9、注释//文本序列
10、基本函数max(表达式1，...、表达式n)
min、ABS、floor、CEIL、EOF、EOLN
11、逻辑运算&&AND运算；|||或运算

示例:线性表的实现:
ADT List{

Object: d = {ai | ai (-elemset，i = 1，2，...，n，n > = 0}

关系:R1={| ai-1，ai(- D，i=2...，n}

基本操作:

InitList(& L)
DestroyList(& L)
list insert(& L，I，e)
ListDelete(&L，I，&e)

}ADT列表

ListInsert(List &L，int i，ElemType e)

{if(iL.length+)返回错误；

q = &(l . elem[I-1])；

for(p = &(l . elem[l . length-1])；p > = q；-p)*(p+1)= * p；

* q = e；

++L .长度；

退货OK；

}