SHARE
TWEET

Untitled

a guest Jun 16th, 2019 68 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include<iostream>
  2. using namespace std;
  3.  
  4. struct nodo{int info; nodo* next; nodo(int a =0, nodo* b=0){info=a; next=b;}};
  5. struct nodoL{nodo* info; nodoL* next; nodoL(nodo* a =0, nodoL* b=0){info=a; next=b;}};
  6.  
  7. nodo* clone(nodo*L)
  8. {
  9.   if(L)
  10.     return new nodo(L->info,clone(L->next));
  11.   return 0;
  12. }
  13.  
  14. void stampaL(nodo*L)
  15. {
  16.   if(L)
  17.     {cout<<L->info<<' '; stampaL(L->next);}
  18.   else
  19.     cout<<endl;
  20.  
  21. }
  22.  
  23. void stampaLL(nodoL*LL,int n)
  24. {
  25.   if(LL)
  26.     {cout<<"fetta "<<n<<") "; stampaL(LL->info); stampaLL(LL->next,n+1);}
  27. }
  28.  
  29. nodo* faiL(int n) {
  30.   if(n>0)
  31.     return new nodo(n, faiL(n-1));
  32.   return 0;
  33.  
  34. }
  35.  
  36. // prototipi funzioni ricorsive
  37. int contaric(nodo*);
  38. nodo* tagliaric(nodo*&, int);
  39. nodoL* affettaric(nodo*&, int*, int);
  40.  
  41. //prototipi funzioni iterative
  42. nodo* concatiter(nodo*, nodo*);
  43. int contaiter(nodo*);
  44. nodo* tagliaiter(nodo*&, int);
  45. nodoL* affettaiter(nodo*&, int*, int);
  46.  
  47. main()
  48. {
  49.   cout<<"start"<<endl;
  50.   nodo* L= faiL(10);
  51.   nodo*L0=clone(L);
  52.   int n, A[10];
  53.   cin >> n;
  54.   for(int i=0; i<n; i++)
  55.     cin >> A[i];
  56.   nodoL*K=affettaric(L,A,n);
  57.   cout<<"Lric=";
  58.   stampaL(L);
  59.   cout<<"LLric:"<<endl;
  60.   stampaLL(K,1);
  61.   cout<<endl;
  62.   K=affettaiter(L0,A,n);
  63.   cout<<"Liter=";
  64.   stampaL(L0);
  65.   cout<<"LLiter:"<<endl;
  66.   stampaLL(K,1);
  67.   cout<<"end"<<endl;
  68.  
  69. }
  70.  
  71. //PARTE RICORSIVA
  72.  
  73. //PRE=(lista(L) corretta, dimA>=0 e A contiene dimA interi non negativi, vL=valore iniziale di L)
  74. nodoL* affettaric(nodo*& L, int* A, int dimA) {
  75.     if(!L) return 0;
  76.     if(!dimA) return 0;
  77.     if(contaric(L)>=A[0]) {
  78.     nodo* t=tagliaric(L, A[0]);
  79.     nodoL* LL=new nodoL(t);
  80.     //PRE_ric=(lista(L) corretta, dimA-1>=0 e A+1 contiene dimA-1 interi non negativi, vL=valore iniziale di L)
  81.     LL->next=affettaric(L, A+1, dimA-1);
  82.     //POST_ric=(restituisce una lista di nodi di tipo nodoL che puntano alle fette di vL secondo quanto descritto, L=vL-fette tolte
  83.     return LL;
  84.     } else return 0;
  85. }
  86. //POST=(restituisce una lista di nodi di tipo nodoL che puntano alle fette di vL secondo quanto descritto, L=vL-fette tolte)
  87.  
  88. /* DIMOSTRAZIONE DI CORRETTEZZA
  89. CASO BASE:
  90.     1. !L, cioe' la lista puntata da L e' vuota: in tal caso LL e' vuota e la funzione restituisce 0, L=vL-fette tolte=0 corretta
  91.     2. !dimA, cioe' non ci sono valori nell'array: in tal caso LL e' vuota e la funzione restituisce 0, L=vL-fette tolte=vL-0=vL corretta
  92.     3. contaric(L)<A[0]: in tal caso L contiene meno elementi del primo valore dell'array e lafunzione restituisce 0, L=vL-fette tolte=vL-0=vL corretta
  93. PASSO INDUTTIVO:
  94.     A questo punto abbiamo L!=0 (-> la lista puntata da L e' ben formata e non vuota) && dimA>0 (-> l'array A contiene degli elementi) &&
  95.     numero di nodi di lista(L)>=primo valore di A (-> si puo' staccare una porzione) [N.B. assumendo contaric valida]. La PRE_ric e':
  96.         1.lista(L) e' corretta;
  97.         2.dimA-1>=0;
  98.         3.A+1 contiene dimA-1 interi non negativi.
  99.     Tutte le pre condizioni sono valide, in quanto (lista(L) e' corretta) && (dimA-1>=0 -> dimA>=1) da caso base && (A+1 contiene dimA-1 interi non negativi) di conseguenza.
  100.     La PRE_ric e' quindi valida, e di conseguenza lo e' anche POST_ric
  101. */
  102.  
  103. //PRE=(lista(L) corretta)
  104. int contaric(nodo* L) {
  105.     if(!L) return 0;
  106.     else return 1+contaric(L->next);
  107. }
  108. //POST=(restituisce il numero di nodi presenti in L)
  109.  
  110. //PRE=(lista(L) corretta e con numero di nodi>=n (garantito da contaric), n>=0 e' il numero di nodi da tagliare, vL=lista(L))
  111. nodo* tagliaric(nodo*& L, int n) {
  112.     if(!L) return 0;
  113.     if(!n) return 0;
  114.     nodo* t=L;
  115.     L=L->next;
  116.     t->next=tagliaric(L, n-1);
  117.     return t;
  118. }
  119. //POST=(ritorna la porzione di vL tagliata, lista(L)=vL-porzione tagliata)
  120.  
  121.  
  122. //PARTE ITERATIVA
  123.  
  124. //PRE=(lista(L) corretta, dimA>=0 e A contiene dimA interi non negativi, vL=valore iniziale di L)
  125. nodoL* affettaiter(nodo*& L, int* A, int dimA) {
  126.     if(!L) return 0; //casi base
  127.     if(!dimA) return 0;
  128.     if(contaiter(L)<A[0]) return 0;
  129.     nodoL* LL=0;
  130.     //PRE_while=(lista(L) corretta e non vuota, dimA>0, esiste almeno una prima parte da staccare, v_dimA=dimA, vL=lista(l))
  131.     while(dimA && L) { //R=(lista(L) e' corretta e non vuota)&&(dimA>0)&&(LL contiene v_dimA-dimA nodi che sono le fette di L)&&(L=vL-n con n=v_dimA-dimA=fette staccate)
  132.         if(contaiter(L)>=A[0]) {
  133.             nodo* t=tagliaiter(L, A[0]);
  134.             if(!LL) LL=new nodoL(t, 0);
  135.             else {
  136.                 nodoL* X=LL; //mi ricordo dove sta
  137.                 while(LL->next) LL=LL->next;
  138.                 LL->next=new nodoL(t, 0);
  139.                 LL=X;
  140.             }
  141.             A++;
  142.             dimA--;
  143.         } else dimA=0; //condizione di uscita dal ciclo
  144.     }
  145.     //POST_while=(lista(LL) contiene le parti di lista staccate, L e' quello che avanza (come da esempio)
  146.     return LL;
  147. }
  148. //POST=(restituisce una lista di nodi di tipo nodoL che puntano alle fette di vL secondo quanto descritto, L=vL-fette tolte)
  149.  
  150. //PRE=(lista(L) corretta)
  151. int contaiter(nodo* L) {
  152.     if(!L) return 0;
  153.     int i=0;
  154.     while(L) {
  155.         i++;
  156.         L=L->next;
  157.     }
  158.     return i;
  159. }
  160. //POST=(restituisce il numero di nodi presenti in L)
  161.  
  162. //PRE=(lista(L) corretta e con numero di nodi>=n (garantito da contaiter), n>=0 e' il numero di nodi da tagliare, vL=lista(L))
  163. nodo* tagliaiter(nodo*& L, int n) {
  164.     if(!L) return 0;
  165.     if(!n) return 0;
  166.     nodo* p=0;
  167.     while(n && L) { //R=(n>0)&&(lista(L) non vuota)&&(v_n=n)&&(p contiene v_n-n nodi consecutivi di lista(L))
  168.         nodo* t=L;
  169.         L=L->next;
  170.         t->next=0;
  171.         p=concatiter(p, t);
  172.         n--;
  173.     }
  174.     return p;
  175. }
  176. //POST=(ritorna la porzione di vL tagliata, lista(L)=vL-porzione tagliata)
  177.  
  178. //PRE=(lista(p) ben formata, lista(t) ben formata, v_p=lista(p))
  179. nodo* concatiter(nodo* p, nodo* t) {
  180.     if(!p) return t;
  181.     if(!t) return p;
  182.     nodo* X=p;
  183.     while(p->next) p=p->next;
  184.     p->next=t;
  185.     return X;
  186. }
  187. //POST=(restituisce v_p@t con @=concatenazione)
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top