Inauguriamo una nuova sezione del blog che avrei voluto iniziare già diverso tempo addietro ma che, per mancanza di tempo, non ho mai cominciato a scrivere.
La nuova sezione, particolarmente interessante per chi vuole approfondire la programmazione ad un livello più alto, tratterà le strutture dati. Per studiare gli algoritmi che gestiscono questi tipi di elementi, useremo il C/C++ vista la potenza del linguaggio e data la presenza dei puntatori che favoriscono la possibilità di sfruttare le qualità stesse delle strutture.
STRUTTURE DATI
Le strutture dati sono dei particolari strumenti strutturali mediante i quali è possibile organizzare un insieme di dati e mantenerli o in memoria centrale, per tutta la durata dell'uso del software, o per riversarli nella memoria di massa per eventuali modifiche successive.
Un buon uso delle strutture dati, prevede la possibilità di utilizzare dati di tipo diverso nello stesso elemento strutturale. Proprio per tale motivo, quando si scrive un algoritmo che gestisce una struttura, la si deve vedere come una situazione il più possibile generica senza soffermarsi in maniera particolare sul tipo di dato da utilizzare. In questo modo si scriverà codice perfettamente utilizzabile in ogni situazione in cui l'utente può trovarsi.
ALGORITMI
Come si è accennato, le strutture dati sono gestite da particolari algoritmi studiati appositamente per la struttura presa di volta in volta in esame.
Un'algoritmo è una serie di step (passi) da effettuare per poter giungere alla realizzazione di uno scopo prefissato. La serie di passi effettuati deve essere finita e deve giungere sempre alla risoluzione del problema iniziale. Un algoritmo deve godere dell'ottimizzazione per la richiesta di memoria al sistema e/o per la richiesta di cicli e quindi di tempo di esecuzione. Tuttavia un buon algoritmo si basa anche su altri parametri quali robustezza, stabilità, modularità, etc...
Una buona organizzazione della struttura dati, favorisce la stesura di buoni algoritmi sia in termini di uso di memoria che di velocità. Ad esempio, cercare una parola all'interno di una lista risulterà più facile se quest'ultima è ordinata e, in tale situazione, l'algoritmo sarà scritto in maniera tale da cercare la parola in base a come è ordinata la lista.
Anche la scelta di una struttura, anziché un'altra, in base alla situazione, porta all'ottimizzazione del codice che la gestirà.
COME SCEGLIERE LA STRUTTURA
La scelta della struttura dati più adatta deve essere studiata dal programmatore e richiede la considerazione di diversi fattori
- Risorse necessarie (codice più veloce o più leggero?)
- Inserimento degli elementi (In testa, in coda o in ordine casuale?)
- Prelievo degli elementi (In testa, in coda o in ordine casuale?)
- Eliminazione degli elementi (In testa, in coda o in ordine casuale?)
Bisogna tener presente che l'uso di una particolare struttura dati può favorire alcuni fattori ma può essere poco pratica per altri. Questo vuol dire che non esiste la struttura perfetta ma quella più adatta ad ogni situazione. Questo vuol dire che c'è, ad esempio, quella più adatta all'ordinamento, quella migliore per il prelievo o quella migliore per l'inserimento.
STRUTTURE DATI DINAMICHE
Le strutture dati possono essere catalogate in base alle loro prestazioni nelle diverse situazioni o in base alle operazioni che è possibile effettuare sulle stesse. Con il termine strutture dati dinamiche si intendono quelle particolari strutture che fanno uso dei puntatori e della locazione dinamica della memoria per la gestione dei propri elementi in fase di esecuzione. Ogni elemento è in qualche modo connesso almeno ad un altro e tale connessione può essere cambiata durante lo svolgimento del software. Qualora l'uso dei puntatori non fosse possibile si può ricorrere ad altri sistemi che però peccano per carenza di flessibilità.
Tra esse troviamo, ad esempio, liste, alberi, grafi e tabelle. Ognuna di esse sarà analizzata in futuro in maniera approfondita.
CONTENITORI
I contenitori sono strutture derivate da quelle dinamiche e si concentrano in maniera particolare sulla gestione dell'inserimento e del prelievo dei dati presenti all'interno. L'accesso ai dati di queste strutture è l'elemento che differisce tra ognuna di esse. C'è chi preleva i dati in testa, chi in coda e chi in base ad un indice.
Tra esse troviamo, ad esempio, la pila o la coda. Ognuna di esse sarà analizzata in futuro in maniera approfondita.
Abbiamo eseguito una breve carrellata di ciò che si studierà in questa sezione.
Alla prossima!!!