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

淡淡的烟草味﹌ 2022-05-19 14:43 116阅读 0赞

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所存放的元素。

Sample Input

5 3
    1 3 5 6 9
    2 4 10

Sample Output

1 2 3 4 5 6 9 10

tip：这题有两种解法：

1：直接对这两个顺序表的某一个顺序表进行操作，但这种方法比较耗时，不推荐这种方法。

2：建立另一个新的顺序表，然后对这两个顺序表两两比较，依次把最小的元数放入新的表中，即：

void Merge(sqlist *l1,sqlist *l2,sqlist *l3,int n,int m)
    {
    
        int a,b,f;
        a=b=1;
        f=0;
        while(a<=n&&b<=m)
        {
            if(l1->eleme[a]<l2->eleme[b])
            {
                l3->eleme[++f]=l1->eleme[a];
                a++;
            }
            else
            {
                l3->eleme[++f]=l2->eleme[b];
                b++;
            }
        }
        if(a>n)
        {
    
            for(int j=b;j<=m;j++)
            l3->eleme[++f]=l2->eleme[j];
        }
        if(b>m)
        {
            for(int i=a;i<=n;i++)
                l3->eleme[++f]=l1->eleme[i];
        }
        for(int i=1;i<=f;i++)
            printf("%d ",l3->eleme[i]);
    
    }

完整代码如下·：

#include<bits/stdc++.h>
    using namespace std;
    #define maxsize 1001000
    #define addsize 10010
    typedef struct
    {
        int *eleme;
        int length;
        int sizelist;
    }sqlist;
    int creatlist1(sqlist *l)
    {
        l->eleme=(int *)malloc(maxsize *sizeof(int));
        if(!l->eleme) return -1;
        l->length=0;
        l->sizelist=maxsize;
        return 0;
    }
    void insertlist1(sqlist *l,int n)
    {
        int x;
       for(int i=1;i<=n;i++)
       {
           scanf("%d",&x);
           l->eleme[i]=x;
       }
    
     l->length=n;
    }
    void Merge(sqlist *l1,sqlist *l2,sqlist *l3,int n,int m)
    {
    
        int a,b,f;
        a=b=1;
        f=0;
        while(a<=n&&b<=m)
        {
            if(l1->eleme[a]<l2->eleme[b])
            {
                l3->eleme[++f]=l1->eleme[a];
                a++;
            }
            else
            {
                l3->eleme[++f]=l2->eleme[b];
                b++;
            }
        }
        if(a>n)
        {
    
            for(int j=b;j<=m;j++)
            l3->eleme[++f]=l2->eleme[j];
        }
        if(b>m)
        {
            for(int i=a;i<=n;i++)
                l3->eleme[++f]=l1->eleme[i];
        }
        for(int i=1;i<=f;i++)
            printf("%d ",l3->eleme[i]);
    
    }
    int main()
    {
        sqlist l1,l2,l3;
        int n,m;
        scanf("%d %d",&n,&m);
            creatlist1(&l1);
            creatlist1(&l2);
            creatlist1(&l3);
            insertlist1(&l1,n);
             insertlist1(&l2,m);
            Merge(&l1,&l2,&l3,n,m);
    }