数据结构教程第二课抽象数据类型的表示与实现
本课主题:抽象数据类型的表示和实现
教学目的:了解抽象数据类型的定义、表示和实现。
教学重点:抽象数据类型表示,类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;
}
位律师回复
0条评论