Fondamenti di Informatica IIIcorsiadistanza.polito.it/corsi/pdf/9255N/fondinf3-03.pdf · 2000. 11....

Gianluca Cena

Fondamenti di Informatica III

GIANLUCA CENA FONDAMENTI DI INFORMATICA III

1

Obiettivi del corso

• Fornire un compendio ai corsi di informatica di base, inerente i principali modelli computazionali

teorici, le tecniche di programmazione, gli algoritmi e le strutture dati più importanti.

• Introdurre i concetti fondamentali della programmazione orientata agli oggetti, che verranno ripresi

ed approfonditi nei corsi successivi.


2

Programma del corso

Il corso si compone fondamentalmente di quattro parti:

• Modelli teorici dell’Informatica.

• Tecniche di programmazione ed algoritmi.

• Strutture dati.

• Programmazione orientata agli oggetti.

Libri di testo

[F&S] B. Fadini e C. Savy “Fondamenti di Informatica per il Diploma Universitario”, Liguori

Editore, Napoli, 1994 (facoltativo, serve ad integrazione delle cassette).

[K&R] B. W. Kernighan, D. M. Ritchie, “Linguaggio C (ANSI C)”, Gruppo Editoriale Jackson, 1989

(facoltativo, serve solo per approfondire gli argomenti relativi a puntatori ed allocazione

dinamica in C).

[COR] T. H. Cormen, C. E. Leiserson, R. L. Rivest “Algorithms” (facoltativo e non necessario per

sostenere l’esame, indicato solo per chi voglia approfondire con maggiore dettaglio la parte di

algoritmi e strutture dati).

[TIC] Bruce Eckel “Thinking in C++”, second edition (disponibile gratuitamente in formato

elettronico sul sito http://www.bruceeckel.com - per la programmazione orientata agli oggetti

va comunque bene un qualunque libro recente).

Avvertenza

Le presenti dispense non sostituiscono in alcun modo le videocassette del corso, ma ne integrano i

contenuti con gli aspetti più pratici che caratterizzano i tutorati in aula.


3

Lezione 1 - Modelli teorici dell’Informatica (I)

• Automi a stati finiti: definizione ed esempi d’uso.

• Macchina di Turing: definizione, calcolabilità, tesi di Church.

Riferimenti

Videocassette: lezioni 22, 23, 24, 25.

Testi: [F&S] capitolo 1.


4

Automa

Un automa a stati finiti M è definito come una quintupla di entità:

M = ( Q, I, U, t, w )

dove:

• Q è l’insieme (finito) degli stati interni q ( Qq ∈ );

• I è l’insieme finito degli ingressi i ( Ii ∈ ), detti anche eventi;

• U è l’insieme finito delle uscite u ( Uu ∈ ), dette anche azioni;

• t è la funzione di transizione ( QIQt →×: ) che ad ogni coppia stato corrente – ingresso associa il

nuovo stato;

• w è la funzione delle uscite.

Esistono due tipi di automi, che si differenziano per la funzione delle uscite:

• automi di Mealy, dove l’uscita dipende dallo stato corrente e dall’ingresso ( UIQw →×: );

• automi di Moore, dove l’uscita dipende unicamente dallo stato corrente ( UQw →: ).

Si può dimostrare che i due tipi di automa sono equivalenti.

Diagramma degli stati

Formalismo grafico utilizzato per rappresentare automi a stati finiti. I diagrammi a stati sono

sostanzialmente dei grafi orientati in cui:

• ad ogni nodo corrisponde un diverso stato q;

• ad ogni vertice corrisponde una transizione, etichettata con l’evento che la ha causata (ingresso i).

Il seguente diagramma a stati rappresenta un automa di Mealy. In tal caso, ogni transizione è etichettata

da una coppia ingresso/uscita (o, equivalentemente, evento/azione).

q1 q2

q3

i1 / u2

i1 / u3 i2 / u2

i3 / u1

i2 / u3


5

Il diagramma a stati che segue rappresenta invece un automa di Moore (diverso dal precedente). In

questo caso l’uscita dipende unicamente dallo stato corrente e può quindi essere specificata

direttamente nei diversi nodi.

q1/u1 q2/u3

q3/u1

i1

i1 i2

i3

i2

In nessun caso è possibile avere transizioni diverse uscenti dallo stesso nodo ed etichettate con lo stesso

ingresso, poiché ciò renderebbe l’automa non deterministico.

Esempio

Automa che riceve in ingresso una sequenza di simboli binari e riconosce il pattern 01001:

q0/0

q1/0

q2/0

0

1

q3/0

0

q4/0

q5/1

0

1

0 1

1 0

0

1

1


6

Macchina di Turing

È sostanzialmente un automa in cui sono definiti in modo opportuno gli ingressi e le uscite (azioni

elaborative). In particolare, la macchina di Turing definisce un concetto di nastro sul quale si muove

una testina che può leggere e scrivere dati e che funge contemporaneamente da dispositivo di I/O e da

memoria.

Calcolabilità

Si indichi con:

• t il contenuto iniziale del nastro;

• d(T) la descrizione di una macchina di Turing, definita in termini di: posizione iniziale della testina

sul nastro, descrizione dell’automa di controllo e stato iniziale di tale automa.

• t’ il contenuto finale del nastro.

Una macchina di Turing che trasforma il contenuto iniziale del nastro t nel contenuto finale t’ e che

termina rappresenta un algoritmo (funzione Y = f(X), che elabora i dati in ingresso X e produce i dati in

uscita Y).

In tal caso è possibile identificare d(T) con la funzione f, mentre il contenuto iniziale del nastro e quello

finale contengono, rispettivamente, i dati in ingresso X e quelli in uscita Y opportunamente codificati.

Tesi di Church

Questa tesi (non dimostrata ma mai smentita) dice che non esiste formalismo né macchina concreta che

possa calcolare una funzione che non è calcolabile secondo Turing.

Si noti che questo non esclude che vi siano macchine calcolatrici più efficienti della macchina di

Turing (ed infatti le macchine reali solitamente hanno un’efficienza molto maggiore della macchina di

Turing).


7

Lezione 2 - Modelli teorici dell’Informatica (II)

• Modello di Von Neumann e struttura delle macchine calcolatrici.

• Grammatiche e linguaggi: definizione di grammatica, compilatori e interpreti.

• BNF ed EBNF: definizione ed esempi d’uso.

• Diagrammi sintattici per la definizione di linguaggi.

Riferimenti

Videocassette: lezioni 26, 27, 28 (cenni), 29.



8

Processo di traduzione

Il processo di traduzione di un programma è costituito dalle seguenti fasi:

• analisi lessicale: per il riconoscimento delle componenti elementari del programma (identificatori,

operatori, parole riservate, costanti numeriche, ecc.);

• analisi sintattica: per il riconoscimento delle frasi del programma, ovvero della sua struttura (frasi

esecutive e frasi dichiarative);

• analisi semantica: partendo dall’analisi sintattica, l’analisi semantica procede alla generazione del

codice oggetto per il programma in esame.

Grammatiche

La sintassi S (detta anche grammatica) di un linguaggio di programmazione L è data dagli elementi V,

U, I e P, dove:

• V è il vocabolario dei simboli terminali (detto anche alfabeto o vocabolario base);

• U è il vocabolario dei simboli non terminali (indicati anche con il termine variabili

metalinguistiche);

• I è il simbolo iniziale della sintassi, che appartiene all’insieme U;

• P è l’insieme delle regole di produzione.

Il linguaggio L generato dalla grammatica S è l’insieme delle stringhe costituite da simboli appartenenti

all’insieme V che possono essere ottenute applicando le regole di produzione P a partire dal simbolo

iniziale non terminale I.

Forma di Backus Naur (BNF)

Formalismo per descrivere le regole di produzione. Utilizza i seguenti simboli metalinguistici:

< var > indica una variabile metalinguistica di nome var appartenente a U; ad esempio:

<cifra>, <lettera>, <identificatore>, ecc.

::= introduce una regola di produzione, ovvero definisce una variabile metalinguistica in

termini di simboli appartenenti a U o a V; ad esempio:<selezione> ::= if ( <condizione> ) <istruzione>

| viene utilizzato per introdurre una scelta nella parte destra di una regola di produzione; ad

esempio:<cifra> ::= 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9


9

Esempio di uso della forma BNF

Si scriva una grammatica per descrivere gli identificatori così come sono definiti nel linguaggio C.

Il simbolo iniziale è <identificatore>, mentre le regole di produzione sono

<cifra> ::= 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9<minuscola> ::= a | b | c | … | x | y | z<maiuscola> ::= A | B | C | … | X | Y | Z<underscore> ::= _<lettera> ::= <minuscola> | <maiuscola> | <underscore><identificatore> ::=

<identificatore><lettera>|<identificatore><cifra>|<lettera>

Forma BNF estesa (EBNF)

Introduce i seguenti formalismi aggiuntivi al fine di semplificare la forma BNF evitando l’uso della

recursione:

[ t ] indica opzionalità (t può comparire 0 o 1 volta)

{ t } indica ripetibilità (t può comparire un numero arbitrario di volte, anche nessuna)

{ t }n indica ripetibilità limitata (t può comparire da 0 a n volte)

dove t indica un simbolo di U o di V o una sequenza di tali simboli.

Esempio di uso della forma EBNF

Si scriva una grammatica per descrivere gli identificatori così come sono definiti nel linguaggio C,

assumendo una lunghezza massima di 16 caratteri.

Il simbolo iniziale è <identificatore>, mentre le regole di produzione sono:

<cifra> ::= 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9<minuscola> ::= a | b | c | … | x | y | z<maiuscola> ::= A | B | C | … | X | Y | Z<underscore> ::= _<lettera> ::= <minuscola> | <maiuscola> | <underscore><identificatore> ::= <lettera> { <lettera> | <cifra> }15


10

Lezione 3 - Modelli teorici dell’Informatica (III)

• Algebra booleana: definizione formale e teoremi.

• Semplificazione algebrica di funzioni logiche,

• Forme SP (somma di prodotti) e PS (prodotto di somme),

• Minimizzazione di espressioni,

• Progetto di funzioni logiche,

• Mappe di Karnaugh,

• Condizioni di don’t care.

Riferimenti

Videocassette: lezioni 30, 31, 32, 33, 34 (cenni), 35 (cenni).



11

Mappe di Karnaugh

( ) dbdcbaf ⋅=,,,

( ) cbadbdcbaf ⋅⋅+⋅=,,,

( ) badbdcbaf ⋅+⋅=,,,

00 01 11 10

00

01

11

10

1 1

1 1

c d a b

00

01

11

10

00 01 11 10

1 1 1

1 1

c d a b

00 01 11 10

00

01

11

10

1 1 1 1

1 1

1 1

c d a b


12

( ) dcbbadcbaf ⋅⋅+⋅=,,,

( ) dcbdcadbadcbaf ⋅⋅+⋅⋅+⋅⋅=,,,

( ) bdcbaf =,,,

00

01

11

10

00 01 11 10

1 1 1 1

1

1

c d a b

00

01

11

10

00 01 11 10

1

1 1

1

c d a b

00 01 11 10

00

01

11

10

1 1 1 1

1 1 1 1

c d a b


13

( ) dbdcbaf ⋅=,,,

Condizioni di don’t care

A volte, la specifica della funzione da realizzare non è completa, ovvero non viene stabilito il valore

dell’uscita per una o più combinazioni degli ingressi. Queste condizioni si dicono di don’t care e si

indicano sulla mappa di Karnaugh con il simbolo ‘-’ (trattino). Esse possono essere utilizzate per

semplificare ulteriormente l’espressione logica finale.

Esempio: realizzare un circuito che riceve in ingresso su 4 bit (a3 a2 a1 a0) una variabile A codificata su

una cifra in BCD e fornisce in uscita un valore vero se il valore di A è compreso fra 3 e 7 (estremi

inclusi), escluso il 6. Dal momento che A è una cifra BCD, essa non potrà assumere valori superiori a 9.

Quindi, i valori dal 10 in su possono essere descritti da una condizione di don’t care in quanto

sappiamo a priori che essi non potranno mai apparire all’ingresso del circuito realizzato.

00

01

11

10

00 01 11 10

1 1

1 1

c d a b

00

01

11

10

00 01 11 10

1

1 1 1

- - - -

- -

x1 x0 x3 x2

0 1 3

4 5 7 6

C D F E

8 9 B A

2


14

Nella mappa è stato indicato per chiarezza in ogni casella anche il valore di A. Al fine di minimizzare la

complessità dell’espressione risultante, appare chiaro che le condizioni di don’t care devono essere

risolte nel modo seguente:

La copertura della mappa risultante dà luogo alla seguente espressione logica:

( ) 01120123 ,,, xxxxxxxxf ⋅+⋅=

00

01

11

10

00 01 11 10

1

1 1 1

- (1)

- (1)

- (1)

- (0)

- (1)

- (0)

x1 x0 x3 x2

0 1 3

4 5 7 6

C D F E

8 9 B A

2

00

01

11

10

00 01 11 10

1

1 1 1

(1) (1) (1)

(1)

x1 x0 x3 x2


15

Lezione 4 - Tecniche di programmazione ed algoritmi (I)

• Programmazione strutturata: costrutti di sequenza, scelta e iterazione, teorema di Bohm-Jacopini.

• Approccio top-down e bottom-up per la stesura di algoritmi.

• Compendio sul linguaggio di programmazione C.

• Puntatori in C: equivalenza fra puntatori e vettori, aritmetica dei puntatori.

• Allocazione dinamica della memoria in C: malloc(), calloc() e free().

Riferimenti

Testi: [F&S] capitoli 5 e 6 (per i concetti generali).

[K&R] capitoli 5, 6 e appendice B (per i dettagli sul linguaggio C).

Sorgenti C: directory ALG1.


16

Costrutti della programmazione

Esistono fondamentalmente tre tipi di costrutti che possono essere utilizzati nell’ambito dei programmi

sequenziali:

• sequenza;

• selezione;

• iterazione.

Costrutto di sequenza

Corrisponde in linguaggio C alla forma:

{ s1(); s2(); s3(); }

dove s1(), s2() e s3() sono operazioni qualsiasi.

S1

S2

S3

Costrutto di selezione (scelta)

Corrisponde in linguaggio C alla forma:

if ( c() )sv();

elsesf();

dove sv() e sf() sono due operazioni qualsiasi e c() è una espressione (condizione).


17

SF SV

C V F

Costrutto di iterazione (ripetizione)

Ve ne sono di due tipi: il primo (a volte detto anche ciclo while… do o con test in cima) corrisponde in

linguaggio C alla forma:

while ( c() )s();

dove s() rappresenta una operazione qualsiasi e c() è una espressione (condizione).

S

C

V

F

Il secondo (a volte detto anche ciclo repeat…until o con test in coda), invece, corrisponde in linguaggio

C alla forma:

dos();

while ( c() );


18

S

C V

F

È possibile dimostrare che i due tipi di costrutti di iterazione si equivalgono.

Programmazione strutturata

Un programma si dice essere in forma strutturata quando utilizza solamente i tre costrutti di sequenza,

selezione e iterazione.

Teorema di Bohm-Jacopini

Il Teorema di Bohm-Jacopini dice sostanzialmente che ogni programma può essere descritto in forma

strutturata.


19

Esempio di uso dei puntatori in C

/*Esempio di uso dei puntatori.

*/

#include <stdio.h>

int i, j; /* due variabili di tipo intero */int *pi, *pj; /* due variabili di tipo puntatore ad intero */

void main(){

i=1;j=2;printf("Esempio di uso dei puntatori in C:\n");

pi=&i; /* & operatore di indirizzo: variabile -> indirizzo */pj=&j;printf("i=%d, j=%d\n", i, j);printf("pi=%p, pj=%p\n", pi, pj);printf("*pi=%d, *pj=%d\n", *pi, *pj);

pi=&j;pj=&i;printf("i=%d, j=%d\n", i, j);printf("pi=%p, pj=%p\n", pi, pj);printf("*pi=%d, *pj=%d\n", *pi, *pj);

*pi=3; /* * operatore di indirezione: indirizzo -> variabile */*pj=4;printf("i=%d, j=%d\n", i, j);printf("pi=%p, pj=%p\n", pi, pj);printf("*pi=%d, *pj=%d\n", *pi, *pj);

}/* ---------------- OUTPUT --------------------Esempio di uso dei puntatori in C:i=1, j=2pi=03D8, pj=03D6*pi=1, *pj=2i=1, j=2pi=03D6, pj=03D8*pi=2, *pj=1i=4, j=3pi=03D6, pj=03D8*pi=3, *pj=4---------------------------------------------*/

Equivalenza fra vettori e puntatori

/*Programma che mostra l'equivalenza fra puntatori e vettori

*/

# include <stdio.h>

#define NMAX 10

void main(){

int a[NMAX]; /* vettore di interi */int *p; /* puntatore a interi */int i;


20

/* inizializza gli elementi del vettore */for(i=0; i<NMAX; i++)

a[i]=i+100; /* inizializzazione arbitraria */

printf("Equivalenza fra vettori e puntatori:\n");printf("a[3] = %d\n", a[3]);printf("*a = %d\n", *a);printf("*(a+1) = %d\n", *(a+1));printf("*p = %d\n", *p);p=a;printf("p[3] = %d\n", p[3]);printf("*p = %d\n", *p);printf("*(p+1) = %d\n", *(p+1));printf("*p++ = %d\n", *p++);printf("*p = %d\n", *p);printf("p[3] = %d\n", p[3]);

}/*------------- Output --------------Equivalenza fra vettori e puntatori:a[3] = 103*a = 100*(a+1) = 101*p = 767p[3] = 103*p = 100*(p+1) = 101*p++ = 100*p = 101p[3] = 104-----------------------------------*/

Matrici bidimensionali e puntatori

/*Analisi delle modalita' per memorizzare una matrice bidimensionale

*/

#include <stdio.h>#include <stdlib.h>

#define NR 3#define NC 4

void main( void ){

int m1[NR][NC]; /* implementazione statica */int *m2; /* area allocata dinamicamente */int **m3; /* vettore di puntatori */int i, j;char s[10];

/* allocazione dinamica di m2 */m2=(int *)calloc(NC*NR, sizeof(int));

/* allocazione dinamica di m3 (vettore di puntatori) */m3=(int **)calloc(NR, sizeof(int *));for(i=0; i<NR; i++)

m3[i]=(int *)calloc(NC, sizeof(int)); /* alloca ogni singola riga */

/* inizializzazione delle tre matrici */for(i=0; i<NR; i++)

for(j=0; j<NC; j++) {m1[i][j] = 10*i+j;


21

m2[i*NC+j] = 10*i+j; /* calcolo esplicito dell'indirizzo */m3[i][j] = 10*i+j;}

printf("Memorizzazione ed accesso ad una matrice bidimensionale.\n");

/* matrice m1 */printf("Matrice m1, metodo di accesso 1:\n");printf("m1[%d][%d] parte da %p e gli indirizzi dei suoi elementi sono:\n",

NR, NC, m1);for(i=0; i<NR; i++) {

for(j=0; j<NC; j++)printf("%p[%2d] ", &m1[i][j], m1[i][j]);

printf("\n");}

printf("Matrice m1, metodo di accesso 2:\n");printf("m1[%d][%d] parte da %p e gli indirizzi dei suoi elementi sono:\n",

NR, NC, m1);for(i=0; i<NR; i++) {

for(j=0; j<NC; j++)printf("%p[%2d] ", *m1+NC*i+j, *(*m1+NC*i+j));

printf("\n");}


NR, NC, m1);for(i=0; i<NR; i++) {

for(j=0; j<NC; j++)printf("%p[%2d] ", (int *)m1+NC*i+j, *((int *)m1+NC*i+j));

printf("\n");}


NR, NC, m1);for(i=0; i<NR; i++) {

for(j=0; j<NC; j++)printf("%p[%2d] ", *(m1+i)+j, *(*(m1+i)+j));

printf("\n");}


NR, NC, m2);for(i=0; i<NR; i++) {

for(j=0; j<NC; j++)printf("%p[%2d] ", m2+NC*i+j, *(m2+NC*i+j));

printf("\n");}


NR, NC, m2);for(i=0; i<NR; i++) {

for(j=0; j<NC; j++)printf("%p[%2d] ", &m2[NC*i+j], m2[NC*i+j]);

printf("\n");}



22

NR, NC, m3);for(i=0; i<NR; i++) {

printf("[%p]\t", m3[i]);for(j=0; j<NC; j++)

printf("%p[%2d] ", &m3[i][j], m3[i][j]);printf("\n");}


NR, NC, m3);for(i=0; i<NR; i++) {

printf("[%p]\t", m3[i]);for(j=0; j<NC; j++)

printf("%p[%2d] ", *(m3+i)+j, *(*(m3+i)+j));printf("\n");}

}/* -------------------------- OUTPUT ---------------------------------------Memorizzazione ed accesso ad una matrice bidimensionale.Matrice m1, metodo di accesso 1:m1[3][4] parte da FFD0 e gli indirizzi dei suoi elementi sono:FFD0[ 0] FFD2[ 1] FFD4[ 2] FFD6[ 3]FFD8[10] FFDA[11] FFDC[12] FFDE[13]FFE0[20] FFE2[21] FFE4[22] FFE6[23]Matrice m1, metodo di accesso 2:m1[3][4] parte da FFD0 e gli indirizzi dei suoi elementi sono:FFD0[ 0] FFD2[ 1] FFD4[ 2] FFD6[ 3]FFD8[10] FFDA[11] FFDC[12] FFDE[13]FFE0[20] FFE2[21] FFE4[22] FFE6[23]Matrice m1, metodo di accesso 3:m1[3][4] parte da FFD0 e gli indirizzi dei suoi elementi sono:FFD0[ 0] FFD2[ 1] FFD4[ 2] FFD6[ 3]FFD8[10] FFDA[11] FFDC[12] FFDE[13]FFE0[20] FFE2[21] FFE4[22] FFE6[23]Matrice m1, metodo di accesso 4:m1[3][4] parte da FFD0 e gli indirizzi dei suoi elementi sono:FFD0[ 0] FFD2[ 1] FFD4[ 2] FFD6[ 3]FFD8[10] FFDA[11] FFDC[12] FFDE[13]FFE0[20] FFE2[21] FFE4[22] FFE6[23]

Matrice m2, metodo di accesso 1:m2[3][4] parte da 093A e gli indirizzi dei suoi elementi sono:093A[ 0] 093C[ 1] 093E[ 2] 0940[ 3]0942[10] 0944[11] 0946[12] 0948[13]094A[20] 094C[21] 094E[22] 0950[23]Matrice m2, metodo di accesso 2:m2[3][4] parte da 093A e gli indirizzi dei suoi elementi sono:093A[ 0] 093C[ 1] 093E[ 2] 0940[ 3]0942[10] 0944[11] 0946[12] 0948[13]094A[20] 094C[21] 094E[22] 0950[23]

Matrice m3, metodo di accesso 1:m3[3][4] parte da 0956 e gli indirizzi dei suoi elementi sono:[0960] 0960[ 0] 0962[ 1] 0964[ 2] 0966[ 3][096C] 096C[10] 096E[11] 0970[12] 0972[13][0978] 0978[20] 097A[21] 097C[22] 097E[23]Matrice m3, metodo di accesso 2:m3[3][4] parte da 0956 e gli indirizzi dei suoi elementi sono:[0960] 0960[ 0] 0962[ 1] 0964[ 2] 0966[ 3][096C] 096C[10] 096E[11] 0970[12] 0972[13][0978] 0978[20] 097A[21] 097C[22] 097E[23]--------------------------------------------------------------------------*/


23

Lezione 5 - Tecniche di programmazione ed algoritmi (II)

• Definizione di complessità computazionale.

• Algoritmi di ordinamento a complessità quadratica: insertion sort, selection sort e bubble sort.

• Algoritmi di ricerca sui vettori: ricerca lineare e binaria (dicotomica) su vettore ordinato.

• Algoritmo di fusione (merge) fra vettori ordinati.

Riferimenti

Videocassette: lezioni 36, 37, 38.

Testi: [F&S] capitolo 4 (solo la complessità) e capitoli 7 e 10.



24

Algoritmo di ordinamento per selezione (selection sort)

/*Algoritmo di ordinamento per selezione (selection sort)

*/

#define MAXN 100

typedef int KEY; /* campo chiave */typedef char ATTR[20]; /* campo attributo */

typedef struct { /* elemento del vettore */KEY key;ATTR attr;} ITEM;

void ssort(ITEM v[], int n){

int i, j, k;ITEM x;

for (i=0; i<n-1; i++) {k=i;for (j=i+1; j<n; j++)

if (v[j].key < v[k].key)k=j;

x=v[i]; /* copia di strutture */v[i]=v[k];v[k]=x;}

}

/* Lettura del vettore */void readvect(ITEM v[], int n){

int i;

for (i=0; i<n; i++) {printf("Elemento [%2d]: ",i);scanf("%d %s", &v[i].key, v[i].attr);}

}

/* Stampa del vettore */void writevect(ITEM v[], int n){

int i;

for (i=0; i<n; i++)printf("(%d,%s) ",v[i].key, v[i].attr);

printf("\n");}

void main(){

ITEM vect[MAXN];int num;

printf("Selection sort\n");

/* lettura del vettore */printf("Numero di elementi del vettore: ");scanf("%d",&num);


25

printf("Introduci gli elementi del vettore (chiave e attributo):\n");readvect(vect, num);

/* stampa vettore iniziale */printf("Vettore iniziale: ");writevect(vect, num);

/* procedura di ordinamento */ssort(vect,num);

/* stampa vettore ordinato */printf("Vettore ordinato: ");writevect(vect, num);

}

Algoritmo di ordinamento per inserimento (insertion sort)

/*Algoritmo di ordinamento per inserimento (insertion sort)

*/

#include <stdio.h>

#define MAXN 100



void isort(ITEM v[], int n){

int i, j;ITEM x;

for (i=1; i<n; i++) {x=v[i];for (j=i-1; j>=0; j--)

if (v[j].key > x.key)v[j+1]=v[j]; /* copia di strutture */

elsebreak;

v[j+1]=x; /* copia di strutture */}

}


int i;

for (i=0; i<n; i++) {printf("Elemento [%2d]: ", i);scanf("%d %s", &v[i].key, v[i].attr);}

}



26

int i;


printf("\n");}

void main(){


printf("Insertion sort\n");

/* lettura del vettore */printf("Numero di elementi del vettore: ");scanf("%d", &num);printf("Introduci gli elementi del vettore (chiave e attributo):\n");readvect(vect, num);


/* procedura di ordinamento */isort(vect, num);


}

Algoritmo di ordinamento a bolle (bubble sort) con flag di scambio.

/*Algoritmo di ordinamento a bolle (bubble sort)- viene utilizzato un flag di scambio per migliorare le prestazioni

*/

#include <stdio.h>

#define MAXN 100

typedef enum {FALSE, TRUE} boolean;



void bsort(ITEM v[], int n){

int i, j;ITEM x;boolean swap;

for (i=n-1; i>0; i--) {swap=FALSE;


27

for (j=0; j<i; j++)if (v[j].key > v[j+1].key) { /* scambio necessario? */

swap=TRUE;x=v[j]; /* copia di strutture */v[j]=v[j+1];v[j+1]=x;}

if (!swap) /* se non c'e' stato uno scambio */break;

}}


int i;


}


int i;


printf("\n");}

void main(){


printf("Bubble sort\n");

/* lettura del vettore */printf("Numero di elementi del vettore: ");scanf("%d",&num);printf("Introduci gli elementi del vettore (chiave e attributo):\n");readvect(vect, num);


/* procedura di ordinamento */bsort(vect,num);


}


28

Algoritmo di fusione per vettori ordinati (merge):

/*Algoritmo di fusione per vettori ordinati (merge):- a partire da due vettori ordinati ne crea uno nuovo, ancora ordinato, contenente tutti gli elementi dei vettori in ingresso;- restituisce il numero di elementi nel vettore finale.

*/

#include <stdio.h>

#define MAXN 100



int merge(ITEM v1[], int n1, ITEM v2[], int n2, ITEM v3[]){

int i1=0;int i2=0;int i3=0;

while (i1<n1 && i2<n2) { /* fondi elementi da v1 e v2 */if (v1[i1].key < v2[i2].key)

v3[i3++]=v1[i1++];else

v3[i3++]=v2[i2++];}

while (i1 < n1) /* copia gli elementi rimanenti di v1 */v3[i3++]=v1[i1++];

while (i2<n2)/* copia gli elementi rimanenti di v2 */v3[i3++]=v2[i2++];

return n1+n2;}


int i;


}


int i;


printf("\n");}


29

/* Ordinamento generico */void sort(ITEM v[], int n){

int i,j;ITEM x;

for (i=0; i<n-1; i++)for (j=i+1; j<n; j++)

if (v[i].key > v[j].key) {x=v[j];v[j]=v[i];v[i]=x;}

}

void main(){

ITEM vect1[MAXN], vect2[MAXN];ITEM vect3[MAXN*2];int num1, num2, num3;

printf("Fusione di due vettori.\n");

/* lettura primo vettore */printf("Numero di elementi del primo vettore: ");scanf("%d", &num1);printf("Introduci gli elementi del primo vettore (chiave e attr.):\n");readvect(vect1, num1);

/* lettura secondo vettore */printf("Numero di elementi del secondo vettore: ");scanf("%d", &num2);printf("Introduci gli elementi del secondo vettore (chiave e attr.):\n");readvect(vect2, num2);

/* i vettori devono essere ordinati */sort(vect1, num1);sort(vect2, num2);

/* stampa vettori ordinati */printf("Primo vettore ordinato: ");writevect(vect1, num1);printf("Secondo vettore ordinato: ");writevect(vect2, num2);

/* esempio di chiamata a merge() */num3=merge(vect1, num1, vect2, num2, vect3);

/* stampa vettore finale */printf("Vettore finale: ");writevect(vect3, num3);

}

Algoritmo di ricerca lineare in un vettore

/*Algoritmo di ricerca lineare in un vettore:- restituisce la posizione dell'elemento quando lo trova;- restituisce -1 se non lo trova.

*/

#include <stdio.h>


30

#define MAXN 100



int lsearch(ITEM v[], int n, KEY k){

int i;

for (i=0; i<n; i++)if (v[i].key == k) /* elemento trovato */

return i;return -1; /* elemento non trovato */

}


int i;


}


int i;


printf("\n");}

void main(){

ITEM vect[MAXN];int num, l;KEY key;

printf("Ricerca lineare\n");

/* lettura del vettore */printf("Numero di Elementi: ");scanf("%d", &num);printf("Introduci gli elementi del vettore (chiave e attributo):\n");readvect(vect, num);

/* stampa vettore iniziale */printf("Vettore iniziale:");writevect(vect, num);

/* esempio di chiamata a lsearch() */for (;;) {

printf("Numero da ricercare (-1 termina): ");scanf("%d",&key);


31

if (key==-1)break;

l=lsearch(vect, num, key);if (l==-1)

printf("Elemento non trovato.\n");else

printf("Elemento (%d,%s) trovato in posizione [%d].\n",vect[l].key, vect[l].attr, l);

}}

Algoritmo di ricerca binaria (dicotomica) in un vettore ordinato

/*Algoritmo di ricerca binaria in un vettore ordinato (binary search):- restituisce la posizione dell'elemento quando lo trova;- restituisce -1 se non lo trova.

*/

#include <stdio.h>

#define MAXN 100



int bsearch(ITEM v[], int n, KEY k){

int l = 0;int r = n-1;int m;

while (l<=r) { /* partizione non vuota? */m=(l+r)/2; /* calcola il punto mediano */if (k > v[m].key) /* cerca nella seconda meta' [m+1,r] */

l=m+1;else if (k < v[m].key) /* cerca nella prima meta' [l,m-1] */

r=m-1;else /* v[m].key == k elemento trovato in posizione m */

return m;}

return -1; /* elemento non trovato */}


int i;


}



32

int i;


printf("\n");}

/* Ordinamento generico */void sort(ITEM v[], int n){

int i,j;ITEM x;

for (i=0; i<n-1; i++)for (j=i+1; j<n; j++)

if (v[i].key > v[j].key) {x=v[j];v[j]=v[i];v[i]=x;}

}

void main(){

ITEM vect[MAXN];int num, l;KEY key;

printf("Ricerca binaria\n");

/* lettura del vettore */printf("Numero di Elementi: ");scanf("%d", &num);printf("Introduci gli elementi del vettore (chiave e attributo):\n");readvect(vect, num);

/* stampa vettore iniziale */printf("Vettore iniziale:");writevect(vect, num);

/* il vettore deve essere ordinato */sort(vect, num);

/* stampa vettore ordinato */printf("Vettore ordinato:");writevect(vect, num);

/* esempio di chiamata a bsearch() */for (;;) {

printf("Numero da ricercare (-1 termina): ");scanf("%d",&key);if (key==-1)

break;l=bsearch(vect, num, key);if (l==-1)

printf("Elemento non trovato.\n");else

printf("Elemento (%d,%s) trovato in posizione [%d].\n",vect[l].key, vect[l].attr, l);

}}


33

Lezione 6 - Tecniche di programmazione ed algoritmi (III)

• Introduzione alle tecniche di programmazione recursive: definizione ed applicabilità.

• Algoritmi di ordinamento a complessità n·lg(n): quicksort, criteri di scelta del pivot.

• Esempi di uso della recursione: calcolo del fattoriale, soluzione del problema delle 8 regine

generalizzato, determinazione degli anagrammi di una parola data.

Riferimenti

Videocassette: lezione 38.

Testi: [F&S] capitolo 7 (recursione) e capitolo 10.



34

Algoritmo di calcolo del fattoriale

/*Programma per il calcolo del fattoriale- versione iterativa,- versione iterativa (ottimizzata),- versione recursiva.

*/

#include <stdio.h>

/* Prototipi */int ifatt(int);int ofatt(int);int rfatt(int);

/* Versione iterativa */int ifatt(int n){

int f=1;int i;

for(i=1; i<=n; i++)f=f*i;

return f;}

/* Versione iterativa ottimizzata */int ofatt(int n){

int f=1;

while(n>1)f*=n--;

return f;}

/* Versione recursiva */int rfatt(int n){

if (n==0)return 1;

elsereturn n*rfatt(n-1);

}

/* Programma pricipale */void main(){

int numero;

printf("Calcolo del fattoriale.\n");

printf("Introduci n: ");scanf("%d", &numero);

printf("Versione iterativa: ");printf("ifatt(%d) = %d\n", numero, ifatt(numero));printf("Versione ottimizzata: ");printf("ofatt(%d) = %d\n", numero, ofatt(numero));printf("Versione recursiva: ");printf("rfatt(%d) = %d\n", numero, rfatt(numero));

}


35

Algoritmo di ordinamento per partizionamento (quicksort)

/*Algoritmo di ordinamento per partizionamento (quicksort)

*/

#include <stdio.h>

#define MAXN 100



void qsort(ITEM v[], int n);void quicksort(ITEM v[], int l, int h);void readvect(ITEM v[], int n);void writevect(ITEM v[], int n);void writepart(char *s, ITEM v[], int l, int h);

void quicksort(ITEM v[], int low, int high){

int l, h;ITEM x;KEY pivot;

writepart("I", v, low, high); /* situazione iniziale */

if(low<high) { /* la partizione contiene almeno 2 elementi */l=low;h=high+1;pivot=v[low].key; /* il pivot e' il primo elemento della partiz. */

while(l<h) {while(l<high && v[++l].key <= pivot)

; /* cerca da sx il primo elemento maggiore del pivot */while(v[--h].key > pivot)

; /* cerca da dx il primo elemento inferiore al pivot */if(l<h) { /* se i due indici non sono invertiti */

x=v[l]; /* scambia i due elementi */v[l]=v[h];v[h]=x;}

}x=v[low]; /* sposta il pivot fra la partizione sx */v[low]=v[h]; /* e partizione dx */v[h]=x;

writepart("P", v, low, high); /* dopo il partizionamento */

quicksort(v, low, h-1); /* ordina la partizione sx */quicksort(v, h+1, high); /* ordina la partizione dx */

writepart("O", v, low, high); /* dopo la chiamata recursiva */}

}

void qsort(ITEM v[], int n){

quicksort(v, 0, n-1);


36

}


int i;


}


int i;


printf("\n");}

/* Stampa di una partizione del vettore */void writepart(char *s, ITEM v[], int l, int h){

int i;

printf("Vettore (%s): ", s);for(i=0; i<=h; i++)

if(i>=l)printf(" %3d ",v[i]);

elseprintf(" ");

printf("\n");}

void main(void){


printf("Quicksort\n");

/* lettura del vettore */printf("Numero di Elementi: ");scanf("%d",&num);printf("Introduci gli elementi del vettore (chiave e attributo):\n");readvect(vect, num);


/* procedura di ordinamento */qsort(vect, num);


}


37

Problema delle 8 regine generalizzato (prima versione)

/*Problema delle 8 regine:- disporre 8 regine su una scacchiera in modo tale che nessuna di esse possa essere mangiata dalle altre;- il programma lista tutte le possibili configurazioni che rispettano tali vincoli;- generalizza il problema al caso di N regine su una scacchiera di lato N;- utilizza un metodo euristico: sicuramente non si possono avere due regine sulla stessa colonna;

- utilizza una matrice per memorizzare la scacchiera.*/

#include <stdio.h>

#define SIZE 10

int m[SIZE][SIZE]; /* scacchiera */int cnt=0; /* contatore di configurazioni */

void stampa(int m[SIZE][SIZE], int n){

int i,j;

for(i=0; i<n; i++) {for(j=0; j<n; j++)

printf(" %c", m[i][j]?'X':'.');printf("\n");}

}

/*Funzione recursiva che tenta di piazzare una nuova reginanella colonna c in modo che non venga mangiata dalle altre

*/void piazzaregina(int m[SIZE][SIZE], int n, int c){

int r, i, j;int bad;char s[80];

for(r=0; r<n; r++) { /* prova in ogni riga r */m[r][c]=1; /* metti una regina in r,c*/bad=0;for(j=0; j<c; j++) /* controllo orizzontale */

if(m[r][j]==1) {bad=1;break;}

if(bad) {m[r][c]=0; /* togli la regina da (r,c) */continue;}

for(j=c-1, i=r-1; j>=0 && i>=0; j--, i--) /* controllo diagonale */if(m[i][j]==1) {

bad=1;break;}



38

for(j=c-1, i=r+1; j>=0 && i<n; j--, i++) /* controllo diagonale */if(m[i][j]==1) {

bad=1;break;}


/* a questo punto una regina e' stata piazzata con successo */

if(c==n-1) { /* se ho piazzato l'ultima regina */printf("Configurazione %d\n",++cnt);stampa(m,n);printf("Altra configurazione ... ");gets(s);}

else { /* piazza un'altra regina */piazzaregina(m, n, c+1);}

m[r][c]=0; /* togli la regina da r,c */}

}

void main(){

int lato;char s[80];

printf("Problema delle 8 regine generalizzato.\n");

printf("Lato della scacchiera: ");gets(s);sscanf(s, "%d", &lato);

piazzaregina(m, lato, 0);printf("Esistono %d configurazioni distinte.\n", cnt);

}

Problema delle 8 regine generalizzato (seconda versione)

/*Problema delle 8 regine:- disporre 8 regine su una scacchiera in modo tale che nessuna di esse possa essere mangiata dalle altre;- il programma lista tutte le possibili configurazioni che rispettano tali vincoli;- generalizza il problema al caso di N regine su una scacchiera di lato N;- utilizza un metodo euristico: sicuramente non si possono avere due regine sulla stessa colonna;

- utilizza una matrice per memorizzare la scacchiera.*/

#include <stdio.h>

#define SIZE 10

int m[SIZE][SIZE]; /* scacchiera */int cnt=0; /* contatore di configurazioni */

void stampa(int m[SIZE][SIZE], int n){


39

int i,j;

for(i=0; i<n; i++) {for(j=0; j<n; j++)

printf(" %c", m[i][j]?'X':'.');printf("\n");}

}

/*Funzione recursiva che tenta di piazzare una nuova reginanella colonna c in modo che non venga mangiata dalle altre

*/void piazzaregina(int m[SIZE][SIZE], int n, int c){

int r, i, j;int bad;char s[80];

for(r=0; r<n; r++) { /* prova in ogni riga r */m[r][c]=1; /* metti una regina in r,c*/bad=0;for(j=0; j<c; j++) /* controllo orizzontale */

if(m[r][j]==1) {bad=1;break;}


for(j=c-1, i=r-1; j>=0 && i>=0; j--, i--) /* controllo diagonale */if(m[i][j]==1) {

bad=1;break;}


for(j=c-1, i=r+1; j>=0 && i<n; j--, i++) /* controllo diagonale */if(m[i][j]==1) {

bad=1;break;}


/* a questo punto una regina e' stata piazzata con successo */

if(c==n-1) { /* se ho piazzato l'ultima regina */printf("Configurazione %d\n",++cnt);stampa(m,n);printf("Altra configurazione ... ");gets(s);}

else { /* piazza un'altra regina */piazzaregina(m, n, c+1);}

m[r][c]=0; /* togli la regina da r,c */}

}


40

void main(){

int lato;char s[80];

printf("Problema delle 8 regine generalizzato.\n");

printf("Lato della scacchiera: ");gets(s);sscanf(s, "%d", &lato);

piazzaregina(m, lato, 0);printf("Esistono %d configurazioni distinte.\n", cnt);

}

Anagrammi (prima versione)

/*Stampa gli anagrammi di una parola data senza ripetizionie senza memorizzare le parole gia' stampate;- gestisce parole fino a SIZE-1 caratteri;- alfabeto di dimensione qualsiasi;- una un vettore di flag per indicare quali caratteri sono gia' stati utilizzati.

*/

#include <stdio.h>

#define FREE 0#define USED 1

#define SIZE 10

/*Funzione che azzera il vettore dei flag

*/void clear(char f[], int n){

int i;

for(i=0; i<n; i++)f[i]=FREE;

}

/*Funzione recursiva che aggiunge un nuovo carattere (in posizione c)all'anagramma a in corso di costruzione

*/void add(char w[], char f[], char a[], int c){

int i, j;int repeated;

if(w[c]!='\0') { /* sono stati considerati tutti i caratteri in w[]?*/

/* cerca un carattere non ancora usato di w[] */for(i=0; w[i]!='\0'; i++) {

if(f[i]==USED) /* se il carattere e' gia' utilizzato */continue; /* passa al carattere successivo

*/

/* un carattere uguale a w[i] e' gia' stato utilizzato? */repeated=0;


41

for(j=0; j<i; j++)if(w[i]==w[j] && f[j]==FREE) {

repeated=1;break;}

if(repeated) /* per evitare le ripetizioni */continue; /* passa al carattere successivo */

/* prova ad aggiungere un altro carattere */a[c]=w[i];f[i]=USED;add(w, f, a, c+1);f[i]=FREE;} /* end for */

}else { /* anagramma completato */

a[c]='\0'; /* aggiungi terminatore di stringa */puts(a); /* stampa l'anagramma ottenuto */}

}

void main(){

char word[SIZE]; /* parola iniziale */char anag[SIZE]; /* anagramma */char flag[SIZE]; /* vettore di flag */

printf("Anagrammi.\n");

printf("Introduci una parola: ");gets(word);

clear(flag, SIZE); /* azzera il vettore dei flag */printf("Anagrammi:\n");add(word, flag, anag, 0); /* stampa tutti gli anagrammi di word */

}

Anagrammi (seconda versione)

/*Stampa gli anagrammi di una parola data senza ripetizionie senza memorizzare le parole gia' stampate;- usa un vettore per conteggiare le frequenze;- e' piu'facile;- alfabeto limitato.

Date: 14 Jan 2000Author: G. Cena

*/

#include <stdio.h>

#define SIZE 10 /* dimensione massima della parola */#define ASIZE256 /* dimensione dell'alfabeto */

/*genera la statistica dei caratteri di s[] (frequenza) in f[] e restituiscela lunghezza della stringa

*/int stat(char s[], int f[]){

int i, l;


42

for(i=0; i<ASIZE; i++) /* azzera le frequenze*/

f[i]=0;for(l=0; s[l]!='\0'; l++) /* conta le occorrenze dei car. in s[] */

f[s[l]]++;return l; /* l e' la lunghezza di s[]*/

}

/*aggiunge un carattere in posizione n nell'anagramma a prelevandolodal pool di caratteri disponibili descritto da f[]

*/void add(int f[], char a[], int l, int n){

int c;

if(n<l) /* altri caratteri da aggiungere? */for(c=0; c<ASIZE; c++) { /* controlla tutti i caratteri */

if(f[c]>0) { /* il carattere e' disponibile?*/

a[n]=c; /* lo appendo all'anagramma*/

f[c]--;add(f, a, l, n+1); /* prova ad aggiungere un altro car.*/f[c]++;}

}else { /* anagramma trovato */

a[n]='\0'; /* aggiungi terminatore di stringa */puts(a); /* stampa l'anagramma */}

}

void main(){

int len;char word[SIZE]; /* parola iniziale */char anag[SIZE]; /* anagramma */int freq[ASIZE]; /* vettore di occorrenze */

printf("Anagrammi.\n");

printf("Introduci una parola: ");gets(word);

printf("Anagrammi:\n");len=stat(word, freq); /* calcola la freq. dei simboli dell'alfabeto */add(freq, anag, len, 0); /* stampa tutti gli anagrammi di word */

}


43

Lezione 7 - Strutture dati (I)

• Vettori allocati staticamente e dinamicamente, stringhe.

• Lista linkata: definizione e caratteristiche.

• Operazioni search, insert e delete su una lista ordinata.

Riferimenti


Sorgenti C: directory SD1.


44

Vettori allocati dinamicamente in C

/*Esempio di uso di vettori allocati dinamicamente:- legge, memorizza e stampa il contenuto di un file (agenda)- la prima riga del file contiene il numero di elementi memorizzati- la funzione calloc() alloca lo spazio di memorizzazione,- l'accesso ai dati e' simile al caso di un vettore.

*/

#include <stdio.h>#include <string.h>#include <stdlib.h>

#define MAXL 81

/* elemento base dell'agenda */typedef struct t_elem {

char nome[20];char cognome[20];int eta;} ELEM;

void main(){

FILE *fin; /* file di ingresso*/char fnin[MAXL]; /* nome del file*/char line[MAXL]; /* buffer per la lettura di una linea */ELEM *dv; /* puntatore all'area allocata dinamicamente */ELEM x;int n; /* numero di elementi (fissato in fase di run) */int i, j;

printf("Esempio di uso di un vettore allocato dinamicamente.\n");

printf("File in ingresso: ");gets(fnin);fin=fopen(fnin,"r");if(fin==NULL) {

puts("Errore in fase di apertura del file.\n");exit(EXIT_FAILURE);}

/* la prima riga del file contiene il numero di righe dello stesso */if(fgets(line, sizeof(line), fin)==NULL) { /* file vuoto? */

puts("File vuoto");exit(EXIT_FAILURE);}

if(sscanf(line, "%d", &n)<1) { /* numero di elementi non valido */puts("Formato file errato");exit(EXIT_FAILURE);}

/* allocazione e azzeramento del vettore */dv=(ELEM*)calloc(n, sizeof(ELEM));if(dv==NULL) { /* errore di allocazione? */

puts("Memoria insufficiente\n");exit(EXIT_FAILURE);}

/* lettura da file */for(i=0; i<n && fgets(line, sizeof(line), fin)!=NULL; i++)


45

sscanf(line, "%s %s %d", dv[i].nome, dv[i].cognome, &dv[i].eta);n=i; /* il file potrebbe avere meno di n elementi */

/* scrittura su video vettore iniziale */printf("Vettore iniziale:\n");for(i=0; i<n; i++)

printf(" %s %s %d\n", dv[i].nome, dv[i].cognome, dv[i].eta);

/* eventuale fase di elaborazione: ordinamento */for(i=0; i<n-1; i++)

for(j=i+1; j<n; j++)if(strcmp(dv[i].cognome, dv[j].cognome)>0 || ( strcmp(dv[i].cognome, dv[j].cognome)==0 &&

strcmp(dv[i].nome, dv[j].nome)>0 ) ) {x=dv[i];dv[i]=dv[j];dv[j]=x;}

/* scrittura su video */printf("Vettore ordinato:\n");for(i=0; i<n; i++)

printf(" %s %s %d\n", dv[i].nome, dv[i].cognome, dv[i].eta);}

Memorizzazione e ordinamento di stringhe (prima versione)

/*Uso di una matrice per la memorizzazione di una sequenza di righe:- legge una sequenza di stringhe da tastiera,- le memorizza in una matrice (vettore di vettori),- quindi ordina e stampa le righe lette.

*/

#include <stdio.h>#include <stdlib.h>#include <string.h>

#define MAXL 80#define MAXN 100

char name[MAXN][MAXL]; /* matrice come vettore di vettori */

void main(){

char line[MAXL];int i, j, n;

/* lettura delle righe da tastiera */printf("Introduci una serie di linee (una linea vuota per terminare):\n");for(n=0; n<MAXN && gets(name[n])!=NULL && *name[n]!='\0'; n++) ;printf("Sono stati letti %d nomi.\n",n);

/* ordinamento delle righe */for(i=0; i<n-1; i++)

for(j=i+1; j<n; j++)if(strcmp(name[i], name[j]) > 0) {

strcpy(line, name[i]);strcpy(name[i], name[j]);strcpy(name[j], line);}

/* stampa delle righe */printf("Elenco ordinato dei nomi:\n",n);


46

for(i=0; i<n; i++)printf("%s\n", name[i]);

}

Memorizzazione e ordinamento di stringhe (seconda versione)

/*Uso di un buffer per la memorizzazione di una sequenza di righe:- legge una sequenza di stringhe da tastiera,- le memorizza in un vettore di stringhe allocate dinamicamente- quindi ordina e stampa le righe lette.

*/


#define MAXL 80#define MAXN 100

char *name[MAXN]; /* vettore di puntatori */

void main(){

char line[MAXL];int i, j, n;char *s;

/* lettura delle righe da tastiera */printf("Introduci una serie di linee (una linea vuota per terminare):\n");for(n=0; n<MAXN && gets(line)!=NULL && *line!='\0'; n++) {

if((name[n]=malloc(strlen(line)+1)) != NULL) { /* alloc. riuscita */strcpy(name[n], line);}

else {printf("Spazio insufficiente\n");break;}

}printf("Sono stati letti %d nomi.\n",n);



s=name[i];name[i]=name[j];name[j]=s;}

/* stampa delle righe */printf("Elenco ordinato dei nomi:\n",n);for(i=0; i<n; i++)

printf("%s\n", name[i]);}

Memorizzazione e ordinamento di stringhe (terza versione)

/*Uso di un buffer per la memorizzazione di una sequenza di righe:- legge una sequenza di stringhe da tastiera,- le memorizza in un unico vettore di caratteri,


47

mantenendo un vettore di puntatori per l'accesso diretto,- quindi ordina e stampa le righe lette.

*/


#define MAXL 80#define MAXN 100#define MAXC 20

char *name[MAXN]; /* vettore di puntatori */char buf[MAXC]; /* buffer */

void main(){

char line[MAXL];int i, j, l, n;char *d,*s;

/* lettura delle righe da tastiera */printf("Introduci una serie di linee (una linea vuota per terminare):\n");d=buf;for(n=0; n<MAXN && gets(line)!=NULL && *line!='\0'; n++) {

l=strlen(line);if(l < MAXC-(d-buf)) { /* spazio libero sufficiente */

strcpy(d, line);name[n]=d;d+=(l+1);}

else {printf("Spazio insufficiente\n");break;}

}printf("Sono stati letti %d nomi.\n",n);



s=name[i];name[i]=name[j];name[j]=s;}

/* stampa delle righe */printf("Elenco ordinato dei nomi:\n",n);for(i=0; i<n; i++)

printf("%s\n", name[i]);}

Liste linkate ordinate (prima versione)

/*Lista gestita dinamicamente e ordinata:- le funzioni insert e delete restituiscono il nuovo puntatore alla testa

*/

#include <stdio.h>#include <stdlib.h>#include <ctype.h>


48

typedef int KEY; /* tipo campo chiave */

/*ogni elemento comprende un campo chiave sul quale viene effettuatol ordinamento)

*/typedef struct t_elem {

KEY key; /* campo chiave*/struct t_elem *next; /* puntatore all'elemento successivo */} ELEM;

/*Inserimento di un nuovo elemento:- restituisce comunque la testa della nuova lista

*/ELEM *insert(ELEM *h, KEY k){

ELEM *p, *q, *r;

q=NULL;for(p=h; p!=NULL && p->key<k; p=p->next) /* ciclo di posizionamento */

q=p;if(p==NULL || p->key>k) { /* elemento non trovato */

r=(ELEM*)malloc(sizeof(ELEM));r->key=k;r->next=p;if(q==NULL) /* inserimento in testa */

return r; /* nuovo punt. di testa */else /* inserimento interno alla lista */

q->next=r; /* collega nuovo elemento */}

return h; /* inserimento interno o elemento gia' presente */}

/*Cancellazione di un elemento:- restituisce comunque la testa della nuova lista

*/ELEM *delete(ELEM *h, KEY k){

ELEM *p, *q, *r;


q=p;if(p!=NULL && p->key==k) { /* elemento trovato */

r=p->next; /* r punta al prossimo elemento */free(p);if(q==NULL) /* cancellazione del primo elemento */

return r;else /* cancellazione di un elemento interno alla lista */

q->next=r;}

return h; /* elemento interno, non trovato o lista vuota */}

/*Ricerca di un elemento:- restituisce il puntatore all' elemento- NULL se non lo trova

*/ELEM *search(ELEM *h, KEY k){


49

ELEM *p;

for(p=h; p!=NULL && p->key<k; p=p->next) /* ciclo di posizionamento */;

if(p!=NULL && p->key==k) /* elemento trovato */return h;

else /* elemento non trovato */return NULL;

}

/*Stampa gli elementi della lista

*/void print(ELEM *h){

while(h!=NULL) {printf("(%d)", h->key);h=h->next;}

printf("\n");}

void main(){

char line[81];char comm[81];KEY key;ELEM *head=NULL; /* puntatore alla testa della lista */ELEM *p;

printf("Gestione di una lista ordinata.\n");do {

printf("Comando> Insert Delete Search Print Quit: ");gets(line);sscanf(line,"%s%d", comm, &key);switch(toupper(*comm)) {

case 'S':p=search(head, key);if(p==NULL)

printf("Elemento %d non presente\n", key);else

printf("Elemento %d presente\n", p->key);break;

case 'I':head=insert(head, key);break;

case 'D':head=delete(head, key);break;

case 'P':printf("Lista: ");print(head);break;

case 'Q':break;

default:printf("Comando errato\n");break;

} /* end switch */} while(toupper(*comm)!='Q');

}


50

Liste linkate ordinate (seconda versione)

/*Lista gestita dinamicamente e ordinata:- le funzioni insert e delete restituiscono il nuovo puntatore alla testa

*/


typedef int KEY; /* tipo campo chiave */

/*ogni elemento comprende un campo chiave sul quale viene effettuatol ordinamento)


KEY key; /* campo chiave*/struct t_elem *next; /* puntatore all'elemento successivo */} ELEM;

/*Inserimento di un nuovo elemento:- restituisce comunque la testa della nuova lista

*/ELEM *insert(ELEM *h, KEY k){

ELEM *p, *q, *r;


q=p;if(p==NULL || p->key>k) { /* elemento non trovato */

r=(ELEM*)malloc(sizeof(ELEM));r->key=k;r->next=p;if(q==NULL) /* inserimento in testa */

return r; /* nuovo punt. di testa */else /* inserimento interno alla lista */

q->next=r; /* collega nuovo elemento */}

return h; /* inserimento interno o elemento gia' presente */}

/*Cancellazione di un elemento:- restituisce comunque la testa della nuova lista

*/ELEM *delete(ELEM *h, KEY k){

ELEM *p, *q, *r;


q=p;if(p!=NULL && p->key==k) { /* elemento trovato */

r=p->next; /* r punta al prossimo elemento */free(p);if(q==NULL) /* cancellazione del primo elemento */

return r;else /* cancellazione di un elemento interno alla lista */


51

q->next=r;}

return h; /* elemento interno, non trovato o lista vuota */}

/*Ricerca di un elemento:- restituisce il puntatore all' elemento- NULL se non lo trova


ELEM *p;

for(p=h; p!=NULL && p->key<k; p=p->next) /* ciclo di posizionamento */;

if(p!=NULL && p->key==k) /* elemento trovato */return h;

else /* elemento non trovato */return NULL;

}



while(h!=NULL) {printf("(%d)", h->key);h=h->next;}

printf("\n");}

void main(){

char line[81];char comm[81];KEY key;ELEM *head=NULL; /* puntatore alla testa della lista */ELEM *p;


printf("Comando> Insert Delete Search Print Quit: ");gets(line);sscanf(line,"%s%d", comm, &key);switch(toupper(*comm)) {



printf("Elemento %d presente\n", p->key);break;

case 'I':head=insert(head, key);break;

case 'D':head=delete(head, key);break;

case 'P':printf("Lista: ");print(head);break;


52

case 'Q':break;



}

Liste linkate ordinate (terza versione)

/*Lista ordinata (senza duplicati) senza dummy record in testa:- si noti il passaggio del puntatore di testa per indirizzo (**ph)- questa tecnica non e' necessaria per le operazioni di ricerca e stampa

*/

#include <stdio.h>#include <stdlib.h>#include <ctype.h>#include <string.h>

typedef int KEY; /* tipo campo chiave */typedef char ATTR[20]; /* tipo campo attributo */

/*ogni elemento comprende un campo chiave (sul quale viene effettuatol'ordinamento) ed un campo attributo


KEY key; /* campo chiave*/ATTR attr; /* campo attributo */struct t_elem *next; /* puntatore all'elemento successivo */} ELEM;

/*Ricerca con eventuale inserimento di un elemento:- se non lo trova lo inserisce- restituisce comunque il puntatore all'elemento cercato

*/ELEM *find(ELEM **ph, KEY k){

ELEM *p;

while(*ph!=NULL && (*ph)->key<k)ph=&((*ph)->next);

if((*ph)==NULL || (*ph)->key>k) { /* elemento non esistente */p=(ELEM*)malloc(sizeof(ELEM));p->key =k;p->next=*ph;*ph=p;return p;}

else /* elemento esistente*/

return *ph;}

/*Inserimento di un nuovo elemento:- se lo trova restituisce NULL- se non lo trova lo inserisce e ne restituisce il puntatore

*/


53

ELEM *insert(ELEM **ph, KEY k){

ELEM *p;


if((*ph)==NULL || (*ph)->key>k) { /* elemento non esistente */p=(ELEM*)malloc(sizeof(ELEM));p->key =k;p->next=*ph;*ph=p;return p;}

else /* elemento esistente*/

return NULL;}

/*Cancellazione di un elemento:- se lo trova lo cancella e restituisce 1- se non lo trova restituisce 0

*/int delete(ELEM **ph, KEY k){

ELEM *p;


if((*ph)!=NULL && (*ph)->key==k) { /* elemento trovato */p=*ph;(*ph)=p->next;free(p);return 1;}

else /* elemento non trovato */return 0;

}

/*Ricerca di un elemento:- se lo trova ne restituisce l' indirizzo- se non lo trova restituisce NULL


while(h!=NULL && h->key<k)h=h->next;

if(h==NULL || h->key>k) /* elemento trovato */return NULL;

elsereturn h; /* elemento non trovato */

}



while(h!=NULL) {printf("(%d,%s)", h->key, h->attr);h=h->next;}

printf("\n");}


54

void main(){

char line[81];char comm[81];KEY key;ATTR attr;ELEM *head=NULL; /* puntatore alla testa della lista */ELEM *p;


printf("Comando> Insert Find Delete Search Modify Print Quit: ");gets(line);sscanf(line,"%s%d%s",comm, &key, attr);switch(toupper(*comm)) {



printf("Elemento %d presente, attributo %s\n",p->key, p->attr);

break;case 'I':

p=insert(&head, key);if(p==NULL)

printf("Elemento %d gia' presente.\n", key);else {

strcpy(p->attr, attr);printf("Elemento %d inserito.\n", key);}

break;case 'F':

p=find(&head, key);p->attr[0]='\0';printf("Elemento %d: attributo %s.\n",

p->key, p->attr);break;

case 'D':if(delete(&head, key)==0)

printf("Elemento %d non presente.\n", key);else

printf("Elemento %d cancellato\n", key);break;

case 'M':p=search(head, key);if(p==NULL)

printf("Elemento %d non presente\n", key);else {

printf("Elemento %d presente, vecchio attributo %s\n",p->key, p->attr);

strcpy(p->attr, attr);printf(" Attributo modificato in %s\n", attr);}

break;case 'P':

printf("Lista: ");print(head);break;

case 'Q':break;



55


}


56

Lezione 8 - Strutture dati (II)

• Code FIFO: definizione e caratteristiche.

• Code FIFO: implementazione statica e dinamica.

• Operazioni insert ed extract su una coda.

• Pila (stack): definizione e caratteristiche.

• Pila (stack): implementazione statica e dinamica.

• Operazioni push, pop, top ed empty su una pila.

• Valutazione di espressioni RPN mediante l’uso di uno stack.

Riferimenti




57

Coda FIFO (implementazione statica)

/*Routines di inserzione ed estrazione in una coda FIFOimplementata per mezzo di un vettore (buffer circolare):- il vettore e gli indici sono memorizzati in una struttura QUEUE;- inserimento in tail;- rimozione da head.

*/


#define MAXQ 10 /* numero max. elementi in coda */

/* tipo di un elemento della coda FIFO */typedef int ITEM;

/* struttura di memorizzazione per la coda FIFO */typedef struct t_queue {

ITEM *buf; /* buffer (circolare) */int head; /* indice elemento di testa */int tail; /* indice elemento di coda */int cnt; /* numero elementi presenti */int max; /* dimensione massima */} QUEUE;

/*crea una coda FIFO vuota di l elementi:- restituisce 1 in caso di successo- restituisce 0 se la memoria e' esaurita

*/int create(QUEUE *pq, int l){

/* allocazione dinamica area per contenere gli l elementi */if ((pq->buf=malloc(l*sizeof(*(pq->buf)))) == NULL) {

return 0;}

/* inizializzazioni */pq->tail=pq->head=0;pq->cnt=0;pq->max=l;return 1;

}

/*inserimento in coda:- restituisce 0 se la coda e' piena- restituisce 1 se l' inserimento ha successo

*/int insert(QUEUE *pq, ITEM v){

if(pq->cnt < pq->max) {pq->buf[pq->tail++]=v;pq->tail%=pq->max;pq->cnt++;return 1;}

elsereturn 0;

}

/*


58

estrazione dalla coda:- restituisce 0 se la coda e' vuota- restituisce 1 se esiste un elemento valido

*/int extract(QUEUE *pq, ITEM *pv){

if(pq->cnt>0) {*pv=pq->buf[pq->head++];pq->head%=pq->max;pq->cnt--;return 1;}

elsereturn 0;

}

/*stampa gli elementi della coda

*/void print(QUEUE q){

int i,j;

j=q.head;for(i=0; i<q.cnt; i++) {

printf("%d ", q.buf[j++]);j%=q.max;}

printf("\n");}

/*stampa (dump) il contenuto dell'array

*/void dump(QUEUE q){

int i,j;

for(i=0; i<q.max; i++) {if(i==q.tail)

printf("t->");if(i==q.head)

printf("h->");printf("%d ", q.buf[i]);}

printf("(%d elementi)\n", q.cnt);}

void main(){

char line[81];char comm[81];ITEM val;QUEUE queue;

printf("Gestione di una coda FIFO (struttura statica).\n");

create(&queue, MAXQ); /* inizializzazione coda FIFO *//* e creazione buffer di elementi */

do {printf("Comando> Insert Extract Dump Print Quit: ");gets(line);sscanf(line,"%s%d", comm, &val);switch(toupper(*comm)) {


59

case 'I':if(!insert(&queue, val))

printf("Coda piena\n");else

printf("Elemento %d inserito\n", val);break;

case 'E':if(!extract(&queue, &val))

printf("Coda vuota\n");else

printf("Elemento letto: %d\n", val);break;

case 'P':printf("Coda FIFO: ");print(queue);break;

case 'D':printf("Buffer: ");dump(queue);break;

case 'Q':break;


} /* end switch */} while (toupper(*comm)!='Q');

}

Coda FIFO (implementazione dinamica)

/*Implementa le procedure di inserzione ed estrazione in una coda FIFOimplementata per mezzo di una lista circolare:- inserimento da tail, estrazione da head;- la coda e' individuata dal puntatore a tail;- l'elemento in tail punta a head.

*/


/* tipo di un elemento della coda FIFO */typedef int ITEM;

/* struttura di memorizzazione per la coda FIFO */typedef struct t_elem {

ITEM val;struct t_elem *next;} ELEM;

/*inserimento in coda:- restituisce 0 se la memoria e' esaurita- restituisce 1 se l'inserimento ha successo

*/int insert(ELEM **pt, ITEM v){

ELEM *p;

p=(ELEM*)malloc(sizeof(ELEM));if(p==NULL) /* memoria esaurita */

return 0;


60

p->val=v;if(*pt!=NULL) { /* coda non vuota */

p->next=(*pt)->next;(*pt)->next=p;}

else /* coda vuota */p->next=p;

(*pt)=p;return 1;

}

/*estrazione dalla coda:- restituisce 0 se la coda e' vuota- restituisce 1 se esiste un elemento valido

*/int extract(ELEM **pt, ITEM *pv){

ELEM *p;

if(*pt==NULL) /* coda vuota */return 0;

/* coda non vuota */p=(*pt)->next; /* punta alla testa */if(p==*pt) /* un unico elemento in coda */

*pt=NULL;else /* piu' di un elemento in coda */

(*pt)->next=p->next;*pv=p->val;free(p);return 1;

}

/*stampa gli elementi in coda

*/void print(ELEM *t){

ELEM *p;

if(t!=NULL) {/* coda non vuota */p=t->next; /* punta alla testa */do {

printf("%d ", p->val);p=p->next;} while(p!=t->next);

}printf("\n");

}

void main(){

char line[81];char comm[81];ITEM val;ELEM *tail=NULL; /* coda FIFO */int i, j;

printf("Gestione di una coda FIFO (struttura dinamica).\n");

do {printf("Comando> Insert Extract Print Quit: ");gets(line);sscanf(line,"%s%d", comm, &val);switch(toupper(*comm)) {


61

case 'I':if(!insert(&tail, val))

printf("Coda piena\n");else

printf("Elemento %d inserito\n", val);break;

case 'E':if(!extract(&tail, &val))

printf("Coda vuota\n");else

printf("Elemento letto: %d\n", val);break;

case 'P':printf("Coda FIFO: ");print(tail);break;

case 'Q':break;


} /* end switch */} while (toupper(*comm)!='Q');

}

Stack per la valutazione di espressioni RPN (versione dinamica)

/*Semplice calcolatrice RPN (Reverse Polish Notation)che lavora su numeri in doppia precisione:- usa una lista semplicemente linkata senza sentinella,- gli operandi (numeri, operatori) sono separati da spazi.

Date: 18 Jan 2000Author: G. Cena

*/


#define MAXL 81

/* tipo di un elemento dello stack */typedef double ITEM;

/* struttura di memorizzazione per lo stack */typedef struct t_elem {

ITEM val;struct t_elem *next;} ELEM;

/*operazione PUSH:- restituisce 0 se si esaurisce la memoria- restituisce 1 se l'operazione ha successo

*/int push(ELEM **pst, ITEM v){

ELEM *p;

p=(ELEM*)malloc(sizeof(ELEM));if(p==NULL) /* memoria esaurita */

return 0;else { /* aggiunta di un elemento in testa */


62

p->val=v;p->next=*pst;*pst=p;return 1;}

}

/*operazione POP:- restituisce 0 se lo stack e' vuoto- restituisce 1 se l'operazione ha successo

*/int pop(ELEM **pst, ITEM *pv){

ELEM *p;

if(*pst==NULL) /* stack vuoto */return 0;

else { /* stack non vuoto */p=*pst;*pv=p->val;*pst=p->next;free(p);return 1;}

}

/*operazione TOP:- restituisce 0 se lo stack e' vuoto- restituisce 1 se l'operazione ha successo

*/int top(ELEM *st, ITEM *pv){

if(st==NULL) /* stack vuoto */return 0;

else { /* stack non vuoto */*pv=st->val;return 1;}

}

/*operazione EMPTY:- restituisce 1 se lo stack e' vuoto- restituisce 0 se esiste almeno un elemento

*/int empty(ELEM *st){

return st==NULL;}

void main(){

int nc;char token[MAXL];char expr[MAXL];char *l;ELEM *stack=NULL;double op1, op2, res;

printf("Calcolo di una espressione RPN (esempio di uso di uno stack).\n");

printf("Espressione RPN: ");gets(expr);


63

l=expr;while(sscanf(l,"%s%n", token, &nc)>0) {

l+=nc;switch(*token) {

case '+':case '-':case '*':case '/':

if(!pop(&stack, &op2)) {printf("Espressione RPN errata\n");exit(EXIT_FAILURE);}

if(!pop(&stack, &op1)) {printf("Espressione RPN errata\n");exit(EXIT_FAILURE);}

switch(*token) {case '+':

res=op1+op2;break;

case '-':res=op1-op2;break;

case '*':res=op1*op2;break;

case '/':res=op1/op2;break;

}push(&stack, res);break;

case '=':if(!top(stack, &res)) {

printf("Espressione RPN errata\n");exit(EXIT_FAILURE);}

elseprintf("Risultato parziale %f\n",res);

break;default: /* inserisci un operando */

if(!push(&stack, atof(token))) {printf("Stack overflow\n");exit(EXIT_FAILURE);}

break;} /* end switch */

} /* end while */

if(!pop(&stack, &res)) { /* leggi il risultato */printf("Espressione RPN errata\n");exit(EXIT_FAILURE);}

if(empty(stack)) {printf("Risultato finale %f\n",res);exit(EXIT_SUCCESS);}

else { /* ci sono altri elementi */printf("Espressione RPN errata\n");exit(EXIT_FAILURE);}

}


64

Stack per la valutazione di espressioni RPN (prima versione statica)

/*Semplice calcolatrice RPN (Reverse Polish Notation)che lavora su numeri in doppia precisione:- usa uno stack realizzato con un vettore esterno;- lo stack pointer (intero) punta alla prima posizione libera;- usa delle macro per l'accesso allo stack.

*/


#define MAXL 81

/*macro per la gestione dello stack

*/#define MAXS 100#define PUSH(x) (stack[sp++]=(x))#define POP() (stack[--sp])#define TOP() (stack[sp-1])#define EMPTY() (sp==0)#define FULL() (sp==MAXS)

/*struttura di memorizzazione per lo stack

*/double stack[MAXS];int sp=0;

void main(){

int nc;char token[MAXL];char expr[MAXL];char *l;double op1, op2, res;



l=expr;while(sscanf(l,"%s%n", token, &nc)>0) {



if(!EMPTY())op2=POP();

else {printf("Espressione RPN errata\n");exit(EXIT_FAILURE);}

if(!EMPTY())op1=POP();



65


res=op1+op2;break;




}PUSH(res);break;

case '=':if(!EMPTY()) {

res=TOP();printf("Risultato parziale %f\n",res);}


break;default: /* operando */

if(!FULL())PUSH(atof(token));

else {printf("Stack overflow\n");exit(EXIT_FAILURE);}

break;} /* end switch */

} /* end while */

if(!EMPTY()) /* leggi il risultato */res=POP();


if(EMPTY()) {printf("Risultato finale %f\n",res);exit(EXIT_SUCCESS);}


}

Stack per la valutazione di espressioni RPN (seconda versione statica)

/*Semplice calcolatrice RPN (Reverse Polish Notation)che lavora su numeri in doppia precisione:- vengono usate macro invece che funzioni- definisce un tipo STACK come struct- usa uno stack realizzato con un vettore,- lo stack pointer (intero) punta alla prima posizione libera.

*/


66


#define MAXL 81#define MAXS 100

typedef double ITEM;

/* struttura di memorizzazione per lo stack */typedef struct t_stack {

int sp;int size;ITEM *stack;} STACK;

/* macro per la gestione dello stack */#define CREATE(s,l) ((s).sp=0,(s).size=(l),\

(s).stack=(ITEM*)malloc((l)*sizeof(ITEM)))#define PUSH(s,x) ((s).stack[(s).sp++]=(x))#define POP(s) ((s).stack[--(s).sp])#define TOP(s) ((s).stack[(s).sp-1])#define EMPTY(s) ((s).sp==0)#define FULL(s) ((s).sp==(s).size)

void main(){

int nc;char token[MAXL];char expr[MAXL];char *l;STACK stk;double op1, op2, res;



CREATE(stk, MAXS);

l=expr;while(sscanf(l,"%s%n", token, &nc)>0) { /* legge un nuovo token */



if(!EMPTY(stk))op2=POP(stk);


if(!EMPTY(stk))op1=POP(stk);



res=op1+op2;break;

case '-':


67

res=op1-op2;break;



} /* end switch interno */PUSH(stk,res);break;

case '=':if(!EMPTY(stk)) {

res=TOP(stk);printf("Risultato parziale %f\n",res);}



if(!FULL(stk))PUSH(stk,atof(token));

else {printf("Stack overflow\n");exit(EXIT_FAILURE);}

break;} /* end switch esterno */

} /* end while */

if(!EMPTY(stk)) /* leggi il risultato */res=POP(stk);


if(EMPTY(stk)) {printf("Risultato finale %f\n",res);exit(EXIT_SUCCESS);}


}

Stack per la valutazione di espressioni RPN (terza versione statica)

/*Semplice calcolatrice RPN (Reverse Polish Notation)che lavora su numeri in doppia precisione- vengono usate macro invece che funzioni- definisce un tipo STACK come struct- usa uno stack realizzato con un vettore,- lo stack pointer (intero) punta alla prima posizione libera.

*/




68



int sp;int size;void *stack;} STACK;

/* macro per la gestione dello stack */#define CREATE(b,s,l) ((s)=(STACK*)malloc(sizeof(STACK)),\

(s)->sp=0, (s)->size=(l),\ (s)->stack=malloc((l)*sizeof(b)))

#define PUSH(b,s,x) ((s)->sp<(s)->size?((b*)((s)->stack))[(s)->sp++]=(x),1:0)#define POP(b,s,x) ((s)->sp>0?x=((b*)((s)->stack))[--(s)->sp],1:0)#define TOP(b,s,x) ((s)->sp>0?x=((b*)((s)->stack))[(s)->sp-1],1:0)#define EMPTY(s) ((s)->sp==0)#define FULL(s) ((s)->sp==(s)->size)

void main(){

int nc;char token[MAXL];char expr[MAXL];char *l;STACK *stk;double op1, op2, res;



CREATE(ITEM, stk, MAXS);




if(!POP(ITEM, stk, op2)) {printf("Espressione RPN errata\n");exit(EXIT_FAILURE);}



res=op1+op2;break;





69

} /* end switch interno */PUSH(ITEM, stk, res);break;

case '=':if(TOP(ITEM, stk, res))

printf("Risultato parziale %f\n", res);else {



if(!PUSH(ITEM, stk, atof(token))) {printf("Stack overflow\n");exit(EXIT_FAILURE);}

break;} /* end switch esterno */

} /* end while */

if(!POP(ITEM, stk, res)) { /* leggi il risultato */printf("Espressione RPN errata\n"); /* stack vuoto */exit(EXIT_FAILURE);}



}

Stack per la valutazione di espressioni RPN (quarta versione statica)

/*Semplice calcolatrice RPN (Reverse Polish Notation)che lavora su numeri in doppia precisione- vengono usate macro invece che funzioni- definisce un tipo STACK come struct- usa uno stack realizzato con un vettore,- lo stack pointer (intero) punta alla prima posizione libera.

*/





int sp;int size;void *stack;} STACK;

/* macro per la gestione dello stack */#define CREATE(b,s,l) ((s).sp=0, (s).size=(l),\

(s).stack=malloc((l)*sizeof(b)))#define PUSH(b,s,x) ((s).sp<(s).size?((b*)((s).stack))[(s).sp++]=(x),1:0)


70

#define POP(b,s,x) ((s).sp>0?x=((b*)((s).stack))[--(s).sp],1:0)#define TOP(b,s,x) ((s).sp>0?x=((b*)((s).stack))[(s).sp-1],1:0)#define EMPTY(s) ((s).sp==0)#define FULL(s) ((s).sp==(s).size)

void main(){

int nc;char token[MAXL];char expr[MAXL];char *l;STACK stk;double op1, op2, res;



CREATE(ITEM, stk, MAXS);







res=op1+op2;break;




} /* end switch interno */PUSH(ITEM, stk, res);break;

case '=':if(TOP(ITEM, stk, res))

printf("Risultato parziale %f\n", res);else {



if(!PUSH(ITEM, stk, atof(token))) {printf("Stack overflow\n");exit(EXIT_FAILURE);


71

}break;

} /* end switch esterno */} /* end while */

if(!POP(ITEM, stk, res)) { /* leggi il risultato */printf("Espressione RPN errata\n"); /* stack vuoto */exit(EXIT_FAILURE);}



}


72

Lezione 9 - Strutture dati (III)

• BST (binary search tree): definizione e caratteristiche.

• Operazioni search, insert e delete su un BST.

• Visite inorder, preorder e postorder di un BST.

Riferimenti




73

Alberi binari di ricerca (BST)

/*Operazioni sugli alberi di ricerca (Binary Search Tree, BST):- inserimento;- ricerca;- cancellazione;- stampa albero in formato grafico;- visita (stampa) in inorder, preorder e postorder;- utilizza funzioni recursive.

*/

#include <stdio.h>#include <stdlib.h>#include <ctype.h>#include <string.h>

typedef int KEY; /* tipo campo chiave */typedef char ATTR[20]; /* tipo campo attributo */

/*ogni elemento del BST comprende un campo chiave (sul quale vieneeffettuato l'ordinamento), un campo attributo e due puntatori alsottoalbero destro e sinistro

*/typedef struct t_elem { /* elemento del BST */

KEY key; /* campo chiave */ATTR attr; /* campo attributo */struct t_elem *left, *right; /* puntatori agli elementi sx e dx */} ELEM;

/*Ricerca con eventuale inserimento di un elemento:- se non lo trova lo inserisce- restituisce comunque il puntatore all'elemento cercato

*/ELEM *find(ELEM **pr, KEY k){

if(*pr!=NULL) /* sono su un nodo valido? */if ((*pr)->key>k)

return find(&(*pr)->left, k);else if ((*pr)->key<k)

return find(&(*pr)->right, k);else /* (*pr)->key==k, ovvero ho trovato la chiave */

return *pr;else { /* trovato il punto di inserimento */

*pr=(ELEM*)malloc(sizeof(ELEM));(*pr)->key=k;(*pr)->left=(*pr)->right=NULL;return *pr;}

}

/*Inserimento di un nuovo elemento:

- restituisce il puntatore all'elemento inserito - restituisce NULL se l' elemento esiste gia'*/ELEM *insert(ELEM **pr, KEY k){

if(*pr!=NULL) /* sono su un nodo valido? */if ((*pr)->key>k)

return insert(&(*pr)->left, k);else if ((*pr)->key<k)


74

return insert(&(*pr)->right, k);else /* (*pr)->key==k, ovvero ho trovato la chiave */

return NULL;else { /* trovato il punto di inserimento */

*pr=(ELEM*)malloc(sizeof(ELEM));(*pr)->key=k;(*pr)->left=(*pr)->right=NULL;return *pr;}

}

/*Cancellazione di un elemento:

- restituisce 1 se ha cancellato l'elemento - restituisce 0 se l'elemento non esiste*/int delete(ELEM **pr, KEY k){

ELEM **q,*r;

if(*pr!=NULL) /* sono su un nodo valido? */if((*pr)->key>k)

return delete(&(*pr)->left, k);else if((*pr)->key<k)

return delete(&(*pr)->right, k);else { /* (*pr)->key==k, chiave da cancellare trovata */

if((*pr)->left==NULL) { /* manca elemento SX */r=*pr;*pr=(*pr)->right;free(r);}

else if((*pr)->right==NULL) { /* c'e' solo l'elemento SX */r=*pr;*pr=(*pr)->left;free(r);}

else { /* ci sono entrambi i figli */for(q=&(*pr)->left; (*q)->right!=NULL; q=&(*q)->right) ;r=*q; /* r punta all'elemento nel sottoalbero SX */*q=(*q)->left;r->left=(*pr)->left;r->right=(*pr)->right;free(*pr);*pr=r;}

return 1;}

else /* nodo non esistente */return 0;

}

/*Ricerca di un elemento:

- restituisce il puntatore all'elemento cercato - restituisce NULL se non lo trova*/ELEM *search(ELEM *r, KEY k){

if(r!=NULL)if(r->key>k)

return search(r->left,k);else if (r->key<k)

return search(r->right,k);else /* (h->key==k) */

return r;


75

elsereturn NULL;

}

/*Operazione di visita del nodo

*/void visit(ELEM *r){

printf("(%d,%s) ", r->key, r->attr);}

/*Visita Inorder

*/void inorder(ELEM *r){

if(r!=NULL) {inorder(r->left);visit(r);inorder(r->right);}

}

/*Visita Postorder

*/void postorder(ELEM *r){

if(r!=NULL) {postorder(r->left);postorder(r->right);visit(r);}

}

/*Visita Preorder

*/void preorder(ELEM *r){

if(r!=NULL) {visit(r);preorder(r->left);preorder(r->right);}

}

/*Stampa Inorder-like

*/void print(ELEM *r,int l,char c){

int i;

if(r!=NULL) {print(r->left,l+4,'/');if(c=='\\') {

for (i=0; i<l; i++)printf("%c",' ');

printf(" \\\n");}

for (i=0; i<l; i++)printf("%c",' ');

printf(" (%d,%s)\n", r->key, r->attr);


76

if(c=='/') {for (i=0; i<l; i++)

printf("%c",' ');printf(" /\n");}

print(r->right,l+4,'\\');}

}

void main(){

char line[81];char comm[81];int d;KEY key;ATTR attr;ELEM *root=NULL; /* definizione del BST */ELEM *p;

printf("Gestione di un BST.\n");

do {printf("Comando> Insert Delete Search Print iNorder pReorder pOstorder Quit:

");gets(line);sscanf(line,"%s%d%s", comm, &key, attr);switch(toupper(*comm)) {

case 'I':p=insert(&root, key);if (p==NULL)

printf("Elemento gia` presente\n");else {

strcpy(p->attr, attr);printf("Elemento %d inserito.\n", key);}

break;case 'F':

p=find(&root, key);p->attr[0]='\0';printf("Elemento %d: attributo %s.\n",

p->key, p->attr);break;

case 'D':d=delete(&root, key);if (d==0)

printf("Elemento non presente\n");else

printf("Elemento cancellato\n");break;

case 'S':p=search(root, key);if (p==NULL)

printf("Elemento (%d) non presente\n", key);else

printf("Elemento (%d,%s) presente\n", p->key, p->attr);break;

case 'P':print(root,0,'-');break;

case 'N':printf("Inorder: ");inorder(root);printf("\n");break;

case 'O':


77

printf("Postorder: ");postorder(root);printf("\n");break;

case 'R':printf("Preorder: ");preorder(root);printf("\n");break;

case 'Q':break;



}


78

Lezione 10 - Programmazione orientata agli oggetti (I)

• Programmazione modulare: compilazione separata, uso di header file.

• Uso di librerie: interfaccia (prototipo) e implementazione delle funzioni.

• Regole di visibilità degli identificatori e tempo di vita delle variabili.

• Tecniche di chiamata a funzione, record di attivazione.

Riferimenti

Testi: [K&R] capitolo 4 (per i dettagli sul linguaggio C).

[F&S] capitoli 13 (cenni) e 14 (cenni).

Sorgenti C: directory OBJ1.


79

Programma su un singolo modulo

/*Esempio di programma su un singolo modulo.

- definisce ed usa le funzioni;- non permette il riuso del S/W;- file di grosse dimensioni.

*/


typedef char KEY[20]; /* tipo campo chiave */typedef int ATTR; /* tipo campo attributo */



KEY key; /* campo chiave*/

ATTR attr; /* campo attributo*/struct t_elem *left, *right; /* puntatori agli elementi sx e dx */} ELEM;

/*prototipi delle funzioni

*/ELEM *insert(ELEM **ph, KEY k);ELEM *search(ELEM *h, KEY k);void inorder(ELEM *h, int l);

/*funzione di inserimento:- restituisce il puntatore all'elemento inserito- restituisce NULL se l'elemento esiste gia'

*/ELEM *insert(ELEM **ph, KEY k){

if(*ph!=NULL)if(strcmp((*ph)->key, k)>0)

return insert(&(*ph)->left, k);else if(strcmp((*ph)->key, k)<0)

return insert(&(*ph)->right, k);else /* == */


*ph=(ELEM*)malloc(sizeof(ELEM));strcpy((*ph)->key, k);(*ph)->left=(*ph)->right=NULL;return (*ph);}

}

/*funzione di ricerca:- restituisce il puntatore all'elemento cercato- restituisce NULL se non lo trova

*/ELEM *search(ELEM *h, KEY k)


80

{if(h!=NULL)

if(strcmp(h->key, k)>0)return search(h->left, k);

else if(strcmp(h->key, k)<0)return search(h->right, k);

else /* (h->key==k) */return h;

elsereturn NULL;

}

/*funzione di vista inorder:- non restituisce nulla;- gestisce un parametro di livello l;- chiama la funzione di visita vst().

*/void inorder(ELEM *h, int l){

int i;

if(h!=NULL) {inorder(h->left, l+1);for (i=0; i<l; i++)

printf(".");printf("%s,%d\n", h->key, h->attr);inorder(h->right, l+1);}

}

/*programma principale

*/void main(){

char line[81];char comm[81];KEY key;ATTR attr;ELEM *root=NULL; /* definizione del BST */ELEM *p;

printf("Gestione di un BST.\n");

do {printf("Comando> Insert Search Print Quit: ");gets(line);sscanf(line,"%s%s%d", comm, key, &attr);switch(toupper(*comm)) {

case 'Q':break;

case 'I':p=(ELEM*)insert(&root, key);p->attr=attr;if (p==NULL)

printf("Elemento %s gia` presente.\n", key);else

printf("Elemento %s inserito.\n", key);break;

case 'S':p=(ELEM*)search(root, key);if (p==NULL)

printf("Elemento %s non presente.\n", key);else


81

printf("Elemento %s presente.\n", key);break;

case 'P':inorder(root, 0);break;


}

Programma su più moduli (header file)

/*Esempio di programma su piu' moduli.

Header file per il modulo BST.C:- prototipi delle funzioni;- definizioni di tipo;- costanti simboliche (in questo caso non ce ne sono).

*/

#ifndef BST_INCLUDED#define BST_INCLUDED

typedef char KEY[20]; /* tipo campo chiave */typedef int ATTR; /* tipo campo attributo */



KEY key; /* campo chiave*/

ATTR attr; /* campo attributo*/struct t_elem *left, *right; /* puntatori agli elementi sx e dx */} ELEM;


*/ELEM *insert(ELEM **ph, KEY k);


*/ELEM *search(ELEM *h, KEY k);


*/void inorder(ELEM *h, int l);

#endif BST_INCLUDED


82

Programma su più moduli (implementazione)


Modulo contenente le funzioni per l'accesso ad un BST:- implementazione della funzione di inserimento;- implementazione della funzione di ricerca;- implementazione della funzione di visita inorder;

*/

#include <stdio.h>#include "bst.h"


*/ELEM *insert(ELEM **ph, KEY k){

if(*ph!=NULL)if(strcmp((*ph)->key, k)>0)

return insert(&(*ph)->left, k);else if(strcmp((*ph)->key, k)<0)

return insert(&(*ph)->right, k);else /* == */


*ph=(ELEM*)malloc(sizeof(ELEM));strcpy((*ph)->key, k);(*ph)->left=(*ph)->right=NULL;return (*ph);}

}



if(h!=NULL)if(strcmp(h->key, k)>0)

return search(h->left, k);else if(strcmp(h->key, k)<0)

return search(h->right, k);else /* (h->key==k) */

return h;else

return NULL;}


*/void inorder(ELEM *h, int l){

int i;


83

if(h!=NULL) {inorder(h->left, l+1);for (i=0; i<l; i++)

printf(".");printf("%s,%d\n", h->key, h->attr);inorder(h->right, l+1);}

}

Programma su più moduli (programma principale)


File principale - operazioni sui BST:- richiama la funzione di inserimento;- richiama la funzione di ricerca;- richiama la funzione di visita inorder e stampa il BST in forma grafica.

*/

#include <stdio.h>#include <stdlib.h>#include "bst.h"

/* programma principale */void main(){

char line[81];char comm[81];KEY key;ATTR attr;ELEM *root=NULL; /* definizione del BST */ELEM *p;

printf("Gestione di un BST.\n");do {

printf("Comando> Insert Search Print Quit: ");gets(line);sscanf(line,"%s%s%d", comm, key, &attr);switch(toupper(*comm)) {

case 'Q':break;

case 'I':p=(ELEM*)insert(&root, key);p->attr=attr;if (p==NULL)

printf("Elemento %s gia` presente.\n", key);else

printf("Elemento %s inserito.\n", key);break;

case 'S':p=(ELEM*)search(root, key);if (p==NULL)

printf("Elemento %s non presente.\n", key);else

printf("Elemento %s presente.\n", key);break;

case 'P':inorder(root, 0);break;


}


84

Lezione 11 - Programmazione orientata agli oggetti (II)

• Introduzione alla programmazione orientata agli oggetti (OOP).

• Definizione di oggetto e di classe.

• Aggregazione, incapsulamento e data hiding.

• Variabili e funzioni membro.

• Metodi di accesso ad un oggetto.

• Costruttori e distruttori.

• Linguaggio di programmazione C++.

Riferimenti

Videocassette: lezioni 1, 2, 3, 4, 5, 6, 7.



85

Classe Rettangolo (versione 0)

/*classe Rettangolo:- sviluppata in C,- uso di typedef,- uso di funzioni.

*/

#include <stdio.h>

typedef struct t_rettangolo{

int base;int altezza;

} Rettangolo;

int area(Rettangolo ret);void stampa(Rettangolo ret);

int area(Rettangolo ret){

return ret.base*ret.altezza;}

void stampa(Rettangolo ret){

int r,c;

for(r=0; r<ret.altezza; r++) {for(c=0; c<ret.base; c++)

printf("*");printf("\n");}

}

void main(){

Rettangolo a, b;

printf("Classe Rettangolo in C.\n");

a.base=6;a.altezza=4;printf("Area del Rettangolo a: %d\n", area(a));stampa(a);

b.base=3;b.altezza=2;printf("Area del Rettangolo b: %d\n", area(b));stampa(b);

}

/* ------------------ output --------------------------Classe Rettangolo in C.Area del Rettangolo a: 24************************Area del Rettangolo b: 6******------------------------------------------------------- */


86


/*classe Rettangolo:- commenti C++ like,- encapsulation (estensione di struct),- output in C++.

*/

#include <iostream.h>

struct Rettangolo{

int base;int altezza;int area(void);void stampa(void);};

int Rettangolo::area(void){

return base*altezza;}

void Rettangolo::stampa(void){

int r,c;

for(r=0; r<altezza; r++) {for(c=0; c<base; c++)

cout << '*';cout << endl;}

}

void main(){

Rettangolo a, b;

cout << "Classe Rettangolo: incapsulamento." << endl;

a.base=6;a.altezza=4;cout << "Area del Rettangolo a: " << a.area() << endl;a.stampa();

b.base=3;b.altezza=2;cout << "Area del Rettangolo b: " << b.area() << endl;b.stampa();

}

/* ------------------ output --------------------------Classe Rettangolo: incapsulamento.Area del Rettangolo a: 24************************Area del Rettangolo b: 6******------------------------------------------------------- */


87


/*classe Rettangolo:- commenti C++ like,- costruttori (di default),- overloading dei metodi.

*/


class Rettangolo{


public:Rettangolo(); // costruttore senza parametriRettangolo(int b); // costruttore per quadratiRettangolo(int b, int h); // costruttore per rettangoliint area(void);void stampa(void);};

Rettangolo::Rettangolo() // costruttore di default (meglio, senza parametri){

base=0;altezza=0;

}

Rettangolo::Rettangolo(int l) // costruttore per quadrati{

base=l;altezza=l;

}

Rettangolo::Rettangolo(int b, int h) // costruttore per rettangoli{

base=b;altezza=h;

}




int r,c;



}

void main(){

Rettangolo a, b(5), c(3,4);

cout << "Classe Rettangolo: costruttori / overloading." << endl;


88

cout << "Area del Rettangolo a: " << a.area() << endl;a.stampa();cout << "Area del Rettangolo b: " << b.area() << endl;b.stampa();cout << "Area del Rettangolo c: " << c.area() << endl;c.stampa();

}

/* ------------------ output --------------------------Classe Rettangolo: costruttori / overloading.Area del Rettangolo a: 0Area del Rettangolo b: 25*************************Area del Rettangolo c: 12************------------------------------------------------------- */


/*classe Rettangolo:- data hiding,- metodi di accesso,- specificatori di accesso.

*/


class Rettangolo{


public:int getb(void);int geth(void);void setb(int);void seth(int);int area(void);void stampa(void);};

int Rettangolo::getb(void){

return base;}

int Rettangolo::geth(void){

return altezza;}

void Rettangolo::setb(int b){

base=b;}

void Rettangolo::seth(int h)


89

{altezza=h;

}




int r,c;



}

void main(){

Rettangolo a, b;

cout << "Classe Rettangolo: data hiding." << endl;

a.setb(6);a.seth(4);cout << "Area del Rettangolo a: " << a.area() << endl;cout << "Base: " << a.getb() << " Altezza: " << a.geth() << endl;a.stampa();

b.setb(3);b.seth(2);cout << "Area del Rettangolo b: " << b.area() << endl;cout << "Base: " << b.getb() << " Altezza: " << b.geth() << endl;b.stampa();

}

/* ------------------ output --------------------------Classe Rettangolo: data hiding.Base: 6 Altezza: 4************************Area del Rettangolo b: 6Base: 3 Altezza: 2******------------------------------------------------------- */


/*classe Rettangolo:- passaggio by reference- check sui parametri- lettura da standard input

*/



90

class Rettangolo{


public:void get(int& b, int& h);void set(int b, int h);int getb();int geth();void setb(int);void seth(int);int area();void stampa();};

void Rettangolo::get(int& b, int& h){

b=base;h=altezza;

}

void Rettangolo::set(int b, int h){

if(b>=0) // ha senso solo un valore non negativobase=b;

if(h>=0) // ha senso solo un valore non negativoaltezza=h;

}

int Rettangolo::getb(){

return base;}

int Rettangolo::geth(){

return altezza;}

void Rettangolo::setb(int b){

if(b>=0) // ha senso solo un valore non negativobase=b;

}

void Rettangolo::seth(int h){

if(h>=0) // ha senso solo un valore non negativoaltezza=h;

}

int Rettangolo::area(){


void Rettangolo::stampa(){

int r,c;




91

}

void main(){

Rettangolo c, d;int b, h;

cout << "Classe Rettangolo: parametri by reference / input." << endl;

cout << "Base: ";cin >> b;cout << "Altezza: ";cin >> h;

c.setb(b);c.seth(h);cout << "Area del Rettangolo c: " << c.area() << endl;cout << "Base: " << c.getb() << " Altezza: " << c.geth() << endl;c.stampa();

d.set(10,4);cout << "Area del Rettangolo d: " << d.area() << endl;d.get(b, h); // lettura contestuale di base ed altezzacout << "Base: " << b << " Altezza: " << h << endl;d.stampa();

}

/* ------------------ output --------------------------Classe Rettangolo: parametri by reference / input.Base: 7Altezza: 5Area del Rettangolo c: 35Base: 7 Altezza: 5***********************************Area del Rettangolo d: 40Base: 10 Altezza: 4****************************************------------------------------------------------------- */


/*classe Rettangolo:- funzioni inline- overloading metodi di accesso

*/


class Rettangolo{

int _base;int _altezza;

public: // qui l'uso di inline e' facoltativoinline void get(int& b, int& h) { b=_base; h=_altezza; }inline void set(int b, int h) {


92

if(b>=0) // ha senso solo un valore non negativo_base=b;

if(h>=0) // ha senso solo un valore non negativo_altezza=h;

}inline int base() { return _base; }inline int altezza() { return _altezza; }inline void base(int b) {

if(b>=0) // ha senso solo un valore non negativo _base=b;}

inline void altezza(int h) {if(h>=0) // ha senso solo un valore non negativo

_altezza=h;}

int area();void stampa();};


return _base*_altezza;}

void Rettangolo::stampa(){

int r,c;

for(r=0; r<_altezza; r++) {for(c=0; c<_base; c++)


}

void main(){

Rettangolo c, d;int b, h;

cout << "Classe Rettangolo: funzioni inline." << endl;

cout << "Base: ";cin >> b;cout << "Altezza: ";cin >> h;

c.base(b); // modifico base ed altezza separatamentec.altezza(h);cout << "Area del Rettangolo c: " << c.area() << endl;cout << "Base: " << c.base() << " Altezza: " << c.altezza() << endl;c.stampa();

d.set(10,4); // modifico insieme base ed altezzacout << "Area del Rettangolo d: " << d.area() << endl;cout << "Base: " << d.base() << " Altezza: " << d.altezza() << endl;d.stampa();

}

/* ------------------ output --------------------------Classe Rettangolo: funzioni inline.Base: 7Altezza: 5Area del Rettangolo c: 35


93

Base: 7 Altezza: 5***********************************Area del Rettangolo d: 40Base: 10 Altezza: 4****************************************------------------------------------------------------- */


94

Lezione 12 - Programmazione orientata agli oggetti (III)

• Passaggio di parametri per riferimento

• Overloading di funzioni ed operatori

• Campi statici (variabili di classe)

• Allocazione dinamica: new, delete, puntatore this.

• Input/output in C++.

• Cenni di polimorfismo ed ereditarietà.

Riferimenti

Videocassette: lezioni 8-16 (solo cenni)



95


/*classe rettangolo:- costruttore di copia,- parametri di default,- parametri reference.

*/


class Rettangolo{


public:Rettangolo(int l=0); // costruttore per quadratiRettangolo(int b, int h); // costruttore per rettangoliRettangolo(const Rettangolo &r); // costruttore di copiaint area(void);void stampa(void);};


base=l;altezza=l;

}


base=b;altezza=h;

}

Rettangolo::Rettangolo(const Rettangolo &r) // costruttore di copia{

base=r.base;altezza=r.altezza;

}




int r,c;



}

void main(){

Rettangolo a, b(5), c(3,4), d(c);

cout << "Classe Rettangolo: costruttore di copia / parametri di default." << endl;


96

cout << "Area del Rettangolo a: " << a.area() << endl;a.stampa();cout << "Area del Rettangolo b: " << b.area() << endl;b.stampa();cout << "Area del Rettangolo c: " << c.area() << endl;c.stampa();cout << "Area del Rettangolo d: " << d.area() << endl;d.stampa();

}

/* ---------------------------- output ------------------------------Classe Rettangolo: costruttore di copia / parametri di default.Area del Rettangolo a: 0Area del Rettangolo b: 25*************************Area del Rettangolo c: 12************Area del Rettangolo d: 12************------------------------------------------------------------------- */


/*classe Rettangolo che conta le istanze create:- uso campi statici (stessa area di memoria per tutti gli oggetti di una classe;- allocazione dinamica di oggetti (new/delete).

*/


class Rettangolo{

int base;int altezza;static int istanze;

public:Rettangolo(int l=0); // costruttore per quadratiRettangolo(int b, int h); // costruttore per rettangoliRettangolo(Rettangolo &r); // costruttore di copia~Rettangolo(void); // distruttoreint area(void);void stampa(void);static int getistanze(void); // campo statico di conteggio};

int Rettangolo::istanze=0;


base=l;altezza=l;istanze++;


97

}


base=b;altezza=h;istanze++;

}

Rettangolo::Rettangolo(Rettangolo &r) // costruttore di copia{

base=r.base;altezza=r.altezza;istanze++;

}

Rettangolo::~Rettangolo(void) // distruttore{

istanze--;}

int Rettangolo::getistanze(void){

return istanze;}




int r,c;



}

void main(){

Rettangolo *pa, *pb; // allocazione dinamicaRettangolo c(6,2); // allocazione statica

cout << "Classe Rettangolo: campi statici / allocazione dinamica." << endl;

cout << "Numero di istanze: " << Rettangolo::getistanze() << endl;

cout << "Creo a" << endl;pa = new Rettangolo(3,4);cout << "Numero di istanze: " << Rettangolo::getistanze() << endl;

cout << "Creo b" << endl;pb = new Rettangolo(5);cout << "Numero di istanze: " << Rettangolo::getistanze() << endl;

cout << "Distruggo a" << endl;delete pa;cout << "Numero di istanze: " << Rettangolo::getistanze() << endl;

cout << "Distruggo b" << endl;


98

delete pb;cout << "Numero di istanze: " << Rettangolo::getistanze() << endl;

}

/* -------------------------- output -------------------------Classe Rettangolo: campi statici / allocazione dinamica.Numero di istanze: 1Creo aNumero di istanze: 2Creo bNumero di istanze: 3Distruggo aNumero di istanze: 2Distruggo bNumero di istanze: 1------------------------------------------------------------- */


/*classe Rettangolo che conta le istanze create:- operator overloading;- definizioni dentro i blocchi;- puntatore this.

*/


class Rettangolo{

int base;int altezza;static int istanze;

public:Rettangolo(int l=0); // costruttore per quadratiRettangolo(int b, int h); // costruttore per rettangoliRettangolo(Rettangolo &r); // costruttore di copia~Rettangolo(); // distruttoreint area();void stampa();static int getistanze(); // campo statico di conteggioRettangolo &operator=(const Rettangolo &r); // overloading assegnaz.};

int Rettangolo::istanze=0;


base=l;altezza=l;istanze++;

}


base=b;altezza=h;istanze++;

}

Rettangolo::Rettangolo(Rettangolo &r) // costruttore di copia{

base=r.base;


99

altezza=r.altezza;istanze++;

}

Rettangolo& Rettangolo::operator=(const Rettangolo &r) // operat. di assegnazione{

base=r.base;altezza=r.altezza;

return *this; // punta all'oggetto corrente}

Rettangolo::~Rettangolo() // distruttore{

istanze--;}

int Rettangolo::getistanze(){

return istanze;}




for(int r=0; r<altezza; r++) {for(int c=0; c<base; c++)


}

void main(){

cout << "Classe Rettangolo: operator overloading." << endl;

Rettangolo c(6,2); // definito prima dell'usocout << "Rettangolo c:" << endl;c.stampa();

Rettangolo d(2); // definito prima dell'usocout << "Rettangolo d prima dell'assegnazione:" << endl;d.stampa();d=c;cout << "Rettangolo d dopo l'assegnazione:" << endl;d.stampa();

}

/* -------------------------- output ----------------------Classe Rettangolo: operator overloading.Rettangolo c:************Rettangolo d prima dell'assegnazione:****Rettangolo d dopo l'assegnazione:************------------------------------------------------------------ */


100

Classe Complex

/*Classe che definisce i numeri complessi- funzioni friend- overloading operatore di output per i complessi

*/

#include <iostream.h>#include <math.h>

class Complex; // dichiarazione classe Complex

ostream& operator<<(ostream &os, const Complex &c);

class Complex// definizione classe Complex{

friend ostream& operator<<(ostream &os, const Complex &c);double _re; // parte realedouble _im; // parte immaginaria

public:Complex(double r=0, double i=0) { _re=r; _im=i; }Complex operator+(const Complex& c);double re() const { return _re; } // funzione inlinedouble im() const { return _im; }// funzione inlinevoid re(double r) { _re=r; } // funzione inlinevoid im(double i) { _im=i; } // funzione inline

};

Complex Complex::operator+(const Complex& c) // overload opr. somma{

Complex s;

s._re = _re + c._re;s._im = _im + c._im;return s;

}

ostream& operator<<(ostream &os, const Complex &c) // ovl. opr. output{

if(c.re() != 0 || c.im() == 0) // posso usare le funzioni di accessoos << c._re; // re() e im()

if(c._im != 0) { // o accedere direttamente ai campiif(c._im > 0) // privati (funzione friend)

if(c._re != 0)os << "+i";

elseos << "i";

elseos << "-i";

os << fabs(c._im);}

return os;}

void main(){

Complex x(-1,-2.5);Complex y(3);Complex z;Complex k0( 0, 0);Complex k1( 0,+6);Complex k2( 0,-6);Complex k3(+3, 0);


101

Complex k4(+3,+6);Complex k5(+3,-6);Complex k6(-3, 0);Complex k7(-3,+6);Complex k8(-3,-6);

cout << "Classe per la gestione di numeri complessi." << endl;

z=x+y;

cout << x << endl;cout << y << endl;cout << z << endl;

cout << k0 << endl;cout << k1 << endl;cout << k2 << endl;cout << k3 << endl;cout << k4 << endl;cout << k5 << endl;cout << k6 << endl;cout << k7 << endl;cout << k8 << endl;

}

/* --------------------- output -------------------------Classe per la gestione di numeri complessi.-1-i2.532-i2.50i6-i633+i63-i6-3-3+i6-3-i6-------------------------------------------------------- */

Classe Individuo

/*Classe che definisce i dati anagrafici di un individuo:- allocazione dinamica (new/delete)- parametri di default- operatore di copia (necessario)- distruttore (necessario)

*/

#include <iostream.h>#include <string.h>

class Individuo{

char *_nome;char *_cognome;int _eta;

public:Individuo(char *n=0, char *c=0, int eta=0);Individuo(const Individuo &i); // costr. di copia - necessario~Individuo(); // distruttore - necessarioconst char *nome() { return _nome; }


102

const char *cognome() { return _cognome; }int eta() { return _eta; }const Individuo &operator=(const Individuo &i);

}

Individuo::Individuo(char *n, char *c, int e) // costruttore{

_nome = new char[strlen(n)+1];strcpy(_nome, n);_cognome = new char[strlen(c)+1];strcpy(_cognome, c);_eta = e;

}

Individuo::Individuo(const Individuo &i) // costruttore di copia{

_nome = new char[strlen(i._nome)+1];strcpy(_nome, i._nome);_cognome = new char[strlen(i._cognome)+1];strcpy(_cognome, i._cognome);_eta = i._eta;

}

Individuo::~Individuo() // distruttore{

delete [] _nome;delete [] _cognome;

}

const Individuo& Individuo::operator=(const Individuo &i) // overload assegn.{

_nome = new char[strlen(i._nome)+1];strcpy(_nome, i._nome);_cognome = new char[strlen(i._cognome)+1];strcpy(_cognome, i._cognome);_eta = i._eta;

return *this;}

void main(){

cout << "Esempio di oggetti con parte statica e dinamica." << endl;

Individuo a("Mario", "Rossi", 40);Individuo b("Luigi", "Neri", 25);Individuo c;Individuo d(a); // costr. di copiachar co[30];char no[30];int et;

c=b; // assegnaz. overload.

cout << "Cognome: ";cin >> co;cout << "Nome: ";cin >> no;cout << "Eta': ";cin >> et;Individuo e(no, co, et);

cout << a.nome() << " " << a.cognome() << " di anni "<< a.eta() << endl;


103

cout << b.nome() << " " << b.cognome() << " di anni "<< b.eta() << endl;

cout << c.nome() << " " << c.cognome() << " di anni "<< c.eta() << endl;

cout << d.nome() << " " << d.cognome() << " di anni "<< d.eta() << endl;

cout << e.nome() << " " << e.cognome() << " di anni "<< e.eta() << endl;

}

Fondamenti di Informatica IIIcorsiadistanza.polito.it/corsi/pdf/9255N/fondinf3-03.pdf · 2000. 11....

Documents

Transcript of Fondamenti di Informatica IIIcorsiadistanza.polito.it/corsi/pdf/9255N/fondinf3-03.pdf · 2000. 11....