Strutture di Dati Introduzione

(1)

G. Mecca – Università della Basilicata – [email protected]

Programmazione Procedurale in Linguaggio C++

Strutture di Dati Introduzione

versione 2.0

Questo lavoro è concesso in uso secondo i termini di una licenza Creative Commons (vedi ultima pagina)

2

Sommario

m

Panoramica

ðLa lista

m

Alcuni Esempi

ðArchivio di Temperature ðIl Gioco del Lotto

ðStudenti Universitari

Strutture di Dati: Introduzione >> Sommario

(2)

G. Mecca - Programmazione Procedurale in Linguaggio C++ 3

Panoramica

m

Metodologia di Sviluppo

ðil passo fondamentale è la scelta

dell’algoritmo (strategia) e la scrittura del codice sorgente

m

Scelta della strategia

ðstrategia di rappresentazione dei dati (dichiarazioni)

ðstrategia di operazioni

Strutture di Dati: Introduzione >> Panoramica

Panoramica

m

Strategia di rappresentazione

ðrappresentare i dati del problema attraverso le variabili del programma

ðscegliere opportunamente i tipi di dato

m

Tipi disponibili

ðtipi di base e predefiniti

ðtipi strutturati (array e record)

ðampia libertà nel costruire strutture complesse (nidificazione)

(3)

Panoramica

m

In generale

ðper rappresentare i dati di problemi

complessi (es: studenti, automobili), bisogna costruire una “struttura di dati”

m

Struttura di dati

ðstrategia secondo la quale sono organizzate le variabili che rappresentano i dati del

problema

6

Panoramica

m

Importanza della struttura di dati

ðtipicamente i dati di un problema possono essere rappresentati utilizzando strutture diverse

ðes: con record o senza record, con array monodimensionali o bidimensionali ecc.

ðla scelta della rappresentazione influenza significativamente le operazioni

ðsi tratta di un passo estremamente delicato

(4)

Panoramica

m

Un possibile approccio

ðimparare dall’esperienza

ðadottando “strutture di dati notevoli”

m

Strutture di Dati Notevoli

ðè possibile classificare la struttura dei dati dei problemi in alcune categorie ricorrenti

ðper i quali esistono soluzioni sperimentate ðcon algoritmi consolidati

Panoramica

m

Obiettivo di questa parte del corso

ðstudiare le tecniche per la costruzione di

strutture di dati notevoli

ðstudiare i relativi algoritmi, che rappresentano tecniche notevoli di programmazione

ðin modo da sapere come utilizzarle opportunamente

(5)

Panoramica

m

Un esempio tipico

ðil problema richiede di trattare una collezione di dati (con struttura semplice o complessa)

m

Collezione

ðgruppo di dati tutti della stessa natura ðpuò contenere duplicati o meno

ðpuò essere rilevante l’ordine degli elementi o meno

10

Panoramica

m

Classificazione delle collezioni principali

ðinsieme: collezione in cui l’ordine non è

rilevante e senza duplicati

es: i modelli delle automobili FIAT ðmultinsieme: insieme con duplicati

(meno frequente)

ðlista: collezione in cui l’ordine è rilevante e possono esserci duplicati

es: numeri estratti sulla ruota di Roma es: voti riportati da uno studente

(6)

Panoramica

m

Esempi visti

ðtemperature medie: una lista di 12 (o 365) temperature

ðpartite di calcio: una lista di 9 partite

m

Caratteristica comune

ðdimensione fissata per tutta la durata del programma

ðè sufficiente utilizzare array e record ðin generale non è così

Panoramica

m

Il caso più generale

ðuna lista di elementi (consente di

rappresentare anche insiemi e multiinsiemi) ðdi dimensione variabile (tra un’esecuzione e

l’altra o durante la stessa esecuzione):

consente aggiunte ed eliminazioni

m

Soluzione

ðla struttura di dati “lista” (fondamentale)

(7)

Alcuni Esempi

m

Nel seguito

ðalcuni esempi per mostrare la programmazione con le liste

m

Esempi

ðgestione dell’archivio di temperature (con aggiunte ed eliminazioni)

ðil gioco del lotto

ðgestione dell’archivio di studenti universitari

Strutture di Dati: Introduzione >> Alcuni Esempi

14

Archivio di Temperature

m

Specifiche

ðscrivere un programma che consente ad un centro di meteorologia di gestire le

temperature rilevate giornalmente ðmantenendo l’archivio su file

ðaggiungere nuove temperature rilevate ðeliminare rilevazioni scorrette

ðmodificare valori rilevati ðelaborare i dati

>> gestioneTemperature1.cpp

>> listaDiReali1.cpp

(8)

Archivio di Temperature

m

La libreria

ðcontiene il codice per la gestione della lista

m

Idea fondamentale

ðutilizzare un array per contenere gli elementi della lista

ðl’array può essere anche parzialmente pieno ðviene utilizzata una variabile (indicatore di

riempimento) per tenere traccia dell’occupazione effettiva

Archivio di Temperature

const int MAXDIM = 100;

struct lista {

int indicatore;

float valori[MAXDIM];

};

void main() { lista l;

...

}

massima capienza per la lista

array che contiene gli elementi della lista indicatore di

riempimento dell’array

(9)

Archivio di Temperature

m

Indicatore di riempimento

ðvariabile intera che dice quanti elementi contiene in quel momento la lista

ðpuò assumere valori tra 0 (lista vuota) e MAXDIM (lista completamente piena)

ðdeve essere gestita nel programma in modo tale che il suo valore rispecchi sempre il numero di elementi della lista

ðquesto è responsabilità del programmatore

18

Archivio di Temperature

void leggi (lista &l) { int i;

cout << "Quanti valori

contiene la lista ? ";

cin >> l.indicatore;

for (i = 0; i < l.indicatore ; i++) { cin >> l.valori[i];

}

return;

}

I operazione:

lettura del numero di elementi

II operazione:

lettura degli elementi il ciclo è guidato dal valore dell’indicatore

(10)

Archivio di Temperature

void stampa (lista l) { int i;

cout << "Valori della lista" << endl;

if (l.indicatore == 0) {

cout << "Lista vuota" << endl;

} else {

for (i = 0; i < l.indicatore; i++) { cout << l.valori[i] << endl;

} }

return;

}

è necessario distinguere il caso in cui la lista è vuota

il ciclo di stampa è guidato dall’indicatore

Archivio di Temperature

void aggiungiInCoda (lista &l, float elem, bool &esito){

if (l.indicatore == MAXDIM) { esito = false;

} else {

l.valori[l.indicatore] = elem;

l.indicatore++;

esito = true;

}

return;

}

è necessario distingure il caso in cui la lista è completamente piena

se c’è spazio, il nuovo elemento viene inserito nella prima posizione libera e cresce l’indicatore

(11)

Alcuni Esempi

m

La libreria

ðil codice per la gestione della lista è riutilizzabile in tutte le applicazioni che gestiscono liste di reali

ðtipico caso in cui è opportuno creare una libreria

ðnota: la libreria presentata è una versione semplificata della tipica libreria per la gestione di liste (>>)

22

Il Gioco del Lotto

m Specifiche

ðdati i 5 numeri estratti su una ruota del Lotto (es:

Roma), acquisire dalla tastiera i dati di una giocata ðverificare che la giocata sia corretta, ovvero: (a) sia

fatta al più di 5 numeri; (b) i numeri siano tutti diversi;

(c) i numeri siano tutti compresi tra 1 e 90 ðse la giocata è corretta, verificare se contiene

almeno un numero superiore a 80

ðe calcolare e stampare il punteggio della giocata rispetto ai numeri estratti

>> lotto1.cpp

(12)

Il Gioco del Lotto

m

Utilizzo della libreria: piccole forzature

ðgiocata: un insieme di numeri interi di

dimensione variabile

ðrappresentato attraverso una struttura di dati pensata per liste di numeri reali

ðvantaggio: riutilizzo del codice ðestrazione: lista di numeri interi di

dimensione fissata (si può usare un array) ðanche in questo caso il vantaggio è il riuso

Alcuni Esempi

m

In altri casi

ðla libreria non è immediatamente utilizzabile perché il programma utilizza una collezione di oggetti diversi

m

Esempio

ðl’archivio degli studenti universitari

ðin questi casi sono comunque riutilizzabili le stesse tecniche, ma devono essere

riprogrammate

(13)

Studenti Universitari

m

Specifiche

ðdato un archivio di studenti universitari dell’Università della Basilicata, memorizzato su file

ðacquisire i dati degli studenti ðstampare i dati sullo schermo

ðeffettuare la ricerca dei dati di uno studente sulla base della sua matricola

ðaggiungere i dati di un nuovo studente

>> studenti1.cpp

26

Studenti Universitari

struct studente { int matricola;

string cognome, nome;

int annoCorso;

};

const int N = 100;

struct listaStudenti { int indicatore;

studente dati[N];

};

massima capienza per la lista

array che contiene gli elementi della lista;

gli elementi sono di tipo studente indicatore di

riempimento dell’array

(14)

Riassumendo

m

Panoramica

ðLa lista

m

Alcuni Esempi

ðArchivio di Temperature ðIl Gioco del Lotto

ðStudenti Universitari

Strutture di Dati: Introduzione >> Sommario

Termini della Licenza

m This work is licensed under the Creative Commons Attribution- ShareAlike License. To view a copy of this license, visit

http://creativecommons.org/licenses/by-sa/1.0/ or send a letter to Creative Commons, 559 Nathan Abbott Way, Stanford, California 94305, USA.

Termini della Licenza

m Questo lavoro viene concesso in uso secondo i termini della licenza “Attribution-ShareAlike” di Creative Commons. Per ottenere una copia della licenza, è possibile visitare

http://creativecommons.org/licenses/by-sa/1.0/ oppure inviare una lettera all’indirizzo Creative Commons, 559 Nathan Abbott Way, Stanford, California 94305, USA.