Differenze tra le versioni di "Emulare una 'Lista Lineare' mediante una Struttura di testa ed i Puntatori"
Riga 74: | Riga 74: | ||
'''End''' | '''End''' | ||
+ | |||
+ | |||
+ | Altra modalità con una sola dichiarazione della Struttura: | ||
+ | Public Struct LISTA | ||
+ | st As String | ||
+ | i As Integer | ||
+ | p As Pointer | ||
+ | End Struct | ||
+ | |||
+ | |||
+ | '''Public''' Sub Main() | ||
+ | |||
+ | Dim b As Byte | ||
+ | Dim ma As New LISTA | ||
+ | Dim po, pn As Pointer | ||
+ | Dim st As Stream | ||
+ | |||
+ | With ma | ||
+ | .st = "Lista_0" | ||
+ | .i = 1111 | ||
+ | .p = Alloc(Object.SizeOf(ma), 1) | ||
+ | End With | ||
+ | |||
+ | po = ma.p | ||
+ | |||
+ | For b = 1 To 3 | ||
+ | pn = Alloc(Object.SizeOf(ma), 1) | ||
+ | st = Memory pn For Write | ||
+ | Seek #st, 8 | ||
+ | Write #st, 100 * b As Integer | ||
+ | st.Close | ||
+ | st = Memory po + 16 For Write | ||
+ | Write #st, pn As Pointer | ||
+ | st.Close | ||
+ | po = pn | ||
+ | Next | ||
+ | |||
+ | |||
+ | <FONT Color=gray>' ''Verifica i risultati:''</font> | ||
+ | Print ma.i | ||
+ | po = ma.p | ||
+ | For b = 1 To 3 | ||
+ | Print Int@(Pointer@(po + 16) + 8) | ||
+ | po = Pointer@(po + 16) | ||
+ | Next | ||
+ | |||
+ | <FONT Color=gray>' ''Libera la memoria precedentemente allocata:''</font> | ||
+ | Free(po - 16) | ||
+ | po = po - 16 | ||
+ | Free(po) | ||
+ | po = po - 16 | ||
+ | Free(po - 16) | ||
+ | Free(ma.p) | ||
+ | |||
+ | '''End''' | ||
+ | |||
Versione delle 15:38, 17 set 2017
Nel linguaggio C una "Lista Lineare" (Linked List) è una serie ordinata e concatenata di Strutture omogenee che occupano posizioni di memoria non necessariamente consecutive. [Nota 1]
L'ultimo membro di ciascuna Struttura, o 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. Dentro la prima struttura, oltre ai dati rilevanti, c'è - come ultimo suo membro - un Puntatore alla Struttura successiva, e così via a catena.
Va precisato che le "Liste Lineari" (Linked List) attualmente non sono esattamente riproducibili nel linguaggio Gambas. Possiamo, però, riprodurre in Gambas il loro comportamento e funzionamento 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.
Mostriamo un 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à con una sola dichiarazione della Struttura:
Public Struct LISTA st As String i As Integer p As Pointer End Struct Public Sub Main() Dim b As Byte Dim ma As New LISTA Dim po, pn As Pointer Dim st As Stream With ma .st = "Lista_0" .i = 1111 .p = Alloc(Object.SizeOf(ma), 1) End With po = ma.p For b = 1 To 3 pn = Alloc(Object.SizeOf(ma), 1) st = Memory pn For Write Seek #st, 8 Write #st, 100 * b As Integer st.Close st = Memory po + 16 For Write Write #st, pn As Pointer st.Close po = pn Next ' Verifica i risultati: Print ma.i po = ma.p For b = 1 To 3 Print Int@(Pointer@(po + 16) + 8) po = Pointer@(po + 16) Next ' Libera la memoria precedentemente allocata: Free(po - 16) po = po - 16 Free(po) po = po - 16 Free(po - 16) Free(ma.p) End
Note
[1] Vedi anche la pagina: Emulare una Lista Lineare mediante i soli Puntatori