IL TIPO ASTRATTO PILA (STACK)

(1)

Elementi di Informatica

Prof. G. A. Di Lucca - Univ. del Sannio 1

• ... astratti rispetto alle modalità implementative

• in generale, non disponibili come tipi primitivi nei linguaggi di programmazione

• definiti in base alle operazioni che si possono effettuare sugli elementi che li costituiscono

• realizzati, se possibile, come tipi di utente dal programmatore

TIPI DI DATO ASTRATTI

IL TIPO ASTRATTO PILA (STACK)

... una pila di piatti ...

... Una pila di monete ...

... una pila di barattoli ...

(2)

IL TIPO ASTRATTO PILA (STACK)

... L’aggiunta di un elemento è fatta (sempre) ponendolo (impilandolo) su quello in cima alla pila ...

... L’eliminazione di un elemento è fatta (sempre) prendendo quello che sta in cima, ovvero l’ultimo inserito ...

Struttura Last In, First Out

• una aggregazione di oggetti tutti dello stesso tipo T

• struttura Last In, First Out (LIFO )

• caratterizzata dalle operazioni che sugli oggetti del tipo si compiono in particolare

IL TIPO ASTRATTO PILA (STACK)

Operazioni:

Inserzione nuovo elemento

• PUSH (nomestack, elemento)

nomestack: pila nella quale si effettua l’inserimento elemento: elemento da inserire in cima pila

• semantica

push (S, 3)

7 9

S

7 9 3

S

... S uno stack di interi

(3)

Eliminazione /estrazione elemento

• POP (nomestack)

nomestack: pila nella quale si effettua l’eliminazione

• semantica

7 9

7 9 3

pop (S)

S S

Lettura elemento

• TOP (nomestack)

nomestack: pila nella quale si effettua la lettura

• semantica

7 9 3

top (S)

S … top (S)=3

7 9 3

i predicati vuoto e pieno

• empty (nomestack)

vero se nella pila non vi sono elementi false in caso contrario

• full (nomestack)

vero se la pila è piena (impossibile inserire) falso in caso contrario

(4)

record pila begin

testa: integer;

integer vet_pila[card];

end;

IL TIPO ASTRATTO PILA (STACK) Una possibile implementazione

Un possibile modo per implementare una pila (stack) di oggetti è quello di modellarlo e simularlo con un record costituito da un campo di tipo array e da una campo che punta alla posizione dello array corrispondente alla testa allo stack:

Inizialmente pila.testa ‘punta’ a

‘null’ (ovvero la pila è vuota);

man mano che sono inseriti elementi nella pila, pila.testa punta alla posizione occupata dall’ultimo elemento inserito

testa= null 1

2 3 4 5

Operazioni

Inserimento nuovo elemento:

push(nomePila, valElem) : Il nuovo elemento sarà inserito nella posizione dello array indicata da pila.testa

testa=1

E1 Es.: push(ST, E1)

1 2 3 4

5 ST

Es.: push(ST, E2)

E2

testa=2 E1

1 2 3 4

5 ST

E1 1 2 3 4 5

E2

testa=2

(5)

Estrazione di un elemento:

pop(nomePila) : sarà prelevato l’elemento dello array puntato da pila.testa, dopo l’operazione pila.testa punta all’elemento immediatamente

precedente (nuova testa dello stack)

Es.: pop(ST) E2

testa=2 1 E1

2 3 4 5

E2

ST

dopo pop(ST)

testa=1 1

2 3 4 5

E1

ST

Lettura valore elemento:

top(nomePila) sarà letto il valore dell’elemento dello array puntato da pila.testa

Es.: top(ST) => E2 E2

testa=2 E1

1 2 3 4 5

E2

testa=2 1

2 3 4 5 ST E1

ST E2

Lo stato dello stack resta immutato

(6)

Definizione del problema: Si vuole realizzare un programma che gestisca uno stack (pila) per contenere dei valori interi, usando una struttura dati di tipo array monodimensionale.

Gestione di uno stack con un array

Definizione della specifica del programma:

I: il tipo di operazione da effettuare sullo stack; valori da inserire nello stack

Pi: non è possibile inserire elementi se lo stack è pieno; non è possibile estrarre elementi se lo stack è vuoto

U: lo stack; l’elemento estratto o ‘visitato’ sulla ‘testa’ dello stack;

Pu: nessuna

Gestione di uno stack con un array

Descrizione del metodo di elaborazione:

Si visualizza un ‘menù’ riportante le operazioni possibili sullo stack; l’utente seleziona un’operazione cui corrisponderà l’attivazione di un

sottoprogramma che eseguirà l’operazione richiesta.

Prima di inserire un elemento si deve verificare che lo stack non è pieno;

prima di estrarre un elemento si deve verificare che lo stack non è vuoto.

Lo stack sarà implementato usando un array monodimensionale ed

un’informazione che indicherà la posizione della testa dello stack all’interno dello array.

Viene usata anche una operazione ‘impropria’ di stampa del contenuto attuale della pila; l’operazione è ‘impropria’ perchè l’unico elemento accessibile nella pila è quello in testa alla stessa.

(7)

Gestione di uno stack : il programma C

#include <stdio.h>

void creapila(int *testap); // inizializza la struttura pila int empty(int testap); // verifica se vuota

int full(int testap, const int cardx); // verifica se piena

void top(int elpilap[], int testap, int *eltop); // accede elemento in testa void push(int *testap, int vet_pilap[], int cardy); // inserisce elemento

void pop(int *testap, int vet_pilap[], int *elpop, int *vuoto); // preleva elemento void stpila(int testap, int vet_pilap[]); // stampa contenuto

main ()

{ const card=20;

struct pila { int testa;

int vet_pila[card];

};

int scelta, el, vuota;

int creata=0; // indica che lo stack non è stato ancora creato/inizializzato struct pila st;

do { do

{ printf("\n PROGRAMMA GESTIONE PILA \n");

printf("1. Crea Pila \n");

printf("2. Inserisci (push)\n");

printf("3. Preleva (pop)\n");

printf("4. Esamina elemento testa (top)\n");

printf("5. Stampa stack\n");

printf("0. FINE\n");

printf("Immetti n.ro operazione \n");

scanf("%d", &scelta);

}

while ((scelta<0) || (scelta>5));

(8)

if (scelta!=0) { switch (scelta)

{ case 1 : { printf("Crea Pila\n");

if (creata==0)

{ creapila(&st.testa);

creata=1;

} else

printf("Pila già creata \n");

break; }

case 2 :{ printf("PUSH\n");

if (creata==1)

push(&st.testa, st.vet_pila, card);

else

printf("Pila non ancora creata\n");

break;}

case 3 :{ printf("POP\n");

if (creata==1)

{ pop(&st.testa, st.vet_pila, &el, &vuota);

if (vuota == 0) // vuota = ‘falso’

printf("Elemento estratto = %d\n", el);

else

printf("Pila vuota: non possibile estrarre \n");

}

else printf("Pila non ancora creata\n");

break;}

case 4 : {printf("TOP\n");

if ((creata==1) &&(!empty(st.testa))) {top(st.vet_pila, st.testa, &el);

printf("Elemento di testa = %d \n", el);

}

else printf("Pila vuota o non ancora creata\n");

break;}

(9)

case 5:{ printf("Stampa Contenuto Pila\n");

if((creata==1) && (!empty(st.testa))) stpila(st.testa, st.vet_pila);

else printf("Pila vuota o non ancora creata\n");

break;}

} // fine switch } // fine if (scelta!=0) } // fine do ... while while (scelta!=0);

printf("Fine");

} // fine main

void creapila(int *testap) {*testap = -1;}

int empty(int testap) { int vta;

return vta=(testap<0);

}

int full(int testap, int cardx) { int piena;

return piena=(testap>=(cardx-1));

}

(10)

void push(int *testap, int vet_pilap[], int cardp) { int elval;

if (!full(*testap, cardp))

{ printf("immetti valore elemento da inserire \n");

scanf("%d", &elval);

*testap=*testap+1;

vet_pilap[*testap] = elval;}

else

printf("Pila piena: Non possibile Inserire\n");

}

void top(int vet_pilap[], int testap, int *eltop) {

*eltop=vet_pilap[testap];

}

void pop(int *testap, int vet_pilap[], int *elpop, int *vuot) { if (!empty(*testap))

{ *vuot=0;

*elpop = vet_pilap[*testap];

*testap = *testap-1;

} else

*vuot=1;

}

void stpila(int testap, int vet_pilap[]) { int i;

for (i=testap;i>=0;i--)

printf("[%d]= %d \n",i,vet_pilap[i]);

}

(11)

IL TIPO ASTRATTO CODA

... Una coda di persone ad uno sportello...

... Una coda di automobili ad uno casello ...

IL TIPO ASTRATTO PILA (STACK)

Struttura First In, First Out ... L’aggiunta di un elemento è

fatta (sempre) ponendolo (accodandolo) dietro l’ultimo ...

... L’eliminazione di un elemento è fatta (sempre) prendendo quello che sta davanti a tutti, ovvero il primo inserito ...

(12)

• aggregazione di oggetti tutti dello stesso tipo

• struttura First In, First Out (FIFO )

• caratterizzata dalle operazioni che si compiono sugli oggetti

IL TIPO ASTRATTO CODA

Operazioni

inserzione

• PUSH(nomecoda, elemento)

1 2

3

head last

1 2

3 4

PUSH(nomecoda, 4) stato prima

di PUSH

stato dopo PUSH

eliminazione

POP(nomecoda, elem)

2 3

4

POP(nomecoda, elem)

elem=1

1 2

3

head last

4

stato dopo POP stato prima

di POP

(13)

i predicati vuoto e pieno

• empty (nomecoda)

true se nella coda non vi sono elementi false in caso contrario

• full (nomecoda)

true se la coda è piena (impossibile inserire) false in caso contrario

record coda begin

head: integer;

last: integer;

integer vet_coda[…...];

end;

Inizialmente coda.head e coda.last

‘puntano’ a ‘null’ (ovvero la coda è vuota); man mano che sono inseriti elementi nella coda, coda.head punta alla posizione occupata dal primo elemento nella coda (il primo da servire) e coda.last alla posizione dell’ultimo elemento inserito

head= null 1

2 3 4

5 last= null

La coda può essere implementata con un array e modellata con un record.

(14)

PUSH(coda, E4)

head= 1 1

2 3 4 5

last= 4 E1

E2 E3 E4 head= 1

1 2 3 4

5 last= 3

E1 E2 E3

… inserimento in coda …

POP(coda)

head= 1 1

2 3 4

5 last= 4

E1 E2 E3 E4

… estrazione dalla coda …

head= 1 1

2 3 4 5

last= 3 E2

E3 E4

(15)

POP(coda)

head= 1 1

2 3 4

5 last= 4

E1 E2 E3 E4

… estrazione dalla coda …

head= 2 1

2 3 4

5 last= 4

E2 E3 E4

… modo alternativo …

Definizione del problema: Si vuole realizzare un programma che gestisca una coda per contenere dei valori interi, usando una struttura dati di tipo array monodimensionale.

Gestione di una coda con un array

Definizione della specifica del programma:

I: il tipo di operazione da effettuare sulla coda; valori da inserire nella coda Pi: non è possibile inserire elementi se la coda è piena; non è possibile estrarre elementi se la coda è vuota

U: la coda aggiornata in base all’operazione eseguita;

Pu: nessuna

Descrizione del metodo di elaborazione: Si visualizza un ‘menù’ riportante le operazioni possibili sulla coda; l’utente seleziona un’operazione cui corrisponderà

l’attivazione di un sottoprogramma che eseguirà l’operazione richiesta. Prima di inserire un elemento si deve verificare che la coda non è piena; prima di estrarre un elemento si deve verificare che la coda non è vuota. La coda sarà implementato usando un array

monodimensionale e le necessarie informazioni che indicheranno la posizione della testa e della fine della coda all’interno dello array.

(16)

Lo studente completi il programma ….

IL TIPO ASTRATTO TABELLA

• è un sottoinsieme del prodotto cartesiano (T1, T2), dove le coppie del sottoinsieme definiscono una corrispondenza biunivoca fra i tipi T1 e T2

• T1 e T2 sono tipi in generale diversi

• T1 è detto CHIAVE

• T2 è un generico tipo di informazione e può essere a sua volta un cartesiano di tipi anche disomogenei (ad es. un record)

IL TIPO ASTRATTO TABELLA

• la tabella è, in pratica, un insieme finito di coppie ( KEY, INFO) realizzante una corrispondenza tra il valore di KEY ed INFO

key info

... un valore di Key compare una ed una sola volta nella tabella ...

(17)

IL TIPO ASTRATTO TABELLA

INFO può essere a sua volta un prodotto cartesiano, ovvero una tupla di elementi (es. un record)

Key INFO

Matricola Cognome Nome Corso di Laurea N.Ro Esami Superati

Media Voti 864/345 Esposito Gennaro Ingegneria Energetica 7 28

862/231 Rossi Ambrogio Ingegneria Informatica 5 24

864/534 Romano Romolo Ingegneria Energetica 12 26

864/425 Esposito Carlo Ingegneria Informatica 15 30

862/157 Esposito Gennaro Ingegneria Informatica 11 25

Definizione di una tabella:

bisogna indicare il nome della tabella, gli attributi costituenti i campi di INFO, e la chiave:

<nome_tabella> (Attr1: T1, Attr2: T2, ..., AttrN: TN);

Uno o più campi della tabella formeranno la chiave

La chiave deve identificare un unico elemento della tabella (una ed una sola riga)

Es.

StudentiUniversità (Matricola: int, Cognome: stringa, Nome: stringa, DataNascita: data, Residenza: stringa)

Chiave: Matricola

L’insieme degli attributi costituisce lo schema della tabella

IL TIPO ASTRATTO TABELLA

(18)

MATRICOLA NOME COGNOME DATA

nascita RESIDENZA 864/345 Esposito Gennaro 1/1/1970 Napoli

862/231 Rossi Ambrogio 1/2/1973 Milano

864/534 Romano Romolo 25/12/67 Roma

862/575 ... ... ... ...

StudentiUniversità

IL TIPO ASTRATTO TABELLA

funzione di accesso

• FUNZIONE DI ACCESSO: a CHIAVE

• si fornisce il valore della chiave e si ottiene l’informazione associata TAB ( KEY ) ==> INFO

altre operazioni

• inserzione: INSERT <nome_tabella> (key, info) Inserisce una nuova riga nella tabella

Vincolo: il valore di key NON deve già esistere nella tabella

• aggiornamento: UPDATE <nome_tabella> (key, info_new)

Le informazioni esistenti (associate a key) sono modificate Vincolo: il valore di key deve esistere nella tabella,

• eliminazione: ELIM <nome_tabella> (key) Elimina la riga corrispondente a key

Vincolo: Il valore di key deve esistere nella tabella

• predicato EMPTY

EMPTY (<nome_tabella>)

vero se non vi sono elementi/righe in <nome_tabella>

falso se c’è almeno un elemento

IL TIPO ASTRATTO TABELLA

(19)

tipi di tabelle

• TABELLE STATICHE

• TABELLE DINAMICHE

le tabelle statiche non possono essere modificate e, quindi, non è possibile effettuare operazioni di inserzione e cancellazione e pertanto sono definite dalla sola operazione di accesso TAB ( key)

• una possibile implementazione:

... array di record ....

• Le tabelle possono essere memorizzate usando file ad accesso diretto (file ad accesso random)

• Nell’ambito delle Basi di Dati (Data Base) la tabella costituisce non solo un tipo primitivo ma anche il tipo fondamentale