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 b

versione 2.4

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

Sommario

m Inserimenti e Cancellazioni

m Utilizzo dei Sottoprogrammi

m Lista di Record

Strutture di Dati: Lista >> Sommario

(2)

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

Inserimenti e Cancellazioni

m Due possibili casi

ðinserimento o cancellazione in coda ðinserimento o cancellazione in posizione

stabilita

m Inserimento in coda

ðsemplice, purché la lista non sia piena

m Cancellazione in coda

ðsemplice, purché la lista non sia vuota

Strutture di Dati: Lista >> Inserimenti e Cancellazioni

Inserimenti e Cancellazioni

m In generale

ðè necessario uno strumento per sapere, nel modulo chiamante se, al termine della

chiamata, l’operazione è stata effettuata o meno

m Il parametro “esito”

ðparametro per riferimento utilizzato nella procedura per segnalare se l’op. è avvenuta (esito vale true) o meno (esito vale false)

ATTENZIONE

all’utilizzo del

parametro esito

(3)

Inserimento in Coda

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;

}

void main() { lista l;

float elem;

bool esito;

...

aggiungiInCoda(l, elem, esito);

}

xxx

#204

xxx

#203 elem 10

#98

l.valori[2] 7

#104 l

l.valori[3] -1

#105

l.valori[4] 234

#106

... ...

...

xxx

#202 esito xxx

#99

l.valori[99] -923

#201

l.valori[1] 4.5

#103

l.valori[0] 3

#102

l.valori #102

#101

l.indicatore 4

#100 5

10 true

l elem esito

#100 10

#99

Cancellazione in Coda

void eliminaInCoda (lista &l, bool& esito){

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

} else {

l.indicatore--;

esito = true;

} return;

}

#203

l.valori[2] 7

#104 l

l.valori[3] -1

#105

l.valori[4] 10

#106

... ...

...

xxx

#202 esito xxx

#99

l.valori[99] -923

#201

l.valori[1] 4.5

#103

l.valori[0] 3

#102

l.valori #102

#101

l.indicatore 5

#100 4

true

l esito

#100

#99

(4)

Inserimenti e Cancellazioni

m Inserimento in posizione stabilita ðdata la lista <3, 4.5, 7, -1, 10>, inserire

l’elemento 20 in posizione 2

ðè necessario verificare se l’inserimento è fattibile (lista non piena e posizione esistente) ðse sì, è necessario preliminarmente spostare tutti gli elementi nelle posizioni successive in basso

ðe poi inserire il nuovo elemento in posiz. 2

Inserimenti e Cancellazioni

m Attenzione

ðlo spostamento in basso deve essere fatto a partire dall’ultimo elemento e andando a ritroso

m Esempio di spostamento scorretto ðinserire 20 in pos. 2 in <3, 4.5, 7, -1, 10>

ðsposto la pos. 2 in pos. 3: <3, 4.5, 7, 7, 10>

ðsposto la pos. 3 in pos. 4: <3, 4.5, 7, 7, 7>

ðsposto la pos. 4 in pos. 5: <3, 4.5, 7, 7, 7, 7>

(5)

Inserimento

void aggiungiInPos(lista &l, float elem, int pos, bool &esito) {

int i;

if (l.indicatore == MAXDIM ||

!posAmmessa(l,pos)) esito = false;

else {

for (i = l.indicatore - 1;

i >= pos; i--) {

l.valori[i+1] = l.valori[i];

}

l.valori[pos] = elem;

l.indicatore++;

esito = true;

} return;

}

xxx

#206

xxx

#205

xxx

#204

xxx

#203

l.valori[5] 78

#107 elem 20

#98 pos 2

#97

l.valori[2] 7

#104 l

l.valori[3] -1

#105

l.valori[4] 10

#106

... ...

...

xxx

#202 esito xxx

#99

l.valori[99] -923

#201

l.valori[1] 4.5

#103

l.valori[0] 3

#102

l.valori #102

#101

l.indicatore 5

#100 6

10 true

4 -1 7 20

32

i=4: l.valori[5]=l.valori[4];

l elem

esito

#100 20

#99

pos 2

i 1

Controllo della Posizione

bool posAmmessa (lista l, int pos){

bool ammessa;

if (l.indicatore == 0) { ammessa = false;

} else {

ammessa = (pos >= 0 && pos < l.indicatore);

}

return ammessa;

}

se la lista è vuota nessuna posizione è ammessa

altrimenti sono ammesse le posizioni

comprese tra 0 e indicatore-1

(6)

Inserimenti e Cancellazioni

m Cancellazione in posizione stabilita

ðdata la lista <3, 4.5, 7, -1, 10>, supponiamo di voler cancellare l’elemento in posizione 2 ðè necessario verificare se la cancellazione è

possibile (lista non vuota e posiz. corretta) ðse sì, per produrre il risultato <3, 4.5, -1, 10>

bisogna spostare di una posizione più in alto tutti gli elementi da pos fino a indicatore-1 ðlo spostamento si può fare in avanti

Cancellazione

void eliminaInPosizione(lista &l, int pos, bool& esito){

int i;

if (!posAmmessa(l, pos)){

esito = false;

} else {

for(i = pos;

i < l.indicatore - 1; i++){

l.valori[i] = l.valori[i+1];

}

l.indicatore--;

esito = true;

} return;

}

i xxx

#205 esito #99

#204 pos 2

#203 pos 2

#97

l.valori[5] 78

#107 ... ...

#98

l.valori[2] 7 l

#104

l.valori[3] -1

#105

l.valori[4] 10

#106

... ...

...

l #100

#202 esito xxx

#99

l.valori[99] -923

#201

l.valori[1] 4.5

#103

l.valori[0] 3

#102

l.valori #102

#101

l.indicatore 5

#100 4

10 true

2 -1

34

(7)

I Prototipi della Libreria

const int MAXDIM=100;

struct lista { int indicatore;

float valori[MAXDIM];

};

void leggi (lista &l);

void leggiIndicatore (int &indicatore);

void stampa (lista l);

void salvaSuDisco (lista l, string nomeFile);

void carica (lista &l, string nomeFile);

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

void aggiungiInPosizione (lista &l, float elem, int pos, bool& esito);

void eliminaInCoda (lista &l, bool& esito);

void eliminaInPosizione (lista &l, int pos, bool& esito);

int cercaPosizione (lista l, float elem);

bool posizioneEsistente (lista l, int pos);

>> listaDiReali1.h commenti

Utilizzo dei Sottoprogrammi

m Sottoprogrammi su una struttura di dati ðapplicabili solo in alcuni casi

ðbisogna distinguere i casi particolari (eccezioni) es: lista vuota, lista piena...

m Nel caso delle procedure

ðla verifica dell’applicabilità viene fatta all’interno (es: parametro “esito”)

ðè sempre possibile chiamare la procedura e poi verificare se ha avuto esito positivo

Strutture di Dati: Lista >> Utilizzo dei Sottoprogrammi

(8)

Utilizzo dei Sottoprogrammi

m Nel caso delle funzioni

ðle funzioni devono calcolare un valore ðse il valore non è calcolabile chiamare la

funzione non ha senso

ðin questi casi è necessario verificare nel modulo chiamante se la funzione è applicabile

ðverifica preventiva

G. Mecca - Programmazione Procedurale in Linguaggio C++ 16 void main() {

lista l;

int scelta; float elem;

bool esito, continua = true;

l.indicatore = 0;

while (continua) { ...

if (scelta == 6) { leggiValore(elem);

aggiungiInCoda(l, elem, esito);

if (esito) { cout << “Operazione effettuata\n” } else { cout << “ERRORE: Operazione scorretta\n” } }

if (scelta==11) {

if (l.indicatore>0) { elabora(l);

cout << “Operazione effettuata";

} else {

cout << "Errore. Lista vuota.\n";

} } ...

(9)

Utilizzo dei Sottoprogrammi

m Riassumendo

ðnelle procedure è possibile concentrare i controlli sulla correttezza all’interno

ðnelle funzioni no; la verifica deve essere fatta all’esterno

m In effetti, però

ðanche per le procedure a volte ha senso fare controlli all’esterno per ragioni di usabilità; es:

inserimento in una posizione inesistente

Utilizzo dei Sottoprogrammi

m In generale, in un’applicazione

ðquando si scrive un sottoprogramma, bisogna studiare le condizioni in cui è applicabile correttamente (“precondizioni”) ðaccertarsi che il sottoprogramma venga

eseguito solo se le precondizioni sono soddisfatte

ðe poi verificare che i risultati siano corretti (“postcondizioni”) attraverso i test

(10)

Lista di Record

m Finora

ðlista di numeri reali

ðelementi di un tipo di base

m In altri casi

ðla lista è fatta di elementi che sono record ðesempio: l’archivio di studenti

ðle tecniche sono le stesse, ma devono essere riprogrammate caso per caso

Strutture di Dati: Lista >> Lista di Record

Lista di Record

struct studente { int matricola;

string cognome, nome;

int annoCorso;

};

const int N=100;

struct listaStudenti { int indicatore;

studente dati[N];

};

(11)

Lista di Studenti

void stampa(listaStudenti studenti){

int i;

cout << "Dati degli studenti\n";

if (studenti.indicatore == 0) { cout << "Lista vuota\n\n";

} else {

for (i = 0; i < studenti.indicatore; i++) { stampaDatiStudente(studenti.dati[i]);

} } return;

}

void stampaDatiStudente(studente s){

cout << "Matricola: " << s.matricola << endl;

cout << "Cognome: " << s.cognome << endl;

cout << "Nome: " << s.nome << endl;

cout << "Anno: " << s.annoCorso << endl;

return;

}

Lista di Studenti

void aggiungiInCoda(listaStudenti &studenti, studente s, bool &esito){

if (studenti.indicatore == N) { esito = false;

} else {

studenti.dati[studenti.indicatore] = s;

studenti.indicatore++;

esito = true;

} return;

}

(12)

Lista di Studenti

int cercaPosizione(listaStudenti studenti, int matricola){

int pos, i;

bool trovato = false;

pos = -1;

i = 0;

while (!trovato && i < studenti.indicatore) { if (studenti.dati[i].matricola == matricola){

pos = i;

trovato = true;

} else { i++;

} }

return pos;

}

Lista di Studenti

int cercaPosizione(listaStudenti studenti, int matricola){

int i;

for (i = 0; i < studenti.indicatore; i++) { if (studenti.dati[i].matricola == matricola){

return i;

} }

return -1;

}

(13)

Riassumendo

m Inserimenti e Cancellazioni

m Utilizzo dei Sottoprogrammi

m Lista di Record

Strutture di Dati: Lista >> 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