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

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

1、数据结构题集（C语言版）答案精神成就事业，态度决定一切。第1主绪论1.l简述下列术语：数据数据元素、数据对象、数据结构、存储结构、数据类型和抽象数据类型角平：数据是对客观察物的符号表示在t才算机科学中是指所有能输入到iI算机中并被t才算机程序处理的符号的总称数据元素是数据的基本单位在t才算机程序中通常作为一个整体进行考虑和处理数据对象是性质相同的数据元素的集合是数据的一个子集数据结构是相互之间存在一种或多种特定关系的数据元素的集合存储结构是数据结构在讨算机中的表示数据类型是一个值的集合和定义在这个值袋上的一组操作的总称抽象数据类型是指一个数学模型以及定义在该模型上的一组操作是对一般数据类型的扩

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

3、和有理数的定义（有理数是其分子、分母均为自然数且分母不为零的分数）角平：ADT Complex 数据对象：D=ri Ir i为实数数据关系：R=基本操作：Ini tCompl ex(&C re i m)操作结果：构造一个复数C其实部和部分别为re和imDestroyCmoplex(&C）操作结果：销毁复数CGet(C k&e)操作结果用e返回复数C的第k元的值Put(&C k e)操作结果改变复数C的第k元的值为eIsAscendi ng(C)操作结果如果复数C的两个元素按开序排列则返回1否则返回0IsDescendi ng(C)操作结果如果复数C的两个元素按降序排列则返回1否则返回OMax(

4、C&e)操作结果：用e返国复数C的两个元素中值较大的一个M in(C&e)操作结果：用e返回复数C的两个元素中值较小的一个ADT Complex ADT RationalNumber 数据对象：D=smis m为自然数且m不为O数据关系：R=基本操作：InitRational Number(&R s m)操作结果构造一个有理数R其分子和分母分别为s和mDestroyRati onalNumber(&R）操作结果：销毁有理数RGet(R k&e)操作结果：用e返回有理数R的第k元的值Put(&R k e)操作结果改变有迎数R的第k元的值为eIsAscending(R)操作结果：若有理数R的两个元

5、素按fl序排列则返回1否则返回0IsDescending(R)操作结果若有理数R的两个元素按降序排列则返回1否则返回0Max(R&e)操作结果用e返回有理数R的两个元素中值较大的一个M in(R&e)操作结果用e返回有理数R的两个元素中值较小的一个ADT RationalNumber 1.5试画出与下列程序段等价的框囚(1)product=!.i=1.while(i=n)product*=i.i+;(2)i=O;do i+.while(i!=n）战（a i!训，(3)switch case xy:z=y-x,break.case x=y:z=abs(x*y).break;defaul t:z=

6、(x-y)I abs(x)*abs(y).1.6在程序设i-1中常用下列三种不同的出错处理方式：(1）用exit语句终止执行并报告错误，(2）以函数的返回值区别正确返回或错误返回，(3）设置一个整型变量的函数参数以区别正确返回或某种错误返回试讨论这三利l方法各自的优缺点解：（1)exit常用于异常错误处理它可以强行中断程序的执行返应操作系统(2）以函数的返回值判断正确与否常用于子程序的测试便于实现程序的局部控巾(3）用整型函数进行错误处理的优点是可以给出错误类型便于迅速确定错误1.7在程序设计中可采用下列三种方法实现输出和输入(1）通过s canf和printf语句，(2）通过函数的参数显式传

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

8、 hile(i=n-1)i+;k+=lO*i(4)k=O;for(i=l.i=n;i+)for(j=i.j=n;j+)k+(5)for(i=l.i=n;i+)for(j=l.j=i.j+)for(k=l.k=j,k+)x+=delta:(6)i=l.j=O;while(i+jj)j+;else i+;(7)x习，y=O;II n是不小于1的常数while(x=(y+l)*(y+l)y+;(8)x=91.y=lOO;while(y o)i f(xlOO)x-=10.y一，else x+;解：(1)n-1(2)n-1(3)n-1(4)n+(n-l)+(n-2)+.+1=(5)1+(1+2)+(1+

9、2+3)+.+(1+2+3+.+n)=(6)n(7）向下取整(8)1100 1.9假设n为2的乘容并且n)2试求下列第法的时间复杂度及变量count的值（以n的函数形式表示）int Time(int n)count=0 x=2 while(xy)i f(xz)return x;else return z.el se if(yz)return y;el se return z.1.17己知k阶斐被那契序列的定义为试编写求k阶斐被那契序列的第m项值的函数第法k本llm均以值调用的形式在函数参数表中出现解，：kO为阶数n为数列的第n项int Fibonacci(int k int n)i f(kl)

10、exi t(OVERFLOII).int*P x.p=new intk+l.if(!p)exit(OVERFLOII).inti J.for(i=O;ik+l.i+)if(i k-1)pi=O;else pi=l.for(i=k+l.i n+l.i+)x=pO .for(j=O;jk;j+)pj=pj+l.pk=2*pk-1-x.return p叶，1.18假设有AB c D E五个高等院校进行回径对抗赛各院校的单项成绩均已存入计算机并构成一张表表中每一行的形式为项目名称性别校名成绩得分编写算法处理上述表格以统剖各统校的男、女总分利团体总分并输出解typedef enumA B c D E S

11、choolNam e;typedef enumFem ale Male SexType;typedef struct char event坷，项目SexType sex.SchoolNam e school int score Component.typedef struct int MaleSum;男团总分int Fem aleSum;女团总分int TotalSum;团体总分S1坝，Sum SumScore(SchoolNam e sn Component a int n)Sum tem p,tem p.MaleSum=O.temp.Fem aleSum=O.temp.TotalSum=O

12、.int 1 for(i=O;iarrsize或对某个使时应按出错处理注意选择你认为较好的出错处理方法角丰：llinclude llinclude lldefine MAXIN T 65535 lldefine ArrSize 100 int fun(int i).int main()i nt 1 k;int aArrSize.coutkif(kArrSi ze-1)exit(O).for(i=O;iMAXIN T)exi t(O).else ai=2*i*ai-1.for(i=O;iMAXIN T)exi t(O).else coutai”Hreturn O 1.20试编写算法求一元多项式的

13、值的值并确定算法中每一语旬的执行次数和整个算法的时间复杂度注意选择你认为较好的输入和输出方法本题的输入为和输出为角甲，llinclude llinclude!define N 10 double polynomail(int a int 1 double x int n).int main()double x:int n 1,int aN.cout”输入变量的值x：”；cinxcout输入多项式的阶次n：”；cinn:i f(nN-1)exi t(O).cout输入多项式的系数aO-an：飞for(i=O;iai .coutThe polynomail value i s npolynomai

14、l(an x n)O)return an-i+polynomail(a i-1 x n)*x.else return a叶，本算法的时间复杂度为o(n)第2主线性表2.1描述以下三个概念的区别：头指针头结点首元结点（第一个元素结点）解头指针是指向链表中第一个结点的指针首元结点是指链表中存储第一个数据元素的结点头结点是在首元结点之前附设的一个结点该结点不存储数据元素其指针域指向首元结点其作用主要是为了方便对链表的操作它可以对空袭、非空袭以及首元结点的操作进行统一处理2.2填空题角丰.(1）在）ll9i字表中插入或删除一个元素需要平均移动表中一半元素具体移动的元素个数与元素在表中的位置有关(2）顺

15、序表中逻辑上相邻的元素的物理位置必定紧邻单链表中逻辑上相邻的元素的物理位置不一定紧邻(3）在单链表中除了首元结点外任一结点的存储位置主l其前驱结点的链域的值指示(4）在单链表中设置头结点的作用是插入和删除首元结点时不用进行特殊处理2.3在什么情况下用顺序表比链表好，角丰当线性表的数据元素在物理位置上是连续存储的时候用顺序表比用链表好其特点是可以进行随机存取2.4对以下单链表分别执行下列各程序段并画出结果示意图自丰：2.5画出执行下列各行语句后各指针及链表的示意图L=(LinkList)m alloc(sizeof(LNode).P=L;for(i=l.inext=(LinkList)m all

16、oc(si zeof(LN ode).P=P-next P-data=i*2-1 P-next肌JLL:for(i=4.i=l.i一）Ins_LinkList(L i+l i*2).for(i=l.inext=S.(2)P-next=P-next-next.(3)P-next=S-next.(4)S-next=P-next.(5)S-next=L;(6)s-next阳LL;(7)Q=P;(8)w hile(P-next!=Q)P=P-next;(9)w hile(P-next!=NULL)P=P-next;(10)P=Q;(11)P=L;(12)L=S;(13)L=P;角丰：a.(4)(1)b

17、.(7)(11)(8)(4)(1)c.(5)(12)d.(9)(1)(6)2.7己知L是辛苦表头结点的非空单链表且P结点既不是首元结点也不是尾元结点试从下列提供的答案中选择合适的语句序列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！阳LL)P=P-next;(6)w hile(Q-next!=NULL)P=Q;Q=Q-next;(7)

18、w hile(P-next!=Q)P=P-next;(8)w hile(P-next-next!=Q)P=P-next.(9)w hile(P-next-nextl=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

19、结点前插入S结点的语句序列是c.删除P结点的直接后继续点的语句序列是d.删除P结点的直接前驱结点的语句序列是e.删除P结点的语句序列是(1)P-next=P-next-next.(2)P-pr iou=P-priou-priou;(3)P-next=S.(4)P-pr iou=S.(5)S-next=P.(6)S-pr iou=P.(7)S-next=P-next.(8)S-pr iou=P-priou;(9)P-pr iou-next=P-next.(10)P-priou-next=P.(11)P-next-pr iou=P.(12)P-next-priou=S.(13)P-priou-ne

20、xt=S.(14)P-next-priou=P-priou;(15)Q=P-next;(16)Q=P-priou;(17)free（肘，(18)free(Q).角丰：a.(7)(3)(6)(12)b.(8)(4)(5)(13)c.(15)(1)(11)(18)d.(16)(2)(10)(18)e.(14)(9)(17)2.9简述以下算法的功能(1)Status A(Linked.List L)/L是无表头结点的单链表if(L拙L-next)Q=L;L=L-next.P=L;while(P-next)P=P-next.P-next=Q;Q-next=NULL;return OK:(2)void

21、BB(LNode*s LN ode*q)p=s.w hile(p-next!=q)p=p-next.p-next=s.void AA(LN ode*pa LN ode*pb)/pa和pb分别指向单循环链表中的两个结点BB(pa pb).BB(pb pa).解.(1）如果L的长度不小子2将L的首元结点变成尾元结点(2）将单循环链表拆成两个单循环链表2.10指出以下第法中的错误和低效之处并将它改写为一个既正确又高效的算法Status DeleteK(SqLi st&a int i int k)；本过程从顺序存储结构的线性表a中删除第i个元素起的k个元素i f(il l lka.length)ret

22、urn INFEASIBLE；参数不合法el se for(count=l.count=i+1.j一）a.elemj-i=a.elemj.a.length 一，return OK:角平：Status DeleteK(SqList&a int 1 int k)从顺序存储结构的线性表a中删除第i个元素起的k个元素注意i的编号从0开始i nt j,i f(ia.length-11 lka.length-i)return INFEASIBLE;for(j=O;jO xB.length?A.length:B.length;for(i=O;i B.elemi)j=l.if(A.elemik)j=l.i f

23、(B.lengthk)j=-1.i f(A.length=B.length)j=O;return j,2.13试写一算法在带头结点的单链表结构上实现线性表操作Locate(Lx).角平：int LocateElem_L(LinkList&L ElemType x)int i=O:LinkLi st p=L;w hile(p&p-data!=x)p=p-next.i+;if(lp)return 0;else return i.2.14试写一算法在带头结点的单链表结构上实现线性表操作Length(L)角丰：返回单链袤的长度int ListLength_L(LinkList&L)int i=O:Li

24、nkList p=L;i f(p)p=p-next.w hile(p)p=p-next.i+;return i.2.15己知指针ha和hb分别指向两个单链衰的头结点并且己知两个链表的长度分别为m和n试写一算法将这两个链表连接在一起假设指针he指向连接后的链表的头绪点并要求算法以尽可能短的时间完成连接运算请分析你的第法的时间复杂度角丰：void MergeLi st_L(LinkLi st&ha LinkLi st&hb LinkLi st&he)LinkLi st pa pb;pa=ha.pb=hb;w hile(pa-next&pb-next)pa=pa-next.pb=pb-next.i

25、f(!pa-next)hc=hb:w hile(pb-next)pb=pb-next.pb-next=ha-next.else hc=ha w hile(pa-next)pa=pa-next.pa-next=hb-next.2.16己知指针la和lb分别指向两个无头结点单链表中的首元结点下列第法是从表la中删除自第i个元素起共len个元素后将它们插入到表lb中第i个元素之前试问此算法是否正确，若有错请改正之Status DeleteAndinser tSub(Linked.Li st la LinkedList lb inti int J int len)i f(iOl ljOl llenO)

26、return INFEASIBLE;p=la;k=l.w hile(knext;k+;q=p,while(knext.k+;s=lb k=l w hile(knext;k+;s-next=p,q-next=s-next.return OK:角丰Status DeleteAndinsertSub(LinkLi st&la LinkLi st&lb int i int j int len)LinkLi st p q s prev=NULL;int k=l i f(iOl ljOl llenO)return INFEA SIBLE;在la表中查找第i个结点p=la.while(p跳knext.k+i

27、f(!p)return INFEA SIBLE;在la表中查找第i+len-1个结点q=p,k=l.w hile(q脱knext.k+if(!q)return INFEASIBLE;完成删除注意i=l的情况需要特殊处理if(!prev)la=q-next.el se prev-next=q-next.将从la中删除的结点插入到lb中if(j=l)q-next=lb.lb=p,el se s=lb k=l while(s跳knext k+if(!s)return INFEASIBLE;q-next=s-next.s-next=p;完成插入ret盯nOK:2.17试写一算法在无头结点的动态单链表上

28、实现线性表操作Insert(Ll b)并和在甜头结点的动态单链表上实现相同操作的第法进行比较2.18试写一算法实现线性表操作Delete(L i)并初在带头结点的动态单链表上实现相同操作的第法进行比较2.19己知线性表中的元素以值递增有序排列并以单链表作存储结构试写一高效的算法删除表中所有值大于mink且小于maxk的元素（若表中存在这样的元素）同时释放被删结点空间并分析你的第法的时间复杂度（注意mink和maxk是给定的两个参变量它们的值可以和表中的元素相同也可以不同）解Status ListDelete_L(Li nkList&L ElemType mi nk ElemType maxk)

29、Li nkList p q prev=NULL;i f(mi nkmaxk)return ERROR;p=L;prev=p,p=p-next.while(p&p-datadatanext.else prev-next=p-next.q=p,p=p-next.free(q).return OK:2.20同2.19题条件试写一高效的第法删除表中所有值相同的多余元素（使得操作后的线性表中所有元素的值均不相同）同时释放被删结点空间并分析你的算法的时间复杂度自丰void Li stDelete_LSameNode(LinkList&L)LinkLi st p Q prev,p=L;prev=p,p=p-

30、next.w hile(p)prev=p,p=p-next.i f(p&p-data=prev-data)prev-next=p-next.q=p,p=p-next.free(q).2.21试写一算法实现顺序表的就地逆置即利用原袤的存储空间将线性表逆直为角丰顺序表的逆盟Status ListOppose_Sq(SqList&L)int 1.ElemType x;for(i=O;inext.L-next肌JLL:w hile(p)q=p,p=p-next.q-next=L-next.L-next=q;return O K:2.23设线性表试写一个按下列规则合并A B为线性表C的算法即使得当时，当

31、时线性表AB和C均以单链表作存储结构且C表利用A表和B表中的结点空间构成注意单链袭的长度值m和n均未显式存储角甲，将合并后的结果放在C表中并删除B表Status Li stMerge_L(LinkList&A LinkList&B LinkList&C)LinkList pa pb qa qb;pa=A-next.pb=B-next.C=A:while(pa脱pb)qa=pa,qb=pb,pa=pa-next.pb=pb-next.qb-next=qa-next.qa-next=qb,i f(!pa)qb-next=pb;pb=B.free(pb).return OK:2.24假设有两个按元素

32、值递增有序排列的线性表A和B均以单链表作存储结构请编写算法将A表和B表归并成一个按元素宣递减有J芋（即非递增有J字允许表中含有值相同的元素）排列的线性表C并要求利用原袋。IIA表和B表）的结点空间构造C表角丰：将合并逆置后的结果放在C表中并删除B表Status ListMergeOppose_L(LinkList&A LinkList&B LinkLi st&C)LinkLi st pa pb qa qb;pa=A;pb=B.qa=pa;保存pa的前驱指针qb=pb;II保存pb的前驱指针pa=pa-next.pb=pb-next.A-next肌JLL:C=A:while(pa，舱内）i f(

33、pa-datadata)qa=pa,pa=pa-next.qa-next=A-next;II将当前最小结点插入A表表头A-next=qa;el se qb=pb,pb=pb-next.qb-next=A-next;将当前最小结点插入A表表头A-next=qb,w hile(pa)qa=pa,pa=pa-next.qa-next=A-next.A-next=qa,w hile(pb)qb=pb,pb=pb-next.qb-next=A-next.A-next=qb,pb=B.free(pb).return O K:2.25假设以两个元素依值递增有序排列的线性表A和B分别表示两个集合（即同一表中的

34、元素值各不相同）现要求另辟空间构成一个线性表C其元素为A和B中元素的交集且表C中的元素有依值递增有序排列试对顺序表编写求C的算法角平：将A、B求交后的结果放在C表中StatusListCross_Sq(SqList&A SqList&B SqList&C)int i=O j=O k=O:w hile(i A.length&jB.length)i f(A.elemiB.elemj)j+;else List!nsert_Sq(C k A.elemi).i+;k+;ret盯nOK:2.26要求同2.25题试对单链表编写求C的算法解将A、B求交后的结果放在C表中并删除B表Status ListCros

35、s_L(LinkList&A LinkList&B Li成List&C)LinkList pa pb qa qb pt,pa=A;pb=B.qa=pa;保存pa的前驱指针qb=pb;保存pb的前驱指针pa=pa-next.pb=pb-next.C=A:while(pa舱内）if(pa-datadata)pt=pa;pa=pa-next.qa-next=pa;free(pt).else i f(pa-datapb-data)pt=pb,pb=pb-next.qb-next=pb,free(pt).el se qa=pa;pa=pa-next.while(pa)pt=pa,pa=pa-next.q

36、a-next=pa,free(pt).w hile(pb)pt=pb,pb=pb-next.qb-next=pb,free(pt).pb=B.free(pb).return OK:2.27对2.25题的条件作以下两点修改对顺序表重新编写求得表C的第法(1）假设在同一表（A或B）中可能存在值相同的元素但要求新生成的表C中的元素值各不相同，(2）利用A表空间存放表C角丰：(1)II A、B求交然后删除相同元素将结果放在C表中Status ListCrossDelSam e_Sq(SqList&A SqList&B SqList&C)int i=O j=O k=O:w hile(i A.length

37、&jB.length)i f(A.elemiB.elemj)j+;else i f(C.length=O)Li st!nsert_Sq(C k A.elemi).k+;el se i f(C.elemC.length-!=A.elemi)List!nsert_Sq(C k A.elemi).k+1+.return OK:(2)II A、B求交然后删除相同元素将结果放在A表中Status ListCrossDelSame_Sq(SqLi st&A SqLi st&B)int i=O j=O k=O:w hile(i A.length&jB.length)i f(A.elemiB.elemj)j+

38、;el se i f(k=O)A.elemk=A.elemi .k+else i f(A.elemk!=A.elemi)A.elemk=A.elemi .k+i+;A.length=k;return OK:2.28对2.25题的条件作以下两点修改对单链表重新编写求得表C的第法(1）假设在同一表（A或B）中可能存在值相同的元素但要求新生成的表C中的元素值各不相同，(2）利用原表（A表或B表）中的结点构成表C并释放A表中的无用结点空间角丰：(1)II A、B求交结果放在C表中并删除相同元素Status ListCrossDelSame_L(LinkList&A LinkList&B LinkLis

39、t&C)LinkList pa pb qa qb pt,pa=A;pb=B.qa=pa;II保存pa的前驱指针qb=pb;II保存pb的前驱指针pa=pa-next.pb=pb-next.C=A:while(pa脱pb)if(pa-datadata)pt=pa,pa=pa-next.qa-next=pa;free(pt).el se i f(pa-datapb-data)pt=pb,pb=pb-next.qb-next=pb,free(pt).el se i f(pa-data=qa-data)pt=pa,pa=pa-next.qa-next=pa;free(pt).else qa=pa;pa

40、=pa-next.w hile(pa)pt=pa;pa=pa-next.qa-next=pa,free(pt).w hile(pb)pt=pb,pb=pb-next.qb-next=pb,free(pt).pb=B.free(pb).ret盯nOK:(2)II A、B求交结果放在A表中并删除相同元素Status ListCrossDelSame_L(LinkList&A LinkList阻）LinkList pa pb qa qb pt,pa=A;pb=B.qa=pa;保存pa的前驱指针qb=pb;保存pb的前驱指针pa=pa-next.pb=pb-next.while(pa脱pb)if(pa

41、-datadata)pt=pa,pa=pa-next.qa-next=pa;free(pt).else if(pa-datapb-data)pt=pb,pb=pb-next.qb-next=pb,free(pt).el se if(pa-data=qa-data)pt=pa;pa=pa-next.qa-next=pa;free(pt).else qa=pa;pa=pa-next.w hile(pa)pt=pa;pa=pa-next.qa-next=pa,free(pt).while(pb)pt=pb,pb=pb-next.qb-next=pb,free(pt).pb=B.free(pb).re

42、turn O K:2.29己知AB和C为三个递增有序的线性表现要求对A表作如下操作：删去那些既在B袋中出现又在C表中出现的元素试对JI阪J字表编写实现上述操作的第法并分析你的第法的时间复杂度（注意题中没有特别指明同一表中的元素值各不相同）角平：在A中删除既在B中出现叉在C中出现的元素结果放在D中Status Li stUnion_Sq(SqList&D SqLi st&A SqLi st&B SqLi st&C)SqLi st Tem p;Ini tLi st_Sq(Tem p).ListCross_L(B c Tem p).Li stMinus_L(A Tem p D).2.30要求同2.2

43、9题试对单链表编写算法请释放A表中的无用结点空间角丰：在A中删除既在B中出现又在C中出现的元素并释放B、cStatus Li stUnion_L(LinkLi st&A LinkLi st&B LinkLi st&C)Li stCross_L(B C).Li stMinus_L(A B).求集合A-B结果放在A表中并删除B表Status ListMinus_L(LinkList&A LinkList臼）LinkLi st pa pb qa qb pt,pa=A;pb=B.qa=pa;保存pa的前驱指针qb=pb;保存pb的前驱指针pa=pa-next.pb=pb-next.while(pa，舱

44、内）if(pb-datadata)pt=pb,pb=pb-next.qb-next=pb,free(pt).el se i f(pb-datapa-data)qa=pa;pa=pa-next.el se pt=pa;pa=pa-next.qa-next。a.free(pt).w hile(pb)pt=pb,pb=pb-next.qb-next=pb,free(pt).pb=B.free(pb).return OK:2.31假设某个单向循环链衰的长度大于1且表中既无头结点也无头指针己知s为指向链表中某个结点的指针试编写算法在链表中删除指针s所指结点的前驱结点角丰：在单循环链表S中删除S的前驱结点

45、StatusListDelete_CL(LinkList&S)LinkList p q,if(S=S-next)return ERROR;q=S.p=S-next.while(p-next!=S)q=p,p=p-next.q-next=p-next.free(p).return OK:2.32己知有一个单向循环链表其每个结点中含三个域：predata和next其中data为数据域next为指向后继结点的指针域pre也为指针域但它的值为空试编写算法将此单向循环链表改为双向循环链表即使pre成为指向前驱结点的指针域角丰建立一个空的循环链表Status InitList_D L(DuLinkList

46、&L)L=(DuLinkLi st)m alloc(si zeof(DuLNode).if(IL)exit(OVERFLOW).L-pre=NULL;L-next=L:return OK:向循环链表中插入一个结点Status Li st insert_D L(DuLinkList&L ElemType e)DuLinkList p;p=(DuLinkLi st)m alloc(sizeof(D uLN ode).if(!p)return ERRO R;p-data=e.p-next=L-next.L-next=p,return O K:将单循环链表改成双向链表Status Li stCirTo

47、Du(DuLinkLi st&L)DuLinkLi st p Q,q=L;p=L-next.while(p!=L)p-pre=q;q=p,p=p-next.i f(p=L）pre气，ret盯nOK:2.33已知主一个线性链表表示的线性表中含有三类字符的数据元素（如字母字符、数字字符和其他字符）试编写算法将该线性表分制为三个循环链表其中每个循环链表表示的线性表中均只含一类字衍解将单链表L戈1J分成3个单循环链表Status Li stDivideinto3CL(LinkList&L LinkList&sl LinkList&s2 LinkList&s3)LinkList p q ptl pt2

48、pt3;p=L-next.ptl=sl.pt2=s2.pt3=s3.while(p)if(p-data=0&p-datanext.q-next=ptl-next.ptl-next=q,ptl=ptl-next.else i f(p-=A&p-datadata=a&p-datanext.q-next=pt2-next.pt2-next=q,pt2=pt2-next.else q=p,p=p-next.q-next=pt3-next.pt3-next=q,pt3=pt3-next.q=L;free(q).return OK:在2.34至2.36题中H异或指针双向链衰类型XorLinkedList和

49、指针异或函数XorP定义为：typedef struct X orNode char data struct X orNode*LRPtr:X orNode*XorPointer typede struct 无头结点的异或指针双向链表X orPointer Left Right:，分别指向链表的左侧和右端 X orLinkedList;X orPointer X orP(XorPointer p X orPointer q).指针异或函数XorP返回指针p和q的异或值2.34假设在算法描述语言中引入指针的二元运算异或若a和b为指针则a?b的运算结果仍为原指针类型且a?(a?b)=(a?a)?b

50、=b(a?b)?b=a?(b?b)=a 则可利用一个指针域来实现双向链表L链表L中的每个结点只含两个域：data域和LRPtr域其中LRPtr域存放该结点的左邻与右邻结点指针（不存在时为阳LL）的异或若设指针L.Left指向链表中的最左结点L.Right指向链表中的最右结点则可实现从左向右或从右向左泡历此双向链袭的操作试写一算法按任一方向依次输出链表中各元素的值角甲，Status TraversingLinkList(XorLinkedLi st&L char d)XorPointer p left r ight;if(d=lI Id=L)p=L.Left.left=NULL:while(p！