題目 1674:
數(shù)據(jù)結(jié)構(gòu)-有序線性表的有序合并
時間限制: 2s
內(nèi)存限制: 96MB 提交: 6504 解決: 2161
題目描述
已知線性表 LA 和 LB 中的數(shù)據(jù)元素按值非遞減有序排列，現(xiàn)要求將 LA 和 LB 歸并為一個新的線性表 LC， 且 LC 中的數(shù)據(jù)元素仍然按值非遞減有序排列。例如，設(shè)LA=(3,5,8,11) ,LB=(2,6,8,9,11,15,20) 則
LC=(2,3,6,6,8,8,9,11,11,15,20)
算法描述如下：
從上述問題要求可知，LC中的數(shù)據(jù)元素或是LA中的數(shù)據(jù)元素，或是LB中的數(shù)據(jù)元素，則只要先設(shè)LC為空表，然后將LA或LB中的元素逐個插入到LC中即可。為使LC中元素按值非遞減有序排列，可設(shè)兩個指針 i 和 j 分別指向LA和LB中某個元素，若設(shè) i 當(dāng)前所指的元素為 a，j 所指的元素為 b，則當(dāng)前應(yīng)插入到 LC 中的元素 c 為 c = a < b ? a : b顯然，指針 i 和 j 的初值均為1（實際寫代碼時往往是從 0 開始的），在所指元素插入 LC 之后，在 LA 或者 LB 中順序后移。上述歸并算法如下圖：
圖：有序列表有序插入算法
輸入格式
有多組測試數(shù)據(jù)，每組測試數(shù)據(jù)占兩行。第一行是集合A，第一個整數(shù)m（0<=m<=100）代表集合A起始有m個元素，后面有m個非遞減排序的整數(shù)，代表A中的元素。第二行是集合B，第一個整數(shù)n(0<=n<=100)代表集合B起始有n個元素，后面有n個非遞減排序的整數(shù)，代表B中的元素。每行中整數(shù)之間用一個空格隔開。
輸出格式
每組測試數(shù)據(jù)只要求輸出一行，這一行含有 m+n 個來自集合 A 和集合B 中的元素。結(jié)果依舊是非遞減的。每個整數(shù)間用一個空格隔開。
樣例輸入
4 3 5 8 11 7 2 6 8 9 11 15 20
樣例輸出
2 3 5 6 8 8 9 11 11 15 20