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-2.00 / parte2.c < prev    next >
C/C++ Source or Header  |  2001-01-29  |  2KB  |  128 lines
  1. /* Una possibile soluzione Esame di Laboratorio di Algoritmi
  2. febbraio 2000 */
  3.  
  4.  
  5. #include <stdio.h> 
  6. #include <stdlib.h> 
  7. #define B  20
  8. #define MAX  20
  9.  
  10. /* fornisco l'implementazione piu' semplice, che non richiede
  11. allocazione dinamica */
  12.  
  13. /* PROTOTIPI */
  14.  
  15. int h(int x); 
  16. int h1(int x, int n); 
  17. void empty(int * tab); 
  18. void insert(int n, int * tab); 
  19. void print(int * tab);
  20. int member(int n,int *tab);
  21.  
  22. /* MAIN */
  23.  
  24.  
  25. main() {
  26.  
  27.     FILE * fp;
  28.     char nome[MAX];
  29.     int n;
  30.     int tab[B];
  31.  
  32.  
  33.     /* svuoto la tabella */
  34.  
  35.     empty(tab);
  36.  
  37.     /* leggo il nome del file */
  38.  
  39.     printf("Fornisci il nome del file: ");
  40.     scanf("%s", nome);
  41.  
  42.     /* apro il file in lettura */
  43.  
  44.     fp = fopen(nome,"r");
  45.  
  46.  
  47.     /* carico i dati nella tabella  */
  48.  
  49.     while (fscanf(fp,"%d",&n) && n != -22)
  50.         insert(n,tab);
  51.  
  52.     /* stampo la tabella */
  53.  
  54.     print(tab);
  55.     
  56.     /*leggo numero da cercare */
  57.     
  58.     printf("\nFornisci numero: ");
  59.     scanf("%d",&n);
  60.     
  61.     /* cerco numero e stampo messaggio */
  62.     
  63.     if (member(n,tab))
  64.             printf("\nNumero presente");
  65.     else
  66.             printf("\nNumero non presente");        
  67. }
  68.  
  69. /* FUNZIONI */
  70.  
  71.  
  72. int h(int x) {
  73.  return x % B;
  74. }
  75.  
  76.  
  77. int h1(int x, int n) {
  78.  return (h(x) + n) % B;
  79. }
  80.  
  81.  
  82. void empty(int * tab) {
  83.     int i;
  84.     for (i=0;i<B;i++)
  85.         tab[i] = 0;
  86. }
  87.  
  88. int member (int n,int * tab)
  89. {
  90.     int b,m=0;
  91.     b = h1(n,m);
  92.     while (m<B && tab[b] != 0) 
  93.         {if (tab[b] == n)  return 1;
  94.          m++;
  95.          b = h1(n,m);
  96.         } 
  97.     return 0;
  98. }
  99.  
  100. void insert(int n,int * tab)
  101. {
  102.     int b,m=0;
  103.     if (!(member(n,tab)))
  104.     {    
  105.         b = h1(n,m);
  106.         while (m<B && tab[b] != 0 && tab[b] != -1) 
  107.             { 
  108.               m++;
  109.               b = h1(n,m);
  110.             } 
  111.         if ( m < B ) tab[b] = n;    
  112.     }
  113. }
  114.  
  115.  
  116. void print(int * tab) {
  117.     int i;
  118.     for (i=0;i<B;i++)
  119.     {
  120.         if (tab[i] != 0 && tab[i] != -1)
  121.            printf("%d: %d\n",i,tab[i]);
  122.         else
  123.            printf("%d: \n",i);
  124.  
  125.    }
  126.  
  127. }
  128.