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-6.98 / turno1 / parte3.c < prev    next >
C/C++ Source or Header  |  1999-03-11  |  3KB  |  132 lines
  1. /* Esame 18 giugno '98 - turno 1 - parte 3 */
  2.  
  3. #include <stdio.h>
  4. #include <stdlib.h>
  5.  
  6. #define MAX 30
  7.  
  8. typedef struct link *list;
  9.  
  10. struct link
  11. {
  12.   int el;
  13.   list next;
  14. };
  15.  
  16. void insert(int i, list *l)
  17. {
  18.   list current, previous, new;
  19.  
  20.   /* creazione nuova cella */
  21.   /* nota bene: posso farlo subito perche` voglio le ripetizioni */
  22.   new=(list) malloc(sizeof(struct link)); 
  23.   new->el=i;
  24.   /* new->next deve essere ancora determinato */
  25.   
  26.   /* ricerca punto di inserimento */
  27.   current=*l;                           
  28.   previous=NULL; /* nessuna posizione precedente a quella di testa! */
  29.   while (current!=NULL && i>current->el) /* attenzione all'ordine dell'and! */
  30.     {
  31.       previous=current;
  32.       current=current->next;
  33.     }
  34.   /* inserimento tra previous e current */
  35.   if (previous==NULL) /* inserimento in testa */
  36.     *l=new;
  37.   else                /* inserimento in mezzo od in coda */
  38.     previous->next=new;
  39.   new->next=current;  /* stessa istruzione per entrambi i casi */
  40. }
  41.  
  42. void print(list l)
  43. {
  44.   for(;l!=NULL;l=l->next)
  45.     printf("%d ",l->el);
  46.   printf("\n");
  47. }
  48.  
  49. /* merge: fonde le due liste *l1 e *l2 */
  50.  
  51. list merge(list *l1, list *l2)
  52. {
  53.   list res=NULL, p1=*l1, p2=*l2, p3=NULL;
  54.   
  55.   /* res = risultato della funzione
  56.      p1  = posizione corrente nella lista *l1
  57.      p2  = posizione corrente nella lista *l2
  58.      p3  = posizione corrente nella lista res
  59.   */
  60.   
  61.   /* *l1 e *l2 non devono contenere piu` nulla (per sicurezza) */
  62.  
  63.   *l1=NULL;
  64.   *l2=NULL;
  65.  
  66.   /* determinazione primo elemeno di res */
  67.  
  68.   if (p1==NULL) 
  69.     return p2;
  70.   else if (p2==NULL)
  71.     return p1;
  72.   else
  73.     if (p1->el<p2->el)
  74.       {
  75.     res=p1;
  76.     p1=p1->next;
  77.       }
  78.     else
  79.       {
  80.     res=p2;
  81.     p2=p2->next;
  82.       }
  83.   p3=res;
  84.   while (p1!=NULL && p2!=NULL)
  85.     {
  86.       if (p1->el<p2->el) 
  87.     {
  88.       p3->next=p1;
  89.       p3=p1;
  90.       p1=p1->next;
  91.     }
  92.       else
  93.     {
  94.       p3->next=p2;
  95.       p3=p2;
  96.       p2=p2->next;
  97.     }
  98.     }
  99.   if (p1==NULL) /* pezzo avanzato da *l2 */
  100.     p3->next=p2;
  101.   else          /* pezzo avanzato da *l1 */
  102.     p3->next=p1;
  103.   return res;
  104. }
  105.  
  106. int main(void)
  107. {
  108.   char fname[MAX];
  109.   list l1=NULL,l2=NULL,l3=NULL;
  110.   FILE *fd=NULL;
  111.   int i;
  112.  
  113.   printf("Enter file name: ");
  114.   scanf("%s",fname);
  115.   if (fd=fopen(fname,"r"))
  116.     {
  117.       while (fscanf(fd,"%d",&i)==1 && i!=-1)
  118.       insert(i,&l1);
  119.       printf("List l1 from file %s: ",fname);
  120.       print(l1);
  121.       while (fscanf(fd,"%d",&i)==1)
  122.       insert(i,&l2);
  123.       printf("List l2 from file %s: ",fname);
  124.       print(l2); 
  125.       printf("Merge: ");
  126.       l3=(merge(&l1,&l2));
  127.       print(l3);
  128.     }
  129.   else
  130.     printf("Error opening file %s\n",fname);
  131. }
  132.