P - ADT Flashcards
1
Q
Perché un dato è detto astratto?
A
Perché maschera la sua implementazione mediante la coppia di moduli interfaccia/implementazione
2
Q
Quali sono le caratteristiche di un quasi ADT?
A
- il nuovo tipo viene definito con la typedef nel file.h
- il client include il file.h quindi vede i dettagli interni del dato
- non richiede allocazione dinamica
- il quasi ADT per composti viola la regola 1 mentre quello per le collezioni viola la 2
3
Q
Quali sono le caratteristiche di un ADT di I classe e le regole? Fare un esempio di file .h e .c con un dato per numeri complessi.
A
- il nuovo tipo viene dichiarato nel file.h ma lasciato incompleto; viene completamente definito nel file.c
- di solito ciò che viene messo nel file.h è un puntatore a struct incompleta
- il client può usare solo il puntatore a struct
- il puntatore è opaco e si dice handle
Regole:
1) nasconde al client i dettagli
2) permette al client di creare più variabili del tipo ADT
Esempio
complex.h
typedef struct complex_s *Complex;
void funzione(Complex c);
complex.c
struct complex_s { float Re; float Im; };
4
Q
Quali sono i modi per definire l’ADT Item?
A
1) typedef int Item;
typedef int Key;
2) typedef char *Item;
typedef char *Key;
3)
typedef struct {
char name[MACX];
int num;
} Item;
typedef char *Key
4)
typedef struct {
char name*;
int num;
} Item;
typedef char *Key
5
Q
Qual è il prototipo della KEYget in base al tipo di Item per i quasi ADT?
A
Key KEYget(Item val); nei casi 1 e 2
Key KEYget(Item *pval); nei casi 3 e 4
6
Q
Quasi ADT, scrivere per il tipo di Item 1 le funzioni:
- Key KEYget(Item val);
- int KEYcompare(Key k1, Key k2);
- Item ITEMscan();
- void ITEMshow(Item v);
- int ITEMless(Item val1, Item val2);
A
Key KEYget(Item val){
return val;
}
int KEYcompare(Key k1, Key k2){
return k1-k2;
}
Item ITEMscan(){
Item i;
scanf(“%d”, &i);
return I;
}
void ITEMshow(Item v){
printf(“%d”, v);
}
int ITEMless(Item val1, Item val2){
return(KEYget(val1) < KEYget(val2));
}
7
Q
Quasi ADT, scrivere per il tipo di Item 2 le funzioni:
- Key KEYget(Item val);
- int KEYcompare(Key k1, Key k2);
- Item ITEMscan();
- void ITEMshow(Item v);
- int ITEMless(Item val1, Item val2);
A
static char buf[MAXC];
Key KEYget(Item val){
return val;
}
int KEYcompare(Key k1, Key k2){
return (strcmp(k1, k2));
}
Item ITEMscan(){
scanf(“%s”, buf);
return strdup(buf);
}
void ITEMshow(Item v){
printf(“%s”, v);
}
int ITEMless(Item val1, Item val2){
return (strcmp(KEYget(val1),KEYget(val2))<0);
}
8
Q
Quasi ADT, scrivere per il tipo di Item 3 le funzioni:
- Key KEYget(Item *pval);
- int KEYcompare(Key k1, Key k2);
- Item ITEMscan();
- void ITEMshow(Item v);
- int ITEMless(Item val1, Item val2);
A
static char buf[MAXC];
Key KEYget(Item *pval){
return pval->name;
}
int KEYcompare(Key k1, Key k2){
return (strcmp(k1, k2));
}
Item ITEMscan(){
Item val;
scanf(“%s%d”, val.name, &val.num);
return val;
}
void ITEMshow(Item v){
printf(“%s %d”, v.name, v.num);
}
int ITEMless(Item val1, Item val2){
return (strcmp(KEYget(&val1),KEYget(&val2))<0);
}
9
Q
Quasi ADT, scrivere per il tipo di Item 4 le funzioni:
- Key KEYget(Item *pval);
- int KEYcompare(Key k1, Key k2);
- Item ITEMscan();
- void ITEMshow(Item v);
- int ITEMless(Item val1, Item val2);
A
static char buf[MAXC];
Key KEYget(Item *pval){
return pval->name;
}
int KEYcompare(Key k1, Key k2){
return (strcmp(k1, k2));
}
Item ITEMscan(){
Item val;
scanf(“%s%d”, buf, &(val.num));
val.name = strdup(buf);
return val;
}
void ITEMshow(Item v){
printf(“%s %d”, v.name, v.num);
}
int ITEMless(Item val1, Item val2){
return (strcmp(KEYget(&val1),KEYget(&val2))<0);
}
10
Q
In quali casi di Item ha senso la deallocazione?
A
Solo nei casi 2 e 4.
11
Q
Quali tipi di Item usiamo per gli ADT di I classe?
Cosa si trova nel file.h?
A
Usiamo il 3 e il 4.
file.h
typedef struct item *Item;
typedef struct char *Key;
…
12
Q
Scrivere le seguenti funzioni per gli ADT di prima classe:
- Key KEYget(Item val);
- int KEYcompare(Key k1, Key k2);
- void ITEMshow(Item val);
- int ITEMless(Item val1, Item val2);
A
Key KEYget(Item val){
return val->name;
}
int KEYcompare(Key k1, Key k2){
return strcmp(k1, k2);
}
void ITEMshow(Item val){
printf(“%s %d”, val->name, val->num);
}
int ITEMless(Item val1, Item val2){
return strcmp(KEYget(val1), KEYget(val2));
}
13
Q
Scrivere le funzioni di allocazione, deallocazione e scan di Item per ADT di I classe (3 e 4)
- Item ITEMnew(void);
- void ITEMfree(Item val);
- Item ITEMscan() (3) e void ITEMscan(Item val) (4)
A
Item ITEMnew(void){
Item val;
val = malloc(sizeof(struct item));
if (val == NULL) return ITEMsetvoid();
val->name = ‘\0’; // 4) val->name = NULL;
val->num = 0;
return val;
}
void ITEMfree(Item val){
free(val->name); //solo nel 4)
free(val);
}
Item ITEMscan(){
Item val = ITEMnew();
scanf(“%s %d”, val->name, &val->num);
return val;
}
void ITEMscan(Item val){
scanf(“%s %d”, buf, &val->num);
val->name = strdup(buf);
}
14
Q
Quali sono i criteri possibili di Delete nelle code in generale?
A
- FIFO
- LIFO
- priorità
- casuale
- contenuto (tabella di simboli)
15
Q
In che modo si possono implementare le code, in generale, e quali sono vantaggi e svantaggi?
A
Si possono implementare con vettori o liste, in versione quasi ADT o ADT di I classe.
I vettori hanno uno spazio sempre alloccato al massimo previsto quindi sono vantaggiosi per code piene o quasi; per le liste lo spazio è proporzionale al numero effettivo di elementi.
Il quasi ADT prevede delle variabili globali e invisibili ad altri (NON ADT), l’ADT di I classe prevede una struct puntata da handle; la struct ha come campi le variabili globali del quasi ADT
16
Q
ADT Stack: quali funzioni lo caratterizzano e qual è la loro complessità?
A
stackpush e stackpop, O(1)
17
Q
ADT Stack: implementazione con vettore quasi ADT. Scrivere Stack.h e Stack.c con strutture dati e funzioni di inizializzazione, push e pop.
- void STACKinit(int MAXN);
- int STACKempty();
- void STACKpush(Item val);
- Item STACKpop();
A
stack.h
void STACKinit(int MAXN);
int STACKempty();
void STACKpush(Item val);
Item STACKpop();
stack.c
static Item *s; //vettore di Item
static int N;
void STACKinit(int MAXN){
s = malloc(MAXN*sizeof(Item));
N = 0;
}
int STACKempty() { return N == 0; }
void STACKpush(Item val){
s[N++] = val;
}
Item STACKpop(){
return s[–N];
}
18
Q
ADT Stack: implementazione con vettore ADT di I classe. Scrivere Stack.h e Stack.c con strutture dati e funzioni di inizializzazione, push e pop.
- STACK STACKinit(int MAXN);
- int STACKempty(STACK sp);
- void STACKpush(STACK sp, Item val);
- Item STACKpop(STACK sp);
A
stack.h
typedef struct stack *STACK;
STACK STACKinit(int MAXN);
int STACKempty(STACK s);
void STACKpush(STACK s, Item val);
Item STACKpop(STACK s);
stack.c
struct stack { Item *s; int N; };
STACK STACKinit(int MAXN){
STACK sp;
sp = malloc(sizeof(sp));
sp->s = malloc(MAXNsizeof(Item));
sp->N = 0;
return sp;
}
int STACKempty(STACK sp){
return sp->N == 0;
}
void STACKpush(STACK sp, Item val){
sp->s[sp->N++] = val;
}
Item STACKpop(STACK sp){
return sp->s[–(sp->N)];
}
19
Q
ADT Stack: implementazione con lista, quasi ADT. Scrivere Stack.h e Stack.c con strutture dati e funzioni di inizializzazione, push e pop.
- void STACKinit(int MAXN);
- int STACKempty();
- void STACKpush(Item val);
- Item STACKpop();
A
stack.h
void STACKinit(int MAXN);
int STACKempty();
void STACKpush(Item val);
Item STACKpop();
stack.c
typedef struct STACKnode *link;
struct STACKnode { Item val; link next; };
static link head;
static link NEW (Item val, link next){
link x;
x = malloc(sizeof(*x));
x->val = val; x->next = next;
return x;
}
void STACKinit(int maxN) { head = NULL; }
int STACKempty() { return head == NULL; }
void STACKpush(Item val) {
head = NEW(val, head);
}
Item STACKpop() {
Item tmp;
tmp = head->val;
link t = head->next;
free(head);
head = t;
return tmp;
}
20
Q
ADT Stack: implementazione con lista, ADT di I classe. Scrivere Stack.h e Stack.c con strutture dati e funzioni di inizializzazione, push e pop.
- STACK STACKinit(int MAXN);
- int STACKempty(STACK s);
- void STACKpush(STACK s, Item val);
- Item STACKpop(STACK s);
A
stack.h
typedef struct stack *STACK;
STACK STACKinit(int MAXN);
int STACKempty(STACK s);
void STACKpush(STACK s, Item val);
Item STACKpop(STACK s);
stack.c
typedef struct STACKnode *link;
struct STACKnode { Item val; link next; };
struct stack { link head; };
static link NEW(Item val, link next){
link x;
x = malloc(sizeof(*x));
x->val = val; x->next = next;
return x;
}
STACK STACKinit(int MAXN){
STACK s = malloc(sizeof(*s));
s->head = NULL;
return s;
}
int STACKempty(STACK s){
return s->head == NULL;
}
void STACKpush(STACK S, Item val){
s->head = NEW(val, s->head);
}
Item STACKpop(STACK s){
Item tmp;
tmp = s->head->val;
link t = s->head->next;
free(s->head);
s->head = t;
return tmp;
}
21
Q
ADT QUEUE: quali operazioni lo caratterizzano e che complessità hanno?
A
QUEUEput e QUEUEget, O(1)
FIFO
22
Q
ADT QUEUE: come si può implementare? Quali sono le caratteristiche?
A
Attraverso lista e vettore.
Il vettore può essere sia lineare che circolare.
- vettore lineare: O(n), head = 0 è fisso e quindi bisogna “scalare” gli elementi
- vettore circolare: O(1), head e tail sono incrementati modulo N e non è più garantito
23
Q
Come funziona il buffer circolare?
A
- head e tail sono incrementati modulo N
- se la coda è vuota vuol dire che head ha raggiunto tail
- se è piena tail ha raggiunto head
- si allocano maxn+1 elementi in modo che non si possa mai avere head == tail
- per convenzione all’inizio head = N e tail =0
- coda vuota: head%N == tail
24
Q
ADT QUEUE: implementazione con vettore, quasi ADT. Scrivere queue.h e queue.c con strutture dati e funzioni di inizializzazione, può e get.
- void QUEUEinit(int MAXN);
- int QUEUEempty();
- void QUEUEput(Item val);
- Item QUEUEget();
A
queue.h
void QUEUEinit(int MAXN);
int QUEUEempty();
void QUEUEput(Item val);
Item QUEUEget();
queue.c
static Item *q;
static int N, head, tail;
void QUEUEinit(int MAXN){
q = malloc((MAXN+1)*sizeof(Item));
N = MAXN+1; head = N; tail = 0;
}
int QUEUEempty() {
return head%N == tail;
}
void QUEUEput(Item val){
q[tail++] = val;
tail = tail%N;
}
Item QUEUEget() {
head = head%N;
return q[head++];
}
25
ADT QUEUE: implementazione con vettore, ADT di I classe. Scrivere queue.h e queue.c con strutture dati e funzioni di inizializzazione, può e get.
- QUEUE QUEUEinit(int MAXN);
- int QUEUEempty(QUEUE q);
- void QUEUEput(QUEUE q, Item val);
- Item QUEUEget(QUEUE q);
queue.h
typedef struct queue *QUEUE;
QUEUE QUEUEinit(int MAXN);
int QUEUEempty(QUEUE q);
void QUEUEput(QUEUE q, Item val);
Item QUEUEget(QUEUE q);
queue.c
struct queue { Item *q; int N, head, tail; };
QUEUE QUEUEinit(int MAXN){
QUEUE q = malloc(sizeof(*q));
q->q = malloc((maxN+1)*sizeof(Item));
q->N = maxN+1;
q->head = N;
q->tail =0;
return q;
}
int QUEUEempty(QUEUE q){
return (q->head)%(q->N) == (q->tail);
}
void QUEUEput(QUEUE q, Item val){
q->q[tail++] = val;
q->tail = q->tail%N;
}
Item QUEUEget(QUEUE q){
q->head = (q->head)%N;
return q->q[q->head++];
}
26
ADT QUEUE: implementazione con lista, quasi ADT. Scrivere queue.h e queue.c con strutture dati e funzioni di inizializzazione, put e get.
- void QUEUEinit(int MAXN);
- int QUEUEempty();
- void QUEUEput(Item val);
- Item QUEUEget();
queue.h
void QUEUEinit(int MAXN);
int QUEUEempty();
void QUEUEput(Item val);
Item QUEUEget();
queue.c
typedef struct QUEUEnode *link;
struct QUEUEnode { Item val; link next; };
static link head, tail;
link NEW(Item val, link next){
link x = malloc(sizeof(*x));
x->val = val; x->next = next;
return x;
}
int QUEUEempty(){
return head == NULL;
}
void QUEUEput(Item val){
if (head == NULL) head = tail = NEW(val, head);
else {
tail ->next = NEW(val, tail->NEXT);
tail = tail->next;
}
}
Item QUEUEget(){
Item tmp;
tmp = head->val;
link t = head->next;
free(head);
head = t;
return tmp;
}
27
ADT QUEUE: implementazione con lista, ADT di I classe. Scrivere queue.h e queue.c con strutture dati e funzioni di inizializzazione, può e get.
- QUEUE QUEUEinit(int MAXN);
- int QUEUEempty(QUEUE q);
- void QUEUEput(QUEUE q, Item val);
- Item QUEUEget(QUEUE q);
queue.h
typedef struct queue *QUEUE;
QUEUE QUEUEinit(int MAXN);
int QUEUEempty(QUEUE q);
void QUEUEput(QUEUE q, Item val);
Item QUEUEget(QUEUE q);
queue.c
typedef struct QUEUEnode *link;
struct QUEUEnode { Item val; link next; };
struct queue {link head, tail; };
QUEUE QUEUEinit(int MAXN){
QUEUE q = malloc(sizeof(*q));
q->head = NULL;
return q;
}
int QUEUEempty(QUEUE q){ return q->head = NULL; }
void QUEUEput(QUEUE q, Item val){
if (q->head == NULL){
q->tail = NEW(val, q->head);
q->head = q->tail;
}
else {
q->tail->next = NEW(val, q->tail->next);
q->tail = q->tail->next;
}
}
Item QUEUEget(QUEUE q){
Item tmp = q->head->val;
link t = q->head->next;
free(q->head); q->head = t;
return tmp;
}
28
ADT PQ: implementazione con vettore/lista non ordinato
Complessità di:
- inserzione in testa alla lista o in coda al vettore
- estrazione del max/min
- cambio di priorità
- inserzione in testa alla lista o in coda al vettore: O(1)
- estrazione del max/min O(N)
- cambio di priorità O(N)
29
ADT PQ: implementazione con vettore/lista ordinato
Complessità di:
- inserzione ordinata
- estrazione del max/min
- cambio di priorità
- inserzione ordinata O(N)
- estrazione del max/min O(1)
- cambio di priorità O(N)
30
ADT PQ: implementazione con heap di item/indici
Complessità di:
- inserzione
- show max/min
- estrazione max/min
- inserzione O(logN)
- show max/min O(1)
- estrazione max/min O(logN)
31
ADT PQ: implementazione con lista ordinata, ADT I classe (max in prima posizione).
Scrivere i PQ.h e PQ.c per le strutture dati e le funzioni:
- PQ PQinit(int maxN);
- int PQempty(PQ pq);
- void PQinsert(PQ pq, Item data);
- Item PQextractmax(PQ pq);
- Item PQshowmax(PQ pq);
- void PQdisplay(PQ pq);
- void PQchange(PQ pq, Item val);
PQ.h
typedef struct pqueue *PQ;
PQ PQinit(int maxN);
int PQempty(PQ pq);
void PQinsert(PQ pq, Item data);
Item PQextractmax(PQ pq);
Item PQshowmax(PQ pq);
void PQdisplay(PQ pq);
void PQchange(PQ pq, Item data);
PQ.c
typedef struct PQnode *link;
struct PQqueue { Item val; link next; };
struct pqueue {link head; };
PQ PQinit(int maxN){
PQ pq = malloc(sizeof(*pq));
pq->head = NULL;
return pq;
}
int PQempty(PQ pq) {
return pq->head == NULL;
}
void PQinsert(PQ pq, Item data){
link x, p;
Key k = KEYget(val);
if(pq->head == NULL || KEYless(k, KEYget(pq->head->val))){
pq->head = NEW(val, pq->head);
return;
}
else{
for(x = pq->head->next, p = pq->head; x !§= NULL && KEYless(k, KEYget(x->val)); p=x, x=x->next);
p->next = NEW(val, x);
return;
}
}
Item PQextractmax(PQ pq){
Item tmp;
tmp = pq->head->val;
link t = pq->head->next;
free(pq->head);
pq->head = t;
return tmp;
}
Item PQshowmax(PQ pq){
return pq->head->val;
}
void PQdisplay(PQ pq){
link x;
for (x = pq->head; x != NULL; x = x->next) ITEMdispaly(x->val);
return;
}
void PQchange(PQ pq, Item val){
link x, p;
for (x = pq->head, p = NULL; x != NULL; p = x, x = x->next){
if(ITEMeq(x->val, val)){
if(x == pq->head) pq->head = x->next;
else p->next = x->next;
free(x);
break;
}
}
PQinsert(pq, val);
return;
}
32
Definizione di Heap
Albero binario con:
- proprietà strutturale: quasi completo (da sx a dx) e quasi bilanciato
- proprietà funzionale: per ogni i ≠ r si ha che Key(Parent(i)) ≥ Key(i)
33
HEAP: che tipo di Item si usa?
tipologia 3:
- char * name
- int value
- chiave che punta a name
34
HEAP: come si implementa?
ADT di I classe, puntatore h
- h-> A vettore di Item
- h->heapsize numero di elementi
- per ogni dato i del vettore, il figlio sx si trova in 2i+1, quello destro in 2i+2, il padre in (i-1)/2
35
HEAP: scrivere i file heap.h e heap.c (prima parte) con le relative strutture dati e funzioni (quasi ADT o ADT di prima classe?):
- Heap HEAPinit(int maxN);
- void HEAPfree(Heap h);
- void HEAPfill(Heap h, Item val);
- void HEAPdisplay(Heap h);
ADT DI PRIMA CLASSE
heap.h
typedef struct heap *Heap;
Heap HEAPinit(int maxN);
void HEAPfree(Heap h);
void HEAPfill(Heap h, Item val);
void HEAPdisplay(Heap h);
heap.c
struct heap { Item *A; int heapsize; }
int LEFT(int i) {return (i*2+1);}
int RIGHT(int i) {return (i*2+2);}
int PARENT(int i) {return ((i-1)/2);}
Heap HEAPinit(int maxN){
Heap h = malloc(sizeof(*h));
h->A = malloc(maxN*sizeof(Item));
h->heaapsize = 0;
return h;
}
void HEAPfree(Heap h){
free(h->A); free(h);
}
void HEAPfill(Heap h, Item val) {
int i;
i = h->heapsize++;
h->A[i] = val;
return;
}
void HEAPdisplay(Heap h){
for(int i = 0; i< h->heapsize; i++) ITEMstore(h->A[i]);
}
36
HEAP: scrivere il file heap.c (seconda parte) con le funzioni:
- void HEAPify(HEAP h, int i);
- void HEAPbuild(Heap h);
- void HEAPsort(Heap h);
void HEAPify(HEAP h, int i){
int l, r, largest;
l = LEFT(i); r = RIGHT(i);
if (l < h->heapsize && KEYcompare(KEYget(h->A[l]), (KEYget(h->A[i])) == 1)
largest = l;
if (r < h->heapsize && KEYcompare(KEYget(h->A[r]), (KEYget(h->A[i])) == 1)
largest = r;
}
if (largest != i){
Swap(h, i, largest);
HEAPify(h, largest);
}
}
void HEAPbuild(Heap h){
int i;
for(i = PARENT(h->heapsize-1); i > 0; i--)
HEAPify(h, i);
}
void HEAPsort(Heap h){
int i, j;
HEAPbuild(h);
j = h->heapsize;
for(i = h->heapsize-1; i>0; i--){
Swap(h, 0, i);
h->heapsize--;
HEAPify(h, 0);
}
h->heapsize = j;
}
37
HEAP: complessità HEAPbuild
Per ogni valore dell'heap, quindi per n volte, viene chiamata la HEAPify che ha complessità log_2(n).
L'equazione alle ricorrenze è T(n) = log_2(n) + 2T(n/2)
dove a = 2 sono i sottoalberi (sottoproblemi) e b = 2 sono i dati dimezzati del sottoproblema
Lo sviluppo per unfolding porta a O(n)
38
HEAP: complessità HEAPsort e caratteristiche
O(nlogN)
in loco
stabile
39
Completa la tabella
PQinsert PQshowmax PQextractmax
vettore non ordinato
lista non ordinata
vettore ordinato
lista ordinata
heap di item/indici
PQinsert PQshowmax PQextractmax
vettore non ordinato 1 O(n) O(n)
lista non ordinata 1 O(n) O(n)
vettore ordinato O(n) 1 1
lista ordinata O(n) 1 1
heap di item/indici O(long) 1 logN
40
PQ: implementazione con HEAP, ADT I classe, vettore di Item
scrivere PQ.h e PQ.c delle funzioni:
- PQ PQinit(int maxN);
- void PQfree(PQ pq);
- int PQempty(PQ pq);
- int PQsize(PQ pq);
- void PQinsert(PQ pq, Item val);
- Item PQshowmax(PQ pq);
- Item PQexctractmax(PQ pq); !!!!
- void PQdisplay(PQ pq);
PQ.h
typedef struct pqueue *PQ;
// tutte le funzioni della domanda
PQ.c
struct pqueue {Item *A; int heapsize; };
// funzioni di LEFT RIGHT PARENT
PQ PQinit(int maxN){
PQ p = malloc(sizeof(*p));
p->A = (Item *)malloc(maxN*sizeof(Item));
p->heapsize = 0;
return p;
}
void PQfree(PQ pq) {
free(pq->A); free(pq);
}
int PQempty(PQ pq) { return pq->heapsize == 0; }
int PQsize(PQ pq) { return pq->heapsize; }
void PQinsert(PQ pq, Item val) {
int i = pq->hepsize++;
Key k = KEYget(val);
while(i≥1 && KEYcompare (KEYget(pq->A[PARENT(i)]), k) == -1) {
pq->A[i] = pq->A[PARENT(i)];
i = PARENT(i);
}
pq->A[i] = val;
return;
}
Item PQshowmax(PQ pq) { return pq->A[0]; }
Item PQexctractmax(PQ pq) {
Item val;
Swap(pq, 0, pq->heapsize-1);
val = pq->A[pq->hepsize-1];
pq->heapsize--;
HEAPify(pq, 0);
return val;
}
void PQdisplay(PQ pq) {
for (int i = 0; i < pq->heapsize; i++) ITEMstore(pq->A[i]);
}
41
PQ: implementazione con HEAP, ADT I classe, vettore di Item
scrivere PQ.c della funzione
- void PQchange(PQ pq, Item val);
void PQchange (PQ pq, Item val) {
int i, found = 0, pos;
for (i = 0; i < pq->heapsize && found == 0; i++)
if (NAMEcmp(NAMEget(&(pq->A[i])), NAMEget(&val))==0) {
found = 1;
pos = i;
}
if (found==1) {
while(pos>=1 && PRIOget(pq->A[PARENT(pos)]) < PRIOget(val)){
pq->A[pos] = pq->A[PARENT(pos)];
pos = PARENT(pos);
}
pq->A[pos] = val;
HEAPify(pq, pos);
}
else printf("key not found!\n");
return;
}
42
PQ: implementazione con HEAP, ADT I classe, vettore di indici
scrivere PQ.h e PQ.c delle funzioni:
- PQ PQinit(int maxN);
- void PQfree(PQ pq);
- int PQempty(PQ pq);
- int PQsize(PQ pq);
- void PQinsert(PQ pq, int index, int prio);
- Item PQshowmax(PQ pq);
- Item PQexctractmax(PQ pq);
- static void Swap(PQ pq, int pos1, int pos2); (solo .c)
- static void HEAPify(PQ pq, int i); (solo .c)
PQ.h
typedef struct pqueue *PQ;
// funzioni
PQ.c
typedef struct { int index; int prio; } heapItem;
struct pqueue { heapItem *A; int heapsize; int *qp};
PQ PQinit(int maxN){
PQ p = malloc(sizeof(*p));
p->A = (heapItem *)malloc(maxN*sizeof(heapItem));
p->qp = malloc(maxN*sizeof(int));
for (int i = 0; i < maxN; i++) {
p->A[i].index = -1; p->qp[i] = -1;
}
p->heapsize = 0;
return p;
}
void PQfree(PQ pq) {
free(pq->qp); free(pq->A); free(pq);
}
int PQempty(PQ pq) { return pq->heapsize == 0; }
int PQsize(PQ pq) { return pq->heapsize; }
void PQinsert(PQ pq, int index, int prio) {
int i, j;
i = pq->hepsize++;
Key k = KEYget(val);
while(i≥1 && (pq->A[PARENT(i)].prio) < prio)){
pq->A[i] = pq->A[PARENT(i)];
pq->qp[pq->A[i].index] = I;
i = PARENT(i);
}
pq->A[i].index = index;
pq->A[i].prio = prio;
pq->qp[index] = i;
}
Item PQshowmax(PQ pq) { return pq->A[0]; }
static void Swap(PQ pq, int pos1, int pos2){
heapItem temp;
int index1, index2;
temp = pq->A[pos1];
pq->A[pos1] = pq->A[pos2]; pq->A[pos2] = temp;
// update correspondence index-pos
index1 = pq->A[pos1].index;
index2 = pq->A[pos2].index;
pq->qp[index1] = pos1;
pq->qp[index2] = pos2;
}
static void HEAPify(PQ pq, int i) {
int l, r, largest;
l = LEFT(i);
r = RIGHT(i);
if (l < pq->heapsize && (pq->A[l].prio > pq->A[i].prio))
largest = l;
else
largest = i;
if (r < pq->heapsize && (pq->A[r].prio > pq->A[largest].prio))
largest = r;
if (largest != i) {
Swap(pq, i, largest);
HEAPify(pq, largest);
}
}
Item PQexctractmax(PQ pq) {
int res;
int j=0;
Swap (pq, 0, pq->heapsize-1);
res = pq->A[pq->heapsize-1].index;
pq->qp[res]=-1;
pq->heapsize--;
pq->A[pq->heapsize].index=-1; // redundant
HEAPify(pq, 0);
return res;
}
43
PQ: implementazione con HEAP, ADT I classe, vettore di indici
scrivere il file PQ.c della funzione
void PQchange (PQ pq, int index, int prio);
void PQchange (PQ pq, int index, int prio) {
int pos = pq->qp[index];
heapItem temp = pq->A[pos];
temp.prio = prio; // new prio
while ((pos>=1) && (pq->A[PARENT(pos)].index < prio) {
pq->A[pos] = pq->A[PARENT(pos)];
pq->qp[pq->A[pos].index] = pos;
pos = PARENT(pos);
}
pq->A[pos] = temp;
pq->qp[index] = pos;
HEAPify(pq, pos);
}
44
ST: definizione; tipo di item, implementazioni
La tabella di simboli è un ADT che supporta operazioni di Insert, Search, Delete
Si realizza con item di tipo 3 e implementazione di quasi ADT
Le implementazioni più comuni sono le tabelle ad accesso diretto, strutture lineari, BST e varianti, tabelle di hash
45
ST: complessità generale del caso PEGGIORE per INSERT, SEARCH, SELECT per le strutture dati:
- tabelle ad accesso diretto
- vettori e liste non ordinate
- vettori e liste ordinate
- BST !!!
- tabelle di hash !!!
- tabelle ad accesso diretto: 1, 1, maxN
- vettori e liste non ordinate: 1, N, /
- vettori e liste ordinate N, search nel caso delle liste N mentre nel caso dei vettori con ricerca dicotomica logN, 1
- BST: N, N, N
- tabelle di hash: 1, N, /
46
ST: implementazione tabella ad accesso diretto, ADT I classe
Come sono identificati gli elementi?
Ogni elemento è identificato univocamente dalla chiave
47
ST: implementazione tabella ad accesso diretto, ADT I classe
Scrivere il file ST.c per le funzioni:
- ST STinit(int maxN);
- int STcount(ST st);
- void STfree(ST st);
- void STinsert(ST st, Item val);
- Item STsearch(ST st, Key k);
- void STdelete(ST st, Key k);
- void STdisplay(ST st);
struct symbtab {Item *a; int N; int M;};
ST STinit(int maxN) {
ST st;
int i;
st = malloc(sizeof(*st));
st->a = malloc(maxN * sizeof(Item));
for (i = 0; i < maxN; i++) st->a[i] = ITEMsetvoid();
st->M = maxN;
st->N= 0;
return st;
}
int STcount(ST st) { return st->N; }
void STfree(ST st) {
free(st->a);
free(st);
}
void STinsert(ST st, Item val) {
int index = GETindex(KEYget(val));
st->a[index] = val;
st->N++;
}
Item STsearch(ST st, Key k) {
int index = GETindex(k);
return st->a[index];
}
void STdelete(ST st, Key k) {
st->a[GETindex(k)] = ITEMsetvoid();
st->N--;
}
void STdisplay(ST st){
int i;
for (i = 0; i < st->M; i++)
if (ITEMcheckvoid(st->a[i])==0)
ITEMstore(st->a[i]);
}
48
ST: implementazione tabella ad accesso diretto, ADT I classe
Vantaggi e svantaggi: inserimento, ricerca, cancellazione, inizializzazione, selezione, occupazione di memoria
Inserimento, ricerca e cancellazione T(1)
inizializzazione e selezione Theta(N)
occupazione di memoria Theta(N)
49
ST: implementazione vettore ordinato e non, ADT I classe
Scrivere il file ST.c per le funzioni:
- ST STinit(int maxN);
- int STcount(ST st);
- void STfree(ST st);
- void STdisplay(ST st);
- void STdelete(ST st, Key k);
vettore non ordinato:
- void STinsert(ST st, Item val);
- Item STsearch(ST st, Key k);
vettore ordinato:
- void STinsert(ST st, Item val);
- Item STselect(ST st, int r);
- Item STsearch(ST st, Key k);
- Item searchR(ST st, int l, int r, Key k);
struct symbtab {Item *a; int maxN; int size;};
ST STinit(int maxN) {
ST st; int i;
st = malloc(sizeof(*st));
st->a = malloc(maxN * sizeof(Item) );
for (i = 0; i < maxN; i++) st->a[i] = ITEMsetvoid();
st->maxN = maxN;
st->size = 0;
return st;
}
int STcount(ST st) { return st->size; }
void STfree(ST st) { free(st->a); free(st); }
void STdisplay(ST st){
int i;
for (i = 0; i < st->size; i++) ITEMstore(st->a[i]);
}
void STdelete(ST st, Key k) {
int i, j=0;
while (KEYcmp(KEYget(&st->a[j]), k)!=0) j++;
for (i = j; i < st->size-1; i++)
st->a[i] = st->a[i+1];
st->size--;
}
Inserzione e ricerca in vettore non ordinato
void STinsert(ST st, Item val) {
int i = st->size;
if (st->size >= st->maxN) {
st->a=realloc(st->a,(2*st->maxN)*sizeof(Item));
if (st->a == NULL) return;
st->maxN = 2*st->maxN;
}
st->a[i] = val; st->size++;
}
Item STsearch(ST st, Key k) {
int i;
if (st->size == 0) return ITEMsetvoid();
for (i = 0; i < st->size; i++)
if (KEYcmp(k, KEYget(&st->a[i]))==0)
return st->a[i];
return ITEMsetvoid();
}
Inserzione, selezione e ricerca in vettore ordinato
void STinsert(ST st, Item val) {
int i = st->size++;
if (st->size > st->maxN) {
st->a=realloc(st->a,(2*st->maxN)*sizeof(Item)); if (st->a == NULL)
return;
st->maxN = 2*st->maxN;
} while((i>0)&&KEYcmp(KEYget(&val),KEYget(&st->a[i-1]))==-1){
st->a[i] = st->a[i-1];
i--; }
st->a[i] = val;
}
Item STselect(ST st, int r) { return st->a[r];
}
Item STsearch(ST st, Key k) {
return searchR(st, 0, st->size-1, k) ;
}
Item searchR(ST st, int l, int r, Key k) {
int m;
m = (l + r)/2; if (l > r)
return ITEMsetvoid();
if (KEYcmp(k,KEYget(&st->a[m]))==0)
return st->a[m];
if (l == r)
return ITEMsetvoid();
if (KEYcmp(k, KEYget(&st->a[m]))==-1)
return searchR(st, l, m-1, k); else
return searchR(st, m+1, r, k); }
50
ST: implementazione vettore ordinato e non, ADT I classe
Vantaggi e svantaggi: inizializzazione, inserimento, ricerca, cancellazione, occupazione di memoria,
Vantaggi/svantaggi (vettore non ordinato)
▪ Complessità dell’operazione di inizializzazione e inserimento: T(n) = O(1)
▪ Complessità delle operazioni di ricerca, cancellazione: T(n) = O(N)
▪ Occupazione di memoria S(n) = Theta(maxN), spreco di memoria per |K| << maxN
Vantaggi/svantaggi (vettore ordinato)
▪ ogni inserzione ordinata ha costo lineare T(n) = O(N), costo quadratico complessivo per N inserzioni T(n) = O(N2)
▪ ricerca dicotomica con costo logaritmico T(n) = O(logN)
▪ ricerca lineare con interruzione non appena possibile T(n) =
O(N)
▪ cancellazione con costo lineare T(n) = O(N)
▪ selezione banale: rango e indice coincidono -> O(1)
51
ST: implementazione lista ordinata e non, ADT I classe
Scrivere il file ST.c per le funzioni:
- ST STinit(int maxN);
- void STfree(ST st);
- int STcount(ST st);
- void STdisplay(ST st);
- Item STsearch(ST st, Key k);
- void STdelete(ST st, Key k);
- Inserzione in lista non ordinata
void STinsert(ST st, Item val);
- Selezione in lista ordinata
Item STselect(ST st, int r);
- Inserzione in lista ordinata void STinsert(ST st, Item val);
typedef struct STnode* link;
struct STnode { Item val; link next; } ; typedef struct { link head; int size; } list; struct symbtab { list tab; };
static link NEW( Item val, link next) {
link x = malloc(sizeof *x);
if (x == NULL) return NULL;
x->val = val; x->next = next;
return x;
}
ST STinit(int maxN) {
ST st;
st = malloc(sizeof(*st));
if (st == NULL) return NULL;
st->tab.size = 0;
st->tab.head = NULL;
return st;
}
void STfree(ST st) {
link x, t;
for (x = st->tab.head; x != NULL; x = t) {
t = x->next;
free(x);
}
free(st);
}
int STcount(ST st) {
return st->tab.size;
}
void STdisplay(ST st) {
link x;
for (x = st->tab.head; x != NULL; x = x->next)
ITEMstore(x->val);
}
Item STsearch(ST st, Key k) {
link x;
if (st == NULL)
return ITEMsetvoid();
if (st->tab.head == NULL)
return ITEMsetvoid();
for (x = st->tab.head; x != NULL; x = x->next)
if (KEYcmp( KEYget(&x->val), k) ==0)
return x->val;
return ITEMsetvoid();
}
void STdelete(ST st, Key k) {
link x, p;
if (st == NULL) return;
if (st->tab.head == NULL) return;
for (x=st->tab.head, p=NULL; x!=NULL; p=x, x=x->next) { if (KEYcmp(k, KEYget(&x->val)) == 0) {
}
Inserzione in lista non ordinata
void STinsert(ST st, Item val) {
if (st == NULL) return;
st->tab.head = NEW(val, st->tab.head);
st->tab.size++;
}
Selezione in lista ordinata
Item STselect(ST st, int r) { int i;
link x = st->tab.head;
for (i = r; i>0; i--) x = x->next; return x->val;
}
void STinsert(ST st, Item val) {
link x, p;
if (st == NULL)
return;
if ((st->tab.head == NULL) || (KEYcmp(KEYget(&st->tab.head->val),KEYget(&val))==1))
st->tab.head = NEW(val,st->tab.head);
else {
for (x = st->tab.head->next, p = st->tab.head;
x!=NULL&& (KEYcmp(KEYget(&val),KEYget(&x->val))==1); p = x, x = x->next);
p->next = NEW(val, x);
}
st->tab.size++; }
52
ST: implementazione lista ordinata e non, ADT I classe
Vantaggi e svantaggi: inizializzazione, inserimento, ricerca, cancellazione, selezione, occupazione di memoria
complessità dell’operazione di inizializzazione e inserimento: T(n) = O(1) (inserimento in lista ordinata T(n) = O(n))
▪ complessità delle operazioni di ricerca e cancellazione: T(n) = O(n)
▪ complessità dell’operazione di selezione con lista ordinata: T(n) = O(n)
▪ occupazione di memoria S(n) = Theta(n)
53
BST: qual è il loro vantaggio rispetto alle altre strutture dati?
Permettono di fare operazioni con costo logn
54
BT: definizione ricorsivi
Un BT è un nodo vuoto oppure una terna formata da una radice, un sottoalbero sinistro e uno destro
55
BT: definizione della struct utilizzata
typedef struct node *link;
struct node { Item val; link left; link right; };
56
BT: come accediamo all'albero?
Con un puntatore h alla radice
57
BT: funzione di count del numero di nodi
int count {link h} {
if (h == NULL) return 0;
return count(h->left) + count(h->right) + 1;
}
58
BT: funzione di count dell'altezza
int height(link h){
int u, v;
if (h == NULL) return -1;
u = height(h->left); v = height(h->left);
if (u > v) return u+1;
else return v+1;
}
59
Bt: funzioni di vista, quali sono le tipologie?
Fare esempio con il seguente albero:
Aa
Z ccc
b e7 x1 2z
d 4s2
- pre-ordine
Aa Z b d 4s2 e7 ccc x1 2z
- in-ordine
d b 4s2 Z e7 Aa x1 ccc 2z
- post-ordine
d 4s2 b e7 Z x1 2z ccc Aa
60
Bt: funzioni di vista, pre-ordine
void preOrder{link h}{
if (h == NULL) return;
printf("%s", h->name);
preOrder{h->left};
preOrder{h->right};
}
61
Bt: funzioni di vista, in-ordine
void inOrder{link h}{
if (h == NULL) return;
inOrder{h->left};
printf("%s", h->name);
inOrder{h->right};
}
62
Bt: funzioni di vista, post-ordine
void postOrder{link h}{
if (h == NULL) return;
postOrder{h->left};
postOrder{h->right};
printf("%s", h->name);
}
63
BT: analisi di complessità per le funzioni di visita nei casi:
a) albero completo
b) albero totalmente sbilanciato
a) strategia divide and conquer con a = 2 (sottoalbero sx e dx) e b = 2 (ogni volta si dimezzano i nodi)
divide: O(1)
conquer: O(1)
Equazione alle ricorrenze: T(n) = 1+2T(n/2)
T(1) = 1 ... T(n) = O(n)
b) strategia decrease and conquer con a = 1 k_i = 1
decrease: O(1)
conquer: O(1)
Equazione alle ricorrenze: T(n) = 1+T(n-1)
T(1) = 1 ... T(n) = O(n)
64
Polacca inversa: struttura dati per risolverla e algoritmo
BT
int eval(){
int x = 0;
while (a[i] == ' ') i++;
if (a[i] == '+') {i++; return eval() + eval();}
if (a[i] == '*') {i++; return eval() * eval();}
while ((a[i] >= '0') && ((a[i] <= '9'))) x = 10*x + (a[i++] - '0');
return x;
}
65
BST: definizione
Albero binario non per forza bilanciato in cui in ogni terna il nodo a sinistra della radice ha chiave minore di quella della radice, mentre quello ha destra ce l'ha maggiore.
66
BST: quale struttura dati si utilizza per l'implementazione? Perché questa piuttosto che l'altra?
Scriverne i file BST.h e BST.c
Si utilizza una strategia simile a quella delle liste con ADT di I classe e non invece un vettore perché essendo l'albero potenzialmente sbilanciato ci sarebbe spreco di spazio
BST.h
typedef struct binarysearchtree *BST;
BST.c
typedef struct BSTnode *link;
struct BSTnode { Item val; link left; link right; };
struct binarysearchtree { link root; link z; };
67
BST: scrivere il codice per le funzioni:
- BST BSTinit();
- funzione di creazione di un nodo; di che tipo è e in che file va messa? e la sua dichiarazione?
NEW: funzione di creazione del nuovo che è di tipo static link perché è vista solo dal file.c, quindi non viene dichiarata nel .h
static link NEW(Item val, link left, link right){
link x = malloc(sizeof(*x));
x->val = val; x->left = left; x->right = right;
return x;
}
BST BSTinit(){
BST bst;
bst = malloc(sizeof(*bst));
bst->root = (bs->z = NEW(ITEMsetnull(), NULL, NULL));
}
68
BST: scrivere il codice per le funzioni:
- void BSTfree(BST bst);
void BSTfree(BST bst){
if (bst == NULL) return NULL;
treefree(best->root, bst->z);
free(bst->z);
free(bst);
}
static voi treefree(link h, link z){
if (h == z) return NULL;
treefree(h->l, z);
treefree(h->r, z);
free(h);
}
69
BST: scrivere il codice per le funzioni:
- int BSTcount(BST bst);
- int BSTempty(BST bst);
static int countR(link h, link z){
if (h == z) return 0;
return countR(h->l) + countR(h->r) + 1;
}
int BSTcount(BST bst){
return countR(bst->root, bst->z);
}
int BSTempty(BST bst){
if (BSTcount(bst) == 0) return 1;
return 0;
}
70
BST: scrivere il codice per le funzioni:
- Item BSTsearch(BST bst, Key k);
Item searchR(link h, Key k, link z){
int cmp;
Key kh;
if (h == z) return ITEMsetnull();
kh = ITEMget(h->item);
cmp = KEYcmp(k, kh);
if (cmp == 0) return h->item;
if (cmp == -1) return searchR(h->l, k, z);
else return searchR(h->r, k, z);
}
Item BSTsearch(BST bst, Key k){
return searchR(BST->root, k, bst->z);
}
71
BST: scrivere il codice per le funzioni:
- Item BSTmin(BST bst);
- Item BSTmax(BST bst);
Item minR(link h, link z){
if (h == z) return ITEMsetnull();
if (h->l == z) return h->item;
else return minR(h->l, z);
}
Item BSTmin(BST bst){
return minR(bst->root, bst->z);
}
Item maxR(link h, link z){
if (h == z) return ITEMsetnull();
if (h->r == z) return h->item;
else return maxR(h->r, z);
}
Item BSTmax(BST bst){
return maxR(bst->root, bst->z);
}
72
BST: scrivere il codice per le funzioni:
- void BSTvisit(BST bst, int strategy);
void treePrintR(link h, link z, int strategy){
if (h == z) return;
if (strategy == PREORDER) ITEMstore(h->item);
treePrintR(h->l, z, strategy);
if (strategy == INORDER) ITEMstore(h->item);
treePrintR(h->r, z, strategy);
if (strategy == POSTORDER) ITEMstore(h->item);
}
void BSTvisit(BST bst, int strategy){
if (BSTempty(bst)) return;
else treePrintR(bst->root, bst->z, strategy);
}
73
BST: scrivere il codice per le funzioni:
- void BST insert_leafR(BST bst, Item x);
static link insertR(link h, Item x, link z){
if (h == z) return NEW(x, z, z);
if (KEYcmp(KEYget(x), KEYget(h->item)) == -1)
h->l = insertR(h->l, x, z);
else h->l = insertR(h->r, x, z);
return h;
}
void BST insert_leafR(BST bst, Item x){
bst->root = insertR(bst->root, x, bst->z);
}
74
BST: complessità delle funzioni di INSERT
Se l'albero è completamente bilanciato allora l'altezza è proporzionale a log_2(n), mentre se non è bilanciato è proporzionale a n.
Ne consegue che O(logn) ≤ T(n) ≤ O(n)
75
BST: scrivere il codice per le funzioni:
- link rotR(link h);
- link rotL(link h);
link rotR(link h){
link x;
x = h->l;
h->l = x->r;
x->r = h;
return x;
}
link rotL(link h){
link x;
x = h->r;
h->r = x->l;
x->l = h;
return x;
}
76
BST: scrivere il codice per le funzioni:
- void BSTinsert_root(BST bst, Item x);
static link insertT(link h, Item x, link z){
if (h == z) return NEW(x, z, z);
if (KEYcmp(KEYget(x), KEYget(h->item)) == -1) {
h->l = insertT(h->l, x, z);
h = rotR(h);
}
else {
h->r = insertT(h->r, x, z);
h = rotL(h);
}
return h;
}
void BSTinsert_root(BST bst, Item x){
bst->root = BSTinsert_root(bst->root, x, bst->z);
}
77
BST_estesi: in che modo si può estendere la struttura dati?
Scrivere i file BST.h e BST.c
BST.h
typedef struct binarysearchtree *BST;
BST.c
typedefstruct BSTnode *link;
struct BSTnode { Item item; link p; link l; link r; int N; };
struct binarysearchtree { link root; link z; };
78
BST_estesi: come si modificano queste funzioni?
- BST init();
static link NEW(Item val, link p, link l, link r, int N){
link x = malloc(sizeof(*x));
x->item = item; x-Zp = p; x->l = l; x->r = r; x->N = N;
return x;
}
BST BSTinit(){
BST bst;
bst = malloc(sizeof(*bst));
bst->root = (bs->z = NEW(ITEMsetnull(), NUll, NULL, NULL, 0));
}
79
BST_estesi: come si modificano queste funzioni?
- void BSTinsert_leafR(BST bst, Item x);
static link insertT(link h, Item x, link z){
if (h == z) return NEW(x, z, z, z, 1);
if (KEYcmp(KEYget(x), KEYget(h->item)) == -1) {
h->l = insertT(h->l, x, z);
h->l->p = h;
}
else {
h->r = insertR(h->r, x, z);
h->r->p = h;
}
(h->N)++;
return h;
}
void BST insert_leafR(BST bst, Item x){
bst->root = insertR(bst->root, x, bst->z);
}
80
BST_estesi: come si modificano queste funzioni?
- void BSTinsert_root(BST bst, Item x);
link insertT(link h, Item x, link z){
if (h == z) return NEW(x, z, z, z, 1);
if (KEYcmp(KEYget(x), KEYget(h->item)) == -1) {
h->l = insertT(h->l, x, z);
h = rotR(h);
h->N++;
}
else {
h->r = insertT(h->r, x, z);
h = rotL(h);
h->N++;
}
return h;
}
void BSTinsert_root(BST bst, Item x){
bst->root = insertT(bst->root, x, bst->z);
}
81
BST_estesi: definizione di successore e predecessore di un nodo.
SUCCESSORE
Il successore di un nodo è:
- se il nodo ha il sottoalbero di destra, il minore dei nodi che ci sono alla sua destra quindi il minore dei maggiori del nodo
- se il nodo non ha il sottoalbero di destra, è il primo antenato del nodo il cui figlio sinistro è anche un antenato del nodo.
PREDECESSORE
Il predecessore di un nodo è:
- se il nodo ha il sottoalbero di sinistra, il maggiore dei nodi che ci sono alla sua sinistra quindi il maggiore dei minori del nodo
- se il nodo non ha il sottoalbero di sinistra, è il primo antenato del nodo il cui figlio destro è anche un antenato del nodo.
82
BST_estesi: scrivere il codice per le funzioni:
- Item BSTsucc(BST bst, Key k);
Item searchSucc(link h, Key k, link z){
if (h == z) return ITEMsetNull();
if (KEYcmp(k, KEYget(h->item)) == 0){
if(h->r != 0) return min(h->r, z);
else {
p = h->p;
while (p != z && h == p->r) { // finch il padre esiste e ha è il suo figlio destro
h = p; p = p->p;
}
return p->item;
}
}
if (KEYcmp(k, KEYget(h->item)) == -1) return searchSucc(h->l, k, z);
else return searchSucc(h->r, k, z);
}
Item BSTsucc(BST bst, Key k){
return searchSucc(best->root, k, bst->z);
}
83
BST_estesi: scrivere il codice per le funzioni:
- Item BSTpred(BST bst, Key k);
Item searchPred(link h, Key k, link z){
if (h == z) return ITEMsetNull();
if (KEYcmp(k, KEYget(h->item)) == 0){
if(h->l != 0) return max(h->l, z);
else {
p = h->p;
while (p != z && h == p->l) { // finch il padre esiste e ha è il suo figlio destro
h = p; p = p->p;
}
return p->item;
}
}
if (KEYcmp(k, KEYget(h->item)) == -1) return searchSucc(h->l, k, z);
else return searchSucc(h->r, k, z);
}
Item BSTpred(BST bst, Key k){
return searchPred(best->root, k, bst->z);
}
84
BST_estesi: scrivere il codice per le funzioni:
- Item BSTselect(BST bst, int r);
Item selectR (link h, int r, link z){
int t;
if (h == z) rerun ITEMsetNull();
t = h->l->N;
if (t > r) return selectR(h->l, r, z);
if (t < r) return selectR(h->r, r-t-1, z);
return h->item;
}
Item BSTselect(BST bst, int r){
return selectR(bst->root, r, bst->z);
}
85
BST_estesi: scrivere il codice per le funzioni:
- link rotR(link h);
- link rotL(link h);
link rotR(link h){
link x = h->l; //
h-l> = x->r; //
x->r->p = h;
x->r = h; //
x->p = h->p;
h->p = x;
x->N = h->N;
h->N = 1;
h->N += (h->l) ? h->l->N : 0;
h->N += (h->r) ? h->r->N : 0;
}
link rotL(link h){
link x = h->r;
h->r = x->l;
x->l->p = h;
x->l = h;
x->p = h->p;
h->p = x;
x->N = h->N;
h->N = 1;
h->N += (h->l) ? (h->l->N) : 0;
h->N += (h->r) ? (h->r->N) : 0;
}
86
BST_estesi: scrivere il codice per le funzioni:
- link partR(link h, int r);
Come funziona il partizionamento?
Il partizionamento riorganizza l’albero mettendo in radice l’r-esima chiave più piccola.
link partR(link h, int r){
int t = h->l->N;
if (t > r) { h->l = partR(h->l, r); h = rotR(h); }
if (t < r) { h->r = partR(h->r, r-t-1); h = rotL(h); }
return h;
}
87
BST_estesi: scrivere il codice per le funzioni:
- link joinLR(link a, link b, link z);
- void BSTdelete(BST bst, Key k);
void BSTdelete(BST bst, Key k){
bst->root = deleteR(bst->root, k, bst->z);
}
link deleteR(link h, Key k, link z){
link y, p;
if (h == z) return z;
if(KEYcmp(k, KEYget(h->item)) == -1) h->l = deleteR(h->l, k, z);
if(KEYcmp(k, KEYget(h->item)) == 1) h->r = deleteR(h->r, k, z);
(h->N)--; // aggiornamento numero nodi
if (KEYcmp(k, KEYget(h->item)) == 0){
y = h; p = h->p;
h = joinLR(h->l, h->r, z);
h->p = p;
free(y);
}
return h;
}
link joinLR(link a, link b, link z){
if(b == z) return a;
b = partR(b, 0);
b->l = a;
a->p = b;
b->N = a->N + b->r->N + 1;
return b;
}
88
BST_estesi: scrivere il codice per le funzioni:
- void BSTbalance(BST bst);
In cosa consiste?
Si tratta di un partizionamento ricorsivo intorno alla chiave mediana inferiore.
void BSTbalance(BST bst){
bst->root = balanceR(bst->root, bst->z);
}
link balanceR(link h, link z){
int r;
if (h == z) return z;
r = (h->N+1)/2-1;
h = partR(h, r);
h->l = balanceR(h->l, z);
h->r = balanceR(h->r, z);
return h;
}
89
TABELLE DI HASH: per cosa le utilizziamo?
per le tabelle di simboli
90
TABELLE DI HASH: in generale qual è la loro complessità?
Possono arrivare ad essere O(1), ma comunque O(1) è in stretta parentela con O(logN) (BST)
91
TABELLE DI HASH: cosa cambia dagli altri metodi di rappresentazione delle tabelle di simboli?
A parte le tabelle ad accesso diretto in cui c'è corrispondenza univoca chiave-indice, gli altri metodi si basano sul confronto mentre le tabelle di hash no
92
TABELLE DI HASH: come vengono rappresentate?
ADT con occupazione O(|K|) e tempo medio di accesso O(1). Non essendoci il confronto non c'è ordinamento o select
93
TABELLE DI HASH: cosa fa la chiave di Hash?
La funzione chiave di hash trasforma la chiave in un indice e quindi in una posizione in tabella
h: U --> {0, 1, ..., M-1}
dove M è la DIM della tabella
94
TABELLE DI HASH: cos'è la collisione?
La collisione è causata dal fatto che nelle tabelle di hash non c'è corrispondenza chiave-indice e quindi a più chiavi può corrispondere lo stesso indice.
95
TABELLE DI HASH: struttura dati
ADT di I classe ST e quasi ADT, 3, per l'item
96
TABELLE DI HASH: funzione di hash ideale e nella realtà
Una funzione di hash ideale presuppone che, date k chiavi, le h(k) siano equiprobabili e quindi che tutte le chiavi siano scorrelate tra loro.
In realtà è tutto il contrario e per rendere i valori h(k) equiprobabili bisogna cercare di scorrelare h(k_i) da h(k_j) per ogni i, j con lo scopo di distribuire uniformemente le h(k)
97
TABELLE DI HASH: funzione di hash con metodo moltiplicativo
Questo metodo prevede numeri in virgola mobile nell'intervallo s ≤ k ≤ t per le chiavi.
h(k) = [(k-s)/(t.s)]*M
int hash(float k, int M, float s, float t) {
return ((k-s)/(t.s))*M;
}
98
TABELLE DI HASH: funzione di hash con metodo modulare (3 casi)
a) chiavi: numeri interi
M: numero primo
h(k) = k%M
int hash(int k, int M) { return k%M; }
b, c) chiavi: stringhe alfanumeriche corte e lunghe che derivano dalla valutazione di polinomi in una data base (se sono stringhe lunghe derivano dal metodo di Horner)
h(k) = k%M
in generale, per esempio se la base è 127 e la stringa è 'now', allora
k = 'n'*127^2 + 'o'*127^1 + 'w'*127^0
Quando le stringhe sono lunghe si preferisce calcolare il modulo.
int hash(char *v, int M){
int h = 0, base = 127;
for( ; *v != '\0'; v++){
h = (base*h + *v)%M;
}
return h;
}
o ancora più precisa, cioè che forma indici ancora più equiprobabili:
int hashU(char * v, int M){
int h, a = 31415, b = 27183;
for (h = 0; *v != '\0'; v++, a = a*b % (M-1)){
h = (a*h + *v)%M;
}
return h;
}
99
TABELLE DI HASH: a cosa serve il numero primo?
Evita di usare solo gli ultimi n bit di k se M = 2^n e di usare solo le ultime n cifre decimali di k se M ? 10^n
100
TABELLE DI HASH: definizione di collisione, possibili metodi di gestione
def := h(k_i) = h(k_j) per k_i ≠ k_j
Gestione: linear chaining o open addressing
101
TABELLE DI HASH: linear chaining, caratteristiche
Prevede che ci siano anche più elementi nella stessa cella -> stesso indice. Quindi la tabella è un vettore di liste. La dimensione è M = n°elementi/n°elementi per lista. M è il primo numero primo ≥ (n°elementi/n°elementi per lista).
102
TABELLE DI HASH: linear chaining, struttura dati in ST.h e ST.c
ST.h
typedef struct symboltable *ST;
ST.c
typedef struct node *link;
struct node { Item item; link next; };
struct symboltable { link *heads; int N; int M; link z; };
103
TABELLE DI HASH: linear chaining, codice delle funzioni:
- ST STinit(int maxN, float r);
- void STfree(ST st);
static int STsizeSet(int maxN, float r){
int primes[16] = {2, 3, 5, 7, 11, 13, 17, 19, 23, ..., 53};
int i = 0, size = maxN/r;
if (size < primes[15]) {
for (i = 0; i < 16; i++){
if(size <= primes[i]) return primes[i];
}
else return -1;
}
}
ST STinit(int maxN, float r){
ST st;
st = malloc(sizeof *st);
st->N = 0;
st->M = STsizeSet(maxN, r);
st->heads = malloc(st->M*sizeof(link));
st->z = NEW(ITEMsetNull(), NULL);
for (int i = 0; i < st->M; i++) st->heads[i] = st->z;
return st;
}
void STfree(ST st){
int i; link t, u;
for (i = 0; i < st->M; i++){
for (t = st->heads[I]; t != st->z; t = u){
u = t->next;
free(t);
}
free(st->z);
free(st->heads);
free(st);
}
}
104
TABELLE DI HASH: linear chaining, codice delle funzioni:
- int STcount(ST st);
- int STempty(ST st);
int STcount(ST st){
return st->N;
}
int STcount(ST st){
if (STcount(st) == 0) return 1;
return 0;
}
105
TABELLE DI HASH: linear chaining, codice delle funzioni:
- void STinsert(ST st, Item val);
void STinsert(ST st, Item val){
int i;
i = hash(KEYget(&val), st->M);
st->heads[I] = NEW(val, st->heads[I]);
}
106
TABELLE DI HASH: linear chaining, codice delle funzioni:
- Item STsearch(ST st, Key k);
- void STdelete(ST st, Key k);
Item searchR(link h, Key k, link z){
if (t == z) return ITEMsetNull();
if (KEYcmp(k, KEYget(&h->item)) == 0) return t->item;
return searchR(h->next, k, z);
}
Item STsearch(ST st, Key k){
int i = hash(k, st->M);
return searchR(st->heads[i], k, st->z);
}
void deleteR(link h, Key k){
if (h == NULL) return NULL;
if (KEYcmp(k, KEYget(&h->item)) == 0) {
link t = h->next; free(t);
return t;
}
h->next = deleteR(h->next, k);
return h;
}
void STdelete(ST st, Key k) {
int i = hash(k, st->M);
st->heads[I] = deleteR(st->heads[I], k);
}
107
TABELLE DI HASH: linear chaining, codice delle funzioni:
- void STdisplay(ST st);
void visitR(link h, link z){
if (h == z) return;
ITEMstore(h->item);
visitR(h->next, z);
}
void STdisplay(ST st){
for(i = 0; i < st->M; i++){
visitR(st->heads[I], st->z)};
}
108
TABELLE DI HASH: linear chaining, complessità (hp. liste non ordinate) delle funzioni di:
- inserimento
- ricerca caso peggiore e medio
- cancellazione
- inserimento O(1) -> in testa
- ricerca caso peggiore e medio O(n), O(1+ alpha) con alpha = N/M
- cancellazione come ricerca oppure O(1) non so quando però
109
TABELLE DI HASH: open addressing
Ogni cella può contenere un solo elemento -> collisione. Si risolve la collisione mediante Probing: linear probing, quadratic probing, double hashing
110
TABELLE DI HASH: clustering
Il clustering è il raggruppamento di posizioni occupate contigue
111
TABELLE DI HASH: open addressing, strutture dati ST.h e ST.c
ST.h
typedef struct symboltable *ST;
ST.c
struct symboltable { Item *a; int N; int M; };
112
TABELLE DI HASH: open addressing, codice delle funzioni:
- ST STinit(int maxN, float a);
ST STinit(int maxN, float a){
int i;
ST st = malloc(sizeof(*st));
st->N = 0;
st->M = STsizeSet(maxN, a);
if (st->M == -1) st = NULL;
else {
st->a = malloc(st->M*sizeof(Item));
for (i = 0; i < st->M; i++){
st->a[i] = ITEMsetNull();
}
}
return st;
}
113
TABELLE DI HASH: open addressing, linear probing (caso di delete: cancellazione e reinserimento di tutte le chiavi), codice delle funzioni:
- void STinsert(ST st, Item item);
- int full(ST st, int i);
- Item STsearch(ST st, Key k);
int full(ST st, int i){
if(ITEMcheckNull(st->a[i])) return 0;
return 1;
}
void STinsert(ST st, Item item){
int i = hash(KEYget(&item), st->M);
while(full(st, i)) I = (I+1)%st->M;
st->a[i] = item;
st->N++;
}
Item STsearch(ST st, Key k){
int i = hash(k, st->M);
while(full(st, i)){
if(KEYcmp(k, KEYget(&st->a[i])) == 0) return st->a[i];
else i = (i+1)%st->M;
}
return ITEMsetNull();
}
114
TABELLE DI HASH: open addressing, linear probing (caso di delete: vettore status), variazione della struttura dati ST.h e ST.c
ST.h
typedef struct symboltable *ST;
ST.c
struct symboltable { Item *a; int *status; int M; int N; };
115
TABELLE DI HASH: open addressing, linear probing (caso di delete: cancellazione e reinserimento di tutte le chiavi), codice delle funzioni:
- void STdelete(ST st, Key k);
void STdelete(ST st, Key k){
int j, i = hash(k, st->M);
Item tmp;
while(full(st, i)){
if (KEYcmp(k, KEYget(&st->a[i])) == 0) break;
else i = (i+1)%st->M;
}
if (ITEMcheckNull(st->a[i])) return;
st->a[i] = ITEMsetNull(); st->N--;
for(j = i+1; full(st, j); j = (j+1)%st->M, st->N--){
tmp = st->a[i];
st->a[j] = ITEMsetNull();
STinsert(st, tmp);
}
}
116
TABELLE DI HASH: open addressing, linear probing (caso di delete: vettore status), codice delle funzioni:
- void STinsert(ST st, Item item);
- Item STsearch(ST st, Key k);
- void STdelete(ST st, Key k);
static int CheckFull(ST st, int i){
if (st->status[i] == 1) return 1;
return 0;
}
static int CheckDeleted(ST st, int i){
if (st->status[i] == -1) return 1;
return 0;
}
void STinsert(ST st, Item item){
int i = hash(KEYget(&item), st->M);
while(CheckFull(st, i)) i = (i+1)%st->M;
st->a[i] = item;
st->status[i] = 1;
st->N++;
}
Item STsearch(ST st, Key k){
int i = hash(k, st->M);
while(CheckFull(st, i) == 1 || CheckDeleted(st, i) == -1)
if (KEYcmp(k, KEYget(&st->a[i])) == 0) return st->a[i];
else I = (I+1)%st->M;
return ITEMsetNull();
}
void STdelete(ST st, Key k){
int i = hash(k, st->M);
while(CheckFull(st, i) == 1 || CheckDeleted(st, i) == -1)
if (KEYcmp(k, KEYget(&st->a[i])) == 0) break;
else I = (I+1)%st->M;
}
if(ITEMcheckNull(st->a[i])) return;
st->a[i] = ITEMsetNull();
st->N--;
st->status[i] = -1;
}
117
TABELLE DI HASH: open addressing, linear probing, tentativi in media per il search hit e il search miss
search hit: 1/2 *(1+1/(1-alpha))
search miss: 1/2 *(1+1/[(1-alpha)^2])
118
TABELLE DI HASH: open addressing, quadratic probing. Vantaggi e caratteristiche
- evita cluster troppo grandi
- i: contatore dei tentativi
- index = (h'(k) + c_1*i + c_2*i^2)%M
- se M = 2^k, c_1 = c_2 = 1/2
- se M primo o alpha < 0.5, c_1 = c_2 = 0.5 || = 1 || c_1 = 0 c_2 = 1
119
TABELLE DI HASH: open addressing, quadratic probing, codice delle funzioni:
- void STinsert(ST st, Item item);
- Item STsearch(ST st, Key k);
- void STdeleted(ST st, Key k);
con c1 = c2 = 1
# define c1 1
# define c2 1
void STinsert(ST st, Item item){
int i = 0;
int start = hash(KEYget(&item), st->M);
int index = start;
while(full(st, index)){
i++;
index = (start + c1*i + c2*i*i)%st->M;
}
st->a[index] = item;
st->N++;
}
Item STsearch(ST st, Key k) {
int i=0, start = hash(k, st->M), index = start;
while (full(st, index))
if (KEYcmp(k, KEYget(&st->a[index]))==0) return st->a[index];
else {
i++;
index = (start + c1*i + c2*i*i)%st->M;
}
return ITEMsetNull();
}
void STdeleted(ST st, Key k){
int i = 0;
int start = hash(k, st->M), index = start;
Item tmp;
while(full(st, index))
if(KEYcmp(k, KEYget(&st->a[index])) == 0) break;
else { I++; index = (start+ c1*i + c2*i*i)%st->M; }
if(ITEMcheckNull(st->a[index])) return;
st->a[index] = ITEMsetNull();
st->N--; i++;
index = (start+ c1*i + c2*i*i)%st->M;
while (full(st, index)){
tmp = st->a[index];
st->a[index] = ITEMsetNull(9;
st->N--; i++;
STinsert(st, tmp);
index = (start+ c1*i + c2*i*i)%st->M;
}
}
120
TABELLE DI HASH: open addressing, double hashing, caratteristiche:
- vengono calcolate le funzioni di hash per i e j
- i = (i+j) %M
- i nuovo non può essere come i vecchio perché sarebbe un ciclo infinito
121
TABELLE DI HASH: open addressing, double hashing, codice delle funzioni:
- void STinsert(ST st, Item item);
- Item STsearch(ST st, Key k);
- void STdelete(ST st, Key k);
static int hash1(Key k, int M) {
int h = 0, base = 127;
for ( ; *k != '\0'; k++) h = (base * h + *k) % M;
return h;
}
static int hash2(Key k, int M) {
int h = 0, base = 127;
for ( ; *k != '\0'; k++) h = (base * h + *k);
h = ((h % 97) + 1)%M;
if (h==0) h=1;
return h;
}
void STinsert(ST st, Item item) {
int i = hash1(KEYget(&item), st->M);
int j = hash2(KEYget(&item), st->M);
while (full(st, i)) i = (i+j)%st->M;
st->a[i] = item; st->N++;
}
Item STsearch(ST st, Key k) {
int i = hash1(k, st->M);
int j = hash2(k, st->M);
while (full(st, i))
if (KEYcmp(k, KEYget(&st->a[i]))==0) return st->a[i];
else i = (i+j)%st->M;
return ITEMsetNull();
}
void STdeleted(ST st, Key k){
int i = hash1(k, st->M), j = hash2(k);
Item tmp;
while(full(st, i))
if(KEYcmp(k, KEYget(&st->a[i])) == 0) break;
else { i = (i+j)%st->M;}
if(ITEMcheckNull(st->a[i])) return;
st->a[i] = ITEMsetNull();
st->N--;
i = (i+j)%st->M;
while (full(st, i)){
tmp = st->a[i];
st->a[i] = ITEMsetNull(9;
st->N--;
STinsert(st, tmp);
i = (i+j)%st->M;
}
}
122
TABELLE DI HASH: open addressing, double hashing, tentativi in media di probing per la ricerca:
- search hit
- search miss
- search hit: 1/(1-alpha)
- search miss: 1/alpha * ln(1/1-alpha)
123
Tabelle di hash VS BST
BST: prestazioni migliori, ordinamenti possibili
HASH: più facili da realizzare, unica soluzione per chiavi senza relazione d'ordine, più facili per chiavi semplici
124
Cosa fa la HEAPify?
Trasforma in heap l'albero i-esimo (infatti HEAPify(Heap h, int i)) supponendo che i suoi figli siano già heap -> per questo nella HEAPbuild si parte dal fondo
125
Quali sono i modi per implementare lo stack?
Lo stack è un tipo di coda generalizzata e quindi può essere implementato con vettori e liste, in quasi ADT (in realtà NON ADT) e ADT di prima classe. In questo caso non ha senso parlare di ordine perché le operazioni di push e pop non lo prevedono ovviamente.
126
ST: complessità generale del caso MEDIO per INSERT, SEARCH, SELECT per le strutture dati:
- tabelle ad accesso diretto
- vettori e liste non ordinate
- vettori e liste ordinate
- BST
- tabelle di hash
- tabelle ad accesso diretto: 1, 1, maxN/2
- vettori e liste non ordinati: 1, N/2, /
- vettori e liste ordinate: N/2, N/2 (e logN nel caso del vettore con ricerca dicotomica), stessa cosa per la select
- BST: logN, logN, logN
- tabelle di hash: 1, 1, /
127
BST: scrivere il codice per le funzioni:
- void BST insert_leafI(BST bst, Item x)
void BST insert_leafI(BST bst, Item x) {
link p = bst -> root, h = p;
if (bst -> root == bst->z) {
bst->root = NEW(x, bst->, bst->z);
return;
}
while (h != bst->z) {
p = h;
h = (KEYcmp(KEYget(x), KEYget(h->item)) == -1) ? h->l : h->r;
}
h = NEW(x, bst->z, bst->z);
if (KEYcmp(KEYget(x), KEYget(p->item)) == -1) p->l = h;
else p->r = h;
}
128
ST: tabelle ad accesso diretto. Codice della
Item STselect(ST st, int r);
Item STselect(ST st, int r) {
int i;
for (i = 0; i < st->M; i++)
if ((ITEMcheckvoid(st->a[i])==0) && (r-- == 0)) return st->a[i];
return NULL;
}
129
BST estesi: come si modifica la seguente funzione?
void BST insert_leafI(BST bst, Item x)
void BST insert_leafI(BST bst, Item x) {
link p = bst -> root, h = p;
if (bst -> root == bst->z) {
bst->root = NEW(x, bst->z, bst->z, bst->z, 1);
return;
}
while (h != bst->z) {
p = h;
h->N++;
h = (KEYcmp(KEYget(x), KEYget(h->item)) == -1) ? h->l : h->r;
}
h = NEW(x, p, bst->z, bst->z, 1);
if (KEYcmp(KEYget(x), KEYget(p->item)) == -1) p->l = h;
else p->r = h;
}
130
IBST: come sono fatti e cos'hanno in più/meno rispetto ai BST?
- hanno item fatti di low e high
- vengono ordinati in base al campo low
- non hanno il puntatore al padre
- hanno sempre N e anche il Max che è il MAX tra gli high dei loro sottoaalberi
131
IBST: quando due intervalli si sovrappongono?
quando low[I] < high[I'] && low[I'] < high[I]
132
IBST: typedef e struct in generale
typedef struct intervalbst *IBST;
struct intervalbst { lins root; link z; int size; };
typedef struct IBSTnode *link;
struct IBSTnode { Item val; int N, int max; link l; link r; };
133
IBST: codice delle funzioni:
- void IBSTinsert_leaf(IBST ibst, Item item);
- link rotL(link h);
- link IBSTdelete(IBST ibst, Item item);
- Item IBSTsearch(IBST ibst, Item item);
appunti
134
IBST: esempio di applicazione
verificare se le piste si intersecano in un circuito elettronico
