PDA

Visualizza la versione completa : [C/C++] Liste concatenate e vettori


Lak3d
14-10-2006, 14:54
Stavo guardando le liste concatenate e leggo che non sono niente di diverso da un vettore di struttura visto che, giustamente, il puntatore che punta all'elemento successivo (struttura ricorsiva) è di fatto l'equivalente dell'indice posizionale di un vettore, essendo il nome del vettore un puntatore al suo primo elemento.
La differenza che cita il manuale però sta nel fatto che un vettore è una struttura di dati statica e che quindi le liste concatenate sono utili quando non sono noti a priori gli elementi che dovranno essere contenuti.

Ora mi domando: è il manuale che si dimentica della funzione realloc oppure sono io che credo i vettori delle strutture di dati dinamiche quando invece non lo sono?

Grazie.

Lak3d
15-10-2006, 09:29
nessuno?

MItaly
15-10-2006, 10:40
I vettori "standard" sono strutture a dimensione prefissata, perché vengono allocati sullo stack e le loro dimensioni sono fissate al momento della compilazione. È certamente vero che si può allocare memoria a runtime con malloc e, nel caso in cui non basti, riallocarla con realloc.
Tuttavia quest'ultima soluzione è molto poco efficiente: mentre le liste concatenate allocano memoria man mano che aggiungi elementi, allocando ogni volta dei minimi blocchettini di memoria (contenenti il puntatore all'elemento precedente, il dato e il puntatore all'elemento successivo), quando tu vuoi aggiungere un elemento ad un vettore la realloc alloca nuova memoria per contenere tutto il vettore (incluso il nuovo elemento), ci copia il vettore da dove era prima e dealloca la memoria in cui era memorizzato prima il vettore. Inoltre se vuoi rimuovere un elemento da un array devi shiftare indietro di uno tutti gli elementi che lo seguono e richiamare la realloc dicendole che ti serve meno memoria (con tutte le perdite di tempo che questa funzione porta): un enorme spreco di tempo rispetto al funzionamento della lista concatenata, che si limita ad aggiornare due puntatori e dealloca un singolo blocchetto di memoria.

MItaly
15-10-2006, 10:41
Ah, dimenticavo...
http://en.wikipedia.org/wiki/Linked_list#Linked_lists_vs._arrays

doraemon83
15-10-2006, 12:21
D'altro canto però gli array hanno il vantaggio dell'accesso posizionale che nelle liste non hai, il che ti costringe a scorrerla tutta per fare una ricerca.

Lak3d
15-10-2006, 12:35
grazie mille a tutti! :D

Loading