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

抽象数据类型三元组的定义 ADT Triplet{ 数据对象：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的最小值。 }ADT Triplet 抽象数据类型的表示与实现 类C语言（做了扩充和修改）的表示 如：预定义常量和类型 #define TRUE 1 #define FALSE 0 #define OK 1 #define ERROR 0 #define INFEASIVLE -1 #define OVERFLOW -2 Typedef int Status Status Get(Triple T,int i,Elemtype *e) // 初始条件：三元组T已经存在，1=i=3. // 操作结果：用e返回三元组T的第i个元素 { If(i1 || i3) return ERROR; *e = T[i-1]; Return OK; } 算法和算法分析 算法（Algorithm）:对特定问题求解步骤的一种描述。 算法的五个重要特性: 1有穷性 2确定性 3可行性 4输入 4输出 算法举例————气泡排序算法 初始条件：N个待排序的数a[0]—a[n-1] 结果：排序后a[0]—a[n-1]从小到大排列 1 置标记change=TRUE; 2 i从n-1知道i=2做（3）-- （6）步 3 change = FALSE; 4 j从0知道j=i-1做（5） 5 若a[j]a[j+1]则交换他们并置change = TRUE 6 若change = FALSE 则结束 7 算法结束 i从n-1知道i=2 做 2—3 步 j从0知道j=i-1做 3 若a[j]a[j+1]则交换他们 算法结束 Void bb_sort(int a[],int n){ for(i=n-1;i 1; --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 ,,, X Y Z） 数据序列 (6.17.28.50) N个元素的线性表 （a1.a2,a3...an） 第一个元素没有前驱 最后一个元素没有后继 第i个元素有唯一前驱 唯一后继 ADT List{ 数据对象：D={ai | ai属于Elemset, (i=1, 2 ,,, n n大