合并两个有序表

描述

已知两个严格单调递增的表a（长度为n，n≤10000）和表b（长度为m，m≤10000），其中数据均为正整数，将其合并成一个严格单调递增的表

格式

输入格式

输入为3行，第一行两个数n和m，表示序列的长度。第二行是一个长度为n的表a，第三行是长度为m的表b。

输出格式

输出合并后的表c

样例

输入样例

5 6
2 4 7 9 12
3 4 8 9 12 15

输出样例

2 3 4 7 8 9 12 15

限制

时间限制：500 ms
内存限制：32767 KB

代码:
way1

#include<stdio.h>
struct node
{
    int data[205];
    int lenth;
}La, Lb, Lc;
int main()
{
    int n, m, i, j;
    int ans = 0;
    scanf("%d", &m);
    scanf("%d", &n);
    for (i = 0; i < m; i++)
    {
        scanf("%d", &La.data[i]);
    }
    La.lenth = m;
    for (i = 0; i < n; i++)
    {
        scanf("%d", &Lb.data[i]);
    }
    Lb.lenth = n;
    int x, y;
    for (x = 0; x < n; x++)
    {
        int flag = 0;
        for (y = 0; y < m; y++)
        {
            if (flag == 1)
            {
                y = y - 1;
                flag = 0;
            }
            if (La.data[x] == Lb.data[y])
            {
                int t;
                for (t = y; t < Lb.lenth-1; t++)
                {
                    Lb.data[t] = Lb.data[t + 1];
                }
                Lb.lenth--;
                flag = 1;
            }
        }
    }
    int k = 0;
    Lc.lenth = 0;
    i = 0; j = 0;
    while (i != La.lenth && j != Lb.lenth)
    {
        if (La.data[i] <= Lb.data[j])
        {
            Lc.data[k] = La.data[i];
            i++;
            k++;
            Lc.lenth++;
        }
        else
        {
            Lc.data[k] = Lb.data[j];
            j++;
            k++;
            Lc.lenth++;
        }
    }
    if (i != La.lenth)
    {
        for (i; i < La.lenth; i++)
        {
            Lc.data[k] = La.data[i];
            k++;
            Lc.lenth++;
        }
    }
    if (j != Lb.lenth)
    {
        for (j; j < Lb.lenth; j++)
        {
            Lc.data[k] = Lb.data[j];
            k++;
            Lc.lenth++;
        }
    }
    int l;
    for (l = 0; l < Lc.lenth; l++)
    {
        if (l != 0)
            printf(" ");
        printf("%d", Lc.data[l]);
    }
    printf("\n");
    return 0;
}

way2

#include <stdio.h>
#include<stdlib.h>
#include<string.h>
#define ERROR 0;
#define MAX 20

typedef struct
{
    int* elem;
    int lenth;
    int listsize;

} SqList;

void CreatList(SqList &L, int n, int* a)
{

    L.elem = (int*)malloc(MAX * sizeof(int));
    if (!L.elem)
    {
        return;
    }
    L.listsize = MAX;
    L.lenth = n;
    int i;
    for (i = 0; i < n; i++)
    {
        L.elem[i] = a[i];
    }
}

void DeleteList(SqList* La, SqList Lb)
{
    int p,q;

    for (p = 0; p < Lb.lenth; p++)
    {
        int flag=0;
        for (q = 0; q < La->lenth; q++)
        {

            if (flag == 1)
            {
                q = q - 1;
                flag = 0;
            }
            if (Lb.elem[p] == La->elem[q])
            {
                int t;
                for (t = q; t < La->lenth; t++)
                {
                    La->elem[t] = La->elem[t + 1];
                }
                La->lenth--;
                flag = 1;
            }
        }
    }

}

void Traverse(SqList L)
{
    int j;
    for (j = 0; j < L.lenth; j++)
    {
        if (j != L.lenth - 1)
        {
            printf("%d ", L.elem[j]);
        }
        else
        {
            printf("%d\n", L.elem[j]);
        }


    }

}

void  Merge(SqList* L1, SqList L2,SqList Lm)
{


    int h=0, u=0, l=0;
    while (h < L1->lenth && u < L2.lenth)
    {
        if (L1->elem[h] < L2.elem[u])
        {
            Lm.elem[l++] = L1->elem[h++];
        }
        else
        {
            Lm.elem[l++] = L2.elem[u++];
        }

    }
    while (h < L1->lenth)
    {
        Lm.elem[l++] = L1->elem[h++];
    }
    while(u < L2.lenth)
    {
        Lm.elem[l++] = L2.elem[u++];
    }
    Lm.lenth = l;

    Traverse(Lm);

}







int main()
{
    int m, n;
    int a[201], b[201],T[201];
    scanf("%d%d", &n, &m);
    int i, j;
    for (i = 0; i < n; i++)
    {
        scanf("%d", &a[i]);
    }
    for (j = 0; j < m; j++)
    {
        scanf("%d", &b[j]);
    }

    SqList L1, L2,Lm;
    CreatList(Lm, MAX, T);

    CreatList(L1, n, a);
    CreatList(L2, m, b);
    DeleteList(&L1, L2);
    Merge(&L1, L2,Lm);

    return 0;
}