数据结构习题集答案(C语言版严蔚敏).pdf

《数据结构习题集答案(C语言版严蔚敏).pdf》由会员分享，可在线阅读，更多相关《数据结构习题集答案(C语言版严蔚敏).pdf（236页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

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

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

3、据类型复数和有理数的定义(有理数是其分子、分母均为自然数且分母不为零的分数)解：A D T C o m p l e x 数据对象：D=ri|ri为实数数据关系：R=基本操作：I n i tR a ti o n a l N um b e r(&Rsm)操作结果：构造一个有理数R其分子和分母分别为s 和 mD e stro yR a ti o n a l N um b e r(&R)操作结果：销毁有理数RGe t(Rk&e)操作结果：用 e返回有理数R的第k元的值P ut(&Rke)操作结果：改变有理数R的第k元的值为eI sAsce n di n g(R)操作结果：若有理数R的两个元素按升序排列

4、则返回1否则返回0I sD e sce n di n g(R)操作结果：若有理数R的两个元素按降序排列则返回1否则返回0M a x(R&e)操作结果：用 e返回有理数R的两个元素中值较大的一个M i n(R&e)操作结果：用 e返回有理数R的两个元素中值较小的一个 AD T R a ti o n a l N um b e r1.5试画出与下列程序段等价的框图(1)pro duct=l;i=l;wh i l e(i=n)pro duct*=i;i+；(2)i=0;do i+；wh i l e(i!=n)&(a i !=x);(3)swi tch ca se xy:z=y-x;b re a k;c

5、a se x=y:z=a b s(x*y);b re a k;de f a ul t:z=(x-y)/a b s(x)*a b s(y);)1.6在程序设计中常用下列三种不同的出错处理方式：(1)用 e xi t语句终止执行并报告错误；(2)以函数的返回值区别正确返回或错误返回；(3)设置一个整型变量的函数参数以区别正确返回或某种错误返回试讨论这三种方法各自的优缺点解：(l)e xi t常用于异常错误处理它可以强行中断程序的执行返回操作系统(2)以函数的返回值判断正确与否常用于子程序的测试便于实现程序的局部控制(3)用整型函数进行错误处理的优点是可以给出错误类型便于迅速确定错误1.7 在程序设

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

7、=n-l)k +=10*i;i+；)(2)i=l;k=0;do k +=10*i;i+；wh i l e(i=n-l);(3)i=l;k=0;wh i l e (i=n-l)i+；k +=10*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+=de l ta;)(6)i=l;j=0;wh i l e(i+j j)j+;e l se i+;x=n;y=0;/n 是不小于 1 的常数 wh i l e(x=(y+l)*(y+l)y+;(8)x=

8、91;y=100;wh i l e(y 0)i f(x 100)x-=10;y-;e l se x+;)解：n-1n-1n-1(4)n+(n-l)+(n-2)+.+1二(5)1+(1+2)+(1+2+3)+.+(1+2+3+.+n)=(6)n(7)向下取整(8)1 1 0 0L 9假设n为2的乘幕并且n 2试求下列算法的时间复杂度及变量c o u n t的 值(以n的函数形式表示)i n t T i m e(i n t n)c o u n t =0;x=2;w h i l e(x 4 3 8时1.1 4 判断下列各对函数和当时哪个函数增长更快？(1)(2)(3)(4)解：(l)g(n)快 g(

9、n)快 f(n)快(4)f(n)快1.1 5 试用数学归纳法证明：(1)(2)1.1 6 试写一算法自大至小依次输出顺序读入的三个整数XY和 Z的值解：i n t m a x 3(i n t x i n t yi n t z)(i f(x y)i f(x z)r e t u r n x;e l 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.17 已知k阶斐波那契序列的定义为试编写求k阶斐波那契序列的第m项值的函数算法k和 m均以值调用的形式在函数参数表中出现解：k 0为阶数n为数列的第n项i n

10、t F i b o n a c c i(i n t ki n t n)i f(k l)e x i t(O V E R F L O W);i n t *px;p=n e w i n t k+1 ;i f(!p)e x i t(O V E R F L O W);i n t iJ；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+U;p k =2*p k-l -x;)r e t u r n p k ;1.1 8假设有ABCDE五个高等院校进

11、行田径对抗赛各院校的单项成绩均已存入计算机 并构成一张表表中每一行的形式为项目名称性别校名成绩得分编写算法处理上述表格以统计各院校的男、女总分和团体总分并输出解：t y p edef en u m ABCDE Scho o lNam e;t y p edef en u m Fem aleMale Sex Ty p e;t y p edef s t ru ct char even t 3;项目 Sex Ty p e s ex;Scho o lNam e s cho o l;in t s co re;Co m p o n en t;t y p edef s t ru ct in t MaleSu

12、m;/男团总分 in t Fem aleSu m;女团总分 in t To t alSu m;/团体总分Su m;Su m Su m Sco re(Scho o lNam e s n Co m p o n en t ain t n)(Su m t em p;t em p.MaleSu m=0;t em p.Fem aleSu m=O;t em p.To t alSu m=0;in t i;fo r(i=0;iarrs iz e或对某个使时应按出错处理注意选择你认为较好的出错处理方法解：#in c1 u de#in clu de#defin e MAXINT 6 5 5 3 5#defin e

13、ArrSiz e 1 0 0in t fu n(in t i);in t m ain ()(in t ik;in t aArrSiz e;co u t z zEn t er k:；cin k;if(kArrSiz e-l)ex it (0);fo r(i=0;iMAXINT)ex it(0);els e ai=2*i*ai-l;fo r(i=0;iMAXINT)ex it(O);els e co u t ai z/；)ret u rn 0;)1.2 0 试编写算法求一元多项式的值的值并确定算法中每一语句的执行次数和整个算法的时间复杂度 注意选择你认为较好的输入和输出方法本题的输入为和输出为解：

14、#in clu de#in clu deSdefin e N 1 0do u ble p o ly n o m ail(in t ain t ido u ble xin t n);in t m ain()do u ble x;in t ni；in t aN;co u t 6输入变量的值X:；cin x;c o u t 输入多项式的阶次n :；cin n;if(n N-l)ex it(0);co u t 输入多项式的系数a0-an:；fo r(i=0;i=n;i+)cin ai;c o u t，zThe p o ly n o m ail valu e is z，p o ly n o m ail(

15、a nxn)0)ret u rn an-i+p o ly n o m ail(ai-1xn)*x;els e ret u rn an;木算法的时间复杂度为o(n)第 2章线性表2.1 描述以下三个概念的区别：头指针头结点首元结点(第一个元素结点)解：头指针是指向链表中第个结点的指针首元结点是指链表中存储第 个数据元素的结点头结点是在首元结点之前附设的一个结点该结点不存储数据元素其指针域指向首元结点其作用主要是为了方便对链表的操作它可以对空表、非空表以及首元结点的操作进行统一处理2.2填空题解：(1)在顺序表中插入或删除一个元素需要平均移动表中一半元素具体移动的元素个数与元素在表中的位置有关(2

16、)顺序表中逻辑上相邻的元素的物理位置必定紧邻单链表中逻辑上相邻的元素的物理位置不一定紧邻(3)在单链表中除了首元结点外任一结点的存储位置由其前驱结点的链域的值指示(4)在单链表中设置头结点的作用是插入和删除首元结点时不用进行特殊处理2.3 在什么情况下用顺序表比链表好？解：当线性表的数据元素在物理位置上是连续存储的时候用顺序表比用链表好其特点是可以进行随机存取2.4对以下单链表分别执行下列各程序段并画出结果示意图解：2.5画出执行下列各行语句后各指针及链表的示意图L=(Lin k Lis t)m allo c(s iz eo f(LNo de);P=L;fo r(i=l;i n ex t=(L

17、in k Lis t)m allo c(s iz eo f(LNo de);P=P-n ex t;P-dat a=i*2 T;)P-n ex t=NULL;fo r(i=4;i=l;i-)In s Lin k Lis t(Li+1i*2);fo r(i=l;i=3;i+)D el_Lin k Lis t(Li)；解：2.6 已知L 是无表头结点的单链表且 P 结点既不是首元结点也不是尾元结点试从下列提供的答案中选择合适的语句序列a.在 P 结点后插入S 结点的语句序列是b.在 P 结点前插入S 结点的语句序列是c.在表首插入S 结点的语句序列是d.在表尾插入S 结点的语句序列是(1)P-n e

18、x t=S;(2)P-n ex t=P-n ex t-n ex t;(3)P-n ex t=S-n ex t;(4)S-n ex t=P-n ex t;(5)S-n ex t=L;(6)S-n ex t=NULL;Q=P；(8)w hile(P-n ex t!=Q)P=P-n ex t;(9)w hile(P-n ex t!=NULL)P=P-n ex 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 结点既不是首元结点也

19、不是尾元结点试从下列提供的答案中选择合适的语句序列a.删 除 P 结点的直接后继结点的语句序列是一b.删除P 结点的直接前驱结点的语句序列是c.删除P 结点的语句序列是d.删除首元结点的语句序列是e.删除尾元结点的语句序列是(1)P=P-next;(2)P-next=P;(3)P-next=P-next-next;(4)P=P-next-next;(5)while(P!=NULL)P=P-next;(6)while(Q-next!=NULL)P=Q;Q=Q-next;(7)while(P-next!=Q)P=P-next;(8)while(P-next-next!=Q)P=P-next;(9)

20、while(P-next-next!=NULL)P=P-next;(10)Q=P;(11)Q=P-next;(12)P=L;(13)L=L-next;(14)free(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)2.8 已知P 结点是某双向链表的中间结点试从卜列提供的答案中选择合适的语句序列a.在 P 结点后插入S 结点的语句序列是b.在 P 结点前插入S 结点的语句序列是c.删除P 结点的直接后继结点的语句序列是d.删除P 结点的直接前驱结点的语句序列是e

21、.删除P 结点的语句序列是(1)P-next=P-next-next;(2)P-priou=P-priou-priou;(3)P-next=S;(4)P-priou=S;(5)S-next=P;(6)S-priou=P;(7)S-next=P-next;(8)S-priou=P-priou;(9)P-priou-next=P-next;(10)P-priou-next=P;(11)P-next-priou=P;(12)P-next-priou=S;(13)P-priou-next=S;(14)P-next-priou=P-priou;(1 5)Q=P-n ex t;(1 6)Q=P-p r i

22、o u;(1 7)fr ee(P);(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(Lin k edLis t L)L是无表头结点的单链表if(L&L-n ex t)Q=L;L=L-n ex t;P=L;w hile(P-n ex t)P=P-n ex t;P-n ex t=Q;Q-n ex t=NULL;)r et u r n OK;)(2)v o id B B(LNo de*sL

23、No de*q)P=s;w hile(p-n ex t!=q)p=p-n ex t;p-n ex t =s;v o id A A(LNo de*p aLNo de*p b)/p a和p b分别指向单循环链表中的两个结点B B(p ap b);B B(p bp a);)解：(1)如果L的长度不小于2将L的首元结点变成尾元结点(2)将单循环链表拆成两个单循环链表2.10指出以下算法中的错误和低效之处并将它改写为一个既正确又高效的算法St at u s D elet eK(Sq Lis t&ain t iin t k)(本过程从顺序存储结构的线性表a中删除第i个元素起的k个元素if(i l|k a.

24、len g t h)r et u r n INFE A SIB LE;参数不合法 els e fo r(co u n t=l;co u n t =i+l；j-)a.elem j-i=a.elem j;a.len g t h;r et u r n OK;解:St at u s D elet eK(Sq Lis t&ain t iin t k)(从顺序存储结构的线性表a 中删除第i 个元素起的k个 元 素 注 意 i 的编号从0开始in t j;if(i a.len g t h-1 1|k a.len g t h-i)r et u r n INFE A SIB LE;fo r(j=0;j 0 x

25、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试写一算法在带头结点的单链表结构上实现线性表操作Lo c a t e (L x);解：i n t Lo c a t e E l e m L(Li n k Li s t&LE l e m T y p e x)(i n t i=0;Li n k Li s

26、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.1 4 试写一算法在带头结点的单链表结构上实现线性表操作Le n g t h (D解：返回单链表的长度i n t Li s t Le n g t h _ L(Li n k Li s t&L)(i n t i=0;Li n k Li s t p=L;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;2.1 5 已知指针h a 和 h b 分别指向

27、两个单链表的头结点并且已知两个链表的长度分别为m和 n试写一算法将这两个链表连接在一起假设指针h e 指向连接后的链表的头结点并要求算法以尽可能短的时间完成连接运算请分析你的算法的时间复杂度解：v o i d Me r g e Li s t _ L(Li n k Li s t&h aLi n k Li s t&h bLi n k Li s t&h c)Li n k Li s t p ap b;p 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

28、c=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 c=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.1 6已知指针l a 和 l b 分别指向两个无头结点单链表中的首元结点下列算法是从表l a中删除自第i 个元素起共l e n 个元素后将它们插入到表1b 中 第 i 个元素之前试问此算法是否正确？若有错请改正之Status DeleteAndlnsertSub(LinkedList laLinke

29、dList lbint iint jint len)(if(i0|j0|len0)return INFEASIBLE;p=la;k=l;while(knext;k+;q=p;while(knext;k+;s=lb;k=l;while(knext;k+;s-next=p;q-next=s-next;return OK;)解：Status DeleteAndlnsertSub(LinkList&la LinkList&lbint iint jint len)(LinkList pqsp r e v=NU LL;i n t k=l;i f(i 0|j 0|l e n 0)r e t u r n IN

30、F E A S IB LE;/在 l a 表中查找第 i 个结点p=l a;w h i l e(p&k n e x t;k+;i f(!p)r e t u r n INF E A S IB LE：/在 l a 表中查找第i+l e n-1个 结 点 q=p;k=l;w h i l e(q&k n e x t;k+;)i f(!q)r e t u r n INF E A S IB LE;/完成删除注意i=l 的情况需要特殊处理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

31、 f (j=l)q-n e x t=l b;l b=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 INF E A S IB LE;q-n e x t=s-n e x t;s-n e x t=p;/完成插入r e t u r n OK;)2.1 7试写一算法在无头结点的动态单链表上实现线性表操作In s e r t (Lib)并和在带头结点的动态单链表上实现相同操作的算法进行比较2.18试写-算法实现线性表操作D e l e t e di)并和在带头结点的动态单链表上实现相同操作的算法进行比较2.1 9已知线性表

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

33、 t u r n E R R OR;P二 L;p r e v=p;p=p-n e x t;w h i l e(p&p-d a t a d a t a n e x t;e l s 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 OK;)2.2 0 同 2.19 题条件试写一高效的算法删除表中所有值相同的多余元素(使得操作后的线性表中所有元素的值均不相同)同时释放被删结点空间并分析你的算法的时间复杂度解：v o i d Li s t D e l e t e _ LS a m e No d e(Li n k Li

34、 s t&L)(Li n k Li s t pqp r e v;P=L;p r e v=p;p=p-n e x t;w h i l e(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 Li s t Op p o s e _ S q(S q Li s t&L)i n t i;E l e m T y p e x;f o

35、 r(i=0;i n e x t;L-n e x t=NU LL;w h i l e(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 OK;)2.2 3 设线性表试写一个按下列规则合并AB为线性表C的算法即使得当时；当时线性表AB和 C均以单链表作存储结构且 C表利用A表和B表中的结点空间构成注意：单链表的长度值m和 n 均未显式存储解：/将合并后的结果放在C表中并删除B表S t a t u s Li s t Mc r g e _ L(Li n k Li s t&ALi n k Li s t&BLi n k Li s

36、t&C)(Li n k Li s t p ap bq aq b;p a=A-n e x t;p b=B-n e x t;C=A;w h i l e(p a&p b)q a=p a;q b=p b;p a=p a-n e x t;p b=p b-n e 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 OK;2.2 4 假设有两个按元素值递增有序排列的线性表A和 B均以单链表作存储结构请编写算法将A表 和 B 表归并成一个按元素值递减有序(即非

37、递增有序 允许表中含有值相同的元素)排列的线性表C并要求利用原表(即A表 和 B表)的结点空间构造C表解：/将合并逆置后的结果放在C表中并删除B表S t a t u s Li s t Me r g e Op p o s e _ L(Li n k Li s t&ALi n k Li s t&BLi n k Li s t&C)Li n k Li s t p ap bq aq 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=NU LL;OA;w h

38、 i l e(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-ne xt=qa;)e lse qb=pb;pb=pb-ne xt;qb-ne xt=A-ne xt;将当前最小结点插入A表表头A-ne xt=qb;wh i le(pa)qa=pa;paz zpa-ne xt;qa-ne xt=A-ne xt;A-ne xt=qa;wh i le(pb)qb=pb;pb 二 pb-ne xt;qb-ne xt=A-ne xt;A-ne xt=qb;pb 二 B;

39、f re e (pb);re turn O K;)2.2 5 假设以两个元素依值递增有序排列的线性表A和 B分别表示两个集合(即同一表中的元素值各不相同)现要求另辟空间构成一个线性表C其元素为A和 B中元素的交集且表C中的元素有依值递增有序排列试对顺序表编写求C的算法解：/将 A、B求交后的结果放在C表 中 S ta tus L i stC ross S q(S qL i st&AS qL i st&BS qL i st&C)i nt i=0J=0k=0;wh i le(i A.le ng th&j B.le ng th)i f(A.e le m i B.e le m j)j+;e lse L

40、 i stI nse rt_ S q(CkA.e le m i );i+；k+;)re turn O K;)2.26要求同2.2 5 题试对单链表编写求C的算法解：/将 A、B求交后的结果放在C表 中 并 删 除 B表S ta tus L i stC ross L(L i nkL i st&AL i nkL i st&BL i nkL i st&C)L i nkL i st papbqaqbpt;pa=A;pb=B;qa=pa;/保 存 p a 的前驱指针qb=pb;/保 存 p b 的前驱指针pa=pa-ne xt;pb=pb-ne xt;C=A;wh i le(pa&pb)i f(pa-d

41、a ta da ta)pt=pa;pa=pa-ne xt;qa-ne xt=pa;f re e (pt);)e lsei f(pa-da ta pb-da ta)pt=pb;pb=pb-ne xt;qb-ne xt=pb;f re e(pt);)e lse qa=pa;paz zpa-ne xt;wh i le(pa)pt=pa;pa=pa-ne xt;qa-ne xt=pa;f re e(pt);)wh i le(pb)pt=pb;pb=pb-ne xt;qb-ne xt=pb;f re e (pt);)pb=B;f re e (pb);re turn O K;2.2 7 对 2.2 5 题

42、的条件作以下两点修改对顺序表重新编写求得表C的算法(1)假设在同 一 表(A 或 B)中可能存在值相同的元素 但要求新生成的表C中的元素值各不相同；(2)利用A表空间存放表C解：(1)/A、B求交然后删除相同元素将结果放在C表中S ta tus L i stC rossD e lS a me _ S q(S qL i st&AS qL i st&BS qL i st&C)(i nt i=0j=0k=0;wh i le(i A.le ng th&j B.le ng th)i f(A.e le m i B.e le m j)j+;e lse i f(C.le ng th=O)L i sti nse

43、 rt S q(CkA.e le m i );k+;)e lsei f(C.e le m C.le ng th-1 !=A.e le m i )L i stI nse rt_ S q(CkA.e le m i );k+;i+；)re turn O K;)(2)/A、B求交然后删除相同元素将结果放在A表中S ta tus L i stC rossD e lS a me _ S q(S qL i st&A S qL i st&B)(i nt i=0J=0k=0;wh i le(i A.le ng th&j B.le ng th)i f (A.e le m i B.e le m j)j+;e lse

44、(i f(k=O)A.e le m k=A.e le m i ;k+;e lsei f(A.e le m k!=A.e le m i )A.e le m k=A.e le m i ;k+;)i+；)A.le ng th=k;re turn O K;2.2 8对 2.2 5 题的条件作以下两点修改对单链表重新编写求得表C的算法(1)假设在同一表(A 或 B)中可能存在值相同的元素但要求新生成的表C中的元素值各不相同；(2)利 用 原 表(A 表或B表)中的结点构成表C并释放A表中的无用结点空间解：(1)/A、B求交结果放在C表中并删除相同元素S ta tus L i stC rossD e lS

45、 a me _ L(L i nkL i st&AL i nkL i st&BL i nkL i st&C)(L i nkL i st pa pbqaqbpt;pa 二 A;pb=B;qa=pa;/保 存 p a 的前驱指针qb=pb;/保 存 p b 的前驱指针pa=pa-ne xt;pb=pb-ne xt;C=A;wh i le(pa&pb)i f(pa-da ta da ta)pt=pa;paz zpa-ne xt;qa-ne xt=pa;f re e (pt);)e lsei f(pa-da ta pb-da ta)pt=pb;pb=pb-ne xt;qb-ne xt=pb;f re e

46、 (pt);e lse i f(pa-da ta=qa-da ta)pt=pa;pa=pa-ne xt;qa-ne xt=pa;f re e(pt);)e lse qa=pa;pa=pa-ne xt;wh i le(pa)pt=pa;pa=pa-ne xt;qa-ne xt=pa;f re e(pt);wh i le(pb)pt=pb;pb=pb-ne xt;qb-ne xt=pb;f re e (pt);pb=B;f re e(pb);re turn O K;)(2)/A、B求交结果放在A表中并删除相同元素S ta tus L i stC rossD e lS a me _ L(L i nk

47、L i st&A L i nkL i st&B)(L i nkL i st papbqaqbpt；pa=A;pb=B;qa=pa;/保 存 p a 的前驱指针qb=pb;/保 存 p b 的前驱指针pa=pa-ne xt;pb=pb-ne xt;wh i le(pa&pb)i f(pa-da ta da ta)pt二 pa；paz zpa-ne xt;qa-ne xt=pa;f re e (pt);e lsei f(pa-da ta pb-da ta)pt=pb;pb=pb-ne xt;qb-ne xt=pb;f re e (pt);)e lse(i f(pa-da ta=qa-da ta)p

48、t=pa;pa=pa-ne xt;qa-ne xt=pa;f re e (pt);)e lse qa=pa;paz zpa-ne xt;wh i le(pa)pt=pa;paz zpa-ne xt;qa-ne xt=pa;f re e (pt);wh i le(pb)pt=pb;pb=pb-ne xt;qb-ne xt=pb;f re e (pt);)pb=B;f re e(pb);re turn O K;)2.29已知AB和C为三个递增有序的线性表现要求对A表作如下操作：删去那些既在B表中出现又在C表中出现的元素试对顺序表编写实现上述操作的算法并分析你的算法的时间复杂度(注意：题中没有特别指

49、明同一表中的元素值各不相同)解：/在A中删除既在B中出现又在C中出现的元素结果放在D中S ta tus L i stU ni on_ S q(S qL i st&DS qL i st&AS qL i st&BS qL i st&C)S qL i st T e mp;I ni tL i st_ S q(T e mp);L i stC ross_ L(B CT e mp);L i stM i nus_ L(AT e mpD);2.3 0要求同2.2 9 题试对单链表编写算法请释放A表中的无用结点空间解：/在 A中删除既在B中出现又在C中出现的元素 并释放B、CS ta tus L i stU ni

50、 on_ L(L i nkL i st&AL i nkL i st&BL i nkL i st&C)(L i stC ross L(B0;L i stM i nus_ L (AB);/求集合A-B结果放在A表中并删除B表S ta tus L i stM i nus_ L(L i nkL i st&AL i nkL i st&B)(L i nkL i st papbqaqbpt;pa=A;pb=B;qa=pa;/保 存 pa 的前驱指针qb=pb;/保 存 p b 的前驱指针pa=pa-ne xt;pb=pb-ne xt;wh i le(pa&pb)i f(pb-da ta da ta)pt二