Differenze tra le versioni di "Emulare una 'Lista Lineare' mediante una Struttura di testa ed i Puntatori"

Da Gambas-it.org - Wikipedia.
(Creata pagina con "Nel linguaggio C una "''Lista Lineare''" (''Linked List'') è una serie ordinata e concatenata di ''Strutture'' omogenee che occupano posizioni di memoria non necessariamente...")
 
 
(21 versioni intermedie di uno stesso utente non sono mostrate)
Riga 1: Riga 1:
−
Nel linguaggio C una "''Lista Lineare''" (''Linked List'') è una serie ordinata e concatenata di ''Strutture'' omogenee che occupano posizioni di memoria non necessariamente consecutive.
+
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''.
  
−
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é).
+
Mostriamo un semplice esempio:
−
 
 
−
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 <SPAN Style="text-decoration:underline">non</span> sono previste nel linguaggio Gambas: <SPAN Style="text-decoration:underline">non</span> esiste un oggetto "''Linked List''"; e pertanto non possono essere utilizzate. Possiamo, però, emulare il loro comportamento e funzionamento in Gambas mediante una variabile del tipo della ''Struttura'' modello, posta alla testa della ''Lista concatenata'', e alcune variabili di tipo ''Puntatore'' di appoggio.
 
−
 
 
−
Mostriamo un esempio commentato:
 
 
  <FONT Color=gray>' ''Impostiamo la "Struttura" modello, molto semplice, che rappresenterà il <SPAN Style="text-decoration:underline">primo</span> elemento della "Lista Lineare" concatenata, ed ove...''</font>
 
  <FONT Color=gray>' ''Impostiamo la "Struttura" modello, molto semplice, che rappresenterà il <SPAN Style="text-decoration:underline">primo</span> elemento della "Lista Lineare" concatenata, ed ove...''</font>
 
  Public Struct STRUTTURA
 
  Public Struct STRUTTURA
 
   i As Integer
 
   i As Integer
−
  <FONT Color=gray>' ''...l'ultimo membro è un "Puntatore" che servirà a creare e connettere questa ''Struttura'' al secondo elemento della "Lista Lineare":''</font>
+
  <FONT Color=gray>' ''...l'ultimo membro è un "Puntatore" che servirà a creare e connettere questa ''Struttura'' al successivo elemento della "Lista Lineare":''</font>
 
   p As Pointer
 
   p As Pointer
 
  End Struct
 
  End Struct
Riga 23: Riga 14:
 
   Dim st As STRUTTURA
 
   Dim st As STRUTTURA
 
   Dim i As Integer
 
   Dim i As Integer
 +
 
 +
<FONT Color=gray>' ''Crea il primo 'elemento-Struttura' della "Lista Lineare":''</font>
 +
  st = New STRUTTURA
 
    
 
    
−
  st = Crea_Lista()
+
<FONT Color=gray>' ''Va a creare i restanti elementi della "Lista Lineare":''</font>
 +
  Crea_Lista(st)
 
    
 
    
−
  Visualizza_Dati(st)
+
  Visualizza_Dati(st)
 
    
 
    
−
  Free(st.p)
+
  Free(st.p)
 
    
 
    
 
  '''End'''
 
  '''End'''
 
   
 
   
−
+
  '''Private''' Function Crea_Lista(nw As STRUTTURA)  <FONT Color=gray>' ''Passaggio della Struttura per "Indirizzo"''</font>
−
  '''Private''' Function Crea_Lista() As STRUTTURA
 
 
    
 
    
−
   Dim nw, sr As STRUTTURA
+
   Dim sr As STRUTTURA
−
  Dim p As Pointer
 
 
   Dim b As Byte
 
   Dim b As Byte
 
      
 
      
−
  <FONT Color=gray>' ''Crea la prima 'Struttura' della "Lista Lineare":''</font>
+
  <FONT Color=gray>' ''Immette il dato del primo elemento-Struttura della lista:''</font>
−
  nw = New STRUTTURA
+
  nw.i = 100
 +
     
 +
  sr = nw
 +
 
 +
<FONT Color=gray>' ''Alloca un'area di memoria riservata per il secondo elemento della "Lista Lineare":''</font>
 +
  sr.p = Alloc(Object.SizeOf(STRUTTURA), 1)
 
    
 
    
−
  <FONT Color=gray>' ''Viene impostato il valore del membro di tipo 'Intero' della prima 'Struttura' (ossia la primo elemento "Lista Lineare"):''</font>
+
  <FONT Color=gray>' ''Crea una catena di altri 9 elementi/Strutture, in modo tale che la "Lista Lineare" sarà formata in totale da 10 elementi/Strutture":''</font>
−
  Print "Immettere dato del 1° elemento/Struttura della 'Lista Lineare':"
+
  For b = 2 To 10
−
  nw = Immette_Valore(nw)
+
    sr = sr.p
 +
<FONT Color=gray>' ''Immette i dati dei successivi elementi-Struttura della lista:''</font>
 +
    sr.i = 100 * b
 +
<FONT Color=gray>' ''Alloca un'area di memoria riservata per il nuovo-successivo elemento della "Lista Lineare":''</font>
 +
    sr.p = Alloc(Object.SizeOf(STRUTTURA), 1)
 +
  Next
 +
     
 +
'''End'''
 
    
 
    
−
  <FONT Color=gray>' ''Alloca un'area di memoria riservata per il nuovo (il secondo) elemento della "Lista Lineare":''</font>
+
  '''Private''' Procedure Visualizza_Dati(tt As STRUTTURA)
−
  nw.p = Alloc(Object.SizeOf(STRUTTURA), 1)
 
−
  sr = nw
 
 
    
 
    
−
<FONT Color=gray>' ''Creiamo una catena di altri 3 elementi/Strutture, in modo tale che''
+
  Print "\nValori inseriti nella 'Lista Lineare':\n"
−
' ''la "Lista Lineare" sarà formata in totale da 4 elementi/Strutture:''</font>
 
−
  For b = 2 To 4
 
−
    sr.p = Alloc(Object.SizeOf(STRUTTURA), 1)
 
−
    sr = sr.p
 
−
    Print "Immettere il dato del "; b; "° elemento/Struttura:"
 
−
    sr = Immette_Valore(sr)
 
−
  Next
 
−
  sr.p = Alloc(Object.SizeOf(STRUTTURA), 1)
 
−
  sr = sr.p
 
 
    
 
    
−
  Return nw
+
  While tt.p > 0
 +
    Print tt.i
 +
    tt = tt.p
 +
    Free(tt.p)
 +
  Wend
 
    
 
    
 
  '''End'''
 
  '''End'''
 +
 +
 +
Altra modalità:
 +
Public Struct LISTA
 +
  sh As Short
 +
  i As Integer
 +
  succ As Pointer
 +
End Struct
 
   
 
   
 
   
 
   
−
  '''Private Function Immette_Valore(ra As STRUTTURA) As STRUTTURA
+
  '''Public''' Sub Main()
−
   
+
 
−
   Dim s As String
+
   Dim lst, lst2 As New LISTA
−
 
+
 
−
  Input s
+
  CreaStruttura(lst, 4)
−
  If IsDigit(s) = False Then Error.Raise("Il valore immesso non è un numero !")
+
 
−
  ra.i = Val(s)
+
  lst2 = lst
−
   
+
 
−
  Return ra
+
  While lst.succ > 0
−
   
+
    Print lst.sh, lst.i
 +
    lst = lst.succ
 +
  Wend
 +
 
 +
  Dealloca(lst2)
 +
 
 
  '''End'''
 
  '''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 Visualizza_Dati(tt As STRUTTURA)
+
  '''Private''' Procedure Dealloca(sl As ListA)
 
    
 
    
−
   Dim po As Pointer
+
   While sl.succ > 0
 +
    Free(sl.succ)
 +
    sl = sl.succ
 +
  Wend
 
    
 
    
−
  Print "\n\nValori inseriti nella 'Lista Lineare':\n"
 
−
 
 
−
  While Not IsNull(tt.p)
 
−
    Print tt.i
 
−
    po = tt.p
 
−
    tt = tt.p
 
−
    Free(po)
 
−
  Wend
 
−
 
 
 
  '''End'''
 
  '''End'''

Versione attuale delle 17:16, 10 nov 2021

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.

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à: 

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
Estratto da "https://www.gambas-it.org/wiki/index.php?title=Emulare_una_%27Lista_Lineare%27_mediante_una_Struttura_di_testa_ed_i_Puntatori&oldid=29211"