quarto appellò (filé)

//
//  quarto_appello_soluzione_ufficiale.cpp
//
//
//  Created by Elisabetta Piombin on 24/11/17.
//
//

#include <stdio.h>
#include<iostream>
using namespace std;

struct nodo{int num, info; nodo* next; nodo(int a=0,int b=0, nodo* c=0){num=a; info=b; next=c;}}; // nodo di lista
struct FIFO{nodo* primo, *ultimo; FIFO(nodo*a=0, nodo*b=0){primo=a; ultimo=b;}};
struct nodoF{FIFO info; nodoF*next; nodoF(FIFO a=FIFO(),nodoF*b=0){info=a; next=b;}}; //nodo di lista con FIFO

FIFO push_end(FIFO a, nodo*b)
{
    b->next=0;
    if(!a.primo)
    {a.primo=a.ultimo=b;}
    else
    {a.ultimo->next=b; a.ultimo=b;}
    return a;
}

FIFO push_begin(FIFO a, nodo* b)
{
    if(!a.primo)
    {a.primo=a.ultimo=b; b->next=0; return a;}
    else
    {
        b->next=a.primo;
        a.primo=b;
        return a;
    }
}

void stampa_L(nodo*L)
{
    if (L)
    {cout<<'['<<L->num<<','<<L->info<<']'<<' '; stampa_L(L->next);}
    else
        cout<<endl;

}
void stampa_F(nodoF* x)
{
    if(x)
    {
        stampa_L(x->info.primo);
        cout<<endl;
        stampa_F(x->next);
    }
}

nodo* costruisci(int n, int dim)
{
    if(dim)
    {int x; cin>>x; return new nodo(n,x,costruisci(n+1,dim-1));}
    return 0;
}
nodo* clone(nodo*a)
{
    if(a)
    {return new nodo(a->num, a->info, clone(a->next));}
    return 0;
}

/* COSEEEEEEE */
//ricorsiva

FIFO eliminaR (nodo*& L, int x) {
    if (!L) return FIFO();
    FIFO b = eliminaR (L->next, x);
    if (L->info == x) {
        nodo* a = L; //mi ricordo il nodo che ha campo info = x
        L = L->next; //lo sgancio
        b = push_begin (b, a); //metto nella nuova struttura fifo il nodo che ho sganciato. si usa push_begin perché stiamo tornando indietro nella ricorsione, e così mi mette tutti i nodi nella fifo nell'ordine originale
    }
    return b;
}

nodoF* insR (nodoF* Q, FIFO x) {
    if (!Q || x.primo->info < Q->info.primo->info)
        return new nodoF (x, Q);
    //se non entro nella if significa che la lista non è vuota o non devo mettere il nodo al primo posto
    Q->next = insR (Q->next, x);
    return Q;
}

nodoF* tieni_primo_ric(nodo*& L) {
    if (!L) return 0;
    FIFO b = eliminaR (L->next, L->info); //invoco su L->next perché in ogni caso il primo nodo  si tiene
    nodoF* z = tieni_primo_ric(L->next);
    if (b.primo)
        z= insR (z, b);
    return z;
}

//iterativa

nodoF* insI (nodoF* Q, FIFO x) {
    if (!Q || x.primo->info < Q->info.primo->info)
        return new nodoF (x, Q);
    //ma se non devo inserirlo al primo posto: il primo nodo c'è e ha campo info < di quello che devo inserire. è utile avere il puntatore che punta al nodo prima rispetto a dove devo inserire il nodo
    nodoF* z = Q; //quindi uso z
    while (z->next && z->next->info.primo->info < x.primo->info)
        z = z->next;
    z->next = new nodoF (x, z->next);
    return Q;
}

nodoF* tieni_primo_iter (nodo*& L) {
    nodoF* x=0;
    nodo* z = L;
    while (z) {
        FIFO a= eliminaR (z->next, z->info);
        x=insI(x,a);
        z=z->next;
    }
    return x;
}


main()
{
    int dim;
    cout<<"start"<<endl;
    cin>>dim;
    nodo*C=costruisci(0,dim);
    nodo* D=clone(C);
    cout<<"Lista costruita"<<endl;
    stampa_L(C);
    nodoF* a =tieni_primo_ric(C); //da fare
    cout<<"soluzione ricorsiva"<<endl<<"nodi tolti:"<<endl;

    stampa_F(a);
    cout<<"lista rimanente:"<<endl;
    stampa_L(C);
    nodoF* b=tieni_primo_iter(D); //da fare
    cout<<"soluzione iterativa"<<endl<<"nodi tolti:"<<endl;
    stampa_F(b);
    cout<<"lista rimanente:"<<endl;
    stampa_L(D);
    cout<<"end";
}