资源描述：
《抽象数据类型三元组的定义.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、抽象数据类型三元组的定义ADTTriplet{数据对象：D={e1,e2,e3
2、e1,e2,e3属于Elemset(定义了关系的某个集合)}数据关系：R1={
3、}基本操作：—InitTriplet(&T,v1,v2,v3)—初始条件：—操作结果：用e值取代三元组T的第i个元素—DestroyTriplet(&T)—初始条件：三元组T已经存在。—操作结果：销毁三元组T。—Get(T,i,&e)—初始条件：三元组T已经存在，1<=i<=3,—操作结果：用e返回三元组T的第i个元素。—Put(&T,i,e)—初始条件：三元组T已经存在，1<=i<=3,—操作结果：用e值
4、取代三元组T的第i个元素。—IsAscending(T)—初始条件：三元组T已经存在。—操作结果：如果三元组T的三个元素按升序排列，则返回TRUE;否则返回FALSE—IsDescending(T)—初始条件：三元组T已经存在。—操作结果：如果三元组T的三个元素按降序排列，则返回TRUE;否则返回FALSE—Max(T,&e)—初始条件：三元组T已经存在。—操作结果：用e返回三元组T的最大值。—Min(T,&e)—初始条件：三元组T已经存在。—操作结果：用e返回三元组T的最小值。}ADTTriplet抽象数据类型的表示与实现类C语言（做了扩充和修改）的表示如：预定义常量和类型#defineTR
5、UE1#defineFALSE0#defineOK1#defineERROR0#defineINFEASIVLE-1#defineOVERFLOW-2TypedefintStatusStatusGet(TripleT,inti,Elemtype*e)//初始条件：三元组T已经存在，1<=i<=3.//操作结果：用e返回三元组T的第i个元素{If(i<1
6、
7、i>3)returnERROR;*e=T[i-1];ReturnOK;}算法和算法分析算法（Algorithm）:对特定问题求解步骤的一种描述。算法的五个重要特性:1有穷性2确定性3可行性4输入4输出算法举例————气泡排序算法初始条件：N个
8、待排序的数a[0]—a[n-1]结果：排序后a[0]—a[n-1]从小到大排列1置标记change=TRUE;2i从n-1知道i=2做（3）--（6）步3change=FALSE;4j从0知道j=i-1做（5）5若a[j]>a[j+1]则交换他们并置change=TRUE6若change=FALSE则结束7算法结束1i从n-1知道i=2做2—3步2j从0知道j=i-1做33若a[j]>a[j+1]则交换他们4算法结束Voidbb_sort(inta[],intn){for(i=n-1;i>1;--i){for(j=0;ja[j+1]){a[j]←→a[j+1];}
9、}//bb_sort算法设计的要求算法应达到的目标1正确性2可读性3健壮性4效率与低存储量算法效率的度量1事后统计法2事前分析估算法]算法的时间复杂度；基本操作重复执行次数。它是问题规模n的某个函数f(n);T(n)=O(f(n))平均时间复杂度——时间复杂度与输入数据有关时采用平均时间复杂度或最最坏时间复杂度//气泡排序时间复杂度只考虑对问题规模的增长率在难以精确计算基本操作执行次数时，仅需要求增长率（或阶）即可。阶：for(i=2;i<=n:++i)For(j=2;j<=i;++j){++x;a[i,j]=x;}++x的执行次数关于n的增长率时O(n平方)最大的数量阶n的n次方n！线性表线
10、性表结构的特点：存在唯一的第一个数据元素存在唯一的最后一个数据元素除第一个外。每个数据元素均有且只有一个前驱元素；除最后一个外。每个数据元素均有且只有一个后继元素。线性表举例；字母表（A,B,C,,,XYZ）数据序列(6.17.28.50)N个元素的线性表（a1.a2,a3...an）第一个元素没有前驱最后一个元素没有后继第i个元素有唯一前驱唯一后继ADTList{数据对象：D={ai
11、ai属于Elemset,(i=1,2,,,nn大于等于0)}数据关系R1={
12、ai-1,ai属于D。（i=2.3...n）}基本操作：—InitList(&L);DestroyList(&L)
13、—ListInsert(8L,i,e)ListDelete(&L,i,e);—等等线性表ADT的基本操作；InitList(&L)操作结果：构造一个空的线性表LDestroyList(&L)初始条件：线性表L已经存在操作结果：销毁线性表LClearList(&L)初始条件：线性表L已经存在操作结果：将线性表L重置为空表。ListEmpty(L)逻辑值初始条件：线性表L已经存在操作结果：线性表L为空
