【算法與資料結構實戰】線性表操作-合并兩個線性表中的元素

輸入：順序表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;
}