数据结构第1-3章作业参考答案

数据结构第1～3章作业参考答案

【1.4】

【解法一】⑴ 抽象数据类型复数： ADT Complex{

数据对象：D={ci|ci?R, i=1,2, 其中R为实数集}

数据关系：R={| ci?D, i=1,2, 其中c1为复数实部, c2为复数虚部} 基本操作：

InitComplex (&C,v1,v2)

操作结果：构造一个复数C，元素c1, c2分别被赋以参数v1, v2的值。 DestroyComplex(&C)

初始条件：复数C已存在。 操作结果：销毁复数C。 GetReal(C, &e)

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

操作结果：用e返回复数C实部的值。 GetImaginary(C, &e)

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

操作结果：用e返回复数C虚部的值。 SetReal(&C, e)

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

操作结果：用e更新复数C实部的值。 SetImaginary(&C, e)

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

操作结果：用e更新复数C虚部的值。 AdditionComplex (&C, C1, C2) 初始条件：复数C1，C2已存在。

操作结果：复数C1与复数C2相加，用复数C返回其和。 SubstractComplex(&C, C1, C2) 初始条件：复数C1，C2已存在。

操作结果：复数C1减去复数C2，用复数C返回其差。 MultipleComplex(&C, C1, C2 )

初始条件：复数C1，C2已存在。

操作结果：复数C1与复数C2相乘，用复数C返回其积。 DividedComplex(&C, C1, C2)

初始条件：复数C1，C2已存在，且C2≠0。

操作结果：复数C1除以复数C2，用复数C返回其商。 ModulusComplex(C, &e) 初始条件：复数C已存在。

操作结果：求复数C的模，用e返回。 ConjugateComplex(&C, C1) 初始条件：复数C1已存在。

操作结果：求复数C1的共轭复数，用复数C返回。

}ADT Complex

⑵ 抽象数据类型有理数：

ADT Rational{

数据对象：D={ri|ri?Z, i=1,2, 其中Z为整数集}

数据关系：R1={| ri?D, i=1,2, 且r2?0，其中r1为分子, r2为分母} 基本操作：

InitRational(&R, v1, v2)

初始条件：分母v2不能为0。

操作结果：构造一个有理数R，元素r1, r2分别被赋以参数v1, v2的值。 IrreducibleRational(&R, R1)

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

操作结果：将R1化为最简分数，用有理数R返回。 DestroyRational(&R)

初始条件：有理数R已存在。 操作结果：销毁有理数R。 GetNumerator(R, &e)

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

操作结果：用e返回有理数的分子。 GetDenominator(R, &e)

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

操作结果：用e返回有理数的分母。 SetNumerator(&R, e)

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

操作结果：用e更新有理数的分子。 SetDenominator(&R, e)

初始条件：有理数R已存在，且e≠0。 操作结果：用e更新有理数的分母。 AdditionRational(&R, R1, R2)

初始条件：有理数R1，R2已存在。

操作结果：有理数R1与有理数R2相加，用有理数R返回其和。 SubstractRational(&R, R1, R2)

初始条件：有理数R1，R2已存在。

操作结果：有理数R1减去有理数R2，用有理数R返回其差。 MultipleRational(&R, R1, R2 )

初始条件：有理数R1，R2已存在。

操作结果：有理数R1与有理数R2相乘，用有理数R返回其积。 DividedRational(&R, R1, R2)

初始条件：有理数R1，R2已存在，且R2≠0。

操作结果：有理数R1除以有理数R2，用有理数R返回其商。 AbsoluteRational(R, &R1)

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

操作结果：求有理数R1的绝对值，用有理数R返回。

NegativeRational(&R, R1)

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

操作结果：求有理数R1的相反数，用有理数R返回。 }ADT Rational

【解法二】该解法仅仅是模仿ADT三元组的定义，并没有实际意义。请大家深刻理解解法一。 ⑴ 抽象数据类型复数： ADT Complex{

数据对象：D={ci|ci?R, i=1,2, 其中R为实数集}

数据关系：R={| ci?D, i=1,2, 其中第一元c1为复数实部, 第二元c2为复数虚部} 基本操作：

InitComplex(&C, v1, v2)

操作结果：构造一个复数C，元素c1, c2分别被赋以参数v1, v2的值。 DestroyCmoplex(&C)

初始条件：复数C已存在。 操作结果：销毁复数C。 Get(C, k, &e)

初始条件：复数C已存在，1≦k≦2。

操作结果：用e返回复数C的第k元的值。 Set(&C , k, e)

初始条件：复数C已存在，1≦k≦2。

操作结果：用e更新复数C的第k元的值。 IsAscending(C)

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

操作结果：如果复数C的两个元素按升序排列，则返回1，否则返回0。 IsDescending(C)

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

操作结果：如果复数C的两个元素按降序排列，则返回1，否则返回0。 Max(C, &e)

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

操作结果：用e返回复数C的两个元素中值较大的一个。 Min(C, &e)

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

操作结果：用e返回复数C的两个元素中值较小的一个。 }ADT Complex

⑵ 抽象数据类型有理数：

ADT Rational{

数据对象：D={ri|ri?Z, i=1,2, 其中Z为整数集}

数据关系：R1={| ri?D, i=1,2, 且r2?0，其中r1为分子, r2为分母} 基本操作：

InitRational (&R, v1, v2)

操作结果：构造一个有理数R，元素r1, r2分别被赋以参数v1, v2的值。

DestroyRational (&R)

初始条件：有理数R已存在。 操作结果：销毁有理数R。 Get(R, k, &e)

初始条件：有理数R已存在，1≦k≦2。

操作结果：用e返回有理数R的第k元的值。 Put(&R, k, e)

初始条件：有理数R已存在，1≦k≦2，若k=2，则e≠0。 操作结果：用e更新有理数R的第k元的值。 IsAscending(R)

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

操作结果：若有理数R的两个元素按升序排列，则返回1，否则返回0。 IsDescending(R)

初始条件：有理数R已存在

操作结果：若有理数R的两个元素按降序排列，则返回1，否则返回0。 Max(R, &e)

初始条件：有理数R已存在

操作结果：用e返回有理数R的两个元素中值较大的一个。 Min(R, &e)

初始条件：有理数R已存在

操作结果：用e返回有理数R的两个元素中值较小的一个。 }ADT Rational

【1.9】

【解】令n?2k(k?1)，则循环部分变为：while(x?2k?1){x*?2；count++；}，那么：

当n=4时，循环不执行，此时count=0，T(n)=O(1)； 当n>4时，循环执行k-2次，此时count=log2综合得：count=log2nn?2，T(n)=O(log2n).

?2，T(n)=O(log2n).

【1.16】

【解】两种算法： 算法一如下： void Descending(){

scanf(x, y, z); if(x

temp=x; x=y; y=temp; //使x≧y }

if(y

temp=z; z=y; //使temp>z if(x>=temp) y=temp; else{ y=x; x=temp;}