G. Amodeo,
C. Gaibisso
Programmazione di Calcolatori
Lezione XXV:
gli stack e i vettori
Programmazione di Calcolatori: gli stack e i vettori
1
G. Amodeo,
C. Gaibisso
Stack di interi e array
• Graficamente:
dimensione
massima
dello stack
posizione
all’interno
dell’array
dell’elemento
affiorante
dello stack
stck[max_dim-1]
struct stoi
max_dim
int
testa
int
stck
max_dim
int *
array per la
memorizzazione
dei valori nello
stack
stck[0]
Programmazione di Calcolatori: gli stack e i vettori
2
G. Amodeo,
C. Gaibisso
Stack di interi: definizione dei tipi
// definizione del tipo strutturato stack di interi
struct stoi {
// dimensione massima dello stack
int max_dim;
// posizione nel vettore dell'elemento
// affiorante dello stack
int testa;
// riferimento al vettore che memorizza gli
// elementi dello stack
int *stck;
};
Programmazione di Calcolatori: gli stack e i vettori
3
G. Amodeo,
C. Gaibisso
InitStack()
• La logica:
stck[dim-1]
struct stoi stack
max_dim
testa
dim
dim
-1
stck
stck[0]
Programmazione di Calcolatori: gli stack e i vettori
4
G. Amodeo,
C. Gaibisso
InitStack()
• La funzione:
Programmazione di Calcolatori: gli stack e i vettori
Continua …
// alloca memoria e inizializza le variabili per uno stack di interi
// di dimensione massima pari al valore del parametro
struct stoi *stoiIni (int dim)
{
// definisce un puntatore alla variabile strutturata per lo stack
struct stoi *stack;
// alloca memoria per la variabile strutturata
stack = (struct stoi *) malloc(sizeof(struct stoi));
// testa l'esito dell'allocazione. Se negativo termina con NULL
if (stack == NULL)
return(NULL);
// altrimenti, alloca memoria per il vettore che memorizzera’ i
// valori dello stack
stack -> stck = (int *) malloc(dim * sizeof(int));
// testa l'esito dell'allocazione. Se negativo recupera la memoria
// gia' allocata e termina con NULL
if (stack -> stck == NULL)
{
free(stack);
return(NULL);
};
5
G. Amodeo,
C. Gaibisso
InitStack()
// nella variabile strutturata, inizializza la dimensione massima dello
// stack
stack -> max_dim = dim;
// nella variabile strutturata, inizializza la posizione nel vettore
// dell’elemento affiorante dello stack
stack -> testa = EMPTY_STACK;
// restituisce il riferimento variabile strutturata per lo stack
return(stack);
};
Programmazione di Calcolatori: gli stack e i vettori
6
G. Amodeo,
C. Gaibisso
Push()
• La logica:
stck[dim-1]
struct stoi stack
max_dim
dim
dim
testa
stck
X
stck[0]
Programmazione di Calcolatori: gli stack e i vettori
7
G. Amodeo,
C. Gaibisso
Push()
• La funzione:
// inserisce sullo stack il valore passato come parametro
int push(struct stoi *stack, int valore)
{
// se lo stack contiene il numero massimo di elementi previsto
// termina con esito negativo
if (stoiFull(*stack) == TRUE)
return(NEG_RESULT);
// altrimenti inserisce il nuovo elemento sullo stack
stack->stck[stack->testa+1] = valore;
// aggiorna la posizione nel vettore dell'elemento affiorante
stack->testa = stack->testa + 1;
// termina con esito positivo
return(POS_RESULT);
};
Programmazione di Calcolatori: gli stack e i vettori
8
G. Amodeo,
C. Gaibisso
Pop()
• La logica:
stck[dim-1]
struct stoi stack
max_dim
dim
dim
testa
stck
X
valore
valore
int val
stck[0]
Programmazione di Calcolatori: gli stack e i vettori
9
G. Amodeo,
C. Gaibisso
Pop()
• La funzione:
// se lo stack non e' vuoto, accede al valore memorizzato dall'elemento
// affiorante, lo memorizza nella variabile riferita dal parametro e
// termina con esito positivo. Termina con esito negativo, altrimenti.
int pop(struct stoi *stack, int *val)
{
// se lo stack e' vuoto termina con esito negativo
if (stoiEmpty(*stack))
return(NEG_RESULT);
// altrimenti memorizza nella variabile riferita dal parametro val il
// valore dell’elemento affiorante dello stack
*val = stack->stck[stack->testa];
// aggiorna la posizione nel vettore dell'elemento affiorante dello stack
stack->testa = stack->testa-1;
// termina con esito positivo
return(POS_RESULT);
};
Programmazione di Calcolatori: gli stack e i vettori
10
G. Amodeo,
C. Gaibisso
Top()
• La logica:
stck[dim-1]
struct stoi stack
max_dim
dim
dim
testa
stck
valore
valore
int val
stck[0]
Programmazione di Calcolatori: gli stack e i vettori
11
G. Amodeo,
C. Gaibisso
Top()
• La funzione:
// se lo stack non e' vuoto, accede al valore memorizzato dell'elemento
// affiorante, lo memorizza nella variabile riferita dal parametro e termina
// con esito positivo. Altrimenti, termina con esito negativo
int top(struct stoi stack, int *val)
{
// se lo stack e' vuoto termina con esito negativo
if (stoiEmpty(stack))
return(NEG_RESULT);
// altrimenti memorizza nella variabile riferita dal parametro val il
// valore sulla testa dello stack
*val = stack.stck[stack.testa];
// termina con esito positivo
return(POS_RESULT);
};
Programmazione di Calcolatori: gli stack e i vettori
12
G. Amodeo,
C. Gaibisso
Gestione di una lista di interi
• Specifiche:
implementare una soluzione per il tipo di dato
astratto stack di interi che preveda le seguenti
operazioni:
1.
2.
3.
4.
5.
6.
7.
inizializzazione
Push()
Top()
Pop()
visualizzazione del contenuto
test di stack vuoto
reset
Programmazione di Calcolatori: gli stack e i vettori
13
G. Amodeo,
C. Gaibisso
Organizzazione del codice: file e loro contenuto
• Definizione dei tipi:
– stoi_tipi.h: definizioni dei tipi, strutturati e non, utilizzati
nella implementazione del tipo di dato
astratto “stack of integer” (stoi)
• Codice sorgente:
– stoi_main.c: codice per l’attivazione delle operazioni
implementate per il tipo di dato astratto
stoi
– stoi_ges.c: definizione delle funzioni che implementano
le operazioni definite sul tipo di dato
astratto stoi
– stoi_uti.c:
definizione delle utilities di supporto alle
funzioni che implementano le operazioni
definite sul tipo di dato astratto stoi
Programmazione di Calcolatori: gli stack e i vettori
14
G. Amodeo,
C. Gaibisso
Organizzazione del codice: file e loro contenuto
• Dichiarazioni extern
– stoi_ges.h:
– stoi_uti.h:
dichiarazioni extern delle funzioni che
implementano le operazioni definite sul tipo
di dato astratto stoi
dichiarazioni extern delle utilities di
supporto alle funzioni che implementano le
operazioni definite sul tipo di dato astratto
stoi
• Pseudodichiarazioni:
– stoi_const.h: pseudodichiarazioni per le costanti
simboliche utilizzate nella implementazione
del tipo di dato astratto stoi
– stoi_msg.h: pseudodichiarazioni per i messaggi
restituiti nella implementazione del tipo di
dato astratto stoi
Programmazione di Calcolatori: gli stack e i vettori
15
G. Amodeo,
C. Gaibisso
Gestione di una lista di interi: file stoi_tipi.h
// Nome e posizione del file:
//
Lezione_XXV/stoi_tipi.h
// Descrizione del contenuto del file:
//
definizioni dei tipi, strutturati e non, utilizzati nella
//
implementazione del tipo di dato astratto “stack of integer”
//
tramite un vettore di interi
// definizione del tipo strutturato
// stack di interi
struct stoi
{
// dimensione massima della istanza
int max_dim;
// posizione nel vettore dell'elemento affiorante della
istanza
int testa;
// riferimento al vettore che memorizza gli elementi
// della istanza
int *stck;
};
Programmazione di Calcolatori: gli stack e i vettori
16
G. Amodeo,
C. Gaibisso
Gestione di una lista di interi: file stoi_ges.c
Programmazione di Calcolatori: gli stack e i vettori
Continua …
// Nome e posizione del file:
//
Lezione_XXV/lista/stoi_ges.c
// Descrizione del contenuto del file:
//
definizione delle funzioni che implementano le operazioni definite
//
sul tipo di dato astratto "stack of integer"
// PSEUDODICHIARAZIONI
// pseudodichiarazioni per i messaggi restituiti nella implementazione del
// tipo di dato astratto "stack of integer"
#include "./stoi_msg.h"
// pseudodichiarazioni per le costanti simboliche utilizzate nella
// implementazione del tipo di dato astratto "stack of integer"
#include "./stoi_const.h"
// DEFINIZIONI DI TIPO
// definizioni dei tipi, strutturati e non, utilizzati nella implementazione
// del tipo di dato astratto “stack of integer” tramite un vettore di interi
#include "./stoi_tipi.h"
// EXTERN
// inclusione del file di intestazione della libreria
// standard che contiene definizioni di macro,
// costanti e dichiarazioni di funzioni e tipi funzionali
// alle varie operazioni di I/O
#include <stdio.h>
17
G. Amodeo,
C. Gaibisso
Gestione di una lista di interi: file stoi_ges.c
Programmazione di Calcolatori: gli stack e i vettori
Continua …
// inclusione del file di intestazione della libreria che contiene
// definizioni di macro, costanti e dichiarazioni di funzioni e tipi
// di interesse generale
#include <stdlib.h>
// dichiarazioni extern delle utilities di supporto alle funzioni che
// implementano le operazioni definite sul tipo di dato astratto
// “stack of integer”
#include "./stoi_uti.h“
18
G. Amodeo,
C. Gaibisso
Gestione di una lista di interi: file stoi_ges.c
Programmazione di Calcolatori: gli stack e i vettori
Continua …
// Nome della funzione:
//
stoiEmpty()
// Tipo, nome e significato dei parametri della funzione:
//
struct stoi stack: descrittore della istanza del tipo
//
di dato astratto "stack of integer"
// Descrizione della funzionalita' implementata:
//
implementa il test di istanza vuota
// Tipo e significato del valore restituito:
//
int:
TRUE se l’istanza è vuota;
//
FALSE altrimenti
int stoiEmpty(struct stoi stack)
{
// restituisce TRUE se l’istanza è vuota, FALSE altrimenti
if (stack.testa == EMPTY_STACK)
return(TRUE);
else
return(FALSE);
};
19
G. Amodeo,
C. Gaibisso
Gestione di una lista di interi: file stoi_ges.c
Continua …
// Nome della funzione:
//
push()
// Tipo, nome e significato dei parametri della funzione:
//
struct stoi *stack: riferimento al descrittore dell’istanza del tipo di
//
dato astratto “stack of integer”
//
int valore:
valore da inserire nell'istanza
// Descrizione della funzionalita' implementata:
//
inserisce un nuovo valore nell’istanza del tipo di dato astratto “stack of
//
integer”
// Tipo e significato del valore restituito:
//
int:
POS_RESULT se l'operazione ha esito positivo;
//
NEG_RESULT altrimenti
int push(struct stoi *stack, int valore)
{
// se l’istanza contiene il numero massimo di elementi previsto
// termina con esito negativo
if (stoiFull(*stack) == TRUE)
return(NEG_RESULT);
// altrimenti inserisce il nuovo elemento nell’istanza
stack->stck[stack->testa+1] = valore;
// aggiorna la posizione dell'elemento affiorante nel vettore
stack->testa = stack->testa + 1;
// termina con esito positivo
return(POS_RESULT);
};
Programmazione di Calcolatori: gli stack e i vettori
20
G. Amodeo,
C. Gaibisso
Gestione di una lista di interi: file stoi_ges.c
Continua …
// Nome della funzione:
//
stoiVis()
// Tipo, nome e significato dei parametri della funzione:
//
struct stoi stack: descrittore dell’istanza del tipo di dato astratto
//
“stack of integer”
// Descrizione della funzionalita' implementata:
//
visualizza l’istanza di un tipo di dato astratto “stack of integer”: gli
//
interi sono visualizzati in ordine inverso rispetto a quello di inserimento
// Tipo e significato del valore restituito:
//
alcuno
void stoiVis (struct stoi stack)
{
// visualizza la dimensione massima e la dimensione attuale dell’istanza
printf(MAX_DIM, stack.max_dim);
printf(NUMB_OF_ITEMS, stack.testa+1);
// se l'istanza e' vuota visualizza un opportuno messaggio e termina
if (stoiEmpty(stack)) printf(EMPTY_STOI);
else // altrimenti
{
int curs; // definisce un cursore
// scandisce l'array riferito dal descrittore
for (curs = stack.testa; curs >= 0; curs--)
printf(" <- %d", stack.stck[curs]); // visualizza l'elemento corrente
};
};
Programmazione di Calcolatori: gli stack e i vettori
21
G. Amodeo,
C. Gaibisso
Gestione di una lista di interi: file stoi_ges.c
Continua …
// Nome della funzione:
//
top()
// Tipo, nome e significato dei parametri della funzione:
//
struct stoi stack: descrittore dell’istanza del tipo di dato astratto
//
“stack of integer”
//
int *val:
riferimento alla variabile nella quale memorizzare
//
il valore dell'elemento affiorante dell’istanza
// Descrizione della funzionalita' implementata:
//
se l’istanza non e' vuota, accede al valore memorizzato dell'elemento
//
affiorante, lo memorizza nella variabile riferita dal parametro e termina
//
con esito positivo. Altrimenti, termina con esito negativo
// Tipo e significato del valore restituito:
//
int:
POS_RESULT se l’istanza non e' vuota;
//
NEG_RESULT altrimenti
int top(struct stoi stack, int *val)
{
// se l’istanza non e' vuota termina con esito negativo
if (stoiEmpty(stack))
return(NEG_RESULT);
// altrimenti memorizza nella variabile riferita dal parametro il valore
// affiorante dell’istanza
*val = stack.stck[stack.testa];
// termina con esito positivo
return(POS_RESULT);
};
Programmazione di Calcolatori: gli stack e i vettori
22
G. Amodeo,
C. Gaibisso
Gestione di una lista di interi: file stoi_ges.c
Continua …
// Nome della funzione:
//
pop()
// Tipo, nome e significato dei parametri della funzione:
//
struct stoi *stack: riferimento al descrittore dell’istanza del tipo di
//
dato astratto “stack of integer”
//
int *val:
riferimento alla variabile nella quale memorizzare
//
il valore dell'elemento affiorante dell’istanza
// Descrizione della funzionalita' implementata:
//
se l’istanza non e' vuota, accede al valore memorizzato dall'elemento
//
affiorante, lo memorizza nella variabile riferita dal parametro e
//
termina con esito positivo. Termina con esito negativo, altrimenti.
// Tipo e significato del valore restituito:
//
int:
POS_RESULT se l’istanza non e' vuota;
//
NEG_RESULT altrimenti
int pop(struct stoi *stack, int *val)
{
// se l’istanza e' vuota termina con esito negativo
if (stoiEmpty(*stack)) return(NEG_RESULT);
// altrimenti memorizza nella variabile riferita dal parametro il valore
// dell’elemento affiorante della istanza
*val = stack->stck[stack->testa];
// aggiorna la posizione nel vettore dell'elemento affiorante dell’istanza
stack->testa = stack->testa-1;
// termina con esito positivo
return(POS_RESULT);
};
Programmazione di Calcolatori: gli stack e i vettori
23
G. Amodeo,
C. Gaibisso
Gestione di una lista di interi: file stoi_ges.c
Continua …
// Nome della funzione:
//
stoiNew()
// Tipo, nome e significato dei parametri della funzione:
//
int dim:
dimensione massima della istanza del tipo di dato astratto
//
“stack of integer”
// Descrizione della funzionalita' implementata:
//
crea una nuova istanza del tipo di dato astratto "stack of integer" e la
//
inizializza
// Tipo e significato del valore restituito:
//
struct stoi *: riferimento al descrittore di una istanza del tipo di dato
//
astratto “stack of integer”, se l'allocazione ha esito
//
positivo; NULL, altrimenti.
struct stoi *stoiNew (int dim)
{
// definisce un puntatore al descrittore dell'istanza del tipo di dato
// astratto "stack of integer"
struct stoi *descr;
// alloca memoria per l'istanza
descr = stoiAllMem(dim);
// testa l'esito dell'allocazione. Se negativo termina con NULL
if (descr == NULL) return(NULL);
// inizializza il descrittore dell'istanza
stoiInit (dim, descr);
// restituisce il riferimento al descrittore della nuova istanza
return(descr);
};
Programmazione di Calcolatori: gli stack e i vettori
24
G. Amodeo,
C. Gaibisso
Gestione di una lista di interi: file stoi_ges.c
// Nome della funzione:
//
stoiReset()
// Tipo, nome e significato dei parametri della funzione:
//
struct stoi *stack: riferimento al descrittore dell’istanza del tipo di
//
dato astratto “stack of integer”
// Descrizione della funzionalita' implementata:
//
azzera il contenuto dell’istanza
// Tipo e significato del valore restituito:
//
alcuno
void stoiReset (struct stoi *stack)
{
// aggiorna la posizione nel vettore dell'elemento affiorante dell’istanza
stack -> testa = EMPTY_STACK;
};
Programmazione di Calcolatori: gli stack e i vettori
25
G. Amodeo,
C. Gaibisso
Gestione di un Stack di interi: file stoi_ges.h
// Nome e posizione del file:
//
Lezione_XXIV/stoi_ges.h
// Descrizione del contenuto del file:
//
contiene le dichiarazioni extern delle funzioni che implementano le
//
operazioni definite sul tipo di dato astratto “stack of integer”
extern int stoiEmpty(struct stoi);
extern int push(struct stoi *, int);
extern void stoiVis(struct stoi);
extern int top(struct stoi, int *);
extern int pop(struct stoi *, int *);
extern void stoiReset (struct stoi *);
extern struct stoi * stoiNew(int);
Programmazione di Calcolatori: gli stack e i vettori
26
G. Amodeo,
C. Gaibisso
Gestione di una lista di interi: file stoi_uti.c
Programmazione di Calcolatori: gli stack e i vettori
Continua …
// Nome e posizione del file:
//
Lezione_XXV/stoi_uti.c
// Descrizione del contenuto del file:
//
definizione delle utilities di supporto alle funzioni che implementano
//
le operazioni definite sul tipo di dato astratto "stack of integer"
// PSEUDODICHIARAZIONI
// pseudodichiarazioni per le costanti simboliche utilizzate nella
// implementazione del tipo di dato astratto "stack of integer"
#include "./stoi_const.h"
// DEFINIZIONI DI TIPO
// definizioni dei tipi, strutturati e non, utilizzati nella implementazione
// del tipo di dato astratto “stack of integer” tramite un vettore
#include "./stoi_tipi.h"
// EXTERN
// inclusione del file di intestazione della libreria che contiene
// definizioni di macro, costanti e dichiarazioni di funzioni e tipi
// di interesse generale
#include <stdlib.h>
27
G. Amodeo,
C. Gaibisso
Gestione di una lista di interi: file stoi_uti.c
// Nome della funzione:
//
stoiFree()
// Tipo, nome e significato dei parametri della funzione:
//
struct stoi *stack: riferimento al descrittore dell’istanza del tipo di
//
dato astratto “stack of integer”
// Descrizione della funzionalita' implementata:
//
libera la memoria allocata per l’istanza
// Tipo e significato del valore restituito:
//
alcuno
void stoiFree (struct stoi *stack)
{
// libera la memoria allocata per il vettore che memorizza i valori
// dell’istanza
free(stack -> stck);
// libera la memoria allocata per il descrittore dell’istanza
free(stack);
};
Continua …
Programmazione di Calcolatori: gli stack e i vettori
28
G. Amodeo,
C. Gaibisso
Gestione di una lista di interi: file stoi_uti.c
Programmazione di Calcolatori: gli stack e i vettori
Continua …
// Nome della funzione:
//
stoiFull()
// Tipo, nome e significato dei parametri della funzione:
//
struct stoi stack: descrittore dell’istanza del tipo di
//
dato astratto “stack of integer”
// Descrizione della funzionalita' implementata:
//
testa se l’istanza ha raggiunto la sua capacità massima
// Tipo e significato del valore restituito:
//
int:
TRUE se l’istanza è vuota;
//
FALSE altrimenti
int stoiFull(struct stoi stack)
{
// restituisce TRUE se l’istanza ha raggiunto la sua dimensione massima,
// FALSE altrimenti
if (stack.max_dim == (stack.testa)+1)
return(TRUE);
else
return(FALSE);
};
29
G. Amodeo,
C. Gaibisso
Gestione di una lista di interi: file stoi_uti.c
Programmazione di Calcolatori: gli stack e i vettori
Continua …
// Nome della funzione:
//
stoiAllMem()
// Tipo, nome e significato dei parametri della funzione:
//
int dim:
dimensione massima della istanza del tipo di dato
//
astratto "stack of integer"
// Descrizione della funzionalita' implementata:
//
alloca memoria per una istanza del tipo di dato astratto "stack of
//
integer"
// Tipo e significato del valore restituito:
//
struct stoi *: indirizzo del descrittore dello stack,
//
se l'operazione ha esito positivo;
//
NULL altrimenti.
struct stoi * stoiAllMem (int dim)
{
// definisce un puntatore per il descrittore della istanza
struct stoi *descr;
// alloca memoria per il descrittore
descr = (struct stoi *) malloc(sizeof(struct stoi));
// testa l'esito dell'allocazione. Se negativo termina con NULL
if (descr == NULL)
return(NULL);
// altrimenti alloca memoria per l’array che memorizza gli elementi
// dello stack
descr -> stck = (int *)(malloc(dim * sizeof(int)));
30
G. Amodeo,
C. Gaibisso
Gestione di una lista di interi: file stoi_uti.c
// testa l'esito dell'allocazione. Se negativo recupera la memoria
// per il descrittore e termina con NULL
if (descr -> stck == NULL)
{
free(descr);
return(NULL);
};
// restituisce l'indirizzo del descrittore se l'operazione
// ha esito positivo. NULL altrimenti
return(descr);
};
Continua …
Programmazione di Calcolatori: gli stack e i vettori
31
G. Amodeo,
C. Gaibisso
Gestione di una lista di interi: file stoi_uti.c
// Nome della funzione:
//
stoiInit()
// Tipo, nome e significato dei parametri della funzione:
//
int dim:
dimensione massima dello stack
//
struct stoi *descr: riferimento al descrittore di una istanza del tipo di
//
dato astratto "stack of integer"
// Descrizione della funzionalita' implementata:
//
inizializza il descrittore di una istanza del tipo di dato estratto
//
"stack of integer"
// Tipo e significato del valore restituito:
//
alcuno
void stoiInit (int dim, struct stoi *descr)
{
// inizializza l'informazione relativa alla dimensione massima della
// istanza
descr -> max_dim = dim;
// inizializza la posizione dell'elemento affiorante
descr -> testa = EMPTY_STACK;
};
Programmazione di Calcolatori: gli stack e i vettori
32
G. Amodeo,
C. Gaibisso
Gestione di una lista di interi: file ldi_uti.h
// Nome e posizione del file:
//
Lezione_XXV/stoi_uti.h
// Descrizione del contenuto del file:
//
contiene le dichiarazioni extern delle utilities di supporto alle
//
funzioni che implementano le operazioni definite sul tipo di
//
dato astratto "stack of integer"
extern void stoiFree(struct stoi *);
extern int stoiFull(struct stoi);
extern struct stoi *stoiAllMem (int);
extern void stoiInit (int, struct stoi *descr)
Programmazione di Calcolatori: gli stack e i vettori
33
G. Amodeo,
C. Gaibisso
Gestione di una lista di interi: file stoi_main.c
Programmazione di Calcolatori: gli stack e i vettori
Continua …
// Nome e posizione del file:
//
Lezione_XXV/stoi_main.c
// Descrizione del contenuto del file:
//
codice per l’attivazione delle funzionalità per la gestione di una
//
istanza del tipo di dato astratto "stack of integer"
// PSEUDODICHIARAZIONI
// pseudodichiarazioni per i messaggi restituiti nella implementazione del
// tipo di dato astratto "stack of integer"
#include "./stoi_msg.h"
// pseudodichiarazioni per le costanti simboliche utilizzate nella
// implementazione del tipo di dato astratto "stack of integer"
#include "./stoi_const.h"
// DEFINIZIONI DI TIPO
// definizioni dei tipi, strutturati e non, utilizzati nella implementazione
// del tipo di dato astratto “stack of integer” tramite un vettore
#include "./stoi_tipi.h"
// EXTERN
// inclusione del file di intestazione della libreria
// standard che contiene definizioni di macro,
// costanti e dichiarazioni di funzioni e tipi funzionali
// alle varie operazioni di I/O
#include <stdio.h>
34
G. Amodeo,
C. Gaibisso
Gestione di una lista di interi: file stoi_main.c
// dichiarazioni extern delle utilities di supporto alle funzioni che
// implementano le operazioni definite sul tipo di dato astratto
// “stack of integer”
#include "./stoi_uti.h"
// dichiarazioni extern delle funzioni che
// implementano le operazioni definite sul tipo di dato astratto
// “stack of integer”
#include "./stoi_ges.h"
Continua …
Programmazione di Calcolatori: gli stack e i vettori
35
G. Amodeo,
C. Gaibisso
Gestione di una lista di interi: file stoi_main.c
Continua …
// Nome della funzione:
//
stoiMenu()
// Tipo, nome e significato dei parametri della funzione:
//
struct stoi *stack: riferimento al descrittore di una istanza del tipo
//
di dato astratto “stack of integer”
// Descrizione della funzionalita' implementata:
//
implementa il menu di scelta delle operazioni definite sul tipo di dato
//
astratto "stack of integer"
// Tipo e significato del valore restituito:
//
alcuno
void stoiMenu(struct stoi *stack)
{
// definisce e inizializza la variabile
// che permette l'uscita dal programma
int quit = 0;
// definisce una variabile per i valori oggetto della push()
// e risultato della top() e della pop()
int valore;
Programmazione di Calcolatori: gli stack e i vettori
36
G. Amodeo,
C. Gaibisso
Gestione di una lista di interi: file stoi_main.c
Programmazione di Calcolatori: gli stack e i vettori
Continua …
// rimane nel ciclo finche' la variabile quit rimane uguale a 0
while(!quit)
{
// definisce la variabile che memorizza la selezione
int selezione;
// visualizza le possibili scelte
printf(SELECT_FUN_STOI);
printf(PUSH);
printf(TOP);
printf(POP);
printf(RESET_LOI);
printf(DISPLAY_STOI);
printf(EMPTY_STOI_TEST);
printf(LEAVE_MAN_STOI);
printf(SELECT_OP_STOI);
// acquisisce la scelta
scanf("%d", &selezione);
// discrimina tra le diverse scelte
switch (selezione)
{
37
G. Amodeo,
C. Gaibisso
Gestione di una lista di interi: file stoi_main.c
Programmazione di Calcolatori: gli stack e i vettori
Continua …
case 1:
// Push()
// acquisisce il valore oggetto della push()
printf(ITEM_VALUE_REQ);
scanf("%d", &valore);
// chiama la funzione che implementa la funzione Push(),
// testa l'esito dell'operazione e lo visualizza
if (push(stack, valore) == POS_RESULT)
printf(POS_RES_MSG);
else
{
printf(NEG_RES_MSG);
printf(STACK_SIZE_EXC);
};
break;
case 2:
// Top()
// chiama la funzione che implementa l'operazione Top(),
// valuta l'esito dell'operazione e lo visualizza. Se
// l'esito e' positivo visualizza il valore affiorante
// della istanza del tipo di dato astratto "stack of integer"
if (top(*stack, &valore) == POS_RESULT)
printf("\nTop(): %d\n", valore);
else
printf(POP_FAILED);
break;
38
G. Amodeo,
C. Gaibisso
Gestione di una lista di interi: file stoi_main.c
Programmazione di Calcolatori: gli stack e i vettori
Continua …
case 3:
// Pop()
// chiama la funzione che implementa l'operazione Pop(),
// valuta l'esito dell'operazione e lo visualizza. Se
// l'esito e' positivo visualizza il valore affiorante
// della istanza del tipo di dato astratto "stack of integer"
if (pop(stack, &valore) == POS_RESULT)
printf("\nPop(): %d\n", valore);
else
printf(TOP_FAILED);
break;
case 4:
// reset dell’istanza del tipo di dato “stack of integer”
// chiama la funziona che azzera l’istanza
stoiReset(stack);
break;
case 5:
// visualizzazione dell’istanza del tipo di dato “stack
// of integer”
// chiama la funzione che visualizza il contenuto dell’istanza
stoiVis(*stack);
break;
39
G. Amodeo,
C. Gaibisso
Gestione di una lista di interi: file stoi_main.c
Programmazione di Calcolatori: gli stack e i vettori
Continua …
};
};
case 6:
// test di istanza vuota
// chiama la funzione che testa se una istanza del tipo di dato
// astratto "stack of integer" è vuota e visualizza il risultato
// il risultato del test
if (stoiEmpty(*stack))
printf(EMPTY_STOI);
else
printf(NOT_EMPTY_STOI);
break;
case 7:
// uscita
quit = 1;
break;
default:
// selezione errata
printf(WRONG_SELECTION);
};
40
G. Amodeo,
C. Gaibisso
Gestione di una lista di interi: file stoi_main.c
Continua …
// Nome della funzione:
//
main()
// Tipo, nome e significato dei parametri della funzione:
//
alcuno
// Descrizione della funzionalita' implementata:
//
chiamante
// Tipo e significato del valore restituito:
//
alcuno
int main()
{
// definisce un puntatore al descrittore della istanza del tipo di dato astratto
// “stack of integer”
struct stoi *stack;
// definisce una variabile per la dimensione massima della istanza
int max_dim;
// acquisisce il valore della dimensione massima della istanza
printf(MAX_DIM_REQ); scanf("%d", &max_dim);
// crea una nuova istanza del tipo di dato astratto "stack of integer"
stack = stoiInit(max_dim);
// se l'operazione ha esito negativo visualizza un opportuno
// messaggio e termina
if (stack == NULL)
{
printf(STACK_INIT_FAILED);
return(0);
};
Programmazione di Calcolatori: gli stack e i vettori
41
G. Amodeo,
C. Gaibisso
Gestione di una lista di interi: file stoi_main.c
// chiama la funzione che implementa il menu di scelta
// delle funzionalita' di gestione di una istanza del tipo di dato astratto
// “stack of integer”
stoiMenu(stack);
// recupera la memoria allocata per l’istanza
stoiFree(stack);
return(1);
};
Continua …
Programmazione di Calcolatori: gli stack e i vettori
42
G. Amodeo,
C. Gaibisso
Gestione di una lista di interi: file stoi_const.h
// Nome e posizione del file:
//
Lezione_XXV/stoi_const.h
// Descrizione del contenuto del file:
//
pseudodichiarazioni per le costanti simboliche utilizzate nella
//
implementazione del tipo di dato astratto "stack of integer“
// definizione delle costanti simboliche utilizzate nella
// inizializzazione di istanze del tipo di dato astratto "stack of integer"
#define EMPTY_STACK
-1
// definizione delle costanti simboliche per gli esiti di una
// operazione
#define NEG_RESULT
0
#define POS_RESULT
1
// definizione delle costanti mnemoniche per gli esiti di un test
#define TRUE
1
#define FALSE
0
Programmazione di Calcolatori: gli stack e i vettori
43
G. Amodeo,
C. Gaibisso
Gestione di una lista di interi: file stoi_msg.h
Continua …
// Nome e posizione del file:
//
Lezione_XXV/stoi_msg.h
// Descrizione del contenuto del file:
//
pseudodichiarazioni per i messaggi restituiti nella implementazione del
//
tipo di dato astratto "stack of integer"
// definizione delle costanti simboliche utilizzate per il menu
#define SELECT_FUN_STOI
"\nSelezionare Funzionalita'\n"
#define PUSH
"\n1: Push()"
#define TOP
"\n2: Top()"
#define POP
"\n3: Pop()"
#define RESET_LOI
"\n4: Azzera lo stack"
#define DISPLAY_STOI
"\n5: Visualizza lo stack"
#define EMPTY_STOI_TEST
"\n6: Test di stack vuoto"
#define LEAVE_MAN_STOI
"\n7: Interrompi"
#define SELECT_OP_STOI
"\n\nSelezione: "
#define WRONG_SELECTION "\nSelezionare 1, 2, 3, 4, 5, 6 o 7"
// definizione dei messaggi di descrizione per l'esito delle
// operazioni
#define STACK_INIT_FAILED
"\nInizializzazione stack fallita"
#define STACK_SIZE_EXC
"\nPush() fallita: stack pieno\n"
#define POP_FAILED
"\nPop() fallita: stack vuoto\n"
#define TOP_FAILED
"\nTop() fallita: stack vuoto\n"
// definizione dei messaggi descrittivi delle istanze
#define EMPTY_STOI
"\nStack vuoto\n"
#define NOT_EMPTY_STOI
"\nStack non vuoto\n"
#define STOI
"\nStack: “
Programmazione di Calcolatori: gli stack e i vettori
44
G. Amodeo,
C. Gaibisso
Gestione di una lista di interi: file stoi_msg.h
// definizione dei messaggi per l'esito delle operazioni
#define NEG_RES_MSG
"\nOperazione fallita\n"
#define POS_RES_MSG
"\nOperazione terminata con successo\n"
// definizione delle costanti simboliche utilizzate nell'acquisizione dei dati
#define ITEM_VALUE_REQ
"\nPush(?): "
#define MAX_DIM_REQ
"\nDimensione massima dello stack? "
#define MAX_DIM
"\nDimensione massima dello stack: %d "
#define NUMB_OF_ITEMS
"\nNumero di elementi nello stack: %d "
Programmazione di Calcolatori: gli stack e i vettori
45
G. Amodeo,
C. Gaibisso
Grafo delle chiamate
stoiNew()
./stoi_ges.c
stoiFree()
./stoi_uti.c
stoiInit()
./stoi_uti.c
stoiAllMem()
./stoi_uti.c
main()
./stoi_main.c
stoiReset()
./stoi_ges.c
top()
./stoi_ges.c
stoiMenu()
./stoi_main.c
stoiEmpty()
./stoi_ges.c
reset()
./stoi_ges.c
pop()
./stoi_ges.c
stoiVis()
./stoi_ges.c
push()
./stoi_ges.c
stoiFull()
./stoi_uti.c
Programmazione di Calcolatori: gli stack e i vettori
46