Przejdź do zawartości

Kody źródłowe/Porównanie dwóch posortowanych list

Z Wikibooks, biblioteki wolnych podręczników.
Metoda • Porównanie dwóch posortowanych list
Metoda
Porównanie dwóch posortowanych list
Wypisywanie wstawień i usunięć z dwóch list przy założeniu że są posortowane. (testowane VC2015)

C++

[edytuj]
#include <random>
#include <stdint.h>
#include <algorithm>

using namespace std;

const int Count = 1000;
vector<int16_t> vecA,vecB;

void generate()
{
	mt19937 gen(0);
	uniform_int_distribution<int16_t> dis(0, Count-1);
	for (int i=0; i<Count; i++)
		vecA.push_back(dis(gen));
	uniform_int_distribution<int16_t> dis1(0, Count/4-1);
	for (int i = 0; i<Count; i++)
	{
		int n = dis1(gen);
		if (n==0);//don't add
		else if (n == 1)
			vecB.push_back(dis(gen));
		else 
			vecB.push_back(vecA[i]);
	}
}


void compare(vector<int16_t> vecA, vector<int16_t> vecB)
{
	int i0 = 0, i1 = 0;
	while (i0 < vecA.size() && i1 < vecB.size())
	{
		if (vecA[i0] < vecB[i1])
		{
			printf("usuniety %d\n", vecA[i0]);
			i0++;
		}
		else if (vecA[i0] > vecB[i1])
		{
			printf("dodany %d\n", vecB[i1]);
			i1++;
		}
		else
		{
			i0++;
			i1++;
		}
	}
	//dokonczenie
	while (i0 < vecA.size())
	{
		printf("usuniety (koncowka) %d\n", vecA[i0]);
		i0++;
	}
	while (i1 < vecB.size())
	{
		printf("dodany (koncowka) %d\n", vecB[i1]);
		i1++;
	}
}


int main()
{
	generate();
	std::sort(vecA.begin(), vecA.end());
	std::sort(vecB.begin(), vecB.end());
	compare(vecA, vecB);
    return 0;
}