Come abbiamo visto nella sezione precedente, vettori e record sono caratterizzati da operazioni che permettono un accesso diretto alle singole componenti ma non consentono di modificare la dimensione della struttura. In questa sezione e nelle successive definiamo invece strutture nelle quali `e possibile modificare le dimensioni aggiungendo o togliendo elementi, ma nelle quali l’accesso alle componenti non sempre `e il risultato di una sola operazione e pu`o richiedere, durante l’implementazione, l’esecuzione di numero di passi proporzionale alla dimensione della struttura stessa.
Una struttura dati tipica nella quale si possono agevolmente introdurre o togliere elementi `e quella di lista. Dato un insieme di valori U , chiamiamo lista una sequenza finita L di elementi di U . In particolare L pu`o essere la lista vuota, che non contiene alcun elemento, e in questo caso denotiamo L con il simbolo Λ; altrimenti rappresentiamo L nella forma
dove n ≥ 1 e ai ∈ U per ogni i = 1, 2, . . . , n. In questo caso diremo anche che ai `e l’i-esimo elemento di L.
Le liste sono inoltre dotate delle operazioniIS EMPTY,ELEMENTO,INSERISCIeTOGLIche de-finiamo nel seguito. Queste consentono di verificare se una lista `e vuota, di determinare i suoi elementi oppure di modificarla introducento un nuovo oggetto o togliendone uno in una posizione qualsiasi. `E importante sottolineare che le operazioni di inserimento e cancellazione dipendono dalla posizione degli elementi nella lista e non dal loro valore.
Per ogni lista L, per ogni k ∈ IN e ogni u ∈ U , le operazioni citate sono cos`ı definite: IS EMPTY(L) = ( 1 se L = Λ, 0 altrimenti; ELEMENTO(L, k) = ( ak se L = ha1, a2, . . . , ani e 1 ≤ k ≤ n, ⊥ altrimenti; INSERISCI(L, k, u) = hui se L = Λ e k = 1, ha1, . . . , ak−1, u, ak, . . . , ani se L = ha1, a2, . . . , ani e 1 ≤ k ≤ n + 1, ⊥ altrimenti; TOGLI(L, k) = ( ha1, . . . , ak−1, ak+1, . . . , ani se L = ha1, a2, . . . , ani e 1 ≤ k ≤ n, ⊥ altrimenti;
Mediante la composizione di queste operazioni possiamo calcolare altre funzioni che permettono di manipolare gli elementi di una lista; tra queste ricordiamo quelle che determinano o modificano il primo elemento di una lista:
TESTA(L) = ( a1 se L = ha1, a2, . . . , ani, ⊥ se L = Λ; INSERISCI IN TESTA(L, u) = ( hu, a1, a2, . . . , ani se L = ha1, a2, . . . , ani, hui se L = Λ; TOGLI IN TESTA(L) = ( ha2, . . . , ani se L = ha1, a2, . . . , ani, ⊥ se L = Λ;
infatti `e evidente cheTESTA(L)=ELEMENTO(L, 1),INSERISCI IN TESTA(L, u)=INSERISCI(L, 1, u),
TOGLI IN TESTA(L)=TOGLI(L, 1). Usando lo stesso criterio possiamo definire l’operazione che calcola la lunghezza di una stringa e quella per sostituire il suo elemento k-esimo.
LUNGHEZZA(L) = (
0 se L = Λ
1 + LUNGHEZZA(TOGLI IN TESTA(L)) altrimenti CAMBIA(L, k, u) = TOGLI(INSERISCI(L, k, u), k + 1)
Analogamente si possono definire altre operazioni di uso frequente. Elenchiamo nel seguito alcune di queste tralasciando la definizione formale e riportando solo il significato intuitivo:
APPARTIENE(L, u) = (
1 se u compare in L, 0 altrimenti
CODA(ha1, . . . , ami) = am
INSERISCI IN CODA(ha1, . . . , ami, x) = ha1, . . . , am, xi
TOGLI IN CODA(ha1, . . . , ami) = ha1, . . . , am−1i
Un calcolo eseguito spesso da algoritmi che manipolano una lista consiste nello scorrere i suoi ele-menti dal primo all’ultimo, compiendo certe operazioni su ciascuno di questi. Un procedimento di questo tipo pu`o essere eseguito applicando opportunamente le operazioni definite sulle liste. Per brevit`a , e con un certo abuso di notazione, nel seguito indicheremo con l’istruzione
forb ∈ LdoOp(b)
la procedura che esegue l’operazione predefinita Op su ciascun elemento b della lista L nell’ordine in cui tali oggetti compaiono in L.
Per esempio, per determinare quante volte un elemento a compare in una lista L, possiamo eseguire la seguente procedura: begin n:=0 forb ∈ Ldo ifb = athenn:=n+1 returnn end
Tale procedura pu`o essere considerata come l’implementazione della seguente operazione definita utiliz-zando le operazioni fondamentali:
NUMERO(a, L) = 0 se L = Λ
1 + NUMERO(a, TOGLI IN TESTA(L)) se L 6= Λ e a = TESTA(L)) NUMERO(a, TOGLI IN TESTA(L)) se L 6= Λ e a 6= TESTA(L))
4.2.1 Implementazioni
In questa sezione consideriamo tre possibili implementazioni della struttura dati appena definita. La pi`u semplice consiste nel rappresentare una lista L = ha1, a2, . . . , ani mediante una tabella T di dimensione m > n che mantiene nelle prime n componenti i valori a1, a2, . . . , annel loro ordine. In questo modo il calcolo del k-esimo elemento di L (ovvero l’esecuzione dell’operazioneELEMENTO(L, k)) `e abbastanza semplice poich´e `e sufficiente eseguire una proiezione sulla k-esima componente di T ; possiamo assumere che nella maggior parte dei casi questo richieda un tempo O(1) secondo il criterio uniforme. Viceversa l’inserimento o la cancellazione di un elemento in posizione k-esima richiede lo spostamento di tutti gli elementi successivi. Inoltre, prima di inserire un elemento, bisogna assicurarsi che la dimensione della lista non diventi superiore a quella della tabella, nel qual caso occorre incrementare opportunamente la dimensione di quest’ultima ed eventualmente riposizionarla in un’altra area di memoria. L’esecuzione di queste operazioni pu`o quindi essere costosa in termini di tempo e spazio e questo rende poco adatta tale implementazione quando occorre eseguire di frequente l’inserimento o la cancellazione di elementi.
Una seconda implementazione, che per molte applicazioni appare pi`u naturale della precedente, `e basata sull’uso dei puntatori ed `e chiamata lista concatenata. In questo caso una lista L = ha1, a2, . . . , ani viene rappresentata mediante n record R1, R2, . . . , Rn, uno per ogni posizione, formati da due campi ciascuno che chiameremo el e punt. Ogni Ri contiene nel campo el il valore ai e nel campo punt un puntatore al record successivo. Inoltre un puntatore particolare (P ) indica il primo record della lista.
P c - a1 R1 c - · · · - an Rn nil
Questa rappresentazione permette inoltre di implementare facilmente (in pseudocodice e quindi su macchina RAM) le operazioni definite sopra. A titolo d’esempio, riportiamo alcuni casi particolari.
IS EMPTY(P)
ifP = nilthen return1
else return0
INSERISCI IN TESTA(P , a)
Crea un puntatore X a una variabile di tipo record ∗X · el := a ∗X · punt := P P := X a c @ @ @ R P c 6 a1 c - · · · -am nil X c - a c @ @ @ R P c - a1 c - · · · -am nil X c - a c P c - a1 c - · · · -am nil
Figura 4.1: Passi esecutivi della proceduraINSERISCI IN TESTA.
APPARTIENE(P, a)
if P = nil then return0
else begin
R = ∗P
while R · el 6= a ∧ R · punt 6= nil doR := ∗(R · punt)
if R · el = athen return1
else return0
end
Nota la differenza tra le implementazioni diIS EMPTYeAPPARTIENEe quella diINSERISCI -IN TESTA: nei primi due casi la procedura restituisce un valore, nel terzo invece modifica direttamente la lista ricevuta in input. In molti casi quest’ultimo tipo di implementazione `e quella effettivamente richiesta nella manipolazione di una struttura dati.
Per quanto riguarda la complessit`a di queste procedure, se supponiamo che l’uguaglianza tra ele-menti richieda tempo O(1), possiamo facilmente osservare che il tempo di calcolo perIS EMPTY e
INSERISCI IN TESTA`e O(1), mentreAPPARTIENErichiede nel caso peggiore O(n) passi, dove n `e il numero di elementi nella lista. Un aspetto molto interessante `e che la complessit`a in spazio risulta essere Θ(n), cosa che permette una efficiente gestione dinamica delle liste.
La lista concatenata pu`o essere “percorsa” in una sola direzione; questa implementazione si rivela inadeguata quando sia utile percorrere la lista dalla coda alla testa. Una rappresentazione della lista sim-metrica rispetto al verso di percorrenza `e la cosiddetta lista bidirezionale. Essa `e ottenuta da una sequenza di records di 3 campi. In ogni record il primo campo (prec) contiene un puntatore al record precedente, il terzo campo (succ) contiene un puntatore al record successivo mentre l’elemento da memorizzare `e contenuto nel secondo (el), come evidenziato nella figura 4.2.
c -Testa L nil a1 c -c a2 c - · · · -c am nil c Coda L
Figura 4.2: Lista bidirezionale.
Un’altra possibile implementazione di una lista pu`o essere ottenuta mediante due tabelle dette Nome e Succ. Se I `e un indice della tabella, Nome[I] `e un elemento della lista L mentre Succ[I] `e l’indice dell’elemento che segue Nome[I] in L. Un indice I 6= 0 identifica la lista se Succ[I] `e definito ma
Nome[I] non lo `e , mentre conveniamo che il “fine lista” sia identificato da 0. Per esempio, la tabella
seguente memorizza in posizione 3 la lista hF, O, C, Ai.
Nome Succ 1 C 4 2 O 1 3 5 4 A 0 5 F 2
Va osservato che l’ordine di inserimento degli elementi nella lista non necessariamente coincide con l’ordine di inserimento nella tabella.
Questa rappresentazione `e flessibile e interessante, permettendo di memorizzare pi`u liste in celle di memoria consecutive. Per esempio, la tabella successiva memorizza in posizione 3 la lista hB, A, S, S, Ai, in posizione 8 la lista hA, L, T, Ai e in posizione 10 la lista hD, U, Ei.
Nome Succ 8 7 1 S 11 9 L 2 2 T 12 10 14 3 4 11 S 6 4 B 5 12 A 0 5 A 1 13 E 0 6 A 0 14 D 15 7 A 9 15 U 13
Anche in questa rappresentazione l’implementazione delle varie operazioni `e lineare. Vediamo un esempio.
APPARTIENE(I, a) S:= Succ[I]
if S = 0then return0
else begin
while Nome[S] 6= a ∧ Succ[S] 6= 0do S:=Succ[S]
if Nome[S] = athen return1
else return0
end
Le liste bidirezionali ammettono una rappresentazione analoga, a patto di aggiungere una terza tabella
Prec, dove Prec[I] `e l’indice dell’elemento che precede Nome[I] nella lista considerata.