Разница множеств с использованием qsort

Question

Дано два массива целых чисел ? и ?. Требуется найти все такие значения элементов массива ?, которых нет среди элементов массива ?. В задаче необходимо использовать функцию qsort из стандартной библиотеки языка C. В первой строке записано целое число ? (1 <= ? <= 10^5) — количество элементов массива ?. Во второй строке через пробел записано ? целых чисел, каждое из которых не превосходит 10^9 по абсолютной величине — элементы массива ?. В следующих двух строках в аналогичном формате записаны элементы массива ?. В первой строке выведите одно целое число — количество значений, удовлетворяющих описанному условию. Во второй строке выведите все такие значения в порядке возрастания. в коде все, в принципе, верно. Но считаются и выводятся также повторяющиеся элементы, а мне этого не нужно. Подскажите как исправить, пожалуйста

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
 
bool search_value (int a[], int size, int value) {
    for (int i=0; i<size; i++)
        if (a[i] == value)
            return true;
    return false;
}
 
void get_error (int error_code, const char message[]) {
    fputs(message, stderr);
    exit(error_code);
}
 
bool get_elements (int a[], int size) {
    for (int i = 0; i < size; i++)
        if (scanf("%d", &a[i]) != 1)
            return false;
    return true;
}
 
int cmp (const void * one, const void * two) {
    return *(int *)one - *(int *)two;
}
 
int main (void) {
    int n, m;
    if (scanf("%d", &n) != 1 || n < 1)          
        get_error(1, "Wrong size of array!");
 
    int *a = (int *) calloc(n, sizeof(int));    
    if (a == NULL)
        get_error(2, "Can't allocate memory!");
 
    if ( !get_elements(a, n) ) {                
        free(a);
        get_error(3, "Can't read the data!");
    }
 
    if (scanf("%d", &m) != 1 || m < 1) {            
        free(a);
        get_error(1, "Wrong size of array!");
    }
    int *b = (int *) calloc(m, sizeof(int));    
    if (b == NULL) {
        free(a);
        get_error(2, "Can't allocate memory!");
    }
    if ( !get_elements(b, m) ) {                
        free(a);
        free(b);
        get_error(3, "Can't read the data!");
    }
 
    int *unique = (int *) calloc(n, sizeof(int));   
    if (unique == NULL) {
        free(a);
        free(b);
        get_error(2, "Can't allocate memory!");
    }
 
    int size = 0;   
    for (int i = 0; i < n; i++)                     
        if ( !search_value(b, m, a[i]) )
            unique[size++] = a[i];
 
    printf("%d\n", size);                   
    if (size > 0) {
        qsort(unique, size, sizeof(int), cmp);
        for (int i = 0; i < size; i++)
            printf("%d ", unique[i]);
        puts("");
    }
 
    free(a);            
    free(b);
    free(unique);
    return 0;
}

Answer 1

Вот как это можно сделать, только я не под ваш ввод-вывод писал, а чтоб понятнее - перепишите сами.

#include <stdlib.h>
#include <stdio.h>
#include <string.h>

int comp(const void* a_, const void* b_) {
    return *(int*)a_ - *(int*)b_;
    }

int main() {
    int N = 20;
    int* A = malloc(N * sizeof(int));
    int* B = malloc(N * sizeof(int));
    int* C = malloc(N * sizeof(int));

    for (int i = 0; i < N; ++i) {
        A[i] = rand() % 30;
        B[i] = rand() % 30;
        }

    for (int i = 0; i < N; ++i) printf("%d ", A[i]);

    puts("");

    for (int i = 0; i < N; ++i) printf("%d ", B[i]);

    puts("");
    // Отсортировали
    qsort(A, N, sizeof(int), comp);
    qsort(B, N, sizeof(int), comp);

    puts("");
    for (int i = 0; i < N; ++i) printf("%d ", A[i]);
    puts("");
    for (int i = 0; i < N; ++i) printf("%d ", B[i]);
    puts("");

    // Выбросили дубли
    int* a = A, *b = B;
    int NA, NB;

    for (int* c = a; ++a < A + N; NA = c - A + 1)
        if (*c != *a && ++c != a) * c = *a;

    for (int* c = b; ++b < B + N; NB = c - B + 1)
        if (*c != *b && ++c != b) * c = *b;

    puts("");
    for (int i = 0; i < NA; ++i) printf("%d ", A[i]);
    puts("");
    for (int i = 0; i < NB; ++i) printf("%d ", B[i]);
    puts("");

    // Находим разность отсортированных смножеств
    a = A;
    b = B;
    int j = 0;

    while (a < A + NA) {
        if (b == B + NB) {
            for (; a < A + NA;) C[j++] = *a++;

            break;
            }

        if (*a < *b) C[j++] = *a++;
        else {
            if (*b >= *a) a++;

            b++;
            }
        }

    printf("%d\n", j);
    for (int i = 0; i < j; ++i) printf("%d ", C[i]);
    puts("");
    }

БЛОГ НА HUSL

Разница множеств с использованием qsort

Ответы (1 шт):