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