как сделать разницу, пересечение и симметричную разницу в множествах?

    #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);
}
→ Ссылка