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:
Rispondi quotando