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.99 / parte2.c < prev    next >
C/C++ Source or Header  |  2001-01-29  |  4KB  |  190 lines
  1. #include <stdio.h>
  2. #include <stdlib.h>
  3. #define MAX 100
  4.  
  5.  
  6. typedef struct cell * mset;
  7.  
  8. typedef unsigned char bool;
  9. typedef int elem;
  10.  
  11. typedef struct cell {
  12.                         elem el;
  13.                         int n;
  14.                         mset next;
  15.                     }cell;
  16.  
  17.  
  18.  
  19. mset makelem();
  20. mset empty();
  21. mset insert(elem,mset);
  22. void print(mset);
  23. mset delete(elem,mset);
  24.  
  25.  
  26. int main()
  27. {
  28.     mset s = empty();
  29.     int m;
  30.     FILE *fp;
  31.     char nome_f[20];
  32.     
  33.     printf("\nInserire il nome del file ");
  34.     scanf("%s",nome_f);
  35.  
  36.     fp=fopen(nome_f,"r");
  37.  
  38.     while (fscanf(fp,"%d",&m) && (m!=-1))
  39.     {
  40.         s=insert(m,s);
  41.     }
  42.     printf("\nIl multi-insieme e': ");
  43.     print(s);
  44.  
  45.     printf("\nFornisci valore: ");
  46.     scanf("%d",&m);
  47.  
  48.     s=delete(m,s);
  49.  
  50.     printf("\nEcco il nuovo multi-insieme: ");
  51.     print(s);
  52. }
  53.  
  54.  
  55.  
  56.  
  57. mset makelem()
  58. {
  59.     return (mset) malloc(sizeof(cell));
  60. }
  61.  
  62.  
  63.  
  64.  
  65.  
  66. mset empty()
  67. {
  68.   return NULL;
  69. }
  70.  
  71.  
  72. mset insert(elem el,mset s)
  73. {
  74.     mset prescorri,scorri, aux;
  75.  
  76.     
  77.     /* cerco la posizione (avanzo fino a trovare un elemento >= el o fine
  78.      * lista)*/
  79.     
  80.     for (prescorri = empty(), scorri = s; scorri != empty() &&
  81.       (scorri ->el < el); prescorri =scorri, scorri = scorri->next);
  82.     
  83.     if (scorri != empty()) /* ho trovato elemento >= el */
  84.        {
  85.           if (scorri -> el > el) /* el non e' presente, quindi lo devo
  86.                                   * aggiungere */
  87.               {
  88.                   if (prescorri != empty()) /* l'inserimento deve essere
  89.                                              * effettuato all'interno della
  90.                                              * lista */
  91.                                {aux = makelem();
  92.                             aux ->el = el;
  93.                     aux ->n =1;    
  94.                             prescorri ->next = aux;
  95.                                 aux ->next = scorri;
  96.                                 return s;}   
  97.                   else                      /* inserimento in prima
  98.                                              * posizione */
  99.                                              
  100.                                { aux = makelem();
  101.                                 aux ->el = el; 
  102.                               aux->n  =1;        
  103.                             aux->next =s;
  104.                          return aux;}    
  105.               }          
  106.           else /* elemento presente, aumento il numero di occorrenze */
  107.          { (scorri->n)++;    
  108.                 return s;               
  109.                  }
  110.        }
  111.     else /* la lista e' vuota o devo inserire in ultima posizione */
  112.        {
  113.           if (prescorri!= empty()) /* inserimento in ultima posizione */
  114.                               { aux = makelem();
  115.                             aux ->el = el;
  116.                             aux ->n = 1;
  117.                             prescorri ->next = aux;
  118.                                 aux ->next = scorri;
  119.                                 return s;
  120.                               }
  121.           
  122.           else /* la lista era vuota */
  123.                                {aux = makelem();
  124.                               aux ->el = el; 
  125.                            aux ->n = 1;
  126.                           aux->next =s;
  127.                        return aux;   }
  128.        }   
  129. }
  130.  
  131.  
  132.  
  133.  
  134. void print(mset s)
  135. {
  136.   int i;
  137.   printf("{ ");
  138.   for (; s!=empty() ; s = s ->next)
  139.     { 
  140.     for(i=0;i<s->n;i++)
  141.          printf("%d ",s->el);
  142.     }
  143.   printf("}\n");
  144. }
  145.  
  146.  
  147.  
  148. mset delete(elem el,mset s)
  149. {
  150.  
  151.   mset prescorri,scorri,aux ; /* prescorri punta alla locazione precedente a quella 
  152.                       * che verra' cancellata  */
  153.  
  154.  
  155.        /* cerco l'elemento */
  156.         
  157.     for (prescorri = empty(), scorri = s; scorri!=empty() && scorri ->el <
  158.     el; prescorri =scorri, scorri = scorri->next);
  159.     
  160.     
  161.     if (scorri!=empty() && (scorri->el == el))
  162.            {
  163.               if (prescorri==empty())
  164.                 {     /* l'elemento da cancellare e' in prima
  165.                     * posizione */
  166.                     
  167.                    if(scorri->n == 1)
  168.                  {aux = s;
  169.                             s = s->next ;
  170.                             free(aux);
  171.                                 }
  172.                         else (scorri->n)--; 
  173.                  }
  174.                      
  175.               else    /* l'elemento non e' in prima posizione */
  176.                  { 
  177.                        if(scorri->n == 1)
  178.                  {prescorri->next = scorri ->next;
  179.                          free(scorri);
  180.                          scorri = prescorri ->next; }
  181.                        else (scorri->n)--;
  182.                  }
  183.             }             
  184.                     
  185.   /* restituisco la lista di partenza;  */
  186.  
  187.   return s;
  188. }
  189.  
  190.