数据结构课后习题答案详解(C语言版_严蔚敏)2.pdf

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

1、数据结构习题集答案(C语肃.版严蔚敏)第 2 聿线性表2.1 描述以下三个概念的区别：头指针，头结点，首元结点(第个元素结点).解：头指针是指向链表中第一个结点的指针。元结点是指链表中存储第个数据元素的结点。头结点是在苜元结点之前附设的一个结点，该结点不存储数据元素，其指针域指向 元结点，其作用主要是为了方便对链表的操作。它可以对空表、非空表以及忏元结点的操作进行统处理。2.2 填空题。解：(1)在顺样表中插入或删除个元素，需要平均移动表中 华元素，具体移动的元素个数与元素在表中的位置有关。(2)顺序表中逻辑上相邻的元素的物理位置必定紧邻。单链表中逻辑上相邻的元素的物理位置不定紧邻。(3)在单

2、链表中，除了首元结点外，住结点的存储位置由其前驱结点的链域的值指示。(4)在单链表中设置头结点的作用是插入和删除首元结点时不用进行特殊处理。2.3 在什么情况下川顺序表比链表好？解：当级性表的数据元素在物理位置上是连续存储的时候，用顺序表比用链表好，其特点是可以进行随机存取.2.4 对以下单链表分别执行下列各程序段，并画出结果示意图。LT 2 H-d ；ii-!iH-f y n 4 ；卜解：(1)-L r r n 一4 y l l 一 r p i-LT 2|4;|!;II-1;II 4;卜 P Q R S(B p T r p n-j n-y T i-*P Q R SP(7)LT 2|1 1 ；

3、II-1 ；II-1 1 ；1卜PQR S2.5 画出执行下列各行语句后各指针及链表的示意图。L=(LinkList)malloc(sizeof(LNode);P=L;for(i=l：incxt=(LinkListjmal loc(sizeof(1 Jnext;P-next=NULL;for(i=4;i=l：i)for(i=l;idata=i*2-l;lns_LinkList(L,i+1,i*2);Del_LinkList(L,i):HZZD-HZLD QUZDDZ0L-OHZH-czo-zu-cm sizucpZBLH IIr m 4ii_1 6 ii_j；【I-8 wp2.6 已知L是无表

4、头结点的单链表，且P 结点既不是首元结点，也不是尾元结点，试从下列提供的答案中选择合适的语句序列。a.在 P 结点后插入S 结点的语句序列是 0b.在 P 结点前插入S 结点的i吾句序列是 Oc.在表首插入S 结点的语句序列是.d.在表尾插入S 结点的语句序列是。(1)P-next=S:(2)P-next=P-next-next;(3)P-next=S-next:(4)S-next=P-next;(5)S-next=L;(6)S-next=NULL;(7)Q=P:(8)while(P-ncxt!=Q)P=P-next;(9)while(P-next!=NULL)P=P-next;(10)4Q;

5、(11)P=L;(12)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.删除P 结点的直接前驱结点的语句序列是_ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _。c.删除P 结点的语句序列是_ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _d.删除苜元结点的语句序列是e.删除尾元结

6、点的语句序列是(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-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 l-n e x l!=N U L L)

7、P=P-n e x t:(1 0)Q=P;(1 1)Q=P-n e x t：(1 2)P=L;(1 3)L=L-n e x t:(1 4)f r e e(Q);解：a.(1 1)(3)(1 4)b.(1 0)c.(1 0)d.(1 2)(1 2)(8)(3)(1 4)(1 2)(7)(3)(1 4)(1 1)(3)(1 4)e.(9)(1 1)(3)(1 4)2.8 已知P结点是某双向链表的中间结点，试从卜.列提供的答案中选择合适的语句序列。a.在P结点后一插入S结点的酒句序列是 _ b.在 P结点前插入S结点的语句序列是.c.删除P 结点的R接后继结点的语句再列是 一.d.删除P结出的I 接

8、前骈结点的语句序列是e.删除P结 点 的 语 句 序 列 是 .(1)P-n e x l=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 i o u:(9)P-p r i o u-n e x t=P-n e x t;(1 0)P-p r i o u-n e x t=P;(1 1)P-n e x t-p r i o u=P

9、;(1 2)P-n e x t-p r i o u=S;(1 3)P-p r i o u-n e x t=S;(1 4)P-n e x t-p r i o u=P-p r i o u;(1 5)Q=P-n e x t:(1 6)Q=P-p r i o u:(1 7)f r e e(P);(1 8)f r e e(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)S t a t u s A(L i n k e d L i s t

10、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 i d A A(L N o d e *p ar L N o d e *p b)(/p a 和 p b 分别指向单循环链表中的两个结点B B(pa

11、.pb);B B (pb,pa);解：(1)如果L 的长度不小于2,将 L 的首元结点变成尾元结点。(2)将单循环链表拆成两个单循环链表。2.1 0 指出以下算法中的错误和低效之处，并将它改写为一个既正确乂高效的算法。S ta tus DeleteKC S q Lis t&a,int i,int k)(本过程从顺序存储结构的线性表a中删除第i个元素起的k 个元素if(i l|k a.length)r etur n INFEA S IB LE:参数不合法els e(for(count：1;count=i+l;j)a.elem j-i=a.elemtj;a.length:r etur n OK;)

12、解：S ta tus DeleleK(S q Lis t&a,ini i,ini k)(从顺序存储结构的线性表a中删除第i个元素起的k个元素注意i的编号从0开始int j;if(i a.length-1 1|k a.length-i)r etur n INFEA S IB LE:for(j=0：j 0,x va.elem i-l;i -)va.clem i=va.e 1 er a i-1 ;va.elem i=x:va.length+;r etur n OK;)2.i2 设4=(4,，)和B =(/7 ,/?)均为顺序表，Ar和8 分别为A和B中除去最大共同前缀后的子表。若A=5=空表，则4=

13、3：若4=空表，而8 w空表，或者两者均不为空表，n A!的首元小于B 的首元，则A B 试写-个比较A ,B大小的算法。解：S ta tus C ompa r eOr der Lis t(S q Lis t&A,S q Lis t&B)(int i,k,j;k=A.length B.length?A.lengthzB.length;for(i=0;i B.elem i)j=l:if(A.elem i)j=-l;if(A.length k)j=l：if(B.length k)j=-l;if(A.length=B.length)j=0;r etur n j：12.1 3试写-算法在带头结点的单链

14、表结构上实现线性表操作Loca te。”x);解：int Loca teEler a _ L(LinkLis t&L,ElemT ype x)(int i=0:LinkLis t p=L：while(p&p-da ta!=x)(p=p-next;i+；if(!p)r etur n 0：els e r etur n i;)2.1 4试写 噂法在带头结点的单链表结构上实现线性表操作Lenglh(L).解：返【可单链表的长度int Lis tLcngth L(LinkLis t&L)(int i=0;LinkLis t p=L;if(p)p=p-next;while(p)p=p-next;i+；r

15、etur n i;)2.1 5已知指针h a和h b分别指向两个单链表的头结点，并且已知两个链表的长度分别为m和n 0试写一算法将这两个链表连接在一起，假设指针he指向连接后的链表的头结点，并要求算法以尽可能短的时间完成连接运算。请分析你的算法的时间更杂度。解：void Mcr gcLis t L(LinkLis t&ha,Linkl.is t&hb,LinkLis t&hc)(LinkLis t pa,pb;pa=ha;pb=hb;while(pa-next&pb-next)(pa=pa-nexl;pb=pb-next：)if(!pa-next)hc=hb;whilc(pb-next)pb=

16、pb-next;pb-next=ha-next:els e(hc=ha;while(pa-nexl)pa=pa-next;pa-next=hb-next;)2.1 6已知指针la和lb分别指向两个无头结点单链表中的首元结点。卜列克法是从表la中删除自第i个元索起共len个元素后，将它们插入到表1 b中第i个元素之前。试问此算法是否jE确？若有错，请改正之。S ta tus DeleteA ndlns er tS ub C LinkedLis t la,LinkedLis t lb,int i,int j,int len)(if(i 0|j 0|len 0)r etur n INFEA S IB

17、 LE;p=la:k=l;while(k next;k+;q=P；while(k next:k+;1s=lb:k=l;while(k next：k+：s-next=p：q-nexl=s-nexI;r etur n OK:解：S ta tus De1 eteA ndIns er tS ub(LinkLis t&la,LinkLis t&Ib,int i,int j,int len)(LinkLis t p,q,s.pr ev=NU L L:i n t k=l;i f(i 0|j 0|l e n 0)re turn I NF E A SI B L E;/在l a表中查找第i个结点P=l a;w h

18、 i l e(p&k n e x t;k+;i f(!p)re turn I NF E A SI B L E：/在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)re turn I NF E A SI B L E：/完成删除，注意，i=l的情况需要特殊处理i f (!p re v)l a=q-n e x t;e l se p re v-n e x t=q-n e x t;/将从l a中删除的结点插入到l b中i f(j=l)q-n e x t=I b:l b=p：e l se s=l b;k=l:w h i l e(s&k

19、 n c x t：k-H-;)i f(!s)re turn I NF E A SI B L E;q-n e x t=s-n e x t;s-n e x t=p;完成插入re turn OK:)2.1 7试写 算法，在无头结点的动态单链表上实现线性表操作I n se rt(L i,b),并和在带头结点的动态单链表上实现相同操作的算法进行比较。2.18试写 算法，实现线性表操作D e l e te d,i),并和在带头结点的动态单链表上实现相同操作的算法进行比较。2.1 9已知线性表中的元素以值递增有序排列，并以单链表作存储结构。试写高效的算法，胴除表中所有值大于m i n k且小于i n a x

20、 k的元素(若表中存在这样的元素)，同时群放被删结点空间，并分析你的算法的时间史杂度(注意，m i n k和m a x k是给定的两个参变量，它们的值可以和表中的元素相同，也可以不同)。解：Sta tus L i stD e l e te L(L i n k L i st&L,E l e m Ty p c m i n k,E l e m Tvp e m a x k)(L i n k L i st p,q,p re v=NUL L;i f(m i n k m a x k)re turn E RROR;P=L;p re v=p;p=p-n e x t;w h i 1c(p&p-d a ta d a

21、 ta n e x t;)e l se p re v-n e x t=p-n e x t;q=P；p=p-n e x t;f re e(q);1)re turn OK;)2.20同2.1 9题条件，试写 高效的算法，删除表中所有值相同的多余元素,(使得操作后的线性表中所有元素的值均不相同)，同时释放被删结点空间，并分析你的算法的时间发杂度。解：vo i d L i stD e l e te _ L Sa m e No d e(L i n k L i st a L)(L i n k L i st p,q,p re v;P=L;p re v=p：p=p-n e x t;w h i l e(p)p

22、re v=p：p=p-n e x l;i f (p&p-d a ta=p re v-d a ta)(p re v-n e x t=p-n e x t;q=P；p=p-n e x t;f re e(q);)2.2 1试写 算法，实现顺序表的就地逆置，即利用原表的存储空间将线性表(”,0)逆置为。解：福 序表的逆置Sta tus L i s t0p p o se _ Sq(Sq L i s t&L)(i n t i;E l c m Ty p e x;f o r(i=0：i n e x t;L-n e x t=NUL L:w h i l e(p)(q=p;p=p-n e x t;q-n e x t=

23、L-n e x t：L-n e x t=q:)re turn OK;)2.2 3设线性衣A=，Q)8=(也，也)试写一个按下列规则合并A,B为线性表C的算法，即使得C=(%,仿3，3+1,也,)m L i n k L i st&B,L i n k L i st&C)(L i n k L i st p a,p b,q a,q 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 l=q a-n e x t：q a-n e x t=q

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

25、 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=rp a-n e x t:p b=p b-n e x t;A-n e x t=NUL L:C=A;w h i l e(p a&p b)(i f(p a-d a ta d a ta)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:e l se q b=p b;p b=p b-n e x t：q b-n e x t=A-n c x t;将当前最小结点插入A表表头

26、A-n e x t=q b;w h i l e(p a)q a=p a;p a=p a-n e x l;q a-n e x t=A-n c x t;A-n e x t=q a;)w h i l e(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 re e(p b):re turn OK：)2.25假设以两个元素依值递增有序排列的线性表八和B分别表示两个集合(即同一表中的元素值各不相同)，现要求另辟空间构成个线性表C,其元素为A和B中元素的交集，且表C中的元素有依位递增有序排列。试对顺序表编 弓求C

27、的算法。解：将A、B求交后的结果放在C表中Status Lis tCr o s s _Sq(Sq Lis t&A,Sq Lis t&B,Sq Lis t&C)(in t i=0,j=0,k=0：w hile(i A.len gth&j B.len gth)if(A.elem i B.elem j)j+：els elLis tIn s er t_Sq(C,k,A.elem i);i+：k+：)r etur n OK:2.26要求同2.2 5题。试对单链表编写求C的算法。解：,将A、B求交后的结果放在C表中，并删除B表Status Lis tCr o s s _L(Lin kLis t&A,Lin

28、 kLis t&B,Lin kLis t&C)(Lin kLis 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 ex t;p b=p b-n ex l;C=A;w hile(p a&p b)(i f(p a-data data)(p t=p a:p a=p a-n ex t;q a-n ex t=p a:fr ee(p t);els eif(p a-data p b-data)p t=p b;p b=p b-n ex t;q b-n ex t=p b:fr ee(p t):el

29、s e(q a=p a;p a-p a-n ex t;)w hile(p a)p t=p a;p a=p a-n ex l;q a-n ex t=p a;fr ee(p t);)w hile(p b)(p t=p b:p b=p b-n ex t;q b-n ex t=p b;fr ee(p t);p b=B:fr ee(p b):r etur n OK:)2.2 7对2.2 5题的条件作以下两点修改，对顺序表重新编写求得表C的算法。(1)假设在同一表(A或B)中可能存在值相同的元素,但要求新生成的衰C中的元素值各不相同:(2)利用A表空间存放表C。解：(1)/A、B求交，然后胴除相同元素，将

30、结果放在C表中Status Lis tCr o s s De 1 Sain e_Sq (Sq Lis t&A,Sq Lis t&B,Sq Lis t&C)(in t i=0,j=0,k=0;w hile(i A.len gth&j B.len gth)i f(A.clem i B.elem j)j+;els eif(C.len gth=0)Lis tIn s er t_Sq(C,k,A.eler ati)：k+;els eif(C.elem C.len gth-1!=A.elem i)(Lis tIn s er t_Sq(C,k,A.elem i);k-H-;i+；)r etur n OK;(

31、2)/A、B求交，然后删除相同元素，将结果放在A表中Status Lis tCr o s s DelSam e_Sq(Sq Lis t&A,Sq Lis t&B)(in t i=0,j=0,k=0：w hile(i A.len gth&j B.len gth)(if(A.elem i B.elem j)j+:els eif(k=0)A.elem k=A.elem ti;k+;)els eif(A.elem tk!=A.elem i)(A.elem k=A.elem i;k+;i+：)A.len gth=k：r etur n OK;)2.2 8对2.2 5题的条件作以下两点修改，对单链表重新编写

32、求得表C的算法。(1)假设在同一表(A或B)中可能存在值相同的元素,但要求新生成的表C中的元素值各不相同;(2)利用原表(A表或B表)中的结点构成表C,并释放A表中的无用结点空间。解：(1)/A.B求交，结果放在C表中，并删除相同元素Status Lis tCr o s s DelSam e_L(Lin kLis t&A,Lin kLis t&B,Lin kLis t&C)(Lin kLis 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 ex t：p b=p b-n ex t;

33、C=A;w hile(p a&p b)i f(p a-data data)p tp a;p a=p a-n ex t：q a-n ex t=p a:fr ee(p t);)els eif(p a-data p b-data)p t=p b;p b=p b-n ex t;q b-n ex t=p b:fr ee(p t):)els eli f(p a-data-q a-data)p t=p a;p a=p a-n ex t;q a-n ex t=p a;fr ee(p t)：)els e q a=p a;p a=p a-n ex t;)w hile(p a)p t=p a：p a=p a-n e

34、x t：q a-n cx t=p a;fr ee(p t);w hile(p b)p t=p b：p b=p b-n ex t:q b-n ex t=p b:fr ee(p t);p b=B;fr ee(p b)：r etur n OK;)(2)/A、B求交，结果放在A表中,并删除相同元素Status Lis tCr o s s DelSam e_L(Lin kLis t&A,Lin kLis t&B)(Lin kLis 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 ex t;p

35、 b=p b-n ex t：w hile(p a&p b)(if(p a-data data)(p t=p a：p a=p a-n ex t;q a-n ex t=p a;fr ee(p t);els ei f(p a-data p b-data)p t=p b：p b=p b-n ex t:q b-n ex l=p b：fr ee(p t);els eif(p a-data=q a-data)p t=p a:p a=p a-n ex t：q a-n ex t=p a：fr ee(p t);)els c(q a=p a;p a=p a-n ex t：)w hile(p a)p t=p a;p

36、a=p a-n ex t;q a-n ex t=p a;fr ee(p t);w hile(p b)(p t=p b：p b=p b-n ex l;q b-n ex t=p b;fr ee(p t);)p b=B:fr ee(p b)：r etur n OK:2.29已知A,B和C为三个递增有序的线性表，现要求对A表作如下操作：删去那些既在B表中出现乂在C表中山现的元素。试对顺序表编写实现上述操作的算法，并分析你的算法的时间复杂度(注意：题中没有特别指明同-表中的元素值各不相同)。解：在A中删除既在B中出现又在C中出现的元素，结果放在D中Status Lis tUn io r _S(i(Sq

37、Lis t&D,Sq Lis t&A,Sq Lis t&B,Sq Lis t&C)(Sq Lis t Tem p;In itLis t_Sq(Tem p):Lis tCr o s s L(B,C,Tem p);Lis tMin us L(A,Tem p,D);2.30要求同2.2 9题。试对单链表编写尊法，请释放A表中的无用结点空间。解：/在A中删除既在B中出现乂在C中出现的元素,并释放B、CStatus Lis tUn io n _L(Lin kLis t&A,Lin kLis t&B,Lin kLis t&C)Lis tCr o s s L(B,C);Lis tMin us _L(A,B)

38、;/求集合A-B,结果放在A表中,并删除B表Status Lis tMin us _L(Lin kLis t&A,Lin kLis t&B)Lin kLis 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 ex t;p b=p b-n ex t;w hile(p aft&p b)if(p b-data data)p t=p b;p b=p b-n ex t;q b-n ex t=p b：fr ee(p t):)els eif(p b-data p a-data)q a=p a;p

39、 a=p a-n ex t：els ep t=p a;p a=p a-n ex t：q a-n cx t=p a：fr ee(p t);)w hile(p b)(p t=p b;p b=p b-n ex t;q b-n ex t=p b;fr ee(p t);p b=B;fr ee(p b):r etur n OK;)2.3 1假设某个单向循环处表的长度大于1,且表中既无头结点也无头指针.已知s为指向链表中某个结点的指针，试编写算法在链表中删除指针s所指结点的前驱结点。解：/在单循环链表S中删除S的前驱结点Status Lis tDelete_CL(Lin kLis t&S)(Lin kLis

40、 t p,q:il(S=S-n ex l)r etur n ERROR;q=S：p=S-n cx t;w hile(p-n ex t!=S)q=P；p=p-n ex t：)q-n ex t=p-n ex t;fr ee(p);r etur n OK;)2.32已知有一个单向循环链表，其每个结点中含三个域:p r e,data和n ex t.其中data为数据域,n ex t为指向后继结点的指针域,p r e也为指针域，但它的值为空，试编写算法将此单向循环链表改为双向循环链表，即使p r e成为指向诃驱结点的指针域.解：/建立一个空的循环链表Status In itLis tDL(DuLin k

41、Lis l&L)(L=(DuLin kLis t)r aallo c(s iz co f(DuLNo de);if(!L)ex it(OVERFLOW);L-p r e=NULL：L-n ex t=L:r etur n OK:)/向循环傩表中插入一个结点Status Lis 1 1 n s er l_DL(DuLin kLis t&L,Elem Ty p e e)(DuLin kI.is t p;p=(DuLin kLis t)m allo c(s iz eo f(DuLNo de);if(!p)r etur n ERROR;p-data=e:p-n ex t=L-n ex t:L-n ex

42、t=p：r etur n OK;)/将单循环链表改成双向链表Status Lis tCir To Du(DuLin kLis t&L)(DuLin kLis t p,q;q=L;p=L-n ex t：w hile(p!=L)p-p r e=q;q=P；p=p-n ex t:i f(p=L)p-p r e=q;r etur n OK:)2.33已知由一个线性链表表示的线性表中含有二:类字符的数据元素(如：字母字符、数字字符和其他字符)，试编写算法将该线性表分割为:个循环链表，其中每个循环处表表示的线性表中均只含一类字符。解：/将单链表L划分成3个单循环链表Status Lis tDivideIn

43、 to 3 CL(Lin kLis t&L,Lin kLis t&s l,Lin kLis t&s 2,Lin kLis t&s 3)(Lin kLis t p,qf p tl,p t2,p t3:p=L-n ex t;p tl=s l：p t2-s 2;p t3=s 3：w hile(p)(if(p-data=*0&p-data n ex t;q-n ex t=p tl-n ex t:p tl-n ex t=q;p tl=p tl-n ex t：1els eif(p-data=*A&p-data data=，a&p-data n ex t;q-n ex t=p t2-n ex t;p t2-

44、n ex t=q:p t2=p t2-n ex t：els e(q=p:p=p-n ex t;q-n ex t=p t3-n ex t;p t3-n ex t=q:p t3=p t3-n ex t;)q=L；fr ee(q);r etur n OK;在2.3 4至2.3 6题中，“异或指针双向链表”类型Xo r L i n k e d L i s l和指针异或函数Xo r P定义为：t yp e d e f s t r u c t Xo r N o d e c h ar d at a;s t r u c t Xo r N o d e *L R P t r;Xo r N o d e,*Xo r

45、P o i n t e r;t yp e d e s t r u c t 无头结点的异或指针双向链表Xo r P o i n t e r L e ft,R i g h t：分别指向链表的左侧和右端 Xo r L i n k e d L i s t：Xo r P o i n t e r Xo r P(Xo r P o i n t e r p,Xo r P o i n t e r q);/指针异或函数Xo r P返回指针p和q的异或值2.3 4假设在算法描述语言中引入指针的二元运算“异或”，若a和b为指针,则a 8b的运算结果仍为原指针类型，且a (a b)=(a a)b-b(a b)b=a (b

46、 b)=a则可利川个指针域来实现双向链表L。链在L中的每个结点只含两个域：d at a域和L R P t r域，其中L R P t r域存放该结点的左邻与右邻结点指针(不存在时为N UL L)的异或。若设指针L L e ft指向链表中的最左结点，L.R i g h t指向链表中的最右结点，则可实现从左向右或从右向左遍历此双向链表的操作。试写一算法按任一方向依次输出链表中各元素的值。解：S t at u s T r av e r s i n g L i n k L i s t(Xo r L i n k e d L i s t&L,c h ar d)(Xo r P o i n t e r p,l

47、e ft,r i g h t;i f(d=l|d-L)p=L L e ft;l e ft=N UL L;w h i l e(p!=N UL L)V i s i t i n g Dat a(p-d at a);l e ft=p;p=Xo r P(l e ft,p-l.R P t r);e l s ei f(d=f r*|d=R)p=L.R i g h t;r i g h l=N UL L：w h i l e(p!=N UL L)V i s i t i n g Dal a(p-d at a):r i g h t=p;p=Xo r P(p-L R P t r,r i g h t)：)e l s e

48、r e t u r n ER R O R:r e t u r n O K;)2.35采用2.3 4题所述的存储结构，写出在第i个结点之前插入一个结点的算法。2.3 6采用2.3 4题所述的存储结构，写出删除第i个结点的算法。2.37设 以 带 头 结 点 的 双 向 循 环 链 表 表 示 的 线 性 表L=(。卜。？，).试 写 一 时 间 复 杂 度05)的 算 法，将L改造为心 二(四,。3,，%，%，电)解：/将双向链表 L=(al,a2.an)改造为(al,a3.an,.,a2)S t at u s L i s t Ch an g e _Du L(Du L i n k L i s t

49、&L)i n t i;Du L i n k L i s l p,q,r;p=L-n e x l;r=L-p r e;i=l：w h i l e(p!=r)i f(i%2=0)(Q=P；p=p-n e x t:/删除结点q-p r e-n e x l=q-n e x t;q-n c x t-p r e=q-p r e;/插入到头结点的左面q-p r e=r-n e x t-p r e;r-n e x t-p r e=q;q-n e x t=r-n e x t:r-n e x t=q：Ie l s e p=p-n e x l;i+；)r e t u r n O K;)2.38设有一个双向循环链表,

50、每个结点中除有p r e,d at a和n e x t三个域外,还增设了 个访问频度域fr e q。在链表被起用之前,频度域fr e q的值均初始化为零,而每当对链衣进行一次L o c al e。,X)的操作后，被访问的结点(即元素值等于x的结点)中的频度域fr e q的值便增1,同时调整链表中结点之间的次序，使其按访问频度非递增的次序顺序排列，以便始终保持被频繁访问的结点总是靠近表头结点。试编写符合上述要求的L o ca t e操作的算法。解：Du L i n k L i s t L i s t L o ca t e _ Du L(Du L i n k L i s t&L,El e m T