数据结构 | 每日一练（45）

数据结构

合抱之木,生于毫末;九层之台,起于累土;千里之行,始于足下

——老子

1

每日一练

1．顺序结构线性表 LA 与 LB 的结点关键字为整数。LA 与 LB 的元素按非递减有序，线性表空间足够大。试

用类 PASCAL 语言给出一种高效算法，将 LB 中元素合到 LA 中，使新的 LA 的元素仍保持非递减有序。高效

指最大限度的避免移动元素。

正确答案

ps：||代表注释

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

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

m:=LA.last;n:=LB.last;∥m，n分别为线性表LA和LB的长度。

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

i:=m;j:=n; ∥i，j分别为线性表LA和LB的工作指针（下标）。

WHILE(i>0)AND(j>0) DO

IF LA.elem[i]>=LB.elem[j]

THEN[LA.elem[k]:=LA.elem[i];k:=k-1;i:=i-1;]

ELSE[LA.elem[k]:=LB.elem[j];k:=k-1;j:=j-1;]

WHILE(j>0) DO [LA.elem[k]:=LB.elem[j];k:=k-1;j:=j-1;]

LA.last:=m+n;

ENDP;

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

如果您觉得本篇文章对您有作用，请转发给更多的人，点一下好看就是对小编的最大支持！

-end-