数据结构考研分类复习真题 第二章 答案[20]

．[题目分析]顺序存储结构的线性表的插入其时间复杂度为O(n)平均移动近一半的元素线性表LA和LB合并时若从第一个元素开始一定会造成元素后移这不符合本题高效算法的要求另外题中叙述线性表空间足够大也暗示出另外合并方式即应从线性表的最后一个元素开始比较大者放到最终位置上设两线性表的长度各为m和n 则结果表的最后一个元素应在m+n位置上这样从后向前直到第一个元素为止

PROC Union(VAR LA:SeqList;LB:SeqList)∥LA和LB是顺序存储的非递减有序线性表本算法将LB合并到LA中元素仍非递减有序

m:=LAlast;n:=LBlast;∥mn分别为线性表LA和LB的长度

k:=m+n;∥k为结果线性表的工作指针(下标)

i:=m;j:=n;∥ij分别为线性表LA和LB的工作指针(下标)

WHILE(i>)AND(j>)DO

IF LAelem[i]>=LBelem[j]

THEN[LAelem[k]:=LAelem[i];k:=k;i:=i;]

ELSE[LAelem[k]:=LBelem[j];k:=k;j:=j;]

WHILE(j>) DO [LAelem[k]:=LBelem[j];k:=k;j:=j;]

LAlast:=m+n;

ENDP;

[算法讨论]算法中数据移动是主要操作在最佳情况下(LB的最小元素大于LA的最大元素)仅将LB的n个元素移(拷贝)到LA中时间复杂度为O(n)最差情况LA的所有元素都要移动时间复杂度为O(m+n)因数据合并到LA中所以在退出第一个WHILE循环后只需要一个WHILE循环处理LB中剩余元素第二个循环只有在LB有剩余元素时才执行而在LA有剩余元素时不执行本算法利用了题目中线性表空间足够大的条件最大限度的避免移动元素是一种高效算法

[] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] []