[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!

codice:

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:

codice:

#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

**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 ... )

Discussione: [C]Spiegazione codice per esame

Strumenti discussione

Ricerca discussione

Visualizza

[C]Spiegazione codice per esame

Permessi di invio