appello_3_testo_1-28.08.2017.cpp

#include<iostream>
using namespace std;

struct nodo{int info; nodo* next; nodo(int a =0, nodo* b=0){info=a; next=b;}};
struct doppioN{nodo*inizio,* fine; int lung; doppioN(nodo* a =0, nodo* b=0, int c=0){inizio=a; fine=b;lung=c;}};


nodo* build(int n)
{
  if(n>0)
    {
      int x;
      cin>>x;
      return new nodo(x,build(n-1));
      }
  else
    return 0;
}
void stampa_DN(doppioN A)
{
  cout<<"valore DN:"<<A.inizio->info<<' '<<A.fine->info<<" lung="<<A.lung<<endl;

}
void stampaL(nodo*L)
{
  if(L)
    {
      cout<<L->info<<' ';
      stampaL(L->next);
    }
  else
    cout<<endl;

}
nodo*clone(nodo*L)
{
  if(L)
    return new nodo(L->info,clone(L->next));
  else
    return 0;
}

void reset_iter_temp(nodo*& inizio, nodo*& fine, int& lung) {
  inizio = NULL;
  fine = NULL;
  lung = 0;
}

// PRE=(lista(L) corretta)
doppioN Fiter(nodo*L) {
  nodo* inizio = NULL;
  nodo* fine = NULL;
  int lung = 0;

  nodo* inizio_tmp = NULL;
  nodo* fine_tmp = NULL;
  int lung_tmp = 0;

/*
ORIGINALE:
R=(lista(L) corretta, non vuota. inizio_tmp contiene l'inizio della successione crescente corrente.
fine_tmp contiene la fine della successione crescente corrente. lung_p contiene la lunghezza della
successione corrente. Se due valori successivi (l->info e l->next->info)
non sono crescenti, allora la successione corrente è terminata.
Se fine_tmp e lung_tmp > lung, allora i valori di inizio, fine e lung vengono
sostituiti da quelli di inizio_tmp, fine_tmp e lung_tmp.
Se !inizio_tmp allora la successione è determinata da un singolo nodo e la lunghezza sarà quindi 1.
)

CORRETTO
R=(lista(L) corretta. inizio_tmp contiene l'inizio della successione crescente corrente.
fine_tmp contiene la fine della successione crescente corrente. inizio contiene l'inizio
della successione crescente più lunga da vL a L. fine contiene la fine della successione
crescente più lunga da vL a L. lung contiene la lunghezza della successione crescente più lunga.
)
*/
  while (L) { // R
    if (L->next && L->info <= L->next->info) {
      if (!inizio_tmp) {
        inizio_tmp = L;
        lung_tmp = 1;
      } else {
        lung_tmp++;
      }
    } else {
      if (!inizio_tmp) {
        inizio_tmp = L;
        lung_tmp = 1;
      } else {
        lung_tmp++;
      }

      fine_tmp = L;

      if (lung_tmp > lung) {
        inizio = inizio_tmp;
        fine = fine_tmp;
        lung = lung_tmp;
      }

      // resetto i valori temporanei
      reset_iter_temp(inizio_tmp, fine_tmp, lung_tmp);
    }

    L = L->next;
  }

  return doppioN(inizio, fine, lung);
}
// POST=(restituisce il valore doppioN che rappresenta la sotto lista crescente di lunghezza massima di L)

// PRE=(lista(L) corretta e non vuota)
doppioN Aux(nodo*L) {
/*
Aux restituisce quindi il prefisso di L crescente di lunghezza massima. Visto che L è non vuota, esiste sempre un tale
prefisso non vuoto.
*/
  if (!L->next || L->info > L->next->info) {
    return doppioN(L,L,1);
  }

  doppioN next = Aux(L->next);
  return doppioN(L, next.fine, next.lung + 1);
}
// POST=(restituisce il valore doppioN che rappresenta la sotto lista di L crescente di lunghezza massima che
// inizia col primo nodo di L)

/* Correttezza Aux
Caso base 1: L->next == NULL. In tal caso in L esiste solo un elemento nella successione (essendo L non vuota per via della PRE):
ha dunque senso che il valore di doppioN da ritornare sia composto da un unico nodo, che inizia e finisce in L,
e che per lunghezza ha 1.
Caso base 2 (L->next && L->info > L->next->info): la successione crescente è terminata con il nodo identificato da L, che è il nodo di partenza.
Ottengo quindi lo stesso risultato del caso base 1.

Caso induttivo: esiste L->next. Si può quindi fare un confronto tra L->info e L->next->info.
Caso L->info <= L->next->info: posso valutare quale sia il risultato di next = Aux(L->next).
Ritornerò quindi un valore doppioN che inizia in L (come da POST), finisce laddove finisce next (next.fine), ed ha come lunghezza
la lunghezza di next + il nodo iniziale, quindi next.lung + 1.
*/

// PRE=(lista(L) corretta, A di tipo doppioN individua una sotto lista di L, vL=L)
nodo* Giter(nodo*& L, doppioN A) {
  if (L == A.inizio) {
    L = A.fine->next;
  } else {
    nodo* x = L;
    while (x->next != A.inizio) {
      x = x->next;
    }
    x->next = A.fine->next;
  }

  A.fine->next = NULL;
  return A.inizio;
}
// POST=(Giter restituisce col return la sotto lista di vL individuata da A e il valore di L diventa vL senza la sotto
// lista restituita col return)

// PRE=(lista(L) corretta, A di tipo doppioN individua una sotto lista di L, vL=L)
nodo* Grec(nodo*& L, doppioN A) {
  if (L == A.inizio) {
    L = A.fine->next;
    A.fine->next = NULL;
    return A.inizio;
  }

  return Grec(L->next, A);
}
// POST=(Grec restituisce col return la sotto lista di vL individuata da A e il valore di L diventa vL senza la sotto
// lista restituita col return)

// PRE=(lista(L) corretta)
doppioN Frec(nodo*L) {
  if (!L) return doppioN();
  
  doppioN A = Aux(L);

  if (!L->next) return A;

  // PRE=(lista(L->next) corretta)
  doppioN B = Frec(L->next);
  // POST_RIC=(restituisce il valore doppioN che rappresenta la sotto lista crescente di lunghezza massima di L->next)

  if (A.lung < B.lung) {
    return B;
  } else {
    return A;
  }
}
// POST=(restituisce il valore doppioN che rappresenta la sotto lista crescente di lunghezza massima di L)

/* Correttezza Frec
Caso base 1: L==NULL. Se non ho una lista non ho nessuna successione. Quindi il valore doppioN avrà i campi inizio e fine a NULL,
e la lunghezza a 0. Per comodità uso il costruttore doppioN().
Case base 2: dato che lista(L) è una lista non vuota, posso assegnare ad una variabile doppioN A = Aux(L), che mi restituisce la sotto lista crescente 
di lunghezza massima di L. Semplicemente, se non ho un altro nella lista (!L->next), restituisco A.

Caso induttivo: so che (L && L->next). Assegno a B il valore di Frec(L->next). Posso farlo perché PRE_RIC e POST_RIC sono valide. 
A questo punto non mi resta che confrontare il campo lung di A e B, e ritornare il valore doppioN relativo alla successione di lunghezza più lunga
*/
main()
{
  int n;
  cin>>  n;
  cout<<"start"<<endl;
  nodo*L=build(n);
  stampaL(L);
  
  nodo*  L1=clone(L);
  doppioN A=Fiter(L);//da fare
  doppioN B=Frec(L1);//da fare
  stampa_DN(A);
  stampa_DN(B);
  nodo*K=Giter(L,A);//da fare
  nodo*K1=Grec(L1,B); //da fare
  stampaL(K);
  stampaL(L);
  stampaL(K1);
  stampaL(L1);
  cout<<"end"<<endl;
}