Esame 30 Giugno 2015

#include<iostream>
#include<fstream>
using namespace std;

struct nodo{int info; nodo* next; nodo(int a=0, nodo* b=0){info=a; next=b;}};
struct FIFO{nodo* primo, *fine; FIFO(nodo*a=0, nodo*b=0){primo=a; fine=b;}};

void stampa_L(nodo* x,ofstream& OUT)
{
  if(x)
  {OUT<<x->info<<' '; stampa_L(x->next,OUT);}
  else
   OUT<<endl;
}

nodo* costruisci(int dim, ifstream & IN)
{
  if(dim)
  {
    int x;
    IN>>x;
    return new nodo(x,costruisci(dim-1,IN));

  }
 else
  return 0;
}

//##############################

//PRE_metti_fondo=(a lista corretta, b nodo definito)
FIFO metti_fondo(FIFO a, nodo *b){

    if(!a.primo){
        a.fine = b;
        a.primo = a.fine;
        return a;
    }

    else{
        a.fine = b;
        return a;
    }
}
//POST_metti_fondo=(la lista a avra' come puntatore fine il nodo b)

//PRE_togli=(lista(C) è corretta e y è definito)
nodo* togli(nodo *C, int y){

    if(!C){         //Se la lista e' vuota
        return 0;       //non potranno esserci ripetizioni
    }

    nodo* punt = C;

    while(punt){

        if(punt->next && punt->next->info == y){
            nodo *puntnext = punt->next->next;  //Prossimo nodo
            nodo *daElim = punt->next;          //Non da eliminare
            punt->next = puntnext;              //Collego
            delete daElim;                      //Elimino
        }

        else{

            if(punt -> info == y){
                nodo *daElim = punt;            //Calcolo nodo da eliminare
                punt = punt->next;              //Sposto il puntatore corrente
                delete daElim;                  //Elimino il nodo
            }

            else{
                punt = punt->next;              //Se non ho da eliminare sposto solo
            }
        }
    }


    return C;

}

//POST_togli=(restituisce la lista che resta eliminando da C i nodi con campo info=y che vengono deallocati. Nessun nodo nuovo rispetto a C è allocato)

//PRE_no_rip=(lista(C) è corretta)
nodo* no_rip(nodo*C){

    if(!C){             //Se lista vuota non posso togliere nulla
        return 0;           //non posso togliere nulla
    }

    if(!C->next){       //Se il successivo non esiste
        return 0;           //non posso togliere nulla
    }

    C->next= togli(C->next, C->info);   //Calcolo la lista partendo dal prossimo nodo senza ripetizioni di valori uguali al campo info del nodo attuale
    C->next= no_rip(C->next);           //Dalla lista rimanente tolgo le ripetizioni del nodo successivo
    return C;
}

//POST_no_rip=( restituisce quello che resta di C mantenendo solo il primo nodo con un dato campo info ed eliminando i nodi successivi con lo stesso campo info.
//       I nodi tolti da C sono deallocati. Nessun nuovo nodo rispetto a C è allocato)


/*

    Dimostrazione induttiva della correttezza di no_rip.

    1. Caso base (lista vuota).
       Essendo L una lista vuota, da essa non si potra' togliere alcun nodo, quindi viene restituita la stessa lista vuota => vale POST

    2. Caso induttivo (lista non vuota)
       Essendo L una lista non vuota, viene prima invocata togli che permette di togliere, a partire dal successivo nodo della lista, tutti i nodi con campo info
       uguale al campo info del nodo attuale => C->next = vC dove vC contiene tutti i nodi di C tranne quelli con campo info uguale a C stesso => vale POST

*/


//PRE_elim=(T e C liste corrette)
void elim(nodo*&T, nodo*C){

    if(!T || !C){           //Se una delle due liste e' vuota
        return;                 //non posso fare nulla
    }

    nodo* punt = C;

    while(punt){
        togli(T, punt->info);   //Tolgo tutti i nodi con campo pari al campo info del puntatore
        punt = punt->next;      //Sposto il puntatore al prossimo nodo di C
    }

    return;

}
//POST_elim=(da T vengono tolti tutti i nodi con campo info uguali ai campi info dei nodi di C)

main()
{
  ifstream IN("input");
  ofstream OUT("output");
  if(IN && OUT)
  {
   int dimT, dimC;
   IN>>dimC;
   nodo*C=costruisci(dimC,IN);
   stampa_L(C,OUT);

   nodo*Y=no_rip(C);

   stampa_L(Y,OUT);
   IN>>dimT;
   nodo* T=costruisci(dimT,IN);
   stampa_L(T,OUT);

   elim(T,Y);

   stampa_L(T,OUT);
   IN.close(); OUT.close();
  }
  else
   cout<<"errore con i files";
 }