Newsgroup: it.comp.lang.c
Titolo: [Q] Memorizzazione su disco di liste

Ciao a tutti,
supponiamo di avere un tipo Lista dichiarato come segue:
struct Lista  {
	int      valore;
	struct Lista   *next, *prev;
	};
come avrete capito si tratta di una semplice lista bidirezionale.
La mia domanda č la seguente: come faccio per registrare la lista su
disco?
Se scrivo i vari elementi Lista su disco, con *next e *prev scrivo gli
indirizzi di memoria dell'elemento successivo e precedente, ma questi
non cambiano ad ogni esecuzione?
In definitiva, come faccio a riaccedere alla lista ordinata?
Il problema piů in generale č come ci si comporta dovendo salvara su
disco strutture contenenti puntatori.
Spero di essere stato adeguatamente chiaro.
Grazie
Robby

Credo che potresti risolvere scaricando la lista in un file sequenziale
nell'ordine della lista , poi appena vuoi riaccedere alla lista scarichi il
file in una nuova lista , i puntatori non serve registrarli perche non ti
servono a nulla poi la malloc() (o qualunque altra funzione usi) da
l'indirizzo in base alla disponibilità di memeoria , quindi cambiano ad agni
reallocazione.
Ciao.

 In definitiva, come faccio a riaccedere alla lista ordinata?
Le tua č una lista di interi: basta salavare un file di interi ordinati, i
puntatori non ti interessano piů.
Devi salvare il contenuto della lista, non tutta la lista.
Quando vorrai leggere il tuo file, per ogni intero crei un elemento della
lista, i puntatori saranno settati run-time.
--
________________________________
Togliete NoSpaM per rispondermi
bye Brain

 disco strutture contenenti puntatori.
Devi salvare ordinatamente i valori in modo tale da poter ricostruire i
puntatori in lettura. Salvare i puntatori stessi non avrebbe alcun
senso.
EMG


Ma se la mia lista č molto grande? č pensabile di rileggere tutto il
file e creare un elemento di lista per ogni intero?
La mia idea era invece di accedere al file un elemento alla volta, in
ordine, fino a ritrovare l'elemento che cerco.
Inoltre vorrei fare una lista dinamica, con aggiunte ed eliminazioni.
Non č possibile in qualche modo, senza dover necessariamente
riordinare il file ogni volta che inserisco nuovi elementi?
Grazie
Ciao

 riordinare il file ogni volta che inserisco nuovi elementi?
Creando un file indice?
In pratica un file che contenga solo le informazioni su cui effettui
l'ordinamento, possibilmente molto piccolo, in modo da poter essere caricato
interamente in memoria e ordinato con qsort.
Ovviamente un indice siffatto deve contenere anche il numero di record
associato sull'altro file.
--
Alessandro Monti

 riordinare il file ogni volta che inserisco nuovi elementi?
Provo a rispiegarmi di nuovo:
1)Tu hai una lista bidirezionale di interi.
2)Ordini la lista... lo si riesce a fare velocemente.
3)Fai quello che vuoi con la lista... aggiungi ordinatamente elementi, togli
elementi, ecc....
4)Leggi gli interi dalla lista ordinatamente, dall'inizio alla fine e li
salvi, uno per uno, su un file.
5)Quando vai a rileggere il file(all'esecuzione successiva del programma),
rimetti ogni elemento in coda alla lista che avrà le stesse dimensioni di
prima e sarà già ordinata.
Se tu parti da un file di grosse dimensioni e non hai abbastanza memoria,
allora puoi fare come ti ha suggerito Alessandro Monti...


prima e sarà già ordinata.
Fino qui è molto chiaro e ti ringrazio. 
Ma se io dovessi aggiungere degli elementi dopo il passo 5, dovrei
comunque prima ricostruire tutta la lista in memoria.
E' proprio questo che volevo evitare, mentre la mia idea era di
scrivere sempre in fondo al file e avere un modo (cioè i puntatori,
che chiamerò fittizi per distinguerli da quelli reali) per accedere
agli elementi.
In questo modo non dovrei ricostruire tutta la lista ogni volta che
aggiungo qualcosa e non dovrei riordinare il file per intero, ma
dovrei solo aggiornare i "puntatori" dell'elemento precedente e
seguente.
provo a farti un esempio della mia idea (tieni presente però che no ho
molta esperienza di programmazione, quindi reclamo il beneficio del
dubbio sulle mie affermazioni.....)
per semplicità considero una lista i cui elementi hanno solo il
puntatore all'elemento successivo.
In un file abbiamo 4 record, separati da /
123,3/453,4/230,2/500,0
il numero prima della virgola è l'informazione, quello dopo è il
puntatore fittizio.
Quindi il primo elemento della lista punta al terzo elemento del file,
il terzo punta al secondo, il secondo punta al quarto e il quarto non
ha seguiti.
se ora aggiungo il numero 270 mi basta modificare i puntatori fittizi
di due soli elementi (il precedente e il nuovo elemento) ottenendo:
123,3/453,4/230,5/500,0/270,2
Per ottenere il record precedente ho dovuto leggere 3 soli record, il
primo, il terzo e il secondo.
Su file di grosse dimensioni il risparmio di memoria può essere
notevole.
Il puntatore fittizio, che per semplicità nell'esempio ho indicato con
i numeri da 1 a 5, potrebbero essere costituiti dalla posizione di
inizio dei vari record, espresso in byte.
Mi spiego: ogni carattere occupa un byte.
quindi il record 123,3/ occupa in tutto 6 bytes OK?
Di conseguenza, il puntatore indicato con 3 sarebbe 13, poichè il
tredicesimo byte è quello di inzio del terzo record.
E così via per tutti gli altri.
Cosa ne dite??????? sto vaneggiando  :-)???
Saluti
Robby

 Cosa ne dite??????? sto vaneggiando  :-)???
No, assolutamente. Puoi inventarti tutti i modi che vuoi per gestire dei
dati. Resta solo da vedere quanto siano funzionali ed efficienti. E
considera poi che molti di questi sono già stati ampiamente studiati e
descritti da gente ben più preparata di me e te. Questo per dire che
forse ti conviene prendere un libro sulle strutture dati e sulla
gestione dei database.
EMG

 > comunque prima ricostruire tutta la lista in memoria.
Che ne diresti, invece, di aggiungere tra i campi della lista un contatore
che faccia da indice? In caso di un nuovo inserimento, devi cambiare
mediamente N/4 elementi (se l'indice può assumere numeri negativi,
altrimenti N/2). E' certamente più semplice che avere un file indice
esterno, dato che, al momento di un nuovo inserimento e una volta saputo il
numero che dovrà avere, devi semplicemente scandire tutti i record, e
eseguire una cosa simile:
if (indice >= indice_del_nuovo_record)
    indice++;
per incrementare.
Nel caso in cui usi anche i numeri negativi, devi prima decidere se
incrementare o decrementare, e poi modifichi le 2 righe sopra in modo ovvio.
Da notare che scappatoie non ne esistono: che tu usi un file indice separato
o no, uno dei due file devi comunque riscriverlo "parecchio". Il file indice
di solito è più conveniente nel caso in cui la chiave di ordinamento sia di
dimensioni molto inferiori rispetto alla lunghezza totale del record. Oltre
che, ovviamente, nel caso in cui hai già delle librerie che fanno il lavoro
al posto tuo :-)
--
Alessandro Monti
--
Alessandro Monti