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

1、抽象数据类型三元组的定义ADT Triplet数据对象：D= e1,e2,e3 | e1,e2,e3属于Elemset(定义了关系的某个集合)数据关系：R1=|基本操作：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个元素。 IsAscend

2、ing(T) 初始条件：三元组T已经存在。 操作结果：如果三元组T的三个元素按升序排列，则返回TRUE;否则返回FALSEIsDescending(T) 初始条件：三元组T已经存在。 操作结果：如果三元组T的三个元素按降序排列，则返回TRUE;否则返回FALSE Max(T,&e) 初始条件：三元组T已经存在。 操作结果：用e返回三元组T的最大值。Min(T,&e) 初始条件：三元组T已经存在。 操作结果：用e返回三元组T的最小值。ADT Triplet抽象数据类型的表示与实现类C语言（做了扩充和修改）的表示如：预定义常量和类型#define TRUE 1#define FALSE0#defi

3、ne OK1#define ERROR0#define INFEASIVLE-1#define OVERFLOW-2Typedef int StatusStatus Get(Triple T,int i,Elemtype *e)/ 初始条件：三元组T已经存在，1=i=3./ 操作结果：用e返回三元组T的第i个元素If(i3) return ERROR;*e = Ti-1;Return OK;算法和算法分析算法（Algorithm）:对特定问题求解步骤的一种描述。算法的五个重要特性:1有穷性 2确定性 3可行性 4输入 4输出算法举例气泡排序算法初始条件：N个待排序的数a0an-1结果：排序后a

4、0an-1从小到大排列1 置标记change=TRUE;2 i从n-1知道i=2做（3）- （6）步3 change = FALSE;4 j从0知道j=i-1做（5）5 若ajaj+1则交换他们并置change = TRUE6 若change = FALSE 则结束7 算法结束1 i从n-1知道i=2 做 23 步2 j从0知道j=i-1做 33 若ajaj+1则交换他们4 算法结束Void bb_sort(int a,int n)for(i=n-1;i 1; -i)for(j=0;jaj+1)ajaj+1; / bb_sort算法设计的要求算法应达到的目标1正确性2可读性3健壮性4效率与低存

5、储量算法效率的度量1事后统计法2事前分析估算法算法的 时间复杂度 ；基本操作重复执行次数。它是问题规模n的某个函数f(n);T(n)= O(f(n)平均时间复杂度时间复杂度与输入数据有关时采用平均时间复杂度或最最坏时间复杂度/ 气泡排序时间复杂度只考虑对问题规模的增长率在难以精确计算基本操作执行次数时，仅需要求增长率（或阶）即可。阶：for(i=2;i=n:+i)For(j=2;j=i;+j)+x;ai,j=x;+x的执行次数关于n的增长率时O(n平方)最大的数量阶 n的n次方 n！线性表线性表结构的特点：存在唯一的第一个数据元素存在唯一的最后一个数据元素除第一个外。每个数据元素均有且只有一个

6、前驱元素；除最后一个外。每个数据元素均有且只有一个后继元素。线性表举例；字母表 （A,B,C , X Y Z）数据序列(6.17.28.50)N个元素的线性表（a1.a2,a3.an）第一个元素没有前驱 最后一个元素没有后继 第i个元素有唯一前驱 唯一后继ADT List数据对象：D=ai | ai属于Elemset, (i=1, 2 , n n大于等于0)数据关系 R1= | ai-1,ai属于D。（i= 2.3.n）基本操作：InitList(&L); DestroyList(&L)ListInsert(8L,i,e) ListDelete(&L,i,e);等等 线性表ADT的基本操作；

7、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,conpar

8、e()初始条件：线性表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）（a