[C] Esercizio ordine elementi di un vettore

[floppyes]

Ciao a tutti!
E' da questa mattina che ci sbatto la testa ma niente da fare, non ne vengo fuori!!
Testo dell'esercizio:
Si sviluppi un programma in linguaggio C che riceva in ingresso due vettori, IN1 e IN2, di 10 elementi interi maggiori di zero. Si supponga che i vettori siano inseriti dall’utente in ordine crescente e che non contengano elementi ripetuti (i due vettori possono pero’ avere elementi in comune). Il programma deve creare e stampare un terzo vettore OUT di 20 elementi interi, ordinato in senso crescente, che includa tutti gli elementi di IN1 e IN2 senza ripetizioni (gli eventuali elementi non utilizzati di OUT devono essere posti a zero).
Ad esempio:
IN1: 2 5 9 14 15 20 25 27 30 32
IN2: 3 5 10 11 12 22 23 25 26 27
OUT: 2 3 5 9 10 11 12 14 15 20 22 23 25 26 27 30 32 0 0 0

Ne ho provate di tutte, ma in un caso non riesco a mettere gli zeri in fondo, nell'altro mi si blocca il programma!
Prima versione: l'utente riempe i due vettori con numeri interi maggiori di zero, il programma prende i numeri dei due vettori e li fonde in un unico vettore, ordina poi tutti gli elementi del vettore. Quello che non riesco a fare è eliminare i doppioni, spostare il codice indietro di una posizione e piazzare in fondo al vettore di uscita gli zeri

#include <stdio.h>
#define DIM1 10
#define DIM2 20
int main ()
{
int IN1[DIM1], IN2[DIM1], IN3 [DIM2], IN4[DIM2], k=0,zeri=0;
int i,j, temp;
printf("Riempi il primo vettore con %d numeri maggiori di zero in ordine crescente:\n", DIM1);
for (i=0;i<DIM1;i++)
{
scanf("%d", &IN1[i]);
if (IN1[i]<0)
i--;
}
printf("Riempi il secondo vettore con %d numeri maggiori di zero in ordine crescente:\n", DIM1);
for (i=0;i<DIM1;i++)
{
scanf("%d", &IN2[i]);
if (IN2[i]<0)
i--;
}
printf("\nEcco il vettore prima di essere ordinato:\n");
for (i=0;i<DIM1;i++)
{
IN3[i]=IN1[i];
printf("%4d", IN3[i]);
}
for (i=0;i<DIM1;i++)
{
IN3[i+DIM1]=IN2[i];
printf("%4d", IN3[i+DIM1]);
}
for(i=0;i<DIM2;i++)
{
for(j=0;j<i;j++)
{
if (IN3[i]<IN3[j])
{
temp=IN3[i];
IN3[i]=IN3[j];
IN3[j]=temp;
}
}
}
printf("\nEcco il vettore dopo averlo ordinato:\n");
for (i=0;i<DIM2;i++)
{
printf("%4d", IN3[i]);
}
return 0;
}

Seconda versione che mi è venuta in mente: l'utente riempie sempre i due vettori, poi il programma confronta il primo vettore con il secondo, se trova un numero che non è presente nel secondo vettore lo aggiunge a quello in uscita, altrimenti passa al successivo. Poi prende tutti i numeri del secondo vettore e li aggiunge al vettore in uscita, in questo modo non avrò doppioni ed inoltre avrò tutti gli zeri in fondo al vettore di uscita (poichè all'inizio lo riempio con tutti zeri). Mi serve solo riordinare il vettore e sono a posto. Il problema è che il programma si blocca al confronto tra i due vettori:

#include <stdio.h>
#define DIM1 10
#define DIM2 20
int main ()
{
int vett1[DIM1], vett2[DIM1], out[DIM2]={0}, k=0,zeri=0;
int i,j, temp,s=0;
printf("Riempi il primo vettore con %d numeri maggiori di zero in ordine crescente:\n", DIM1);
for (i=0;i<DIM1;i++)
{
scanf("%d", &vett1[i]);
if (vett1[i]<0)
i--;
}
printf("Riempi il secondo vettore con %d numeri maggiori di zero in ordine crescente:\n", DIM1);
for (i=0;i<DIM1;i++)
{
scanf("%d", &vett2[i]);
if (vett2[i]<0)
i--;
}
printf("\nEcco il vettore prima di essere ordinato:\n");
for (i=0;i<DIM1;i++)
{
for (j=0;j<DIM1;j++)
{
if (vett1[i]!=vett2[j])
{
out[s]=vett1[i];
s++;
}
}
}
for (i=0;i<DIM1;i++)
{
out[s]=vett2[i];
s++;
}
for (i=0;i<DIM2;i++)
{
printf("%4d", out[i]);
}
return 0;
}

Se riuscite a dirmi come finire l'esercizio o seguendo la prima strada o la seconda vi offro un paio di litri di caffè
Grazie mille in anticipo
Ciaoo

[Atem1]

Scusa non ho tempo per guardare cosa c'è che non va, quindi l'ho semplicemente rifatto leggermente "evoluto" e cioè:
-con allocazione dinamica della memoria (inserisci il numero di valori che vuoi, quindi non l'ho fissato a 10)
-puoi aggiungere qualsiasi valore (e non solamente valori maggiori di 0)

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

int *crea_vettore(int n);
void visualizza_vettore(int *v, int n);
void unisci_vettori(int *v3, int *v2, int n2, int vecchia_dimensione, int *dimensione_finale);
void insert_sort(int *v, int n);

int main()
{
    int n1, n2, n3=0;
    int *v1, *v2, *v3;

    printf("Quanti valori vuoi inserire nel primo vettore? ");
    scanf("%d", &n1);
    v1=crea_vettore(n1);
    insert_sort (v1, n1);

    printf("\nQuanti valori vuoi inserire nel secondo vettore? ");
    scanf("%d", &n2);
    v2=crea_vettore(n2);
    insert_sort (v2, n2);

    v3=calloc(n1+n2, sizeof(int));
    unisci_vettori(v3, v1, n1, 0, &n3);
    unisci_vettori(v3, v2, n2, n3, &n3);
    insert_sort(v3, n3);

    printf("\nIl vettore ordinato e': \n");
    visualizza_vettore(v3, n1+n2);

    free(v1);
    free(v2);
    free(v3);


    return 0;
}

int *crea_vettore(int n)
{
    int i;
    int *v=malloc(n*sizeof(int));
    for (i=0; i<n; i++)
    {
        printf("Inserisci il %d valore: ", i+1);
        scanf("%d", &v[i]);
    }
    return v;
}


void visualizza_vettore(int *v, int n)
{
    int i;
    for (i=0; i<n; i++) printf ("%d ", v[i]);
}

void scambia(int *a, int *b)
{
    int tmp=*a;
    *a=*b;
    *b=tmp;
}

void insert_sort(int *v, int n)
{
    int i, j, tmp;
    for (i=1; i<n;i++) if (v[i]<v[0]) scambia (&v[i], &v[0]);

    for (i=2; i<n; i++)
    {
        tmp=v[i];
        j=i;
        while (tmp < v[j-1])
        {
            v[j]=v[j-1];
            j--;
        }
        v[j]=tmp;
    }

}


int valore_assente(int* v, int dim, int x)
{
    int i;
    for (i=0; i<dim; i++) if (v[i]==x) return 0;
    return 1;

}


void unisci_vettori(int *v3, int *v2, int n2, int vecchia_dimensione, int *dimensione_finale)
{
    int i, j=0;
    for (i=0; i<n2 ;i++)
    {
        if (valore_assente(v3, j+vecchia_dimensione, v2[i]))
        {
            v3[j+vecchia_dimensione]=v2[i];
            j++;
        }
    }
    *dimensione_finale=j+vecchia_dimensione;
}

Nota l'utilizzo della calloc che inizializza a 0 tutti gli elementi del nuovo vettore.
Con allocazione statica della memoria avrei dovuto scorrere gli n1+n2 elementi del nuovo vettore e inizializzarli a 0 manualmente.

E poi nota:

insert_sort(v3, n3);
...
visualizza_vettore(v3, n1+n2);

n3 sarebbe la dimensione reale del terzo vettore (cioè senza i doppioni) mentre n1+n2 chiaramente è la somma delle dimensioni degli altri due vettori.

Quindi nell'esempio da te citato n3 corrisponde a 17, mentre n1+n2 vale 20.
1.Ho inizializzato a zero tutti gli elementi (n1+n2) del nuovo vettore,
2.Ho unito i due vettori nel nuovo vettore senza i doppioni sono n3 elementi (usando la procedura unisci_vettori)
3.Ho ordinato il nuovo vettore di n3 elementi (usando l'Insert Sort)
4.Ho visualizzato gli n1+n2 elementi

Comunque fra pochi giorni avrò l'esame quindi non posso più risponderti perchè ho bisogno di concetrarmi su quello.
Se ci sono cose che non hai capito e nessun altro ti avrà risposto, ti risponderò Sabato.

[apatriarca]

Con allocazione statica della memoria avrei dovuto scorrere gli n1+n2 elementi del nuovo vettore e inizializzarli a 0 manualmente.

Non è assolutamente vero. È infatti sufficiente scrivere out[DIM2]={0} come ha fatto giustamente floppyes.

Non ho tempo di fornire una risposta completa, ma entrambi i vostri codici sono incredibilmente molto più complicati di quanto non sia necessario. Gli array in input sono ORDINATI, per cui è sufficiente scorrere i due array in contemporanea e inserire nell'array di output l'elemento più piccolo tra quelli correnti dei due array (incrementando quindi il corrispondente indice). Quando i valori sono uguali, si inserisce il valore nell'array di output e si incrementano entrambi gli indici. Il codice è molto simile al "merge" nel mergesort..

[Atem1]

"apatriarca":

Con allocazione statica della memoria avrei dovuto scorrere gli n1+n2 elementi del nuovo vettore e inizializzarli a 0 manualmente.

Non è assolutamente vero. È infatti sufficiente scrivere out[DIM2]={0} come ha fatto giustamente floppyes.

Ah ok ti ringrazio perchè questa cosa non la sapevo.

"apatriarca":Gli array in input sono ORDINATI.

Avevo letto molto velocemente il testo e non mi ero accorto che dicesse che fossero già ordinati infatti li ho ordinati.

"apatriarca":
Non ho tempo di fornire una risposta completa, ma entrambi i vostri codici sono incredibilmente molto più complicati di quanto non sia necessario.

Però quello che ho scritto io è modulare nel senso che se volessi aggiungere un terzo o un quarto vettore o un i-esimo, sarebbe sufficiente, per ogni nuovo vettore X creato, aggiungere la riga:

unisci_vettori(vfinale, vx, nx, nfinale, &nfinale);

[apatriarca]

L'operazione di merging è associativa e commutativa sui vettori ordinati. In particolare merge(v1, v2, v3) = merge(merge(v1, v2),v3) = merge(v1, merge(v2, v3)) = merge(v2, merge(v1, v3)) = ... A patto di avere una funzione che calcoli questa operazione su due array ordinati, non vedo differenze rispetto al tuo codice in quanto a modularità.

[Atem1]

"apatriarca":L'operazione di merging è associativa e commutativa sui vettori ordinati. In particolare merge(v1, v2, v3) = merge(merge(v1, v2),v3) = merge(v1, merge(v2, v3)) = merge(v2, merge(v1, v3)) = ... A patto di avere una funzione che calcoli questa operazione su due array ordinati, non vedo differenze rispetto al tuo codice in quanto a modularità.

Sì è vero, hai ragione. Non avevo pensato proprio quello che hai scritto dopo "a patto" e cioè che ci realizzavi una funzione che operi sempre su due vettori ordinati.
Mi sono confuso perchè nel frattempo sto facendo un altro esercizio e penso a più cose tutte insieme...

[floppyes]

Ciao Atem!
Grazie per la soluzione, però non ho capito bene come fai a fare certi passaggi, comunque ti lascio al tuo esame in caso ci risentiamo a fine settimana
In bocca al lupo!

"apatriarca":

Con allocazione statica della memoria avrei dovuto scorrere gli n1+n2 elementi del nuovo vettore e inizializzarli a 0 manualmente.

Non è assolutamente vero. È infatti sufficiente scrivere out[DIM2]={0} come ha fatto giustamente floppyes.
Non ho tempo di fornire una risposta completa, ma entrambi i vostri codici sono incredibilmente molto più complicati di quanto non sia necessario. Gli array in input sono ORDINATI, per cui è sufficiente scorrere i due array in contemporanea e inserire nell'array di output l'elemento più piccolo tra quelli correnti dei due array (incrementando quindi il corrispondente indice). Quando i valori sono uguali, si inserisce il valore nell'array di output e si incrementano entrambi gli indici. Il codice è molto simile al "merge" nel mergesort..

Ciao!
Ho provato a riscrivere il codice:

#include <stdio.h>
#define DIM1 10
#define DIM2 20
int main ()
{
int IN1[DIM1], IN2[DIM1], OUT[DIM2]={0}, i, j, num, s=0;
printf("Riempi il primo vettore:\n");
for (i=0;i<DIM1;i++)
{
scanf("%d", &num);
IN1[i]=num;
}
printf("Riempi il secondo vettore:\n");
for (i=0;i<DIM1;i++)
{
scanf("%d", &num);
IN2[2]=num;
}
for (i=0;i<DIM1;i++)
{
for (j=0;j<DIM1;j++)
{
if (IN1[i]!=IN2[i])
{
OUT[s]=IN1[i];
s++;
}
}
}
for (i=0;i<DIM1;i++)
{
OUT[s]=IN2[i];
}
printf("\n");
for (i=0;i<DIM2;i++)
{
printf("%4d", OUT[i]);
}
return 0;
}

L'utente riempie i due vettori, poi faccio partire un ciclo che si dovrebbe comportare in questo modo: confronto l'elemento i del primo vettore con tutti gli elementi j del secondo vettore, se l'elemento i è diverso dall'elemento j allora lo aggiungo al vettore in uscita, altrimenti passo al successivo.
Fatto questo avrò nel vettore in uscita solamente i numeri del primo vettore che non sono ripetuti nel secondo, allora aggiungo con un altro ciclo for tutti i numeri del secondo vettore a quello in uscita. Manca solo la parte di codice per ordinare il vettore, però il codice non mi funziona perché se inserisco:

IN1: 2 5 9 14 15 20 25 27 30 32
IN2: 3 5 10 11 12 22 23 25 26 27

ottengo come output:

2 2 2 2 2 2 2 2 2 2 5 5 5 5 5 5 5 5 5 5

Penso anche io che il codice sia più semplice più che altro perchè devo scriverlo a mano su foglio di carta in meno di 60 minuti (contando che devo rispondere anche a delle domande di teoria )
Grazie
Ciaoo!

[apatriarca]

Non ho provato il codice (e sono un po' di fretta) ma dovrebbe venire qualcosa del genere..

int unisci(int v1[10], int v2[10], int out[20])
{
    int i = 0, j = 0, k = 0;
    while (i < 10 && j < 10) {
        if (v1[i] < v2[j]) {
            out[k++] = v1[i++];
        } else if (v1[i] == v2[j]) {
            out[k++] = v1[i++]; ++j;
        } else {
            out[k++] = v2[j++];
        }
    }
    while (i < 10) { out[k++] = v1[i++]; }
    while (j < 10) { out[k++] = v2[j++]; }
    return k;
}

[floppyes]

Ciao!

Cavolo funziona alla perfezione

Però non ho capito due cose:
Con il ciclo while passo ogni elemento dei due vettori, se l'elemento del primo vettore è più piccolo dell'elemento del secondo vettore, allora copio l'elemento all'interno del vettore di uscita out. Se l'elemento del primo vettore è uguale all'elemento del secondo vettore allora copio l'elemento del primo vettore e incremento la variabile del secondo vettore, così da passare all'elemento successivo.
Se invece l'elemento del secondo vettore è più grande di quello del primo vettore allora stampo direttamente nel vettore in uscita il valore del secondo elemento.

Gli ultimi due cicli while invece a cosa servono? Ed inoltre perchè hai messo return k?

Grazie mille era da due giorni che non ne venivo fuori!

Ciaoo

[apatriarca]

k è l'indice nel vettore in uscita, per cui quel return k serve per restituire il numero di elementi non nulli nel vettore di destinazione. Il primo ciclo while si ferma quando uno dei due indici che rappresentano le posizioni nei due vettori di input raggiunge la fine del vettore. Ma l'altro indice potrebbe non aver raggiunto la fine. Gli ultimi due cicli servono per copiare gli eventuali elementi rimanenti nei vettori di input dopo il primo ciclo all'interno di quello di destinazione. Di fatto al massimo uno dei due cicli verrà eseguito almeno una volta.

[floppyes]

Ciao!

Grazie mille per la spiegazione! adesso mi torna tutto

Grazie ancora!
Ciaoo