Array e liste

[Absolut]

Salve ragazzi, sapreste dirmi la differenza tra un array e una lista in modo molto semplificato ed eventualmente facendomi un esempio? Sto leggendo una cosa in cui la questione è questa: Ho una serie di documenti in cui sono contenuti tantissimi termini. E per ogni termine T dovrei memorrizzare i documenti in cui tale termine è presente. Il problema che ci si pone è: usare array o liste?

Esempio: consideriamo tre Termini: A B C

il termine A è contenuto dei documenti 2 4 8 16 32 64 128
il termine B è contenuto dei documenti 1 2 3 5 8 12 21 34
il termine C è contenuto dei documenti 13 16

che succede se il termine C viene aggiunto al documento 14?

Viene detto che le Liste concatenate sono preferibili agli array perchè:

Dynamic space allocation
Insertion of terms into documents easy
Space overhead of pointer

Sapreste spiegarmi questo?

vi rignrazio!!!

[Toni]

un array devi pensarlo come una area di memoria continua suddivisa in parti , tramite l' indice che alla fine segue l ' algebra dei puntatori edindicizza la zona di memoria su cui vuoi scrivere .

alla base di una lista vi una struttura che contiene :

nel caso di lista unidirezionale ( puoi scorrerla in un solo verso):
- un area dati
- un puntatore che punta ad una struttura dello stesso tipo

nella area dati puoi metterci quello che vuoi , altre strutture etc etc

Per accedere agli elementi della lista si utilizza il puntatore

Dal punto di vista di utilizzo della memoria è efficente infatti non richiede che l 'area di memoria deve essere continua

Ovviamente una volta costruiti i metodi per inserire , scorrere , eliminare elementi dalla lista risulta molto comodo .
In c++ esistono molte implementazioni ( classi ) già pronte ognuna con i suoi metodi

[FireEater]

Questo problema si può risolvere in tanti modi, io userei una lista di liste oppure un array di liste (magari ordinato in modo da poter usare la ricerca dicotomica sui termini)

La differenza tra array e liste sta nel metodo di allocazione.
Gli array sono allocati per intero, se dichiari un array di 1000 elementi da 4byte verrà cercato(o creato) uno spazio di memoria contiguo di 4000 byte dove è possibile allocare tutta la struttura per intero.

Dynamic space allocation
Quando viene creata una lista i nodi vengono allocati uno alla volta, quindi occupano la memoria in maniera non contigua, in questo modo è possibile sfruttare meglio la memoria perché non è necessario effettuare swap su disco se la RAM è quasi piena o molto frammentata. Inoltre quando gli elementi di una lista vengono eliminati vengono anche deallocati liberando la memoria che occupavano mentre con gli array questo non è possibile(parlo di array statici).

Insertion of terms into documents easy
L'inserimento ordinato in una lista è una cosa semplicissima, basta creare un nuovo elemento e fare in modo che l'elemento precedente punti a lui ed il suo campo indirizzo punti al successivo.
In questo modo sarebbe semplicissimo inserire il num. 14 nella lista dei documenti in cui è contenuto C (10 righe di codice).

Space overhead of pointer
Questo proprio non lo so,
Mi sembra più uno svantaggio, ma è l'unico modo per avere l'allocazione sparsa. Comunque provo a darti una spiegazione(che è più una supposizione):
Utilizzando le liste "sprechi" un po' di memoria perché devi avere(per ogni elemento)un puntatore all'indirizzo dell'elemento successivo, perché non è adiacente.
Utilizzando array risparmi memoria in quanto viene memorizzato soltanto il puntatore al primo elemento del vettore e la lunghezza del vettore.


Si per risolvere il problema io userei una array di liste.

Ciao Fire

[Absolut]

grazie mille... ora mi è più chiaro il tutto!

[Mario Vanoni]

Robert J. Traister
Mastering C Pointers
Second Edition
(C) 1993
Academic Press
ISBN 0-12-697409-8

Mario Vanoni