【算法与数据结构实战】线性表操作-合并两个线性表中的元素-阿里云开发者社区

开发者社区> 人工智能> 正文
登录阅读全文

【算法与数据结构实战】线性表操作-合并两个线性表中的元素

简介: 输入:顺序表A,顺序表B 输出:合并了AB元素的顺序表C,其中C中元素按照非递减排列 分析:顺序表C是一个空表,首先取出顺序表A和B中的元素,并将这两个元素比较,如果A中的元素m1大于B中的元素n1,则将B中的元素n1插入C中,继续取出B中下一个元素n2与A中元素m1比较。

输入:顺序表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;
}

 

版权声明:本文内容由阿里云实名注册用户自发贡献,版权归原作者所有,阿里云开发者社区不拥有其著作权,亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容,填写侵权投诉表单进行举报,一经查实,本社区将立刻删除涉嫌侵权内容。

分享:
人工智能
使用钉钉扫一扫加入圈子
+ 订阅

了解行业+人工智能最先进的技术和实践,参与行业+人工智能实践项目

其他文章
最新文章
相关文章