Differenze tra le versioni di "Emulare una Lista Lineare"
(Creata pagina con "Nel linguaggio C una "''Lista Lineare'' " (''Linked List'') è una serie ordinata e concatenata di ''Strutture'' omogenee che occupano posizioni di memoria <U>non</u> necessar...") |
(Nessuna differenza)
|
Versione attuale delle 05:09, 27 lug 2024
Nel linguaggio C una "Lista Lineare " (Linked List) è una serie ordinata e concatenata di Strutture omogenee che occupano posizioni di memoria non necessariamente consecutive (come invece è per gli "array").
Ogni Struttura rappresenta un "elemento" dell'intera "Lista lineare concatenata ".
L'ultimo membro di ciascuna Struttura (elemento) della "Lista", è un Puntatore alla Struttura successiva. In questo senso la Lista concatenata è formata - appunto - da una concatenazione di Strutture, ove ciascuna Struttura fa riferimento ad un'altra Struttura.
Se si è giunti all'ultimo elemento (Struttura) della Lista Lineare, il suo Puntatore è nullo (non punta ad alcunché).
Nella sostanza le Linked List sono particolari Strutture, che si collegano fra loro come una sorta di catena e che servono a memorizzare in modo dinamico una grande quantità non predefinita di dati.
Questo genere di Strutture si usa, quando non si conosce a priori quanti dati dovranno essere memorizzati; ed allora viene occupata memoria poco per volta, quando serve.
Il primo dato viene "rintracciato" da un puntatore, che punta alla prima struttura. All'interno della prima struttura, oltre ai dati rilevanti, c'è - come ultimo suo membro - un Puntatore alla Struttura successiva, e così via a catena.
Emulare una 'Lista Lineare' mediante una Struttura di testa ed i Puntatori
In Gambas è possibile riprodurre il comportamento e il funzionamento di una "Lista Lineare" mediante una variabile del tipo della Struttura modello, posta alla testa della Lista concatenata, della quale ci si servirà in modo particolare del suo ultimo membro di tipo Puntatore, che punta all'area di memoria, opportunamente ed preventivamente riservata, che ospiterà la Struttura/elemento successiva, appartenente alla Lista Lineare.
Al riguardo va sottolineato che nel codice Gambas il membro della Struttura, che fa da Puntatore alla successiva nuova Struttura concatenata, non deve essere dichiarato con la parola-chiave "As Struct", bensì soltanto con "As".
Mostriamo un semplice esempio per creare e gestire una "Lista Lineare":
Public Struct ELEMENTO i As Integer prossima As ELEMENTO End Struct Public Sub Main() ' Dichiara le seguenti variabili del tipo Struttura "LISTA": ' - "p", puntatore alla testa della "Lista"; ' - "ap", puntatore ausiliario che permette la creazione degli elementi della "Lista" successivi al primo. Dim p, ap As ELEMENTO Dim n As Integer ' Crea una "Lista": la variabile "p" punta alla testa di tale "Lista":" p = New ELEMENTO ' Assegna un valore al primo membro (di tipo Integer) del primo elemento della "Lista":" p.i = 100 ' Assegna ad "ap" il valore di "p". ' Entrambe le variabili fanno riferimento al primo elemento della "Lista":" ap = p ' Esegue un ciclo per creare i nuovi "elementi" della "Lista" concatenata successivi al primo, assegnando anche un valore al primo membro dell'elemento appena creato:" For n = 2 To 10 ' Crea il nuovo "elemento" (ossia quello successivo) della "Lista" concatenato al precedente:" ap.prossima = New ELEMENTO ' Attualizza la variabile ausiliaria "ap", in modo da farla puntare al nuovo elemento (Struttura) della "Lista":" ap = ap.prossima ' Assegna un valore al primo membro (di tipo Integer) del nuovo elemento della "Lista":" ap.i = 100 * n Next ' Mostra quindi il risultato:" While Not IsNull(p) Print p.i p = p.prossima Wend End
Mostriamo un altro analogo semplice esempio:
' Impostiamo la "Struttura" modello, molto semplice, che rappresenterà il primo elemento della "Lista Lineare" concatenata, ed ove...
Public Struct STRUTTURA
i As Integer
' ...l'ultimo membro è un "Puntatore" che servirà a creare e connettere questa Struttura al successivo elemento della "Lista Lineare":
p As Pointer
End Struct
Public Sub Main()
Dim st As STRUTTURA
Dim i As Integer
' Crea il primo 'elemento-Struttura' della "Lista Lineare":
st = New STRUTTURA
' Va a creare i restanti elementi della "Lista Lineare":
Crea_Lista(st)
Visualizza_Dati(st)
Free(st.p)
End
Private Function Crea_Lista(nw As STRUTTURA) ' Passaggio della Struttura per "Indirizzo"
Dim sr As STRUTTURA
Dim b As Byte
' Immette il dato del primo elemento-Struttura della lista:
nw.i = 100
sr = nw
' Alloca un'area di memoria riservata per il secondo elemento della "Lista Lineare":
sr.p = Alloc(Object.SizeOf(STRUTTURA), 1)
' Crea una catena di altri 9 elementi/Strutture, in modo tale che la "Lista Lineare" sarà formata in totale da 10 elementi/Strutture":
For b = 2 To 10
sr = sr.p
' Immette i dati dei successivi elementi-Struttura della lista:
sr.i = 100 * b
' Alloca un'area di memoria riservata per il nuovo-successivo elemento della "Lista Lineare":
sr.p = Alloc(Object.SizeOf(STRUTTURA), 1)
Next
End
Private Procedure Visualizza_Dati(tt As STRUTTURA)
Print "\nValori inseriti nella 'Lista Lineare':\n"
While tt.p > 0
Print tt.i
tt = tt.p
Free(tt.p)
Wend
End
Altra modalità:
Public Struct LISTA sh As Short i As Integer succ As Pointer End Struct Public Sub Main() Dim lst, lst2 As New LISTA CreaStruttura(lst, 4) lst2 = lst While lst.succ > 0 Print lst.sh, lst.i lst = lst.succ Wend Dealloca(lst2) End Private Function CreaStruttura(sl As LISTA, c As Short) Dim n As Short For n = 1 To c sl.sh = n * c sl.i = n * c * 1000 If n <= c Then sl.succ = Alloc(Object.SizeOf(sl), 1) sl = sl.succ Endif sl.succ = 0 Next End Private Procedure Dealloca(sl As ListA) While sl.succ > 0 Free(sl.succ) sl = sl.succ Wend End
Emulare una Lista Lineare mediante i soli Puntatori
E' possibile emulare in Gambas il loro comportamento e funzionamento delle "Liste Lineari " (Linked List) anche mediante le sole variabili di tipo Puntatore.
Mostriamo un esempio commentato:
' Impostiamo la "Struttura" modello: ci servirà soltanto per definire la dimensione delle aree di memoria da allocare, ciascuna delle quali rappresenterà un elemento della "Lista Lineare" concatenata: Public Struct STRUTTURA b As Byte s As Short i As Integer ' L'ultimo membro della Struttura modello nelle "Linked List" è rappresentato da un "Puntatore", il quale serve - come si sa - a creare e connettere un elemento della "Lista Lineare" a quello successivo: p As Pointer End Struct Public Sub Main() Dim p, prm As Pointer Dim i As Integer Dim st As Stream ' Alloca un'area di memoria riservata per il primo elemento della "Lista Lineare": p = Alloc(Object.SizeOf(STRUTTURA)) prm = p For i = 1 To 4 st = Memory p For Write ' Scrive nell'area riservata, puntata dal Puntatore, il primo valore (in questo caso è di tipo Byte): Write #st, 11 * i As Byte ' Nel rispetto delle norme dell'allineamento effettua uno spostamento in avanti dell'indice nell'area riservata puntata dal Puntatore: Seek #st, 2 ' Scrive nell'area riservata, puntata dal Puntatore, il secondo valore (in questo caso è di tipo Short): Write #st, 1111 * i As Short ' Scrive nell'area riservata, puntata dal Puntatore, il terzo valore (in questo caso è di tipo Integer): Write #st, 111111 * i As Integer If i < 4 Then ' Alloca un'area di memoria riservata per il nuovo elemento della "Lista Lineare": p = Alloc(Object.SizeOf(STRUTTURA)) ' Se non si è giunti all'ultimo elemento dela Lista, scrive nell'area riservata, puntata dal Puntatore, il quarto valore (in questo caso è l'indirizzo di memoria della successiva area di memoria riservata per il nuovo elemento della Lista: Write #st, p As Pointer Endif st.Close Next VisualizzaLista(prm) End Private Procedure VisualizzaLista(po As Pointer) Dim b As Byte Dim pu As Pointer For b = 1 To 4 Print Byte@(po) Print Short@(po + 2) Print Int@(po + 4) pu = po po = Pointer@(po + 8) ' Libera la memoria precedentemente allocata: Free(pu) Next End