Repository 32bit  Forum
Repository 64bit  Wiki

Array e liste

Forum dedicato alla programmazione.

Moderatore: Staff

Regole del forum
1) Citare in modo preciso il linguaggio di programmazione usato.
2) Se possibile portare un esempio del risultato atteso.
3) Leggere attentamente le risposte ricevute.
4) Scrivere i messaggi con il colore di default, evitare altri colori.
5) Scrivere in Italiano o in Inglese, se possibile grammaticalmente corretto, evitate stili di scrittura poco chiari, quindi nessuna abbreviazione tipo telegramma o scrittura stile SMS o CHAT.
6) Appena registrati è consigliato presentarsi nel forum dedicato.

La non osservanza delle regole porta a provvedimenti di vari tipo da parte dello staff, in particolare la non osservanza della regola 5 porta alla cancellazione del post e alla segnalazione dell'utente. In caso di recidività l'utente rischia il ban temporaneo.

Array e liste

Messaggioda Absolut » mar gen 22, 2008 11:58

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!!!
Avatar utente
Absolut
Linux 3.x
Linux 3.x
 
Messaggi: 1465
Iscritto il: gio feb 10, 2005 0:00
Località: Roma
Slackware: current

Re: Array e liste

Messaggioda Toni » mar gen 22, 2008 13:00

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
Avatar utente
Toni
Linux 2.6
Linux 2.6
 
Messaggi: 993
Iscritto il: lun gen 30, 2006 22:08
Località: milano
Slackware: slackware-14
Kernel: 3.10.5
Desktop: i3

Re: Array e liste

Messaggioda FireEater » mar gen 22, 2008 13:09

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, #-o
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 8)
Avatar utente
FireEater
Linux 2.6
Linux 2.6
 
Messaggi: 508
Iscritto il: sab feb 05, 2005 0:00
Località: Cagliari <---> Torino
Nome Cognome: Giuseppe M.
Slackware: Current
Kernel: 2.6.32.7-smp
Desktop: kde 4.3.4

Re: Array e liste

Messaggioda Absolut » mar gen 22, 2008 13:41

grazie mille... ora mi è più chiaro il tutto!
Avatar utente
Absolut
Linux 3.x
Linux 3.x
 
Messaggi: 1465
Iscritto il: gio feb 10, 2005 0:00
Località: Roma
Slackware: current

Re: Array e liste

Messaggioda Mario Vanoni » mar gen 22, 2008 15:19

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

Mario Vanoni
Mario Vanoni
Iper Master
Iper Master
 
Messaggi: 3174
Iscritto il: lun set 03, 2007 20:20
Località: Cuasso al Monte (VA)
Nome Cognome: Mario Vanoni
Slackware: 12.2
Kernel: 3.0.4 statico
Desktop: fluxbox/seamonkey


Torna a Programmazione

Chi c’è in linea

Visitano il forum: Google [Bot] e 1 ospite

cron