Dati due insiemi A e B trovare l'insieme differenza

[dalca]

Buongiorno a tutti,
sto svolgendo un esercizio il quale mi chiede, mediante il linguaggio C, di scrivere una funzione che, dati due insiemi A e B di numeri naturali, mi calcoli l'insieme C differenza dei due.

Quanto sono riuscito a fare è il seguente listato:

#include <stdio.h>

int differenza(int u[], int n, int v[], int m, int z[]);

int main(void) {
    int A[] = {1, 2, 3, 4, 5}, B[] = {3, 4, 5, 6, 7}, C[5];
    int na = 5, nb = 5, nc, i;
    
    nc = differenza(A, na, B, nb, C);
    
    printf("\nLa differenza dei due insiemi è:\n");
    
    for(i = 0; i < nc; i++) {
        printf("%d ", C[i]);
    }
    printf("\n");
    
    return(0);
    
}


int differenza(int u[], int n, int v[], int m, int z[]) {
    int i, j, ok, d = 0;
    
    for(i = 0; i < n; i++) {
        ok = 1;
        for(j = 0; j < m && ok == 1; j++) {
            if(u[i] == v[j]) {
                ok = 0;
            }
        }
        if(ok == 1) {
            z[d++] = u[i];
        }
    }
    
    return(d);
}

Questo listato però non funziona perché con gli insiemi di esempio mi trova solo l'insieme differenza {1,2} mentre dovrebbe essere {1,2,6,7}.
Qualcuno mi può dare una dritta su come risolvere?
Grazie.

 

[DispatchCode]

Dovresti riguardare l'algoritmo che hai scritto, ci sono almeno un paio di errori.
Per esempio quando u[i] = 4 fai solo 2 cicli nell'array interno, poichè 4 != 3 quando j=0; nel ciclo dopo hai j=1 quindi v[j] = 4 di conseguenza 4 == 4 e setti "ok = 0", questo interrompe il ciclo.

Anche risolvendo questo avresti il secondo problema: assegni a 'z' solo i valori provenienti da 'u'; nel caso di specie i due valori che devi prendere sono nell'altro array.

La cosa più semplice che mi viene in mente, se hai solo i valori che hai mostrato o comunque nr ragionevolmente bassi, è mapparli in un altro array.
eg

int differenza(int u[], int n, int v[], int m, int z[]) {
    int i, j, d = 0, k = 0;
    int tmp[10] = {0};

    for(i = 0; i < n; i++) {
        tmp[u[i]]++; tmp[v[i]]++;
    }

    for(k=0; k < 10; k++) {
        if(tmp[k] & 1) z[d++] = k;
    }

    return(d);
}

In pratica: conti quante volte compaiono negli array i nr, indistintamente dall'array, e alla fine prendi tutti quelli che hanno come contatore 1 (presenti quindi solo in uno dei due array).

Non è molto efficiente in termini di spazio, poichè per 5 elementi ne sto sprecando altri 5 (eg. tmp = 10).
Se puoi avere numeri più grandi dovresti creare questo array più grande; immagina se hai li dentro nell'array il nr 500, dovresti fare tmp = 500, il che lo renderebbe... inadatto.

 

[M1n021]

Ciao, innanzitutto va detto che la differenza tra insiemi non è commutativa e che l'insieme differenza A-B è costituito dall'insieme di elementi di A che non appartengono a B .
Nel caso specifico sarebbe A-B = {1,2} e B-A = {6,7} , e quindi, stando alla traccia, il risultato che ottieni è corretto.
Inoltre, sempre stando alla traccia, farei qualcosa del genere, che mi sembra molto più chiaro e conciso:

#include <stdio.h>

#define N 5

unsigned int u_meno_v(int *u, unsigned int dim_u, int *v, unsigned int dim_v, int *w)
{
    unsigned int dim_w = 0;
    for(unsigned int i_u = 0, i_v; i_u < dim_u; i_v == dim_v ? w[dim_w++] = u[i_u++] : ++i_u)
    {
        for(i_v = 0; i_v < dim_v && v[i_v] != u[i_u]; ++i_v);
    }
    return dim_w;
}

int main()
{
    int A[N] = {1, 2, 3, 4, 5};
    int B[N] = {3, 4, 5, 6, 7};
    int C[N];
    for(unsigned int dim_C = u_meno_v(A, N, B, N, C), i = 0; i < dim_C; printf("%d ", C[i++]));
    printf("\n");
    return 0;
}

Se invece quello che vuoi ottenere è l'insieme {1,2,6,7} (che insiemisticamente può essere visto come l'unione di A e B meno la loro intersezione), oltre all'utilizzo di una sorta di tabella hash suggerita da @DispatchCode, si possono utilizzare diversi approcci, il cui livello di efficienza dipende anche dalle caratteristiche dei due array di partenza; per esempio (anche se in teoria degli insiemi non sarebbe possibile) A e B possono avere al loro interno elementi che si ripetono?

 

[BAT]

dovrebbe essere {1,2,6,7}

questa non è la differenza ma la differenza simmetrica (A-B) unione (B-A), che puoi calcolare anche con (A unione B) - (A intersezione B) nel caso avessi già definito il codice per il calcolo di unione e intersezione tra insiemi (il che ti obbliga in ogni caso a scrivere il codice per il calcolo della differenza tra 2 insiemi)

 

[dalca]

Innanzi tutto grazie per le risposte,
L'esercizio chiede A-B per cui è stato un mio errore ritenere che la differenza A-B fosse {1,2,6,7} e involontariamente ho svolto l'esercizio correttamente.
Comunque ora provo anche a risolvere la differenza simmetrica (A-B) unione (B-A).
Grazie ancora per le risposte e i suggerimenti.

 

[DispatchCode]

Devo essere sincero, non ho nemmeno letto la consegna, ho solo basato la risposta su quanto avevi realizzato.