PDA

Visualizza la versione completa : esercizio sui vettori in C


Haring01
23-01-2012, 13:15
devo fare questo semplice esercizio in C:
Scrivere una funzione int diffvals(int A[], int B[], int n) che presi in input due array A e B, ognuno di n interi, ritorna il numero di valori distinti che o sono presenti in A ma non in B oppure sono presenti in B ma non in A.
Es:
A = {1,2,1,3,3} B = {5,2,2,5,2} diffvals(A, B, 5) ritorna 3

io la funzione l'ho fatta in questo modo:



int diffvals(int a[], int b[], int n){
int j,k,Fa=1,Fb=1,count=0;

for(int i=0;i<n;i++){
j=0; k=0;

while(Fa==1 && j<n){
if(a[i]!=b[j])
Fa=1;
else
Fa=0;

j++;
}

while(Fb==1 && k<n){
if(b[i]!=a[k])
Fb=1;
else
Fb=0;

k++;
}

if(Fa==1)
count++;

if(Fb==1)
count++;

}

return count;
}


però è sbagliata perchè se, come nell'esempio, ci sono due valori uguali nello stesso vettore, la funzione conta entrambi. Sapreste aiutarmi voi? io ho pensato di mettere tutti i valori distinti (comprese le ripetizioni) in un terzo vettore e poi fare la verifica li ma so che non è giusta come cosa

ramy89
23-01-2012, 13:49
Le sai usare le liste? Se le sai usare non è poi così difficile risolvere il problema.
i è in [0,4].
Per ogni elemento i-esimo di A:
-Se A[i] non è presente nella lista lo inserisci nella lista;

Per ogni elemento i-esimo di B:
-Se B[i] è già presente nella lista, in qualche modo lo marchi come "falso".

Per ogni elemento i-esimo di B:
-Se B[i] non è presente nella lista lo inserisci nella lista.

Questo in tre cicli for separati.
Alla fine della procedura tutti gli elementi presenti nella lista e non marcati come "falsi" saranno quelli presenti solo in A o solo in B.
Per tenere traccia dei valori marcati come "falsi" puoi definire una struttura.
Ho calcolato approssimativamente n^2/2 operazioni, con n=5.Sicuramente ci sarà una procedura più veloce.

Haring01
23-01-2012, 13:57
il ragionamento potrebbe essere giusto, proverò a fare in questo modo
grazie :)

Haring01
23-01-2012, 15:14
ecco ho modificato il codice così:



struct distinti{
int val;
int flag;
struct distinti *next;
};

typedef struct distinti distinti;
typedef struct distinti *testa;

int diffvals(int a[], int b[], int n){
testa m=NULL;
int f,count;

for(int i=0;i<n;i++){
if(verifica(m))
m=add_head(m,a[i]);
else{
while(m!=NULL){
if(a[i]!=m->val)
f=1;
else
f=0;

m=m->next;
}

if(f==1)
m=add_head(m,a[i]);
}
}

for(int i=0;i<n;i++){
while(m!=NULL){
if(b[i]==m->val)
m->flag=1; //b[i] è gia presente nella lista
else
m->flag=0; //b[i] non è presente nella lista

m=m->next;
}
}

for(int i=0;i<n;i++){
if(verifica(m))
m=add_head(m,b[i]);
else{
while(m!=NULL){
if(b[i]!=m->val)
f=1;
else
f=0;

m=m->next;
}

if(f==1)
m=add_head(m,b[i]);
}
}

while(m!=NULL){
if(m->flag!=1)
count++;
}

svuota(m);

return count;
}

testa add_head(testa m, int valore){
testa nuovo=malloc(sizeof(distinti));
nuovo->val=valore;
nuovo->next=m;
return nuovo;
}


void svuota(testa m){
testa temp;

if(m!=NULL){
do {
temp=m;
m=m->next;
free(temp);
}while(m!=NULL);
}
else
return;

}

int verifica(testa m){
int s=0;

if(m==NULL)
s=1;

return s;
} //ritorna 1 se è vuota, 0 se non lo è


però non riesco a capire perchè all'inizio quando la lista è vuota insierisce correttamente il primo valore del vettore A, poi il secondo sovrascrivo il primo nella lista e così via, quindi la lista è sempre e solo di un elemento

Loading