|
|
Supponiamo di dover implementare in linguaggio C, una lista circolare bidirezionale con sentinella.
Innanzi tutto va definita la struttura che avrà ogni cella. Questa struttura conterrà il valore dell’ i-esimo elemento della lista e gli indirizzi sia della cella successiva che precedente (realizzazione bidirezionale).
Vengono anche definiti alcuni elementi del tipo struttura cella e short, per facilitare la stesura del codice seguente. Iniziamo con l’ operatore crealista.
Con la funzione malloc viene allocata un’ area di memoria necessaria a contenere la nostra struttura di tipo Lista (o cella). L’ indirizzo di questa locazione di memoria viene assegnato ai puntatori next e prev della cella. Ci ritroveremo quindi in questa situazione:
Proseguendo analizziamo l’ operator listavuota che restituisce vero se la lista non contiene oggetti, falso altrimenti (quindi restituisce un valore di tipo booleano):
Vi sono poi gli operatori primolista e ultimolista che consentono l’accesso al primo/ultimo elemento di una lista.
Viene restituito un puntatore al primo elemento della lista. Se invece di next ci fosse indicato L->prev; verrebbe restituito un puntatore all’ ultimo elemento della lista (sfruttando la circolarità della lista). L’ operatore succlista restituisce il puntatore al successivo oggetto, ipotizzando naturalmente di essere già in qualche posizione della lista. Viene infatti passata alla funzione la posizione della lista nella quale ci troviamo:
La funzione succlista restituisce il puntatore che punta all’ elemento successivo. Vi è poi la funzione finelista che restituisce vero se si è oltrepassato un estremo della lista.
Sfruttando la circolarità della lista, se p è uguale a L (puntano entrambi alla sentinella) vuol dire che abbiamo oltrepassato l’ estremo della lista e siamo quindi tornati all’ inizio della lista. Vi sono poi le funzioni per leggere un elemento di una lista, e per scrivere in un elemento di una lista.
Ed ora le due funzioni leggermente più complesse. Iniziamo dalla funzione inslista, utilizzata per inserire un nuovo elemento.
Viene inserito un elemento a in posizione i-esima, spostando gli elementi successivi da posizione i a posizione i+1 ecc..
Passiamo alla funzione inslista l’ elemento da inserire e la posizione nella quale vogliamo inserire l’ elemento. Viene allocato lo spazio di memoria per la nuova cella. Viene assegnato l’ elemento a all’ elemento della cella. Facciamo puntare il puntatore prev della nuova cella alla cella precedente, che sappiamo essere puntata da p->prev. Analogamente il puntatore next della nuova cella viene fatto puntare all’ elemento successivo, ovvero quello puntato da p. Poi il next della cella a-1 viene fatto puntare alla nuova cella, cosi come il prev della cella ai viene fatto puntare alla nuova cella da noi creata. In fine analizziamo la funzione canclista, utilizzata per cancellare un elemento dalla lista:
Viene eliminato un elemento a in posizione i-esima spostando l’ elemento da pos i+1 a pos i.
Assegniamo al next della cella precedente a quella che vogliamo eliminare, l’ indirizzo della cella a+1 (che era puntata dal next della cella che vogliamo eliminare). Assegniamo al prev della cella antecedente a quella che vogliamo eliminare l’ indirizzo della cella a-1 (che era puntata dal prev della cella che vogliamo eliminare). Dopodiché viene spostata la posizione p dall’ elemento che vogliamo eliminare a quello successivo. In fine viene “eliminato q”.
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.