(线性表)顺序结构线性表LA与LB的结点关键字为整数。LA与LB的元素按非递减有序,线性表空间足够大。试用类PASCAL语言给出一种高效算法,将LB中元素合到LA中,使新的LA的元素仍保持非递减有序。高效指最大限度的避免移动元素。
时间: 2023-05-30 12:04:14 浏览: 170
数据结构 线性表的顺序表示
算法步骤如下:
1. 初始化两个指针:$i$指向LA的最后一个元素,$j$指向LB的最后一个元素。
2. 从后往前遍历,比较LA中第$i$个元素和LB中第$j$个元素的大小,将较大的元素放在LA的$(i+j+1)$位置,即最后一个位置,同时将指针向前移动一位。
3. 继续比较,直到LA或LB的指针移到了头部,即$i$或$j$等于0为止。
4. 如果LA的指针移到了头部,将LB中剩余的元素依次放在LA的前面。
5. 如果LB的指针移到了头部,则不需要做任何操作,因为LB中剩余的元素已经在LA中了。
代码如下:
```PASCAL
procedure Merge(var LA, LB: array of Integer; lenA, lenB: Integer);
var
i, j, k: Integer;
begin
i := lenA - 1;
j := lenB - 1;
k := lenA + lenB - 1;
while (i >= 0) and (j >= 0) do
begin
if LA[i] > LB[j] then
begin
LA[k] := LA[i];
k := k - 1;
i := i - 1;
end
else
begin
LA[k] := LB[j];
k := k - 1;
j := j - 1;
end;
end;
while j >= 0 do
begin
LA[k] := LB[j];
k := k - 1;
j := j - 1;
end;
end;
```
其中,$lenA$和$lenB$分别为LA和LB的长度。
阅读全文