[C] Ordinamento e accesso random

[gabmac2]

Ho 1 problema e una domanda da porre,
come si può accedere a dati in modo random in un file per porli in una lista,ho un txt contenente
es
111
aaa
bbb
222
ccc
ddd
333
ttt
hhhh
555
yyy
iiii

ad esempio si vuole che il random prenda valori a caso ,come si fa a "mandarlo a capo" nella ricerca ,nel senso,come si fa a fargli capire di prendere i valori (sono in terzine,codice,nome e cognome)

domanda,miglior algoritmo ordinamento per lista linkata?

Grazie in ancitipo

[lupoxxx87]

Originariamente inviato da gabmac2

ad esempio si vuole che il random prenda valori a caso ,come si fa a "mandarlo a capo" nella ricerca ,nel senso,come si fa a fargli capire di prendere i valori (sono in terzine,codice,nome e cognome)

EEEEH ?!

per l'ordinamento di algoritmi ce n'è a bizzeffe

[gabmac2]

si,ok,ma per creare un archivio qual' è il miglior tipo di lista ,linkata,doppiamente linkata ,circolare.....?e su questo tipo di lista qual' è il miglior ordinamento ?

[WarDuck]

Bisogna vedere bene cosa vuoi fare, cmq in genere un'ottima struttura dati è un albero binario di ricerca, consente la ricerca in O(log N).

In pratica ogni nodo X dell'albero ha un figlio sinistro e uno destro, nel figlio sinistro in genere si pone l'elemento minore di X, mentre nel figlio destro l'elemento maggiore o uguale a X (se vuoi memorizzare doppioni).

Uno dei problemi con questa struttura è che l'albero può essere sbilanciato tutto da un lato e degenerare nel caso pessimo in una lista collegata (ricerca in O(N) in tal caso), per ovviare a questo si adotta il bilanciamento automatico, che non è immediato da implementare (vedi alberi AVL).

[gabmac2]

grazie,avrei però bisogno di ordinare in loco e come lista per un piccolo archivio,va bene la linkata?

[WarDuck]

Originariamente inviato da gabmac2

grazie,avrei però bisogno di ordinare in loco e come lista per un piccolo archivio,va bene la linkata?

Se spieghi meglio cosa vorresti fare forse riusciamo a darti un aiuto più mirato.

In ogni caso l'ordinamento in genere è finalizzato alla ricerca, e una struttura come un albero binario se mantenuta opportunamente bilanciata ti garantisce prestazioni superiori senza ricorrere ad un continuo ordinamento dei dati (l'ordinamento viene imposto direttamente all'inserimento dei dati).

Se il fine è la ricerca dei dati allora ti consiglio di usare un albero binario.

Tanto per la cronaca i principali DBMS fanno uso di strutture ad albero.

[gabmac2]

grazie! ok,ma io devo (per esercizio) creare in una lista (come voglio) ,ed effettuare ricerche e l' ordinamento (con quello che voglio),non posso usare db
Da qui le domande per entrambe le cose,andrei su linkata e quicksort,confermate?

Per l' altra domanda come posso fare a posizionarmi su una riga i-esima di un file txt (accedendo con read) ,dove questa riga sia multipla di 3? (seek?)

Grazie in anticipo!

[WarDuck]

Originariamente inviato da gabmac2

grazie! ok,ma io devo (per esercizio) creare in una lista (come voglio) ,ed effettuare ricerche e l' ordinamento (con quello che voglio),non posso usare db
Da qui le domande per entrambe le cose,andrei su linkata e quicksort,confermate?

Per l' altra domanda come posso fare a posizionarmi su una riga i-esima di un file txt (accedendo con read) ,dove questa riga sia multipla di 3? (seek?)

Grazie in anticipo!

Ah ecco se era un'esercizio potevi dirlo prima ,cmq non ho mai detto che devi usare un DB, ho detto che le strutture ad albero proprio per la loro efficienza sono usate nei DB.

Detto ciò una lista doppiamente linkata (che quindi ha anche riferimento al predecessore) la vedo meglio.

Puoi andare di quicksort, però non ho mai implementato algoritmi di ordinamento su strutture diverse dagli array, ci potrebbero essere delle difficoltà dovute al fatto che non puoi accedere in maniera diretta agli elementi della lista ma devi usare un iteratore.

[clockover]

Con lsesk puoi posizionarti in un punto qualsiasi del file! Dai uno sguardo qui http://www.manpagez.com/man/2/lseek/

Comunque per un algoritmo di ordinamento devi sempre definire un (non ricordo bene il nome ma te lo chiamo così) comparatore!
Ad esempio per i numeri un comparatore ti dice che 1 è minore di 2 oppure che 1 è uguale a 1! Per elementi diversi dai numeri devi definirlo tu! Ad esempio per un ordinamento lessicografico "pippa" viene prima di "pippo" (che esempiaccio gagliardo eh)!
Comunque come Java anche il C ha già la funzione di quick sort e anche di merge sort, e addirittura anche di heap sort .... http://www.manpagez.com/man/3/qsort/
devi solo implementare il comparatore...

[WarDuck]

Se non erro quelle funzioni vanno bene solo per gli array, e non ad esempio per le liste collegate.

[clockover]

Originariamente inviato da WarDuck

Se non erro quelle funzioni vanno bene solo per gli array, e non ad esempio per le liste collegate.

A non ne ho idea però se c'era una cavia che voleva ammazzarsi un po per provare

[gabmac2]

grazie ragazzi,allora ,al momento però penso partirò con una linkata semplice e quicksort,eventualmente poi approfondirò con la doppiamente linkata

per lseek come faccio a portarmi ad esempio alla quarta riga?

lseek(file, 4, SEEK_SET); ?

Grazie!

[clockover]

Originariamente inviato da gabmac2

grazie ragazzi,allora ,al momento però penso partirò con una linkata semplice e quicksort,eventualmente poi approfondirò con la doppiamente linkata

per lseek come faccio a portarmi ad esempio alla quarta riga?

lseek(file, 4, SEEK_SET); ?

Grazie!

tutto dipende dal terzo parametro... comunque ricorda che l'offset parte da zero quindi se sei all'inizio la quarta è 3

[WarDuck]

Edit.

[gabmac2]

grazie,ma allora cosa devo scrivere per andare alla terza riga?

[gugoXX]

E' probabile che ti convenga leggere prima tutta le righe, e poi sceglierle a caso

[gabmac2]

ad esempio vorrei generare un numero es 6 e andare al sesto record,come posso fare?

[gugoXX]

Carichi tutte le stringhe in una lista o un array, e poi vai a prendere il sesto elemento...

Possibile pseudocodice per il C
1. conto quante righe ci sono
2. Creo un array di tante righe
3. rileggo il file, memorizzando ciascuna riga nel posto giusto
4. inizio a tirare i valori a caso e restituisco ogni volta il record corrispondente.

In C#, che mi piace tanto ma tanto ma tanto di piu', sarebbe

string[] data = File.ReadAllLines(@"C:\temp\mioFile.dat");
Random rnd=new Random();
string primoDato = data[rnd.Next(data.Length)];

Non ho invece capito a cosa ti servirebbe l'ordinamento.

[gabmac2]

grazie,è l' idea che avevo avuto io,ma devo assolutamente andare sul file come ho scritto (è il testo del problema),come posso fare?Penso si possa accedere a un iesima riga

[DanieleC88]

Originariamente inviato da WarDuck

Puoi andare di quicksort, però non ho mai implementato algoritmi di ordinamento su strutture diverse dagli array, ci potrebbero essere delle difficoltà dovute al fatto che non puoi accedere in maniera diretta agli elementi della lista ma devi usare un iteratore.

In realtà (in particolare per il quicksort) non comporta grosse difficoltà. Tempo fa aveva implementato proprio il quicksort su una lista doppiamente collegata, magari lo ripesco e lo posto qua.