第2章算法答案.doc

2.1 设线性表存于a1.arrsize的前elenum个分量中, 且递增有序. 试写一算法,将x插入到线性表的适当位置, 以保持线性表的有序性。设计思想：(1) 先查找 x 的插入位置 i ；(2) 将线性表中自Ai至Aelenum的元素后移一个位置；(3) 最后将x查入到Ai中， 并且将表长加1。算法：proc ds0201(var a:array1.size of integer; var elenum:integer; x:integer); if elenum=size then error(array overflow) else i:=elenum; while (i=1) cand (x=0)and(1=i+k=last)and(0=last=array) then for j:=i+k to last do aj-k:=aj; 前移k个元素 last:=last-k; 表长k else error(入口参数错误)endp; ds02022.3已知两个线性表va和vb，且顺序存储，其值递增排列，要求将它们归并成一个新的有序表vc。设计思想：(1) 当线性表va和线性表vb均未结束时，比较，将较小数存于线性表vc;(2) 若一线性表结束，将另一线性表存于vc。算法：PROC ds0203(va,vb:sqlisttp;VAR vc:sqlisttp); i:=1;j:=1;k:=0; 指针初始化 WHILE (i=va.last) AND (j=vb.last) DO 归并 IF va.elemi=vb.elemj THEN vc.elemk+1:=va.elemi;k:=k+1;i:=i+1 ELSE vc.elemk+1:=vb.elemj;k:=k+1;j:=j+1; WHILE i=va.last DO 插入VA的剩余段 vc.elemk+1:=va.elemi;k:=k+1;i:=i+1; WHILE j=vb.last DO 插入VB的剩余段 vc.elemk+1:=vb.elemj;k:=k+1;j:=j+1; vc.last:=k K为VC中元素个数ENDP;ds02032.5写出在带头结点的动态单链表结构上实现线性表操作 一. LOCATE(L,X) 二. LENGTH(L)的算法一. 设计思想： 用x与每一元素结点的数据域的值进行比较，若等于x，表示查找成功，否则，查找失败。算法：proc ds0205_1(ha:pointer; x:datatype); ha:带头结点的单链表的头指针 p:=ha.next; p:指向第一个元素结点 while (pnil) cand p.datax do p:=p.next; 当p不空并且p.data不等于x时, p后移 return(p); 成功: pnil ; 失败:p=nilend; ds0205_1二. 设计思想： 逐一访问每一结点并计数, 即可得此链表的长度。算法：proc ds0205_2(ha:pointer; x:datatype); ha:带头结点的单链表的头指针 p:=ha; p:指向头结点 len:=0; while (p.nextnil) do p:=p.next; len:=len+1 当p不空x时, 访问其结点, 并计数 return(len); len:即为此链表的长度)end; ds0205_22.6已知ha和hb分别指向两个单链表的头结点, 且头结点的数据域(整型)中存放链表的长度, 写一算法将这两个链表接在一起, 并要求以尽可能短的时间完成。设计思想：(1) 比较ha和hb两链表, 找较短链；(2) 沿较短链找到最后一个结点；(3) 将两链连接上。算法：proc ds0206(var hc:pointer; ha,hb:pointer); ha,hb,hc:带头结点的单链表的头指针,其中hc是新生成的) pc:=ha; hc:新生成的链表的头指针, 利用原空间 if ha.data hb.data then p:=ha; q:=hb.next else p:=hb; q:=ha.next p指向较短链, q指向较长链 while (p.nextnil) do p:=p.next; 沿较短的链表查找至链表尾端 当p.next 不空, p后移, 找到此链表中的最后一个结点 p.next := q 两链表链接上)end; ds02062.7已知线性表中的元素按值递增排列, 并以单链表作存储结构. 写一高效算法, 删除表中所有值大于mink且小于maxk的元素(若表中存在这样的元素)。设计思想：(1) 从第一个结点开始找其值minK的结点p(它的前趋结点为q)；(2) 保存q, 从p开始找所有值=maxk的结点, 并删除每个这样的p结点；(3) q.next指向p。算法：proc ds0207(var h:pointer; mink,maxk:integer); h:带头结点的单链表的头指针, q:=h; p:=h.next; while (pnil) and (p.datamink的结点, q是p的前趋 while (pnil) and (p.datamink并且maxk的结点p q.next:=pendp; ds02072.8已知线性表中的元素按值递增排列, 并以单链表作存储结构. 写一高效算法, 删除表中的多余元素, 使得运算后的线性表中所有元素的值均不相同。设计思想： 从第一个结点开始, 每一结点的值与后一结点的值作比较 , 若相等, 则删除后一结点, 直至整个链表结束。算法：proc ds0208(var h:pointer); h:带头结点的单链表的头指针, p:=h.next; while p.nextnil do if p.data=p.next.data then u:=p; p:=p.next; dispose(u) 删除相同值的结点 else q:=p; p:=p.next ; p后移endp; ds02082.9以一维数组和链表作存储结构, 实现线性表就地逆置的算法, 即将线性表(a1,a2,.an)=(an,.,a2,a1)一. 以一维数组为存储结构：设计思想： 用a1与an交换，a2与an-1交换，以此类推，直至n div 2止。算法：proc ds0209_1(a:array 1.n of elemtp; n:integer); a:顺序存储的线性表, 表中有n个数据元素 for i:=1 to n div 2 do aian-i+1;end; ds0209_1二. 以链表为存储结构：设计思想：(1) 取出原链表(a1,.an序)中的一结点(2) 插入到新链表(an,.,a1序)的表头处(3) 重复(1)和(2)步, 直到原链表空止。算法：proc ds0209_2(var ha,hb:pointer); ha,hb:单链表的头指针 hb:=nil; 新链表置初值 while hanil do 原表不空,执行 p:=ha; ha:=ha.next; p.next:=hb; hb:=p; end; ds0209_22.10设有两个按元素值递增有序排列的线性表A和B, 均以单链表作存储结构, 写一算法将A表和B表归并成一个按元素值递增有序排列(允许值相同)的线性表C.设计思想：(1) 当A表和B表都不空时, 进行比较, 将较小数链入C表表尾, 以保证其递增性;(2) 若某一链表空, 将另一链表接在C表之后。算法：proc ds0210(var hc:pointer; ha,hb:pointer); ha,hb,hc分别为A链.B链和C链的头指针 pa:ha; pb:=hb; new(hc); rc:=hc; 生成新链表的头结点, hc:头指针, rc:尾指针 while (panil) and (pbnil) do A,B表不空 if pa.data=pb.data then s:=pa; pa:=pa.next else s:=pb; pb:=pb.next ; rc.next:=s; rc:=s if pa=nil then rc.next:=pb else rc.next:=pa;endp; ds02102.11设有两个按元素值递增有序排列的线性表A和B, 均以单链表作存储结构, 写一算法将A表和B表归并成一个按元素值非递增有序排列(允许值相同)的线性表C.设计思想(1) 当A表和B表都不空时, 进行比较, 将较小数插入C表表首, 以保证其递减性；(2) 若某一链表空, 将另一链表剩余部分依次插入在C表的表首。算法：proc ds02011(var hc:pointer; ha,hb:pointer); ha,hb,hc分别为A链.B链和C链的头指针 pa:=ha; pb:=hb; new(hc); 生成新链表的头结点 while (panil) and (pbnil) do A,B表不空 if pa.data=pb.data then s:=pa; pa:=pa.next else s:=pb; pb:=pb.next ; s.next:=hc.next; hc.next:=s while panil do s:=pa; pa:=pa.next ; s.next:=hc.next; hc.next:=s while pbnil do s:=pb; pb:=pb.next; s.next:=hc.next; hc.next:=s endp;ds020112.12 已知A、B和C为以链表存储的三个递增有序的线性表，对A作如下运算：删除那些在B中出现又在C中出现的元素。设计思想 从A表中取出每一个元素p.data，检查是否出现在B表和C表中，是，则删除P。 注意：应保留p的前趋算法：proc ds02012(var ha:pointer; hb,hc:pointer); ha,hb,hc分别为A链.B链和C链的头指针 pre:=ha; pa:=ha.next; pre:pa的前趋 pb:=hb.next; pc:=hc.next; pb,pc:总指向hb,hc链的最后一个已考查的结点 while panil do A表不空 x:=pa.data; while (pbnil)and (pb.datax) do pb:=pb.next 当pb不空时，找等于x的结点pb while (pcnil)and (pc.datax) do pc:=pc.next 当pc不空时，找等于x的结点pb if (pbnil)and (pb.data=x)and(pcnil)and (pc.data=x) x在B中出现同时又在c中出现 then pre.next:=pa.next; dispose(pa); 删除pa pa:=pre.next pa:接着考察下一结点 else pre:=pa; p:=pa.nextpa后移 endp;ds020122.13n个人坐在圆桌边, 从第s人开始报数, 报到第m人出列, 再从下一人开始报, 直至所有的人都出列为止。 设n=8,s=1,m=4 。 则出列次序为: 4,8,5,2,1,3,7,6设计思想： 以循环链表存储，且不应有头结点； 在循环链表中查找，到第m处，删除（报数）算法：proc ds0213(var la:pointer，m,n:integer); p:=la;从第p人开始报数 FOR i:=1 TO n-1 DO FOR j:=1 TO m-1 DO p:=p.next; p定位于要出列人之前 write(p.next.data); 报数 s:=p.next; p.next:=s.next; dispose(s); 出列 p:=p.next;从第p人开始报数 write(p.data); dispose(p);最后一人报数, 并出列end; ds02142.14已知单向循环链表表示的线性表中含有三全域:pre、data和next, 其中 data为数据域,next为指针域,其值为后继, pre也是指针域, 其值为NIL. 写一算法, 将此链改为双向链表。设计思想： 检查链表中的每一结点, 若其pre为空, 则将它指向其前趋结点。 算法：proc ds0215(var ha:dpointer); ha链表的头指针 p:=ha; while p.next.prenil do p.next.pre:=p; p:=p.next endp; ds02152.15写出双向链表倒置的算法.设计思想： p从next方向，q从pre方向逐一对两个结点的数据进行交换，直至p=q或p.pre=q止，使得双向链表被倒置。算法：proc ds0216(var dh:dpointer); dh:指向双向循环链表的头结点 q:=dh.pre; q沿前趋指针方向 p:=dh.next; p沿后继指针方向 while (pq) and (p.preq) do q.datap.datat; p:=p.next; q:=q.pre end; ds02162.16在其元素值按递增排序的双向链表中增加一个freq频度域(初值为0), 每当进行LOCATE(L,X)运算时, X结点的freq加1, 写一算法完成LOCATE(L,X), 并保证其有序性。设计思想：(1) 从第一个结点开始，逐一比较每一结点的数据中是否当等于x，若相等，则转(2)；(2) x结点的freq+1，从x结点开始向前以freq比较，找到x结点的恰当位置，保证其递减性。算法：proc ds0216(var h:dpointer; x:elemtp); h带头结点的链表的头指针, 头结点的freq=max p:=h.next; p指向第一个元素结点 while (pnil) and (p.datax) do p:=p.next if p=nil then error(没找到)else p.freq:=P.freq+1;q:=p.pre; while q.freqpfreq do q:=q.pre; if q.nextp then p.pre.next:=p.next; p.next.pre:=p.pre; 删p q.next.pre:=p; p.next:=q.next; p.pre:=q; q.next:=p; p插入到q之后 end; ds0