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

蔚落 2022-09-26 00:24 100阅读 0赞

### 顺序表应用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>  
\#defineLISTINCREASMENT 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;  
\}

[Submit]: http://www.sdutacm.org/onlinejudge2/index.php/Home/Contest/contestsubmit/cid/1823/pid/3329.html
[Statistic]: http://www.sdutacm.org/onlinejudge2/index.php/Home/Contest/conteststatus/cid/1823/pid/3329.html