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

Time Limit: 100MS Memory Limit: 800KB

Submit 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

#include <stdio.h>
#include <iostream>
#include <stdlib.h>
#include <malloc.h>
#define LISTINCREASMENT 100 /*每次分配元素的个数*/
#define LISTSIZE 10 /*顺序存储的最大个数*/
#define OVERFLOW -1
#define OK 1
int n,m;
using namespace std;
typedef int ElemType;

typedef struct /*顺序表元素的的定义*/
{
ElemType * elem;
int length;
int listsize;
} Sqlist;

int SqInitial(Sqlist &L) /*初始化线性表*/
{
L.elem=(ElemType *) malloc (LISTSIZE*sizeof(ElemType));
if (! L.elem) exit(OVERFLOW); //存储分配失败
L.length=0;
L.listsize=LISTSIZE;
return OK;
}

int ListInsert(Sqlist &L,int i,ElemType e) /*插入元素*/
{
if(i<1|| i > L.length+1) exit(-1);
if(L.length>=L.listsize)
{
ElemType*newbase=(ElemType*)realloc(L.elem,(L.listsize+LISTINCREASMENT)
*sizeof(ElemType));
if(!newbase) return OVERFLOW;// 当前存储空间已满

L.elem=newbase;
L.listsize+=LISTINCREASMENT; /*表的容量不足分配内存*/
}
ElemType * q=&(L.elem[i-1]);
ElemType * p;
for(p=&(L.elem[L.length-1]); p>=q; --p)
*(p+1)=*p;
*q=e;
++L.length;
return OK;

}
void display(Sqlist &L)
{
int i;
for(i=0;i<L.length-1;i++)
{
cout<<L.elem[i]<<" ";
}
cout<<L.elem[i]<<endl;
}

void Merge(Sqlist &L,Sqlist &L1,Sqlist &L2)
{

int i=0,j=0,t=0,f;
while(i<n && j<m)
{ t++;
if(L.elem[i]<L1.elem[j])
{
ListInsert(L2,t,L.elem[i]);
i++;
}
else
{
ListInsert(L2,t,L1.elem[j]);
j++;
}
}
// cout<<"提前输出"<<endl;
// display(L2);
while(i<n)
{
t++;
ListInsert(L2,t,L.elem[i]);
i++;
}
while(j<m)
{
t++;
ListInsert(L2,t,L1.elem[j]);
j++;
}

// cout<<"i=="<<i<<" j=="<<j<<endl;

}

int main()
{
Sqlist L,L1,L2;
int t =1 ,d;
cin>>n>>m;
SqInitial(L);
SqInitial(L1);
SqInitial(L2);
//printf("构建长度为len的顺序表。\n");
for(t=1; t<=n; t++) /*构建长度为n的顺序表*/
{
//printf("Please input the %dth list elem:",t);
scanf("%d",&d);
ListInsert(L,t,d);
}
for(t=1; t<=m; t++) /*构建长度为n的顺序表*/
{

scanf("%d",&d);
ListInsert(L1,t,d);
}
Merge(L,L1,L2);
display(L2);

return 0;
}