P - ADT

Question 1

Perché un dato è detto astratto?

Answer 1

Perché maschera la sua implementazione mediante la coppia di moduli interfaccia/implementazione

Question 2

Quali sono le caratteristiche di un quasi ADT?

Answer 2

• 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

Question 3

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.

Answer 3

• 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; };

Question 4

Quali sono i modi per definire l’ADT Item?

Answer 4

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

Question 5

Qual è il prototipo della KEYget in base al tipo di Item per i quasi ADT?

Answer 5

Key KEYget(Item val); nei casi 1 e 2
Key KEYget(Item *pval); nei casi 3 e 4

Question 6

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

Answer 6

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

Question 7

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

Answer 7

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

Question 8

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

Answer 8

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

Question 9

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

Answer 9

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

Question 10

In quali casi di Item ha senso la deallocazione?

Answer 10

Solo nei casi 2 e 4.

Question 11

Quali tipi di Item usiamo per gli ADT di I classe?
Cosa si trova nel file.h?

Answer 11

Usiamo il 3 e il 4.

file.h
typedef struct item *Item;
typedef struct char *Key;
…

Question 12

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

Answer 12

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

Question 13

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)

Answer 13

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

Question 14

Quali sono i criteri possibili di Delete nelle code in generale?

Answer 14

• FIFO
• LIFO
• priorità
• casuale
• contenuto (tabella di simboli)

Question 15

In che modo si possono implementare le code, in generale, e quali sono vantaggi e svantaggi?

Answer 15

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

Question 16

ADT Stack: quali funzioni lo caratterizzano e qual è la loro complessità?

Answer 16

stackpush e stackpop, O(1)

Question 17

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

Answer 17

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];
}

Question 18

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

Answer 18

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

Question 19

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

Answer 19

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

Question 20

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

Answer 20

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

Question 21

ADT QUEUE: quali operazioni lo caratterizzano e che complessità hanno?

Answer 21

QUEUEput e QUEUEget, O(1)
FIFO

Question 22

ADT QUEUE: come si può implementare? Quali sono le caratteristiche?

Answer 22

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

Question 23

Come funziona il buffer circolare?

Answer 23

• 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

Question 24

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

Answer 24

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++];
}

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

Answer 25

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++];
}

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

Answer 26

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

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

Answer 27

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

Question 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à

Answer 28

• inserzione in testa alla lista o in coda al vettore: O(1)
• estrazione del max/min O(N)
• cambio di priorità O(N)

Question 29

ADT PQ: implementazione con vettore/lista ordinato
Complessità di:
- inserzione ordinata
- estrazione del max/min
- cambio di priorità

Answer 29

• inserzione ordinata O(N)
• estrazione del max/min O(1)
• cambio di priorità O(N)

Question 30

ADT PQ: implementazione con heap di item/indici
Complessità di:
- inserzione
- show max/min
- estrazione max/min

Answer 30

• inserzione O(logN)
• show max/min O(1)
• estrazione max/min O(logN)

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

Answer 31

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

Question 32

Definizione di Heap

Answer 32

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)

Question 33

HEAP: che tipo di Item si usa?

Answer 33

tipologia 3:
- char * name
- int value
- chiave che punta a name

Question 34

HEAP: come si implementa?

Answer 34

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

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

Answer 35

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 (i2+1);}
int RIGHT(int i) {return (i2+2);}
int PARENT(int i) {return ((i-1)/2);}

Heap HEAPinit(int maxN){
Heap h = malloc(sizeof(h));
h->A = malloc(maxNsizeof(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]);
}

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

Answer 36

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

Question 37

HEAP: complessità HEAPbuild

Answer 37

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)

Question 38

HEAP: complessità HEAPsort e caratteristiche

Answer 38

O(nlogN)
in loco
stabile

Question 39

Completa la tabella

                                 PQinsert     PQshowmax       PQextractmax vettore non ordinato lista non ordinata vettore ordinato lista ordinata heap di item/indici

Answer 39

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

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

Answer 40

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(maxNsizeof(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]);
}

Question 41

PQ: implementazione con HEAP, ADT I classe, vettore di Item
scrivere PQ.c della funzione
- void PQchange(PQ pq, Item val);

Answer 41

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

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

Answer 42

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(maxNsizeof(heapItem));
p->qp = malloc(maxNsizeof(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;
}

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

Answer 43

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

Question 44

ST: definizione; tipo di item, implementazioni

Answer 44

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

Question 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 !!!

Answer 45

• 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, /

Question 46

ST: implementazione tabella ad accesso diretto, ADT I classe
Come sono identificati gli elementi?

Answer 46

Ogni elemento è identificato univocamente dalla chiave

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

Answer 47

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

Question 48

ST: implementazione tabella ad accesso diretto, ADT I classe
Vantaggi e svantaggi: inserimento, ricerca, cancellazione, inizializzazione, selezione, occupazione di memoria

Answer 48

Inserimento, ricerca e cancellazione T(1)
inizializzazione e selezione Theta(N)
occupazione di memoria Theta(N)

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

Answer 49

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,(2st->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,(2st->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); }

Question 50

ST: implementazione vettore ordinato e non, ADT I classe
Vantaggi e svantaggi: inizializzazione, inserimento, ricerca, cancellazione, occupazione di memoria,

Answer 50

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

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

Answer 51

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++; }

Question 52

ST: implementazione lista ordinata e non, ADT I classe
Vantaggi e svantaggi: inizializzazione, inserimento, ricerca, cancellazione, selezione, occupazione di memoria

Answer 52

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)

Question 53

BST: qual è il loro vantaggio rispetto alle altre strutture dati?

Answer 53

Permettono di fare operazioni con costo logn

Question 54

BT: definizione ricorsivi

Answer 54

Un BT è un nodo vuoto oppure una terna formata da una radice, un sottoalbero sinistro e uno destro

Question 55

BT: definizione della struct utilizzata

Answer 55

typedef struct node *link;
struct node { Item val; link left; link right; };

Question 56

BT: come accediamo all’albero?

Answer 56

Con un puntatore h alla radice

Question 57

BT: funzione di count del numero di nodi

Answer 57

int count {link h} {
if (h == NULL) return 0;
return count(h->left) + count(h->right) + 1;
}

Question 58

BT: funzione di count dell’altezza

Answer 58

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

Question 59

Bt: funzioni di vista, quali sono le tipologie?
Fare esempio con il seguente albero:
Aa
Z ccc
b e7 x1 2z
d 4s2

Answer 59

• 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

Question 60

Bt: funzioni di vista, pre-ordine

Answer 60

void preOrder{link h}{
if (h == NULL) return;
printf(“%s”, h->name);
preOrder{h->left};
preOrder{h->right};
}

Question 61

Bt: funzioni di vista, in-ordine

Answer 61

void inOrder{link h}{
if (h == NULL) return;
inOrder{h->left};
printf(“%s”, h->name);
inOrder{h->right};
}

Question 62

Bt: funzioni di vista, post-ordine

Answer 62

void postOrder{link h}{
if (h == NULL) return;
postOrder{h->left};
postOrder{h->right};
printf(“%s”, h->name);
}

Question 63

BT: analisi di complessità per le funzioni di visita nei casi:
a) albero completo
b) albero totalmente sbilanciato

Answer 63

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)

Question 64

Polacca inversa: struttura dati per risolverla e algoritmo

Answer 64

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

Question 65

BST: definizione

Answer 65

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.

Question 66

BST: quale struttura dati si utilizza per l’implementazione? Perché questa piuttosto che l’altra?
Scriverne i file BST.h e BST.c

Answer 66

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

Question 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?

Answer 67

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

Question 68

BST: scrivere il codice per le funzioni:
- void BSTfree(BST bst);

Answer 68

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

Question 69

BST: scrivere il codice per le funzioni:
- int BSTcount(BST bst);
- int BSTempty(BST bst);

Answer 69

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

Question 70

BST: scrivere il codice per le funzioni:
- Item BSTsearch(BST bst, Key k);

Answer 70

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

Question 71

BST: scrivere il codice per le funzioni:
- Item BSTmin(BST bst);
- Item BSTmax(BST bst);

Answer 71

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

Question 72

BST: scrivere il codice per le funzioni:
- void BSTvisit(BST bst, int strategy);

Answer 72

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

Question 73

BST: scrivere il codice per le funzioni:
- void BST insert_leafR(BST bst, Item x);

Answer 73

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

Question 74

BST: complessità delle funzioni di INSERT

Answer 74

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)

Question 75

BST: scrivere il codice per le funzioni:
- link rotR(link h);
- link rotL(link h);

Answer 75

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

Question 76

BST: scrivere il codice per le funzioni:
- void BSTinsert_root(BST bst, Item x);

Answer 76

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

Question 77

BST_estesi: in che modo si può estendere la struttura dati?
Scrivere i file BST.h e BST.c

Answer 77

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

Question 78

BST_estesi: come si modificano queste funzioni?
- BST init();

Answer 78

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

Question 79

BST_estesi: come si modificano queste funzioni?
- void BSTinsert_leafR(BST bst, Item x);

Answer 79

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

Question 80

BST_estesi: come si modificano queste funzioni?
- void BSTinsert_root(BST bst, Item x);

Answer 80

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

Question 81

BST_estesi: definizione di successore e predecessore di un nodo.

Answer 81

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.

Question 82

BST_estesi: scrivere il codice per le funzioni:
- Item BSTsucc(BST bst, Key k);

Answer 82

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

Question 83

BST_estesi: scrivere il codice per le funzioni:
- Item BSTpred(BST bst, Key k);

Answer 83

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

Question 84

BST_estesi: scrivere il codice per le funzioni:
- Item BSTselect(BST bst, int r);

Answer 84

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

Question 85

BST_estesi: scrivere il codice per le funzioni:
- link rotR(link h);
- link rotL(link h);

Answer 85

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

Question 86

BST_estesi: scrivere il codice per le funzioni:
- link partR(link h, int r);
Come funziona il partizionamento?

Answer 86

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

Question 87

BST_estesi: scrivere il codice per le funzioni:
- link joinLR(link a, link b, link z);
- void BSTdelete(BST bst, Key k);

Answer 87

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

Question 88

BST_estesi: scrivere il codice per le funzioni:
- void BSTbalance(BST bst);
In cosa consiste?

Answer 88

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

Question 89

TABELLE DI HASH: per cosa le utilizziamo?

Answer 89

per le tabelle di simboli

Question 90

TABELLE DI HASH: in generale qual è la loro complessità?

Answer 90

Possono arrivare ad essere O(1), ma comunque O(1) è in stretta parentela con O(logN) (BST)

Question 91

TABELLE DI HASH: cosa cambia dagli altri metodi di rappresentazione delle tabelle di simboli?

Answer 91

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

Question 92

TABELLE DI HASH: come vengono rappresentate?

Answer 92

ADT con occupazione O(|K|) e tempo medio di accesso O(1). Non essendoci il confronto non c’è ordinamento o select

Question 93

TABELLE DI HASH: cosa fa la chiave di Hash?

Answer 93

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

Question 94

TABELLE DI HASH: cos’è la collisione?

Answer 94

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.

Question 95

TABELLE DI HASH: struttura dati

Answer 95

ADT di I classe ST e quasi ADT, 3, per l’item

Question 96

TABELLE DI HASH: funzione di hash ideale e nella realtà

Answer 96

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)

Question 97

TABELLE DI HASH: funzione di hash con metodo moltiplicativo

Answer 97

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

Question 98

TABELLE DI HASH: funzione di hash con metodo modulare (3 casi)

Answer 98

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 = (baseh + *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 = ab % (M-1)){
h = (a*h + *v)%M;
}
return h;
}

Question 99

TABELLE DI HASH: a cosa serve il numero primo?

Answer 99

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

Question 100

TABELLE DI HASH: definizione di collisione, possibili metodi di gestione

Answer 100

def := h(k_i) = h(k_j) per k_i ≠ k_j
Gestione: linear chaining o open addressing

Question 101

TABELLE DI HASH: linear chaining, caratteristiche

Answer 101

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

Question 102

TABELLE DI HASH: linear chaining, struttura dati in ST.h e ST.c

Answer 102

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

Question 103

TABELLE DI HASH: linear chaining, codice delle funzioni:
- ST STinit(int maxN, float r);
- void STfree(ST st);

Answer 103

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->Msizeof(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);
}
}

Question 104

TABELLE DI HASH: linear chaining, codice delle funzioni:
- int STcount(ST st);
- int STempty(ST st);

Answer 104

int STcount(ST st){
return st->N;
}

int STcount(ST st){
if (STcount(st) == 0) return 1;
return 0;
}

Question 105

TABELLE DI HASH: linear chaining, codice delle funzioni:
- void STinsert(ST st, Item val);

Answer 105

void STinsert(ST st, Item val){
int i;
i = hash(KEYget(&val), st->M);
st->heads[I] = NEW(val, st->heads[I]);
}

Question 106

TABELLE DI HASH: linear chaining, codice delle funzioni:
- Item STsearch(ST st, Key k);
- void STdelete(ST st, Key k);

Answer 106

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

Question 107

TABELLE DI HASH: linear chaining, codice delle funzioni:
- void STdisplay(ST st);

Answer 107

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

Question 108

TABELLE DI HASH: linear chaining, complessità (hp. liste non ordinate) delle funzioni di:
- inserimento
- ricerca caso peggiore e medio
- cancellazione

Answer 108

• 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ò

Question 109

TABELLE DI HASH: open addressing

Answer 109

Ogni cella può contenere un solo elemento -> collisione. Si risolve la collisione mediante Probing: linear probing, quadratic probing, double hashing

Question 110

TABELLE DI HASH: clustering

Answer 110

Il clustering è il raggruppamento di posizioni occupate contigue

Question 111

TABELLE DI HASH: open addressing, strutture dati ST.h e ST.c

Answer 111

ST.h
typedef struct symboltable *ST;

ST.c
struct symboltable { Item *a; int N; int M; };

Question 112

TABELLE DI HASH: open addressing, codice delle funzioni:
- ST STinit(int maxN, float a);

Answer 112

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->Msizeof(Item));
for (i = 0; i < st->M; i++){
st->a[i] = ITEMsetNull();
}
}
return st;
}

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

Answer 113

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

Question 114

TABELLE DI HASH: open addressing, linear probing (caso di delete: vettore status), variazione della struttura dati ST.h e ST.c

Answer 114

ST.h
typedef struct symboltable *ST;

ST.c
struct symboltable { Item *a; int *status; int M; int N; };

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

Answer 115

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

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

Answer 116

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

Question 117

TABELLE DI HASH: open addressing, linear probing, tentativi in media per il search hit e il search miss

Answer 117

search hit: 1/2 *(1+1/(1-alpha))
search miss: 1/2 *(1+1/[(1-alpha)^2])

Question 118

TABELLE DI HASH: open addressing, quadratic probing. Vantaggi e caratteristiche

Answer 118

• evita cluster troppo grandi
• i: contatore dei tentativi
• index = (h’(k) + c_1i + c_2i^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

Question 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

Answer 119

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 + c1i + c2i*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 + c1i + c2i*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+ c1i + c2i*i)%st->M; }

if(ITEMcheckNull(st->a[index])) return;
st->a[index] = ITEMsetNull();
st->N–; i++;
index = (start+ c1i + c2ii)%st->M;
while (full(st, index)){
tmp = st->a[index];
st->a[index] = ITEMsetNull(9;
st->N–; i++;
STinsert(st, tmp);
index = (start+ c1i + c2ii)%st->M;
}
}

Question 120

TABELLE DI HASH: open addressing, double hashing, caratteristiche:

Answer 120

• 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

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

Answer 121

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

Question 122

TABELLE DI HASH: open addressing, double hashing, tentativi in media di probing per la ricerca:
- search hit
- search miss

Answer 122

• search hit: 1/(1-alpha)
• search miss: 1/alpha * ln(1/1-alpha)

Question 123

Tabelle di hash VS BST

Answer 123

BST: prestazioni migliori, ordinamenti possibili
HASH: più facili da realizzare, unica soluzione per chiavi senza relazione d’ordine, più facili per chiavi semplici

Question 124

Cosa fa la HEAPify?

Answer 124

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

Question 125

Quali sono i modi per implementare lo stack?

Answer 125

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.

Question 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

Answer 126

• 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, /

Question 127

BST: scrivere il codice per le funzioni:
- void BST insert_leafI(BST bst, Item x)

Answer 127

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

Question 128

ST: tabelle ad accesso diretto. Codice della
Item STselect(ST st, int r);

Answer 128

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

Question 129

BST estesi: come si modifica la seguente funzione?
void BST insert_leafI(BST bst, Item x)

Answer 129

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

Question 130

IBST: come sono fatti e cos’hanno in più/meno rispetto ai BST?

Answer 130

• 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

Question 131

IBST: quando due intervalli si sovrappongono?

Answer 131

quando low[I] < high[I’] && low[I’] < high[I]

Question 132

IBST: typedef e struct in generale

Answer 132

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

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

Answer 133

appunti

Question 134

IBST: esempio di applicazione

Answer 134

verificare se le piste si intersecano in un circuito elettronico