Esame 31 Marzo 2013

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

/////////////////////////////////////////////////////////////////////////
///////////////////////////  FUNZIONI DATE  /////////////////////////////
/////////////////////////////////////////////////////////////////////////

struct nodo{

    int info1, info2;
    nodo* next;

    nodo(int a=0, int c=0, nodo* b=0){

        info1=a;
        info2=c;
        next=b;

    }

};

nodo* copia(nodo* X){

    if(X){

        return new nodo(X->info1, X->info2, copia(X->next));

    }

    return 0;

}

void crea(nodo* &L, int dim, ifstream & INP, int n){

    int x;

    if(n<dim){

        INP>>x;
        L=new nodo(x,n,0);
        crea(L->next, dim,INP,n+1);
    }

    else{

        L=0;

    }

}

void crea1(nodo*&L, int dim, ifstream & INP, int n){

    int x,y;

    if(n<dim){

        INP>>x>>y;
        cout<<"x="<<x<<" y="<<y<<endl;
        L=new nodo(x,y,0);
        crea1(L->next, dim,INP,n+1);

    }

    else{

        L=0;

    }
}

void stampa(nodo* x, ofstream & OUT){

    if(x){

        OUT<<'('<< x->info1<<','<<x->info2<<')';
        if(x->next)
        OUT<<"->";
        cout<< x->info1<<' '<<x->info2<<' ';
        stampa(x->next, OUT);

    }

    else{

        OUT<<endl;
        cout<<endl;

    }

}


/////////////////////////////////////////////////////////////////////////
/////////////////////////  FUNZIONI CREATE  /////////////////////////////
/////////////////////////////////////////////////////////////////////////


//Controlla a partire da T(x, indiceT) in che nodo di T inizia un match di P[indiceP] && Restituisce -1 se non vi è match
int startmatch(nodo* T, int*P, int indiceP, int indiceT){

    nodo *punt = T;

    for(int i=0; i<indiceT; i++){   //Vado all'indice di T che mi serve per iniziare il match

        if(punt->next){                 //Se esiste il successivo...
            punt = punt->next;              //...mi muovo
        }

        else{                           //Altrimentri...
            return -1;                      //...ritorno -1
        }

    }

    for(int i=0; true; ){           //Inizio il controllo

        if(punt->info1==P[indiceP]){    //Se il campo info1 è uguale a P[indiceP]
            return punt->info2;             //la ricerca si ferma
        }

        else{                           //Altrimenti

            if(punt->next){                 //se esiste un prossimo
                punt=punt->next;                //mi sposto sul prossimo
                i++;                            //e continuo la ricerca
            }

            else{                           //se non esiste
                return -1;                      //non ho trovato il match
            }

        }

    }

    return -1;

}

//Controlla quanto è lungo un match di P[indiceP...dimP-1] a partire da T(x, indiceT) && Restituisce 0 se non vi è match
int checklung(nodo* T, int*P, int indiceP, int indiceT, int dimP){

    if(indiceT == -1){

        return 0;

    }

    nodo *punt = T;

    for(int i=0; i<indiceT; i++){   //Vado all'indice di T che mi serve per iniziare il match

        if(punt->next){                 //Se esiste il successivo...
            punt = punt->next;              //...mi muovo
        }

        else{                           //Altrimentri...
            return 0;                      //...ritorno -1
        }

    }

    for(int i=0; true; ){     //Controllo quanto è lungo il match

        if(P[indiceP+i]==punt->info1){  //Se trovo un match tra il campo info1 di T e P[i]
            i++;                            //cerco il prossimo

            if(i==dimP){                        //se ho trovato tutto il match
                return i;                           //ritorno la lunghezza
            }

            if(punt->next){
                punt = punt->next;
            }

            else{
                return i;
            }

        }

        else{                           //Se non trovo match
            return i;                       //ritorno la lunghezza fin'ora trovata
        }

    }

    return 0;

}

//PRE=(T lista corretta, dimP>=0)
nodo* M1(nodo* T, int*P, int dimP){     //ITERATIVA

    nodo *lista;

    //Crea il primo nodo della lista
    lista->info1 = startmatch(T, P, 0, 0);
    lista->info2 = checklung(T, P, 0, lista->info1, dimP);


    int ultimoT = lista->info1 + lista->info2, ultimoP = lista->info2;
    nodo *pros = lista;

    while(true){

        int start = startmatch(T, P, ultimoP, ultimoT);
        int lung = checklung(T, P, ultimoP, start, dimP);

        if(start!= -1 && lung!= 0){

            pros->next = new nodo(start-ultimoT, lung, 0);
            pros = pros->next;
            ultimoT = start + lung;
            ultimoP += lung;

        }

        else{

            return lista;

        }


    }


    return lista;

}
//POST=(M1 restituisce col return la lista del match di P in T)















//PRE_TB=(T e X sono liste corrette, I campi info1 e info2 dei nodi di X (se ci sono nodi) sono tutti maggiori o uguali a 0, T=vT)
void TB(nodo*&T, nodo*X){
    return;
}
//POST_TB=( T=(vT-X), i nodi di (X di vT) sono deallocati).



//PRE_TC=(T e X sono liste corrette, i campi info1 e info2 dei nodi di X (se ci sono nodi) sono tutti maggiori o uguali a 0, T=vT)
nodo* TC(nodo*&T, nodo*X){
    return T;

}
//POST_TC=( T=(vT-X), e restituisce (X di vT) con il return)


main(){

    try{

        ifstream INP("input");
        ofstream OUT("output");

        if(!INP){

            throw(0);

        }

        if(!OUT){

            throw(1);

        }

        int P[100], dim, dimP, dimX;
        INP>>dim>>dimP>>dimX;

        nodo*L=0;
        crea(L,dim,INP,0);
        stampa(L, OUT);

        for(int i=0;i<dimP ; i++){

            INP>>P[i];

        }

        nodo *z = M1(L, P,dimP);

        if(!z){

            OUT<<"nessun match"<<endl;

        }

        else{

            stampa(z,OUT);

        }


        OUT<<endl;


        nodo* X=0;

        crea1(X,dimX,INP,0);

        nodo*L1=copia(L);

        TB(L1,X);               //da fare

        stampa(L1,OUT);

        cout<<endl;

        nodo* z1=TC(L,X);       //da fare
        stampa(L,OUT);

        cout<<endl;

        stampa(z1,OUT);

        cout<<endl;

    }

    catch(int x){

        switch(x){

            case 0: cout<<"problemi con input"<<endl; break;
            case 1: cout<<"problemi con output"<<endl; break;

        }

    }

}