第2章算法答案

2.1设线性表存于a[l..arrsize]的前elenum个分量中，旦递增有序.试写一算法，将x插入到线性表的适当位置，以保持线性表的有序性。设计思想：先查找x的插入位置i;⑵将线性表中自A[i]至AEelenum]的元素后移一个位置；(3)最后将x查入到A[i]中，并旦将表长加1。算法：procds0201(vara：array[1..size,ofinteger;varelenum:integer;x：integer);ifelenum=sizethenerrorCarrayoverflow')elseEi:=elenum;while(i>=l)cand(x<a[i])do[a[i+l]：=a[i];i：=i-l];｛查找插入位置，并后移｝a[i+l]：=x;elenum：=elenum+l]endp;｛ds0201｝2.2巳知线性表存于a[l..array]中的前last个分量中，删除从第i个元素起的k个元素。设计思想：将k个元素一次删除，即从i+k开始，每一元素前移k个元素位置。算法：procds0202(vara：array[1..size,ofinteger;varlast:integer;i,k：integer);if(k>=0)and(l<=i+k<=last)and(0<=last<=array)then[forj:二i+ktolastdoa[j-k]：=a[j];｛前移k个元素｝last：=last~k;｛表长一k｝]elseerror入「I参数错误')endp;｛ds0202｝2.3已知两个线性表va和vb,且顺序存储，其值递增排列，要求将它们归并成一个新的有序表vc。设计思想：当线性表va和线性表vb均未结束时，比较，将较小数存于线性表vc;若一线性表结束，将另一线性表存于vc。算法：PROCds0203(va,vb:sqlisttp;VARvc:sqlisttp);i:=l;j:=l;k:=O; ｛指针初始化｝WHILE(i<=va.last)AND(j<=vb.last)DO｛归并｝IFva.elem[ij<=vb.elem[j]THEN[vc.elem[k+l]：=va.elem[i];k:=k+1;i:=i+l]ELSE[vc.elem[k+l]:=vb.elem[j];k:=k+1;j:=j+l];WHILEi<=va.lastDO｛插入VA的剩余段｝[vc.elem[k+l]：=va.elem[i];k：=k+l;i：=i+1];WHILEj<=vb.lastDO｛插入VB的剩余段｝[vc.elem[k+l]：=vb.elem[j];k：=k+l;j：=j+l];vc.last：=k ｛K为VC中元素个数｝ENDP;(ds0203｝2.5写出在带头结点的动态单链表结构上实现线性表操作LOCATE(L,X)LENGTH(L)的算法设计思想：用x与每一元素结点的数据域的值进行比较，若等于x,表示查找成功，否则，查找失败。算法：procds0205_l(ha:pointer;x：datatype);(ha：带头结点的单链表的头指针｝p：=ha\next;｛p：指向第一个元素结点｝while(pOnil)candp'.dataOxdop：=p.next;｛当p不空并且p".data不等于x时，p后移｝return(p);｛成功:pOnil;失败:p=nil｝end;(ds0205_l｝设计思想：逐一访问每一结点并计数，即可得此链表的长度。算法：procds0205_2(ha:pointer;x：datatype);(ha：带头结点的单链表的头指针｝P：=ha;｛p：指向头结点｝len：=0;while(p\nextOnil)do[p：=p.next;len：=len+l]｛当P不空x时，访问其结点，并计数｝return(len);｛len：即为此链表的长度)end;(ds0205_2｝2.6已知ha和hb分别指向两个单链表的头结点，旦头结点的数据域(整型)中存放链表的长度，写一算法将这两个链表接在一起，并要求以尽可能短的时间完成。设计思想：比较ha和hb两链表，找较短链；沿较短链找到最后一个结点；将两链连接上。算法：procds0206(varhe:pointer;ha,hb:pointer);(ha,hb,hc：带头结点的单链表的头指针，其中he是新生成的)pc：=ha;{he：新生成的链表的头指针，利用原空间}ifha一・data<hb\datathen[p:=ha:q：=hb*.next]else[p:=hb:q：=ha*.next]{P指向较短链，q指向较长链}while(p*.nextOnil)dop:=p\next;{沿较短的链表查找至链表尾端}{当p\next不空，p后移，找到此链表中的最后一个结点}p\next：=q{两链表链接上)end;{ds0206}2.7已知线性表中的元素按值递增排列，并以单链表作存储结构.写一高效算法，删除表中所有值大于mink且小于maxk的元素(若表中存在这样的元素)o设计思想：从第一个结点开始找其值〉minK的结点p(它的前趋结点为q);保存q,从p开始找所有值〈二maxk的结点，并删除每个这样的p结点：q\next指向p。算法：procds0207(varh:pointer;mink,maxk:integer);(h:带头结点的单链表的头指针,}q：=h;p：=h\next;while(pOnil)and(p".data<=mink)do[q：=p;p：=p・next];{p：其值>mink的结点，q是p的前趋}while(pOnil)and(p".data<maxk)do[u:=p;p:=p.next;dispose(p)];(删除所有的其值>mink井且<maxk的结点p}q.next:二pendp;{ds0207}2.8已知线性表中的元素按值递增排列，并以单链表作存储结构.写一高效算法，删除表中的多余元素，使得运算后的线性表中所有元素的值均不相同。设计思想：从第一个结点开始，每一结点的值与后一结点的值作比较，若相等，则删除后一结点，直至整个链表结束。算法：procds0208(varh：pointer);{h：带头结点的单链表的头指针,}p：=h.next;whilep\nextOnildoifp".data二p.next",datathen[u：=p;p：=p~.next;dispose(u)](删除相同值的结点}else[q：=p;p：=p'.next];{p后移}endp;{ds0208}2.9以一维数组和链表作存储结构，实现线性表就地逆置的算法，即将线性表(al,q.2,...an)—>(an,...,a2,al)以一维数组为存储结构：设计思想：用a[l]与a[n]交换，a[2]与a[nT]交换，……,以此类推，直至ndiv2止。算法：procds0209_l(a:array[1..n]ofelemtp;n：integer);{a：顺序存储的线性表，表中有n个数据元素}fori：=1tondiv2doa[i]*—a[n-i+l];end;{ds0209_l}以链表为存储结构：设计思想：取出原链表(al,...an序)中的一结点插入到新链表(an,...,al序)的表头处重复(1)和(2)步，直到原链表空止。算法：procds0209_2(varha,hb：pointer);{ha,hb：单链表的头指针}hb：=nil;{新链表置初值}whilehaOnildo{原表不空,执行}[p：=ha;ha:二ha.next;p".next：=hb;hb：=p;]end;(ds0209_2}2.10设有两个按元素值递增有序排列的线性表A和B,均以单链表作存储结构，写一算法将A表和B表归并成一个按元素值递增有序排列(允许值相同)的线性表C.设计思想：当A表和B表都不空时，进行比较，将较小数链入C表表尾，以保证其递增性;若某一链表空，将另一链表接在C表之后。算法：procds0210(varhe:pointer;ha,hb:pointer);(ha,hb,he分别为A链.B链和C链的头指针｝pa：ha;pb：=hb;new(he);re:=hc;｛生成新链表的头结点，he：头指针，re：尾指针｝while(paOnil)and(pbOnil)do｛A,B表不空｝[ifpa\data<=pb".datathen[s:=pa;pa:二pa.next]else[s：=pb;pb：=pb.next];Are.next:=s;re:=s]ifpa=nilthenre.next:=pbelsere.next:=pa;endp;｛ds0210｝2.11设有两个按元素值递增有序排列的线性表A和B,均以单链表作存储结构，写一算法将A表和B表归并成一个按元素值非递增有序排列(允许值相同)的线性表C.设计思想当A表和B表都不空时，进行比较，将较小数插入C表表首，以保证其递减性;若某一链表空，将另一链表剩余部分依次插入在C表的表首。算法：procds02011(varhe:pointer;ha,hb:pointer);(ha,hb,he分别为A链.B链和C链的头指针｝pa:=ha;pb:=hb;new(he); ｛生成新链表的头结点｝while(paOnil)and(pbOnil)do｛A,B表不空｝[ifpa\data<=pb".datathen[s:=pa;pa:二pa.next]else[s：=pb;pb:=pb.next];s*.next：=hc.next;he*,next:=s]whilepaOnildo[s:=pa;pa：=pa".next;s*.next：=hc.next;he*,next:=s]whilepbOnildo[s:=pb;pb：=pb".next;s*.next：=hc.next;he*,next:=s]endp;｛ds02011｝2.12已知A、B和C为以链表存储的三个递增有序的线性表，对A作如下运算：删除那些在B中出现又在C中出现的元素。设计思想从A表中取出每一个元素pLdata,检查是否出现在B表和C表中，是，则删除P。注意：应保留P的前趋算法：procds02012(varha：pointer;hb,he：pointer);(ha,hb,he分别为A链.B链和C链的头指针｝pre：=ha;pa：=ha",next;｛pre：pa的前趋｝pb：=hb".next;pc：=he",next;｛pb,pc:总指向hb,he链的最后一个己考查的结点｝whilepaOnildo｛A表不空｝[x：=pa.data;while(pbOnil)and(pb.dataOx)dopb：=pb.next｛当pb不空时，找等于x的结点pb｝while(pcOnil)and(pc.dataOx)dopc：=pc.next｛当pc不空时，找等于x的结点pb｝if(pbOnil)and(pb\data=x)and(pcOnil)and(pc\data=x)｛x在B中出现同时又在c中出现｝then[pre",next：=pa.next;dispose(pa);｛删除pa｝pa：=pre",next｛pa：接着考察下一结点｝1else[pre：=pa;p：=pa.next｛pa后移｝]endp;(ds02012)2.13n个人坐在圆桌边，从第s人开始报数，报到第m人出列，再从下一人开始报，直至所有的人都出列为止。设n=8,s=l,m=4。则出列次序为：4,8,5,2,1,3,7,6设计思想：以循环链表存储，旦不应有头结点；在循环链表中查找，到第m处，删除(报数)算法：procds0213(varla：pointer»m,n：integer);P：=la;｛从第p人开始报数｝FORi:=lTOn-1DO[FORj:=lTOm-1DOp：=p'.next;｛p定位于要出列人之前｝write(p.next",data);｛报数｝s：=p.next";p.next：=s".next;dispose(s);｛出歹U｝p：=p".next;｛从第p人开始报数｝]write(p".data);dispose(p);｛最后一■人报数，并出列｝end;(ds0214｝2.14已知单向循环链表表示的线性表中含有三全域:pre、data和next,其中data为数据域,next为指针域,其值为后继，pre也是指针域，其值为NIL.写一算法，将此链改为双向链表。设计思想：检查链表中的每一结点，若其pre为空，则将它指向其前趋结点。算法：procds0215(varha：dpointer);{ha链表的头指针}p：二ha;whilep".next.pre=nildo[p~.next,pre：=p;p：=p.next]endp;(ds0215}2.15写出双向链表倒置的算法.设计思想：p从next方向，q从pre方向逐一对两个结点的数据进行交换，直至p=q或p\pre=qjl：,使得双向链表被倒置。算法：procds0216(vardh：dpointer);{dh：指向双向循环链表的头结点}q：=dh\pre;{q沿前趋指针方向}p：=dh\next;{p沿后继指针方向}while(p<>q)and(p'.preOq)do[q".data—fp".datat;p：=p.next;q：=q.pre]end;{ds0216}2.16在其元素值按递增排序的双向链表中增加一个freq频度域(初值为0),每当进行LOCATE(L,X)运算时，X结点的freq加1,写一算法完成LOCATE(L,X),并保证其有序性。设计思想：从第一个结点开始，逐一比较每一结点的数据中是否当等于x,若相等，则转(2)；x结点的freq+1,从x结点开始向前以freq比较，找到x结点的恰当位置，保证其递减性。算法：procds0216(varh：dpointer;x：elemtp);(h带头结点的链表的头指针，头结点的freq=max}p：=h\next;{p指向第一■个元素结点}while(pOnil)and(p*.dataOx)dop：=p".nextifp=nilthenerrorC没找到')else[p\freq：=P\freq+1;q：=p.pre;whileq".freq<p*freqdoq：二qLpre;ifq.nextOpthenLp.pre",next:=p.next;p".next~.pre：=p".pre;｛删p｝q・next*,pre:=p;p・next:=q\next;pLpre：=q;q\