[C]Progetto algoritmi "Bunga-Bunga"

[goldorak]

Originariamente inviato da matteo.pata

Dicevo che va bene l'union find però volevo capire dove e come memorizzare le persone che struttura dati utilizzare.

Le strutture dati da utilizzare dipendono dalle operazioni a cui devono essere soggette. E le operazioni sono determinate dalle specifiche del problema in questione. Dal problema risulta che devi avere delle operazioni per inserire e rimuovere persone dalla struttura dati, e inoltre le operazioni devono essere efficienti. Ovverosia devono avere una complessita' logaritmica. Roba tipo liste semplici o array non vanno bene perche' al crescere dei dati di input ti ritrovi con complessita' quadratica nel caso peggiore.
Vanno bene alberi (meglio se bilanciati quindi alberi AVL, alberi 2-3, alberi 2-3-4, alberi red-black etc...). La scelta e' sterminata prendi quello che ti risulta piu' semplice da implementare.
Un altra struttura dati efficiente e' quella delle skip lists.

Tutte queste strutture sono spiegate nei vari libri sugli algoritmi (Comer Leiserson Rivest, etc...)

Infine per memorizzare i dati. Le strutture dati si classificano in due grosse famiglie, strutture dati endogene e strutture dati esogene.
Nelle strutture dati endogene gli attributi dei dati che vuoi memorizzare vanno inseriti direttamente nei nodi della struttura dati. Nelle strutture dati esogene invece di mantenere direttamente gli attributi nel nodo si mantiene un semplice puntatore ad una struttura (in genere un record) che conterra' gli attributi dei dati.

Sta a te decidere se vuoi usare una struttura dati endogena o esogena. E una questione di comodita'. Ovviamente nei nodi della struttura dati ci potranno essere anche dei puntatori ad altre strutture dati se questo si rendesse necessario dal problema.

[matteo.pata]

Grazie mille sei stato molto esaustivo e di molto aiuto....

[Vincenzo1968]

http://milano.repubblica.it/cronaca/...ga-12017379/1/

[goldorak]

Originariamente inviato da Vincenzo1968

http://milano.repubblica.it/cronaca/...ga-12017379/1/