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

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

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个元素。

— 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 FALSE0

#define OK1

#define ERROR0

#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(i<1 || i>3) 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;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个

满意答案

hweiwei420

2015.10.10

采纳率：50%    等级：13

已帮助：14203人

a.

抽象数据类型复数complex：

ADT complex{

数据对象：D={e1,e2|e1,e2∈R}

数据关系：R1={}

基本操作：

Initcomplex(&T,v1,v2)

操作结果：构造了复数T,元素e1,e2分别被赋以参数v1,v2的值.

Destroycomplex(&T)

初始条件：复数T已存在.

操作结果：复数T被销毁.

Get(T,i,&e)

初始条件：复数T已存在，1≤i≤2.

操作结果：用e返回T的实部或虚部的值。

Isascending(T)

初始条件：复数T已存在。

操作结果：两部分按升序排列，则返回1，否则返回0.

Isdescending(T)

初始条件：复数T已存在。

操作结果：两部分按降序排列，则返回1，否则返回0.

Put(&T,I,e)

初始条件：复数T已存在, 1≤i≤2.

操作结果：改变T实部或虚部的值为e.

Max(T,&e)

初始条件：复数T已存在。

操作结果：用e返回实部，虚部中较大的值。

Min(T,&e)

初始条件：复数T已存在

操作结果：用e返回实部，虚部中较小的值。

}ADT complex

b. 抽象数据类型有理数：

ADT rational{

数据对象：D={a,b|a,b为整数，且b不为0}

数据关系：R={}

基本操作：

Initrational(&T,v1,v2)

操作结果：构造有理数T,元素啊，a,b分别被赋以参数v1,v2的值。

Destroyrational(&T)

初始条件：有理数T已存在。

操作结果：有理数T被销毁。

Get(T,i,&e)

初始条件：有理数T已存在，1≤i≤2.

操作结果：用e返回T的分子或分母的值。

Put(&T,i,e)

初始条件：有理数T已存在，1≤i≤2.

操作结果：改变T的分子或分母的值为e.

Isascending(T)

初始条件：复数T已存在。

操作结果：两部分按升序排列，则返回1，否则返回0.

Isdescending(T)

初始条件：复数T已存在。

操作结果：两部分按降序排列，则返回1，否则返回0.

Max(T,&e)

初始条件：有理数T已存在。

操作结果：用e返回分子，母中较大一个的值。

Min(T,&e)

初始条件：有理数T已存在。

操作结果：用e返回分子，分母中较小的一个。

}ADT rational

00分享举报