dubbi sulle strutture dati Liste, alberi, code

[giupardeb]

Salve a tutti ragazzi, ho un dubbio sulle strutture dati messe in oggetto. In particolare ho il dubbio sul quale utilizzare a seconda del problema. Mi spiego meglio, come faccio a capire datomi un esercizio se devo usare una pila, o una lista o un albero e così via? Non si dovrebbe usare nella quasi sempre l'albero dato che la complessità è sempre logaritmica?

[andbin]

Originariamente inviato da giupardeb
come faccio a capire datomi un esercizio se devo usare una pila, o una lista o un albero e così via? Non si dovrebbe usare nella quasi sempre l'albero dato che la complessità è sempre logaritmica?

No.
Quando devi scegliere una "collezione" devi farti una serie di domande, del tipo (elenco assolutamente non esaustivo!):
- la collezione deve mantenere associazioni tra "chiavi" e valori o no?
- la collezione deve ammettere duplicati o no?
- la collezione deve mantenere ordinati gli elementi o no?
- la collezione deve permettere inserimenti veloci? o permettere di rintracciare velocemente (es. per indice) un elemento?
- la collezione deve fornire un iteratore con una sequenza prevedibile/ordinata o no?

Poi è chiaro che devi valutare la tipologia in base allo scenario reale. Se ti si chiede di fare associazioni tra chiavi e valori, allora la tipologia utile è una "map". Se ti si chiede di avere una collezione in cui avere elementi "unici" in cui poi devi solo verificare se un elemento c'è o no, allora la tipologia è un "set".

[giupardeb]

mmmh ho capito, grazie sei stato chiaro.. ma diciamo che non hai fatto esempi che riguardavano liste e alberi.. quando posso scegliere una liste e quando un albero?

[andbin]

Originariamente inviato da giupardeb
mmmh ho capito, grazie sei stato chiaro.. ma diciamo che non hai fatto esempi che riguardavano liste e alberi.. quando posso scegliere una liste e quando un albero?

Gli alberi servono in genere o per rappresentare qualcosa che è proprio un "albero" (filesystem, nodi di un XML, ecc...) oppure, con certi tipi di alberi, per tenere ordinati gli elementi in modo da avere accesso con complessità O(log n).
Una lista serve quando non hai bisogno di ordinamento particolare, accetti eventuali duplicati e ti basta solo una "sequenza" di elementi. (poi a seconda del tipo di lista puoi avere accesso immediato per indice oppure no)
Insomma, sono 2 cose ben diverse!

[giupardeb]

sisi..che sono due cose ben diverse è ovvio comunque adesso ho capito bene la differenza.. adesso capisco..grazie