P - Allocazione dinamica e liste Flashcards
Cosa significa allocazione?
Associazione di una parte di memoria
Quali tipologie di allocazione esistono?
Implicita, esplicita, dinamica
In che momento avviene l’allocazione dinamica?
In fase di esecuzione
A che tipo di regole sono soggette le variabili?
A regole di esistenza, memoria, visibilità
Che differenze ci sono tra variabili globali e locali in fatto di definizione?
- globali: sono definite fuori dalle funzioni e in generale nell’intestazione del file
- locali: sono definite all’interno delle funzioni
Che differenze ci sono tra variabili globali e locali in fatto di visibilità e come avviene il passaggio tra funzioni?
- 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
Che differenze ci sono tra variabili globali e locali in fatto di esistenza?
- globali: sono permanenti
- locali: iniziano e cessano con le funzioni
Quali sono i passaggi per arrivare al codice eseguibile?
- si parte dal codice sorgente
- 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
- il LINKER risolve questi riferimenti e anche i riferimenti tra i file
- e si ottiene il codice eseguibile che viene caricato in memoria dal LOADER che è un modulo del sistema operativo
Come sono disposte all’incirca le cose in memoria?
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
Come si accede all’heap?
Solo tramite puntatore
Nel caso di allocazione automatica, come viene gestita la dimensione?
- è nota per le variabili locali e globali
- è calcolabile per vettori e matrici
Nel caso di allocazione automatica, che caratteristiche hanno le variabili globali?
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.
Nel caso di allocazione automatica, che caratteristiche hanno le variabili locali?
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.
Cosa si può dire dell’istruzione void *malloc(size_t size)? A che libreria appartiene?
- 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)
Dato struct stud e struct stud *s, allocare lo spazio per s.
s = (struct stud )malloc(sizeof(s));
s = (struct stud *)malloc(sizeof(struct stud));
Cosa si può dire dell’istruzione void *calloc(size_t n, size_t size);
- corrisponde a una malloc + azzeramento della memoria -> O(n)
Cosa si può dire dell’istruzione void free(void *p);?
- si può deallocare solo qualcosa che è stato allocato esplicitamente
- non si può deallocare solo un pezzo di qualcosa
Cos’è il memory leak?
Quando ci si dimentica di deallocare aumenta la probabilità che una malloc ritorni NULL
Cosa si può dire dell’istruzione void *realloc(void *p, size_t newsize);?
- 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
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?
1) 2 letture da file
2) realloc
a) ad ogni iterazione -> O(N^2)
b) solo quando è pieno viene raddoppiato -> O(NlogN)
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);
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;
Quali sono le caratteristiche di una sequenza lineare?
- 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
Quali sono le differenze tra un vettore e una lista concatenata?
- 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
Quali sono le 5 possibili definizioni dei nodi?
// 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; };
Quali sono le funzioni usali per gestire le chiavi degli Item?
key KEYget(Item d);
int KEYeq(key k1, key k2);
int KEYless(key k1, key k2);
int KEYgreater(key k1, key k2);
Come si alloca un nodo definito con la terza modalità?
[
typedef struct node *link;
struct node { Item val; link next; };
]
link x;
x = malloc(sizeof(*x));
Come si dichiara un puntatore alla testa di una lista (terza modalità)?
[
typedef struct node *link;
struct node { Item val; link next; };
]
link head == NULL;
Come si inserisce dopo x un nodo t definito con la terza modalità?
[
typedef struct node *link;
struct node { Item val; link next; };
]
t->next = x->next;
x->next = t;
Come si elimina il nodo t che è dopo x, definito con la terza modalità?
[
typedef struct node *link;
struct node { Item val; link next; };
]
x->next = t->next;
Come si fa l’attraversamento di una lista senza necessità di modifica?
[
typedef struct node *link;
struct node { Item val; link next; };
]
link x, head;
for(x = head; x != NULL; x = x->next) {…}
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; };
]
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);
}
Scrivere la funzione di creazione di un nodo.
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;
}
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);
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;
}
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);
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;
}
}
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);
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
}
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);
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;
}
Funzione di estrazione di un nodo:
- dalla testa: Item listExtrHeadP(link *hp);
- con chiave: link listExtrKeyP(link *hp, Key k);
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;
}
LISTA CIRCOLARe MANCA
MANCA
Funzioni di inversione di lista, versione con due liste link listReverseF(link x);
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;
}
Funzioni di inversione di lista, versione con inversione di puntatori link listReverseP(link h);
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;
}
Insertion Sort per list, versione con due liste: link listSortF(link h);
link listSortF(link h){
link y = h, r = NULL;
Item tmp;
while (y != NULL){
tmp = listExtrHeadP(&y);
r = sortListIns(r, tmp);
}
return r;
}
Insertion Sort per list, versione con inversione di puntatori
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;
}
}
}
