как сделать разницу, пересечение и симметричную разницу в множествах?
#include <iostream>
#include <windows.h>
using namespace std;
int max_SIZE = 1000;
void SortSet(int Set[], int SIZE)
{
int i, j, k, p;
for (i = 0; i < SIZE - 1; i++)
{
p = 0;
for (j = SIZE - 1; j > i; j--)
if (Set[j] < Set[j - 1])
{
k = Set[j];
Set[j] = Set[j - 1];
Set[j - 1] = k;
p = 1;
}
if (p == 0) return;
}
}
void GenerationSet(int* Set, int SIZE)
{
int i = 0;
Set[i] = 2000 - rand() % 1000;
int temp;
while (i < SIZE)
{
temp = 1000 - rand() % 2000;
for (int j = 0; j < SIZE; j++)
if (temp == Set[j]) continue;
i++;
Set[i] = temp;
}
SortSet(Set, SIZE);
}
void ShowSet(int* Set, int SIZE)
{
cout << endl;
for (int i = 0; i < SIZE; i++)
cout << Set[i] << "\t";
cout << endl;
}
int FindSet(int* const Set, int const x, int const SIZE)
{
if (x < Set[0])
{
return -1;
}
if (Set[0] == x)
return 0;
if (x > Set[SIZE - 1])
{
return -1;
}
if (Set[SIZE - 1] == x)
return SIZE - 1;
int i0 = 1;
int i1 = SIZE - 1;
while (i0 < i1) {
int i01 = (i0 + i1) / 2;
if (Set[i01] == x)
return i01;
if (x < Set[i01])
i1 = i01;
else
i0 = i01 + 1;
}
return -1;
}
int InsertSet(int* Set, int x, int& SIZE)
{
int temp;
if (x < Set[0])
{
for (int i = SIZE; i > 0; i--)
Set[i] = Set[i - 1];
Set[0] = x;
SIZE++;
return 1;
}
if (x > Set[SIZE - 1])
{
Set[SIZE] = x;
SIZE++;
return 1;
}
if (Set[SIZE - 1] == x) return 0;
for (int i = 0; i < SIZE - 1; i++)
{
if (Set[i] == x) return 0;
if (Set[i]<x && Set[i + 1]>x)
{
temp = i;
break;
}
}
for (int i = SIZE; i > temp; i--)
Set[i] = Set[i - 1];
Set[temp + 1] = x;
SIZE++;
return 1;
}
void DifferSet(int* Set, int SIZE, int* Set_1, int SIZE_1, int* Set_2, int
& SIZE_2)
{
SIZE_2 = 0;
for (int i = 0; i < SIZE; i++)
if (FindSet(Set_1, Set[i], SIZE_1) == -1)
InsertSet(Set_2, Set[i], SIZE_2);
}
void IntersectionSet(int* Set, int SIZE, int* Set_1, int SIZE_1, int* Set_3, int
& SIZE_3) {
SIZE_3 = 0;
for (int i = 0; i < SIZE; i++)
if (FindSet(Set_1, Set[i], SIZE_1) != -1)
InsertSet(Set_3, Set[i], SIZE_3);
}
int DelSet(int* Set, int x, int& SIZE)
{
int temp = -1;
for (int i = 0; i < SIZE; i++)
{
if (Set[i] == x)
{
temp = i;
break;
}
}
if (temp == -1) return 0;
for (int i = temp; i < SIZE; i++)
Set[i] = Set[i + 1];
SIZE--;
return 1;
}
void UnionSet(int* Set, int SIZE, int* Set_1, int SIZE_1, int* Set_0, int
& SIZE_0)
{
SIZE_0 = SIZE;
for (int i = 0; i < SIZE; i++)
Set_0[i] = Set[i];
for (int i = 0; i < SIZE_1; i++)
InsertSet(Set_0, Set_1[i], SIZE_0);
}
int main()
{
int SIZE = 0;
int SIZE_1 = 0;
int SIZE_0 = 0;
int SIZE_2 = 0;
int SIZE_3 = 0;
int x,y;
SetConsoleCP(1251);
SetConsoleOutputCP(1251);
int* Set = new int[max_SIZE];
int* Set_1 = new int[max_SIZE];
int* Set_0 = new int[max_SIZE];
int* Set_2 = new int[max_SIZE];
int* Set_3 = new int[max_SIZE];
cout << "Введите размер первого множества, которая должна быть сгенерирована" << endl;
cin >> SIZE;
GenerationSet(Set, SIZE);
ShowSet(Set, SIZE);
cout << "Введите размер второго множества, которая должна быть сгенерирована" << endl;
cin >> SIZE_1;
GenerationSet(Set_1, SIZE_1);
ShowSet(Set_1, SIZE_1);
cout << "Результат объединения двух множеств" << endl;
UnionSet(Set, SIZE, Set_1, SIZE_1, Set_0, SIZE_0);
ShowSet(Set_0, SIZE_0);
UnionSet(Set, SIZE, Set_1, SIZE_1, Set_0, SIZE_0);
cout << "Результат разницы двух множеств" << endl;
DifferSet(Set, SIZE, Set_1, SIZE_1, Set_2, SIZE_2);
ShowSet(Set_2, SIZE_2);
cout << "Результат пересечение двух множеств" << endl;
IntersectionSet(Set, SIZE, Set_1, SIZE_1, Set_3, SIZE_3);
ShowSet(Set_3, SIZE_3);
cout << "Введите значение элемента для вставки в первую множество" << endl;
cin >> x;
if (InsertSet(Set, x, SIZE) == 0) cout << "Такой элемент в множестве уже присутствует"<<endl;
ShowSet(Set, SIZE);
cout << "Введите значение элемента для удаления из первого множества" << endl;
cin >> x;
if (DelSet(Set, x, SIZE) == 0)cout << "Такой элемент в множестве отсутствует" << endl;
ShowSet(Set, SIZE);
cout << "Введите значение элемента для вставки в другую множество" << endl;
cin >> y;
if (InsertSet(Set_1, y, SIZE_1) == 0) cout << "Такой элемент в множестве уже присутствует" << endl;
ShowSet(Set_1, SIZE_1);
cout << "Введите значение элемента для удаления из второго множества" << endl;
cin >> y;
if (DelSet(Set_1, y, SIZE_1) == 0)cout << "Такой элемент в множестве отсутствует" << endl;
ShowSet(Set_1, SIZE_1);
return 0;
}
Ответы (1 шт):
Автор решения: AlexGlebe
→ Ссылка
Сначала напишем ещё вспомогательную функцию поиска элемента.
// not found = -1
// found = index
int FindSet(int * const Set, int const x, int const SIZE)
{
if (x < Set[0])
{
return -1;
}
if (Set[0] == x)
return 0;
if (x > Set[SIZE - 1])
{
return -1;
}
if (Set[SIZE - 1] == x)
return SIZE - 1;
int i0 = 1;
int i1 = SIZE - 1;
// ищем в пределах [ i0 .. i1 )
while (i0 < i1) {
int i01 = (i0 + i1) / 2 ;
if (Set[i01] == x)
return i01 ;
if (x < Set[i01])
i1 = i01 ;
else
i0 = i01 + 1; }
return -1 ; }
Дальше уже у вас всё написано. Разница множества находиться путём цикла из первого и поискам во втором. Сначала создаём пустое множество как результат. Если во втором не нашлось, добавляем его в результат. А если нашлось то нет.
У вас написано объединение :
void UnionSet(int* Set, int SIZE, int* Set_1, int SIZE_1, int* Set_0, int
& SIZE_0)
{
SIZE_0 = SIZE;
for (int i = 0; i < SIZE; i++)
Set_0[i] = Set[i];
for (int i = 0; i < SIZE_1; i++)
InsertSet(Set_0, Set_1[i], SIZE_0);
}
Переделываем на разницу :
void DifferSet(int* Set, int SIZE, int* Set_1, int SIZE_1, int* Set_0, int
& SIZE_0)
{
SIZE_0 = 0 ;
for (int i = 0; i < SIZE; i++)
// ищем элемент из первого множества, находявшееся
// во втором
if (FindSet(Set_1,Set[i],SIZE_1) == -1)
// если не нашёлся, то добавляем в результат
InsertSet(Set_0, Set[i], SIZE_0);
}