Newsgroup: it.comp.lang.c
Titolo: Funzione random e alberi binari di ricerca

Buongiorno a tutto il NG,
dovrei risolvere il seguente problema e avendo pochissimo tempo e poca
esperienza mi chiedevo se qualcuno di voi lo avesse per caso già fatto e
potesse darmi il codice oppure buttare giù qualche idea e qualche stralcio
di codice. Lo so, la richiesta forse non è delle più ortodosse, però sono
proprio in una situazione critica.
Mi appello alla vostra clemenza, grazie a tutti e scusate.
Problema: Creare con la funzione "random" due insiemi di dimensioni
variabili (da 1 a 20) con valori variabili (da 1 a 20). Ordinare questi due
insiemi e calcolarne l'unione, l'intersezione e la differenza utilizzando
gli alberi binari di ricerca.

 gli alberi binari di ricerca.
Considerando che poi si fanno operazioni insiemistiche,
forse andrebbe specificato se i due insiemi possono
contenere o meno elementi ripetuti. Assumiamo che gli
elementi siano unici. Questo complica lievemente la
generazione (bisogna controllare di non generare lo stesso
numero due volte nello stesso insieme), ma semplifica le
operazioni successive.
La prima parte e' proprio una bischerata, la puoi fare in
tanti modi diversi.
Questo e' un modo, non il migliore, ma corto.
/* funzione che genera numeri casuali tra 0 e n-1 */
int myrand(int n){return 1+(int)(((double)(n))*rand()/(RAND_MAX+1.0));}
/* funzione che mette i numeri tra 1 e n in un vettore di n posizioni */
void randvec(int n, int *V)
{
   int i,r,t;
   /* numeri da 1 a 20 */
   for (i=0; i<n; i++) V[i]=i+1;
   /* swap a caso per mescolarli */
   for (i=n-1; i>=1; i++)
   { r=myrand(i+1); t=V[r]; V[r]=V[i]; V[i]=t;}
}
/* funzione per il qsort di interi */
int compInt(const void *a, const void *b)
{
   return *(int *)a - *(int *)b;
}
/* funzione che basandosi sulla bisezione determina
se il valore x e' contenuto o no nel vettore ORDINATO V
di dimensione nV; QUESTA TE LA SCRIVI DA SOLO
IN CINQUE MINUTI DOPO AVER STUDIATO LA RICERCA BINARIA!!!! */
int Presente(int x, int *V, int nV)
{
.........
}
int main(....
......
int A[20],B[20]; /* alloco lo spazio massimo necessario */
int Differenza[20], Intersezione[20], Unione[20];
/* nota: ci sono in gioco i numeri da 1 a 20, quindi anche
l'unione al massimo ha 20 elementi... */
int nA, nB, nD, nI, nU; /* numeri contenuti nei vari set */
srand(time(0)); /* per inizializzare i numeri casuali */
/* genero i vettori casuali */
randvec(20,A);
randvec(20,B);
/* li restringo (idealmente) alla loro porzione iniziale:
in questo modo ottengo sottoinsiemi di nA e nB numeri
casuali tra 1 e 20 (e senza ripetizioni).
nA=1+myrand(20);
nB=1+myrand(20);
/* stampo i bastardissimi insiemi */
printf("A[%d] = ",nA);
for (i=0; i<nA; i++) printf("%d ",A[i]); printf("\nB[%d] = ",nB);
for (i=0; i<nB i++) printf("%d ",B[i]); printf("\n");
/* ordino gli insiemi */
qsort(A,nA,sizeof(int),compInt);
qsort(B,nB,sizeof(int),compInt);
/* ri-stampo i bastardissimi insiemi per vedere se ho
cannato qualcosa o se sono ordinati */
printf("A[%d] = ",nA);
for (i=0; i<nA; i++) printf("%d ",A[i]); printf("\nB[%d] = ",nB);
for (i=0; i<nB i++) printf("%d ",B[i]); printf("\n");
/* USANDO la ricerca binaria trovo l'unione.
(questa non e' la cosa piu' furba da fare,
avendo i vettori ordinati bastava fare una
specie di merge. ma se e' quello richiesto... )
*/
/* l'unione contiene almeno tutti gli elementi di A */
for (i=0; i<nA; i++) Unione[i]=A[i];
nU=nA;
/* aggiungo tutti gli elementi di B che non sono
gia' in A (e quindi in Unione)*/
for (i=0; i<nB; i++)
  if (!Presente(B[i],A,nA)) Unione[nU++]=B[i];
/* USANDO la ricerca binaria trovo l'intersezione
(questa non e' la cosa piu' furba da fare,
avendo i vettori ordinati bastava fare una
specie di merge. ma se e' quello richiesto... )
*/
/* l'intersezione non contiene una mazza, inizialmente */
nI=0;
/* aggiungo tutti gli elementi di B che sono presenti
anche in A */
for (i=0; i<nB; i++)
  if (Presente(B[i],A,nA)) Intersezione[nI++]=B[i];
/* DIFFERENZA: e questa te la fai tu */
Piu' di questo non penso sia il caso di dirti.
ciao,
g.