Appunti di fondamenti di informatica e programmazione II

Algoritmo di visita di un labirinto

/* SE IL NODO NON E' GIA' STATO VISITATO, VISITALO */

if(Labirinto[i_estratto].visitato==0 )

{ //Visita nodo

printf("[%c] ", Labirinto[i_estratto].info.nome);

Labirinto[i_estratto].visitato=1;

n_cnt++; /* Ad ogni estrazione, conto */

/* SE SI E' ARRIVATI A VISITARE L'USCITA Q, Esci dalla VISITA! */

if(Labirinto[i_estratto].info.nome=='Q')

{/* SIAMO ARRIVATI A Q, sarebbe inutile continuare perche' era

return; lo SCOPO RICHIESTO */

/* INSERISCI ADIACENZE NELLO STACK per n nodi adiacenti al nodo estratto */

n_adiacenze = Labirinto[i_estratto].n_nodi_adiac; //n adiacenze per quel nodo

i

{

for(i=0;

Push(Stack, Labirinto[i_estratto].Adiacenze[i], &i_testa);

}

}

/* Push: Inserire in testa dell'array, appunto, come lo stack. */

Push(short Vet_Stack[], Elemento, *Testa)

{ //Se non ho superato il massimo dello stack

if(*Testa

{ /* *Testa=*Testa+1 -> Vet_Stack=Elemento

La mia testa puntera' SEMPRE */

all'ULTIMO ELEMENTO inserito, quindi incrementando
mettero' l'elemento in testa o PUSHO */Vet_Stack[++(*Testa)]=Elemento;}
{puts("\n*------- NON INSERISCO NULLA, STACK PIENO! --------*\n");exit(1);}
else}
/* Pop: Eliminare dalla testa dell'array. */
Pop(short Vet_Stack[], *i_estratto, *Testa)
void short short{
    //Se c'e' qualcosa
    if(*Testa>-1){
        *i_estratto = Vet_Stack[*Testa];
        /* Decrementando l'indice dell'ultimo elemento inserito, appunto, non verra'piu' "visto" l'ultimo elemento inserito, nascondendolo*/
        (*Testa)--;
        //altrimenti "Stack vuoto" viene gestito nel main
        Giuseppe Accardo - Programmazione II 134}
    {puts("---- ERRORE Stack vuoto!! -----");exit(1);}
    else}
Disegna_labirinto()
void{
    puts("\tK---&---A---B---C ");
    puts("\t| \\ / | ");
    puts("\t| \\ / | ");
    puts("\tJ D E ");
    puts("\t| / \\ | ");
    puts("\t| / \\ | ");
    puts("\tY--- X G");

---F");puts("\t| | | | ");puts("\t| | | | ");puts("\tW Z H I");puts("\t| | | | ");puts("\t| | | | ");puts("\tV--- U L ---M");puts("\t| \\ / | ");puts("\tT---S--R-N--O---P");puts("\t \\ / ");puts("\t \\ / ");puts("\t \\ / ");puts("\t Q ");}
/* Assegna Adiacenze: Potremo usare sia una matrice di adiacenze che una lista di adiacenze,ma per il problema interessato e per rapidita', scegliamo di implementare una strutturareticolare molto semplice (e' come se avessimo un albero generico)*/
assegna_adiacenze(VERTICE_LABIRINTO Labirinto[], *inizio_lab)
void short{
    /* Da dove comincio a visitare? Da A individuato dall'indice 0 */
    *inizio_lab = 0;
    Labirinto[0].info.nome='A';
    Labirinto[0].n_nodi_adiac=2;
    Labirinto[0].Adiacenze[0] = 26; //Il vertice A è collegato al vertice &Labirinto[0].Adiacenze[1] = 1; //Il vertice A è

collegato al vertice BLabirinto[0].visitato = 0; //1 - nodo visitato; 0 - nodo non visitato

Labirinto[1].info.nome='B';

Labirinto[1].n_nodi_adiac=3;

Labirinto[1].Adiacenze[0] = 0; //Il vertice B è collegato al vertice A

Labirinto[1].Adiacenze[1] = 2; //Il vertice B è collegato al vertice C

Labirinto[1].Adiacenze[2] = 3; //Il vertice B è collegato al vertice D

Labirinto[1].visitato = 0; //1 - nodo visitato; 0 - nodo non visitato

Labirinto[2].info.nome='C';

Labirinto[2].n_nodi_adiac=2;

Labirinto[2].Adiacenze[0] = 1; //Il vertice C è collegato al vertice B

Labirinto[2].Adiacenze[1] = 4; //Il vertice C è collegato al vertice E

Labirinto[2].visitato = 0; //1 - nodo visitato; 0 - nodo non visitato

Labirinto[3].info.nome='D';

Labirinto[3].n_nodi_adiac=4;

Labirinto[3].Adiacenze[0] = 26; //Il vertice D è collegato al vertice #

Labirinto[3].Adiacenze[1] = 1; //Il vertice D è collegato al vertice

visitatoLabirinto[6].info.nome='G';

Labirinto[6].n_nodi_adiac=3;

Labirinto[6].Adiacenze[0] = 3; //Il vertice G è collegato al vertice D

Labirinto[6].Adiacenze[1] = 5; //Il vertice G è collegato al vertice F

Labirinto[6].Adiacenze[2] = 7; //Il vertice G è collegato al vertice H

Labirinto[6].visitato = 0; //1 - nodo visitato; 0 - nodo non visitato

Labirinto[7].info.nome='H';

Labirinto[7].n_nodi_adiac=3;

Labirinto[7].Adiacenze[0] = 6; //Il vertice H è collegato al vertice G

Labirinto[7].Adiacenze[1] = 25; //Il vertice H è collegato al vertice Z

Labirinto[7].Adiacenze[2] = 11; //Il vertice H è collegato al vertice L

Labirinto[7].visitato = 0; //1 - nodo visitato; 0 - nodo non visitato

Labirinto[8].info.nome='I';

Labirinto[8].n_nodi_adiac=2;

Labirinto[8].Adiacenze[0] = 5; //Il vertice I è collegato al vertice F

Labirinto[8].Adiacenze[1] = 12; //Il vertice I è collegato al vertice L

L'è collegato al vertice N

Labirinto[11].visitato = 0; //1 - nodo visitato; 0 - nodo non visitato

Labirinto[12].info.nome='M';

Labirinto[12].n_nodi_adiac=3;

Labirinto[12].Adiacenze[0] = 8; //Il vertice M è collegato al vertice I

Labirinto[12].Adiacenze[1] = 11; //Il vertice M è collegato al vertice L

Labirinto[12].Adiacenze[2] = 15; //Il vertice M è collegato al vertice P

Labirinto[12].visitato = 0; //1 - nodo visitato; 0 - nodo non visitato

Labirinto[13].info.nome='N';

Labirinto[13].n_nodi_adiac=3;

Labirinto[13].Adiacenze[0] = 11; //Il vertice N è collegato al vertice L

Labirinto[13].Adiacenze[1] = 14; //Il vertice L è collegato al vertice O

Labirinto[13].Adiacenze[2] = 17; //Il vertice L è collegato al vertice R

Labirinto[13].visitato = 0; //1 - nodo visitato; 0 - nodo non visitato

Labirinto[14].info.nome='O';

Labirinto[14].n_nodi_adiac=3;

Labirinto[14].Adiacenze[0] = 13; //Il vertice O

è collegato al vertice NLabirinto[14].

Adiacenze[1] = 15; //Il vertice O è collegato al vertice PLabirinto[14].

Adiacenze[2] = 16; //Il vertice O è collegato al vertice Q (uscita)Labirinto[14].

visitato = 0; //1 - nodo visitato; 0 - nodo non visitatoLabirinto[15].info.nome='P';

Labirinto[15].n_nodi_adiac=2;Labirinto[15].Adiacenze[0] = 12; //Il vertice P è collegato al vertice MLabirinto[15].

Adiacenze[1] = 14; //Il vertice P è collegato al vertice OLabirinto[15].

visitato = 0; //1 - nodo visitato; 0 - nodo non visitatoLabirinto[16].info.nome='Q';

Labirinto[16].n_nodi_adiac=2;Labirinto[16].Adiacenze[0] = 14; //Il vertice Q è collegato al vertice OLabirinto[16].

Adiacenze[1] = 18; //Il vertice Q è collegato al vertice SLabirinto[16].

visitato = 0; //1 - nodo visitato; 0 - nodo non visitatoLabirinto[17].info.nome='R';

Labirinto[17].n_nodi_adiac=3;Labirinto[17].Adiacenze[0] = 13; //Il

visitatoLabirinto[20].info.nome='U';

Labirinto[20].n_nodi_adiac=3;

Labirinto[20].Adiacenze[0] = 25; //Il vertice U è collegato al vertice Z

Labirinto[20].Adiacenze[1] = 21; //Il vertice U è collegato al vertice V

Labirinto[20].Adiacenze[2] = 17; //Il vertice U è collegato al vertice R

Labirinto[20].visitato = 0; //1 - nodo visitato; 0 - nodo non visitato

Labirinto[21].info.nome='V';

Giuseppe Accardo - Programmazione II 136

Labirinto[21].n_nodi_adiac=3;

Labirinto[21].Adiacenze[0] = 22; //Il vertice V è collegato al vertice W

Labirinto[21].Adiacenze[1] = 20; //Il vertice V è collegato al vertice U

Labirinto[21].Adiacenze[2] = 19; //Il vertice V è collegato al vertice T