P - Allocazione dinamica e liste

Question 1

Cosa significa allocazione?

Answer 1

Associazione di una parte di memoria

Question 2

Quali tipologie di allocazione esistono?

Answer 2

Implicita, esplicita, dinamica

Question 3

In che momento avviene l’allocazione dinamica?

Answer 3

In fase di esecuzione

Question 4

A che tipo di regole sono soggette le variabili?

Answer 4

A regole di esistenza, memoria, visibilità

Question 5

Che differenze ci sono tra variabili globali e locali in fatto di definizione?

Answer 5

• globali: sono definite fuori dalle funzioni e in generale nell’intestazione del file
• locali: sono definite all’interno delle funzioni

Question 6

Che differenze ci sono tra variabili globali e locali in fatto di visibilità e come avviene il passaggio tra funzioni?

Answer 6

• globali: sono visibili ovunque e non si passano come parametri perché sono accessibili da tutti
• locali: sono visibili solo nella funzione relativa perciò bisogna passarle

Question 7

Che differenze ci sono tra variabili globali e locali in fatto di esistenza?

Answer 7

• globali: sono permanenti
• locali: iniziano e cessano con le funzioni

Question 8

Quali sono i passaggi per arrivare al codice eseguibile?

Answer 8

1. si parte dal codice sorgente
2. il COMPILATORE ne esegue un’analisi e genera il codice oggetto che è un file in linguaggio macchina che ha ancora riferimenti a funzioni di libreria
3. il LINKER risolve questi riferimenti e anche i riferimenti tra i file
4. e si ottiene il codice eseguibile che viene caricato in memoria dal LOADER che è un modulo del sistema operativo

Question 9

Come sono disposte all’incirca le cose in memoria?

Answer 9

partendo dagli indirizzi bassi:
1. codice (istruzioni)
2. variabili globali
3. variabili locali e parametri: deallocate e allocate a ogni chiamata
4. heap: è la memoria dinamica a cui si accede solo tramite puntatore

Question 10

Come si accede all’heap?

Answer 10

Solo tramite puntatore

Question 11

Nel caso di allocazione automatica, come viene gestita la dimensione?

Answer 11

• è nota per le variabili locali e globali
• è calcolabile per vettori e matrici

Question 12

Nel caso di allocazione automatica, che caratteristiche hanno le variabili globali?

Answer 12

Vengono allocate all’inizio del programma e restano in vita fino alla fine.
Ricordano i valori assegnati da funzioni.
L’attributo static limita la loro visibilità solo al file in cui sono definite.

Question 13

Nel caso di allocazione automatica, che caratteristiche hanno le variabili locali?

Answer 13

Vengono allocate con i parametri formali nello Stack frame. Vengono deallocate alla fine di ogni chiamata e in generale non ricordano i valori precedenti a meno che non ci sia l’attributo static con il quale però vengono allocate con le variabili globali.
La visibilità è limitata alle funzioni in cui sono definite.

Question 14

Cosa si può dire dell’istruzione void *malloc(size_t size)? A che libreria appartiene?

Answer 14

• stilib.h
• ritorna un puntatore che contiene l’indirizzo di memoria allocata
• ritorna NULL se non c’è spazio
• il puntatore ritornato è generico, opaco, quindi deve essere assegnato
• size è un intero che indica il numero di Byte da assegnare
• complessità O(1)

Question 15

Dato struct stud e struct stud *s, allocare lo spazio per s.

Answer 15

s = (struct stud )malloc(sizeof(s));
s = (struct stud *)malloc(sizeof(struct stud));

Question 16

Cosa si può dire dell’istruzione void *calloc(size_t n, size_t size);

Answer 16

• corrisponde a una malloc + azzeramento della memoria -> O(n)

Question 17

Cosa si può dire dell’istruzione void free(void *p);?

Answer 17

• si può deallocare solo qualcosa che è stato allocato esplicitamente
• non si può deallocare solo un pezzo di qualcosa

Question 18

Cos’è il memory leak?

Answer 18

Quando ci si dimentica di deallocare aumenta la probabilità che una malloc ritorni NULL

Question 19

Cosa si può dire dell’istruzione void *realloc(void *p, size_t newsize);?

Answer 19

• p è lo spazio da reallocare con la newsize
• la realloc può essere possibile o non, o anche possibile ma altrove e in quel caso avviene una nuova allocazione, la copia del contenuto e la free del vecchio spazio
• ritorna il puntatore aggiornato

Question 20

Come si può allocare una struttura dinamica nel caso in cui la sua dimensione non sia nota fino ad acquisizione conclusa con per esempio un carattere speciale?

Answer 20

1) 2 letture da file
2) realloc
a) ad ogni iterazione -> O(N^2)
b) solo quando è pieno viene raddoppiato -> O(NlogN)

Question 21

Scrivere le funzioni che allocano e deallocano una matrice sia nel caso in cui questa venga passata by pointer che by value:
- void malloc2dP(Item ***mp, int nr, int nc);
- Item **malloc2dR(int nr, int nc);

Answer 21

void malloc2dP(Item **mp, int nr, int nc){
Item **m;
m = (Item **)malloc(nrsizeof(Item ));
for(int i = 0; i < nr; i++){
m[i] = malloc(ncsizeof(Item));
}

*mp = m; }

Item **malloc2dR(int nr, int nc){
Item **m;
m = (Item **)malloc(nr*sizeof(Item ));
for(int i = 0; i < nr; i++){
m[i] = malloc(ncsizeof(Item));
}

return m;

Question 22

Quali sono le caratteristiche di una sequenza lineare?

Answer 22

• insieme finito di elementi
• elementi dello stesso tipo consecutivi
• relazione predecessore e successore
• ogni elemento è associato a un indice
• elementi ordinati in base a posizione o chiave
• accesso diretto in base a posizione o chiave, diretto o sequenziale

Question 23

Quali sono le differenze tra un vettore e una lista concatenata?

Answer 23

• vettore: dati contigui in memoria, accesso diretto O(1), meglio quando è noto o stimabile il numero di elementi
• lista: dati non contigui in memoria, accesso con scorrimento O(n), meglio se non è noto il numero di elementi. possono essere doppie o semplici in base alla presenza del predecessore

Question 24

Quali sono le 5 possibili definizioni dei nodi?

Answer 24

// 1
struct node { Item val; struct node *next; };

// 2
typedef struct node { Item val; struct node *next; } node_t, *link;

// 3
typedef struct node *link;
struct node { Item val; link next; };

// 4
typedef struct node node_t;
struct node { Item val; node_t *next; };

// 5
typedef struct node *link, node_t;
struct node { Item val; link next; };

Question 25

Quali sono le funzioni usali per gestire le chiavi degli Item?

Answer 25

key KEYget(Item d);
int KEYeq(key k1, key k2);
int KEYless(key k1, key k2);
int KEYgreater(key k1, key k2);

Question 26

Come si alloca un nodo definito con la terza modalità?

[
typedef struct node *link;
struct node { Item val; link next; };
]

Answer 26

link x;
x = malloc(sizeof(*x));

Question 27

Come si dichiara un puntatore alla testa di una lista (terza modalità)?

[
typedef struct node *link;
struct node { Item val; link next; };
]

Answer 27

link head == NULL;

Question 28

Come si inserisce dopo x un nodo t definito con la terza modalità?

[
typedef struct node *link;
struct node { Item val; link next; };
]

Answer 28

t->next = x->next;
x->next = t;

Question 29

Come si elimina il nodo t che è dopo x, definito con la terza modalità?

[
typedef struct node *link;
struct node { Item val; link next; };
]

Answer 29

x->next = t->next;

Question 30

Come si fa l’attraversamento di una lista senza necessità di modifica?

[
typedef struct node *link;
struct node { Item val; link next; };
]

Answer 30

link x, head;
for(x = head; x != NULL; x = x->next) {…}

Question 31

Come si fa l’attraversamento di una lista con necessità di modifica?
1) puntatore al predecessore p di x
2) puntatore a nodo
3) ricorsione in avanti
4) ricorsione all’indietro

[
typedef struct node *link;
struct node { Item val; link next; };
]

Answer 31

1) link x, p, head;
for(p = NULL, x = head; x!=NULL; p = x, x = x->next) {…}

2) link head, *xp;
for(xp = &head; xp != NULL; xp = &((xp)->next)) {…}

3)
void listTravRAvanti(link h) {
if (h == NULL) return;
ITEMdisplay(h->val);
listTravRAvanti(h->next);
}

4)
void listTravRAvanti(link h) {
if (h == NULL) return;
listTravRAvanti(h->next);
ITEMdisplay(h->val);
}

Question 32

Scrivere la funzione di creazione di un nodo.

Answer 32

link newNode(Item val, link next){
link x;
x = malloc(sixes(*x));
if (x == NULL) return NULL;
x->val = val;
x->next = next;
return x;
}

Question 33

Funzioni di inserzione in testa per una lista non ordinata e (2 modi) in modo ordinato per una lista ordinata.
- ordinata: link SortListIns(link h, Item val);
- non ordinata: link listInsHead(link h, Item val); e link listInsHeadP(link *hp, Item val);

Answer 33

link listInsHead(link h, Item val) {
link x;
x = newNode(val, h);
return x;
}

// main: listInsHeadP(&head, d);
link listInsHeadP(link *hp, Item val) {
*hp = newNode(val, *hp);
}

link SortListIns(link h, Item val) {
link x, p;
Key k = KEYget(val);
Key kh = KEYget(h->val);
if (h == NULL || KEYgreater(kh, k)) return newNode(val, h);

for(x = h->next, p = h; x!=NULL & KEYgreater(k, KEYget(x->val)); p = x, x = x->next);

p->next = newNode(val, x);
return h;

}

Question 34

Funzione di inserzione in coda:
- link listInsTail(link h, Item val);
- link listInsTailP(link *hp, Item val);
- link listInsTailP(link *hp, Item val); (puntatore al puntatore)
- void listInsTFast(link *hp, link *tp, Item val);

Answer 34

link listInsTail(link h, Item val) {
link x;
if (h == NULL) return newNode(val, NULL);
for(x = h; x->next != NULL; x = x->next);
x->next = newNode(val, NULL);
return h;
}

// listInsTailP(&head, d);
link listInsTailP(link *hp, Item val){
link x = *hp;
if (x == NULL) *hp = newNode(val, NULL);
for( ; x->next != NULL; x = x->next);
x->next = newNode(val, NULL);
}

link listInsTailP(link hp, Item val){
link xp = hp;
while (xp != NULL) xp = &((xp)->next);
*xp = newNode(val, NULL);
}

void listInsTFast(link *hp, link tp, Item val){
if (hp == NULL) *hp = tp = newNode(val, NULL);
else {
(tp)->next = newNode(val, NULL);
tp = (tp)->next;
}
}

Question 35

Funzione di ricerca di una chiave in lista: cosa si ritorna in base a se il dato c’è o non c’è?
- Item listSearch(link h, Key k);
- Item SortListIns(link h, Key k);

Answer 35

Item listSearch(link h, Key k){
link x;
for(x = h; x != NULL; x = x->next){
if(KEYeq(KEY(x->val), k)) return x->val;
}
return ITEMsetvoid();
}

Item SortListIns(link h, Key k){
// uguale
}

Question 36

Funzioni di cancellazione di un nodo dalla lista:
- link listDelHead(link h);
- link SortListDel(link h, Key k);
- link listDelKey(link h, Key k);
- link listDelKeyR(link x, Key k);

Answer 36

link listDelHead(link h){ // non ordinate
link t = h;
if (h == NULL) return NULL;
h = h->next;
free(t);
return h;
}

link SortListDel(link h, Key k){ //ordinate
link x, p;
if (h == NULL) return NULL;

for(x = h, p = NULL; x!= NULL && KEYgeq(k, KEYget(x->val)); p = x, x = x->next){
if (KEYeq(KEYget(x->val), k)){
if (x == h) h = h->next;
else p->next = x->next;
free(x); break;
}
}
return h;
}

link listDelKey(link h, Key k){ // non ordinate
link x, p;
if (h == NULL) return NULL;

for(x = h, p = NULL; x!= NULL; p = x, x = x->next){
if (KEYeq(KEYget(x->val), k)){
if (x == h) h = h->next;
else p->next = x->next;
free(x); break;
}
}
return h;
}

link listDelKeyR(link x, Key k){ // non ordinate
link t;
if (x == NULL) return NULL;
if (KEYeq(KEYget(x->val), k)){
t = x->next;
free(x); return t; }
x->next = listDelKeyR(x->next, k);
return x;
}

Question 37

Funzione di estrazione di un nodo:
- dalla testa: Item listExtrHeadP(link *hp);
- con chiave: link listExtrKeyP(link *hp, Key k);

Answer 37

ci sono da ritornare sia il dato che head quindi usiamo i puntatori

Item listExtrHeadP(link *hp){
link t = *hp;
Item tmp;
if (t == NULL) return ITEMsetvoid();
tmp = t->val;
*hp = t->next;
free(t);
return tmp;
}

link listExtrKeyP(link hp, Key k){
link xp, t;
Item i = ITEMsetvoid();
for(xp = hp; (xp) != NULL; xp = &((xp)->next)){
if (KEYeq(k, KEYget((*xp)->val)) {
t = *xp; xp = (xp)->next; i = t->val; free(t); break;
}
}
return I;
}

Question 38

LISTA CIRCOLARe MANCA

Answer 38

MANCA

Question 39

Funzioni di inversione di lista, versione con due liste link listReverseF(link x);

Answer 39

link listReverseF(link h){
link y, new;
y = h; new = NULL;
Item tmp;
while (y != NULL) {
tmp = listExtrHeadP(&y);
new = listInsHead(new, tmp);
}
return new;
}

Question 40

Funzioni di inversione di lista, versione con inversione di puntatori link listReverseP(link h);

Answer 40

link listReverseP(link h){
link t, y = h, r = NULL;
while (y != NULL){
t = y->next;
y->next = r;
r = y;
y = t;
}
return r;
}

Question 41

Insertion Sort per list, versione con due liste: link listSortF(link h);

Answer 41

link listSortF(link h){
link y = h, r = NULL;
Item tmp;
while (y != NULL){
tmp = listExtrHeadP(&y);
r = sortListIns(r, tmp);
}
return r;
}

Question 42

Insertion Sort per list, versione con inversione di puntatori

Answer 42

for(t = h->next, h->next = NULL; t != NULL; t = u){
u = t->next;
if(h->val > t->val) { t->next = h; h = t; }
else {
for(x = h; x->next != NULL; x = x->next){
if (x->next->val > t->val) break;
t->next = x->next;
x->next = t;
}
}
}