PPT《*》

Z, v1, v2 )操作结果:构造复数Z,其实部和虚部分别被赋以参数v1和v2的值.DestroyComplex( &

Z)操作结果:复数Z被销毁.GetReal( Z, &

realPart)初始条件:复数已存在.操作结果:用realPart返回复数Z的实部值.GetImag( Z, &

ImagPart)初始条件:复数已存在.操作结果:用ImagPart返回复数Z的虚部值.Add( z1,z2, &

sum )初始条件:z1, z2是复数.操作结果:用sum返回两个复数z

1、z2的和值.} ADT Complex §1.1 基本概念和术语 * 抽象数据类型的表示与实现通过程序设计语言中的类型来实现C抽象数据类型数据对象结构体基本操作函数C++,Java抽象数据类型类class数据对象数据成员基本操作成员函数(方法) §1.1 基本概念和术语 * ADT复数的C描述typedef struct {double realpart;

double imagpart;

}Complex;

boolean assign(Complex *pSrc, Complex *pDes){if (pSrc ==NULL || pDes==NULL ) return ERROR;

pDes->

realpart = pSrc->

realpart;

pDes->

imagpart = pSrc->

imagpart;

return TRUE;

}Complex *add(Complex *pZ1, Complex *pZ2){Complex *pSum = (Complex *)malloc(sizeof(Complex));

if ( pSum==NULL )return NULL;

pSum->

realpart = pZ1->

realpart + pZ2->

realpart;

pSum->

imagpart = pZ1->

imagpart + pZ2->

imagpart;

return pSum;

} * ADT复数的C++描述class Complex{ // 类的声明protected:double realpart;

double magpart;

public:Complex( );

Complex(double realVal,double imagVal);

Complex(Complex&

z){ assign(z) ;

}~Complex( );

void assign(Complex&

z);

double getReal(void) const { return realpart;

}double getImag(void) const { return imagpart;

}friend Complex add(Complex&

z1, Complex&

z2);

};

* // 类的实现部分Complex::Complex(double realVal, double imagVal){realpart = realVal;

imagpart= imagVal;

}void Complex::assign(Complex&

z){realpart = z.realpart;

imagpart= z.imagpart;

}Complex add(Complex&

z1, Complex&

z2){Complex sum(z1);

sum.realpart += z2.realpart;

sum.imagpart += z2.imagpart;

return sum;

} * §1.2 算法描述 分析 算法重要性:数据的运算是通过算法描述的定义:非形式地说,算法是任意一个良定义的计算过程,它以一个或多个值作为输入,并产生一个或多个值作为输出.因此,一个算法就是一系列将输入转换为输出的计算步骤.5要素 输入、输出、有穷性(有穷步骤,每步时间有限) 确定性(算法只有唯一执行路径)、可行性(所有操作可通过已经实现的基本运算有限次实现之)算法与程序的联系与区别 * §1.2 算法描述 分析 输入实例 一个问题的输入实例是由满足问题陈述中的限制、并能计算出该问题解的所有输入构成的. 算法描述 自然语言、数学语言、伪语言、程序语言等均可 本课程以C为主,但不拘泥于细节算法评价 正确性、可读性、健壮性、 时空性能 * 算法分析算法效率的度量事后统计:利用计算机内部的计时功能缺陷必须先运行依据算法编制的程序时间统计量依赖于计算机的软硬件环境double start, stop;

time (&

start);

main process(n, …);

time (&

stop);

double runTime = stop -start;

printf ( %d%d\n , n, runTime );

§1.2 算法描述 分析 * 事前分析估算(时间)求出该算法的一个时间界限函数一些影响因素:?算法的策略?问题的规模?书写程序的语言?编译器产生的机器代码的质量?机器执行指令的速度 §1.2 算法描述 分析 * §1.2 算法描述与分析 算法分析 算法的时间是每语句执行时间的总和 每语句的执行时间=该语句执行次数(频度)X该语句执行1次的时间 假定:每语句执行1次的时间为1个时间单位 则:算法的执行时间=∑各语句频度问题的规模(Size)n 输入量的大小,如…时间复杂度:算法的运行时间,是问题规模的函数 * §1.2 算法描述与分析 时间复杂度 例1:矩阵乘法 for ( i=0;