数据结构学习习题.pdf

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

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

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

3、例画出其逻辑结构图。解：1.4 试仿照三元组的抽象数据类型分别写出抽象数据类型复数和有理数的定义(有理数是其分子、分母均为自然数且分母不为零的分数)。解：A D T C om p l e x 数据对象：D=r,i|r,i为实数)数据关系：R=基本操作：I n i(C om p l e x(&C,r e,i m)操作结果：构造一个复数C,其实部和虚部分别为r e和i mD e s t r oy C m op l e x(&C)操作结果：销毁复数CG e t (C,k,&e)操作结果：用e返回复数C的第k元的值P u t (&C,k,e)操作结果：改变复数C的第k元的值为eI s A s c e

4、n d i n g(C)操作结果：如果复数C的两个元素按升序排列，则返回1,否则返回0I s D e s c e n d i n g(C)操作结果：如果复数C的两个元素按降序排列，则返回1,否则返回0M a x(C,&e)操作结果：用e返回复数C的两个元素中值较大的一个M i n(C,&e)操作结果：用e返回复数C的两个元素中值较小的一个 A D T C om p l e xA D T R a t i on a l N u m b e r(数据对象：D=s,m|s,m为自然数，且m不为0 数据关系：R=s,m 基本操作：I n i t R a t i on a l N u m b e r (&

5、R,s,m)操作结果：构造一个有理数R,其分子和分母分别为s和mD e s t r oy R a t i on a l N u m b e r(&R)操作结果：销毁有理数RG e t (R,k,&e)操作结果：用e返回有理数R的第k元的值P u t (&R,k,e)操作结果：改变有理数R的第k元的值为eI s A s c e n d i n g(R)操作结果：若有理数R的两个元素按升序排列，则返回1,否则返回0I s D e s c e n d i n g(R)操作结果：若有理数R的两个元素按降序排列，则返回L否则返回0M a x (R,&e)操作结果：用e返回有理数R的两个元素中值较大的一个

6、M i n(R,&e)操作结果：用e返回有理数R的两个元素中值较小的一个)A D T R a t i on a l N u m b e r1.5试画出与下列程序段等价的框图。(1)pr o d u c t=l;i=l;w h i l e (i =n)pr o d u c t *=i;i+；)(2)i=0;d o i+；w h i l e(i !=n)&(a i !=x);(3)s w i t c h c a s e x y:z=y-x;b r e a k;c a s e x=y:z=a b s(x*y);b r e a k;d e f a u l t:(x-y)/a b s(x)*a b s(

7、y);1.6 在程序设计中，常用下列三种不同的出错处理方式：(1)用 e x i t 语句终止执行并报告错误；(2)以函数的返回值区别正确返回或错误返回；(3)设置一个整型变量的函数参数以区别正确返回或某种错误返回。试讨论这三种方法各自的优缺点。解：(D e x i t 常用于异常错误处理，它可以强行中断程序的执行，返回操作系统。(2)以函数的返回值判断正确与否常用于子程序的测试，便于实现程序的局部控制。(3)用整型函数进行错误处理的优点是可以给出错误类型，便于迅速确定错误。1.7 在程序设计中，可采用下列三种方法实现输出和输入：(1)通过s c a n f 和 pr i n t f 语句；(

8、2)通过函数的参数显式传递：(3)通过全局变量隐式传递。试讨论这三种方法的优缺点。解：(1)用 s c a n f 和 pr i n t f 直接进行输入输出的好处是形象、直观，但缺点是需要对其进行格式控制,较为烦琐，如果出现错误，则会引起整个系统的崩溃。(2)通过函数的参数传递进行输入输出，便于实现信息的隐蔽，减少出错的可能。(3)通过全局变量的隐式传递进行输入输出最为方便，只需修改变量的值即可，但过多的全局变量使程序的维护较为困难。1.8 设n为正整数。试确定下列各程序段中前置以记号 的语句的频度：(1)i=l;k=0;w h i l e(i =n-l)k +=1 0*i;i+;)(2)i

9、=l;k=0;d o k +=1 0*i;i+；w h i l e(i =n-l);(3)i=l;k=0;w h i 1 e (i =n-l)i+；k +=1 0*i;)(4)k=0;f o r(i=l;i =n：i+)f o r(j=i;j =n;j+)k+;(5)f o r(i=l;i =n：i+)f o r(j=l;j =i;j+)f o r(k=l;k =j;k+)x +=d e l t a;(6)i=l;j=0;w h i l e(i+j j)j+;e l s e i+;)(7)x=n;y=0;/n是不小于1的常数w h i l e(x =(y+l)*(y+l)y+;)(8)x=9

10、1;y=1 00;w h i l e(y 0)(i f(x 1 00)x -=1 0;y-；e l s e x+;)解：(1)n Tn-1n-1n(n+1)(4)n+(n-l)+(n-2)+1=-21+(1+2)+(1+2+3)+.+(1+2+3+.+n);Zi=2=Q(i+l)=总仔乙/=1 乙i=l 乙/=1 乙/=1=n(n+l)(2 z?+1)+n(z?+1)=n(n+1)(2/?+3)1 2 4 1 2(6)n(7)|_ V n J向下取整(8)1 1 00L 9假设n为2的乘鼎，并且n 2,试求下列算法的时间复杂度及变量c o u n t的值(以n的函数形式表示)。i n t T

11、i m e(i n t n)c o u n t =0;x=2;w h i l e (x 43 8 时，n2 5 0 log2 n1.1 4 判断下列各对函数/()和 g()，当-00时，哪个函数增长更快？(1)f(n)=1 0/?2+ln(!+1 0 )g()=2 n4+7(2)f(n)=(ln(n!)+5)2,g(n)=1 3 n2 5(3)/(n)=n2 A+yin4+1 ,g(n)=(ln(n!)2+n(4)/()=2(+(2),=/解：(l)g(n)快(2)g(n)快(3)f(n)快(4)f(n)快1.1 5 试用数学归纳法证明：(1)=(+1)/6 (n 0)/=i(2)x1=(xM

12、+,-l)/(x-l)(x l,n 0)i=0 2-=2-1 (1)/=1 2 -1)=/n 1)/=11.1 6 试写一算法，自大至小依次输出顺序读入的三个整数X,Y和Z的值解：int max3(int x,int y,int z)(if(x y)if(x z)r e t u r n x;e ls e r e t u r n z;e ls eif(y z)r e t u r n y;e ls e r e t u r n z;)1.1 7 已知k 阶斐波那契序列的定义为f 0 =。，力=0 ,fk-2 =。，fk-=1 ；fn=/.|+/,-2 +/-2 n=k,k+,-试编写求k 阶斐波那契

13、序列的第m 项值的函数算法，k 和m 均以值调用的形式在函数参数表中出现。解：k 0 为阶数，n 为数列的第n 项int Fib onac c i(int k,int n)(if(k l)e xit(O V ER FL O W);int *p,x;p二 ne w int k+1 ;if(!p)e xit(O V ER FL O W);int i,j;f or(i=0;i k+l;i+)if(i k-l)p i=0;e ls e p i=l;)f or(i=k+l;i n+l;i+)x=p 0 :f or(j=0;j k;j+)p j=p j+l;p k=2*p k-l-x;)r e t u r

14、 n p k;1.1 8 假设有A,B,C,D,E 五个高等院校进行田径对抗赛，各院校的单项成绩均已存入计算机，并 构 成 张表，表中每一行的形式为I项 目 名 称 I 性别 I 校名 I 成绩 I 得分 I编写算法，处理上述表格，以统计各院校的男、女总分和团体总分，并输出。解：ty ped ef en u m A,B,C,D,E Scho o l Nam e;ty ped ef en u m Fem al e,Mal e Sex Ty pe;ty ped ef s tr u ctchar ev en t 3;项目Sex Ty pe s ex;Scho o l Nam e s cho o l;

15、in t s co r e;Co m po n en t;ty ped ef s tr u ctin t Mal eSu m;男团总分in t Fem al eSu m;女团总分in t To tal Su m;团体总分 Su m;Su m Su m Sco r e(Scho o l Nam e s n,Co m po n en t a,in t n)(Su m tem p;tem p.Mal eSu m=0;tem p.Fem al eSu m=O;tem p.To tal Su m=0;in t i;fo r(i=0;iar r s iz e或对某个女(1 V k4)，使女!2 人m a

16、x in t时，应按出错处理。注意选择你认为较好的出错处理方法。解：#i n c1 u d e#in cl u d ettd efin e MAXINT 65 5 3 5d efin e Ar r Siz e 1 0 0in t fu n(in t i);in t m ain()in t i,k;in t aAr r Siz e;co u t/En ter k:;cin k;if(k Ar r Siz e-l)ex it(0);fo r(i=0;iMAXINT)ex it(0);el s e ai=2*i*ai-l;)fo r(i=0;iMAXINT)ex it(O);el s e co u

17、t ai*)r etu r n 0;)1.2 0 试编写算法求一元多项式的值e,(x)=z。/的值匕(%)，并确定算法中每一语句的执行次数/=0和整个算法的时间复杂度。注意选择你认为较好的输入和输出方法。本题的输入为%(i =0,1,),x0和，输出为E,(x o)。解：#in cl u d e#in cl u d ed efin e N 1 0d o u bl e po l y n o m ai1(in t a,in t i,d o u bl e x,in t n);in t m ain()(d o u bl e x;in t n,i;in t aN;co u tx;co u tn;if(n

18、 N-l)ex it(0);co u t输入多项式的系数a0 an:；fo r(i=0;iai;co u tz，The po l y n o m ai 1 v al u e is /zpo l y n o m ai 1 (a,n,x,n)0)r etu r n an-i+po l y n o m ail(a,i-l,x,n)*x;el s e r etu r n an;)本算法的时间复杂度为。(n)。第 2章 线 性 表2.1描述以下三个概念的区别：头指针，头结点，首元结点(第一个元素结点)。解：头指针是指向链表中第 个结点的指针。首元结点是指链表中存储第一个数据元素的结点。头结点是在首元结点

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

20、储的时候，用顺序表比用链表好，其特点是可以进行随机存取。2.4 对以下单链表分别执行下列各程序段，并画出结果示意图。L解TIRTQTHpL2.5 画出执行下列各行语句后各指针及链表的示意图。L=(LinkLis t)m allo c(s iz eo f(LNo de);P=L;fo r(i=l;i nex t=(LinkLis t)m allo c(s iz eo f(LNo de);P=P-nex t;P-dat a=i*2-l;)P-nex t=NULL;fo r(i=4;i=l;i-)Ins _LinkLis t(L,i+1,i*2);fo r(i=l;i 3-57pTAL 2 4 6

21、7 8 A丁P2.6 已知L是无表头结点的单链表，且P结点既不是首元结点，也不是尾元结点，试从下列提供的答案中选择合适的语句序列。a.在P结点后插入S结点的语句序列是。b.在P结点前插入S结点的语句序列是。c.在表首插入S结点的语句序列是.d.在表尾插入S结点的语句序列是(1)P-nex t=S;(2)P-nex t=P-nex t-nex t;(3)P-nex t=S-nex t;(4)S-nex t=P-nex t;(5)S-nex t=L;(6)S-nex t=NULL;(7)Q=P;(8)w hile(P-nex t!=Q)P=P-nex t;(9)w hile(P-nex t!=NU

22、LL)P=P-nex t;(1 0)P=Q;(1 1)P=L;(1 2)L=S;(1 3)L=P;解：a.(4)(1)b.(7)(1 1)(8)(4)(1)c.(5)(1 2)d.(9)(1)(6)2.7已知L是带表头结点的非空单链表，且P结点既不是首元结点，也不是尾元结点，试从下列提供的答案中选择合适的语句序列。a.删除P结 点 的 直 接 后 继 结 点 的 语 句 序 列 是.b.删除P结 点 的 直 接 前 驱 结 点 的 语 句 序 列 是。c.删除P结点的语句序列是。d.删除首元结点的语句序列是。e.删除尾元结点的语句序列是。(1)P=P-nex t;(2)P-nex t=P;(3

23、)P-nex t=P-nex t-nex t;(4)P=P-nex t-nex t;(5)w hile(P!=NULL)P=P-nex t;(6)w hile(Q-nex t!=NULL)P=Q;Q=Q-nex t;(7)w hile(P-nex t!=Q)P=P-nex t;(8)w hile(P-nex t-nex t!=Q)P=P-nex t;(9)w hile(P-nex t-nex t!=NULL)P=P-nex t;(1 0)Q=P;(1 1)Q=P-nex t;(P=L;(1 3)L=L-nex t;(1 4)fr ee(Q);解:a.(1 1)(3)(1 4)b.(1 0)(1

24、 2)(8)(3)(1 4)c.(1 0)(1 2)(7)(3)(1 4)d.(1 2)(1 1)(3)(1 4)e.(9)(1 1)(3)(1 4)2.8 已知P 结点是某双向链表的中间结点，试从下列提供的答案中选择合适的语句序列。a.在 P 结点后插入S 结点的语句序列是 ob.在 P 结点前插入S 结点的语句序列是 Oc.删除P 结 点 的 直 接 后 继 结 点 的 语 句 序 列 是。d.删除P 结点的直接前驱结点的语句序列是 oe.删除P 结点的语句序列是。(1)P-nex t=P-nex t-nex t;(2)P-p r io u=P-p r io u-p r io u;(3)P

25、-nex t=S;(4)P-p r io u=S;(5)S-nex t=P;(6)S-p r io u=P;(7)S-nex t=P-nex t;(8)S-p r io u=P-p r io u;(9)P-p r io u-nex t=P-nex t;(1 0)P-p r io u-nex t=P;(1 1)P-nex t-p r io u=P;(1 2)P-nex t-p r io u=S;(1 3)P-p r io u-nex t=S;(1 4)P-nex t-p r io u=P-p r io u;(1 5)Q=P-nex t;(1 6)Q=P-p r io u;(1 7)fr ee(P

26、);(1 8)fr ee(Q);解：a.(7)(3)(6)(1 2)b.(8)(4)(5)(1 3)c.(1 5)(1)(1 1)(1 8)d.(1 6)(2)(1 0)(1 8)e.(1 4)(9)(1 7)2.9 简述以下算法的功能。(1)St at u s A(LinkedLis t L)L是无表头结点的单链表if(L&L-nex t)Q=L;L=L-nex t;P=L;w hile(P-nex t)P=P-nex t;P-nex t=Q;Q-nex t=NULL;)r et u r n OK;)(2)v o id BB(LNo de*s,LNo de*q)p=s;w hile(p-ne

27、x t!=q)p=p-nex t;p-nex t =s;)v o id A A(LNo de*p a,LNo de*p b)/p a和p b分别指向单循环链表中的两个结点BB(p a,p b);BB(p b,p a);解：(1)如果L的长度不小于2,将L的首元结点变成尾元结点。(2)将单循环链表拆成两个单循环链表。2.1 0指出以下算法中的错误和低效之处，并将它改写为一个既1 E确又高效的算法。St at u s D elet eK(Sq Lis t&a,int i,int k)(本过程从顺序存储结构的线性表a中删除第i个元素起的k个元素if(i l!|k a.lengt h)r et u r

28、 n INF E A SIBLE;参数不合法els e fo r(co u nt=l;co u nt =i+l;j-)a.elem j-i=a.elem j;a.lengt h一;)r et u r n OK;)解：St at u s D elet eK(Sq Lis t&a,int i,int k)(/从顺序存储结构的线性表a中删除第i个元素起的k个元素注意i的编号从0开始int j;if(i a.lengt h-1 1 Ik a.lengt h-i)r et u r n INF E A SIBLE;fo r(j=0;j 0,x v a.elem i-l;i-)v a.elem i=v a.

29、e 1 em i-1 ;v a.elem i=x;v a.lengt h+;r et u r n OK;)2.1 2 设A =(%,，4“)和B=(仇，仇J 均为顺序表，A 和B 分别为A和B中除去最大共同前缀后的子表。若A =8=空表，则 A =8；若A =空表，而8 工空表，或者两者均不为空表，且A的首元小于B 的首元，则A B.l en gt h?A.l en gt h:B.l en gt h;fo r(i=0;iB.el em i)j=l;if(A.el em i k)j=l;if(B.l en gt hk)j=-l;if(A.l en gt h=B.l en gt h)j=0;r e

30、t u r n j;)2.1 3 试写一算法在带头结点的单链表结构上实现线性表操作Lo ca l e(L,x);解：in t Lo ca t eEl em _ L(Lin kLis t&L,El em T y p e x)(in t i=0;Lin kLis t p=L;whil e(p&p-da t a!=x)p=p-n ex t;i+；)if(!p)r et u r n 0;el s e r et u r n i;)2.14试写算法在带头结点的单链表结构上实现线性表操作Len gt h(L).解：返回单链表的长度in t Lis t Len gt h_ L(Lin kLis t&L)(in

31、 t i=0;Lin kLis t p=L;if(p)p=p-n ex t;whi l e(p)p=p-n ex t;i+；)r et u r n i;)2.15 已知指针ha 和 hb分别指向两个单链表的头结点，并且已知两个链表的长度分别为m和 n。试写一算法将这两个链表连接在一起，假设指针he指向连接后的链表的头结点，并要求算法以尽可能短的时间完成连接运算。请分析你的算法的时间复杂度。解：v o id Mer geLis t L(Lin kLis t&ha,Lin kLis t&hb,Lin kLis t&hc)(Lin kLis t p a,p b;p a=ha;p b=hb;wh i1

32、e(p a-n ex t&p b-n ex t)p a=p a-n ex t;p b=p b-n ex t;)if(!p a-n ex t)hc=hb;whi1e(p b-n ex t)p b=p b-n ex t;p b-n ex t=ha-n ex t;el s e he=ha;whil e(p a-n ex t)p a=p a-n ex t;p a-n ex t=hb-n ex t;)2.16 已知指针l a 和 l b分别指向两个无头结点单链表中的首元结点。下列算法是从表l a 中删除自第i个元素起共l en 个元素后，将它们插入到表1b中第i个元素之前。试问此算法是否正确？若有错，请

33、改正之。S t a t u s Del et eAn dIn s er t S u b(Lin kedLis t l a,Lin kedLis t l b,in t i,in t j,in t l en)(if(i0i|j0|l en 0)r et u r n INFEAS IBLE;p=l a;k=l;whil e(kn ex t;k+;q=P；whil e(kn ex t;k+;s=l b;k=l;whil e(kn ex t;k+;s-n ex t=p;q-n ex t=s-n ex t;r et u r n OK;)解：S t a t u s Del et eAn dl n s er

34、t S u b(Lin kLis t&l a,Lin kLis t&l b,in t i,in t j,in t l en)Lin kLis t p,q,s,p r ev=NU LL;in t k=l;if(i0|j0|l en 0)r et u r n INFEAS IBLE;/在 l a 表中查找第i 个结点p 二 l a;whil e(p&kn ex t;k+;)if(!p)r et u r n INFEAS IBLE;/在 l a 表中查找第i+l en T 个结点q二 P；k=1;whil e(q&kn ex t;k+;)if(!q)r et u r n INFEAS IBLE;/完

35、成删除，注意，i=l 的情况需要特殊处理if(!p r ev)l a=q-n ex t;el s e p r ev-n ex t=q-n ex t;/将从l a 中删除的结点插入到l b中if(j=l)q-n ex t=l b;l b=p;)el s es=l b;k=l;whil e(s&kn ex t;k+;)if(!s)r et u r n INFEAS IBLE;q-n ex t=s-n ex t;s-n ex t=p;完成插入)r et u r n OK;)2.17试写一算法，在无头结点的动态单链表上实现线性表操作In s er t (L,i,b),并和在带头结点的动态单链表上实现相

36、同操作的算法进行比较。2.18试写一算法，实现线性表操作Del et e(L,i),并和在带头结点的动态单链表上实现相同操作的算法进行比较。2.19已知线性表中的元素以值递增有序排列，并以单链表作存储结构。试写一高效的算法，删除表中所有值大于m in k且小于m a x k的元素(若表中存在这样的元素)，同时释放被删结点空间，并分析你的算法的时间复杂度(注意，m in k和 m a x k是给定的两个参变量，它们的值可以和表中的元素相同，也可以不同)。解：S t a t u s Lis t Del et e_ L(Lin kLis t&L,El em T y p e m in k,El em

37、T y p e m a x k)(Lin kLis t p,q,p r ev=NU LL;if(m in km a x k)r et u r n ERROR;P二 L;p r ev=p;p=p-n ex t;whil e(p&p-da t a da t a n ex t;)el s e p r ev-n ex t=p-n ex t;q二 P；p=p-n ex t;fr ee(q);r et u r n OK;2.2 0 同 2.19题条件，试写高效的算法，删除表中所有值相同的多余元素(使得操作后的线性表中所有元素的值均不相同)，同时释放被删结点空间，并分析你的算法的时间复杂度。解：v o id

38、 Lis t Del et e_ LS a m eNo de(Lin kLis t&L)(Lin kLis t p,q,p r ev;P=L；p r ev=p;p=p-n ex t;whil e(p)p r ev=p;p=p-n ex t;i f(p&p-da t a-p r ev-da t a)p r ev-n ex t=p-n ex t;q二 P；p=p-n ex t;fr ee(q);)2.2 1试写一算法，实现顺序表的就地逆置，即利用原表的存储空间将线性表（内,，。）逆置为I )。解：/顺序表的逆置S t a t u s Lis t Op p o s e_ S q(S qLis t&L

39、)(in t i;El em T y p e x;fo r(i=0;in ex t;L-n ex t=NU LL;whi l e(p)q=P；p=p-n ex t；q-n ex t=L-n ex t;/*L-n ex t存储q前的结点，q是p前的结点，每次执行使L-n ex t=q;P指向前,个结点，初始为N UL L */)return O K;)2.2 3设线性表A =B =(4 也，a)，试写一个按下列规则合并A,B为线性表C的算法，即使得C =(卬 也，,am也 也 出，也)当加 W 时；C =（卬，当加 时。线性表A,B和C均以单链表作存储结构，且C表利用A表和B表中的结点空间构成。

40、注意：单链表的长度值m和n均未显式存储。解：将合并后的结果放在C 表中，并删除B 表S tatus L istM erge_ L(L inkL ist&A,L inkL ist&B,L inkL ist&C)(L inkL ist pa,pb,qa,qb;pa=A-nex t;pb=B-nex t;C=A;while(pa&,pb)qa=pa;qb=pb;pa=pa-nex t;pb=pb-nex t;qb-nex t=qa-nex t;qa-nex t=qb;)if(!pa)qb-nex t=pb;pb=B;free(pb);return O K;)2.2 4 假设有两个按元素值递增有序排列

41、的线性表A和 B,均以单链表作存储结构，请编写算法将A表和B表归并成一个按元素值递减有序(即非递增有序，允许表中含有值相同的元素)排列的线性表C,并要求利用原表(即A 表和B 表)的结点空间构造C表。解：将合并逆置后的结果放在C 表中，并删除B表S tatus L istM ergeO ppose_ L(L inkL ist&A,L inkL ist&B,L inkL ist&C)(L inkL ist pa,pb,qa,qb;pa=A;pb 二 B;qa=pa;/保存pa的前驱指针qb=pb;/保存pb的前驱指针pa=pa-nex t;pb=pb-nex t;A-nex t=N UL L;C

42、=A;while(pa&pb)i f(pa-data data)qa=pa;pa=pa-nex t;qa-nex t=A-nex t;将当前最小结点插入A表表头A-nex t=qa;)elseqb=pb;pb=pb-nex t;qb-nex t=A-nex t;将当前最小结点插入A 表表头A-nex t=qb;)while(pa)qa=pa;pa=pa-nex t;qa-nex t=A-nex t;A-nex t=qa;while(pb)qb二 pb;pb=pb-nex t;qb-nex t=A-nex t;A-nex t=qb;)pb=B;free(pb);return O K;)2.2 5

43、假设以两个元素依值递增有序排列的线性表A和 B分别表示两个集合(即同一表中的元素值各不相同)，现要求另辟空间构成一个线性表C,其元素为A 和 B中元素的交集，且表C中的元素有依值递增有序排列。试对顺序表编写求C的算法。解：/将 A、B 求交后的结果放在C 表中S tatus L istC ross_ S q(S qL ist&A,S qL ist&B,S qL ist&C)(int i=0,j=0,k=0;while(i A.length&j B.length)(if(A.elem i B.elem j)j+;else L istI nsert_ S q(C,k,A.elem i);i+；k+

44、;)return O K;)2.2 6 要求同2.2 5题。试对单链表编写求C的算法。解：/将 A、B 求交后的结果放在C表中，并删除B表S tatus L istC ross L(L inkL ist&A,L inkL ist&B,L inkL ist&C)L inkL ist pa,pb,qa,qb,pt;pa=A;pb 二B;qa=pa;/保存pa的前驱指针qb=pb;/保存pb的前驱指针pa=pa-nex t;pb=pb-nex t;C=A;while(pa&pb)if(pa-data data)pt二pa;pa=pa-nex t;qa-nex t=pa;free(pt);elseif

45、(pa-data pb-data)pt=pb;pb=pb-nex t;qb-nex t=pb;free(pt);)else qa=pa;pa=pa-nex t;)while(pa)pl=pa;pa=pa-nex t;qa-nex t=pa;free(pt);while(pb)pt=pb;pb=pb-nex t;qb-nex t=pb;free(pt);pb 二B;free(pb);return O K;2.2 7对2.2 5题的条件作以下两点修改，对顺序表重新编写求得表C的算法。(1)假设在同一表(A或B)中可能存在值相同的元素，但要求新生成的表C中的元素值各不相同;(2)利用A表空间存放表C

46、。解：(1)/A、B求交，然后删除相同元素，将结果放在C表中S tatus L istC rossD elS ame S q(S qL ist&A,S qL ist&B,S qL ist&C)(int i=0,j=0,k=0;while(i A.length&j B.length)if(A.elem i B.elem j)j+;elseif(C.length=0)L istI nsert_ S q(C,k,A.elem i);k+;)elseif(C.elem C.length-1!=A.elem i)L istinsert S q(C,k,A.elemfi);k+;i+；)return O

47、K;)(2)/A、B求交，然后删除相同元素，将结果放在A表中S tatus L istC rossD elS ame S q(S qL ist&A,S qL ist&B)(int i=0,j=0,k=0;while(i A.length&j B.length)if(A.elem i B.elem j)j+;elseif(k=0)A.elem k=A.elem i;k+;)elseif(A.elem k !=A.elem i)A.elem k=A.elem i;k+;)i+；)A.length=k;return O K;)2.2 8 对 2.2 5题的条件作以卜两点修改，对单链表重新编写求得表C

48、的算法。(1)假设在同一表(A 或 B)中可能存在值相同的元素，但耍求新生成的表C中的元素值各不相同;(2)利用原表(A 表或B 表)中的结点构成表C,并释放A表中的无用结点空间。解：(1)/A、B 求交，结果放在C 表中，并删除相同元素S tatus L istC rossD elS ame_ L(L inkL ist&A,L inkL ist&B,L inkL ist&C)(L inkL ist pa,pb,qa,qb,pt;pa=A;pb 二 B;qa=pa;/保存pa的前驱指针qb=pb;/保存pb的前驱指针pa=pa-nex t;pb=pb-nex t;C=A;while(pa&pb

49、)if(pa-data data)pl=pa;pa=pa-nex t;qa-nex t=pa;free(pt);elseif(pa-data pb-data)pt=pb;pb=pb-nex t;qb-nex t=pb;free(pt);)elseif(pa-data=qa-data)pt=pa;pa=pa-nex t;qa-nex t=pa;free(pt);)else qa=pa;pa=pa-nex t;)while(pa)pt二pa;pa=pa-nex t;qa-nex t=pa;free(pt);)while(pb)pt=pb;pb=pb-nex t;qb-nex t=pb;free(p

50、t);pb=B;free(pb);return O K;)(2)/A、B求交，结果放在A表中，并删除相同元素S tatus L istC rossD elS ame L(L inkL ist&A,L inkL ist&B)(L inkL ist pa,pb,qa,qb,pt;pa=A;pb=B;qa=pa;/保存p a的前驱指针qb=pb;/保存p b的前驱指针pa=pa-nex t;pb=pb-nex t;while(pa&pb)if(pa-data data)pt=pa;pa=pa-nex t;qa-nex t=pa;free(pt);)el seif(pa-data pb-data)pt