[C] Linked List

[daniele_dll]

finalmente ho deciso di mettermi a programmare in C ^^
e ieri non sapendo cosa fare mi sono scritto un server...xo ... ho usato degli array...e ovviamente immagginate se ci stanno 5000 elementi e devo cercarne uno che si trova alla posizione 4899 ^^

un po di materiale\codice donde lo trovo?

+/- so già cosa sono e come funzionano...xo vorrei qualke esempio pratico, un po di codice

[daniele_dll]

e ci aggiungo (sempre nella speranza che qualcuno risponda)

mi servirebbe creare una struttura basata su un doppio dizionario con accesso casuale...

^^

ovvero

array[0]
   |---array[0]
   |      |---linkded list
   |---array[1]
   |      |---linkded list
   |---array[2]
   |      |---linkded list
   |---array[3]
   |      |---linkded list
.
.
.
   |---array[255]
   |      |---linkded list

array[1]
   |---array[0]
   |      |---linkded list
   |---array[1]
   |      |---linkded list
   |---array[2]
   |      |---linkded list
   |---array[3]
   |      |---linkded list
.
.
.
   |---array[255]
   |      |---linkded list

array[2]
   |---array[0]
   |      |---linkded list
   |---array[1]
   |      |---linkded list
   |---array[2]
   |      |---linkded list
   |---array[3]
   |      |---linkded list
.
.
.
   |---array[255]
   |      |---linkded list

.
.
.
array[255]
...

e vorrei accedere ai vari elementi della linked list in maniera casuale in modo da velocizzare l'accesso

che mi consigliate?

[pixer]

Originariamente inviato da daniele_dll
e ovviamente immagginate se ci stanno 5000 elementi e devo cercarne uno che si trova alla posizione 4899 ^^

Puoi usare la ricerca binaria.

[kuarl]

oppure puoi usare un'albero bilanciato come struttura dati, x la ricerca è il migliore in assoluto, non so' se sia + veloce della ricerca binaria in un array xò ti assicuro che è molto veloce. Gli indici delle tabelle di mysql sono fatte con un albero bilanciato :sexpulp:

[daniele_dll]

stavo leggendo 1 po di documentazione sui binary tree

dove la trovo un po di docuemntazione?
(ehm...in maniera MOLTO veloce mi spiegate cosa sono e come funzionano? tenente conto che comunque una struttura di quel tipo anche se mastodondica è comunque molto veloce, xche non mi ritroverei + di 30\50 elementi x lista)

[daniele_dll]

http://libredblack.sourceforge.net/

che ne pensate?

qualcuno di voi ne ha usati?

in assembler per 586\mmx di già pronta roba c'è ne?

[iguana13]

Ma tu vuoi comunque mantenere tutti i dati in un vettore ad una sola dimensione od andrebbe bene anche un albero vero e proprio con i puntatori?

La ricerca binaria è molto veloce e funziona solo con gli array ordinati.
Su un vettore di n elementi, il numero di confronti per trovarlo nel peggiore dei casi è il logaritmo il base 2 di n.
Esempio:
su 5000 elementi, ci mette 13 confronti perchè 2 ^ 13 è un numero maggiore di 5000.
Nel caso medio il numero di confronti è di poco minore, nel caso migliore è 1.

[daniele_dll]

How stable is the code?: Very. I have used this at the heart of the SDDB directory service for several years now, which itself is the heart of the Cisco Enterprise Print System(CEPS). It performs at least a couple of hundred lookups a second day in and day out. It has also been used as the main indexing system in DENTS.

http://libredblack.sourceforge.net/
http://libredblack.sourceforge.net/rbgen.1.html

mi sa che uso questa libreria qui ^^

---

Ma tu vuoi comunque mantenere tutti i dati in un vettore ad una sola dimensione od andrebbe bene anche un albero vero e proprio con i puntatori?

La ricerca binaria è molto veloce e funziona solo con gli array ordinati.
Su un vettore di n elementi, il numero di confronti per trovarlo nel peggiore dei casi è il logaritmo il base 2 di n.
Esempio:
su 5000 elementi, ci mette 13 confronti perchè 2 ^ 13 è un numero maggiore di 5000.
Nel caso medio il numero di confronti è di poco minore, nel caso migliore è 1.

mi vanno bene in qualsiasi modo, il consumo di memoria non è molto importante

xo ho trovato sta libreria che mi permette anche l'utilizzo di array hash basati sull'algorittimo b-tree, quindi molto veloce ^^