Che materia stai cercando?

Anteprima

ESTRATTO DOCUMENTO

La GESTIONE DELLA MEMORIA è uno degli argomenti più fighi ma anche ostici del

corso di Fondamenti di Informatica. I tuoi programmi crasheranno di brutto a causa sua!

Prima di tutto che cos'è un OGGETTO in C++? È una regione di memoria di un

determinato tipo dato. Un intero in memoria quindi è un oggetto.

La variabile è un oggetto con nome, per cui int a è un oggetto di tipo intero con il nome a.

Nei linguaggi orientati agli oggetti il termine è anche sinonimo di istanza di una classe:

anche se si usa lo stesso termine NON è la stessa cosa.

Ogni oggetto è caratterizzato da un tempo di vita (o LIFETIME), che è il tempo che

intercorre tra la sua creazione e la sua distruzione. In base a questo criterio è possibile

classificare un oggetto in una di queste categorie:

− TEMPORANEO

− AUTOMATICO

− STATICO

− DINAMICO

− THREAD LOCAL

TEMPORANEI

Sono oggetti creati dal calcolatore con lo scopo di contenere valori intermedi per la

valutazione di un'espressione. Per esempio in un calcolo come x+(y*z) il valore di y*z

deve essere memorizzato da qualche parte per essere poi sommato a x.

Sono oggetti senza nome con i quali l'utente non ha alcun contatto: vengono creati in

modo invisibile all'utente e non esiste alcun metodo di accesso (né per nome né per

indirizzo). Sono solo un dettaglio tecnico. Hanno un breve lifetime, poiché vengono subito

distrutti al completamento dell'espressione. È buona idea fare in modo che si creino il

minor numero di questi oggetti in modo da aumentare l'efficienza del programma.

AUTOMATICI

Sono tutti quegli oggetti che vengono definiti in uno scope e vengono automaticamente

distrutti al termine dello scope stesso. A questa categoria appartengono quindi tutte le

variabili locali alle funzioni o appartenenti a blocchi di if, for, switch... Sono perciò la

maggior parte delle variabili con cui abbiamo a che fare e hanno la caratteristica che

vengono distrutte automaticamente al termine del blocco di istruzioni. Attenzione però a

non confondere il concetto di durata con quello di visibilità: il fatto che un oggetto sia

automatico e locale ad una funzione sono due caratteristiche separate dell'oggetto.

STATICI

Sono oggetti statici tutte le variabili globali o dichiarate come static. Vengono definiti una

volta sola e muoiono solo al termine del programma. NON USARE VARIABILI GLOBALI

PERCHÉ IL PROF TOGLIE PUNTI: le variabili globali influiscono su qualsiasi parte di

codice e non permettono di capire il funzionamento di un blocco osservando solo quello.

Sono delle variabili “latenti” che possono generare bug difficilissimi da trovare, dato che

non possiamo sapere facilmente che valore hanno in un determinato punto. Tanto per

ribadire la differenza tra durata e visibilità: una variabile statica in una funzione esisterà

per tutta l'esecuzione del programma, ma sarà sempre e solo visibile all'interno della sua

funzione. Ricorda anche un'altra cosa importante: le variabili globali e statiche sono

sempre inizializzate a zero di default, quelle locali no.

DINAMICI

Non appartengono a nessuna funzione e non vengono gestite in automatico dal sistema

operativo: sono sotto la nostra piena responsabilità. Le creiamo noi e dobbiamo

distruggerle noi, altrimenti rimarranno lì per tutta l'esecuzione del programma. Non è

importante dove creiamo l'oggetto dinamico all'interno del codice: sopravviverà tra le

funzioni e gli scope, perché esisteranno finché non chiederemo esplicitamente di

distruggerle. Nota che, anche se possiamo manipolarli, sono oggetti senza nome:

abbiamo solo l'indirizzo come strumento di accesso.

THREAD LOCAL

Sono complicati e non ci interessano.

Prima di parlare meglio di questi oggetti dinamici è bene fare un'introduzione su un

argomento fighissimo: la SEGMENTAZIONE DELLA MEMORIA.

Ogni applicazione in esecuzione è detta PROCESSO e il sistema operativo ha il compito

di riservare dello spazio in memoria RAM per permetterne il funzionamento. Qui sono

memorizzate tutte le informazioni del processo in modo ordinato, ovvero la memoria è

segmentata in pezzi ognuno dei quali ha il compito di conservare informazioni di un certo

tipo. In particolare i segmenti in cui è suddivisa la memoria portano i seguenti nomi:

− CODE SEGMENT o TEXT SEGMENT

− DATA SEGMENT

− BSS SEGMENT

− HEAP SEGMENT

− STACK SEGMENT

CODE SEGMENT

Contiene le istruzioni in linguaggio macchina dell'applicazione da eseguire, in pratica ciò

che vediamo quando disassembliamo un programma con il debugger. È un segmento a

sola lettura e di dimensioni fisse.

DATA e BSS SEGMENT

Contengono gli oggetti statici (cioè le variabili globali o dichiarate come static). La

differenza tra i due segmenti è che il primo contiene variabili inizializzate e il secondo no

(hanno perciò il valore di default zero).

HEAP SEGMENT

Lo vediamo dopo ;)

STACK SEGMENT

Contiene gli oggetti automatici, cioè tutte le variabili locali alle funzioni e agli scope. È

organizzata come una pila che sale man mano che vengono invocate delle funzioni. La

metafora della pila funziona bene anche perché gli indirizzi nei quali vengono memorizzati

i dati proseguono da valori alti verso valori più bassi, come una pila che sale verso l'alto.

Ogni volta che viene invocata una funzione si genera un nuovo FRAME che contiene i dati

relativi a quella funzione: i parametri in ingresso, le variabili locali e le informazioni

necessarie per ritornare alla funzione chiamante (in particolare nello stack si inseriscono in

ordine 1) parametri della funzione 2) indirizzo di ritorno 3) SFP 4) variabili locali). Al

termine della funzione il frame viene rimosso dallo stack, ne consegue che le variabili

locali vengono automaticamente distrutte. Naturalmente lo stack non ha memoria illimitata,

per cui una ricorsione infinita si risolve in uno STACK OVERFLOW.

HEAP SEGMENT

Ora possiamo vederlo: è il segmento di memoria che memorizza gli oggetti dinamici. Se lo

stack è una pila bella ordinata, lo heap è un cestino dove ci butti quello che ti serve. Tutto

infatti viene inserito lì in modo casuale e per questo è compito tuo eliminare le variabili che

non ti servono più dopo che le hai utilizzate. Se lasciamo lì dei dati inutilizzati causiamo un

MEMORY LEAK, cioè uno spreco di risorse di memoria, che può portare ad un crash del

programma per mancanza di risorse di sistema. Anche se il posizionamento delle variabili

nell'heap è casuale, il sistema operativo generalmente tenta di inserire gli oggetti

ordinatamente partendo da indirizzi più bassi verso quelli più alti.

Per vedere nella pratica come allocare e deallocare spazio nell'heap, vai nel documento

dedicato alla programmazione pura.

Il nome della lezione si spiega da solo, quindi è inutile che sto mezz'ora a introdurre

l'argomento: il problema è cercare un elemento in un array e ottenere un array ordinato.

Prima di trattare l'argomento è bene fornire alcuni concetti base sulla COMPLESSITÀ.

Il costo di risorse di un algoritmo computazionale si misura prendendo in considerazione il

numero di operazioni che esegue e la quantità di memoria che richiede. Non considera

il tempo di esecuzione e il numero di istruzioni svolte dalla CPU (questi dettagli sono

dipendenti dalla singola unità hardware e non dall'algoritmo).

Si usa un modello di COSTO (ce ne sono vari): uno di questi è considerare solamente la

quantità di operatori coinvolti ed assegnare 1 unità di tempo ciascuno (escludendo

dereferenziazione, accesso ad indici, allocazione di memoria, chiamate a funzioni). In

realtà alcune operazioni sono meno costose di altre (somma vs prodotto), le chiamate a

funzioni richiedono operazioni sullo stack, la dereferenziazione richiede il calcolo di

indirizzi ecc... ma è un'idea generale :P

Nella valutazione della complessità è importante anche la DIMENSIONALITÀ, cioè la

quantità dei dati in ingresso. Nel caso di algoritmi di ricerca e ordinamento, la

dimensionalità coincide con il numero di elementi contenuti nell'array e questo valore lo

indicheremo con n.

Nel nostro MODELLO di complessità prendiamo in considerazione il tempo di esecuzione

e la dimensionalità dei dati. Tra tutti gli scenari legati ai valori dei dati in ingresso, si

considera quello caratterizzato dal caso peggiore. Chiameremo T(n) il tempo di

esecuzione dell'algoritmo in funzione della dimensionalità dei dati in ingresso e useremo la

notazione O per indicare la complessità dell'algoritmo. Non diamo la definizione di

complessità perché ci penserà il Bonzo, ma alcuni valori di complessità da sapere sono:

O(1) Costante

O(logn) Logaritmica

O(n) Lineare

O(nlogn) n logaritmo di n

2

O(n ) Quadratica

3

O(n ) Cubica

Per intenderci, a ognuno di questi gradi di complessità corrisponde un certo numero di

operazioni massime (nel nostro caso i logaritmi sono in base 2). 2 3

n O(1) O(logn) O(n) O(nlogn) O(n ) O(n )

1 1 1 1 1 1 1

2 1 1 2 2 4 8

4 1 2 4 8 16 64

8 1 3 8 24 64 512

16 1 4 16 64 256 4.096

9

1.024 1 10 1.024 10.240 1.048.576 10

12 16

1.048.576 1 20 1.048.576 20.971.520 10 10

La complessità O(1) si presenta in algoritmi a tempo costante, cioè totalmente

indipendenti dalla quantità dei dati in ingresso. Nel caso di O(n) rientrano gli algoritmi a

tempo lineare, la cui durata è direttamente proporzionale alla quantità dei dati in entrata.

x

Tutti i gradi di tipo O(n ) si ottengono per mezzo di cicli annidati.

RICERCA SEQUENZIALE

È l'algoritmo di ricerca più semplice e intuitivo in assoluto: scorri tutto l'array dall'inizio alla

fine finché non trovi il valore cercato.

Implementazione nel main

int numeri[5] = {19, 5, 3, 15, 9};

int elem;

cout << "Inserisci il valore da cercare: ";

cin >> elem;

int i;

for (i = 0; i < 5; ++i) {

if (numeri[i] == elem) {

cout << "Elemento trovato alla posizione " << i << endl;

break;

}

}

if (i == 5)

cout << "Elemento non trovato" << endl;

Implementazione a funzione

int ricerca_sequenziale(int array[], int dim, int elem) {

bool trovato = false;

int i = 0;

while (i < dim && !trovato) {

if (array[i] == elem) {

trovato = true;

return i;

}

else

++i;

}

return -1;

}

int main() {

int numeri[5] = {19, 5, 3, 15, 9};

int x;

cout << "Inserisci il valore da cercare: ";

cin >> x;

int i = ricerca_sequenziale(numeri, 5, x);

if (i+1)

cout << "Elemento trovato alla posizione " << i << endl;

else

cout << "Elemento non trovato" << endl;

return 0;

}

È un metodo molto lento, infatti:

Caso peggiore = L'elemento cercato è l'ultimo, O(n)

Caso medio = L'elemento cercato è nel mezzo dell'array, O(n/2)

Caso ottimo = L'elemento cercato è il primo, O(1)

È utilizzato quando la struttura dati:

− Non è ordinata

− È di piccole dimensioni

− Permette l'accesso casuale

È l'unico metodo utilizzabile in presenza di strutture dati non ordinate.

RICERCA BINARIA o DICOTOMICA

È il metodo più utilizzato in presenza di strutture dati ordinate. Non si cerca partendo dal

primo elemento, ma da quello centrale e lo si confronta con l'elemento da cercare: se è più

grande la ricerca continua nella seconda metà della struttura, altrimenti nella prima metà,

e si continua ricorsivamente a cercare in porzioni sempre più piccole finché non si arriva

all'elemento cercato. Ricorda molto il modo con cui cerchiamo una parola in un dizionario.

Implementazione iterativa

int ricerca_binaria(int array[], int dim, int elem) {

int low = 0, high = dim, mid;

bool trovato = false;

while (low <= high && !trovato) {

mid = (low + high) / 2;

if (array[mid] == elem) {

trovato = true;

return mid;

}

else if (elem > array[mid])

low = mid+1;

else if (elem < array[mid])

high = mid-1;

}

return -1;

}

int main() {

int numeri[13] = {1, 4, 8, 12, 18, 26, 37, 42, 58, 78, 94, 101, 105};

int x;

cout << "Inserisci il valore da cercare: ";

cin >> x;

int i = ricerca_binaria(numeri, 13, x);

if (i+1)

cout << "Elemento trovato alla posizione " << i << endl;

else

cout << "Elemento non trovato" << endl;

return 0;

}

Implementazione ricorsiva

int ricerca_binaria(int array[], int elem, int low, int high) {

int mid = (high + low) / 2;

if (low > high)

return -1;

else if (array[mid] == elem)

return mid;

else if (elem < array[mid])

return ricerca_binaria(array, elem, low, mid-1);

else if (elem > array[mid])

return ricerca_binaria(array, elem, mid+1, high);

}

int main() {

int numeri[13] = {1, 4, 8, 12, 18, 26, 37, 42, 58, 78, 94, 101, 105};

int x;

cout << "Inserisci il valore da cercare: ";

cin >> x;

int i = ricerca_binaria(numeri, x, 0, 13);

if (i+1)

cout << "Elemento trovato alla posizione " << i << endl;

else

cout << "Elemento non trovato" << endl;

return 0;

}

Al contrario della ricerca sequenziale, è un algoritmo molto efficiente, infatti il caso

peggiore e medio è O(logn), cioè non più di 30 confronti in una struttura di 1 miliardo di

elementi.

È utilizzato quando la struttura dati:

− È ordinata

− È di medie-grandi dimensioni

− Permette l'accesso casuale

− È soggetta a poche modifiche

Appunto: deve essere una struttura ordinata. Come possiamo allora, di fronte ad un array

con i valori inseriti a muzzo, ottenere un nuovo array con i valori ordinati in ordine

crescente o decrescente? Anche qui abbiamo a disposizione vari algoritmi, ognuno con

prestazioni differenti riguardo la memoria, la velocità ecc... tra i quali:

− SELECTION SORT

− INSERTION SORT

− BUBBLE SORT

− SHELL SORT

− QUICK SORT

− MERGE SORT

SELECTION SORT

È uno degli algoritmi più semplici. Divide la struttura in due parti: la prima già ordinata e la

seconda da ordinare. Ad ogni iterazione scorre la sequenza da ordinare e mette l'elemento

più piccolo trovato in fondo alla sequenza ordinata.

void selection_sort(int array[], int dim) {

int temp;

for (int i = 0; i < dim-1; ++i)

for (int j = i; j < dim; ++j) {

if (array[j] < array[i]) {

temp = array[i];

array[i] = array[j];

array[j] = temp;

}

}

}

int main() {

int array[6] = {32, 44, -15, 66, 44, 119};

selection_sort(array, 6);

for (int i = 0; i < 6; ++i)

cout << array[i] << " ";

cout << endl;

return 0;

}

Caratteristiche:

− 2

Sempre O(n ).

− É un algoritmo cieco: non sfrutta sequenze già parzialmente ordinate.

− Ogni elemento viene spostato una volta sola: è efficiente in strutture dati dove ogni

elemento occupa molto spazio in memoria, ovvero dove lo spostamento è più

costoso del confronto.

INSERTION SORT

È l'algoritmo più vicino al modo di pensare umano: scorre l'array e man mano che trova un

elemento fuori posto lo mette nella posizione corretta. In pratica l'array è diviso in una

parte ordinata e una parte da ordinare: ad ogni iterazione prende il primo elemento della

parte non ordinata e lo mette al posto giusto della parte ordinata.

void insertion_sort(int array[], int dim) {

for (int i = 1; i < dim-1; ++i) {

int j = i-1;

int current = array[i];

while (j >= 0 && array[j] > current) {

array[j+1] = array[j];

--j;

}

array[j+1] = current;

}

}

int main() {

int array[6] = {32, 44, -15, 66, 44, 119};

insertion_sort(array, 6);

for (int i = 0; i < 6; ++i)

cout << array[i] << " ";

cout << endl;

return 0;

}

Caratteristiche:

− 2

Il caso peggiore e medio è O(n ), ma in caso di array già ordinati è O(n).

− Non è di certo tra i più efficienti, ma nella pratica è migliore del selection sort.

− È veloce in presenza di sequenze già parzialmente ordinate.

BUBBLE SORT

È il metodo delle bolle! Fa “cadere” gli elementi più pesanti nel fondo dell'array facendo

confronti con coppie di valori ad ogni iterazione.

void bubble_sort(int array[], int dim) {

int temp;

for (int j = dim-1; j >= 1; --j)

for (int i = 0; i <= j-1; ++i)

if (array[i] > array[i+1]) {

temp = array[i];

array[i] = array[i+1];

array[i+1] = temp;

}

}

int main() {

int array[6] = {32, 44, -15, 66, 44, 119};

bubble_sort(array, 6);

for (int i = 0; i < 6; ++i)

cout << array[i] << " ";

cout << endl;

return 0;

}

Caratteristiche:

− Il caso peggiore è un array ordinato al contrario e anche nel caso medio è di

2

complessità O(n ), in presenza di array già ordinati O(n).

− Anche questo non è tra gli algoritmi più efficienti, però è intuitivo e facile da

implementare. È veloce in strutture già parzialmente ordinate.

SHELL SORT

È uno degli algoritmi più datati ed è un'estensione dell'insertion sort, sfruttando il fatto che

quest'ultimo è efficiente in presenza di strutture parzialmente ordinate ed ha il vantaggio di

spostare gli elementi una volta sola. È un algoritmo facile da capire e implementare, ma è

difficile analizzarne la complessità.

Concettualmente l'array viene trasportato in una matrice bidimensionale di h colonne e

ordina gli elementi di ogni colonna tramite insertion sort. Ripete l'operazione con matrici di

minori colonne fino ad arrivare al caso base di una matrice formata da una sola colonna.

Da questo punto in poi l'algoritmo si comporta come l'insertion sort. Nella pratica non si fa

una copia dell'intera struttura, ma si opera su un'opportuna indicizzazione. Il valore h è

detto gap sequence e il problema maggiore di questo algoritmo è proprio scegliere questo

valore: si era proposto inizialmente di usare n/2, ma questo non rende l'algoritmo più

2

efficiente, dato che mantiene la complessità a O(n ). L'idea migliore è quella di usare un

k

numero appartenente alla sequenza di Hibbard, cioè l'insieme dei numeri 2 - 1 = (1, 3, 7,

3/2

15, 31, 63...), i quali portano la complessità dell'algoritmo a O(n ).

void shell_sort(int array[], int dim) {

static const int gaps[] = {1, 3, 7, 15, 31, 63, 127};

for (int size_index = sizeof(gaps)/sizeof(gaps[0])-1; size_index >= 0; --size_index)

// (32*7)/32 – 1 = 6

shell_sort_phase(array, dim, gaps[size_index]);

}

void shell_sort_phase(int array[], int dim, int gap) {

for (int i = gap; i < dim; ++i) {

int value = array[i];

int j = i - gap;

while (j >= 0 && array[j] > value) {

array[j+gap] = array[j];

j -= gap;

}

array[j+gap] = value;

}

}

int main() {

int array[6] = {32, 44, -15, 66, 44, 119};

shell_sort(array, 6);

for (int i = 0; i < 6; ++i)

cout << array[i] << " ";

cout << endl;

return 0;

}

Caratteristiche:

− La complessità non è prevedibile e dipende dalla gap sequence scelta. Il miglior

4/3

caso individuato è stato O(n ).

− La scelta della gap sequence permette un miglioramento della complessità rispetto

all'insertion sort.

QUICK SORT

Usa la strategia divide et impera (o oszd meg és uralkodj come dicono i ballerini ungheresi

del video): ordina una sequenza più piccola per poterne ordinare una più grande. Si

partiziona l'array in due sezioni S e S tali che S [i] <= S [j] per ogni coppia {i, j}. In

1 2 1 2

questo modo non c'è alcun bisogno di ricomporre gli array, perché saranno già ordinati. Il

partizionamento avviene scegliendo un perno (che nel nostro esempio sarà il valore

intermedio) e si fa in modo che ogni elemento minore del perno stia alla sua sinistra ed

ogni elemento maggiore del perno stia alla sua destra. Si ripete ricorsivamente l'algoritmo

con tutte le sottosequenze e al termine di ogni partizionamento il perno sarà nella sua

posizione definitiva.

void quick_sort(int array[], int left, int right) {

int i = left, j = right;

int temp;

int pivot = array[(left+right)/2];

while (i <= j) {

while (array[i] < pivot)

++i;

while (array[j] > pivot)

--j;

if (i <= j) {

temp = array[i];

array[i] = array[j];

array[j] = temp;

++i;

--j;

}

}

if (left < j)

quick_sort(array, left, j);

if (i < right)

quick_sort(array, i, right);

}

int main() {

int array[6] = {32, 44, -15, 66, 44, 119};

quick_sort(array, 0, 6);

for (int i = 0; i < 6; ++i)

cout << array[i] << " ";

cout << endl;

return 0;

}

Caratteristiche:

− È un algoritmo molto veloce, ottimo per gestire grosse quantità di dati.

− Nel caso peggiore l'array è fortemente sbilanciato e ciò porta la complessità a

2

O(n ). Mediamente e nel caso ottimo è O(nlogn).

− Il problema centrale sta nella scelta del perno: la scelta sbagliata può rendere molto

inefficiente l'algoritmo, persino al livello dell'insertion sort. Per questo generalmente

viene scelto un elemento casuale oppure la mediana di tre elementi scelti

casualmente.

MERGE SORT

Anche questo algoritmo segue la strategia divide et impera: se la sequenza ha lunghezza

1 è già ordinata, altrimenti viene spezzata in due metà e queste due metà vengono

ordinate applicando ricorsivamente l'algoritmo. Al termine le sottosequenze vengono fuse

inserendo di volta in volta il valore minimo nelle due sequenze e lo si riporta nella

sequenza in uscita, che sarà ordinata. È stato ideato da Von Neumann.

Caratteristiche:

− È un algoritmo molto veloce, non prevede caso peggiore e offre sempre una

complessità O(nlogn).

− Il caso migliore è che la sequenza sia già ordinata, O(n).

Le liste puntate sono una struttura dati lineare che sfrutta l'allocazione dinamica della

memoria ed hanno vantaggi e svantaggi complementari a quelli degli array:

- Gli array hanno il vantaggio di garantire la contiguità degli elementi, permettendo così

l'accesso a indici. Sono anche facili da dichiarare e gestire. Tuttavia gli array hanno

dimensioni fisse e un inserimento in testa è costoso, perché bisogna spostare in avanti di

una cella tutti gli elementi.

- Le liste puntate al contrario hanno lunghezza variabile, permettono di aggiungere un

elemento quando è necessario e l'inserimento in testa è molto veloce. Tuttavia sono più

difficili da gestire e non permettono l'accesso ad indici, perché gli elementi delle liste sono

sparsi in memoria, rendendo necessario scorrere tutta la lista per raggiungere l'elemento

desiderato.

Gli elementi della lista sono detti NODI. Ogni nodo contiene i dati e un puntatore al

prossimo elemento. Il primo nodo della lista è detto TESTA, l'ultimo è detto CODA. Il

puntatore in coda è sempre nullo per indicare la fine della lista. Per entrare nella lista noi

abbiamo solo il puntatore alla testa che conserviamo nello stack: occhio quindi a non

perderlo, altrimenti perdi tutta la lista con tanto di memory leak!

Siccome i nodi devono contenere dati di tipi diversi, essi sono rappresentati da una struct.

L'interfaccia di un nodo quindi ha questa struttura:

struct ListNode {

int data;

ListNode *next;

}

Vediamo tutte le operazioni che si possono compiere su una lista.

DICHIARAZIONE DELL'INTERFACCIA

struct Tipa {

string nome;

string cognome;

int eta;

Tipa *next;

};

Esempio concreto della formula generale presentata sopra.

CALCOLO DELLA LUNGHEZZA

int list_lenght(Tipa *head) {

Tipa *walker = head;

int lenght = 0;

while (walker != nullptr) {

++lenght;

walker = walker->next;

}

return lenght;

}

Per scorrere la lista si crea un puntatore “camminatore” inizializzato con la testa della lista.

Si itera finché non si arriva all'elemento interessato o al termine della lista.

INSERIMENTO IN TESTA

void insert_first_node(Tipa *&head, string nome, string cognome, int eta) {

Tipa *new_node = new Tipa;

new_node->next = head;

head = new_node;

head->nome = nome;

head->cognome = cognome;

head->eta = eta;

}

A differenza degli array, l'inserimento in testa è veloce ed efficiente. Bisogna ricordarsi di

passare la testa per riferimento perché deve essere aggiornata. L'inserimento in testa ha

comunque lo svantaggio che gli elementi si presentano in ordine opposto rispetto a quello

con cui sono stati inseriti.

INSERIMENTO IN CODA

void insert_last_node(Tipa *head, Tipa *&tail, string nome, string cognome, int eta) {

Tipa *new_node = new Tipa;

new_node->nome = nome;

new_node->cognome = cognome;

new_node->eta = eta;

new_node->next = nullptr;

Tipa *walker = head;

while (walker->next != nullptr)

walker = walker->next;

walker->next = new_node;

tail = new_node;

}

In presenza del solo puntatore di testa, l'inserimento in coda è costoso perché richiede di

scorrere l'intera lista.

INSERIMENTO IN CODA INTELLIGENTE

void insert_last_node_tail(Tipa *&tail, string nome, string cognome, int eta) {

Tipa *new_node = new Tipa;

new_node->nome = nome;

new_node->cognome = cognome;

new_node->eta = eta;

new_node->next = nullptr;

tail->next = new_node;

tail = new_node;

}

L'inserimento in coda può essere reso efficiente come quello in testa se si tiene traccia

anche di un puntatore alla coda della lista. In questo caso l'inserimento è immediato.

INSERIMENTO IN MEZZO

void insert_middle_node(Tipa *head, int position, string nome, string cognome, int eta) {

Tipa *new_node = new Tipa;

new_node->nome = nome;

new_node->cognome = cognome;

new_node->eta = eta;

new_node->next = nullptr;

Tipa *walker = head;

for (int i = 0; i < position - 1; ++i) {

walker = walker->next;

if (walker == nullptr) {

cout << "Errore: la posizione indicata non esiste." << endl;

return;

}

}

new_node->next = walker->next;

walker->next = new_node;

}

Per inserire un elemento in mezzo bisogna spostarsi fino all'elemento precedente alla

posizione in cui vogliamo inserire l'elemento. Come negli array, la posizione è 0-based.

STAMPA DELLA LISTA

void print_list(Tipa *head) {

Tipa *walker = head;

while (walker != nullptr) {

cout << walker->nome << ' ' << walker->cognome << ", " << walker->eta << endl;

walker = walker->next;

}

}

ELIMINAZIONE DI UN NODO

void delete_element(Tipa *&head, string nome) {

Tipa *walker = head;

Tipa *previous = nullptr;

while (walker != nullptr) {

if (walker->nome == nome) {

if (previous == nullptr)

head = walker->next;

else

previous->next = walker->next;

delete walker;

return;

}

previous = walker;

walker = walker->next;

}

}

Per eliminare un nodo da una lista bisogna tenere due puntatori: uno al nodo corrente ed

uno al nodo precedente. Il primo punterà al nodo da cancellare, mentre secondo punterà

al nodo che dovrà essere agganciato al resto della lista.

ELIMINAZIONE DELLA LISTA

void delete_list(Tipa *&head) {

Tipa *walker = head;

while (head != nullptr) {

walker = head->next;

delete head;

head = walker;

}

}

int main() {

Tipa *head = new Tipa{"Roobi", "Roobi", 19, nullptr};

Tipa *tail = head;

cout << list_lenght(head) << endl;

insert_first_node(head, "Nelly", "Furtado", 36);

cout << list_lenght(head) << endl;

insert_last_node(head, tail, "Zsofi", "Zimonyi", 43);

cout << list_lenght(head) << endl;

insert_last_node_tail(tail, "Lara", "Croft", 46);

cout << list_lenght(head) << endl;

int position = 3; // 0-based

insert_middle_node(head, position, "Jessica", "Aresi", 19);

cout << list_lenght(head) << endl;

cout << endl;

print_list(head);

cout << endl;

delete_element(head, "Jessica");

print_list(head);

delete_list(head);

if (head == nullptr) {

cout << "\nLa lista ora e' vuota." << endl;

}

return 0;

}

Esistono anche le LISTE PUNTATE DOPPIE, ovvero con nodi che memorizzano due

puntatori: uno all'elemento successivo ed uno all'elemento precedente. In questo modo le

liste di questo tipo sono percorribili in entrambe le direzioni, ma aumentano la difficoltà di

gestione.

Ma ora passiamo a qualcosa di ancora più complicato: gli ALBERI.

Gli alberi sono un sottogruppo dei GRAFI: un grafo è un insieme di elementi (NODI)

connessi da lati (ARCHI). Un grafo è definito come G(V, E) dove V sono i nodi ed E sono

gli archi, tali che ogni arco è una coppia di elementi in V.

Un grafo può essere

− ORIENTATO: se ogni arco è percorribile in una sola direzione (da A a B, ma non

viceversa)

− NON ORIENTATO: se ogni arco è percorribile in entrambe le direzioni

Un esempio con i social network può essere Facebook vs Twitter: Facebook è non

orientato, perché se A è amico di B allora anche B è amico di A, mentre Twitter è orientato,

perché se A è follower di B non vale per forza il contrario.

Un CLIQUE è un grafo in cui tutti i nodi sono connessi tra di loro.

L'ALBERO è un grafo non orientato nel quale due vertici sono connessi da uno e un solo

cammino. I nodi sono gli elementi mentre gli archi sono i collegamenti gerarchici.

L'albero è ACICLICO: non esistono strade alternative per andare dal punto A al punto B.

Viene utilizzato per:

− Rappresentare strutture gerarchiche

− Ricercare rapidamente oggetti

− Rappresentare flussi di decisione

− Rappresentare ordinamenti di oggetti

L'albero è caratterizzato da nodi RADICE, RAMI e FOGLIE. È detto:

− Radice il nodo che non ha archi entranti: la radice è unica e non esiste albero

senza radice.

− Foglia ogni nodo che non presenta archi uscenti: ogni albero ha almeno una foglia.

− Ramo ogni nodo che stabilisce livelli gerarchici.

Un nodo può essere PADRE se ha un arco uscente, FIGLIO se ha un arco entrante.

Ogni nodo può essere sia padre che figlio, e in questo caso è detto nodo INTERNO.

La radice non ha padre. Le foglie non hanno figli.

Un albero è BILANCIATO se presenta tutte le foglie sullo stesso livello, altrimenti è NON

BILANCIATO.

L'ALTEZZA di un nodo è il percorso più lungo che c'è tra il nodo e una foglia.

La PROFONDITÀ di un nodo è la lunghezza del percorso dal nodo alla radice.

Definiamo SOTTOALBERO di T un albero che consiste in un nodo n appartenente a T e

tutti i suoi discendenti in T.

Un albero è BINARIO se ogni nodo ammette al massimo due figli. Se non vi sono limiti di

figli l'albero è chiamato N-ARIO.

Un albero binario è COMPLETO se ogni livello fino al penultimo è completamente riempito

e se i nodi stanno tutti il più alla sinistra possibile. L'ultimo livello può contenere un numero

inferiore al massimo consentito, a patto che i nodi stiano tutti sulla sinistra. Altrimenti

l'albero è definito NON COMPLETO.

Se i nodi di una lista puntata contengono un puntatore all'elemento successivo, il nodo di

un albero binario contiene due puntatori: uno al sottoalbero sinistro ed uno al sottoalbero

destro. L'interfaccia del nodo di un albero quindi ha la seguente struttura:

struct TreeNode {

int data;

TreeNode *left;

TreeNode *right;

}

Tutte le operazioni che si possono fare con gli alberi richiedono la ricorsione. Quindi se odi

la ricorsione odierai anche gli alberi, c'è implicazione tra i due fatti.

CONTARE I NODI

int count_nodes(TreeNode *current_node) {

if (current_node == nullptr)

return 0;

else

return 1 + count_nodes(current_node->left)

+ count_nodes(current_node->right);

}

Il numero di nodi di un albero è il nodo corrente più la lunghezza del sottoalbero sinistro

più la lunghezza del sottoalbero destro.

CALCOLO DELL'ALTEZZA

int tree_height(TreeNode *current_node) {

if (current_node == nullptr)

return 0;

else

return 1 + max(tree_height(current_node->left,

tree_height(current_node->right)));

}

L'altezza di un albero è rappresentata dal nodo corrente più l'altezza massima tra il

sottoalbero sinistro e il sottoalbero destro.

RICERCA DI UN ELEMENTO (albero non ordinato)

int find_node(TreeNode *current_node, int element) {

if (current_node == nullptr || current_node->data == element)

return current_node;

else {

TreeNode *left_search = find_node(current_node->left, element);

TreeNode *right_search = find_node(current_node->right, element);

if (left_search != nullptr)

return left_search;

else

return right_search;

}

}

Se il nodo corrente non esiste oppure è l'elemento cercato, ritornane il puntatore.

Altrimenti cerca a sinistra. Se non c'è a sinistra, cerca a destra.

STAMPA DI UN ALBERO

Troppo complicato, arrangiati.

CANCELLARE UN ALBERO

void delete_tree(TreeNode *current_node) {

if (current_node == nullptr)

return;

else

delete_tree(current_node->left);

delete_tree(current_node->right);

delete current_node;

}

Se il nodo corrente esiste, termina. Altrimenti cancella il sottoalbero di sinistra, cancella il

sottoalbero di destra e poi il puntatore corrente.

Le differenze sostanziali tra grafi e alberi sono:

− L'albero ha una sola radice, il grafo ne ha tante.

− Ogni nodo di un albero ha un solo arco entrante, nel grafo no.

Finora abbiamo sempre realizzato programmi usando l'approccio FUNZIONALE, ovvero i

programmi si sono basati sulla scomposizione del problema in tanti sottoproblemi, ognuno

dei quali è gestito da una funzione. Questo sistema è potente ma ha una limitazione

importante: funziona solo con programmi sequenziali, che devono svolgere sempre le

stesse operazioni seguendo un ordine ben preciso. Questo approccio quindi diventa

debole quando si ha a che fare con programmi interattivi, per esempio quello che sto

usando ora per scrivere questa lezione: non c'è un ordine sequenziale delle cose da fare,

ad ogni esecuzione il comportamento dell'applicazione sarà diverso. È qui che entra in

gioco la programmazione AD OGGETTI.

Per capire la differenza tra i due paradigmi dobbiamo pensare che gli elementi

fondamentali dei programmi sono i DATI e le FUNZIONI. La programmazione funzionale è

utile quando le funzioni (cioè le operazioni da compiere) sono sempre le stesse, mentre ad

ogni esecuzione ciò che cambiano sono i dati da elaborare. La programmazione ad oggetti

invece funziona in modo opposto: al centro ci sono i dati (cioè gli oggetti), che rimangono

stabili, mentre ciò che cambia è il modo con cui utilizziamo questi dati per mezzo delle

funzioni.

Rivediamo meglio la definizione di TIPO nella programmazione funzionale:

Esprime la rappresentazione in memoria di un dato e le operazioni predefinite che

– si possono effettuare su quel dato.

Le operazioni definite dall'utente sono specificate in funzioni separate, che

– comunque non vanno a toccare internamente il funzionamento predefinito di un

tipo.

Non è possibile esprimere relazioni tra tipi simili (int e short saranno sempre

– considerati due tipi completamente scorrelati, anche se intuitivamente non lo sono).

Non è possibile esprimere vincoli complessi.

Nella programmazione ad oggetti invece noi definiamo tutto di un tipo: descriviamo le

proprietà dei dati, le operazioni che si possono effettuare, i vincoli che vogliamo e

possiamo anche collegare tra loro tipi diversi. Tutto questo senza la necessità di sapere

come funziona internamente il tipo stesso (noi finora abbiamo usato senza problemi string

e vector senza sapere minimamente come funzionano internamente, la stessa cosa

possiamo farla anche noi).

In pratica creiamo un TIPO DI DATO ASTRATTO, in cui ciò che ci interessa è sapere cosa

si può fare con quel tipo, ma non come è strutturato internamente. L'esempio classico è

quello della pila: le operazioni che possiamo fare su una pila sono aggiungere un

elemento in cima (push), eliminare un elemento (pop), sapere qual è l'elemento in cima

(top), sapere se la pila è vuota (is_empty). I vincoli sono che non è possibile prendere un

elemento in mezzo e non si possono fare pop e top su una pila vuota. Con un tipo

personalizzato possiamo rendere possibili tutte queste caratteristiche in un tipo a sé

stante.

COS'È UN LINGUAGGIO DI PROGRAMMAZIONE ORIENTATO AGLI OGGETTI?

È un linguaggio di programmazione che permette la realizzazione di tipi di dato astratto ed

ha le seguenti proprietà:

OGGETTI

– CLASSI

– EREDITARIETÀ

– POLIMORFISMO E LATE BINDING

– EREDITARIRETÀ MULTIPLA (opz.)

– GESTIONE TRASPARENTE DELLA MEMORIZZAZIONE DEGLI OGGETTI (opz.)

L'OGGETTO è una variabile, e come tutte le variabili ha un tipo, dei valori, una visibilità,

una durata, può essere statica o dinamica, può essere creata, inizializzata, modificata,

passata come parametro... Ma oltre alle variabili tradizionali gli oggetti sono più potenti

perché, oltre alle operazioni che si possono effettuare, definiscono anche le funzioni che

puoi applicarci. Gli oggetti possono essere classificati e avere funzioni diverse in base alla

loro classificazione (funzioni che valgono per qualsiasi classificazione e funzioni

specifiche). Per esempio le persone del Politecnico possono essere tutte sotto la

classificazione di “persona” e suddividersi in “studente”, “ex studente”, “professore”,

“ricercatore”, “impiegato”. Gli oggetti quindi sono molto più vicini al modo di pensare

umano, perché rappresentano il modello di un oggetto reale, nascondendo i dettagli

tecnici.

La CLASSE è il tipo di un oggetto. Il tipo indica le caratteristiche e le operazioni di una

variabile, quindi la classe indica le proprietà e le operazioni che si possono svolgere su un

oggetto. Non sono molto diverse sintatticamente da una struct, ma a differenza loro hanno

la particolarità di poter contenere anche le funzioni.

L'EREDITARIETÀ è la possibilità di far derivare un tipo da un altro e specializzarlo.

Ponendo l'esempio delle persone del Politecnico, “persona” rappresenta un tipo generico

contenente nome, cognome e matricola. Tra le persone del Politecnico ci sono studenti,

professori, ricercatori, impiegati: ognuna di queste figure può essere rappresentata con un

tipo che eredita da “persona”, perché tutte le persone del Politecnico hanno un nome, un

cognome, una matricola. Ogni classe poi può essere singolarmente estesa aggiungendo

le funzioni specifiche per quel tipo di persona. È naturalmente possibile anche ridefinire

funzioni ereditate dalla classe superiore.

Il POLIMORFISMO è il fatto che uno stesso oggetto, se eredita da un altro, può essere

visto secondo più forme, ovvero sia nella forma specializzata che in quella più generica.

Se la forma specializzata ridefinisce una funzione presente anche nella forma generica, si

ha un LATE BINDING, ovvero l'invocazione di quella funzione farà riferimento alla sua

versione più specifica.

La caratteristica dei programmi che fanno uso di oggetti è che hanno un main ridottissimo

e tutta la logica del programma si trova nel modo con cui gli oggetti comunicano tra loro.

Le classi infatti possono contenere altre classi interne oppure un puntatore ad una classe

esterna (in questo modo è possibile creare oggetti condivisi).

La STANDARD TEMPLATE LIBRARY è una collezione di funzionalità che ci semplifica la

vita enormemente, perché ci permette di gestire strutture dati e di usare algoritmi su di

essi già pronti senza doverseli inventare ogni volta. Si basa sulle macrocategorie di

CONTENITORI, ITERATORI e ALGORITMI.

I contenitori STL sono un insieme di strutture dati già implementate che

– funzionano indipendentemente dal tipo di dato che andranno a contenere e si

allungano e accorciano automaticamente secondo le necessità.

Gli iteratori sono un tipo di puntatore che punta ad un oggetto all'interno di un

– contenitore.

Gli algoritmi permettono di effettuare facilmente tutte le operazioni più comuni con i

– contenitori e garantiscono una determinata complessità.

I contenitori messi a disposizione da STL sono:

Vector Array monodimensionale

Vantaggi: automaticamente espandibile, accesso rapido

Svantaggi: poco efficiente negli inserimenti non in coda

List Lista puntata doppia

Vantaggi: veloce ad inserire ed eliminare elementi

Svantaggi: accesso lento

Deque Coda a doppia testa

Un misto tra una coda e una pila (l'inserimento e la rimozione sono

possibili sia in testa che in coda)

Queue Coda Inserimento in coda, rimozione in testa (logica FIFO)

Stack Pila Inserimento e rimozione in coda (logica LIFO)

Set Insieme

Insieme di chiavi

Map Array associativo

Fa uso di una chiave e di un valore ad essa associato

Multiset Set con chiavi non univoche

Multimap Map con chiavi non univoche

I contenitori si dividono in tre categorie.

SEQUENCE CONTAINERS: contenitori sequenziali (vector, list, deque).

– ASSOCIATIVE CONTAINERS: contenitori che fanno uso di una coppia

– chiave/valore (set, map).

CONTAINER ADAPTERS: contenitori simili ai precedenti ma con alcune limitazioni

– per comportarsi in un certo modo (queue, stack).

Siccome i contenitori sono delle classi, ammettono l'uso di metodi su di essi. Tutti i

contenitori possiedono infatti:

Costruttore di default, costruttore per copia, distruttore

– .empty()

– .max_size() e .size()

– = < <= == != >= >

– .swap()

Altre funzioni a disposizione di tutti i contenitori tranne coda e pila sono:

.begin() e .rbegin()


ACQUISTATO

1 volte

PAGINE

47

PESO

1.10 MB

AUTORE

fiorixf2

PUBBLICATO

+1 anno fa


DESCRIZIONE APPUNTO

Appunti completi del (tostissimo) corso di Fondamenti di Informatica tenuto dal prof Piero Fraternali al Politecnico di Milano. Argomenti trattati:
- Algoritmi
- Introduzione al C++
- Tipi
- Istruzioni
- Algebra di Boole
- Aritmetica dei calcolatori
- Matrici
- Ricorsione
- Gestione della memoria
- Algoritmi di ricerca e ordinamento
- Liste puntate e alberi
- Programmazione ad oggetti
- STL


DETTAGLI
Corso di laurea: Corso di laurea in ingegneria informatica (COMO - CREMONA - MILANO)
SSD:
A.A.: 2017-2018

I contenuti di questa pagina costituiscono rielaborazioni personali del Publisher fiorixf2 di informazioni apprese con la frequenza delle lezioni di Fondamenti di Informatica e studio autonomo di eventuali libri di riferimento in preparazione dell'esame finale o della tesi. Non devono intendersi come materiale ufficiale dell'università Politecnico di Milano - Polimi o del prof Fraternali Piero.

Acquista con carta o conto PayPal

Scarica il file tutte le volte che vuoi

Paga con un conto PayPal per usufruire della garanzia Soddisfatto o rimborsato

Recensioni
Ti è piaciuto questo appunto? Valutalo!

Altri appunti di Corso di laurea in ingegneria informatica (como - cremona - milano)

Robotica - Elementi introduttivi
Dispensa
Formulario Elettrotecnica
Appunto
Controllo di posizione e velocità
Dispensa
Cinematica - Elementi
Dispensa