home *** CD-ROM | disk | FTP | other *** search
/ ftp.disi.unige.it / 2015-02-11.ftp.disi.unige.it.tar / ftp.disi.unige.it / pub / .person / CataniaB / teach-act / testi-esami / labo-7.97 / bin.txt
Text File  |  1999-03-11  |  2KB  |  68 lines
  1. Prova di Laboratorio: Lunedi' 14 Luglio
  2.  
  3. - Bin Sorting -
  4.  
  5. Scopo dell'esercizio: ordinare un insieme di coppie (chiave,dato)
  6. in base al valore della chiave, utilizzando l'algoritmo di bin-sorting. 
  7. L'idea \`e quindi: inserire i dati in una tabella di liste, una per ogni
  8. valore delle chiavi, mantenendo un puntatore all'ultimo elemento; 
  9. ricostruire la lista ORDINATA IN BASE ALLE CHIAVI (NON in base al valore dei 
  10. dati!) semplicemente collegando tra loro le liste al passo precedente. 
  11. Il tutto deve avere complessita' lineare nel numero degli elementi da 
  12. ordinare. 
  13.  
  14. Svolgimento dell'esercizio:
  15.  
  16. Le chiavi sono numeri interi compresi tra 0 e M-1 con M fissato a priori; 
  17. i dati sono stringhe (ad esempio: nomi).   
  18.  
  19. Considerate un file di input  contenente i seguenti dati:
  20.  - Un intero N  che indica quante coppie (chiave,dato) leggere...;
  21.  - La sequenza delle coppie.
  22. Ad esempio:
  23.  
  24. 11          %n. di coppie da ordinare
  25. 1 Vittorio 
  26. 1 Mario
  27. 2 Augusto 
  28. 9 Nadia
  29. 2 Marco
  30. 5 Luca
  31. 1 Giovanni
  32. 3 Fabrizio
  33. 6 Giacomo
  34. 2 Roberto 
  35. 9 Luca
  36.  
  37. Quindi:
  38.  
  39. 1) Fissato M=10, definite la tabella dei bin utilizzando un array di LISTE
  40.    con un puntatore all'ultimo elemento (ad esempio: array di record 
  41.    primo/ultimo).
  42.  
  43. 2) Leggete il nome del file di input (questo per poter provare con file 
  44.    diversi).  
  45.  
  46. 3) Leggete i dati dal file di cui al passo (2)  ed inserite gli 
  47.    elementi nella tabella in base alla chiave 
  48.    (inserimento in tempo costante). 
  49.    Ricordatevi di mantenere il puntatore all'ultimo elemento di ogni lista. 
  50.  
  51. 4) Passo delicato: ricostruite un'unica lista a partire dalla tabella 
  52.    al passo 3, utilizzando il puntatore all'ultimo elemento 
  53.    in modo che il costo di tale procedimento sia lineare nel numero 
  54.    degli elementi.    
  55.  
  56. 5) Stampate la lista risultante (gli elementi devono essere ordinati rispetto
  57.    alle chiavi).
  58.  
  59. Ad esempio, dato il file precedente un possibile output e' il seguente:
  60.  
  61. Vittorio  Mario  Giovanni  Augusto  Roberto  Marco  Fabrizio  Luca 
  62. Giacomo   Nadia  Luca
  63.  
  64. Oss: gli elementi con lo stesso codice (ad esempio Vittorio, Mario e Giovanni 
  65. che hanno codice 1) non sono necessariamente ordinati tra loro.
  66. Luca compare due volte in posizioni diverse in quanto ha codice sia 5 che 9.
  67.  
  68.