MODULO 2: Strutture dati avanzate e allocazione dinamica della memoria UD 3: Le Liste UD 4: Pile e...

MODULO 2: “Strutture dati avanzate e allocazione dinamica della memoria”

UD 3: “Le Liste”UD 4: “Pile e Code”UD 5: “Alberi e grafi”

MODULO 2: “Strutture dati avanzate e allocazione dinamica della memoria”

Questo modulo è proposto per una quarta classe di un Istituto Tecnico Industriale ad indirizzo Informatico.

L’obiettivo del modulo è di presentare:

schemi significativi di organizzazione delle informazioni;

le regole operative per la manipolazione delle strutture astratte di dati;

i metodi di rappresentazione (memorizzazione) delle strutture dati all’interno di un elaboratore.

UNITA’ DIDATTICA 4: Pile e code

A cura di Tania Barbagallo

Classe di Concorso: 42A

Docente: Prof. D. Cantone

Prerequisiti Conoscenza della rappresentazione della

memoria di un calcolatore. Conoscenze sicure del linguaggio C++. Conoscenza e utilizzo delle strutture di controllo,

delle strutture di dati e delle funzioni. Conoscenza dei puntatori. Definizione delle classi con attributi e metodi. Applicazione dei concetti della programmazione

ad oggetti nel linguaggio C++.

CompetenzeAl termine di questa unità didattica lo

studente dovrà essere in grado di: definire le caratteristiche delle strutture

astratte ”pila” e “coda”; comprendere la differenza tra gestione

statica e gestione dinamica della memoria;

implementare ”pila” e “coda” come strutture dinamiche di dati;

definire i modelli di classe.

Conoscenze

Al termine di questa unità didattica lo studente dovrà possedere le seguenti conoscenze:

strutture astratte di “pila” e “coda”; creazione dinamica di aree di memoria; gestione di pile e code; modelli di classe.

Abilità

Al termine di questa unità didattica lo studente dovrà aver acquisito le seguenti abilità:

saper utilizzare i metodi per la gestione della ”pila” ;

saper utilizzare i metodi per la gestione della “coda”.

Contenuti Richiami sul concetto di struttura

astratta di dati. La ”pila” come struttura statica. La ”pila” come struttura dinamica. La “coda” come struttura statica. La “coda” come struttura

dinamica.

Metodologia Lezione frontale

Lezione dialogata

Brainstorming

Gruppi di lavoro

Strumenti Libro di testo

Dispense fornite dal docente

Lavagna luminosa

Proiettore

Computer

Spazi

Aula

Laboratorio di Informatica

Verifiche

Questionari e test (strutturati e semistrutturati).

Prove di laboratorio.

Interventi di vario genere.

Valutazione Di tipo sommativo - in relazione al

raggiungimento degli obiettivi; sia in termini di conoscenza dei contenuti, sia in termini di acquisizione di competenze e abilità specifiche.

Di tipo formativo - in relazione all’impegno, costanza nello studio e partecipazione.

Tempi Lezione: 5 ore

Laboratorio: 3 ore

Verifica: 2 ore

Potenziamento e recupero: 2 ore

Cos’è una struttura astratta di dati?

Struttura astratta di

dati

Insiemi finiti di dati tra i quali esistono delle relazioni logiche.

Ha la funzione di un contenitore che può essere riempito con dati di volta in volta di tipo diverso.

Esempi di insiemi di dati correlati tra loro da relazioni logiche

Elenco telefonico

Schedario di una biblioteca

Elenco degli alunni di una classe

Le tessere degli abbonati di un garage di autovetture

Operazioni relative alle strutture dati

Accesso

Ricerca

Inserimento

Modifica

Cancellazione

a un elemento (o nodo) per leggere il contenuto.

di un elemento con un determinato contenuto.

di un elemento senza alterare le connessioni con gli altri nodi.

di un nuovo elemento.

del contenuto di un elemento tramite la ricerca e l’accesso al nodo.

Struttura astratta di dati Il processo di

realizzazione delle strutture della memoria del calcolatore prende il nome di implementazione.

Struttura astratta di dati

Statica

Dinamica

Quando non è posto alcun vincolo sulla dimensione della struttura.

Quando la dimensione è definita nel momento di creazione della struttura e non può essere modificata.

Struttura astratta di dati

LineareQuando un nodo può avere al più un nodo che lo precede e al più un nodo che lo segue.

Non lineare

Quando un nodo può avere due o più nodi che lo precedono o lo seguono.

Strutture informative significative Array Tabelle Lista lineare Lista concatenata Pila Coda Grafi Alberi

La PilaUna pila (detta anche STACK) è una struttura dati lineare, i cui elementi possono essere inseriti o estratti da un’unica estremità (LIFO).

LIFO è acronimo di Last In First Out, ovvero l’ultimo ad entrare è il primo ad uscire.

Modalità d’impiego delle pile La pila è un tipo di dato astratto che trova

impiego nell’organizzazione dei dati in memoria centrale in molti sistemi operativi, nonché nella memorizzazione degli indirizzi di ritorno delle funzioni.

Tale struttura è comune nei processi nei quali un problema in corso d’esame viene lasciato temporaneamente sospeso per affrontare un sottoproblema che, a sua volta è lasciato in sospeso, per affrontare un nuovo sottoproblema e così via finché l’ultimo sottoproblema generato è messo in testa alla pila dei vari sottoprogrammi da risolvere.

Operazioni sulle PileLe operazioni che si possono definire per una

pila (stack) sono: Push: aggiunge nuovo elemento alla pila. Pop: elimina l’elemento emergente dalla pila

TopElem: ritorna il valore del primo elemento della pila, senza estrarlo.

IsEmpty: per verificare se la pila è vuota (ritorna true se la pila non ha elementi).

IsFull: per verificare se la pila è piena. Clear: per cancellare tutti i dati.

viene ritornato l’elemento inserito da meno tempo!

La pila come struttura statica In alcuni casi le strutture LIFO hanno una

dimensione limitata, per cui è necessario definire un valore massimo di elementi inseribili.

Per l’implementazione di una pila servono: uno spazio di memoria ordinato, dove inserire

gli elementi; un indice per sapere quale è l’ultimo

elemento inserito.

La pila come struttura statica L’indice deve tener conto di quanti

elementi ci sono nella pila. Si utilizza un array per memorizzare gli

elementi e un numero intero che indica la prima posizione libera dello stack.

12345

top 5

Top = 0

Pila vuota

Top=max

Pila piena

Definizione della classe “pila”public class Pila{ private int top;

private final int MAX;private int elem[];private static final int MAXDEFAULT = 10;

public Pila(){ this(MAXDEFAULT);}public Pila(int max){ top = 0;

MAX = max;elem = new int[MAX];

}…

}

Definizione della classe “pila”public class Pila{ …

public bool IsFull(){ return (top == MAX);}

public bool IsEmpty(){ return (top == 0);}

public void Clear(){ top = 0;}…

}

Procedura IsFull

Procedura IsEmpty

Procedura Clear

Definizione della procedura “TopElem”

E’ la procedura che restituisce il valore dell’oggetto in cima.

public int TopElem()

{ if (IsEmpty())

return 0);

return elem[top-1] ;

}

Definizione della procedura “Push”

Nella procedura di inserimento bisogna eseguire i seguenti passi:

verificare che la pila non sia piena;

inserire l’elemento appena passato;

spostare di una posizione in alto l’indice top.

public bool Push(int val)

{ if (IsFull())

return false);

elem[top++] = val;

return true;

}

Definizione della procedura “Pop”

Nella procedura di estrazione bisogna eseguire i seguenti passi:

verificare che la pila non sia vuota;

decrementare il valore dell’indice;

leggere l’oggetto che sta in cima alla pila.

public int Pop()

{ if (IsEmpty())

return 0);

return elem[--top] ;

}

Esercizio da proporre agli studenti

Dati in input una sequenza di numeri, visualizzarla in ordine inverso. L’ultimo numero della sequenza sia zero.

Descrizione del problemaI numeri della sequenza vengono acquisiti da tastiera uno ad uno ed inseriti nella pila con l’operazione di Push, finché viene inserito il valore 0. Successivamente in una ripetizione i numeri vengono estratti dalla pila con l’operazione di Pop finché la pila è vuota.

Dati di inputNumeri della sequenza.

Dati di outputNumeri in ordine inverso all’inserimento.

Gestione statica e gestione dinamica

Gestione statica

Le aree di memoria richieste dal codice sorgente vengono predisposte dal compilatore attraverso la dichiarazione delle variabili e allocate all’avviamento del programma eseguibile.

Le istruzioni per l’allocazione di nuova memoria vengono richiamate durante l’esecuzione del programma.

Gestione dinamica

C++ :istruzioni relative alla memoria

NewPer l’allocazione di nuova memoria.

DeletePer la cancellazione di un’area di memoria.

Istruzione: New Questa istruzione restituisce l’indirizzo di memoria. Deve essere seguita dal tipo di dato a cui si vuole

allocare la memoria.

Si assegna il risultato di questa istruzione a un puntatore.

Una volta esaurito lo spazio di memoria, new restituisce un puntatore vuoto (0).

Esempio:

int *p=new int;

Istruzione: Delete Questa istruzione permette di

cancellare un indirizzo di memoria.

E’ seguita dall’indirizzo di memoria da deallocare, solitamente contenuto in un puntatore.

Esempio:

delete p;

La pila come struttura dinamica

dati

link

dati

link

dati dati

dati

link

Push

Pop

Si distingue una parte di dati e una parte di puntatori di collegamento (link).

3

2

1

Esempio “garage”

Creare la classe con i relativi metodi per gestire con un’organizzazione LIFO le tessere degli abbonati di un garage di autovetture. Il numero di posti auto del garage non è conosciuto a priori.

Esempio “garage” Organizzazione LIFO con gestione dinamica della memoria

Per realizzare tale struttura si deve definire l’elemento della pila che contiene l’informazione, cioè il numero dell’abbonato.

Quindi si predispongono le operazioni indispensabili a garantire la connessione di questi dati tra loro.

La parte di collegamento deve consentire di unire tra loro gli elementi della pila in modo da definire una sequenza ordinata per i dati memorizzati, per poter passare da un dato al successivo.

Il programma deve contenere una procedura di eliminazione delle aree create dinamicamente in modo da renderle disponibili ad altre applicazioni.

Esempio “garage” - DESCRIZIONE DEGLI OGGETTI

Lista

cima coda

InserisciPostoPostiOccupati

Tessera

numero *successiva

La classe “Lista” serve per la definizione dei dati da archiviare. I suoi attributi sono i puntatori agli elementi della lista.Un elemento della lista è di tipo “Tessera” ed è formato da: numero, che rappresenta la parte dati; successiva, che costituisce la parte dei link.

Algoritmo in pseudocodifica

INIZIOcrea oggetto garage di tipo Pilaaperto trueMENTRE (aperto = true)

chiedi “Numero di tessera”, leggi (num_tessera)inserisci num_tessera nella pilachiedi “0=Chiuso, 1=Ingresso cliente”, leggi

(aperto)PER (i=0; i < numero posti occupati; i++)

scrivi (numero posto, numero cliente)FINE

Esempio “garage” – Codice C++ (1)

#include <iostream.h>

class Tessera {public:

int numero; Tessera *successiva ;

}; // fine classe

La classe “Tessera” è formata da una parte contenente il dato vero e proprio, cioè il numero dell’abbonato e una parte per il collegamento con l’elemento successivo della pila (*successiva) .


class Lista {Tessera *cima;

public:Lista() : cima(0) {} // costruttore~ Lista () { // distruttoreTessera *tessera = cima;while (tessera) {

cima = tessera ->successiva;

delete tessera;tessera = cima;}

}

Il costruttore della classe si preoccupa di inizializzare gli attributi.

Il distruttore libera la memoria svuotando la lista.

Esempio “garage” – Codice C++ (3)void Inserisci (int n) { Tessera *tessera = new Tessera;tessera ->numero = n;tessera ->successiva = cima;cima = tessera;}

La funzione Inserisci serve alla creazione di ciascun elemento della pila.

Il metodo Inserisci utilizza l’istruzione new per creare un nuovo elemento della lista, inserisce i dati ricevuti nell’apposita area e aggiorna il puntatore *cima in modo da creare un collegamento con l’ultimo elemento inserito.


int posto (int n) { int i;Tessera *tessera = cima;for (i=0; tessera!=0; i++) {

if (i==n) return tessera->numero;tessera = tessera-

>successiva; }return –1;

}

Il metodo “posto” restituisce il numero di tessera del cliente che ha parcheggiato al posto n-esimo.


int postiOccupati () { int i;Tessera *tessera = cima;for (i=0; tessera != 0; i++)

tessera = tessera->successiva;

return i;}

}; // fine classe

istream &operator>>(istream &s, bool &b) { int r;s>>r;if (r) b = true; else b = false;retun s; }

Si utilizza l’overloading dell’’operatore >>, per acquisire da tastiera un tipo di dato booleano, indicante l’ingresso di un cliente o la chiusura del garage.

Il metodo “postiOccupati” restituisce il numero di posti occupati.


void main(){

bool aperto=true; int num_tessera,i;Lista garage;

while (aperto) {cout << “Numero di tessera del cliente: “;cin >> num_tessera;garage.inserisci (num_tessera);cout << “Immettere: 0= Chiuso, 1= Ingresso cliente\n“;cin >> aperto;

}cout << “Posto n.\tcliente\n”;for (i=0; i < garage.postiOccupati(); i++)

if (garage.posto(i) ! = -1)cout << “ “ << i << “\t\t “ garage.posto(i)

<<endl; }

Output prodotto dall’esecuzione del programma Numero di tessera del cliente: 10Immettere 0=Chiuso, 1=Ingresso cliente1 Numero di tessera del cliente: 20Immettere 0=Chiuso, 1=Ingresso cliente1 Numero di tessera del cliente: 30Immettere 0=Chiuso, 1=Ingresso cliente0

Posto Cliente

0 30

1 20

2 10

OUTPUT

INPUT da tastiera

Osservazioni (1)

In questo caso il programma riporta l’elenco dei clienti che occupano il garage in ordine inverso rispetto al loro ingresso in autorimessa.

Da notare che il programma è in grado di gestire pile di qualsiasi dimensione limitatamente alla capacità della memoria del calcolatore impiegato nell’esecuzione.

Osservazioni (2) La gestione delle pile vista finora

prevede la memorizzazione di un solo dato (numero). In una soluzione più generale si deve prevedere un’opportuna struttura per la parte dedicata ai dati.

Osservazioni (3)typedef struct DatiTessera {

int numero;char nome_cliente[30];char targa_auto[30];

} DatiTessera;

class Tessera {public:

// parte dei datiDatiTessera dato;// parte dei linksTessera *successiva;// costruttoreTessera() : successiva(0) {}

};

In una soluzione più generale, nell’esempio dell’autorimessa è possibile introdurre informazioni dati relative ai clienti prevedendo di conseguenza un’opportuna struttura per la parte dedicata ai dati .

Esempio “pila”

Scrivere il codice in grado di gestire una pila. Verificarne il funzionamento utilizzando un programma di collaudo in cui la struttura dei dati contenga un intero e un reale.

“Soluzione per la gestione di una generica pila”

Esempio “pila” - DESCRIZIONE DEGLI OGGETTI

Pila

*cima conta

Pila ~ Pila PushPop Size

Nodo

dato*successivo

Nodo

In una gestione generica delle pile la classe della lista dispone dei seguenti metodi:

Push() , che aggiunge un elemento alla pila;

Pop() , che estrae l’ultimo elemento inserito;

Size() , che restituisce il numero di elementi presenti nella lista attraverso l’attributo conta.~ Pila è il distruttore

definito per l’eliminazione di eventuali dati rimasti in memoria.

Algoritmo in pseudocodificaINIZIO

crea oggetto pila di tipo Pilachiedi “numero intero”, leggi (dato.x)MENTRE (dato.x<>0)

chiedi “numero reale”, leggi (dato.y)inserisci dato nella pilachiedi “numero intero”, leggi (dato.x)chiedi “svuotamento della pila”, leggi (risp)

SE (risp==“si”)MENTRE (dimensione della pila<>0)

estrai dato dalla pilascrivi(dato.x, dato.y)

scrivi (“la memoria è stata liberata”)FINE

Esempio “pila” – Codice C++ (1)

//STRUTTURA DEI DATItypedef struct Dato {

int x;float y;

} Dato;const Dato Dato_NULLO = {0,0.0};//PILA#include <iostream.h>class Nodo {public:

Dato dato; Nodo *successivo ;

Nodo (Dato d=Dato_NULLO, Nodo *n=0): dato(d), successivo(n) {}

}; // fine classe

Esempio “pila” – Codice C++ (2)class Pila {

Nodo *cima;double conta

public:Pila() : cima(0), conta(0) {} ~ Pila () {while (Size() ) Pop();} virtual bool Push(Dato &d) {

Nodo *p = new Nodo(d, cima);if (!p) {

cerr<< “\nMemoria esaurita\n”;return false;} cima = p;conta++;return true;

}


virtual Dato Pop() { Nodo *p = cima;Dato d = Dato_NULLO; if (p) {

d =p->dato; cima = p ->successivo; delete p;conta--; }

return d;}virtua double Size() { return conta; }

}; // fine classe


void main()

{ Pila pila;Dato dato = Dato_NULLO; char risposta;cout << “Immissione di un intero e di un reale (0 = fine): “;cin >> dato.x;while (dato.x) {

cin >> dato.y;if (!(pila.Push(dato))) return ;cout << “Immissione di un intero e di un reale (0 =

fine): “;cin >> dato.x;

} // fine while…


…cout << endl;cout << “Procedere allo svuotamento della pila (S/N) ? “;cin >> risposta;if risposta == ‘ S ’ ׀ ׀ risposta == ‘ s ’) { while (pila.Size() ) {

dato = pila.Pop();cout << dato.x << “ “ << dato.y << endl;

} cout << “La memoria è stata liberata” << endl;}

}

Osservazioni (1) Dopo la struttura dei dati è stata

definita la costante di annullamento del loro contenuto Dato_NULLO.Tale costante risulta molto utile per la creazione di un costruttore con valori di default:

Nodo(Dato d=Dato_NULLO, Nodo *n=0): dato(d), successivo(n) {}

Osservazioni (2) Questo tipo di costruttore, che

giustifica l’impiego di una classe anziché di una struttura per la definizione degli elementi della lista, permette di inizializzare un nuovo elemento durante la sua creazione:

Nodo *p = new Nodo(d, cima);

Osservazioni (3) Questo modo di inserire i dati nel

nuovo elemento della lista risulta più elegante rispetto a quello tradizionale:

N. B. Gli attributi della classe sono privati e i metodi sono tutti virtual.

Nodo *p = new Nodo;…P->dato = d;P->successivo = cima;

La Coda Le code (queue) sono strutture lineari i

cui elementi si inseriscono da un estremo e si estraggono dall’altro (FIFO).

FIFO è acronimo di First In First Out, ovvero il primo entrato è il primo ad uscire.

Modalità d’impiego delle code Come si usa dire impilare o accatastare

riferendosi alle pile, si dice accodare riferendosi alle code.

Lavorando sui computer multiutente è frequente che si accodino stampe o lavori nelle rispettive code: i moduli software del sistema operativo che gestiscono queste attività del sistema di elaborazione seguono infatti il principio FIFO.

Così, ad esempio, se più utenti richiedono le stampe sulla stessa stampante, esse vengono eseguite nello stesso ordine con cui sono state richieste (coda di SPOOL).

Operazioni sulle CodeLe operazioni che si possono definire per una

coda (queue) sono: Enqueue (o Push): aggiunge nuovo elemento

alla coda. Dequeue (o Pop): estrae un elemento dalla

coda.

FirstElem: ritorna il valore del primo elemento della coda, senza estrarlo.

IsEmpty: per verificare se la coda è vuota (ritorna true se la coda non ha elementi).

IsFull: per verificare se la coda è piena. ClearQueue: per cancellare tutti i dati.

viene ritornato l’elemento inserito da più tempo!

La coda come struttura statica In alcuni casi anche le strutture

FIFO hanno una dimensione limitata, oltre la quale non vengono più accettati inserimenti.

Per definire una coda servono: uno spazio di memoria ordinato, dove

inserire gli elementi; due indici per sapere quali sono il

primo e l’ultimo elemento.

La coda – Estrazione\Inserimento

In seguito ad ogni estrazione, gli elementi rimanenti vengono fatti avanzare di una posizione.

Per l’inserimento, invece, viene occupata l’ultima posizione libera.

5 7 2 4 3 1

9

5 7 2 4 3 1

5 7 2 4 3 1

3

9 5 7 2 4

5 7 2 4

5 7 2 4

La coda come struttura statica E’ possibile implementare una

coda per mezzo di un array.

Si tenga presente, però, che diventa oneroso eseguire uno shift di tutti gli elementi dopo ogni estrazione.

La coda come struttura statica

3 5 9 2 4 1 8

head

tail2

4

18

359

tail

head

Per tale motivo conviene pensare all’array come una struttura nella quale si passa dall’ultimo al primo elemento in modo “circolare” (nel quale l’elemento che segue l’ultimo è il primo). E quindi occorre tener presente due indici, head e tail, che indicano il primo elemento e l’ultimo.

La coda come struttura “circolare”

Il vantaggio di una simile struttura logica è che non è necessario effettuare uno shift per ogni inserimento, ma basta una sola assegnazione (più la modifica della variabile head).

Head viene incrementato per ogni operazione di Estrazione.

Tail viene incrementato per ogni operazione di Inserimento.


Il valore di tail potrà raggiungere, ma non superare il valore di head (a seguito di operazioni di Inserimento ne segue il riempimento della coda).

tail head


Analogamente, il valore di head non potrà superare tail (dopo operazioni di Estrazione ne segue lo svuotamento della coda).

headtail


Se però i due puntatori coincidono, dobbiamo distinguere le condizioni di coda vuota o coda con un solo elemento.

Si può decidere se: lasciare sempre una casella vuota e far

indicare a tail la prima posizione vuota; usare una variabile booleana per sapere se

la coda contiene elementi.


Nel primo caso gli indici head e tail si possono sovrapporre solo se la coda è vuota.

Head punta al primo elemento della coda. Tail punta alla prima posizione libera dopo

l’ultimo elemento (tranne se la coda è vuota). In ogni caso rimane sempre una casella vuota.

tailhead

xx

x

xxx

x

x

x


Nel secondo caso si ha: Head punta alla prima posizione piena. Tail punta all’ultima posizione piena (tranne se la

coda è vuota). In tal caso se gli indici head e tail si sovrappongono

la coda può essere vuota o con un solo elemento. Tramite una variabile booleana si possono distinguere i due casi.

head

tailtail

head

Empty=true

Empty=false

x


Nella implementazione si considererà il primo caso cioè si fa in modo che rimanga sempre una casella vuota.

Head punta al primo elemento della coda.Tail punta alla prima posizione libera dopo

l’ultimo elemento. Qualunque operazione coinvolga gli indici deve essere fatta modulo la dimensione dell’array.

Esempio (1)

A

A B

head

tail

Coda

vuota

headtail

A B C

A B C D B C D

head

head

head

head

tail tail

tail tail

Push(A)

Push(B)

Push(C)

Push(D)

Pop(A)

Esempio (2)

B C D E B C D E F

head

tail head

tail

head

head

head

head

tail tail

tail tail

Coda

piena

G C D E FC D E F Coda

piena

G D E F G E F

Push(G)

Push(E)

Push(F)

Pop(B)

Pop(C) Pop(D)

Esempio (3)

G H

head

tail head

tail

H

head

head

head

tail tail

tail

G H E F G H F

Coda

vuota

Pop(E)Push(H)

Pop(F) Pop(G)

Pop(H)

Definizione della classe “coda”

public class Coda{ private int head, tail;

private final int MAX;private int elem[];private static final int MAXDEFAULT = 10;

public Coda(){ this(MAXDEFAULT);}public Coda(int max){ head = tail = 0;

MAX = max;elem = new int[MAX];

}…

}

Definizione della classe “coda”

public class Coda{ …

public bool IsFull(){ return (head == (tail+1) % MAX);}

public bool IsEmpty(){ return (head == tail);}

public void ClearQueue(){ head = tail = 0;}…

}

Procedura IsFull

Procedura IsEmpty

Procedura ClearQueue

Definizione della procedura “FirstElem”

public int FirstElem()

{ if (IsEmpty())

return 0);

return elem[head];

}

E’ la procedura che restituisce il valore del primo elemento .

Definizione della procedura“Push”

public bool Push(int val){ if IsFull())

return false;elem[tail] = val;tail = ++tail % MAX;return true;

}

Nella procedura di inserimento bisogna eseguire i seguenti passi:

verificare che la coda non sia piena;

inserire l’elemento appena passato;

aumentare di una posizione l’indice tail (modulo la dimensione dell’array).

Definizione della procedura“Pop”

public int Pop()

{ if IsEmpty()return 0;

int val = elem[headl];head = ++head % MAX;return val;

}

Nella procedura di estrazione bisogna eseguire i seguenti passi:

verificare che la coda non sia vuota;

leggere l’oggetto che occupa la prima posizione;

aumentare di una posizione il valore dell’indice head (modulo la dimensione dell’array).

Esercizio da proporre agli studenti

Dati in input una sequenza di numeri, si visualizzino gli ultimi dati inseriti secondo l’ordine di inserimento. Per segnalare la fine dell’inserimento, l’ultimo numero della sequenza sia 0.

Descrizione del problemaI numeri della sequenza vengono inseriti nella coda in seguito a quelli già esistenti; se però nella coda tutti i posti sono occupati viene segnalato un messaggio di indisponibilità perché la coda è piena: in questo caso il procedimento forza un’operazione di estrazione all’inizio della coda, prima di inserire il nuovo elemento. Al termine dell’elaborazione (con l’inserimento del numero 0), svuotando la coda si ha il risultato desiderato.

Dati di inputNumeri della sequenza.

Dati di outputGli ultimi numeri inseriti secondo l’ordine di inserimento.

La coda come struttura dinamica

dati

link

dati

link

dati

dati

dati

link

Pop

Push

Si distingue una parte di dati e una parte di puntatori di collegamento (link).

1

3

2

Struttura dati di una coda La realizzazione di una coda generica

prevede la stessa struttura dati vista per la pila, cioè una classe per la gestione della lista e una classe per la definizione degli elementi.

In questo caso la lista contiene due puntatori ai suoi elementi in modo da gestire il caricamento, metodo Push(), e l’estrazione, metodo Pop(), attraverso la modalità FIFO.

Esempio “coda”

Scrivere il codice in grado di gestire una coda. Verificarne il funzionamento utilizzando un programma di collaudo in cui la struttura dei dati contenga un intero e un reale.

“Soluzione per la gestione di una generica coda”

Esempio “coda” - DESCRIZIONE DEGLI OGGETTI

Coda

*cima *codaconta

Coda ~ Coda PushPop Size

Nodo

dato*successivo

Nodo

In una gestione generica delle code la classe della lista dispone dei seguenti metodi:

Push() , che aggiunge un elemento alla coda;

Pop() , che estrae l’elemento inserito da più tempo;

Size() , che restituisce il numero di elementi presenti nella lista attraverso l’attributo conta. ~ Coda è il

distruttore definito per l’eliminazione di eventuali dati rimasti in memoria.

Algoritmo in pseudocodificaINIZIO

crea oggetto coda di tipo Codachiedi “numero intero”, leggi (dato.x)MENTRE (dato.x<>0)

chiedi “numero reale”, leggi (dato.y)inserisci dato nella codachiedi “numero intero”, leggi (dato.x)

chiedi “svuotamento della pila”, leggi (risp)SE (risp==“si”)

MENTRE (dimensione della coda<>0estrai dato dalla codascrivi(dato.x, dato.y)

scrivi (“la memoria è stata liberata”)FINE

Esempio “coda” – Codice C++ (1)//STRUTTURA DEI DATItypedef struct Dato {

int x;float y;

} Dato;const Dato Dato_NULLO = {0,0.0};//CODA#include <iostream.h>class Nodo {public:

Dato dato; Nodo *successivo ;

Nodo(Dato d=Dato_NULLO, Nodo *n=0): dato(d), successivo(n) {}

}; // fine classe

Esempio “coda” – Codice C++ (2)

class Coda {Nodo *cima;Nodo *coda;double conta

public:Coda() : cima(0), conta(0) {} ~ Coda () {while (Size() ) Pop();} virtual bool Push(Dato &d) {

Nodo *p = new Nodo(d);if (!p) {

cerr<< “\nMemoria esaurita\n”;return false;}

if (cima) coda->successivo =p; else cima=p; coda = p;conta++;return true;

}


virtual Dato Pop() { Nodo *p = cima;Dato d = Dato_NULLO; if (p) {

d =p->dato; cima = p ->successivo; delete p;conta--; }

return d;}virtua double Size() { return conta; }

}; // fine classe


void main()

{ Coda coda;Dato dato = Dato_NULLO; char risposta;cout << “Immissione di un intero e di un reale (0 = fine): “;cin >> dato.x;while (dato.x) {

cin >> dato.y;if (!(coda.Push(dato))) return ;cout << “Immissione di un intero e di un reale (0 =

fine): “;cin >> dato.x;

} // fine while…


…cout << endl;cout << “Procedere allo svuotamento della coda (S/N) ? “;cin >> risposta;if risposta == ‘ S ’ ׀ ׀ risposta == ‘ s ’) { while (coda.Size() ) {

dato = coda.Pop();cout << dato.x << “ “ << dato.y << endl;

} cout << “La memoria è stata liberata” << endl;}

}

Osservazioni La gestione di una coda richiede una

particolare attenzione per l’implementazione per l’inserimento di nuovi elementi.

La struttura dell’elemento che è rappresentato dalla classe Nodo, il metodo di estrazione Pop() e il metodo che restituisce la dimensione della lista Size() , rimangono invece invariati.

Si può pensare di derivare la classe Coda dalla classe Pila

class Coda : public Pila {Nodo *coda;double conta

public:Coda() : Pila(), coda(0) {} virtual bool Push(Dato &d) {

Nodo *p = new Nodo(d);if (!p) {

cerr<< “\nMemoria esaurita\n”;

return false;}

if (cima) coda->successivo =p; else cima=p;

coda = p;conta++;return true;

}}; // fine classe

Il distruttore della classe derivata viene omesso in quanto la lista viene svuotata dal distruttore della classe di base. La cima della pila non potrà più essere di tipo private.

MODULO 2: Strutture dati avanzate e allocazione dinamica della memoria UD 3: Le Liste UD 4: Pile e...

Documents

Transcript of MODULO 2: Strutture dati avanzate e allocazione dinamica della memoria UD 3: Le Liste UD 4: Pile e...