disiodj

Esami_2010_Febbraio

Jan 16th, 2016
263
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. VERIFICA-ARCO-USCENTE(A,u)
  2.     temp = A[u] //verifica prima che temp sia diverso da null
  3.     if(temp.next.next!=NULL) //errore su doppio next.
  4.         return FALSE;
  5.     return  TRUE;
  6.  
  7. */La complessità è Teta(1) poichè non si può impegare ne meno nè più dell'esecuzione richiesta./*
  8. ____________________________________________
  9. VERIFICA-ARCO-ENTRANTE(A,u)
  10.     for(i=0 to A.lenght-1){
  11.         cont = CERCA-NODO-USCENTE(A,i, u)
  12.     }
  13.     if(cont>2) 
  14.         return FALSE
  15.     return TRUE;
  16.    
  17. CERCA-NODO-USCENTE(A, x)
  18.     temp = A
  19.     while(temp!=NULL){
  20.         if(temp.info = x.info)
  21.             cont++
  22.         temp = temp.next
  23.     }
  24.     return cont
  25.  
  26. /*La complessità è O(n^2) nel caso peggiore, poichè sicuramente bisognerà scandire ogni nodo, in più il nodo potrebbe avere la lista di tutti i nodi da contare. Nel Caso migliore e Omega(n), poichè un nodo potrebbe non avere archi uscenti, e quindi la procedure di while potrebbe non esser richiamata/*
  27.  
  28. _________________________________________________
  29.  
  30. /*Se per ogni nodo, esiste un solo arco allora, true, altrimenti ritorna false.*/
  31. VERIFICA(A)
  32.     verificato = TRUE
  33.     for(i=0 to A.lenght-1 && trovato)
  34.         if(A[i].next.next==NULL && A[i].next!=NULL)
  35.             verificato = true;
  36.     return verificato;
  37.  
  38. La complessità è Teta(n)
  39. ______________________________________________________
Add Comment
Please, Sign In to add comment