 |
italo80 |
.novellino.
Registered: Dec 2003
Posts: 1 (0.00 al dì)
Location: Saronno
Corso: Informatica tlc
Anno: 1
Time Online: 0:45:23 [...]
Status: Offline
Edit | Report | IP: Logged |
Se ti può aiutare questo sono degli appunti trovati in giro;
L'ADT "stack"
Generalità
· Lo stack è un contenitore di elementi
· Caratterizzato da una politica L.I.F.O.
· Due funzioni: put() per inserire un elemento, e get() per rimuoverlo
Due possibili approcci
Sfruttare i file come contenitori per:
1. creare un oggetto stack di elementi
o nessuna necessità di creare espressamente uno stack
o nessuna possibilità di avere più stack distinti
o put() e get() non richiedono alcun oggetto stack esplicito fra i loro parametri (fanno riferimento implicitamente all'unico stack)
2. definire l'ADT stack di elementi (un "modello")
o necessario creare espressamente uno stack prima di poterlo usare
o possibile definire più stack distinti
o lo specifico stack su cui si opera figura esplicitamente fra i parametri di put() e get()
Differenza fondamentale
· Nel primo caso, il file conterrà anche le variabili globali (static) che realizzano l'oggetto stack
I° caso - Il singolo oggetto stack
· Un file per il tipo element element.h, element.c
· Un file per l'oggetto stack (di element) stackobj.h, stackobj.c
· Non esiste un tipo stack !
Interfaccia
· void put(element) per inserire un elemento
· element get(void) per rimuovere un elemento
· BOOL isEmpty(void) per controllare se lo stack è vuoto
Possibili implementazioni
· un vettore val + un indice sp (invisibili fuori dal file static)
o ci sarà un limite superiore al numero di elementi inseribili
necessità di una ulteriore funzione di controllo
o BOOL isFull(void) per controllare se lo stack è pieno
· una lista l di element, allocata e deallocata dinamicamente
Problemi
· cosa succede se si invoca get() quando lo stack è vuoto?
o "non dovrebbe succedere" (!)
o una convenzione (quale?)
o un concetto di esito dell'operazione leggibile tramite un'opportuna primitiva check_result()
· [nel caso dell'implementazione con limite superiore: cosa succede se si invoca put() quando lo stack è pieno?]
o "non dovrebbe succedere" (!)
o un messaggio d'errore ?
L'oggetto stack - Implementazione con vettore
/* File STACKOBJ.H: dichiara l'astrazione stack */
#include "element.h"
void put(element);
element get(void);
BOOL isFull(void);
BOOL isEmpty(void);
/* File STACKOBJ.C: implementa l'astrazione stack */
#include <stdio.h>
#include "stackobj.h"
#define MAXDIM 100
static int sp=0;
static element val[MAXDIM];
void put(element e) {
if (!isFull()) val[sp++]=e;
else printf("\nErrore: stack pieno");
}
element get(void) {
if (!isEmpty()) return val[--sp];
else { printf("\nErrore: stack vuoto\n");
return BAD_ELEMENT; // ?????? }
}
BOOL isFull(void) {
return (sp==MAXDIM);
}
BOOL isEmpty(void) {
return (sp==0);
}
L'oggetto stack - Implementazione a liste
· lo header rimane intoccato (ovviamente!!)
· la funzione isFull() restituisce sempre FALSE
/* File STACKOBJ.H: dichiara l'astrazione stack */
#include "element.h"
void put(element);
element get(void);
BOOL isFull(void);
BOOL isEmpty(void);
/* File STACKOBJ.C: implementa l'astrazione stack */
#include <stdio.h>
#include "stackobj.h"
#include "list.h"
static list l = emptyList();
void put(element e) { l = cons(e,l); }
element get(void) {
if (!isEmpty()) { element e = head(l); l = tail(l); return e; }
else {printf("\nErrore: stack vuoto\n");
return BAD_ELEMENT; // ?????? }
}
BOOL isFull(void) { return FALSE; }
BOOL isEmpty(void) { return isEmtpy(l); }
· la funzione isFull() restituisce sempre FALSE una macro ?
#define isFull(X) (FALSE)
II° caso - L'ADT stack
· Un file per il tipo element element.h, element.c
· Un file per il tipo stack (di element) stack.h, stack.c
Interfaccia
· void put(element, stack) per inserire un elemento nello stack dato
· element get(stack) per rimuovere un elemento dallo stack dato
· BOOL isEmpty(stack) per controllare se lo stack dato è vuoto
· [BOOL isFull(stack) per controllare se lo stack dato è vuoto]
· un costruttore createStack()
Possibili rappresentazioni concrete per stack
· un vettore + un indice
/* File STACK.H: introduce il tipo stack */
#include "element.h"
typedef struct {element val[MAX]; int sp; } stack;
void put(element, stack);
element get(stack);
......
stack createStack(void);
· una lista
/* File STACK.H: introduce il tipo stack */
#include "element.h"
#include "list.h"
typedef list stack;
void put(element, stack);
......
stack createStack(void);
... MA E' CORRETTO QUESTO ?
Rappresentazioni concrete di stack
· una struttura (vettore + indice)
· una lista
Il problema
· put() e get() devono modificare lo stack
o impossibile passare lo stack per valore!!
o prima si accedeva a variabili globali.... ma ora ?
· definire il tipo stack come puntatore (a una struttura, a una lista...)
Quindi:
· Caso struttura (vettore + indice)
/* File STACK.H: introduce il tipo stack */
#include "element.h"
typedef struct stk {element val[MAX]; int sp; } *stack;
......
· Caso lista
/* File STACK.H: introduce il tipo stack */
#include "element.h"
#include "list.h"
typedef list *stack; // è un puntatore a puntatore
......
Possibili implementazioni per stack
· Caso struttura (vettore + indice)
/* File STACK.C: implementa il tipo stack */
#include <stdio.h>
#include "stack.h" // include la typedef
stack createStack(void){
stack s = (stack)malloc(sizeof(struct stk));
s->sp = 0;
return s;
}
void put(element e, stack s) {
if (!isFull(s)) s->val[s->sp++]=e;
else printf("\nErrore: stack pieno");
}
.......
· una lista
/* File STACK.C: implementa il tipo stack */
#include <stdio.h>
#include "stack.h" // include la typedef e le liste
stack createStack(void){
stack s = (stack)malloc(sizeof(list));
*s = emptyList();
return s;
}
void put(element e, stack s) {
if (!isFull(s)) *s= cons(e,*s);
else printf("\nErrore: stack pieno");
}
......
L'ADT "coda circolare"
Generalità
· La coda (circolare o meno) è un contenitore di elementi
· Caratterizzato da una politica F.I.F.O.
· Due funzioni: put() per inserire un elemento, e get() per rimuoverlo
Caratteristiche
· Due approcci (come per lo stack): oggetto singolo o ADT
· Interfaccia uguale a stack (cambia solo la politica di gestione)
· Implementazione simile a stack (adattata alle mutate circostanze)
o due indici anziché uno
o first indica l'inizio della coda, last la fine
o gli indici fanno riferimento alla cella vuota adiacente all'elemento
o tutti i confronti fra gli indici avvengono modulo QUEUE_DIM
Esempio: l'oggetto coda (impl. con vettore)
Interfaccia
/* File QUEUEOBJ.H: dichiara l'astrazione coda */
/* identico a STACKOBJ.H */
#include "element.h"
void put(element);
element get(void);
BOOL isFull(void);
BOOL isEmpty(void);
Implementazione
/* File QUEUEOBJ.C: implementa l'oggetto coda */
#include <stdio.h>
#define QUEUE_DIM 100
#define QUEUE_LENGTH QUEUE_DIM-1
static int last=0;
static int first=QUEUE_LENGTH;
static element val[QUEUE_DIM];
int isFull(void) {
// coda piena se diff. fra indici > = dimensione coda
int delta = last>first ? last-first : QUEUE_DIM+last-first;
return (delta >= QUEUE_DIM);
}
int isEmpty(void) {
// coda vuota se diff. fra indici <= 1
int delta = last>first ? last-first : QUEUE_DIM+last-first;
return (delta <= 1);
}
void put(element el) {
if (!isFull()) { val[last++]=el;
if (last>=QUEUE_DIM) last -= QUEUE_DIM;}
else printf("\nErrore: coda piena.\n",el);
}
......
Il tema della genericità
· Stack e code sono contenitori di elementi
· In ogni applicazione, si può scegliere l'element necessario
· Ma è impossibile avere nella stessa applicazione stack e/o code diverse per contenere elementi diversi
o ad esempio, non è possibile avere uno stack s1 di float e anche uno stack s2 di complex, e magari una coda c3 di person, etc..
Il problema
· se element denota un tipo, non può contemporaneamente denotarne un altro
· quindi, usando l'approccio ADT si possono avere più stack e/o code nella stessa applicazione, ma tutti contenenti lo stesso tipo di elementi
Soluzioni ?
· il C non offre soluzioni semplici, efficaci e "pulite" a questo problema
o in C++ esiste invece il concetto di template
· tuttavia, alcuni meccanismi possono essere sfruttati allo scopo:
o il costrutto union
o il concetto di "void pointer" (void*)
Il costrutto union
· simile alla struct, ma alloca spazio per uno solo dei campi
· usandolo come element, si possono inserire nel contenitore tutti i tipi corrispondenti ai campi
· ma
o non è possibile introdurre tipi non previsti dalla union
o ogni contenitore potrebbe contenere oggetti di tipi diversi
(inopportuno)
Il concetto di "void pointer" (void*)
· Un void* è un tipo di puntatore generico, un "puro indirizzo"
· compatibile con ogni tipo di puntatore "effettivo"
· ma privo di informazioni di tipo
· e perciò non dereferenziabile (occorre un cast)
Quando può servire?
· Quando si deve manipolare non l'oggetto puntato, ma solo il puntatore
· Esempio: una funzione che scambi due oggetti generici
void gen_swap(void** x, void** y){
void* tmp = *x;
*x = *y; *y = tmp;
}
· Uso:
void main(){
int *pi1, *pi2;
data *pd1, *pd2;
pi1 = malloc(sizeof(int)); *pi1 = 3;</
|
Apllo²°°³
Adt
