PDA

Visualizza la versione completa : [C]Spiegazione codice per esame


Metalmino
12-02-2013, 22:03
Raga vi propongo questo codice. In pratica prende da file di testo un numero e il corrispettivo coseno e il programma deve calcolare il coseno del numero mancante usando la media pesata. Molto semplice, però non capisco la riga 48, la riga 54 e quindi la riga 80. Cioè, cosa sta a significare la comparazione con argc del main? Perchè poi passa argv[1] all'albero?
Grazie in anticipo!





001: #include <stdio.h>
002: #include <malloc.h>
003: #include <stdlib.h>
004:
005:
006: /*Struttura nodo*/
007: typedef int bst_key; /*definizione della tipologia della chiave di un BST */
008: typedef float bst_val;
009:
010: struct bst_node{
011: bst_key item; /*etichetta x BST*/
012: bst_val value; /*valore assegnato a questo nodo*/
013: int N; /*numero dei nodi del sottoalbero*/
014: struct bst_node *left; /*puntatore al sottolabero sx*/
015: struct bst_node *right; /*puntatore al sottolabero dx*/
016: };
017:
018:
019: // funzioni recuperate dalla libreria ed adattate
020: struct bst_node * bst_insertNode(struct bst_node *, bst_key, bst_val);
021:
022: void bst_visit_preorder(struct bst_node *);
023:
024: // struct bst_node * bst_searchNode(struct bst_node *, bst_key);
025:
026: struct bst_node * bst_rotR(struct bst_node *);
027:
028: struct bst_node * bst_rotL(struct bst_node *);
029:
030: struct bst_node * bst_partR(struct bst_node *, int);
031:
032: struct bst_node * bst_balanceR(struct bst_node * );
033:
034:
035: // funzioni nuove implementate
036: struct bst_node * read_lut(char *);
037:
038: bst_val bst_computeValue(struct bst_node *, bst_key);
039:
040: struct bst_node * bst_findPre(struct bst_node *, bst_key, struct bst_node *);
041:
042: struct bst_node * bst_findSuc(struct bst_node *, bst_key, struct bst_node *);
043:
044:
045:
046: int main(int argc, char *argv[])
047: {
048: if (argc < 2)
049: {
050: printf("USAGE: %s <lut filename>\n", argv[0]);
051: exit(0);
052: }
053: // carico la LUT nell'albero binario di ricerca
054: struct bst_node * bst = read_lut(argv[1]);
055:
056: // bilancio il BST
057: bst = bst_balanceR(bst);
058:
059: // stampo il BST
060: bst_visit_preorder(bst);
061:
062: // leggo la chiave da cercare/calcolare
063: printf("Inserisci il valore da valutare: ");
064: bst_key key;
065: scanf("%f", &key);
066: /*
067: struct bst_node * find = bst_searchNode(bst, key);
068: if (find)
069: value = find->value;
070: else
071: value = bst_computeValue(bst, key);
072:
073: printf("f(%f)=%f\n", key, value);
074: */
075: printf("f(%f)=%f\n", key, bst_computeValue(bst, key));
076: }
077:
078:
079:
080: struct bst_node * read_lut(char* lut_file)
081: {
082: // apro il file
083: FILE *f = fopen(lut_file, "r");
084: if (!f)
085: {
086: printf("ERROR opening file %s\n", lut_file);
087: exit(-1);
088: }
089:
090: struct bst_node * bst = NULL;
091: bst_key key;
092: bst_val val;
093: while(!feof(f))
094: {
095: // leggo chiave e valore dal file
096: if(fscanf(f, "%f %f", &key, &val) != 2)
097: continue;
098:
099: // inserisco il dato nell'albero binario di ricerca
100: bst = bst_insertNode(bst, key, val);
101: }
102:
103: // chiudo il file
104: fclose(f);
105: return bst;
106: }
107:
108:
109: bst_val bst_computeValue(struct bst_node * p, bst_key key)
110: {
111: // devo cercare il valore successivo e precedente
112: struct bst_node * pre = bst_findPre(p, key, NULL);
113: struct bst_node * suc = bst_findSuc(p, key, NULL);
114:
115: // se entrambi mi hanno restituito NULL vuol dire che non ho caricato la LUT: non ho informazioni e quindi restituisco 0
116: if(!pre && !suc)
117: return 0;
118:
119: // se non ho trovato uno dei due estremi vuol dire che ho chiesto una chiave al di fuori del range della LUT, quindi restituisco il valore di quell'estremo
120: if(!pre)
121: return suc->value;
122:
123: if(!suc)
124: return pre->value;
125:
126: // se pre == suc ho chiesto una chiave contenuta nella LUT, e quindi devo restituire il valore di quella chiave (non va usata la fomula)
127: if(pre == suc)
128: return pre->value;
129:
130: // se ho trovato entrambi gli estremi e sono diversi tra loro calcolo il valore usando la media pesata
131: return (pre->value * (suc->item - key) + suc->value * (key - pre->item)) / (suc->item - pre->item);
132: }
133:
134:
135: struct bst_node * bst_findPre(struct bst_node *p, bst_key key, struct bst_node *find)
136: {
137: // se questo albero e' vuoto
138: if(!p)
139: return find;
140:
141: // se questo nodo corrisponde esattamente alla chiave cercata lo restituisco
142: if(p->item == key)
143: return p;
144:
145: // se questo nodo ha una chiave minore della chiave cercata E
146: // non ho ancora trovato nessuna chiave OPPURE
147: // questa chiave e' migliore di quella trovata finora
148: if(p->item < key && (!find || p->item > find->item) )
149: find = p;
150:
151: // continuo la ricerca
152: if(key > p->item)
153: /*visita sottoalbero destro*/
154: find = bst_findPre(p->right, key, find);
155: else
156: /*visita sottoalbero sinistro*/
157: find = bst_findPre(p->left, key, find);
158:
159: return find;
160: }
161:
162:
163: struct bst_node * bst_findSuc(struct bst_node *p, bst_key key, struct bst_node *find)
164: {
165: // se questo albero e' vuoto
166: if(!p)
167: return find;
168:
169: // se questo nodo corrisponde esattamente alla chiave cercata lo restituisco
170: if(p->item == key)
171: return p;
172:
173: // se questo nodo ha una chiave maggiore della chiave cercata E
174: // non ho ancora trovato nessuna chiave OPPURE
175: // questa chiave e' migliore di quella trovata finora
176: if(p->item > key && (!find || p->item < find->item) )
177: find = p;
178:
179: // continuo la ricerca
180: if(key > p->item)
181: /*visita sottoalbero destro*/
182: find = bst_findSuc(p->right, key, find);
183: else
184: /*visita sottoalbero sinistro*/
185: find = bst_findSuc(p->left, key, find);
186:
187: return find;
188: }
189:
190:
191: /*Inserimento di un nodo*/
192: struct bst_node * bst_insertNode(struct bst_node * p, bst_key key, bst_val val)
193: {
194: if ( (p==NULL) ) /*raggiunto il punto di inserimento*/
195: {
196: /*Creazione nuovo nodo*/
197: p=(struct bst_node *) malloc(sizeof(struct bst_node));
198: p->item = key;
199: p->value = val;
200: p->N = 0;
201: p->left = NULL;
202: p->right = NULL;
203: }
204: else
205: {
206: p->N++;/*aumento il numero N del nodo*/
207: /* ricerca punto inserimento*/
208: if(key > p->item)
209: /*inserimento sottoalbero destro*/
210: p->right = bst_insertNode(p->right, key, val);
211: else
212: /*inserimento sottoalbero sinistro*/
213: p->left = bst_insertNode(p->left, key, val);
214: }
215: return (p); //ritorna il puntatore alla radice
216: }
217:
218:
219: // struct bst_node * bst_searchNode(struct bst_node * p, bst_key key)
220: // {
221: // if((p==NULL)||(p->item ==key)) /*ho raggiunto una foglia oppure ho trovato un nodo con la chiave ricercata*/
222: // return p;
223: // else /*continuo l ricerca*/
224: // {
225: // if(key > p->item)
226: // return bst_searchNode(p->right, key);
227: // else
228: // return bst_searchNode(p->left, key);
229: // }
230: // }
231:
232:
233: void bst_visit_preorder(struct bst_node *p)
234: {
235: if(!p)
236: return ;
237:
238: /*stampa nodo*/
239: printf("key: %f , val: %f , N: %d \n", p->item, p->value, p->N);
240: /*visita sottoalbero sinistro*/
241: bst_visit_preorder(p->left);
242: /*visita sottoalbero destro*/
243: bst_visit_preorder(p->right);
244: }
245:
246:
247: /* Rotazione a destra*/
248: struct bst_node * bst_rotR(struct bst_node * h)
249: {
250: struct bst_node * x = h->left;
251: h->left = x->right;
252: x->N=h->N; //aggiorno il numero dei nodi dei sottoalberi
253: x->right = h;
254: int i=0;
255: if(h->left!=NULL) i+=h->left->N+1;
256: if(h->right!=NULL) i+=h->right->N+1;
257: h->N=i;//N è la somma dei nodi del sottoalbero sinistro e destro
258: return x;
259: }
260:
261:
262: /* Rotazione a sinistra*/
263: struct bst_node * bst_rotL(struct bst_node * h)
264: {
265: struct bst_node * x = h->right;
266: h->right = x->left;
267: x->N=h->N;//aggiorno il numero dei nodi dei sottoalberi
268: x->left = h;
269: int i=0;
270: if(h->left!=NULL) i+=h->left->N+1;
271: if(h->right!=NULL) i+=h->right->N+1;
272: h->N=i;//N è la somma dei nodi del sottoalbero sinistro e destro
273: return x;
274: }
275:
276:
277: struct bst_node * bst_partR(struct bst_node * p, int k)
278: {
279: /*Combino selezioni e rotazioni*/
280: int t;
281: if (p->left==NULL) t=0;
282: else t = p->left->N+1;
283: if (t > k ){
284: p->left = bst_partR(p->left, k);
285: /*il nodo di indice k selezionato e un figlio sinistro,
286: quindi lo ruoto verso destra*/
287: p = bst_rotR(p);
288: }
289:
290: if (t < k ){
291: p->right = bst_partR(p->right, k-t-1);
292: /*il nodo di indice k selezionato e un figlio destro,
293: quindi lo ruoto verso sinistra*/
294: p = bst_rotL(p);
295: }
296: return p;
297: }
298:
299:
300: /* Bilanciamento*/
301: struct bst_node * bst_balanceR(struct bst_node * p)
302: {
303: /*se il nodo e' una foglia oppure ha un solo figlio ho finito*/
304: if (p->N < 2) return p;
305: /*Partiziono scegliendo l'indice del nodo corrispondente alla mediana*/
306: p = bst_partR(p, p->N/2);
307: /*Eseguo l'operazione ricorsivamente sul sottoalbero sinistro e destro*/
308: p->left = bst_balanceR(p->left);
309: p->right = bst_balanceR(p->right);
310: return p;
311: }
312:
313:

oregon
12-02-2013, 22:06
Non le capisci o non sai cosa sono argc, argv ?

Metalmino
12-02-2013, 22:25
Tutti e due... xD

oregon
12-02-2013, 22:31
Beh, se vai ad un esame (spero non universitario) di C senza sapere cosa siano argc, argv non c'è professore che ti farebbe passare ...

Tra i tantissimi link da leggere ...

http://digilander.libero.it/uzappi/C/C-main.html

Metalmino
12-02-2013, 22:40
Ciò che mi hai detto già lo sapevo, solo che per la risoluzione dei programmi non ho mai usato argc e argv e non capisco come lo abbia implementato nella sua soluzione, infatti il suddetto programma l'ho risolto con questo codice qui:



#include <stdio.h>
#include <stdlib.h>
#include <math.h>
typedef struct dati* lut;
struct dati{
int numero;
float coseno;
int N;
lut left;
lut right;
};
lut bast_rotR(lut h);
lut bast_rotL(lut h);
lut bast_partR(lut p, int k);
lut bast_balanceR(lut p);
lut bast_insertNode(lut p, int key, float cs);
void bast_visit_inorder(lut p);
lut bast_searchNode(lut p, int key);
lut bast_searchnumero(lut p, int key);
int main(int argc, char *argv[])
{
int n,x; float cos;
lut ia=NULL;
lut temp=NULL;
FILE* fp;
fp=fopen("LUT_cos.txt","r");
if(fp==NULL){
printf("File vuoto");
return 0;}
while(!feof(fp)){
fscanf(fp,"%d %f\n",&n,&cos);
ia=bast_insertNode(ia,n,cos);
}
printf("Ecco i valori:\n");
bast_visit_inorder(ia);
printf("\nInserisci il numero di cui vuoi il coseno:\n");
scanf("%d",&x);
temp=bast_searchNode(ia,x);
if(temp==NULL){
float m;
lut temp1=NULL; lut temp2=NULL;
temp1=bast_searchNode(ia,x-1);
temp2=bast_searchNode(ia,x+1);
m=((temp1->numero*temp1->coseno)+(temp2->numero*temp2->coseno))/(temp1->numero+temp2->numero);
ia=bast_insertNode(ia,x,m);
printf("\nIl coseno di %d vale %f\n", x,m);
printf("\nHo calcolato e inserito nella lista in ordine il coseno richiesto\n");
}

else printf("\nEcco i valori: %d\t%f\n",temp->numero,temp->coseno);
ia= bast_balanceR(ia);
bast_visit_inorder(ia);
system("PAUSE");
return 0;
}

lut bast_insertNode(lut p, int key, float cs)
{
if ( (p==NULL) )
{
p=(lut) malloc(sizeof(struct dati));
p->numero = key;
p->coseno=cs;
p->N = 0;
p->left = NULL;
p->right = NULL;
}
else
{
p->N++;
/* ricerca punto inserimento*/
if(key > p->numero)
/*inserimento sottoalbero destro*/
p->right = bast_insertNode(p->right, key, cs);
else
/*inserimento sottoalbero sinistro*/
p->left = bast_insertNode(p->left, key, cs);
}
return (p); //ritorna il puntatore alla radice
}

void bast_visit_inorder(lut p)
{
if(!p)
return ;
bast_visit_inorder(p->left);
printf("%d\t%f\n", p->numero, p->coseno);
bast_visit_inorder(p->right);
}

lut bast_searchNode(lut p, int key)
{
if((p==NULL)||(p->numero==key)) /*ho raggiunto una foglia oppure ho trovato un nodo con la chiave ricercata*/
return p;
else /*continuo l ricerca*/
{
if(key > p->numero)
return bast_searchNode(p->right, key);
else
return bast_searchNode(p->left, key);
}
}

lut bast_rotR(lut h)
{
lut x = h->left;
h->left = x->right;
x->N=h->N; //aggiorno il numero dei nodi dei sottoalberi
x->right = h;
int i=0;
if(h->left!=NULL) i+=h->left->N+1;
if(h->right!=NULL) i+=h->right->N+1;
h->N=i;//N è la somma dei nodi del sottoalbero sinistro e destro
return x;
}

lut bast_rotL(lut h)
{
lut x = h->right;
h->right = x->left;
x->N=h->N;//aggiorno il numero dei nodi dei sottoalberi
x->left = h;
int i=0;
if(h->left!=NULL) i+=h->left->N+1;
if(h->right!=NULL) i+=h->right->N+1;
h->N=i;//N è la somma dei nodi del sottoalbero sinistro e destro
return x;
}


lut bast_partR(lut p, int k)
{
/*Combino selezioni e rotazioni*/
int t;
if (p->left==NULL) t=0;
else t = p->left->N+1;
if (t > k ){
p->left = bast_partR(p->left, k);
/*il nodo di indice k selezionato e’ un figlio sinistro,
quindi lo ruoto verso destra*/
p = bast_rotR(p);
}

if (t < k ){
p->right = bast_partR(p->right, k-t-1);
/*il nodo di indice k selezionato e’ un figlio destro,
quindi lo ruoto verso sinistra*/
p = bast_rotL(p);
}
return p;
}


lut bast_balanceR(lut p)
{
/*se il nodo e’ una foglia oppure ha un solo figlio ho finito*/
if (p->N < 2) return p;
/*Partiziono scegliendo l’indice del nodo corrispondente alla mediana*/
p = bast_partR(p, p->N/2);
/*Eseguo l’operazione ricorsivamente sul sottoalbero sinistro e destro*/
p->left = bast_balanceR(p->left);
p->right = bast_balanceR(p->right);
return p;
}

oregon
12-02-2013, 22:46
Hai notato che tu apri un file con un nome fisso

fp=fopen("LUT_cos.txt","r");

e lui invece apre un file che può essere indicato dalla linea di comando

FILE *f = fopen(lut_file, "r");


?

Metalmino
12-02-2013, 22:57
Si ho appena notato, sono un microcefalo io xD

comunque scherzi a parte, per quanto possano valere parole scritte su un forum, grazie davvero oregon, non sai in questo tempo quanto tu mi sia stato d'aiuto. Grazie sincero :D

oregon
12-02-2013, 23:02
Originariamente inviato da Metalmino
Si ho appena notato

Capita a tutti ...


non sai

Di nulla ... (e invece so ... perché leggo tanti altri forum ... )

Loading