（TOJ1215）数据结构练习题—

（TOJ1215）数据结构练习题——合并表

描述

已知va和vb分别为非递减有序线性表，将va和vb进行合并为新的线性表vc，并保持vc仍然非递减有序。

本题中，线性表元素为整数。线性表的最大长度为1000。

输入

输入数据有多组，第一行为测试数据的组数n，接下来为2n行，每一组测试数据有两行：

第一行的第一个数为va的元素个数，后面是n个整数，代表va的所有元素

第二行的第一个数为vb的元素个数，后面是n个整数，代表vb的所有元素

输出

输出合并后的长度以及vc的所有元素

样例输入

样例输出

4 1 2 2 3
6 1 2 3 4 5 6

提示

你也可以使用链表来实现，有空也练练吧

 1 #include<stdio.h>
 2 #include<math.h>
 3 #include<string.h>
 4 #include<ctype.h>
 5 
 6 int a[1000],b[1000],c[2000];
 7 
 8 void deal(int a[], int m, int b[], int n)
 9 {
10    int i,j,k,s;
11    i=k=j=s=0;
12    while(i<m && j<n)
13    {
14         if(a[i]<b[j])
15         {
16             c[k]=a[i];
17             i++;k++;
18         }
19         else if(a[i]==b[j])
20         {
21           c[k]=a[i];
22          c[k+1]=a[i];
23          k+=2;  
24          i++;j++;    
25      }
26      else
27      {
28          c[k]=b[j];
29          j++;k++;
30      }
31    }
32    if(i==m)
33    {
34          while(j<n) c[k++]=b[j++];
35    }
36    if(j==n)
37    {
38          while(i<m) c[k++]=a[i++];
39    }
40    printf("%d",k);
41    for(i=0; i<k; i++)
42      printf(" %d",c[i]);
43    printf("\n");
44 }
45 
46 void solve()
47 {
48   int N,i,m,n;
49   scanf("%d",&N);
50   while(N--)
51   {
52       scanf("%d",&m);
53       for(i=0; i<m; i++)
54          scanf("%d",&a[i]);
55     scanf("%d",&n);
56     for(i=0; i<n; i++)
57       scanf("%d",&b[i]);
58     deal(a,m,b,n);
59   }
60 }
61 
62 
63 int main()
64 {
65     solve();
66      getchar();
67      getchar();
68     return 0;
69 }