第2章算法答案.doc

2.1 设线性表存于a[1..arrsize]的前elenum个分量中, 且递增有序. 试写一算法,将x插入到线性表的适当位置, 以保持线性表的有序性。 设计思想： (1) 先查找 x 的插入位置 i ； (2) 将线性表中自A[i]至A[elenum]的元素后移一个位置； (3) 最后将x查入到A[i]中， 并且将表长加1。 算法： proc ds0201(var a:array[1..size] of integer; var elenum:integer; x:integer); if elenum=size then error(array overflow) else [ i:=elenum; while (i=1) cand (xa[i]) do [a[i+1]:=a[i]; i:=i-1 ]; {查找插入位置, 并后移} a[i+1]:=x; elenum:=elenum+1 ] endp; {ds0201} 2.2 已知线性表存于a[1..array]中的前last个分量中，删除从第i个元素起的k个元素。 设计思想： 将k个元素一次删除，即从i+k开始，每一元素前移k个元素位置。 算法： proc ds0202(var a:array[1..size] of integer; var last:integer; i,k:integer); if (k=0)and(1=i+k=last)and(0=last=array) then [ for j:=i+k to last do a[j-k]:=a[j]; {前移k个元素} last:=last-k; {表长－k} ] else error(入口参数错误) endp; {ds0202} 2.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.elem[i]=vb.elem[j] THEN [vc.elem[k+1]:=va.elem[i];k:=k+1;i:=i+1] ELSE [vc.elem[k+1]:=vb.elem[j];k:=k+1;j:=j+1]; WHILE i=va.last DO {插入VA的剩余段} [vc.elem[k+1]:=va.elem[i];k:=k+1;i:=i+1]; WHILE j=vb.last DO {插入VB的剩余段} [vc.elem[k+1]:=vb.elem[j];k:=k+1;j:=j+1]; vc.last:=k {K为VC中元素个数} ENDP;{ds0203} 2.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=nil} end; {ds0205_1} 二. 设计思想： 逐一访问每一结点并计数, 即可得此链表的长度。 算法： proc ds0205_2(ha:pointer; x:datatype); { ha:带头结点的单链表的头指针} p:=ha; {p:指向头结点}