Esami_2010_Febbraio

VERIFICA-ARCO-USCENTE(A,u)
    temp = A[u] //verifica prima che temp sia diverso da null
    if(temp.next.next!=NULL) //errore su doppio next.
        return FALSE;
    return  TRUE;

*/La complessità è Teta(1) poichè non si può impegare ne meno nè più dell'esecuzione richiesta./*
____________________________________________
VERIFICA-ARCO-ENTRANTE(A,u)
    for(i=0 to A.lenght-1){
        cont = CERCA-NODO-USCENTE(A,i, u)
    }
    if(cont>2)
        return FALSE
    return TRUE;

CERCA-NODO-USCENTE(A, x)
    temp = A
    while(temp!=NULL){
        if(temp.info = x.info)
            cont++
        temp = temp.next
    }
    return cont

/*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/*

_________________________________________________

/*Se per ogni nodo, esiste un solo arco allora, true, altrimenti ritorna false.*/
VERIFICA(A)
    verificato = TRUE
    for(i=0 to A.lenght-1 && trovato)
        if(A[i].next.next==NULL && A[i].next!=NULL)
            verificato = true;
    return verificato;

La complessità è Teta(n)
______________________________________________________