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 / parte4.c < prev    next >
C/C++ Source or Header  |  2001-01-29  |  2KB  |  143 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 my_union(int * tab1,int * tab2);
  24.  
  25. /* MAIN */
  26.  
  27.  
  28. main() {
  29.  
  30.     FILE * fp;
  31.     char nome[MAX];
  32.     int n;
  33.     int tab1[B], tab2[B] ;
  34.  
  35.  
  36.     /* svuoto le tabelle */
  37.  
  38.     empty(tab1);
  39.     empty(tab2);
  40.  
  41.     /* leggo il nome del file */
  42.  
  43.     printf("Fornisci il nome del file: ");
  44.     scanf("%s", nome);
  45.  
  46.     /* apro il file in lettura */
  47.  
  48.     fp = fopen(nome,"r");
  49.  
  50.  
  51.     /* carico i dati nelle tabelle  */
  52.  
  53.     while (fscanf(fp,"%d",&n) && n != -2)
  54.            insert(n,tab1);
  55.  
  56.     while (fscanf(fp,"%d",&n) && n != -2)
  57.         insert(n,tab2);
  58.  
  59.     /* stampo le tabelle */
  60.     
  61.     printf("\nPrima tabella: \n");
  62.     print(tab1);
  63.     printf("\nSeconda tabella: \n");
  64.     print(tab2);
  65.  
  66.     /* calcolo union */
  67.  
  68.     my_union(tab1,tab2);
  69.  
  70.     /* stampo tabella unione */
  71.  
  72.     printf("\nTabella Unione: \n");
  73.     print(tab1);
  74. }
  75.  
  76. /* FUNZIONI */
  77.  
  78.  
  79. int h(int x) {
  80.  return x % B;
  81. }
  82.  
  83.  
  84. int h1(int x, int n) {
  85.  return (h(x) + n) % B;
  86. }
  87.  
  88.  
  89. void empty(int * tab) {
  90.     int i;
  91.     for (i=0;i<B;i++)
  92.         tab[i] = 0;
  93. }
  94.  
  95. int member (int n,int * tab) {
  96.     int b,m=0;
  97.     b = h1(n,m);
  98.     while (m<B && tab[b] != 0)
  99.         {if (tab[b] == n)  return 1;
  100.          m++;
  101.          b = h1(n,m); 
  102.         }
  103.     return 0;
  104. }
  105.  
  106. void insert(int n,int * tab) {
  107.     int b,m=0;
  108.     if (!(member(n,tab)))
  109.     {
  110.         b = h1(n,m);
  111.         while (m<B && tab[b] != 0 && tab[b] != -1)
  112.             {
  113.               m++;
  114.               b = h1(n,m); 
  115.             }
  116.         if ( m < B ) tab[b] = n;
  117.     }
  118. }
  119.  
  120.  
  121.  
  122.  
  123. void print(int * tab) {
  124.     int i;
  125.     for (i=0;i<B;i++)
  126.     {
  127.         if (tab[i] != 0 && tab[i] != -1)
  128.            printf("%d: %d\n",i,tab[i]);
  129.         else
  130.            printf("%d: \n",i);
  131.  
  132.    }
  133.  
  134. }
  135.  
  136. void my_union(int * tab1,int * tab2)
  137. {
  138.     int i;
  139.     for (i=0;i<B;i++)
  140.         insert(tab2[i],tab1);
  141.  
  142. }
  143.