合并线性表

56 阅读 0 评论 37 点赞

我是靠谱客的博主悦耳母鸡，最近开发中收集的这篇文章主要介绍合并线性表，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

描述

已知两非递减的顺序线性表，要求合并成一个新的非递减顺序线性表。

输入

输入包含四行，第一行为自然数n，表示第一个非递减顺序线性表的长度，第二行为n个自然数构成的非递减顺序线性表，第三行为自然数m，表示第二个非递减顺序线性表的长度，第四行为m个自然数构成的非递减顺序线性表。

输出

用一行输出合并后的非递减顺序线性表，各数之间用一个空格隔开。

样例输入

2
1 3
3
2 3 6

样例输出

1 2 3 3 6

#include<iostream>
#include<stdlib.h>
#define MI 10
#define MX 20
using namespace std;
struct list
{
    int *elem;
    int length;
    int listsize;
};
void initializer_list(list &l)
{
    l.elem=(int *)malloc(MI*sizeof(int));
    l.length=0;
    l.listsize=MI;
}
void create(list &l,int n)
{
    int i;
    for(i=0;i<n;i++)
    {
        if(l.length>=l.listsize)
        {
            l.elem=(int *)realloc(l.elem,(l.listsize+MX)*(sizeof(int)));
            if(!l.elem)return ;
            l.listsize+=MX;
        }
        cin>>l.elem[l.length++];
     //   cout<<l.elem[l.length-1]<<endl;
    }
}
int booll(list &l,int i,int &e)
{
    if(i<0||i>l.length)return 0;
    e=l.elem[i];
    return e;
}
void mergelist(list la,list lb,list &lc)
{
    int i=0,j=0,ai,aj;
    while(i<la.length&&j<lb.length)
    {
        booll(la,i,ai);booll(lb,j,aj);
     //   cout<<ai<<" "<<aj<<endl;
       if(lc.length>=lc.listsize)
       {
            lc.elem=(int *)realloc(lc.elem,(lc.listsize+MX)*(sizeof(int)));
            if(!lc.elem)return ;
            lc.listsize+=MX;
       }
       if(ai<=aj)
         {
            lc.elem[lc.length++]=ai;i++;
         }
    else {
            lc.elem[lc.length++]=aj;j++;
         }
    }
    while(i<la.length)
    {
          booll(la,i++,ai);
           if(lc.length>=lc.listsize)
          {
            lc.elem=(int *)realloc(lc.elem,(lc.listsize+MX)*(sizeof(int)));
            if(!lc.elem)return ;
             lc.listsize+=MX;
          }
           lc.elem[lc.length++]=ai;
    }
    while(j<lb.length)
    {
          booll(lb,j++,aj);
           if(lc.length>=lc.listsize)
          {
            lc.elem=(int *)realloc(lc.elem,(lc.listsize+MX)*(sizeof(int)));
            if(!lc.elem)return ;
             lc.listsize+=MX;
          }
           lc.elem[lc.length++]=aj;

    }
}
int main()
{
    list la,lb,lc;
    int n,m;
    while(cin>>n)
    {
        initializer_list(la);
        initializer_list(lb);
        initializer_list(lc);
        create(la,n);
        cin>>m;
        create(lb,m);
        mergelist(la,lb,lc);
        for(int i=0;i<lc.length-1;i++)
            cout<<lc.elem[i]<<" ";
            cout<<lc.elem[lc.length-1]<<endl;
    }
    return 0;
}