Strutture dati

Strutture dati

Arianna Guidolin

Strutture

Array

Liste

Pile

Code

Alberi

Organizzazionenella memoria

Puntatori

Strutture statichee dinamiche

Memorizzazionedelle strutture

Array

Liste

Pile e code

Alberi binari

Creazione di tipidi dati

Strutture datiJ. Glenn Brookshear, Computer Science: An Overview

Capitolo 8: Data Abstractions

Arianna Guidolin

Universita degli Studi di Trento

4 maggio 2012

Arianna Guidolin (Universita degli Studi di Trento) Strutture dati 4 maggio 2012 1 / 35

Strutture dati

Arianna Guidolin

Strutture

Array

Liste

Pile

Code

Alberi


Puntatori



Array

Liste

Pile e code

Alberi binari


Array

Si chiamano array le strutture di dati organizzate come vettori omatrici.

Array che contengono dati dello stesso tipo si dicono omogenei,mentre array che contengono dati di diverso tipo si dicono eterogenei


Strutture dati

Arianna Guidolin

Strutture

Array

Liste

Pile

Code

Alberi


Puntatori



Array

Liste

Pile e code

Alberi binari


Liste

Una lista e una collezione di dati organizzati sequenzialmente

L’inizio di una lista si chiama testa, la fine coda

Le operazioni che si possono fare su una lista sono:

rimuovere elementi

aggiungere elementi

controllare quali elementi sono presenti

cambiare l’ordine degli elementi

cercare un determinato elemento


Strutture dati

Arianna Guidolin

Strutture

Array

Liste

Pile

Code

Alberi


Puntatori



Array

Liste

Pile e code

Alberi binari


Esempi di liste

Mario ← testa

Giovanni

Francesca

Lucia ← coda


Strutture dati

Arianna Guidolin

Strutture

Array

Liste

Pile

Code

Alberi


Puntatori



Array

Liste

Pile e code

Alberi binari


Esempi di liste

De Nicola ←coda

Einaudi

Gronchi

Segni

Saragat

Leone

Pertini

Cossiga

Scalfaro

Ciampi

Napolitano ←testa


Strutture dati

Arianna Guidolin

Strutture

Array

Liste

Pile

Code

Alberi


Puntatori



Array

Liste

Pile e code

Alberi binari


Possiamo imporre delle restrizioni sui modi in cui gli elementivengono aggiunti o eliminati da una lista

Una pila (stack) e una lista in cui i vari elementi possono essereinseriti o rimossi solo dalla testa

Otteniamo un modello di struttura LIFO (Last In, First Out):l’ultimo elemento inserito nella lista sara il primo ad essere tolto


Strutture dati

Arianna Guidolin

Strutture

Array

Liste

Pile

Code

Alberi


Puntatori



Array

Liste

Pile e code

Alberi binari


Esempio

pila di libri


Strutture dati

Arianna Guidolin

Strutture

Array

Liste

Pile

Code

Alberi


Puntatori



Array

Liste

Pile e code

Alberi binari


Una coda (queue) e una lista in cui i termini possono essere inseritisolo in coda e rimossi solo dalla testa

Una coda ha una struttura di tipo FIFO (First In, First Out): ilprimo elemento ad essere inserito corrisponde al primo elemento cheverra tolto


Strutture dati

Arianna Guidolin

Strutture

Array

Liste

Pile

Code

Alberi


Puntatori



Array

Liste

Pile e code

Alberi binari


Esempio

fila di bambini


Strutture dati

Arianna Guidolin

Strutture

Array

Liste

Pile

Code

Alberi


Puntatori



Array

Liste

Pile e code

Alberi binari


Alberi

Un albero e una collezione di elementi organizzati in modo gerarchico

radice

nodo nodo

foglia foglia foglia foglia


Strutture dati

Arianna Guidolin

Strutture

Array

Liste

Pile

Code

Alberi


Puntatori



Array

Liste

Pile e code

Alberi binari


Esempio

NASA Astrobiology Institute


Strutture dati

Arianna Guidolin

Strutture

Array

Liste

Pile

Code

Alberi


Puntatori



Array

Liste

Pile e code

Alberi binari


Nella memoria principale del computer i dati sono organizzati comesuccessione di celle di memoria

L’organizzazione secondo le strutture di alberi, liste o array riguardagli utenti ed e solo simulata all’interno di un computer in modi diversia seconda della struttura voluta:

gli utenti non vedono come i dati sono organizzati nella memoria

l’accesso ai dati avviene come se fossero organizzati secondo lastruttura desiderata


Strutture dati

Arianna Guidolin

Strutture

Array

Liste

Pile

Code

Alberi


Puntatori



Array

Liste

Pile e code

Alberi binari


Ogni cella di memoria e identificata da un indirizzo, che e un valorenumerico

Anche l’indirizzo di una cella viene memorizzato in una cella dimemoria, chiamata puntatore

Ogni elemento di una struttura e memorizzato in una cella, e quindi ilpuntatore di un determinato elemento contiene l’indirizzo della cellain cui questo elemento e memorizzato

Le strutture elencate corrispondono quindi a determinati modi diorganizzare le celle di memoria e i puntatori


Strutture dati

Arianna Guidolin

Strutture

Array

Liste

Pile

Code

Alberi


Puntatori



Array

Liste

Pile e code

Alberi binari


Le strutture in cui sono organizzati i dati possono essere di tipostatico oppure dinamico.

Una struttura statica e utile quando si deve accedere ai dati perleggerli o cambiare i loro valori, ma la dimensione o la configurazionedella struttura non cambiano nel tempo. Nel momento della creazionedella struttura si riserva lo spazio necessario per contenere i suoi dati

Se invece c’e bisogno di aggiungere o rimuovere elementi, omodificare la struttura, si usa un tipo di struttura dinamica. Inquesto caso si deve considerare il fatto che la struttura puo crescere equindi potrebbe essere necessario spostare i dati in una parte dimemoria in cui c’e piu spazio disponibile


Strutture dati

Arianna Guidolin

Strutture

Array

Liste

Pile

Code

Alberi


Puntatori



Array

Liste

Pile e code

Alberi binari


Array omogenei 1-dimensionali

Identifichiamo i dati nell’array grazie alla loro posizione

I dati vengono memorizzati in una successione di celle di memoriacon indirizzi consecutivi

Se x e l’indirizzo della prima cella di memoria, allora l’indirizzo dellaj-esima cella di memoria e x + (j − 1)


Strutture dati

Arianna Guidolin

Strutture

Array

Liste

Pile

Code

Alberi


Puntatori



Array

Liste

Pile e code

Alberi binari


Array omogenei 2-dimensionali

Si memorizzano i dati riga per riga oppure colonna per colonna. Nellarappresentazione per riga, se x e l’indirizzo della prima cella dimemoria e il numero di colonne e c , l’indirizzo dell’elemento che stanella i-esima riga e j-esima colonna e

x + c(i − 1) + (j − 1)


Strutture dati

Arianna Guidolin

Strutture

Array

Liste

Pile

Code

Alberi


Puntatori



Array

Liste

Pile e code

Alberi binari


Array eterogenei

Se il numero di celle richieste per ogni componente dell’array e fisso,possiamo memorizzarlo in un blocco di celle consecutive come nelcaso di array omogenei

Se ad esempio abbiamo tre componenti che richiedonorispettivamente n, m, l celle di memoria e x e l’indirizzo della primacella, l’indirizzo della prima cella della seconda componente e x + n


Strutture dati

Arianna Guidolin

Strutture

Array

Liste

Pile

Code

Alberi


Puntatori



Array

Liste

Pile e code

Alberi binari


Nel caso di array dinamici, ogni componente viene memorizzata inuna porzione di memoria separata

Le varie componenti sono poi collegate utilizzando puntatori

Ad esempio se si deve memorizzare un array eterogeneo formato datre componenti, in memoria bisogna anche riservare uno spazio per ipuntatori. Se il blocco di memoria in cui questi sono memorizzati haindirizzo x , possiamo trovare la prima componente dell’arrayguardando a cosa punta il puntatore con indirizzo x , e per accederealla componente successiva dell’array bisogna riferirsi a quantoriportato nel puntatore che ha indirizzo x + 1


Strutture dati

Arianna Guidolin

Strutture

Array

Liste

Pile

Code

Alberi


Puntatori



Array

Liste

Pile e code

Alberi binari


Liste

Possono essere memorizzate in un unico blocco di celle di memoriacon indirizzi consecutivi: se assumiamo che ogni elemento della listanon sia piu lungo di n caratteri, possiamo dividere il blocco di celle insotto-blocchi, ognuno contenente n celle

Questo metodo va bene nel caso di liste statiche, in cui compare unnumero fisso di elementi. Rimuovere un elemento provocherebbeinfatti la creazione di un buco nella lista, mentre aggiungere unelemento richiederebbe di spostare la lista in una porzione di memoriain grado di contenerla tutta


Strutture dati

Arianna Guidolin

Strutture

Array

Liste

Pile

Code

Alberi


Puntatori



Array

Liste

Pile e code

Alberi binari


Per le liste dinamiche bisogna agire diversamente:

ogni elemento della lista viene memorizzato in un’area dellamemoria

le varie celle di memoria vengono collegate tramite puntatori

Se ogni elemento della lista e formato da n caratteri, lo spaziorichiesto per memorizzali consiste in n + 1 celle di memoria: n celleper l’elemento e una cella per il puntatore dell’elemento successivo


Strutture dati

Arianna Guidolin

Strutture

Array

Liste

Pile

Code

Alberi


Puntatori



Array

Liste

Pile e code

Alberi binari


Ogni lista ha una testa e una coda: un puntatore particolare indica lacella di memoria che contiene l’elemento in testa alla lista, mentreall’ultimo elemento si associa un puntatore NULL, che indica che nonci sono termini successivi nella lista.


Strutture dati

Arianna Guidolin

Strutture

Array

Liste

Pile

Code

Alberi


Puntatori



Array

Liste

Pile e code

Alberi binari


In questo modo le operazioni di inserimento ed eliminazione dielementi si fanno unicamente con i puntatori

Per rimuovere un elemento basta modificare il puntatore precedente,facendogli indicare l’elemento successivo a quello che si vuoleeliminare


Strutture dati

Arianna Guidolin

Strutture

Array

Liste

Pile

Code

Alberi


Puntatori



Array

Liste

Pile e code

Alberi binari


Per aggiungere un elemento, dopo aver trovato lo spazio di memoriaadatto per contenerlo, bisogna modificare due puntatori: quellodell’elemento precedente e quello del nuovo elemento


Strutture dati

Arianna Guidolin

Strutture

Array

Liste

Pile

Code

Alberi


Puntatori



Array

Liste

Pile e code

Alberi binari


Pile

Una delle estremita del blocco di memoria in cui memorizzare la pilaviene utilizzata come base (cella in cui viene memorizzato il primoelemento). Gli elementi da inserire vengono posti successivamenteandando in direzione dell’altra estremita

Quello che cambia quando si aggiungono o rimuovono elementi dauna pila e la posizione della testa: un puntatore contiene quindil’indirizzo della testa della pila


Strutture dati

Arianna Guidolin

Strutture

Array

Liste

Pile

Code

Alberi


Puntatori



Array

Liste

Pile e code

Alberi binari


Per aggiungere un elemento, il puntatore viene modificato ad indicarela posizione immediatamente oltre la testa e quindi in questaposizione si va ad inserire il nuovo elemento

Per eliminare un elemento basta modificare il puntatore in modo chepunti all’elemento precedente


Strutture dati

Arianna Guidolin

Strutture

Array

Liste

Pile

Code

Alberi


Puntatori



Array

Liste

Pile e code

Alberi binari


Code

Poiche gli elementi vengono inseriti dal fondo e tolti dalla testa,servono due puntatori alle due estremita

Quando la coda e vuota, entrambi i puntatori indicano la stessaposizione

Per inserire un elemento, si cambia la posizione del puntatore allacoda


Strutture dati

Arianna Guidolin

Strutture

Array

Liste

Pile

Code

Alberi


Puntatori



Array

Liste

Pile e code

Alberi binari


Quando si elimina un elemento, quello che cambia e il puntatore allatesta

Con le operazioni di aggiunta ed eliminazione dei termini, la coda“scorre”nella memoria


Strutture dati

Arianna Guidolin

Strutture

Array

Liste

Pile

Code

Alberi


Puntatori



Array

Liste

Pile e code

Alberi binari


Per mantenere sempre i termini all’interno dello stesso blocco dimemoria, quando il puntatore alla coda arriva ad indicare l’estremitadel blocco di memoria, i nuovi termini da aggiungere vengono postiall’altra estremita. Otteniamo una struttura circolare


Strutture dati

Arianna Guidolin

Strutture

Array

Liste

Pile

Code

Alberi


Puntatori



Array

Liste

Pile e code

Alberi binari


Alberi binari

Un albero binario e un albero in cui ogni nodo ha al massimo due figli.

Per memorizzare una struttura di questo tipo possiamo usare ipuntatori. Ogni nodo dell’albero consiste di tre componenti

il dato

un puntatore al primo figlio (a sinistra nel grafico dell’albero)

un puntatore al secondo figlio (a destra nel grafico dell’albero)

Quindi ogni nodo deve essere pensato come un blocco continuo dicelle di memoria


Strutture dati

Arianna Guidolin

Strutture

Array

Liste

Pile

Code

Alberi


Puntatori



Array

Liste

Pile e code

Alberi binari


Ogni puntatore deve puntare o ad un figlio del nodo a cui e associatooppure deve avere valore NULL, che significa che non ci sono nodisuccessivi in quella direzione

Come per le liste, uno speciale puntatore indica qual e l’elementoiniziale dell’albero, cioe la radice


Strutture dati

Arianna Guidolin

Strutture

Array

Liste

Pile

Code

Alberi


Puntatori



Array

Liste

Pile e code

Alberi binari


Un altro modo per memorizzare alberi binari puo essere quello diconsiderare un unico blocco di memoria in cui vengono messi insuccessione un nodo, il figlio sinistro, il figlio destro e cosı via: i figlidel nodo in posizione n sono in posizione 2n (sinistro) e 2n + 1(destro)


Strutture dati

Arianna Guidolin

Strutture

Array

Liste

Pile

Code

Alberi


Puntatori



Array

Liste

Pile e code

Alberi binari


In questo modo si trovano facilmente genitori, figli o fratelli di unnodo, ma nel caso di alberi sbilanciati oppure con tanti buchi, restanoinutilizzate molte celle di memoria


Strutture dati

Arianna Guidolin

Strutture

Array

Liste

Pile

Code

Alberi


Puntatori



Array

Liste

Pile e code

Alberi binari


I linguaggi di programmazione mettono a disposizione dei tipi di datiprimitivi, come ad esempio gli interi e i reali

Ci sono anche dei modi in cui creare dei tipi di dati personalizzati, aseconda delle proprie esigenze

Supponiamo di dover gestire molte variabili contemporaneamente,che hanno tutte la stessa struttura, per esempio vogliamo catalogaredei libri indicando autore, anno di pubblicazione e genere letterario


Strutture dati

Arianna Guidolin

Strutture

Array

Liste

Pile

Code

Alberi


Puntatori



Array

Liste

Pile e code

Alberi binari


Invece di definire ogni volta una variabile con la struttura desiderata,si puo definire direttamente un nuovo tipo di dato con la nuovastruttura che si intende utilizzare: definiamo il nuovo tipo di datoLibro:

define type Libro {char Autore;

int Anno;

char Genere;

}


Strutture dati

Arianna Guidolin

Strutture

Array

Liste

Pile

Code

Alberi


Puntatori



Array

Liste

Pile e code

Alberi binari


Successivamente questo nuovo tipo di dato viene utilizzato come sefosse un tipo primitivo: come per una variabile intera dichiariamo

int a;

per un dato del nuovo tipo possiamo dichiarare

Libro Amleto;

Quindi la variabile Amleto fa riferimento ad una struttura contenenteautore, anno e genere del libro e possiamo poi andare ad assegnare lecaratteristiche


Strutture dati

Arianna Guidolin

Strutture

Array

Liste

Pile

Code

Alberi


Puntatori



Array

Liste

Pile e code

Alberi binari


Un tipo di dato completo e costituito da:

un metodo di memorizzazione dei dati

un insieme di operazioni

Nella creazione di un nuovo tipo di dato abbiamo solo descritto comesi possa definire un metodo di memorizzazione di alcuni dati entrouna certa struttura, ma non abbiamo posto condizioni per poter fareoperazioni

Per aggiungere procedure sui nuovi tipi di dati, bisogna definirleall’interno della definizione del tipo stesso. I tipi definiti in cuicompaiono anche operazioni vengono chiamati tipi di dati astratti


Strutture dati

Documents

Transcript of Strutture dati