线性表:例2－2

问题描述： 已知线性表LA和LB中的数据元素按值非递减有序排列，现要求将LA和LB归并为一个新的线性表LC，且LC中的数据元素仍按值非递减有序排列。例如，设 LA = (3,5,8,11) LB = (2,6,8,9,11,15,20) 则 LC = (2,3,5,6,8,8,9,11,11,15,20) 从上述为题要求可知，LC中的数据元素或是LA中的数据元素，或是LB中的数据元素，则只要现设LC为空表，然后将LA或LB中的元素逐个插入到LC中即可。为使LC中元素按值非递减有序排列，可设两个指针 i 和 j 分别指向LA和LB中某个元素，若设 i 当前所指的元素为 a，j 当前所指的元素为 b，则当前应插入到LC中的元素 c 为 当 a <= b时，c = a 当 a > b时，c = b 显然，指针 i 和 j 的初值均为 1，在所指元素插入LC之后，在LA或LB中顺序后移。 原书伪代码描述：

PROC merge_list(LA,LB:Linear_list; VAR LC:Linear_list);
{ 已知线性表LA和LB中元素依值非递减有序排列，本算法归并LA和LB得到线性表LC，LC中的元素仍依值非递减有序排列 }

INITIATE(LC); i := 1; j := 1; k := 0; { 初始化 }
WHILE (i<=LENGTH(LA)) AND (j<=LENGTH(LB)) DO { LA和LB均非空 }
IF GET(LA,i)<=GET(LB,j) THEN [INSERT(LC,k+1,GET(LA,i)); k:=k+1; i:=i+1]
ELSE [INSERT(LC,k+1,GET(LB,j)); k:=k+1; i:=i+1];
WHILE (i<=LENGTH(LA) DO [INSERT(LC,k+1,GET(LA,i)); k:=k+1; i:=i+1];
WHILE (j<=LENGTH(LB) DO [INSERT(LC,k+1,GET(LB,j)); k:=k+1; j:=j+1]
ENDP;

Python代码：


#!/usr/bin python
#Data Structure-Linear_list example 2-2

def merge_list(LA,LB):
i = 1
j = 1
LC = [ ]
while (i
if LA[i-1] <= LB[j-1]: LC.append(LA[i-1]) i = i + 1 else: LC.append(LB[j-1]) j = j + 1 while i<=len(LA): LC.append(LA[i-1]) i = i + 1 while j<=len(LB): LC.append(LB[j-1]) j = j + 1 return LC if name == "main": la = [11,2,8,5] lb = [15,2,8,6,11,20] la.sort() lb.sort() print merge_list(la,lb)