10: Allocazione dinamica della memoria Vers. 9.1 – Ottobre 2025
STRUTTURE DATI ASTRATTE LINEARI Definiamo nodo l’ unità di informazione relativa alla struttura dati che stiamo analizzando
SEQUENZA O LISTA
La sequenza o lista è uno dei tipi più semplici di struttura dati astratta informatica. E’ composta da una collezione di nodi tutti dello stesso tipo( s. d. omogenea) che sono caratterizzati dal fatto di avere, ad eccezione del primo e dell’ ultimo nodo della sequenza, un unico predecessore ed un unico successore
( N. B. PER QUESTO MODO SI USA PER TALI STRUTTURE ASTRATTE L’ AGGETTIVO LINEARE)
Esempio: consideriamo come nodo il giorno della settimana possiamo rappresentare graficamente la settimana come la sequenza seguente
1 ° nodo 2 ° nodo ultimo ° nodo
LUN MAR MER GIO VEN SAB DOM
Dal punto di vista formale una sequenza o lista può essere vista come un insieme di n nodi
P1, P2,…. Pn dove P1 è il primo nodo, Pn è l’ ultimo nodo ed il generico nodo Pk è preceduto dal nodo Pk-1 ed è seguito dal nodo Pk + 1 Il parametro n definisce la lunghezza della sequenza o lista. Se n = 0 la sequenza o lista è vuota.
Una sequenza o lista può essere:
(-) a lunghezza fissa: ossia il numero di nodi che la costituisce non può variare e quindi in tal caso la struttura dati è statica;
(-) a lunghezza variabile: ossia il numero di nodi che la costituisce può variare e quindi in tal caso la struttura dati è dinamica.
Sulla struttura dati sequenza o lista non è consentito l’ accesso diretto come avviene per l’ array, ma solo l’ accesso sequenziale ossia per accedere ad un determinato nodo della lista occorre accedere prima necessariamente a tutti i nodi che lo precedono.
Per questo motivo su tale tipo di struttura dati sono consentite ricerche solo di tipo sequenziale.
Una premessa rotazionale: indichiamo |
con [ ] una sequenza o lista vuota( con‘[’ che indica la testa e con‘]’ che indica il fondo) |
con [ P1, P2,…. Pn ] |
una sequenza formata dai nodi P1, P2,…. Pn con P1 in testa e Pn in fondo |
con N |
l’ insieme dei possibili nodi di una sequenza |
con S |
l’ insieme di tutte le possibili sequenze di nodi |
con φ |
l’ insieme vuoto |
con Β |
l’ insieme contenente i valori booleani VERO e FALSO |
Autore: Rio Chierego( email: riochierego @ libero. it- sito web: www. riochierego. it) Pag. 27