Differenze tra le versioni di "Emulare una Lista Lineare mediante i soli Puntatori"

Versione delle 18:24, 21 mag 2016

Nel linguaggio C una "Lista Lineare" (Linked List) è una serie ordinata e concatenata di Strutture omogenee che occupano posizioni di memoria non necessariamente consecutive.

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 riproducibili nel linguaggio Gambas. Possiamo, però, emulare il loro comportamento e funzionamento in Gambas 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