《第2章算法答案.doc》由会员分享，可在线阅读，更多相关《第2章算法答案.doc（9页珍藏版）》请在金锄头文库上搜索。
1、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) ca
2、nd (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:
3、=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
4、中元素个数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
5、; 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分别指向两个单链表的头结点, 且头结点的数据域(整型)中存放链表的长度, 写一算法将这两个链表接在一起, 并要求以尽可能短的时间完成
6、。设计思想：(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 不空
7、, 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
8、; 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.ne
9、xtnil 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个数据元素
10、 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和
11、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; ds0
