2019年数据结构习题集.pdf

《2019年数据结构习题集.pdf》由会员分享，可在线阅读，更多相关《2019年数据结构习题集.pdf（148页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、清华数据结构习题集答案(C语言版严蔚敏)第1章 绪 论1.1简述下列术语：数据，数据元素、数据对象、数据结构、存储结构、数据类型和抽象数据类型。解：数据是对客观事物的符号表示。在计算机科学中是指所有能输入到计算机中并被计算机程序处理的符号的总称。数据元素是数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理。数据对象是性质相同的数据元素的集合，是数据的一个子集。数据结构是相互之间存在一种或多种特定关系的数据元素的集合。存储结构是数据结构在计算机中的表示。数据类型是一个值的集合和定义在这个值集上的一组操作的总称。抽象数据类型是指一个数学模型以及定义在该模型上的一组操作。是对般数据类型的扩

2、展。1.2试描述数据结构和抽象数据类型的概念与程序设计语言中数据类型概念的区别。解：抽象数据类型包含一般数据类型的概念，但含义比一般数据类型更广、更抽象。一般数据类型由具体语言系统内部定义，直接提供给编程者定义用户数据，因此称它们为预定义数据类型。抽象数据类型通常由编程者定义，包括定义它所使用的数据和在这些数据上所进行的操作。在定义抽象数据类型中的数据部分和操作部分时，要求只定义到数据的逻辑结构和操作说明，不考虑数据的存储结构和操作的具体实现，这样抽象层次更高，更能为其他用户提供良好的使用接口。1.3 设有数据结构(D,R),其中试按图论中图的画法惯例画出其逻辑结构图。1.4 试仿照三元组的抽

3、象数据类型分别写出抽象数据类型复数和有理数的定义(有理数是其分子、分母均为自然数且分母不为零的分数)。解：A D T C o m p l e x 数据对象：D=r,i|r,i为实数数据关系：R=r,i 基本操作：I n i tC o m p l e x(&C,r e,i m)操作结果：构造一个复数C,其实部和虚部分别为r e和i mD e s tr o y C m o p 1 e x(&C)操作结果：销毁复数CG e t(C,k,&e)操作结果：用e返回复数C的第k元的值P u t(&C,k,e)操作结果：改变复数C的第k元的值为。I s A s c e n d i n g(C)1操作结果：如

4、果复数C的两个元素按升序排列，则返回1,否则返回0I s D e s c e n d i n g(C)操作结果：如果复数C的两个元素按降序排列，则返回1,否则返回0M a x (C,&e)操作结果：用。返回复数C的两个元素中值较大的一个M i n(C,&e)操作结果：用。返回复数C的两个元素中值较小的一个 A D T C o m p l e xA D T R a ti o n a l N u m b e r 数据对象：D=s,m|s,m为自然数，且m不为0 数据关系：R=)基本操作：Ini tRai ionalN umber(&R,s,m)操作结果：构造一个有理数R,其分子和分母分别为s和mD

5、 estroy RationalN umber(&R)操作结果：销毁有理数RGet(R,k,&e)操作结果：用e返回有理数R的第k元的值P ut(&R,k,e)操作结果：改变有理数R的第k元的值为eIsA scending(R)操作结果：若有理数R的两个元素按升序排列，则返回1,否则返回0IsD escending(R)操作结果：若有理数R的两个元素按降序排列，则返回1,否则返回0M ax (R,&e)操作结果：用。返回有理数R的两个元素中值较大的一个M in(R,&e)操作结果：用e返回有理数R的两个元素中值较小的一个 A D T RationalN umber1.5试画出与下列程序段等价的

6、框图。(1)product=l;i=l;w hile(i=n)product*=i;i+；)(2)i=0;do i+；w hile(i!=n)&(a i!=x);(3)sw itch case x y:z=y-x;break;case x=y:z=abs(x*y);break;default:z=(x-y)/abs(x)*abs(y);21.6在程序设计中，常用下列三种不同的出错处理方式：(1)用 ex it语句终止执行并报告错误；(2)以函数的返回值区别正确返回或错误返回；(3)设置一个整型变量的函数参数以区别正确返回或某种错误返回。试讨论这三种方法各自的优缺点。解：(l)ex it常用于异

7、常错误处理，它可以强行中断程序的执行，返回操作系统。(2)以函数的返回值判断正确与否常用于子程序的测试，便于实现程序的局部控制。(3)用整型函数进行错误处理的优点是可以给出错误类型，便于迅速确定错误。1.7 在程序设计中，可采用下列三种方法实现输出和输入：(1)通过scanf和 printf语句；(2)通过函数的参数显式传递；(3)通过全局变量隐式传递。试讨论这三种方法的优缺点。解：(1)用 scanf和 printf直接进行输入输出的好处是形象、直观，但缺点是需要对其进行格式控制，较为烦琐，如果出现错误，则会引起整个系统的崩溃。(2)通过函数的参数传递进行输入输出，便于实现信息的隐腋，减少出

8、错的可能。(3)通过全局变量的隐式传递进行输入输出最为方便，只需修改变量的值即可，但过多的全局变量使程序的维护较为困难。1.8 设 n 为正整数。试确定下列各程序段中前置以记号 的语句的频度：(1)i=l;k=0;w hile(i=n-l)k+=1 0*i;i+；(2)i=l;k=0;do(0 k+=1 0*i;i+；w hile(i=n-l);(3)i=l;k=0;w hile(i=n-l)i+：k+=1 0*i;(4)k=0;for(i=l;i=n;i+)for(j=i;j=n;j+)0 k+;(5)for(i=l;i=n;i+)for(j=l;j=i;j+)for(k=l;k=j;k+)

9、x +=delta;(6)i=l;j=0;3w hile(i+j j)j+;else i+;)(7)x=n;y=0;/n 是不小于1 的常数w hi le(x =(y+1)*(y+1)y+;)(8)x=91;y=1 0 0;w hile(y 0)if(x 1 0 0)x -=1 0;y 一;else x+;解:)(1)n-1n-l(4)n+(n-l)+(n-2)+.+1=l+(l+2)+(l+2+3)+.+(1+2+3+.+n)n=ya-+-i-)-/,=1 2=挣-1)=/2+T/+*乙/=!乙/=1 乙/=!乙i=-n(n+1)(2n+1)+n(n+1)=+1)(2n+3)(6)n(7)_

10、 V nJ 向下取整(8)1 1 0 01.9 假设n 为 2 的乘黑，并且n 2,试求下列算法的时间复杂度及变量c o u n t 的值(以n的函数形式表示)。i n t Ti m e(i n t n)c o u n t =0;x=2;w h i l e(x n/2)x *=2;c o u n t+;r e t u r n c o u n t;)解：438 时，n2 5 0/7 1 o g2 n1.1 4 判断下列各对函数/()和g()，当8时，哪个函数增长更快？(1)f(n)=1 0?2+l n(n!+l(y ),g(n)=2 n4+7(2)f(n)=(l n(n!)+5)2,g()=13

11、 n2 5(3)f(n)=n2 1+J/+1,g()=(l n(n!)2+n(4)/()=+(2n,g()=+n5解：g(n)快 g(n)快(3)f(n)快(4)f(n)快1.1 5试用数学归纳法证明：(1)+1)(2 +1)/6 (/?0)/=15(2)2=-1)/(X -1)(X W 1,2 0)/=0(3)2,M=2W-1(H1)i=l(4)Z -1)=2 (n 1)i=L 1 6试写一算法，自大至小依次输出顺序读入的三个整数X,Y和Z的值解：i n t m a x 3(i n t x,i n t y,i n t z)i f (x y)i f(x z)r e t u r n x;e l

12、s e r e t u r n z;e l s ei f(y z)r e t u r n y;e l s e r e t u r n z;1.1 7已知k阶斐波那契序列的定义为fo/)=0,fk_2=0,于 1=1；.力=力-1+力-2+/；i，n=k,k +L 试编写求k阶斐波那契序列的第m项值的函数算法，k和m均以值调用的形式在函数参数表中出现。解：k 0为阶数，n为数列的第n项i n t Fi b o n a c c i(i n t k,i n t n)(i f(k l)e x i t(O V ER FL O W);i n t *p,x;p=n e w i n t k+l ;i f(!p

13、)e x i t(O V ER FL O W);i n t i,j;f o r(i=0;i k+l;i+)i f(i k-l)p i =0;e l s e p i =l;f o r(i=k+l;i n+l;i+)x=p 0;f o r(j=0;j k;j+)p j =p j+l ;p k =2*p k-l -x;)r e t u r n p k ;6L 1 8 假设有A,B,C,D,E 五个高等院校进行田径对抗赛，各院校的单项成绩均己存入计算机，并构成一张表，表中每一行的形式为|项 目 名 称|性别|校名|成绩|得分|编写算法，处理上述表格，以统计各院校的男、女总分和团体总分，并输出。解：t

14、y p e d e f e n u m A,B,C,D,E Sc h o o l N a m e;t y p e d e f e n u m Fe m a l e,M a l e S e x T y p e;t y p e d e f s t r u c t c h a r e v e n t 3 ;项目S e x T y p e s e x;S c h o o l N a m e s c h o o l;i n t s c o r e;Co m p o n e n t;t y p e d e f s t r u c t i n t M a l e S u m;男团总分i n t Fe m a

15、 l e S u m;女团总分i n t T o t a l S u m;团体总分 S u m;S u m S u m S c o r e(S c h o o 1 N a m e s n,Co m p o n e n t a ,i n t n)(S u m t e m p;t e m p.M a l e S u m=0;t e m p.Fe m a l e S u m=O;t e m p.T o t a l S u m=0;i n t i;f o r(i=0;i a r r s i z e 或对某个左。人，使m a x i n t 时，应按出错处理。注意选择你认为较好的出错处理方法.解：#i

16、n c l u d e#i n c l u d e d e f i n e M AXIN T 6553 5S d e f i n e Ar r S i z e 100i n t f u n(i n t i);7i n t m a i n()i n t i,k;i n t a Ar r S i z e ;c o u t k;i f(k Ar r S i z e-l)e x i t(0);f o r(i=0;i M AXIN T)e x i t(O);e l s e a i =2*i*a i-l ;)f o r(i=0;i N f AXIN T)e x i t(O);e l s e c o u t

17、 a i ，z ；)r e t u r n 0;)1.20试编写算法求一元多项式的值(x)=Z qx的值乙(%),并确定算法中每一语句的执行次数三0和整个算法的时间复杂度。注意选择你认为较好的输入和输出方法。本 题 的 输 入 为=0,1,)，玉)和 ，输出为?(左0)。解：f t i n c l u d e#i n c l u d e d e f i n e N 10d o u b l e p o l y n o m a i l(i n t a ,i n t i,d o u b l e x,i n t n);i n t m a i n()d o u b l e x;i n t n,i;i n

18、 t a N ;。“”输入变量的值*:；c i n x;c o u t n;i f(n N l)e x i t (0);c o u t 输入多项式的系数a 0 a n :;f o r (i=0;i=n;i+)c i n a i ;8c o u t 0)r e t u r n a n-i +p o l y n o m a i l (a,i-1,x,n)*x;e l s e r e t u r n a n ;)本算法的时间复杂度为。(n)。第2章 线 性 表2.1描述以下三个概念的区别：头指针，头结点，首元结点(第一个元素结点)。解：头指针是指向链表中第一个结点的指针。首元结点是指链表中存储第一个

19、数据元素的结点。头结点是在首元结点之前附设的一个结点，该结点不存储数据元素，其指针域指向首元结点，其作用主要是为了方便对链表的操作。它可以对空表、非空表以及首元结点的操作进行统一处理。2.2填空题。解：(1)在顺序表中插入或删除一个元素，需要平均移动表史二主元素，具体移动的元素个数 与 懑在表中的位置Z关。(2)顺序表中逻辑上相邻的元素的物理位置 逛 紧邻。单链表中逻辑上相邻的元素的物理位的不一定紧邻。(3)在单链表中，除了首元结点外，任一结点的存储位中由其前驱结点的链域的值指 示。(4)在阜臃表中设置次线点的作箱是插入和删除首元结点时不用进行特殊处理.2.3在什么情况下用顺序表比链表好？解：

20、当线性表的数据元素在物理位置上是连续存储的时候，用顺序表比用链表好，其特点是可以进行随机存取。2.4对以下单链表分别执行下列各程序段，并画出结果示意图。92.5 画出执行下列各行语句后各指针及链表的示意图。L=(L i n k L i s t)m a l l o c(s i z e o f(L N o d e);P=L;f o r(i=l;i n e x t=(L i n k L i s t)m a l l o c(s i z e o f(L N o d e);P=P-n e x t;P-d a t a=i*2-l;)P-n e x t=N U L L;f o r(i=4;i=l;i)In s

21、 _ L i n k L i s t(L,i+1,i*2);f o r(i=l;i p1-3-5 7 A丁p2 4 67 8八L-pL 2.6 已知L 是无表头结点的单链表，且 P结点既不是首元结点，也不是尾元结点，试从下列提供的答案中选择合适的语句序列。a.在 P 结点后插入S 结点的语句序列是。b.在 P 结点前插入S 结点的语句序列是10c.在表首插入S结点的语句序列是。d.在表尾插入S 结点的语句序列是.(1)P-n e x t=S;(2)P-n e x t=P-n e x t-n e x t;(3)P-n e x t=S-n e x t;(4)S-n e x t=P-n e x t;

22、(5)S-n e x t=L;(6)S-n e x t=N U L L;(7)Q=P;(8)w h i l e(P-n e x t!=Q)P=P-n e x t;(9)w h i l e(P-n e x t!=N U L L)P=P-n e x t;(10)P=Q;(H)P=L;(L=S;(13)L=P：解：a.(4)(1)b.(7)(11)(8)(4)(1)c.(5)(12)d.(9)(1)(6)2.7 已知L是带表头结点的非空单链表，且 P 结点既不是首元结点，也不是尾元结点，试从下列提供的答案中选择合适的语句序列。a.删除P 结 点 的 直 接 后 继 结 点 的 语 句 序 列 是b.

23、删除P 结 点 的 直 接 前 驱 结 点 的 语 句 序 列 是。c.删除P 结点的语句序列是_ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _。d.删除首元结点的语句序列是 0e.删除尾元结点的语句序列是。(1)P=P-n e x t;(2)P-n e x t=P;(3)P-n e x t=P-n e x t-n e x t;(4)P=P-n e x t-n e x t;(5)w h i l e(P!=N U L L)P=P-n e x t;(6)w h i l e(Q-n e x t!=N U L L)P=Q;Q=Q-n e x t;(7)w h i l e(P-

24、n e x t!=Q)P=P-n e x t;(8)w h i l e(P-n e x t-n e x t!=Q)P=P-n e x t;(9)w h i l e(P-n e x t-n e x t!=N U L L)P=P-n e x t;(10)Q=P;(11)Q=P-n e x t;(12)P=L;(13)L=L-n e x t;(14)f r e e (Q);解：a.(11)(3)(14)b.(10)(12)(8)(3)(14)c.(10)(12)(7)(3)(14)d.(12)(11)(3)(14)e.(9)(11)(3)(14)1 12.8 已知P 结点是某双向链表的中间结点，试从

25、下列提供的答案中选择合适的语句序列。a.在 P结点后插入S 结点的语句序列是 ob.在 P 结点前插入S 结点的语句序列是。c.删除P 结点的直接后继结点的语句序列是 od.删除P 结点的直接前驱结点的语句序列是 Oe.删除P 结点的语句序列是 o(1)P-n e x t=P-n e x t-n e x t;(2)P-p r i o u=P-p r i o u-p r i o u;(3)P-n e x t=S;(4)P-p r i o u=S;(5)S-n e x t=P;(6)S-p r i o u=P;(7)S-n e x t=P-n e x t;(8)S-p r i o u=P-p r

26、i o u;(9)P-p r i o u-n e x t=P-n e x t;(10)P-p r i o u-n e x t=P;(11)P-n e x t-p r i o u=P;(12)P-n e x t-p r i o u=S;(13)P-p r i o u-n e x t=S;(14)P-n e x t-p r i o u=P-p r i o u;(15)Q=P-n e x t;(16)Q=P-p r i o u;(17)f r e e(P);(18)f r e e (Q);解：a.(7)(3)(6)(12)b.(8)(4)(5)(13)c.(15)(1)(11)(18)d.(16)(

27、2)(10)(18)e.(14)(9)(17)2.9 简述以下算法的功能。(1)S t a t u s A(L i n k e d L i s t L)L 是无表头结点的单链表i f(L&L-n e x t)Q=L;L=L-n e x t;P=L;w h i l e(P-n e x t)P=P-n e x t;P-n e x t=Q;Q-n e x t=N U L L;)r e t u r n O K;(2)v o i d B B(L N o d e *s,L N o d e *q)P=s;w h i l e(p-n e x t!=q)p=p-n e x t;p-n e x t =s;)v o

28、 i d A A(L N o d e *p a,L N o d e *p b)/p a 和 p b 分别指向单循环链表中的两个结点12B B(p a,p b);B B(p b,p a);解：(1)如果L的长度不小于2,将L的首元结点变成尾元结点。(2)将单循环链表拆成两个单循环链表。2.1 0指出以下算法中的错误和低效之处，并将它改写为一个既正确又高效的算法。S t a t u s D e l e t e K(S qL i s t&a,i n t i,i n t k)(本过程从顺序存储结构的线性表a中删除第i个元素起的k个元素i f (i l|k a.l e n g t h)r e t u r

29、 n I N F E A S I B L E;参数不合法e l s e f o r (c o u n t=l;c o u n t =i+l;j-)a.e l e m j-i =a.e l e m j ;a.l e n g t h一；)r e t u r n O K;)解：S t a t u s D e l e t e K(S qL i s t&a,i n t i,i n t k)(从顺序存储结构的线性表a中删除第i个元素起的k个元素注意i的编号从0开始i n t j;i f (i a.l e n g t h _ 11|k a.l e n g t h-i)r e t u r n I N F E

30、A S I B L E;f o r(j=0;j 0,x v a.e l e m i-l ;i-)v a.e l e m i =v a.e l e m i-l ;v a.e l e m i =x;v a.l e n g t h+;r e t u r n O K;132.1 2 设 A=(q,和 8 =(4，均为顺序表，A 和 B 分别为A和/3 中除去最大共同前缀后的子表。若 A =8 =空表，则 A =B ；若 A=空表，而 8 *空表，或者两者均不为空表，且A 的首元小于B 的首元，则 A 8。试写一个比较A ,B大小的算法。解：S t a t u s C o m p a r e O r d

31、 e r L i s t (S qL i s t&A,S qL i s t&B)(i n t i,k,j;k=A.l e n g t h B.l e n g t h?A.l e n g t h:B.l e n g t h;f o r(i=0;i B.e l e m i )j=l;i f (A.e l e m i k)j=l;i f(B.l e n g t h k)j=-l;i f(A.l e n g t h=B.l e n g t h)j=0;r e t u r n j;)2.13 试写一算法在带头结点的单链表结构上实现线性表操作L o c a t e d,x);解：i n t L o c a

32、 t e E l e m _ L(L i n k L i s t&L,E l e m T y p e x)(i n t i=0;L i n k L i s t p=L;w h i l e(p&p-d a t a!=x)p=p-n e x t;i+；)i f(!p)r e t u r n 0;e l s e r e t u r n i;2.14 试写一算法在带头结点的单链表结构上实现线性表操作L e n g t h(L)。解：返回单链表的长度i n t L i s t L e n g t h _ L(L i n k L i s t&L)i n t i=0;L i n k L i s t p=L;

33、i f(p)p=p-n e x t;w h i l e(p)p=p-n e x t;i+；)r e t u r n i;142.1 5 己知指针h a和h b分别指向两个单链表的头结点，并且己知两个链表的长度分别为m和n。试写一算法将这两个链表连接在一起，假设指针h e指向连接后的链表的头结点，并要求算法以尽可能短的时间完成连接运算。请分析你的算法的时间复杂度。解：v o i d M e r g e L i s t _ L(L i n k L i s t&h a,L i n k L i s t&h b,L i n k L i s t&h c)L i n k L i s t p a,p b;p

34、a二h a;p b二h b;w h i l e(p a-n e x t&p b-n e x t)p a=p a-n e x t;p b=p b-n e x t;)i f(!p a-n e x t)h e二h b;w h i l e(p b-n e x t)p b=p b-n e x t;p b-n e x t=h a-n e x t;e l s e h e二h a;w h i l e(p a-n e x t)p a=p a-n e x t;p a-n e x t=h b-n e x t;)2.16 已知指针l a和l b分别指向两个无头结点单链表中的首元结点。下列算法是从表3 中删除自第i个元

35、素起共l e n个元素后，将它们插入到表1b中第i个元素之前。试问此算法是否正确？若有错，请改正之。S t a t u s D e l e t e A n d l n s e r t S u b(L i n k e d L i s t l a,L i n k e d L i s t l b,i n t i,i n t j,i n t l e n)(i f(i 0|I j 0|l e n 0)r e t u r n I N F E A S I B L E;p =l a;k=l;w h i l e(k n e x t;k+;q=P；w h i l e(k n e x t;k+;s=l b;k=l;

36、w h i l e(k n e x t;k+;s-n e x t=p;q-n e x t=s-n e x t;r e t u r n O K;)解：S t a t u s D e l e t e A n d l n s e r t S u b(L i n k L i s t&l a,L i n k L i s t&l b,i n t i,i n t j,i n t l e n)L i n k L i s t p,q,s,p r e v=N U L L;i n t k=l;i f(i 0|j 0|l e n 0)r e t u r n I N F E A S I B L E;/在l a表中查找第

37、i个结点15p=l a;w h i l e(p&k n e x t;k+;i f(!p)r e t u r n I N F E A S I B L E;/在l a表中查找第i+l e n-1个结点q二P；k=1;w h i l e (q&.k n e x t;k+;)i f(!q)r e t u r n I N F E A S I B L E;/完成删除，注意，i=1的情况需要特殊处理i f(!p r e v)l a=q-n e x t;e l s e p r e v-n e x t=q-n e x t;/将从l a中删除的结点插入到l b中i f(j=l)q-n e x t=l b;l b=

38、p;)e l s e s=l b;k=l;w h i l e(s&k n e x t;k+;)i f(!s)r e t u r n I N F E A S I B L E;q-n e x t=s-n e x t;s-n e x t=p;完成插入)r e t u r n O K;)2.1 7试写一算法，在无头结点的动态单链表上实现线性表操作I n s e r t (L,i,b),并和在带头结点的动态单链表上实现相同操作的算法进行比较。2.1 8 试写一算法，实现线性表操作D e l e t e d,i),并和在带头结点的动态单链表上实现相同操作的算法进行比较。2.1 9 己知线性表中的元素以值递

39、增有序排列，并以单链表作存储结构。试写一高效的算法，删除表中所有值大于m i n k且小于m a x k的元素(若表中存在这样的元素)，同时释放被删结点空间，并分析你的算法的时间复杂度(注意，m i n k和m a x k是给定的两个参变量，它们的值可以和表中的元素相同，也可以不同)。解：S t a t u s L i s t De le t e _ L(L i n k L i s t&L,E le m T y p e m i n k,E le m T y p e m a x k)L i n k L i s t p,q,p r e v=N U L L;16i f(m i n k m a x k

40、)r e t u r n E R R O R;P=L;p r e v=p;p=p-n e x t;w h i le(p&p-d a t a d a t a n e x t;e ls e p r e v-n e x t=p-n e x t;q=P；p=p-n e x t;f r e e (q);)r e t u r n O K;)2.2 0同2.19题条件，试写一高效的算法，删除表中所有值相同的多余元素(使得操作后的线性表中所有元素的值均不相同)，同时释放被删结点空间，并分析你的算法的时间复杂度。解：v o i d L i s t De le t e _ L S a m e N o d e(L

41、i n k L i s t&L)(L i n k L i s t p,q,p r e v;P二L;p r e v=p;p=p-n e x t;w h i le(p)p r e v=p;p=p-n e x t;i f (p&p-d a t a=p r e v-d a t a)p r e v-n e x t=p-n e x t;q=P；p=p-n e x t;f r e e (q);)2.21试写一算法，实现顺序表的就地逆置，即利用原表的存储空间将线性表(田，,。)逆置为必)。解：顺序表的逆置S t a t u s L i s t O p p o s e _ S q(S q L i s t&L)1

42、7i n t i;E le m T y p e x;f o r(i=0;i n e x t;L-n e x t=N U L L;w h i le(p)q=P；p=p-n e x t;q-n e x t=L-n e x t;L-n e x t=q;)r e t u r n O K;2.23设线性表4 =(卬，。2,M,)，8 =(4也，也)，试写一个按下列规则合并A,B为线性表C的算法，即使得C=QI,4，M%,也)当 n e x t;p b=B-n e x t;C=A;w h i le(p a&p b)18q a=p a;q b=p b;p a=p a-n e x t;p b=p b-n e

43、x t;q b-n e x t=q a-n e x t;q a-n e x t=q b;i f(!p a)q b-n e x t=p b;p b=B;f r e e (p b);r e t u r n O K;)2.2 4假设有两个按元素值递增有序排列的线性表A和B,均以单链表作存储结构，请编写算法将A表和B表归并成一个按元素值递减有序(即非递增有序，允许表中含有值相同的元素)排列的线性表C,并要求利用原表(即A表和B表)的结点空间构造C表。解：/将合并逆置后的结果放在C表中，并删除B表S t a t u s L i s t M e r g e O p p o s e _ L(L i n k

44、L i s t&A,L i n k L i s t&B,L i n k L i s t&C)(L i n k L i s t p a,p b,q a,q b;p a二 A;p b=B;q a=p a ；/保存p a的前驱指针q b=p b;/保存p b的前驱指针p a=p a-n e x t;p b=p b-n e x t;A-n e x t=N U L L;C=A;w h i le (p a&p b)i f (p a-d a t a d a t a)q a=p a;p a=p a-n e x t;q a-n e x t=A-n e x t;将当前最小结点插入A表表头A-n e x t=q a

45、;)e ls e q b=p b;p b=p b-n e x t;q b-n e x t=A-n e x t:将当前最小结点插入A表表头A-n e x t=q b;)w h i le(p a)q a=p a;p a=p a-n e x t;q a-n e x t=A-n e x t;A-n e x t=q a;19)w h i le (p b)q b=p b;p b=p b-n e x t;q b-n e x t=A-n e x t;A-n e x t=q b;)p b二B;f r e e(p b);r e t u r n O K;)2.2 5假设以两个元素依值递增有序排列的线性表A和B分别表

46、示两个集合(即同一表中的元素值各不相同)，现要求另辟空间构成一个线性表C,其元素为A和B中元素的交集，且表C中的元素有依值递增有序排列。试对顺序表编写求C的算法。解：/将A、B求交后的结果放在C表中S t a t u s L i s t Cr o s s _ S q(S q L i s t&A,S q L i s t&B,S q L i s t&C)(i n t i=0,j=0,k=0;w h i le(i A.le n g t h&j B.le n g t h)i f (A.e le m i B.e le m j )j+;e ls e (L i s t!n s e r t _ S q(C,k

47、,A.e le m i );i+；k+;)r e t u r n O K;)2.2 6要求同2.25题。试对单链表编写求C的算法。解：/将A、B求交后的结果放在C表中，并删除B表S t a t u s L i s t Cr o s s _ L(L i n k L i s t&A,L i n k L i s t&B,L i n k L i s t&C)L i n k L i s t p a,p b,q a,q b,p t;p a=A;p b二B;q a=p a;/保存p a的前驱指针q b=p b;/保存p b的前驱指针p a=p a-n e x t;p b=p b-n e x t;C=A;w

48、h i le(p a&p b)20i f(p a-d a t a d a t a)p t=p a;p a=p a-n e x t;q a-n e x t=p a;f r e e(p t);e ls ei f(p a-d a t a p b-d a t a)p t=p b;p b=p b-n e x t;q b-n e x t=p b;f r e e (p t);)e ls e q a=p a;p a=p a-n e x t;)w h i le(p a)p t二p a;p a=p a-n e x t;q a-n e x t=p a;f r e e (p t);)w h i le (p b)p t

49、=p b;p b=p b-n e x t;q b-n e x t=p b;f r e e(p t);)p b=B;f r e e(p b);r e t u r n O K;)2.2 7对2.25题的条件作以下两点修改，对顺序表重新编写求得表C的算法。(1)假设在同一表(A或B)中可能存在值相同的元素，但要求新生成的表C中的元素值各不相同(2)利用A表空间存放表C。解：(1)/A、B求交，然后删除相同元素，将结果放在C表中S t a t u s L i s t Cr o s s De lS a m e _ S q(S q L i s t&A,S q L i s t&B,S q L i s t&C

50、)i n t i=0,j=0,k=0;w h i le(i A.le n g t h&j B.le n g t h)i f (A.e le m i B.e le m j )j+;e ls e i f (C.le n g t h=二0)L i s t i n s e r t S q(C,k,A.e le m i );k+;)e ls ei f (C.e le m C.le n g t h-1 !=A.e le m i )L i s 11n s e r t _ S q(C,k,A.e le m i );k+;i+；)r e t u r n O K;)(2)/A、B求交，然后删除相同元素，将结果放在