• è una aggregazione di oggetti tutti dello stesso tipo T

(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

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

TIPI DI DATO ASTRATTI

• è una aggregazione di oggetti tutti dello stesso tipo T

• è caratterizzata dalle operazioni che sugli oggetti del tipo si compiono in particolare: operazioni LIFO (Last In, First Out)

IL TIPO ASTRATTO PILA (STACK)

Operazioni:

inserzione

• PUSH (nomestack, elemento)

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

• semantica

push (S,3)

1 2

S

1 2 3

S

(2)

eliminazione

• POP (nomestack)

nomestack: pila nella quale si effettua l’eliminazione

• semantica

1 2

1 2 3

pop (S)

S S

lettura

• TOP (nomestack)

nomestack: pila nella quale si effettua la lettura

• semantica

1 2 3

top (S)

S … top (S)=3

1 2 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

(3)

record pila begin

testa: integer;

integer elpila[…...];

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 all’elemento in 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

Inserimento: push().

Il nuovo elemento sarà inserito nell’elemento dello array puntato da pila.testa, che poi punterà all’elemento immediatamente successivo

E1

testa=1 1

2 3 4 5

Es.: push(E1)

Es.: push(E2)

E2

testa=2 E1

1 2 3 4 5

(4)

Estrazione: pop(): l’elemento sarà prelevato dall’elemento dello array puntato da pila.testa, che poi punterà all’elemento immediatamente precedente

Es.: pop() E2

testa=2 E1

1 2 3 4 5

E2

Es.: pop()

E1

testa=1 1

2 3 4 5

E1

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

(5)

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.

Gestione di uno stack : il programma C

#include <stdio.h>

void creapila(int *testap);

int empty(int testap);

int full(int testap, const int cardx);

void top(int elpilap[], int testap, int *eltop);

void stpila(int testap, int elpilap[]);

void push(int *testap, int elpilap[], int cardy);

void pop(int *testap, int elpilap[], int *elpop, int *vuoto);

main ()

{ const card=20;

struct pila { int testa;

int elpila[card];

};

int scelta, el, vuota, creata=0;

struct pila st;

(6)

Gestione di uno stack : il programma C

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));

Gestione di uno stack : il programma C

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.elpila, card);

else

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

break;

(7)

Gestione di uno stack : il programma C

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

if (creata==1)

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

if (vuota==0)

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.elpila, st.testa, &el);

printf("Elemento di testa = %d \n",st.elpila[st.testa]);

}

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

break;

Gestione di uno stack : il programma C

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

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

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

break;

} } }

while (scelta!=0);

printf("Fine");

} // fine main

(8)

Gestione di uno stack : il programma C

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));

}

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

*eltop=elpilap[testap];

}

Gestione di uno stack : il programma C

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

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

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

}

void push(int *testap, int elpilap[], int cardy) { int elval;

if (!full(*testap, cardy))

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

scanf("%d", &elval);

*testap=*testap+1;

elpilap[*testap]=elval;}

else

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

}

(9)

Gestione di uno stack : il programma C

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

{ *vuot=0;

*elpop=elpilap[*testap];

*testap=*testap-1;

} else *vuot=1;

}

• è una aggregazione di oggetti tutti dello stesso tipo

• è caratterizzata dalle operazioni che si compiono sugli oggetti del tipo in particolare: operazioni FIFO (First In, First Out)

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

(10)

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

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

(11)

record coda begin

head: integer;

last: integer;

integer elcoda[…...];

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.

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 …

(12)

POP(coda)

head= 1 1

2 3 4

5 last= 4

E1 E2 E3 E4

… eliminazione in coda …

head= 1 1

2 3 4 5

last= 3 E2

E3 E4

POP(coda)

head= 1 1

2 3 4

5 last= 4

E1 E2 E3 E4

… eliminazione in coda …

head= 2 1

2 3 4

5 last= 4

E2 E3 E4

… modo alternativo …

(13)

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.

Lo studente completi il programma ….

(14)

IL TIPO ASTRATTO TABELLA

• è un sottoinsieme del cartesiano (T1, T2), dove le coppie del

sottoinsieme definiscono una corrispondenza biunivoca fra i tipi T1 e T2

• T1 e T2 sono in generale diversi

• T1 è detto CHIAVE

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

IL TIPO ASTRATTO TABELLA

• la tabella è, quindi, un insieme finito di coppie ( KEY, INFO) key info

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

IL TIPO ASTRATTO TABELLA

key Nome Cogn Tel ….. …...

100 azxw hnm 234 ….. …...

125 kljgh vbhn 786 ….. …...

133 fgysu bchd 760 ….. …...

in genere, INFO è a sua volta un cartesiano, ovvero una tupla di elementi

(es. un record)

(15)

Definizione di una tabella:

indicare il nome, gli attributi costituenti i campi di INFO, 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

MATRICOLA NOME COGNOME DATA

nascita RESIDENZA

100 Gennaro Esposito 1/1/1970 Napoli

105 Ambrogio Rossi 1/2/1973 Milano

201 Romolo Romano 25/12/67 Roma

170 ... ... ... ...

StudentiUniversità

IL TIPO ASTRATTO TABELLA

(16)

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)

il valore di key NON deve già esistere nella tabella

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

Il valore di key deve esistere nella tabella, le informazioni esistenti sono modificate

• eliminazione: ELIM <nome_tabella> (key)

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

tipi di tabelle

• TABELLE STATICHE

• TABELLE DINAMICHE

le tabelle statiche sono definite dalla sola operazione TAB ( key) e non è

possibile, quindi, effettuare operazioni di inserzione e cancellazione

(17)