《清华大学课程讲义-数据结构答案1.doc》由会员分享，可在线阅读，更多相关《清华大学课程讲义-数据结构答案1.doc（4页珍藏版）》请在金锄头文库上搜索。
1、1-4什么是抽象数据类型？试用C+的类声明定义“复数”的抽象数据类型。要求(1) 在复数内部用浮点数定义它的实部和虚部。(2) 实现3个构造函数：缺省的构造函数没有参数；第二个构造函数将双精度浮点数赋给复数的实部，虚部置为0；第三个构造函数将两个双精度浮点数分别赋给复数的实部和虚部。(3) 定义获取和修改复数的实部和虚部，以及+、-、*、/等运算的成员函数。(4) 定义重载的流函数来输出一个复数。【解答】抽象数据类型通常是指由用户定义，用以表示应用问题的数据模型。抽象数据类型由基本的数据类型构成，并包括一组相关的服务。/在头文件complex.h中定义的复数类#ifndef _complex_
2、h_#define _complex_h_#include class comlex public: complex ( ) Re = Im = 0; /不带参数的构造函数 complex ( double r ) Re = r; Im = 0; /只置实部的构造函数 complex ( double r, double i ) Re = r; Im = i; /分别置实部、虚部的构造函数 double getReal ( ) return Re; /取复数实部 double getImag ( ) return Im; /取复数虚部 void setReal ( double r ) Re
3、= r; /修改复数实部 void setImag ( double i ) Im = i; /修改复数虚部 complex& operator = ( complex& ob) Re = ob.Re; Im = ob.Im; /复数赋值 complex& operator + ( complex& ob );/重载函数：复数四则运算 complex& operator ( complex& ob ); complex& operator * ( complex& ob ); complex& operator / ( complex& ob ); friend ostream& operat
4、or ( ostream& os, complex& c );/友元函数：重载private: double Re, Im;/复数的实部与虚部;#endif /复数类complex的相关服务的实现放在C+源文件complex.cpp中#include #include #include “complex.h”complex& complex : operator + ( complex & ob ) /重载函数：复数加法运算。complex * result = new complex ( Re + ob.Re, Im + ob.Im );return *result; complex& co
5、mplex : operator ( complex& ob ) /重载函数：复数减法运算 complex * result = new complex ( Re ob.Re, Im ob.Im );return * result;complex& complex : operator * ( complex& ob ) /重载函数：复数乘法运算complex * result = new complex ( Re * ob.Re Im * ob.Im, Im * ob.Re + Re * ob.Im );return *result;complex& complex : operator /
6、 ( complex& ) /重载函数：复数除法运算double d = ob.Re * ob.Re + ob.Im * ob.Im;complex * result = new complex ( ( Re * ob.Re + Im * ob.Im ) / d,( Im * ob. Re Re * ob.Im ) / d );return * result;friend ostream& operator ( ostream& os, complex & ob ) /友元函数：重载，将复数ob输出到输出流对象os中。 return os ob.Re = 0.0 ) ? “+” : “-” f
7、abs ( ob.Im ) arraySize或者对于某一个k (0 k n)，使得k!*2k maxInt时，应按出错处理。可有如下三种不同的出错处理方式：(1) 用cerr及exit (1)语句来终止执行并报告错误；(2) 用返回整数函数值0, 1来实现算法，以区别是正常返回还是错误返回；(3) 在函数的参数表设置一个引用型的整型变量来区别是正常返回还是某种错误返回。试讨论这三种方法各自的优缺点，并以你认为是最好的方式实现它。【解答】#include iostream.h#define arraySize 100#define MaxInt 0x7fffffffint calc ( int
8、 T , int n ) int i, value = 1;if ( n != 0 ) int edge = MaxInt / n / 2;for ( i = 1; i edge ) return 0;value *= n * 2;Tn = value;cout A n = Tn endl;return 1;void main ( ) int AarraySize;int i;for ( i = 0; i arraySize; i+ )if ( !calc ( A, i ) ) cout failed at i . endl;break;1-9 (1) 在下面所给函数的适当地方插入计算coun
9、t的语句：void d (ArrayElement x , int n ) int i = 1; do xi += 2; i +=2; while (i = n ); i = 1; while ( i = (n/2) ) xi += xi+1; i+; (2) 将由(1)所得到的程序化简。使得化简后的程序与化简前的程序具有相同的count值。(3) 程序执行结束时的count值是多少？(4) 使用执行频度的方法计算这个程序的程序步数，画出程序步数统计表。 【解答】(1) 在适当的地方插入计算count语句void d ( ArrayElement x , int n ) int i = 1;
10、count +; do xi += 2; count +;i += 2; count +; count +;/针对while语句 while ( i = n ); i = 1; count +; while ( i = ( n / 2 ) ) count +;/针对while语句xi += xi+1;count +;i +;count +; count +;/针对最后一次while语句(2) 将由(1)所得到的程序化简。化简后的程序与原来的程序有相同的count值：void d ( ArrayElement x , int n ) int i = 1;do count += 3; i += 2
11、; while ( i = n ); i = 1;while ( i = ( n / 2 ) ) count += 3; i +; count += 3;(3) 程序执行结束后的count值为 3n + 3。当n为偶数时，count = 3 * ( n / 2 ) + 3 * ( n / 2 ) + 3 = 3 * n + 3当n为奇数时，count = 3 * ( ( n + 1 ) / 2 ) + 3 * ( ( n 1 ) / 2 ) + 3 = 3 * n + 3(4) 使用执行频度的方法计算程序的执行步数，画出程序步数统计表：行 号 程 序 语 句一次执行步数执行频度程序步数 1 2 3 4 5 6 7 8 9 10 11 12void d ( ArrayElement x , int n ) int i = 1; do xi += 2;i += 2; while ( i = n ); i = 1; while ( i = ( n / 2 ) ) xi += xi+1; i +; 0 1 0 1 1 1 1 1 1 1 0 011 (n+1)/2 (n+1)/2 (n+1)/2 (n+1)/21 n/2+1 n/2 n/2 n/2 101 0 (n+1)/2 (n+1)/2 (n+1)/21 n/2+1 n/2 n/2 0 0 ( n 0 ) 3n + 3
