算法2-2：有序线性表的有序合并

<div> 已知线性表 LA 和 LB 中的数据元素按值非递减有序排列，现要求将 LA 和 LB 归并为一个新的线性表 LC， 且 LC 中的数据元素仍然按值非递减有序排列。例如，设LA=(3,5,8,11) ,LB=(2,6,8,9,11,15,20) 则 </div> <div> LC=(2,3,6,6,8,8,9,11,11,15,20) </div> <div> 算法描述如下： </div> <div> 从上述问题要求可知，LC中的数据元素或是LA中的数据元素，或是LB中的数据元素，则只要先设LC为空表，然后将LA或LB中的元素逐个插入到LC中即可。为使LC中元素按值非递减有序排列，可设两个指针 i 和 j 分别指向LA和LB中某个元素，若设 i 当前所指的元素为 a，j 所指的元素为 b，则当前应插入到 LC 中的元素 c 为 c = a &lt; b ? a : b显然，指针 i 和 j 的初值均为1（实际写代码时往往是从 0 开始的），在所指元素插入 LC 之后，在 LA 或者 LB 中顺序后移。上述归并算法如下图： </div> <div style="text-align:center;"> <img width="500" height="493" alt="" src="http://tk.hustoj.com/upload/pimg1324_1.jpg" /> </div> <div align="center" style="text-align:center;"> <img width="0" height="0" alt="" src="http://tk.hustoj.com/upload/pimg1324_1.jpg" /> </div> <div align="center" style="text-align:center;"> &nbsp; </div> <div align="center" style="text-align:center;"> 图：有序列表有序插入算法 </div>

<p> <span style="font-size:10.5pt;">有多组测试数据，每组测试数据占两行。第一行是集合</span><span style="font-size:10.5pt;">A</span><span style="font-size:10.5pt;">，第一个整数</span><span style="font-size:10.5pt;">m</span><span style="font-size:10.5pt;">（</span><span style="font-size:10.5pt;">0&lt;=m&lt;=100</span><span style="font-size:10.5pt;">）代表集合</span><span style="font-size:10.5pt;">A</span><span style="font-size:10.5pt;">起始有</span><span style="font-size:10.5pt;">m</span><span style="font-size:10.5pt;">个元素，后面有</span><span style="font-size:10.5pt;">m</span><span style="font-size:10.5pt;">个非递减排序的整数，代表</span><span style="font-size:10.5pt;">A</span><span style="font-size:10.5pt;">中的元素。第二行是集合</span><span style="font-size:10.5pt;">B</span><span style="font-size:10.5pt;">，第一个整数</span><span style="font-size:10.5pt;">n(0&lt;=n&lt;=100)</span><span style="font-size:10.5pt;">代表集合</span><span style="font-size:10.5pt;">B</span><span style="font-size:10.5pt;">起始有</span><span style="font-size:10.5pt;">n</span><span style="font-size:10.5pt;">个元素，后面有</span><span style="font-size:10.5pt;">n</span><span style="font-size:10.5pt;">个非递减排序的整数，代表</span><span style="font-size:10.5pt;">B</span><span style="font-size:10.5pt;">中的元素。每行中整数之间用一个空格隔开。</span> </p>

<p> <span style="font-size:10.5pt;">每组测试数据只要求输出一行，这一行含有</span><span style="font-size:10.5pt;"> m+n </span><span style="font-size:10.5pt;">个来自集合</span><span style="font-size:10.5pt;"> A </span><span style="font-size:10.5pt;">和集合</span><span style="font-size:10.5pt;">B </span><span style="font-size:10.5pt;">中的元素。结果依旧是非递减的。每个整数间用一个空格隔开。</span> </p>