顺序表应用5：有序顺序表归并

TimeLimit: 100MS Memory Limit: 800KB

SubmitStatistic

ProblemDescription

已知顺序表A与B是两个有序的顺序表，其中存放的数据元素皆为普通整型，将A与B表归并为C表，要求C表包含了A、B表里所有元素，并且C表仍然保持有序。

Input

 输入分为三行：
第一行输入m、n（1<=m,n<=10000）的值，即为表A、B的元素个数；
第二行输入m个有序的整数，即为表A的每一个元素；
第三行输入n个有序的整数，即为表B的每一个元素；

Output

 输出为一行，即将表A、B合并为表C后，依次输出表C所存放的元素。

ExampleInput

53

13 5 6 9

24 10

ExampleOutput

12 3 4 5 6 9 10

Hint

 

Author

  

#include <iostream>
#include<string.h>
#include<math.h>
#include<stdlib.h>
#include<algorithm>
#include<queue>
#include<deque>
#include<stdio.h>
#define max 20002

using namespace std;
typedef struct node
{
   int *elem;
   int size;
   int length;
}list;
int init(list *l)
{
  l->elem = (int*)malloc(max*sizeof(int));
  if(l->elem) return 0;
  l->length = 0;
  l->size = max;
  return 1;
}
void creat(list *l,int n)
{
  for(int i=1;i<=n;i++)
  {
  scanf("%d",&l->elem[i]);
  }
  l->length = n;
}
void show(list*l,int n)
{
 for(int i=1;i<n;i++)
 {printf("%d ",l->elem[i]);}
 printf("%d\n",l->elem[n]);
}
void guibing(list*l1,list*l2,list*l3,int m,int n)
{
    int c,j,a,b;
    a = 1;
    b = 1;
    c = 1;
    while(a<=m&&b<=n)
    {
    if(l1->elem[a]<l2->elem[b])
    {
       l3->elem[c] = l1->elem[a];
       a++;
       c++;
    }
    else
    {
        l3->elem[c] = l2->elem[b];
        c++;
        b++;
    }
    }
   if(a>=m+1)
   {
       for(j = b;j<=n;j++)
       {
         l3->elem[c] = l2->elem[j];
         c++;
       }
   }
   else
   {
    for(j=a;j<=m;j++)
    {
      l3->elem[c] = l1->elem[j];
      a++;
    }

   }

}
int main()
{
    int n,m;
    list l1,l2,l3;
    cin>>m>>n;
    init(&l1);
    creat(&l1,m);
    init(&l2);
    creat(&l2,n);
    init(&l3);
    guibing(&l1,&l2,&l3,m,n);
    show(&l3,m+n);

    return 0;
}


/***************************************************
User name: jk160505徐红博
Result: Accepted
Take time: 8ms
Take Memory: 336KB
Submit time: 2017-01-16 09:15:22
****************************************************/