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-6.97 / hash.txt next >
Text File  |  1999-03-11  |  3KB  |  133 lines
  1. Prova di Laboratorio: Martedi' 17 Giugno
  2.  
  3. - Tabelle Hash -
  4.  
  5. Lo scopo dell'esercizio e' rappresentare mediante una tabella hash 
  6. un sottoinsieme I di numeri naturali.
  7.  
  8. Fissiamo la funzione di hashing h: Nat --> 0..M-1, con M stabilito a priori, 
  9. definita come  h(x)=x modulo M (cioe' il resto della divisione di x per M).
  10.  
  11. In questo caso per tabella hash si intende un array T con indici 0...M 
  12. di liste di naturali (cioe' le chiavi coincidono con gli elementi 
  13. da rappresentare) tale che la lista in posizione T[i] contenga tutti gli 
  14. elementi x di I con h(x)=i. 
  15.  
  16. Svolgimento dell'esercizio:
  17.  
  18. Considerate un file di input  contenente i seguenti dati:
  19.  
  20.  - Un intero N  che denota la cardinalita' dell'insieme da rappresentare 
  21.    con la tabella hash (cioe` quanti numeri leggere...);
  22.  - La sequenza di numeri (interi positivi) dell'insieme.
  23.  
  24. Allora:
  25.  
  26. 1) Definite la struttura dati in C per rappresentare una tabella hash
  27.     utilizzando un array di LISTE, fissando M=8.  
  28. 2) Leggete il nome del file di input (questo per poter provare con file 
  29.    diversi).  
  30. 3) Leggete i dati dal file di cui al passo 2) ed inserite gli elementi nella 
  31.    tabella (senza ripetizioni) sulla base della funzione di hashing 'h' 
  32.    definita qui sopra (in C il resto della divisione si ha con 
  33.    l'operatore %). 
  34. 4) Stampate la tabella di hash bucket per bucket.   
  35.  
  36. Ad esempio, dato il file:
  37.  
  38. 12
  39.  
  40. 23 45 8 12 46 8 1 100 2 67 11 98
  41.  
  42. L'output deve contenere le seguenti informazioni:
  43.  
  44. Tabella:
  45.  
  46. 0 ->8 
  47. 1 ->1 
  48. 2 ->98 2 
  49. 3 ->11 67 
  50. 4 ->100 12 
  51. 5 ->45 
  52. 6 ->46 
  53. 7 ->23 
  54.  
  55. %%%%%% Una possibile soluzione %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
  56.  
  57. #include <stdio.h>
  58. #include <string.h>
  59. #define M 8
  60. #define h(x) x%M
  61.  
  62. /* liste di adiacenza */
  63.  
  64. typedef struct cella* lista;
  65. struct cella 
  66.  { int x; 
  67.    lista next; 
  68.  };
  69.  
  70. /* tabella di hashing: */
  71.  
  72. lista Tabella[M];
  73.  
  74.  
  75. /* Tutto nel programma principale */
  76.  
  77. main()
  78. {
  79.  
  80.  FILE *in; 
  81.  
  82.  int E,N;   
  83.  int v,w,V,W; 
  84.  lista aux;
  85.  
  86.  in=fopen("input","r");
  87. fscanf(in,"%d",&N);       
  88.  
  89.  for (v=0;v<=N;v++)          /* Inizializzo la tabella */
  90.     Tabella[v]=NULL;
  91.  
  92. /* Lettura e inserimento (nella tabella) degli archi */
  93.   if (in==stdin) printf("Elementi\n"); 
  94.   for (v=0;v<N;v++) 
  95.     {    
  96.       fscanf(in,"%d",&V);
  97.       aux=Tabella[h(V)];
  98.  
  99. /* Controllo se l'elemento esiste gia */
  100.  
  101.       while (aux!=NULL && aux->x != V) aux=aux->next;
  102.  
  103. /* Se non c'e' lo aggiungo alla lista di V */
  104.  
  105.       if (aux==NULL)
  106.        { 
  107.          aux=(lista)malloc(sizeof(struct cella));
  108.          aux->x=V; 
  109.          aux->next=NULL;
  110.          aux->next=Tabella[h(V)]; 
  111.          Tabella[h(V)]=aux; 
  112.          E++; 
  113.        }  
  114.     }
  115.  
  116. /* Stampa della tabella */
  117.  
  118.   printf("\nTabella:\n");
  119.   for (v=0;v<M;v++)    
  120.    { 
  121.      printf("%d ->",v);
  122.      aux=Tabella[v];
  123.      while(aux!=NULL)     
  124.       {  
  125.         printf("%d ",aux->x);
  126.         aux=aux->next;
  127.       } 
  128.      printf("\n");
  129.     }
  130.   printf("\nNo. elementi:%d\n",E);
  131. }
  132.  
  133.