第2章算法答案

2.1設(shè)線性表存于a[l..arrsize]的前elenum個(gè)分量中，旦遞增有序.試寫一算法，將x插入到線性表的適當(dāng)位置，以保持線性表的有序性。設(shè)計(jì)思想：先查找x的插入位置i;⑵將線性表中自A[i]至AEelenum]的元素后移一個(gè)位置；(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]中的前l(fā)ast個(gè)分量中，刪除從第i個(gè)元素起的k個(gè)元素。設(shè)計(jì)思想：將k個(gè)元素一次刪除，即從i+k開始，每一元素前移k個(gè)元素位置。算法：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個(gè)元素｝last：=last~k;｛表長一k｝]elseerror入「I參數(shù)錯(cuò)誤')endp;｛ds0202｝2.3已知兩個(gè)線性表va和vb,且順序存儲(chǔ)，其值遞增排列，要求將它們歸并成一個(gè)新的有序表vc。設(shè)計(jì)思想：當(dāng)線性表va和線性表vb均未結(jié)束時(shí)，比較，將較小數(shù)存于線性表vc;若一線性表結(jié)束，將另一線性表存于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中元素個(gè)數(shù)｝ENDP;(ds0203｝2.5寫出在帶頭結(jié)點(diǎn)的動(dòng)態(tài)單鏈表結(jié)構(gòu)上實(shí)現(xiàn)線性表操作LOCATE(L,X)LENGTH(L)的算法設(shè)計(jì)思想：用x與每一元素結(jié)點(diǎn)的數(shù)據(jù)域的值進(jìn)行比較，若等于x,表示查找成功，否則，查找失敗。算法：procds0205_l(ha:pointer;x：datatype);(ha：帶頭結(jié)點(diǎn)的單鏈表的頭指針｝p：=ha\next;｛p：指向第一個(gè)元素結(jié)點(diǎn)｝while(pOnil)candp'.dataOxdop：=p.next;｛當(dāng)p不空并且p".data不等于x時(shí)，p后移｝return(p);｛成功:pOnil;失敗:p=nil｝end;(ds0205_l｝設(shè)計(jì)思想：逐一訪問每一結(jié)點(diǎn)并計(jì)數(shù)，即可得此鏈表的長度。算法：procds0205_2(ha:pointer;x：datatype);(ha：帶頭結(jié)點(diǎn)的單鏈表的頭指針｝P：=ha;｛p：指向頭結(jié)點(diǎn)｝len：=0;while(p\nextOnil)do[p：=p.next;len：=len+l]｛當(dāng)P不空x時(shí)，訪問其結(jié)點(diǎn)，并計(jì)數(shù)｝return(len);｛len：即為此鏈表的長度)end;(ds0205_2｝2.6已知ha和hb分別指向兩個(gè)單鏈表的頭結(jié)點(diǎn)，旦頭結(jié)點(diǎn)的數(shù)據(jù)域(整型)中存放鏈表的長度，寫一算法將這兩個(gè)鏈表接在一起，并要求以盡可能短的時(shí)間完成。設(shè)計(jì)思想：比較ha和hb兩鏈表，找較短鏈；沿較短鏈找到最后一個(gè)結(jié)點(diǎn)；將兩鏈連接上。算法：procds0206(varhe:pointer;ha,hb:pointer);(ha,hb,hc：帶頭結(jié)點(diǎn)的單鏈表的頭指針，其中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;{沿較短的鏈表查找至鏈表尾端}{當(dāng)p\next不空，p后移，找到此鏈表中的最后一個(gè)結(jié)點(diǎn)}p\next：=q{兩鏈表鏈接上)end;{ds0206}2.7已知線性表中的元素按值遞增排列，并以單鏈表作存儲(chǔ)結(jié)構(gòu).寫一高效算法，刪除表中所有值大于mink且小于maxk的元素(若表中存在這樣的元素)o設(shè)計(jì)思想：從第一個(gè)結(jié)點(diǎn)開始找其值〉minK的結(jié)點(diǎn)p(它的前趨結(jié)點(diǎn)為q);保存q,從p開始找所有值〈二maxk的結(jié)點(diǎn)，并刪除每個(gè)這樣的p結(jié)點(diǎn)：q\next指向p。算法：procds0207(varh:pointer;mink,maxk:integer);(h:帶頭結(jié)點(diǎn)的單鏈表的頭指針,}q：=h;p：=h\next;while(pOnil)and(p".data<=mink)do[q：=p;p：=p?next];{p：其值>mink的結(jié)點(diǎn)，q是p的前趨}while(pOnil)and(p".data<maxk)do[u:=p;p:=p.next;dispose(p)];(刪除所有的其值>mink井且<maxk的結(jié)點(diǎn)p}q.next:二pendp;{ds0207}2.8已知線性表中的元素按值遞增排列，并以單鏈表作存儲(chǔ)結(jié)構(gòu).寫一高效算法，刪除表中的多余元素，使得運(yùn)算后的線性表中所有元素的值均不相同。設(shè)計(jì)思想：從第一個(gè)結(jié)點(diǎn)開始，每一結(jié)點(diǎn)的值與后一結(jié)點(diǎn)的值作比較，若相等，則刪除后一結(jié)點(diǎn)，直至整個(gè)鏈表結(jié)束。算法：procds0208(varh：pointer);{h：帶頭結(jié)點(diǎn)的單鏈表的頭指針,}p：=h.next;whilep\nextOnildoifp".data二p.next",datathen[u：=p;p：=p~.next;dispose(u)](刪除相同值的結(jié)點(diǎn)}else[q：=p;p：=p'.next];{p后移}endp;{ds0208}2.9以一維數(shù)組和鏈表作存儲(chǔ)結(jié)構(gòu)，實(shí)現(xiàn)線性表就地逆置的算法，即將線性表(al,q.2,...an)—>(an,...,a2,al)以一維數(shù)組為存儲(chǔ)結(jié)構(gòu)：設(shè)計(jì)思想：用a[l]與a[n]交換，a[2]與a[nT]交換，……,以此類推，直至ndiv2止。算法：procds0209_l(a:array[1..n]ofelemtp;n：integer);{a：順序存儲(chǔ)的線性表，表中有n個(gè)數(shù)據(jù)元素}fori：=1tondiv2doa[i]*—a[n-i+l];end;{ds0209_l}以鏈表為存儲(chǔ)結(jié)構(gòu)：設(shè)計(jì)思想：取出原鏈表(al,...an序)中的一結(jié)點(diǎn)插入到新鏈表(an,...,al序)的表頭處重復(fù)(1)和(2)步，直到原鏈表空止。算法：procds0209_2(varha,hb：pointer);{ha,hb：單鏈表的頭指針}hb：=nil;{新鏈表置初值}whilehaOnildo{原表不空,執(zhí)行}[p：=ha;ha:二ha.next;p".next：=hb;hb：=p;]end;(ds0209_2}2.10設(shè)有兩個(gè)按元素值遞增有序排列的線性表A和B,均以單鏈表作存儲(chǔ)結(jié)構(gòu)，寫一算法將A表和B表歸并成一個(gè)按元素值遞增有序排列(允許值相同)的線性表C.設(shè)計(jì)思想：當(dāng)A表和B表都不空時(shí)，進(jìn)行比較，將較小數(shù)鏈入C表表尾，以保證其遞增性;若某一鏈表空，將另一鏈表接在C表之后。算法：procds0210(varhe:pointer;ha,hb:pointer);(ha,hb,he分別為A鏈.B鏈和C鏈的頭指針｝pa：ha;pb：=hb;new(he);re:=hc;｛生成新鏈表的頭結(jié)點(diǎn)，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設(shè)有兩個(gè)按元素值遞增有序排列的線性表A和B,均以單鏈表作存儲(chǔ)結(jié)構(gòu)，寫一算法將A表和B表歸并成一個(gè)按元素值非遞增有序排列(允許值相同)的線性表C.設(shè)計(jì)思想當(dāng)A表和B表都不空時(shí)，進(jìn)行比較，將較小數(shù)插入C表表首，以保證其遞減性;若某一鏈表空，將另一鏈表剩余部分依次插入在C表的表首。算法：procds02011(varhe:pointer;ha,hb:pointer);(ha,hb,he分別為A鏈.B鏈和C鏈的頭指針｝pa:=ha;pb:=hb;new(he); ｛生成新鏈表的頭結(jié)點(diǎn)｝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為以鏈表存儲(chǔ)的三個(gè)遞增有序的線性表，對(duì)A作如下運(yùn)算：刪除那些在B中出現(xiàn)又在C中出現(xiàn)的元素。設(shè)計(jì)思想從A表中取出每一個(gè)元素pLdata,檢查是否出現(xiàn)在B表和C表中，是，則刪除P。注意：應(yīng)保留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鏈的最后一個(gè)己考查的結(jié)點(diǎn)｝whilepaOnildo｛A表不空｝[x：=pa.data;while(pbOnil)and(pb.dataOx)dopb：=pb.next｛當(dāng)pb不空時(shí)，找等于x的結(jié)點(diǎn)pb｝while(pcOnil)and(pc.dataOx)dopc：=pc.next｛當(dāng)pc不空時(shí)，找等于x的結(jié)點(diǎn)pb｝if(pbOnil)and(pb\data=x)and(pcOnil)and(pc\data=x)｛x在B中出現(xiàn)同時(shí)又在c中出現(xiàn)｝then[pre",next：=pa.next;dispose(pa);｛刪除pa｝pa：=pre",next｛pa：接著考察下一結(jié)點(diǎn)｝1else[pre：=pa;p：=pa.next｛pa后移｝]endp;(ds02012)2.13n個(gè)人坐在圓桌邊，從第s人開始報(bào)數(shù)，報(bào)到第m人出列，再從下一人開始報(bào)，直至所有的人都出列為止。設(shè)n=8,s=l,m=4。則出列次序?yàn)椋?,8,5,2,1,3,7,6設(shè)計(jì)思想：以循環(huán)鏈表存儲(chǔ)，旦不應(yīng)有頭結(jié)點(diǎn)；在循環(huán)鏈表中查找，到第m處，刪除(報(bào)數(shù))算法：procds0213(varla：pointer?m,n：integer);P：=la;｛從第p人開始報(bào)數(shù)｝FORi:=lTOn-1DO[FORj:=lTOm-1DOp：=p'.next;｛p定位于要出列人之前｝write(p.next",data);｛報(bào)數(shù)｝s：=p.next";p.next：=s".next;dispose(s);｛出歹U｝p：=p".next;｛從第p人開始報(bào)數(shù)｝]write(p".data);dispose(p);｛最后一■人報(bào)數(shù)，并出列｝end;(ds0214｝2.14已知單向循環(huán)鏈表表示的線性表中含有三全域:pre、data和next,其中data為數(shù)據(jù)域,next為指針域,其值為后繼，pre也是指針域，其值為NIL.寫一算法，將此鏈改為雙向鏈表。設(shè)計(jì)思想：檢查鏈表中的每一結(jié)點(diǎn)，若其pre為空，則將它指向其前趨結(jié)點(diǎn)。算法：procds0215(varha：dpointer);{ha鏈表的頭指針}p：二ha;whilep".next.pre=nildo[p~.next,pre：=p;p：=p.next]endp;(ds0215}2.15寫出雙向鏈表倒置的算法.設(shè)計(jì)思想：p從next方向，q從pre方向逐一對(duì)兩個(gè)結(jié)點(diǎn)的數(shù)據(jù)進(jìn)行交換，直至p=q或p\pre=qjl：,使得雙向鏈表被倒置。算法：procds0216(vardh：dpointer);{dh：指向雙向循環(huán)鏈表的頭結(jié)點(diǎn)}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在其元素值按遞增排序的雙向鏈表中增加一個(gè)freq頻度域(初值為0),每當(dāng)進(jìn)行LOCATE(L,X)運(yùn)算時(shí)，X結(jié)點(diǎn)的freq加1,寫一算法完成LOCATE(L,X),并保證其有序性。設(shè)計(jì)思想：從第一個(gè)結(jié)點(diǎn)開始，逐一比較每一結(jié)點(diǎn)的數(shù)據(jù)中是否當(dāng)?shù)扔趚,若相等，則轉(zhuǎn)(2)；x結(jié)點(diǎn)的freq+1,從x結(jié)點(diǎn)開始向前以freq比較，找到x結(jié)點(diǎn)的恰當(dāng)位置，保證其遞減性。算法：procds0216(varh：dpointer;x：elemtp);(h帶頭結(jié)點(diǎn)的鏈表的頭指針，頭結(jié)點(diǎn)的freq=max}p：=h\next;{p指向第一■個(gè)元素結(jié)點(diǎn)}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\