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-10.00 / parte3.c < prev    next >
C/C++ Source or Header  |  2001-01-14  |  3KB  |  157 lines
  1. #include<stdio.h> 
  2. #include<stdlib.h> 
  3. #define B 10
  4.  
  5. /* la soluzione propone allocazione dinamica della tabella hash */
  6. /* gli esercizi potevano essere risolti anche con allocazione
  7. statica */
  8.  
  9. typedef struct cell{int el;
  10.                     struct cell*next;} cell;
  11. typedef cell*list; 
  12. typedef list*hash;
  13.  
  14.  
  15.  
  16. int h(int);
  17. hash empty();
  18. void insert(int,hash);
  19. void my_delete(int,hash);
  20. void print(hash);
  21.  
  22.  
  23.  
  24. int h(int n)
  25. {return(n%B);}
  26.  
  27.  
  28. hash empty() {
  29.  hash t;
  30.  int i;
  31.  t=(hash)calloc(B,sizeof(list));
  32.  for(i=0;i<B;i++)
  33.      t[i]=NULL;
  34.  return t;
  35.  }
  36.  
  37.  
  38. void insert(int n,hash t) {
  39.   int  b=h(n);
  40.   list l=t[b];
  41.   list prec=NULL, aux;
  42.  
  43. // scandisco la lista per trovare la posizione in cui inserire la nuova cella
  44.  
  45.   while (l!=NULL && l->el<n)
  46.     {
  47.        prec=l;
  48.        l=l->next;
  49.     }
  50.  
  51.   if (prec == NULL && (l == NULL ||  l ->el !=n)) // inserimento in testa
  52.   {
  53.        aux=(list)malloc(sizeof(cell));
  54.        aux->el=n;
  55.        aux->next=t[b];
  56.        t[b]=aux;
  57.        return;
  58.   }
  59.  
  60.  
  61.   if (l == NULL) // inserimento in fondo
  62.         {
  63.           aux=(list)malloc(sizeof(cell));
  64.           aux->el=n;
  65.           prec ->next = aux;
  66.           aux ->next = NULL;
  67.           return;
  68.         }
  69.  
  70.  /* se le prime due condizioni non sono verificate, l'inserimento
  71.     deve essere effettuato nel mezzo della lista */
  72.  
  73.   if (l->el !=n) /* l'elemento non e` gia` presente */
  74.     {
  75.        aux=(list)malloc(sizeof(cell));
  76.        aux->el=n;
  77.        prec ->next = aux;
  78.        aux ->next = l;
  79.     }
  80. }
  81.  
  82.  
  83.  
  84.  
  85.  
  86.  
  87. void my_delete(int n,hash t)
  88. {
  89.   int i;
  90.   list l, prec,aux; 
  91.   
  92.   for(i=0;i<B;i++)
  93.   {
  94.     l=t[i]; 
  95.     prec=NULL;
  96.     while((l!=NULL) && (l->el<n)) 
  97.       {prec=l;l=l->next;}
  98.     while(l!=NULL)
  99.          {
  100.            aux=l; 
  101.            l=l->next; 
  102.            free(aux);
  103.          }           
  104.     if(prec==NULL) 
  105.            t[i]=NULL;
  106.     else 
  107.            prec->next=NULL;
  108.    }
  109. }
  110.  
  111.  
  112.  
  113.  
  114.  
  115.  
  116. void print(hash t) {
  117.   int i;
  118.   list l;
  119.   for (i=0;i<B;i++)
  120.     {
  121.       printf("\n%d: ",i);
  122.       for(l=t[i];l!=NULL;l=l->next)
  123.             printf("%d ",l->el);
  124.       printf("\n");
  125.     }
  126. }
  127.  
  128.  
  129.  
  130.  
  131. main() {
  132.   char nome[20];
  133.   int n;
  134.   hash t;
  135.   FILE*fp;
  136.   t=empty();
  137.   printf("\nFornisci nome del file: ");
  138.   scanf("%s",nome);
  139.   if(fp=fopen(nome,"r"))
  140.   {
  141.     while(fscanf(fp,"%d",&n) && n!=-1)
  142.         insert(n,t);
  143.   }
  144.   else exit(EXIT_FAILURE);
  145.  
  146.   printf("\n\nLa tabella e':\n");
  147.   print(t);
  148.   printf("\n\nFornisci numero: \n");
  149.   scanf("%d",&n);
  150.   my_delete(n,t);
  151.   printf("\n\nLa nuova tabella e': \n");
  152.   print(t);
  153.  
  154.   fclose(fp);
  155.   return 0;
  156. }
  157.