Programmazione Procedurale in Linguaggio C++

(1)

G. Mecca – Università della Basilicata – mecca@unibas.it

Programmazione Procedurale in Linguaggio C++

Strutture di Dati La Lista – parte a

versione 2.3

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

Sommario

m

Introduzione

m

Definizione di Lista

m

Rappresentazione con Record e Array

m

Operazioni sulla Lista

m

Lettura e Stampa

m

Ricerca

m

Altre Elaborazioni

Strutture di Dati: Lista >> Sommario

(2)

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

Introduzione

m

La lista

ðè la struttura di dati fondamentale

ðutilizzabile in tutti i casi in cui è necessario programmare su collezioni di valori

ðutilizzabile anche per insiemi e multiinsiemi

m

In questa lezione

ðne diamo una definizione semplificata ðrappresentazione con record e array

ðesistono altre possibili rappresentazioni (>>)

Strutture di Dati: Lista >> Introduzione

Definizione di Lista

m

Definizione dell’oggetto matematico lista

ðuna sequenza (o serie) di zero o più elementi

tutti dello stesso tipo

ðil numero di elementi contenuti è detto lunghezza della lista

m

Esempio

ðuna lista di numeri: <3, 4.5, 7, -1> - lista di lunghezza 4

ðla lista vuota: <> - lista di lunghezza zero

Strutture di Dati: Lista >> Definizione di Lista

(3)

Definizione di Lista

m

Proprietà della lista

ðgli elementi sono accessibili sulla base della loro posizione nella lista

m

Esempio: <3, 4.5, 7, -1>

ðelemento in posizione 0: 3 ðelemento in posizione 1: 4,5 ðelemento in posizione 2: 7 ðelemento in posizione 3: -1

ðelemento in posizione 4: ERRORE

Definizione di Lista

m

Proprietà della lista (continua)

ðla lista può cambiare dimensione a seguito di inserimenti e cancellazioni

m

Esempio: <3, 4.5, 7, -1>

ðinserisci 10 in posizione 2: <3, 4.5, 10, 7, -1>

ðelimina in posizione 1: <3, 10, 7, -1>

ðinserisci 20 in coda: <3, 10, 7, -1, 20>

ðelimina in coda: <3, 10, 7, -1>

(4)

Definizione di Lista

m

Attenzione agli errori; es: <3, 10, 7, -1>

ðinserisci in posizione 5: ERRORE ðelimina in posizione 4: ERRORE ðelimina in posizione -1: ERRORE

m

Attenzione alle condizioni limite

ðnon è possibile eliminare da una lista vuota ðnon è possibile inserire se la lista ha

raggiunto la capienza massima (caso pratico)

Definizione di Lista

m

Operazioni fondamentali sulla lista

ðrestituisci il valore dell’elemento in posiz. p ðinserisci un elemento x in posizione p

caso particolare: inserisci in fondo alla lista ðelimina l’elemento in posizione p

caso particolare: elimina in fondo alla lista ðcerca la posizione dell’elemento di valore x

(5)

Definizione di Lista

m

Altre operazioni

ðci sono altre operazioni rilevanti in pratica ðsono esprimibili in termini di quelle fondam.

m

Esempio

ðcambia il valore dell’elemento in posizione p assegnandogli x

ðelimino in posizione p e poi inserisco x in posizione p

ðin pratica però non ha senso fare così

Definizione di Lista

m

In concreto

ðin molti problemi è possibile rappresentare i dati come una lista di elementi

ðe manipolarli attraverso le relative operazioni

m

Di conseguenza

ðla scelta della rappresentazione è

semplificata adottandone una standard e i relativi algoritmi

ðin alcuni casi, addirittura una libreria pronta

(6)

Definizione di Lista

m

Nel linguaggio

ðsono possibili varie rappresentazioni di una lista di oggetti

m

Rappresentazioni principali

ðrecord, array e indicatore di riempimento:

meno flessibile ma più semplice

ðrecord e puntatori (>>): più flessibile ma più complessa (gestione della memoria)

ðper ora studieremo la prima

Rappresentazione con Record e Array

m

Idea

ðgli elementi sono contenuti in un array (dimensione massima fissata)

ðgli indici dell’array corrispondono alle posizioni

ðl’array può essere utilizzato parzialmente ðviene utilizzato un indicatore di riempimento

per segnalare quanti sono gli elementi della lista

Strutture di Dati: Lista >> Rappresentazione con Record e Array

(7)

Rappresentazione con Record e Array

m

Indicatore di riempimento

ðpuò assumere valori compresi tra 0 e MAXDIM

ðse vale 0, la lista è vuota

ðse vale MAXDIM, la lista è completam. piena ðin ogni momento, il numero di componenti

utilizzate dell’array corrisponde al valore dell’indicatore

ðdeve essere manipolato con attenzione

ATTENZIONE ai valori dell’indicatore

Rappresentazione con Record e Array

const int MAXDIM = 100;

struct lista { int indicatore;

float valori[MAXDIM];

};

void main() { lista l;

...

}

l.valori[2] xxx l

#104

l.valori[3] xxx

#105

l.valori[4] xxx

#106

... ...

...

xxx

#202

xxx

#99

l.valori[99] xxx

#201

l.valori[1] xxx

#103

l.valori[0] xxx

#102

l.valori #102

#101

l.indicatore xxx

#100

(8)

Operazioni sulla Lista

m

Nel seguito

ðverranno illustrate le principali operazioni su una lista di numeri

ðlettura dalla tastiera ðstampa sullo schermo

ðlettura e scrittura su da e su file ðricerche

ðinserimenti ðcancellazioni

Strutture di Dati: Lista >> Operazioni sulla Lista

Operazioni sulla Lista

m

Attenzione

ðnelle operazioni, è necessario tenere in conto vari aspetti

m

Problema n.1

ðgestire correttamente il valore dell’indicatore di riempimento

m

Problema n.2

ðverificare la correttezza delle operazioni (lista vuota, lista piena, posizioni corrette ecc.)

(9)

Operazioni sulla Lista

m

Inizializzazione della lista

ðappena dichiarata l’indic. ha valore indefinito ðper preparare la lista all’utilizzo è possibile

assegnare all’indicatore il valore 0

l.indicatore = 0;

...

}

Lettura e Stampa

m

Lettura dalla tastiera

ðacquisisco per cominciare il numero di elementi (valore dell’indicatore)

ðpoi utilizzo un ciclo per la lettura comandato dal valore dell’indicatore

m

Stampa sullo schermo

ðbasta utilizzare un ciclo comandato dal valore dell’indicatore

Strutture di Dati: Lista >> Lettura e Stampa

(10)

Lettura da Tastiera

void leggi (lista &l) { int i;

cout << “Quanti valori ?”;

cin >> l.indicatore;

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

} return;

}

leggi (l);

...

}

xxx

#203

l.valori[2] xxx

#104 l

l.valori[3] xxx

#105

l.valori[4] xxx

#106

... ...

...

xxx

#202

xxx

#99

l.valori[99] xxx

#201

l.valori[1] xxx

#103

l.valori[0] xxx

#102

l.valori #102

#101

l.indicatore xxx

#100 4

Quanti valori ? 4 3 4.5 7 -1

3 4.5 7 -1

l #100

i 01234

Lettura e Stampa

m

Lettura dell’indicatore

ðconviene utilizzare una procedura, in modo da poter fare anche la convalida

void leggiIndicatore (int &ind) { cout << "Quanti valori ? ";

cin >> ind;

while ((ind < 0) || (ind > MAXDIM)) { cout << "ERRORE" << endl;

cout << "Immetti valore corretto: ";

cin >> ind;

} return;

}

(11)

Lettura e Stampa

m

Procedura per la lettura da tastiera

ðversione finale

void leggi (lista &l) { int i;

leggiIndicatore (l.indicatore);

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

} return;

}

Stampa a Schermo

void stampa (lista l) { int i;

cout << "Valori:" << endl;

if (l.indicatore == 0) cout << "Lista vuota\n“;

else

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

return;

}

leggi (l);

stampa (l);

...

}

... ...

...

#304

#303 ...

#208

#207

#206

#205

#204

#203

#202

l.valori[0] 3

#102 l

-923 l.valori[99]

#201

l.valori #102

#101

l.indicatore 4

#100

Valori:

3 4.5 7 -1

i xxx

l.valori[2] 7 l

l.valori[3] -1 l.valori[4] 234 ... ...

l.valori[99] -923 l.valori[1] 4.5 l.valori[0] 3 l.valori #204 l.indicatore 4

(12)

Ricerca

m

Problema

ðrisalire da un valore alla sua eventuale posizione nella lista

m

Specifica in dettaglio

ðdato un valore reale, cercarlo nella lista ðse il valore è presente, restituirne la

posizione (in caso ci siano varie occorrenze, restituire la posizione della prima)

ðse il valore non è presente, restituire -1

Strutture di Dati: Lista >> Ricerca

ATTENZIONE all’utilizzo del valore

speciale -1

Ricerca

m

Idea

ðfino a prova contraria il valore non esiste (risultato = -1)

ðscandisco linearmente la lista con un ciclo e confronto ogni elemento con quello cercato ðse trovo l’elemento, cambio il risultato

m

Fermata del ciclo

ðcaso a: l’elemento è stato trovato ðcaso b: la lista è terminata

(13)

Ricerca

m

Condizione del ciclo

ðutilizzo una variabile intera (i) per la scansione

ðe un flag per controllare se l’elemento è stato trovato

ðil ciclo deve andare avanti finchè ci sono ancora elementi (i < l.indicatore)

ðe contemporaneamente il valore cercato non è stato trovato (trovato == false o !trovato)

Ricerca

int cercaPosizione (lista l, float elem) { int i;

bool trovato = false;

int risultato = -1;

i = 0;

while (i < l.indicatore && !trovato) { if (l.valori[i] == elem){

trovato = true;

risultato = i;

} else { i++;

} }

return risultato;

}

ricerca di 7 in <3, 4.5, 7, -1>

il ciclo si ferma, risultato vale 2

risultato trovato

l.valori[i]

elem i

-1 false 3

7 0

-1 false 4.5

7 1

2 true 7

7 2

inizialmente: trovato=false, risultato=-1

(14)

Ricerca

bool trovato = false;

int risultato = -1;

i = 0;

while (i < l.indicatore && !trovato) { if (l.valori[i] == elem){

trovato = true;

risultato = i;

} else { i++;

} }

return risultato;

}

ricerca di 15 in <3, 4.5, 7, -1>

i=4, il ciclo si ferma, risultato vale -1

risultato trovato

l.valori[i]

elem i

-1 false -1

15 3

-1 false 3

15 0

-1 false 4.5

15 1

-1 false 7

15 2

inizialmente: trovato=false, risultato=-1

Ricerca

m

Una versione corretta ma inefficiente

ðutilizza un ciclo for e non un while

ðscandisce sempre la lista fino in fondo

int risultato = -1;

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

risultato = i;

} }

return risultato;

(15)

Ricerca

m

Una versione più efficiente con for

ðsfrutta la possibilità di inserire in un

sottoprogramma più di un’istruzione di ritorno

m

Istruzione di ritorno (return)

ðinterrompe l’esecuzione del sottoprogramma ðpuò essercene più di una

ðpuò essere utilizzata per semplificare il flusso di controllo in alcuni casi

ðes: interrompere un ciclo senza usare il flag

Ricerca

for(i = 0; i < l.indicatore; i++){

if (l.valori[i] == elem){

return i;

} }

return -1;

}

questa istruzione interrompe il sottoprogramma e restituisce il valore di i

(16)

Ricerca

m

Vantaggi

ðil codice si semplifica

ðè possibile utilizzare il for e non il while

m

Attenzione però

ðsi tratta di un esempio di “programmazione non strutturata” (modulo con più di un punto di uscita)

ðva bene solo per sottoprogrammi molto brevi e con al massimo due-tre istruzioni di ritorno

ATTENZIONE all’utilizzo del

return

Altre Elaborazioni

m

Nell’applicazione

ðcalcolo della media ðconteggio valori negativi ðmassimo e minimo

ðsi utilizzano le tecniche note

m

Differenza fondamentale

ðutilizzare l’indicatore di riempimento

Strutture di Dati: Lista >> Altre Elaborazioni

(17)

G. Mecca - Programmazione Procedurale in Linguaggio C++ 33 float calcolaMedia(lista l){

float somma, media;

int i;

somma = 0;

for(i=0;i<l.indicatore; i++){

somma += l.valori[i];

}

media = somma / l.indicatore;

return media;

}

int posizioneMax(lista l){

int i, pos = 0

for(i=1;i<l.indicatore;i++){

if (l.valori[i]>

l.valori[pos]) { pos = i;

} }

return pos;

}

int contaNegativi(lista l){

int i;

int conta = 0;

for (i = 0;i < l.indicatore; i++){

if(l.valori[i] < 0) { conta++;

} }

return conta;

}

int posizioneMin(lista l){

int i;

int pos = 0;

for(i = 1; i < l.indicatore; i++){

if(l.valori[i] < l.valori[pos]){

pos = i;

} }

return pos;

} Strutture di Dati: Lista >> Altre Elaborazioni

Riassumendo

m

Introduzione

m

Definizione di Lista

m

Rappresentazione con Record e Array

m

Operazioni sulla Lista

m

Lettura e Stampa

m

Ricerca

m

Altre Elaborazioni

Strutture di Dati: Lista >> Sommario

(18)

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.