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 / parte1.c < prev    next >
C/C++ Source or Header  |  2001-01-29  |  2KB  |  123 lines
  1. /* Una possibile soluzione Esame di Laboratorio di Algoritmi febbraio 2000 */
  2.  
  3.  
  4. #include <stdio.h>
  5. #include <stdlib.h>
  6. #define B  20
  7. #define MAX  20
  8.  
  9.  
  10. /* fornisco l'implementazione piu' semplice, che non richiede allocazione dinamica */
  11.  
  12. /* PROTOTIPI */
  13.  
  14. int h(int x);
  15. int h1(int x, int n);
  16. void empty(int * tab);
  17. void insert(int n, int * tab);
  18. void print(int * tab);
  19. int member(int n,int *tab);
  20.  
  21. /* MAIN */
  22.  
  23.  
  24. main()
  25. {
  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 != -2)
  50.          insert(n,tab);
  51.  
  52.     /* stampo la tabella */
  53.  
  54.     print(tab);
  55.  
  56. }
  57.  
  58. /* FUNZIONI */
  59.  
  60.  
  61. int h(int x)
  62. {
  63.  return x % B;
  64. }
  65.  
  66.  
  67. int h1(int x, int n)
  68. {
  69.  return (h(x) + n) % B;
  70. }
  71.  
  72.  
  73. void empty(int * tab)
  74. {
  75.     int i;
  76.     for (i=0;i<B;i++)
  77.         tab[i] = 0;
  78. }
  79.  
  80. int member (int n,int * tab)
  81. {
  82.     int b,m=0;
  83.     b = h1(n,m);
  84.     while (m<B && tab[b] != 0) 
  85.         {if (tab[b] == n)  return 1;
  86.          m++;
  87.          b = h1(n,m);
  88.         } 
  89.     return 0;
  90. }
  91.  
  92. void insert(int n,int * tab)
  93. {
  94.     int b,m=0;
  95.     if (!(member(n,tab)))
  96.     {    
  97.         b = h1(n,m);
  98.         while (m<B && tab[b] != 0 && tab[b] != -1) 
  99.             { 
  100.               m++;
  101.               b = h1(n,m);
  102.             } 
  103.         if ( m < B ) tab[b] = n;    
  104.     }
  105. }
  106.                 
  107.  
  108.  
  109.  
  110. void print(int * tab)
  111. {
  112.     int i;
  113.     for (i=0;i<B;i++)
  114.     {
  115.         if (tab[i] != 0 && tab[i] != -1)
  116.            printf("%d: %d\n",i,tab[i]);
  117.         else
  118.            printf("%d: \n",i);
  119.  
  120.    }
  121.  
  122. }
  123.