数据结构第1～3章作业参考答案
【1.4】
【解法一】⑴ 抽象数据类型复数： ADT Complex{
数据对象：D={ci|ci?R, i=1,2, 其中R为实数集}
数据关系：R={
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={
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={
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={
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;} } printf(x, y, z); }//Descending 算法二如下：(此算法是冒泡排序算法) void Descending(){ scanf(x, y, z); if(x if(x x?y ; //如果x printf(x, y, z); }//Descending 【2.1】 【解】头指针是指向链表中第一个结点的指针。首元结点是指链表中存储第一个数据元素的结点。 头结点是在首元结点之前附设的一个结点，该结点不存储数据元素，其指针域指向首元结点，其作用主要是为了方便对链表的操作。它可以对空表、非空表以及首元结点的操作进行统一处理。 【2.2】 【解】(1) 表中一半，表长和该元素在表中的位置。 (2) 必定，不一定。 (3) 其直接前驱结点的链域的值。 (4) 插入和删除首元结点时不必进行特殊处理。 【2.4】 【解】 … L 6 4 ∧ 2 5 7 3 8 (1) (2) (3) (4) (5) (6) P Q P S L 7 Q 3 R 8 S … 6 4 ∧ L 2 5 P 7 Q 5 R 8 S … 6 4 ∧ L 2 5 P 7 Q 7 R 8 S … 6 4 ∧ L 2 5 P 7 Q 3 R 5 … 6 4 ∧ L 2 10 P 14 Q 6 R 16 … 12 8 ∧ 搜索“diyifanwen.net”或“第一范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，第一范文网，提供最新初中教育数据结构第1-3章作业参考答案 全文阅读和word下载服务。
相关推荐：
薄荷少年