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.99 / turno2 / parte4.c < prev   
C/C++ Source or Header  |  1999-06-16  |  3KB  |  159 lines
  1. /* Una possibile soluzione Esame di Laboratorio di Algoritmi 15 giugno 1999
  2.  * Turno 2 */
  3.  
  4.  
  5. /* Tipo di dato coda implementato in modo molto semplice ed inefficiente: liste,
  6. la testa della coda e' in fondo alla lista, quindi per cancellare devo scandire
  7. la coda. Questa implementazione era comunque accettabile e confrontabile come
  8. complessita' all'esercizio del turno 1 
  9.  
  10. Implementazioni alternative: puntatore al primo e ultimo elemento della coda,
  11. liste linkate.
  12.  
  13. Provare per esercizio */
  14.  
  15.  
  16. #include <stdio.h>
  17. #include <stdlib.h>
  18.  
  19. #define MAX 20
  20.  
  21. /* definizione dei tipi */
  22.  
  23. typedef  struct codael * coda;    /* una coda  e' un puntatore */
  24. typedef  struct codael{ int el; coda next; } cdl;
  25.  
  26. /* operazioni sulla coda */ 
  27.  
  28. coda   empty(void);    /* restituisce una coda vuota, cioe' restituisce NULL
  29. */
  30. coda in_coda(int,coda);   /* aggiunge in coda      */
  31. void  print(coda);      /* stampa la coda */
  32. coda makecodael(void);     /* alloca una nuova cella */
  33. void pos_neg(coda s, coda * s1, coda * s2);
  34.  
  35.  
  36.  
  37. /* main */  
  38.  
  39. main()
  40. {
  41.   
  42.     FILE * fp;
  43.     char nome[MAX];
  44.     int n;
  45.     coda s,s1=empty(),s2=empty();
  46.  
  47.   
  48.     /* creo coda vuota */
  49.  
  50.         s = empty();
  51.  
  52.     /* leggo il nome del file */
  53.  
  54.         printf("Fornisci il nome del file: ");
  55.     scanf("%s", nome);
  56.  
  57.     /* apro il file in lettura */
  58.  
  59.     fp = fopen(nome,"r");
  60.  
  61.  
  62.     /* carico la coda con i dati letti da file 
  63.      * (assumendo il file del formato corretto */
  64.  
  65.     while (fscanf(fp,"%d",&n) && n != 0)
  66.         s = in_coda(n,s);
  67.  
  68.     /* stampo la coda */
  69.  
  70.     print(s);
  71.     
  72.     
  73.     /* creo le nuove code */
  74.  
  75.     pos_neg(s,&s1,&s2);
  76.  
  77.     /* stampo le nuove code */
  78.  
  79.     print(s1);
  80.     print(s2);
  81.  
  82. }
  83.  
  84.  
  85. /* funzioni */
  86.  
  87.  
  88. coda empty()
  89.  { 
  90.   return NULL;  
  91.  }
  92.  
  93.  
  94.  
  95. coda in_coda(int el, coda s) 
  96.  { 
  97.    coda t;
  98.  
  99.    t=makecodael();      
  100.    t->el=el;
  101.    t->next=s;
  102.    return t; 
  103.  } 
  104.  
  105.  
  106.  
  107.  
  108.  
  109. coda makecodael(){ return (coda)malloc(sizeof(cdl)); }
  110.  
  111.  
  112. void print(coda s) 
  113. {  
  114.     printf("\nLa coda ha il seguente contenuto: ");
  115.     for(; s !=NULL ; s = s -> next)
  116.            printf(" %d",s->el);
  117.     printf("\n\n");
  118.  } 
  119.  
  120.  
  121.  
  122.  
  123. void pos_neg(coda s, coda * s1, coda * s2)
  124. {
  125.   coda aux1=empty(),aux2=empty();
  126.  
  127.   for (; s != empty(); s = s-> next)
  128.     { 
  129.       if (s->el > 0)          /* elemento positivo */
  130.          if (aux1 == empty())       /*primo elemento */
  131.                 {
  132.                    *s1 = s;
  133.                    aux1 = s;
  134.                 }
  135.          else                    /* elementi successivi */
  136.                 {
  137.                     aux1 -> next = s;
  138.                     aux1 = s;
  139.                 }
  140.                 
  141.       else                          /* elemento negativo */
  142.          if (aux2 == empty())       /*primo elemento */
  143.                 {
  144.                    *s2 = s;
  145.                    aux2 = s;
  146.                 }
  147.          else                    /* elementi successivi */
  148.                 {
  149.                     aux2 -> next = s;
  150.                     aux2 = s;
  151.                 }    
  152.     }
  153.  
  154.   if (aux1 != empty())
  155.       aux1->next = empty();
  156.   if (aux2 != empty())
  157.       aux2 -> next = empty();
  158. }
  159.