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

以你之姓@ 2022-06-07 10:36 152阅读 0赞

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

Time Limit: 100MS Memory Limit: 880KB

#### Problem Description ####

已知顺序表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所存放的元素。

#### Example Input ####

5 3
    1 3 5 6 9
    2 4 10

#### Example Output ####

1 2 3 4 5 6 9 10

#include <bits/stdc++.h>
    
    using namespace std;
    #define intlist 100010
    typedef int elemtype;
    
    typedef struct
    {
        elemtype *elem;
        int length;
        int listsize;
    }sqlist;
    
    void initlist(sqlist &l, int n)
    {
        l.elem = new elemtype [intlist];
        l.listsize = n;
        for(int i=0;i<n;i++)
        {
            scanf("%d",&l.elem[i]);
        }
    }
    
    void output(sqlist &l, int n)
    {
        for(int i=0; i<n-1;i++)
        {
            printf("%d ",l.elem[i]);
        }
        printf("%d\n",l.elem[n-1]);
    }
    
    void change(sqlist l1, sqlist l2, sqlist l3)
    {
        int i =0, j =0, k =0;
        while(i<l1.listsize&&j<l2.listsize)
        {
            if(l1.elem[i]<=l2.elem[j])
            {
                l3.elem[k++]=l1.elem[i++];
            }
            else
            {
                l3.elem[k++]=l2.elem[j++];
            }
        }
        while(i<l1.listsize)
        {
            l3.elem[k++]=l1.elem[i++];
        }
        while(j<l2.listsize)
        {
            l3.elem[k++]=l2.elem[j++];
        }
    }
    
    int main(){
    	int n,m;
    	sqlist l1,l2,l3;
    	scanf("%d %d",&n,&m);
    	initlist(l1,n);
    	initlist(l2,m);
    	initlist(l3,0);
        change(l1,l2,l3);
        output(l3,n+m);
    	return 0;
    }