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