.dsy:it. (http://www.dsy.it/forum/)
- Programmazione (http://www.dsy.it/forum/forumdisplay.php?forumid=259)
-- [nomeDelCorso???] Adt (http://www.dsy.it/forum/showthread.php?threadid=7522)

Adt

CIAO A TUTTI! FINALMENTE CI SONO ANCHE IO SUL FORUM...
PER CASO SAPRESTE DARMI QUALCHE DRITTA SUGLI ADT? NN HO POTUTO SEGUIRE LA LEZIONE DEL PROF... E SUL LIBRO C'E' POCO E NIENTE...
GRAZIE MILLE
ATTY

Off-Topic:
non urlare perfavore!

__________________
http://www.twitter.com/0m4r

...io non credo che volesse urlare ma che semplicemente non sapesse che scrivere in maiuscolo equivale ad urlare!!!!
Cmq se qualcuno ha capito bene bene cosa e come si fa qs progetto sull'ADT potrebbe farcelo sapere?
Ciao a tutti!

A lezione il prof ha fatto degli esempi di stack, di lista e di una hash table.

In pratica bisogna scrivere un file.h contenente i prototipi delle funzioni definite in un file .c.

Per la lista le funzioni che si possono implementare sono init, insert, delete e free (o se preferite in italiano inizializza_lista, inserisci_elemento, cancella_elemento, libera_memoria).

Per lo stack init, push, pop, makenull.

Per la hash table init, insert, delete, find, makenull.

Poo chiaramente se voltete potete aggiungere le funzioni che volete.

Se avete il libro di Sedgewick "Algoritmi in C" trovate qualcosa su tutto, anche sulle hash table (che sono le più rognose secondo me).
Ora non vorrei dire fesserie, ma se volete rendervi la vita più semplice documentatevi e buttatevi sull' ADT stack che è il più semplice e veloce da implementare.

Buon mazzo a tutti

__________________
~ get Debian! ~ get FreeBSD! ~ get OpenBSD! ~

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