抽象数据类型三元组的定义

抽象数据类型三元组的定义ADTTriplet{数据对象：D={e1,e2,e3|e1,e2,e3属于Elemset(定义了关系的某个集合)}数据关系：R1={e1,e2|e2,.e3}基本操作：—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值取代三元组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语言（做了扩充和修改）的表示如：预定义常量和类型#defineTRUE1#defineFALSE0#defineOK1#defineERROR0#defineINFEASIVLE-1#defineOVERFLOW-2TypedefintStatusStatusGet(TripleT,inti,Elemtype*e)//初始条件：三元组T已经存在，1=i=3.//操作结果：用e返回三元组T的第i个元素{If(i1||i3)returnERROR;*e=T[i-1];ReturnOK;}算法和算法分析算法（Algorithm）:对特定问题求解步骤的一种描述。算法的五个重要特性:1有穷性2确定性3可行性4输入4输出算法举例————气泡排序算法初始条件：N个待排序的数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;i1;--i){for(j=0;ji;++j)if(a[j]a[j+1]){a[j]←→a[j+1];}}//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！线性表线性表结构的特点：存在唯一的第一个数据元素存在唯一的最后一个数据元素除第一个外。每个数据元素均有且只有一个前驱元素；除最后一个外。每个数据元素均有且只有一个后继元素。线性表举例；字母表（A,B,C,,,XYZ）数据序列(6.17.28.50)N个元素的线性表（a1.a2,a3...an）第一个元素没有前驱最后一个元素没有后继第i个元素有唯一前驱唯一后继ADTList{数据对象：D={ai|ai属于Elemset,(i=1,2,,,nn大于等于0)}数据关系R1={ai-1,ai|ai-1,ai属于D。（i=2.3...n）}基本操作：—InitList(&L);DestroyList(&L)—ListInsert(8L,i,e)ListDelete(&L,i,e);—等等线性表ADT的基本操作；InitList(&L)操作结果：构造一个空的线性表LDestroyList(&L)初始条件：线性表L已经存在操作结果：销毁线性表LClearList(&L)初始条件：线性表L已经存在操作结果：将线性表L重置为空表。ListEmpty(L)逻辑值初始条件：线性表L已经存在操作结果：线性表L为空表。则返回TURE;否则返回FALSEListLength(L)初始条件：线性表L已经存在操作结果：返回线性表L中的数据元素个数GetElem(L,i,&e);初始条件：线性表已经存在1=i=ListLength(L)操作结果：用e返回线性表L中第i个数据元素的值LocateElem(L,e,conpare())初始条件：线性表L已经存在，conpare()时数据元素判定函数。操作结果：返回L中第1个与e满足compare()的数据元素的位序。若这样的数据元素不存在则返回值为0.（返回位序）PriorElem(L,cur_e,&pre_e)初始条件：线性表已经存在。操作结果：若cur_e时L的数据元素，且不是第一个，则用pre_e返回它的前驱，否则操作失败；pre_e无意义//若cur_e为第一元素则返回一个复制，否则返回它本身NextElem(L,cur_e,&next_e)初始条件：线性表L已经存在，操作结果：若cur_e是L的数据元素。且不是最后一个。则用next_e返回它的后继，否则操作失败。Next_e无意义ListInsert(&L,i,e)初始条件：线性表L已经存在，i=i=Listlength(L)+1.操作结果：在L在第I个位置之前插入新的数据元素e。L的长度加一。插入前（长度为N）（a1,a2-------an）插入后（长度为N+1）（a1...ai-1,e,ai...an）ListDelete(&L,i,&e)初始条件：线性表L已经存在，1=i=Listlength(L).操作结果：删除L的第i个数据元素，并用E返回其值。L的长度减一删除前（a1.a2....an）删除后（a1...ai-1.ai+1...an）