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

1、本课主题：抽象数据类型的表示与实现教学目的：了解抽象数据类型的定义、表示和实现方法教学重点：抽象数据类型表示法、类C语言语法教学难点：抽象数据类型表示法授课内容：一、抽象数据类型定义（ADT）作用：抽象数据类型可以使我们更容易描述现实世界。例：用线性表描述学生成绩表，用树或图描述遗传关系。定义：一个数学模型以及定义在该模型上的一组操作。关键：使用它的人可以只关心它的逻辑特征，不需要了解它的存储方式。定义它的人同样不必要关心它如何存储。例：线性表这样的抽象数据类型，其数学模型是：数据元素的集合，该集合内的元素有这样的关系：除第一个和最后一个外,每个元素有的前趋和的后继。可以有这样一些操作：插入一

2、个元素、删除一个元素等。抽象数据类型分类原子类型值不可分解，如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,.,n除第一个和最后一个外，每个元素有的直接前趋和的直接后继基本操作Listlnse

3、rt（&L,i,e）L为线性表，i为位置，e为数据元素。类C语言语法示例1、预定义常量和类型#defineTRUE1#defineFALSE0#defineOK1#defineERROR0#definelNFEASlBLE-1#defineOVERFLOW-2typedefinStatus;/Statu是函数的类型，其值是函数结果状态代码。2、数据结构的存储结构typedefElemTypefirst;3、基本操作的算法函数类型函数名（函数参数表）/算法说明语句序列/函数名4、赋值语句简单赋值：变量名=表达式；串联赋值：变量名1=变量名2=.=变量名丘=表达式；成组赋值：（变量名1,变量名k）

4、=（表达式1,表达式k）;结构名=结构名；结构名=（值1,，值k）;变量名=表达式；变量名起始下标终止下标=变量名起始下标终止下标;交换赋值：变量名变量名；条件赋值：变量名=条件表达式？表达式？表达式T:表达式F5、选择语句1、if（表达式）语句；2、if（表达式）语句；else语句；3、switch（表达式）case值1：语句序列1；break;case值n:语句序列n;break;default:语句序列n+1;break;4、switchcase条件1：语句序列1；break;case条件n:语句序列n;break;default:语句序列n+1;break;6、循环语句for（赋初值表

5、达式；条件；修改表达式序列）语句;while（条件）语句；do语句序列while（条件）；7、结束语句return表达式；return;/函数结束语句break;/case纟吉束语句exit（异常代码）;/异常结束语句&输入和输出语句scanf（格式串,变量1,变量n）;9、注释文字序列10、基本函数max（表达式1,，表达式n）min,abs,floor,ceil,eof,eoln11、逻辑运算&与运算；|或运算例：线性表的实现：ADTList数据对象：D=ai|ai（-ElemSet,i=1,2,.,n,n=0数据关系：R1=|ai-1,ai（-D,i=2,.,n基本操作：InitList（&L）DestroyList（&L）ListInsert（&L,i,e）ListDelete（&L,i,&e）ADTListListInsert（List&L,inti,ElemTypee）if（iL.length+）returnERR