数据结构第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;}

}

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 ∧

(7)

【2.5】 【解】

L L

L

L 2 10 P 14 Q 6 R 16 S … 12 4 ∧ ∧ 1 1 3 2 5 3 7 4 ∧ 5 6 7 8 ∧

L 8 ∧ 2 4 6 7

【2.6】 【解】 a. (4)(1)

b. (7)(11)(8)(4)(1) c. (5)(12)

d. (9)(4)(1)或(9)(1)(6)

【2.7】 【解】

a. (11)(3)(14)

b. (10)(12)(8)(11)(3)(14) c. (10)(12)(7)(3)(14) d. (12)(11)(3)(14) e. (9)(11)(3)(14)

【2.8】 【解】

a. (7)(6)(12)(3)或(6)(12)(7)(3)或(6)(7)(12)(3)或(7)(12)(6)(3)或(7)(12)(3)(6)等 b. (8)(5)(13)(4)或(8)(13)(5)(4)或(13)(8)(5)(4)或(5)(8)(13)(4)等 c. (15)(1)(11)(18) d. (16)(2)(10)(18) e. (9)(14)(17)

【2.10】 【解】

Status DeleteK(SqList &a, int i, int k){

//本过程从顺序存储结构的线性表a中删除第i个元素起的k个元素 if (i<1||i>a.length||k<0||k>a.length-i) return INFEASIBLE; for (j=0; j

a.elem[j+i-1]=a.elem[j+k+i-1];

a.length-=k; return OK; }//DeleteK

或一：for循环改变如下，算法其余部分不变。 ……

for (j=i+k; j<=a.length; j++) a.elem[j-k-1]=a.elem[j-1];

……

或二：for循环改变如下，算法其余部分不变。 ……

for (j=i-1; j

……

【2.13】

【解法一】查找算法必须找到待查找结点在内存中的地址，不能仅仅找到位序。 LinkList Locate(Linklist L, ElemType X){

//在单链表L中查找第1个值为X的元素，若找到，则返回它的地址，否则返回空指针。 for (p=L->next; p&&p->data!=X; p=p->next); //循环体为空 return p; }//Locate 【解法二】

Status Locate(Linklist L, ElemType X, LinkList &p){

//在单链表L中查找第1个值为X的元素，则用形参p返回它的地址。 //若找到，返回OK，否则返回ERROR。 p=L->next;

while(p&&p->data!=X)

p=p->next; if (p) return OK; return ERROR; }//Locate

【2.14】 【解法一】

int Length(LinkList L ) { k=0;

for(p=L; p->next; p=p->next) k++; return k; }//Length

【解法二】

int Length(LinkList L ) { k=0;

P=L->next; while(p){ k++;

p=p->next; }

return k; }//Length

【3.1】 【解】

（1）123 231 321 213 132

（2）可以得到135426的出站序列，但不能得到435612的出站序列。因为4356出站说明12已经在栈中，1不可能先于2出栈。135426的出站序列为：SXSSXSSXXXSX。

【3.3】

【解】输出结果：stack

【3.4】 【解】

（1） 栈中的数据元素逆置。

（2） 用栈T作辅助，将栈S中值为e的所有元素删除。

【3.12】

【解】输出结果：char

【3.13】

【解】用栈作辅助，将队列中的数据元素逆置。

本文来源：https://www.bwwdw.com/article/cc2h.html