10 : Allocazione dinamica della memoria Vers . 8.3 – Ottobre 2023
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