题目

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

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

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

样例输入：样例输出：

2 1 2 3 3 6

1 3

3

2 3 6

思路

依照题目输出，是从小到大排序的，所以是优先队列的题。当然，也可以直接合并，然后sort排序。

优先队列：

即从头开始比较两个顺序表的元素，谁小就插入谁。直到某一顺序表全部被插完，那么剩下还有一个顺序表，直接把后面的元素数据复制插入就行。

比如样例：先是第一个顺序表（L1）第一个元素（1)和第二个顺序表（L2)第一个元素（2）比较。

1小，所以插入1

接下来就是L1的第二个元素（3）和L2的第一个元素（2）比较。

2小，所以插入2

以此类推。

代码

数据结构

#include<bits/stdc++.h>
using namespace std;
//定义顺序表 
typedef struct{int number[10001],len;
}Seqlist;
//初始化 
void SeqlistInit(Seqlist* &L){L=(Seqlist*)malloc(sizeof(Seqlist));L->len=0;
}
//创建顺序表
void  SeqlistCreate(Seqlist* &L){int n,x;cin>>n;while(n--){cin>>x;L->number[L->len++]=x;}
}
//合并顺序表
void SeqlistMerge(Seqlist* &L1,Seqlist* &L2,Seqlist* &L3){SeqlistInit(L3);int x=0,y=0;while(x<L1->len&&y<L2->len){if(L1->number[x]<L2->number[y]) L3->number[L3->len++]=L1->number[x++];else L3->number[L3->len++]=L2->number[y++];}while(x<L1->len) L3->number[L3->len++]=L1->number[x++];while(y<L2->len) L3->number[L3->len++]=L2->number[y++];
}
//输出顺序表
void SeqlistPrint(Seqlist* &L){for(int i=0;i<L->len-1;i++){cout<<L->number[i]<<" ";}cout<<L->number[L->len-1]<<endl;
} 
int main(){Seqlist *L1,*L2,*L3;SeqlistInit(L1);SeqlistCreate(L1);SeqlistInit(L2);SeqlistCreate(L2);SeqlistMerge(L1,L2,L3);SeqlistPrint(L3);return 0;
}

STL

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
int main() {vector<int>a,b;int n,m,x;cin>>n;while(n--) {cin>>x;a.push_back(x);}cin>>m;while(m--) {cin>>x;b.push_back(x);}vector<int>::iterator it;for(it=b.begin();it!=b.end();it++) a.push_back(*it);sort(a.begin(),a.end());for(it=a.begin();it!=a.end();it++) cout<<*it<<" ";system("pause");return 0;
}

仿STL

#include <iostream>
#include <algorithm>
#include <cstdio>
using namespace std;
typedef struct {int data[10005],len;
}Seqlist;
//初始化顺序表
void SeqlistInit(Seqlist* &L) {L=(Seqlist*)malloc(sizeof(Seqlist));L->len=0;
}
//正向迭代器
int* begin(Seqlist* &L) {int *p=&L->data[0];return p;
}
int* end(Seqlist* &L) {int *p=&L->data[L->len];return p;
}
//尾插
void push_back(Seqlist* &L,int key) {L->data[L->len++]=key;
}
int main() {Seqlist *L1,*L2;SeqlistInit(L1);SeqlistInit(L2);int m,n,x;cin>>n;while(n--) {cin>>x;push_back(L1,x);}cin>>m;while(m--) {cin>>x;push_back(L2,x);}int* it;for(it=begin(L2);it!=end(L2);it++) push_back(L1,*it);sort(begin(L1),end(L1));for(it=begin(L1);it!=end(L1);it++) cout<<*it<<" ";system("pause");return 0;
}

SWUST OJ#941 顺序表合并

题目

思路

代码

数据结构

STL

仿STL