Fondamenti di Informatica - moduli A e B

Prof. M. Gavanelli, E. Lamma

29 Giugno 2016

Esercizio 1 (Punti 15 su 31 per parte B; ulteriori 20 su 32 per parte A) (1h e 30 min)

In un file binario  alimenti.bin, sono scritte le giacenze dei prodotti alimentari di un piccolo supermercato alimentare. Per ciascun prodotto, il file alimenti.bin contiene

• il nome del prodotto (stringa di 50 char),
• il numero di scatole (intero).

Ad esempio, per il prodotto cracker si ha:
"cracker" 439
perché ci sono 439 scatole di cracker.

In un secondo file, di testo, ordini.txt, sono scritti gli alimenti ordinati dal supermercato. Ad esempio:
"cracker" 40
"pasta" 100
"tonno" 80
se si è ordinato 40 scatole di cracker, 100 di pasta e 80 di tonno.

Si realizzi un programma C, organizzato in almeno tre funzioni, rispettivamente dedicate a:

1. a partire dal file alimenti.bin, creare una lista L in memoria centrale che contiene i dati dei prodotti, ordinata in base al nome del prodotto; la funzioneA riceve come parametri:
   • il puntatore al file,
   • il puntatore a L (inizializzato a NULL nel main ),
   più eventuali parametri a scelta, e restituisce il puntatore alla radice della lista L;
2. stampare la lista L a video; la funzioneB riceve come parametri:
   • il puntatore a L,
   più eventuali parametri a scelta, e restituisce void ;
3. caricare il contenuto del file ordini.txt in un opportuno array di strutture considerando che gli elementi nel file ordini.txt sono al massimo 100.

   FACOLTATIVO: Si potrebbe anche caricare l'array in memoria heap, allocando in heap lo spazio minimo indispensabile per contenere il file, senza doverlo sovradimensionare a 100 ...

4. mostrare a video il contenuto dell'array.
5. ordinare l'array in base al nome del prodotto utilizzando la funzione qsort .
6. a partire dall'array creato al punto 3 e dalla lista L creata al punto 1, produrre su un file di uscita l'elenco complessivo dei prodotti una volta ricevuti gli ordini, ciascun prodotto con la quantità totale (valore in lista più valore del prodotto nell'array). Il file di uscita output.txt deve essere consegnato con i codici sorgente; la funzioneC riceve come parametri
   • il puntatore al secondo file,
   • il puntatore a L,
   più eventuali parametri a scelta, e restituisce void ; si noti che non tutti i prodotti in lista compaiono nel file ordini.txt.

FACOLTATIVO: Considerando che sia la lista, sia l'array sono ordinati rispetto al nome del prodotto, è possibile scrivere un algoritmo simile al merge di due array ordinati ...

NOTA BENE: Si consegnino i sorgenti e il file di uscita generato. È possibile utilizzare librerie C (ad esempio per le stringhe). Nel caso si strutturi a moduli l'applicazione qualunque libreria utente va riportata nello svolgimento.

Esercizio 2 (Punti 3 su 31) (15 min)

NOTA BENE: Per questo esercizio si consegni la soluzione in un file complex.txt .

Sia data la seguente funzione fun che riceve un carattere e un albero binario di ricerca di caratteri

int fun(char i, tree T)
{ if (T!=NULL) 
    if (i==T->value) return (1);
        else 
             if (i<T->value) return (fun(i,T->left));
             else return fun(i,T->right); 
  else return 0;
}

Si indichi cosa fa la funzione fun e che tipo di algoritmo realizza. Se ne valuti anche la complessità asintotica come numero di test i==T->value , motivando adeguatamente, nel caso in cui il carattere i non appartenga all'albero T. Motivare adeguatamente la risposta.