输入：顺序表A，顺序表B
输出：合并了AB元素的顺序表C，其中C中元素按照非递减排列
分析：顺序表C是一个空表，首先取出顺序表A和B中的元素，并将这两个元素比较，如果A中的元素m1大于B中的元素n1，则将B中的元素n1插入C中，继续取出B中下一个元素n2与A中元素m1比较。如果A中的元素m1小于等于B中的元素n1，则将A中的元素m1插入C中，继续取出A中下一个元素m2与B中元素n1比较。以此类推比较下去，直到一个表中元素比较完毕，将另一个表中剩余元素插入C中。
以下代码在VS2017环境下编译通过。
//数据结构与算法基础题1:合并两个线性表中的元素
//输入一个顺序表A，输入一个顺序表B，要求合并AB到C中，C是非递减排列
#include "stdafx.h"
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#pragma warning(disable:4996)
using namespace std;
int main()
{
int num_of_elements_in_A = 0;
int num_of_elements_in_B = 0;
vector<int> list_A;
vector<int> list_B;
vector<int> list_C;//结果存储在的序列
cout << "请输入列表A的元素个数：";
cin >> num_of_elements_in_A;
if (num_of_elements_in_A <= 0) {
cout << "元素个数不可以小于0！"<<endl;
return 1;
}
cout << "A列表元素个数为:" << num_of_elements_in_A << endl;
for (int i = 0; i < num_of_elements_in_A; i++) {
int temp = 0;
cout << "请输入列表A的第" << i + 1 << "个元素：";
cin >> temp;
list_A.push_back(temp);
}
cout << "请输入列表B的元素个数：";
cin >> num_of_elements_in_B;
if (num_of_elements_in_B <= 0) {
cout << "元素个数不可以小于0！" << endl;
return 1;
}
cout << "B列表元素个数为:" << num_of_elements_in_B << endl;
for (int i = 0; i < num_of_elements_in_B; i++) {
int temp = 0;
cout << "请输入列表B的第" << i + 1 << "个元素：";
cin >> temp;
list_B.push_back(temp);
}
sort(list_A.begin(), list_A.end());//把列表A中的元素进行非递减排列
sort(list_B.begin(), list_B.end());//把列表B中的元素进行非递减排列
vector<int>::iterator it_A= list_A.begin(), it_B= list_B.begin();
//进行比较，依次按照大小插入AB元素到C，任意列表指针移动到尾部就退出
while (it_A != list_A.end() && it_B != list_B.end()) {
if (*it_A <= *it_B) {
list_C.push_back(*it_A);
it_A++;
}
else if (*it_B < *it_A) {
list_C.push_back(*it_B);
it_B++;
}
}
//对还没插入C列表的元素进行处理
if (it_A == list_A.end()) {
for (; it_B != list_B.end(); it_B++)
{
list_C.push_back(*it_B);
}
}
if (it_B == list_B.end()) {
for (; it_A != list_A.end(); it_A++)
{
list_C.push_back(*it_A);
}
}
//对最终列表C的元素进行输出，检验结果
for (vector<int>::iterator it_C=list_C.begin(); it_C != list_C.end(); it_C++)
{
cout << *it_C << " ";
}
cout << endl;
system("pause");
return 0;
}
