|
|
Nel linguaggi che non hanno i puntatori come tipi primitivi (per esempio il Fortran) è possibile simulare puntatori con cursori, cioè con variabili intere, il cui valore è interpretato come un indice di un vettore. Questo vettore simula la memoria disponibile per i puntatori , che deve essere gestita esplicitamente nella realizzazione. Per far questo si deve definire un vettore SPAZIO che contiene tutte le liste, ognuna individuata dal proprio cursore iniziale; e contiene tutte le celle libere, organizzate anch’ esse in una lista detta “listalibera”. Siano L ed M due liste di interi ed il vettore SPAZIO contenga in tutto 10 celle, ciascuna divisa nei campi “precedente”, “elemento” e “successivo”. Una possibile configurazione del vettore è la seguente:
In questo modo la posizione dell’ i-esimo elemento di L è uguale al valore del cursore alla cella che contiene l’ i-esimo elemento. In linguaggio C, potremmo implementare questa lista nel seguente modo:
Creiamo cosi un vettore di 100 elementi, ognuno dei quali avrà una struttura del tipo cella. Queste celle andranno prima di tutto inizializate, creiamo quindi una funzione inizializza:
Questa funzione fa in modo che ogni variabile next dell’ i-esima cella contenga il “cursore” alla cella successiva e che ogni variabile prev contenga il “cursore” alla cella precedente. Viene garantita anche la circolarità, in quanto la prima cella (spazio[0]) ha come variabile prev il “cursore” all’ ultima cella, mentre la variabile next dell’ ultima cella (spazio[99]) conterrà il “cursore” alla cella 0, ovvero al primo elemento del vettore (grazie al modulo %MAXL). La realizzazione degli operatori usando cursori è analoga a quella mediante puntatori, gli unici cambiamenti si hanno nelle procedure INSLISTA e CACLISTA. Per realizzare queste operazioni è comodo definire una procedura SPOSTA(p,q), che trasferisce la cella puntata da p, spostandola prima della cella puntata da q. Supponiamo per esempio di avere definito e inizializato un vettore SPAZIO come indicato sopra, e posizioniamo p e q su questo vettore in modo casuale.
Implementiamo ora in C, una funzione che trasferisce la cella puntata da p, spostandola prima della cella puntata da q.
Alla variabile t viene assegnato spazio[p].next e quindi il valore intero 3. Nella cella spazio[spazio[p].prev].next che è uguale a spazio[spazio[2].prev].next e quindi uguale a spazio[1].next viene assegnato il valore di spazio[p].next, ovvero il valore 3. Analogamente si prosegue con le altre righe della funzione fino ad ottenere una cosa di questo tipo:
Si noti che la procedura aggiorna il cursore p, in modo che punti alla cella che seguiva quella spostata (il next della riga due conteneva infatti il valore 3) e il cursore q in modo che punti alla cella spostata. Per capire meglio il funzionamento della funzione SPOSTA si osservi il seguente schema, che riassume l’ intera procedura di spostamento.
In questo schema si capisce bene cosa significa trasferire la cella puntata da p, spostandola prima della cella puntata da q. Infatti la cella prima di quella puntata da q (cella 4), non contiene più in Next il cursore alla cella 5, ma contiene il cursore alla cella 2. La cella 2 a sua volta contiene in next il cursore alla cella 5, e cosi via. La cella puntata da p viene quindi spostata prima della cella puntata da q. Dopodiché q viene fatto puntare alla cella spostata, e p viene fatto puntare alla cella successiva a quella spostata. La funzione SPOSTA viene utile quando si hanno le funzioni INSLISTA e CANCLISTA, in quanto viene spostata una cella dalla listalibera alla lista L o viceversa. Per esempio se voglio inserire un elemento nella posizione q, e una listalibera è nella posizione p, allora con la funzione SPOSTA(p,q), spostiamo la listalibera nella posizione q ed inseriamo qui l’ elemento desiderato.
Tutto quanto riportato in questa pagina è a puro scopo informativo personale. Se non ti trovi in accordo con quanto riportato nella pagina, vuoi fare delle precisazioni, vuoi fare delle aggiunte o hai delle proposte e dei consigli da dare, puoi farlo mandando un email. Ogni indicazione è fondamentale per la continua crescita del sito.