Strutture/Array e pila/coda in C++

Strutture di dati
Una struttura è un insieme finito di variabili (dette campi) non
necessariamente dello stesso tipo, ognuna identificata con un nome
l’insieme dei campi è denominato record
Laboratorio di Informatica
sintassi
struct nome_struttura {
tipo1 nome_variabile1;
.........
tipon nome_variabilen;
}
5. Strutture / Array di oggetti / Pila&Coda in C++
La struttura definisce un nuovo tipo di dato
Corso di Laurea in Ingegneria Elettronica e Telecomunicazioni
A.A. 2013-2014
2° Semestre
Prof. Giovanni Pascoschi
Laboratorio di Informatica – A.A. 2013-2014
Strutture di dati
2
Strutture di dati
Dopo aver definito una variabile struttura, si accede ai singoli campi
mediante la notazione . (punto)
i campi di una struttura possono essere usati come qualunque variabile
dello stesso tipo
Una volta definito un tipo dati struttura, essa si comporta come
un qualsiasi altro tipo di dati. Si puo’ ad esempio:
assegnare una variabile struttura ad un’altra
far si’ che una funzione restituisca una struttura alla funzione
chiamante
passare strutture sia per valore che per referenza (riferimento)
esempio:
cd.prezzo=10;
cout<<cd.titolo;
cd.copie++;
Laboratorio di Informatica – A.A. 2013-2014
a cura di Pascoschi Giovanni
a cura di Pascoschi Giovanni
3
Laboratorio di Informatica – A.A. 2013-2014
a cura di Pascoschi Giovanni
4
Esempi strutture di dati
Tabelle di dati
La tabella di dati è un array di strutture
daticd cd1 = {“Toccata e fuga”, “Bach”, 30, sinfonia };
//uguaglianza tra strutture
daticd cd2 = cd1;
struct giorno {
int gg;
int mm;
int aa;
};
void stampa_cd(daticd x) {
// passaggio per valore
cout<<“x.autore<<x.titolo<<x.prezzo<<x.genere<<endl;
}
void prezzo_scontato(daticd& x) {
x.prezzo=x.prezzo * 80/100;
}
Laboratorio di Informatica – A.A. 2013-2014
struct daticd {
string titolo;
string autore;
float prezzo;
string genere;
struct giorno giorno_vendita;
};
struct daticd CD[100]; // tabella costituita da 100 CD
// passaggio per referenza
a cura di Pascoschi Giovanni
5
Istruzione typedef
a cura di Pascoschi Giovanni
6
Accesso agli elementi di una Tabella
per poter descrivere in maniera piu’ concisa un tipo struttura si puo’ usare la
parola chiave typedef
struct giorno {
int gg;
int mm;
int aa;
};
L’indice di una tabella puo’ essere una espressione costante intera o
comunque una qualsiasi espressione intera
Esempio di caricamento di una tabella:
for (int i=0; i< 500; i++) {
cin >> CD[i].titolo>> CD[i].autore >> CD[i].prezzo>> CD[i].genere;
cin >> CD[i].vendita.gg >> CD[i].vendita.mm >> CD[i].vendita.aa ;
}
struct daticd {
string titolo;
string autore;
float prezzo;
string genere;
struct giorno vendita;
};
typedef struct daticd cddata; //non definisce un nuovo tipo, ma un sinonimo!!!!
cddata CD[100]; // tabella costituita da 100 CD
Laboratorio di Informatica – A.A. 2013-2014
Laboratorio di Informatica – A.A. 2013-2014
a cura di Pascoschi Giovanni
7
Laboratorio di Informatica – A.A. 2013-2014
a cura di Pascoschi Giovanni
8
Array di oggetti
Strutture dati complesse
#include<iostream>
using namespace std;
class Persona {
public:
int id_persona;
int anno_nasc;
Persona() {
id_persona = 0;
anno_nasc = 0;
}
Persona(int id_pers, int anno) {
id-persona = id-pers;
anno_nasc = anno;
}
void stampa() {
cout <<id-persona << " " << anno_nasc << "\n";
}
};
Esempi di strutture dati complesse in C++:
int main() {
const int dim = 10;
Pila (Stack)
Coda (queue)
Liste semplici (semplicemente linkate) (in seguito)
Liste doppie (doppiamente linkate) (in seguito)
Persona a[dim];
// richiede il costruttore di default
for (int i = 0; i < dim; i++) {
a[i].id_persona = i;
cin>>a[i].anno_nasc;
}
for (int i = 0; i < dim; i++) {
a[i].stampa();
}
system("pause");
}
Laboratorio di Informatica – A.A. 2013-2014
9
a cura di Pascoschi Giovanni
Pila (Stack) con array
Laboratorio di Informatica – A.A. 2013-2014
a cura di Pascoschi Giovanni
10
Pila (Stack) con array
la Pila (Stack) è un insieme di dati che permette l’inserimento di nuovi
elementi e l’estrazione degli elementi introdotti da un’unica estremità
L’implementazione di una pila puo’ essere fatta tramite un array
(dimensione fissa)
push
pop
il funzionamento della pila viene denominato LIFO (Last Input First Output)
testa = 0
meccanismo utilizzato per gestire le chiamate alle funzioni (insieme degli
indirizzi di rientro) oppure nel registro di stack (linguaggio assembly)
operazione di inserimento di un dato
operazione di estrazione di un dato
A[0]
A[1]
push
A[2]
pop
.......
A[MAX-1]
testa = MAX
Laboratorio di Informatica – A.A. 2013-2014
a cura di Pascoschi Giovanni
11
Laboratorio di Informatica – A.A. 2013-2014
a cura di Pascoschi Giovanni
12
Esempio Pila
Esempio Pila
do {
menu( );
cout<<“Seleziona una voce”;
cin>>scelta;
} while(scelta <1 || scelta >5);
switch(scelta) {
case 1:
clearPila( );
break;
case 2:
pop( );
break;
case 3:
push( );
break;
case 4:
readPila( );
break;
}
}while(scelta !=5);
return 0;
#include <iostream>
using namespace std;
const int MAX = 20;
int Pila[MAX];
int testa;
void clearPila( );
void pop( );
void push( );
void readPila( );
void menu( );
int main( )
{
int scelta;
clearPila( );
do {
void pop( ) {
if( testa == MAX)
cout<<“La pila e’ vuota. Impossibile estrarre un dato”<< endl;
else{
cout << “Elemento estratto = “ << Pila[testa] << endl;
testa++;
}
}
void push( ) {
int dato;
if (testa == 0)
cout<<“La pila è piena. Impossibile inserire altri dati”<< endl;
else{
cout << “dato da inserire = “;
cin>> dato;
testa- -;
Pila[testa] = dato;
}
}
}
Laboratorio di Informatica – A.A. 2013-2014
a cura di Pascoschi Giovanni
13
Esempio Pila
a cura di Pascoschi Giovanni
14
Coda (Queue) con array
la Coda (Queue) è un insieme di dati che permette l’inserimento di nuovi
elementi da una parte e l’estrazione degli elementi introdotti dalla parte
opposta
void clearPila( ) {
testa = MAX;
cout<< “Pila vuota” << endl;
}
void readPila( ) {
for(int i=testa; i< MAX; i++) {
cout<< Pila[i] << endl;
}
}
il funzionamento della coda viene denominato FIFO (First Input First
Output)
operazione di inserimento di un dato
operazione di estrazione di un dato
void menu( ) {
cout << endl;
cout << “1. Pulisci pila” << endl;
cout << “2. Estrai un dato” << endl;
cout << “3. Aggiungi un dato” << endl;
cout << “4. Leggi pila” << endl;
cout << “5. Fine” << endl;
}
Laboratorio di Informatica – A.A. 2013-2014
Laboratorio di Informatica – A.A. 2013-2014
a cura di Pascoschi Giovanni
15
Laboratorio di Informatica – A.A. 2013-2014
push
pop
a cura di Pascoschi Giovanni
16
Coda (Queue) con array
Esempio Coda
L’implementazione di una coda puo’ essere fatta tramite un array
(dimensione fissa)
A[0]
A[1]
A[MAX-1]
pop
push
void clearCoda( );
void pop( );
void push( );
void readCoda( );
void menu( );
.........
fine = MAX-1
fine = -1
do {
menu( );
cout<<“Seleziona una voce”;
cin>>scelta;
} while(scelta <1 || scelta >5);
switch(scelta) {
case 1:
clearCoda( );
break;
case 2:
pop( );
break;
case 3:
push( );
break;
case 4:
readCoda( );
break;
}
}while(scelta !=5);
return 0;
#include <iostream>
using namespace std;
const int MAX = 20;
int Coda[MAX];
int fine;
int main( )
{
int scelta;
clearCoda( );
do {
}
Laboratorio di Informatica – A.A. 2013-2014
a cura di Pascoschi Giovanni
17
Esempio Coda
a cura di Pascoschi Giovanni
18
a cura di Pascoschi Giovanni
20
Esempio Coda
void pop( ) {
if( fine ==-1)
cout<<“La coda e’ vuota. Impossibile estrarre un dato”<< endl;
else{
cout << “Elemento estratto = “ << Coda[0] << endl;
for(int i=1; i<= fine; i++) Coda[i-1] = Coda[i];
fine- -;
}
}
void clearCoda( ) {
fine = -1;
cout<< “Coda vuota” << endl;
}
void readCoda( ) {
for(int i=0; i<= fine; i++) {
cout<< Coda[i] << endl;
}
}
void push( ) {
int dato;
if (fine == MAX-1)
cout<<“La coda è piena. Impossibile inserire altri dati”<< endl;
else{
cout << “dato da inserire = “;
cin>> dato;
fine++;
Coda[fine] = dato;
}
}
Laboratorio di Informatica – A.A. 2013-2014
Laboratorio di Informatica – A.A. 2013-2014
a cura di Pascoschi Giovanni
void menu( ) {
cout << endl;
cout << “1. Pulisci coda” << endl;
cout << “2. Estrai un dato” << endl;
cout << “3. Aggiungi un dato” << endl;
cout << “4. Leggi coda” << endl;
cout << “5. Fine” << endl;
}
19
Laboratorio di Informatica – A.A. 2013-2014
Riepilogo della lezione
Fine della lezione
Funzioni in C++
Strutture di dati
Tabelle di dati
Array di oggetti
Pila/Coda con array
Laboratorio di Informatica – A.A. 2013-2014
Domande?
a cura di Pascoschi Giovanni
21
Laboratorio di Informatica – A.A. 2013-2014
a cura di Pascoschi Giovanni
22