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

快来打我* 2022-10-01 01:49 16阅读 0赞

###     ###

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

Time Limit: 100MS  Memory Limit: 800KB

[Submit][] [ Statistic][Statistic]

#### 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

#### Hint ####

#### Author ####

\#include<stdio.h>  
\#include<stdlib.h>  
\#include<string.h>  
struct node  
\{  
    int \*elem,listsize,length;  
\};  
struct node  initializer\_list(struct node l)  
\{  
    l.elem=(int \*)malloc(1000011\*sizeof(int ));  
    if(!l.elem) return l;  
    l.length=0;  
    l.listsize=1000011;  
    return l;  
\}  
struct node creatlist(struct node l,int n)  
\{  
    int i;  
    l.elem=(int \*)malloc(1000011\*sizeof(int ));  
    if(!l.elem) return l;  
    else  
    \{  
        for(i=0; i<n; i++)  
        \{  
            scanf("%d",&l.elem\[i\]);  
        \}  
        l.length=n;  
    \}  
    return l;  
\}  
  
  
void display(struct node l)  
\{  
    int i;  
    for(i=0; i<l.length-1; i++)  
        printf("%d ",l.elem\[i\]);  
    printf("%d\\n",l.elem\[i\]);  
\}  
struct node contact(struct node a,int n,struct node b,int m,struct node c)  
\{  
    int i=0,j=0,d=0;  
    while(i<n&&j<m)  
    \{  
        if(a.elem\[i\]<b.elem\[j\])  
        \{  
            c.elem\[d++\]=a.elem\[i\];  
            i++;  
        \}  
        else  
        \{  
            c.elem\[d++\]=b.elem\[j\];  
            j++;  
        \}  
    \}  
    if(i==n)    ///插入剩余的元素  
    \{  
        for(; j<m; j++)  
            c.elem\[d++\]=b.elem\[j\];  
    \}  
    else  
    \{  
        for(; i<n; i++)  
            c.elem\[d++\]=a.elem\[i\];  
    \}  
    c.length=d;  ///记下动态数组的长度  
    return c;  
  
  
\};  
int main()  
\{  
    struct node a,b,c;  
    int n,m;  
    scanf("%d%d",&n,&m);  
    a=initializer\_list(a);  
    a=creatlist(a,n);  
      
    b=initializer\_list(b);  
    b=creatlist(b,m);  
      
    c=initializer\_list(c);  
    c=contact(a,n,b,m,c);  
    display(c);  
  
  
    return 0;  
\}

[Submit]: http://acm.sdut.edu.cn/onlinejudge2/index.php/Home/Contest/contestsubmit/cid/1998/pid/3329.html
[Statistic]: http://acm.sdut.edu.cn/onlinejudge2/index.php/Home/Contest/conteststatus/cid/1998/pid/3329.html