Questo articolo del corso di C non può che iniziare con una riga di commiato verso lo scomparso Dennis Ritchie (http://it.wikipedia.org/wiki/Dennis_Ritchie) autore del linguaggio che è materia di queste lezioni.
Grazie Dennis.
L’argomento di questa lezione è alla base di interi corsi universitari e materia di studio di tanti informatici al mondo, quindi questo articolo non può essere né una guida né un tutorial.
Non troverete sorgenti né esercizi oggi, nel prossimo articolo vedremo qualche possibile implementazione delle strutture dati più comuni, ma lo scopo di questa lezione è quello di fornirvi i primi concetti, le idee base per muoversi e comprendere il complesso mondo delle strutture dati.
Cos’è una struttura dati?
Come sempre diamo un’occhiata a cosa dice wikipedia (http://it.wikipedia.org/wiki/Struttura_dati)
una struttura dati è un’entità usata per organizzare un insieme di dati all’interno della memoria del computer.
Preciso e formale, ma forse non tanto comprensibile, vediamo quindi di chiarire meglio di cosa stiamo parlando.
I programmi possono essere considerati come dei “manipolatori di dati”: ricevono qualcosa in input, la elaborano e forniscono un output. I dati devono essere memorizzati secondo un preciso schema che può dipendere da tanti fattori, ciascun particolare schema prende il nome di “struttura dati”.
Le operazioni fondamentali
Determinare la struttura dati più adeguata al nostro programma ha un solo scopo: quello di rendere il programma più efficiente, perché come vedremo l’efficienza di un programma dipende dall’algoritmo eseguito e l’algoritmo dipende dalla struttura dati utilizzata.
Ma come si fa a scegliere una struttura dati al posto di un’altra?
Le strutture dati vengono catalogate in base alla loro efficienza sulle operazioni fondamentali che sono:
- Ricerca
- Inserimento
- Cancellazione
In un mondo imperfetto come il nostro non esiste la struttura dati perfetta e quindi ciascuna struttura fornirà dei buoni risultati su un’operazione e meno buoni su altre e, c’era da aspettarselo, quelle più efficienti sono anche le più difficili da mettere in pratica.
Bisogno di formalismo
Non vorrei addentrarmi in tecnicismi che forse non interessano ai molti, ma una precisazione è necessaria: come si stabilisce l’efficienza di una struttura dati su una particolare operazione?
Potremmo utilizzare un’approccio empirico, misurando il tempo impiegato su un certo numero di operazioni e generare così una “classifica”, ma come potremmo essere certi che questa classifica resterà valida anche in altre condizioni, con altri computer e altri dati? Bandito quindi l’approccio empirico si usa invece un’approccio formale basato su formule matematiche.
Per uniformità si utilizza un’approccio denominato “worst case” (caso pessimo) e si calcola quindi il numero di operazioni necessarie ad eseguire una operazione base nel peggiore dei casi. Tale numero spesso non è una costante, ma dipende dalla grandezza della struttura dati dove bisogna eseguire l’operazione, quindi il risultato è una funzione f(n) dove n è la taglia della struttura dati, questa funzione prende il nome di complessità.
Ecco quindi che abbiamo un metodo formale e rigoroso per paragonare due strutture dati: basta paragonare le loro funzioni di complessità. Tutto sarà più chiaro più avanti nell’articolo, quando faremo un breve esempio.
L’esempio più semplice: un array
L’array statico è la più semplice tra le strutture dati e non è particolarmente efficiente in nessuna operazione.
Supponiamo infatti di avere un array statico di taglia 100 in cui memorizzare dei semplici interi, quanto ci costano le operazioni base di ricerca inserimento e cancellazione?
Ricerca
Come si può ricercare un’elemento in un array? Non abbiamo molta scelta l’unica possibilità che abbiamo è scorrere con un ciclo for tutti gli elementi dell’array fin quando non l’abbiamo trovato. Sembrerebbe quindi che il numero di operazioni da eseguire dipenda dalla posizione dell’elemento nell’array e qui entra in gioco il concetto di “worst case”, poniamoci quindi nelle condizioni peggiori e calcoliamo la funzione di complessità. Il caso peggiore nella ricerca di un elemento è che questo elemento non sia presente nell’array ed in quel caso siamo costretti ad eseguire 100 confronti su un’array di taglia 100, 200 su un’array di taglia 200 e così via. Non è difficile quindi capire che la funzione di complessità è f(n)=n
Più precisamente si dice che che se l’arrray è di taglia n l’operazione di ricerca ha una complessità di O(n) (si legge “O-grande di n”) http://it.wikipedia.org/wiki/O-grande
Inserimento e cancellazione
Le altre due operazioni hanno almeno la stessa complessità della ricerca perchè per poter inserire un elemento bisogna prima effettuare una ricerca di una posizione vuota e per cancellarlo bisogna prima trovarlo.
Se il nostro programma utilizza pochissimi dati e non ci preoccupa il fatto che ogni singola operazione ci costi O(n) allora possiamo utilizzare un array, ma se avessimo bisogno di fare tanti inserimenti? Possiamo inventare una struttura dati che ci permetta di eseguire l’insert in modo più veloce?
Un accenno ad una struttura più complessa: la lista concatenata
La lista concatenata (o anche semplicemente “lista”) è una struttura dati fondamentale che viene usata per costruire delle strutture dati più complesse. La cancellazione e la ricerca hanno lo stesso costo che nell’array, ma la lista offre un efficientissimo O(1) per l’inserimento. O(1) significa che il numero di operazioni da eseguire per effettuare un inserimento è costante e non dipende dalla taglia della lista.
Una lista è composta da nodi ed un nodo è una semplice struct dove risiede il contenuto informativo e un puntatore, il puntatore punta al successivo nodo della lista se c’è, altrimenti punta a null.
Il primo nodo di una lista viene chiamato testa.
Se volessimo ricercare un elemento all’interno di questa struttura dovremmo necessariamente percorrerla tutta seguendo i puntatori quindi, come abbiamo già detto, la ricerca ci costerebbe O(n), stessa cosa per la cancellazione: O(n) anche in questo caso. E per l’inserimento?
L’inserimento non dipende dalla taglia della lista perché basta creare un nuovo nodo e posizionarlo all’inizio della lista. Ecco che abbiamo creato una struttura dati in cui l’inserimento costa O(1).
Esistono decine, se non centinaia, di strutture dati differenti, ciascuna nata per un preciso scopo ed ottimizzata per quello; è nostro compito di programmatori riuscire di volta in volta ad identificare la struttura dati più adatta al compito che ci è stato richiesto.
Purtroppo la potenza dei calcolatori viene spesso sfruttata per sopperire alla pigrizia dei programmatori: scrivere un ciclo su un array è più facile che implementare una struttura dati più complessa e su piccole quantità di dati la differenza di prestazioni è difficile da notare, ma quando i dati iniziano ad essere tanti a quel punto le strutture dati sono indispensabili e fanno la differenza tra un programma che funziona e uno che non funziona.
Buona programmazione.
IgnazioC
19 Responses to “18. Introduzione alle strutture dati in C”
26 Ottobre 2011
IgnaziocPer ogni dubbio parliamone pure sul forum!
6 Novembre 2011
fraif 2*2 then6 Novembre 2011
Ignaziocnon ho capito a cosa ti riferisci.
30 Novembre 2011
MarcoComplimenti ancora per questa guida, esponi molto bene gli argomenti, però mi raccomando a questo punto portaci fino in fondo, non lasciarci a metà strada. A quando la prossima lezione? Grazie
4 Gennaio 2012
dix93ciao ignazio, volevo solamente ringraziarti.. quando hai iniziato il corso io ero uno dei maggiori attivisti, e mi hai permesso di iniziare la facoltà di ingegneria con ottime basi per la formazione da scientifico che ho ricevuto! 😀
corsi del genere non se ne trovano sul web..
quindi grazie!! 🙂
4 Gennaio 2012
Ignaziocche dire? grazie! 🙂
11 Gennaio 2012
filippoVeramente ottimo corso, uno dei pochi veramente di qualità! Ormai c’è troppo web-spazzatura! Vorrei chiederti di non abbandonare questo corso perché è fantastico! e anche se non saremo in tantissimi a seguirlo questo non vuol dire che non sia migliore di tanti altri, perfavore cerca di riprendere la frequenza che avevi all’inizio!
11 Gennaio 2012
IgnaziocCiao e grazie per i complimenti. Come avrai notato sono molto attivo anche per quel che riguarda gli articoli per iOS e purtroppo non posso far tutto 😉 sempre che tutti gli utenti non decidano di versare un’euro ciascuno 🙂 a quel punto sarei molto più ricco di adesso e potrei lasciare il mio lavoro!
11 Gennaio 2012
AlexArrivo adesso dalla lezione 7! (ero curioso di vedere quante fossero!)
Parto praticamente da meno di zero però il corso è davvero bello e si capisce tutto!!
Non so quanto ci metto a spingermi fino a qui alla N°18 ma spero di trovarne altre in piu quando sarò arrivato!
@Ignazio: Grazie… 😀
18 Gennaio 2012
Maqix@Ignazioc il corso è fatto veramente bene ed è una risorse importante, per favore, non abbandonarlo!
24 Gennaio 2012
LucaMa i record (tipo di file) voi gli avete mai sentiti?
24 Gennaio 2012
Ignaziocricordo che me ne avevano parlato in pascal…era un modo per memorizzare all’interno di un file una struttura chiave-valore se non ricordo male.Non so se esiste l’equivalente in C ma in ogni caso puoi salvare su un file binario una struct e poi leggerla a blocchi.
23 Febbraio 2012
filippose vuoi io una donazione al sito la faccio se continuate a scrivere lezioni! ormai ho iniziato con questo corso e non vorrei continuare con un’altro!
23 Febbraio 2012
IgnaziocGrazie! I complimenti sono sempre ben accetti…ma guardate che questo corso è già bello corposo! Che argomenti vi interesserebbero?
26 Marzo 2012
alessandro porrociao complimenti per il corso.
non ho ben capito una cosa:
il corso é da ritenersi concluso?
se la risposta é affermativa, perché non cominciare con un corso completo di objective-c, scritto con la stessa lnea chiara e semplice?
4 Aprile 2012
MarcoGrazie per il corso. Anche io volevo sapere se dobbiamo attenderci altre lezioni oppure possiamo considerare il corso concluso qui. Solo per informazione.
Grazie mille
4 Aprile 2012
IgnaziocIl corso non è ufficialmente concluso, è conclusa la sua parte “sistematica” di pubblicazione. Tornerò presto a pubblicare qualche altro articolo sull’argomento.
13 Aprile 2012
alessandro porrobene non vedo l’ora di continuare il corso.
grazie mille.
28 Agosto 2012
SteveAllora Ignazioc… il corlo lo continuate a fare oppure no ?
spero proprio di si …. corsi ome questi nn sene trovano tutti i giorni sul web 😀