Esercizio-0-29-5-2017.cpp

#include<iostream>
using namespace std;

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

nodo* crea(int dim) {
  if(dim) {
    int x;
    cin >> x;
    return new nodo(x, crea(dim-1));
  }
 return 0;
}

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

void leggi(int dim, int*P) {
  if(dim) {
    cin>>*P;
    leggi(dim-1,P+1);
  }
}

void delete_curr_node(nodo* &T) {
  nodo* tmp = T->next;
  delete T;
  T = tmp;
}

// PRE=(L(T) è corretta, dimP>0, P ha dimP elementi definiti)
nodo* match(nodo* &T, int *P, int dimP) {
  if (T) {
    if (T->info == P[0]) {
      if (dimP == 1) {
        delete_curr_node(T);
        return new nodo(P[0]);
      } else {
        // PRE_RIC1=(L(T->next) è corretta, dimP-1>0, (P+1) ha dimP-1 elementi definiti)
        nodo* match_list = match(T->next, P+1, dimP-1);
        // POST_RIC1=(se c'è un match di (P+1) in L(T+1) allora match_list è la lista del match, e in T->next la lista restante,
        //           altrimenti match_list è NULL e T è invariata rispetto a PRE_RIC1)
        if (match_list) {
          delete_curr_node(T);
          return new nodo(P[0], match_list);
        } else { 
          return NULL;
        }
      }
    } else {
      // PRE_RIC2(L(T->next) è corretta, dimP>0, P ha dimP elementi definiti)
      return match(T->next, P, dimP);
      // POST_RIC2=(se c’è un match di P in L(T->next) allora la funzione restituisce col return la lista del match e in T la lista
      //       restante, altrimenti, restituisce NULL col return e T punta alla stessa lista cui puntava all’inizio))
    }
  } else {
    return NULL;
  }
}
// POST=(se c’è un match di P in L(T) allora la funzione restituisce col return la lista del match e in T la lista
//       restante, altrimenti, restituisce NULL col return e T punta alla stessa lista cui puntava all’inizio))

/**** CORRETTEZZA ****

I) Caso base (PRE<caso base>POST)
  - T è corretta ma è un nodo vuoto, l'unica cosa che faccio è ritornare NULL.
    Ciò significa che T punta alla stessa lista cui puntava all’inizio e che la lista del match è effettivamente nulla.
  - T è corretta e ha almeno un nodo. Se T->info==P[0] e dimP==1 allora la lista del match da restituire è
    composta dall'unico elemento matchato: P[0]. Inoltre eliminiamo direttamente tale elemento dalla lista T,
    poiché ho già verificato il matching non necessariamente contiguo completo.

II) Caso induttivo (PRE<caso non base>POST)
  - Se T && T->info!=P[0] restituisco l'invocazione di match con T->next al posto di T.
    Dato che T!=NULL e P e dimP sono invariati, allora anche T->next sarà una lista corretta.
  - Se T->info==P[0] e dimP!=1 allora devo prima verificare che esista il match anche nelle successive chiamate ricorsive,
    altrimenti rischio di modificare T potenzialmente per nulla, invalidando la POST.
    Quindi se match_list altero T e ritorno P[0]@match_list, ovvero la concatenazione dell'elemento matchato con i prossimi
    che daranno esito positivo nel match. Se !match_list, significa che nelle successive invocazioni non avrò possibilità
    di fare un match completo. Ritorno allora NULL senza modificare T.

*/

int main() {
  int dim, dimP, P[20];
  cin >> dim;
  nodo* L1 = crea(dim);
  cin >> dimP;
  leggi(dimP, P);

  cout << "start" << endl;

  nodo* L2 = match(L1, P, dimP);
  if (L2)
    stampa(L2);
  else
    cout<<"Lista del match vuota"<<endl;
    if(L1)
      stampa(L1);
    else
      cout<<"Lista restante vuota"<<endl;

  cout<<"end"<<endl;
}