{"id":7844,"date":"2011-10-26T15:44:43","date_gmt":"2011-10-26T13:44:43","guid":{"rendered":"http:\/\/www.devapp.it\/wordpress\/?p=7844"},"modified":"2011-10-26T15:44:59","modified_gmt":"2011-10-26T13:44:59","slug":"18-introduzione-alle-strutture-dati-in-c","status":"publish","type":"post","link":"https:\/\/www.devapp.it\/wordpress\/18-introduzione-alle-strutture-dati-in-c\/","title":{"rendered":"18. Introduzione alle strutture dati in C"},"content":{"rendered":"<p><a href=\"http:\/\/www.devapp.it\/wordpress\/wp-content\/uploads\/2011\/10\/corso-completo-c-Introduzione-alle-strutture-dati-in-C-00.jpg\"><img loading=\"lazy\" decoding=\"async\" src=\"http:\/\/www.devapp.it\/wordpress\/wp-content\/uploads\/2011\/10\/corso-completo-c-Introduzione-alle-strutture-dati-in-C-00.jpg\" alt=\"corso-completo-c-Introduzione-alle-strutture-dati-in-C-00\" title=\"corso-completo-c-Introduzione-alle-strutture-dati-in-C-00\" width=\"200\" height=\"100\" class=\"alignleft size-full wp-image-7910\" \/><\/a> Questo articolo del corso di C non pu\u00f2 che iniziare con una riga di commiato verso lo scomparso Dennis Ritchie (<a href=\"http:\/\/it.wikipedia.org\/wiki\/Dennis_Ritchie\" target=\"_blank\">http:\/\/it.wikipedia.org\/wiki\/Dennis_Ritchie<\/a>) autore del linguaggio che \u00e8 materia di queste lezioni.<br \/>\nGrazie Dennis.<\/p>\n<p>L&#8217;argomento di questa lezione \u00e8 alla base di interi corsi universitari e materia di studio di tanti informatici al mondo, quindi questo articolo non pu\u00f2 essere n\u00e9 una guida n\u00e9 un tutorial.<br \/>\nNon troverete sorgenti n\u00e9 esercizi oggi, nel prossimo articolo vedremo qualche possibile implementazione delle strutture dati pi\u00f9 comuni, ma lo scopo di questa lezione \u00e8 quello di fornirvi i primi concetti, le idee base per muoversi e comprendere il complesso mondo delle <strong>strutture dati<\/strong>.<!--more--><\/p>\n<h4>Cos&#8217;\u00e8 una struttura dati?<\/h4>\n<p>Come sempre diamo un&#8217;occhiata a cosa dice wikipedia (<a href=\"http:\/\/it.wikipedia.org\/wiki\/Struttura_dati\" target=\"_blank\">http:\/\/it.wikipedia.org\/wiki\/Struttura_dati<\/a>)<\/p>\n<blockquote><p>una struttura dati \u00e8 un&#8217;entit\u00e0 usata per organizzare un insieme di dati all&#8217;interno della memoria del computer.<\/p><\/blockquote>\n<p>Preciso e formale, ma forse non tanto comprensibile, vediamo quindi di chiarire meglio di cosa stiamo parlando.<\/p>\n<p>I programmi possono essere considerati come dei &#8220;manipolatori di dati&#8221;: ricevono qualcosa in input, la elaborano e forniscono un output. I dati devono essere memorizzati secondo un preciso schema che pu\u00f2 dipendere da tanti fattori, ciascun particolare schema prende il nome di &#8220;struttura dati&#8221;.<\/p>\n<h4>Le operazioni fondamentali<\/h4>\n<p>Determinare la struttura dati pi\u00f9 adeguata al nostro programma ha un solo scopo: quello di rendere il programma pi\u00f9 efficiente, perch\u00e9 come vedremo l&#8217;efficienza di un programma dipende dall&#8217;algoritmo eseguito e l&#8217;algoritmo dipende dalla struttura dati utilizzata.<\/p>\n<p>Ma come si fa a scegliere una struttura dati al posto di un&#8217;altra?<\/p>\n<p>Le strutture dati vengono catalogate in base alla loro efficienza sulle operazioni fondamentali che sono:<\/p>\n<ul>\n<li>Ricerca<\/li>\n<li>Inserimento<\/li>\n<li>Cancellazione<\/li>\n<\/ul>\n<p>In un mondo imperfetto come il nostro non esiste la struttura dati perfetta e quindi ciascuna struttura fornir\u00e0 dei buoni risultati su un&#8217;operazione e meno buoni su altre e, c&#8217;era da aspettarselo, quelle pi\u00f9 efficienti sono anche le pi\u00f9 difficili da mettere in pratica.<\/p>\n<h4>Bisogno di formalismo<\/h4>\n<p>Non vorrei addentrarmi in tecnicismi che forse non interessano ai molti, ma una precisazione \u00e8 necessaria: come si stabilisce l&#8217;efficienza di una struttura dati su una particolare operazione?<br \/>\nPotremmo utilizzare un&#8217;approccio empirico, misurando il tempo impiegato su un certo numero di operazioni e generare cos\u00ec una &#8220;classifica&#8221;, ma come potremmo essere certi che questa classifica rester\u00e0 valida anche in altre condizioni, con altri computer e altri dati? Bandito quindi l&#8217;approccio empirico si usa invece un&#8217;approccio formale basato su formule matematiche.<br \/>\nPer uniformit\u00e0 si utilizza un&#8217;approccio denominato &#8220;worst case&#8221; (caso pessimo) e si calcola quindi il numero di operazioni necessarie ad eseguire una operazione base nel peggiore dei casi. Tale numero spesso non \u00e8 una costante, ma dipende dalla grandezza della struttura dati dove bisogna eseguire l&#8217;operazione, quindi il risultato \u00e8 una funzione f(n) dove n \u00e8 la taglia della struttura dati, questa funzione prende il nome di complessit\u00e0.<\/p>\n<p>Ecco quindi che abbiamo un metodo formale e rigoroso per paragonare due strutture dati: basta paragonare le loro funzioni di complessit\u00e0. Tutto sar\u00e0 pi\u00f9 chiaro pi\u00f9 avanti nell&#8217;articolo, quando faremo un breve esempio.<\/p>\n<h4>L&#8217;esempio pi\u00f9 semplice: un array<\/h4>\n<p>L&#8217;array statico \u00e8 la pi\u00f9 semplice tra le strutture dati e non \u00e8 particolarmente efficiente in nessuna operazione.<\/p>\n<p>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?<\/p>\n<p><strong>Ricerca<\/strong><\/p>\n<p>Come si pu\u00f2 ricercare un&#8217;elemento in un array? Non abbiamo molta scelta l&#8217;unica possibilit\u00e0 che abbiamo \u00e8 scorrere con un <em>ciclo for<\/em> tutti gli elementi dell&#8217;array fin quando non l&#8217;abbiamo trovato. Sembrerebbe quindi che il numero di operazioni da eseguire dipenda dalla posizione dell&#8217;elemento nell&#8217;array e qui entra in gioco il concetto di &#8220;worst case&#8221;, poniamoci quindi nelle condizioni peggiori e calcoliamo la funzione di complessit\u00e0. Il caso peggiore nella ricerca di un elemento \u00e8 che questo elemento non sia presente nell&#8217;array ed in quel caso siamo costretti ad eseguire 100 confronti su un&#8217;array di taglia 100, 200 su un&#8217;array di taglia 200 e cos\u00ec via. Non \u00e8 difficile quindi capire che la funzione di complessit\u00e0 \u00e8 f(n)=n<\/p>\n<p>Pi\u00f9 precisamente si dice che che se l&#8217;arrray \u00e8 di taglia <em>n<\/em> l&#8217;operazione di ricerca ha una complessit\u00e0 di O(n) (si legge &#8220;O-grande di n&#8221;) <a href=\"http:\/\/it.wikipedia.org\/wiki\/O-grande\" target=\"_blank\">http:\/\/it.wikipedia.org\/wiki\/O-grande<\/a><\/p>\n<p><strong>Inserimento e cancellazione<\/strong><\/p>\n<p>Le altre due operazioni hanno almeno la stessa complessit\u00e0 della ricerca perch\u00e8 per poter inserire un elemento bisogna prima effettuare una ricerca di una posizione vuota e per cancellarlo bisogna prima trovarlo.   <\/p>\n<p>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&#8217;insert in modo pi\u00f9 veloce?<\/p>\n<h4>Un accenno ad una struttura pi\u00f9 complessa: la lista concatenata<\/h4>\n<p><center><br \/>\n<img loading=\"lazy\" decoding=\"async\" alt=\"\" src=\"http:\/\/upload.wikimedia.org\/wikipedia\/commons\/thumb\/9\/9c\/Single_linked_list.png\/800px-Single_linked_list.png\" class=\"aligncenter\" width=\"400\" height=\"108\" \/><br \/>\n<\/center><\/p>\n<p>La lista concatenata (o anche semplicemente &#8220;lista&#8221;) \u00e8 una struttura dati fondamentale che viene usata per costruire delle strutture dati pi\u00f9 complesse. La cancellazione e la ricerca hanno lo stesso costo che nell&#8217;array, ma la lista offre un efficientissimo O(1) per l&#8217;inserimento. O(1) significa che il numero di operazioni da eseguire per effettuare un inserimento \u00e8 costante e non dipende dalla taglia della lista.<\/p>\n<p>Una lista \u00e8 composta da <strong>nodi<\/strong> ed un nodo \u00e8 una semplice <em>struct<\/em> dove risiede il contenuto informativo e un puntatore, il puntatore punta al successivo nodo della lista se c&#8217;\u00e8, altrimenti punta a <em>null<\/em>.<\/p>\n<p>Il primo nodo di una lista viene chiamato <strong>testa<\/strong>.<\/p>\n<p>Se volessimo ricercare un elemento all&#8217;interno di questa struttura dovremmo necessariamente percorrerla tutta seguendo i puntatori quindi, come abbiamo gi\u00e0 detto, la ricerca ci costerebbe O(n), stessa cosa per la cancellazione: O(n) anche in questo caso. E per l&#8217;inserimento?<br \/>\nL&#8217;inserimento non dipende dalla taglia della lista perch\u00e9 basta creare un nuovo nodo e posizionarlo all&#8217;inizio della lista. Ecco che abbiamo creato una struttura dati in cui l&#8217;inserimento costa O(1).<\/p>\n<p>Esistono decine, se non centinaia, di strutture dati differenti, ciascuna nata per un preciso scopo ed ottimizzata per quello; \u00e8 nostro compito di programmatori riuscire di volta in volta ad identificare la struttura dati pi\u00f9 adatta al compito che ci \u00e8 stato richiesto.<\/p>\n<p>Purtroppo la potenza dei calcolatori viene spesso sfruttata per sopperire alla pigrizia dei programmatori: scrivere un ciclo su un array \u00e8 pi\u00f9 facile che implementare una struttura dati pi\u00f9 complessa e su piccole quantit\u00e0 di dati la differenza di prestazioni \u00e8 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.<\/p>\n<p>Buona programmazione.<br \/>\nIgnazioC<\/p>\n<p><center><br \/>\n<a href=\"http:\/\/www.devapp.it\/wordpress\/supporto-applicazioni\/le-applicazioni-dei-nostri-autori\/parole-vietate-di-ignazio-calo\" target=\"_blank\"><img loading=\"lazy\" decoding=\"async\" class=\"aligncenter\" src=\"http:\/\/www.devapp.it\/wordpress\/wp-content\/uploads\/2010\/02\/bannerIgnazioc.png\" alt=\"\" width=\"480\" height=\"100\" \/><\/a><br \/>\n<\/center><\/p>\n","protected":false},"excerpt":{"rendered":"<p>Questo articolo del corso di C non pu\u00f2 che iniziare con una riga di commiato verso lo&#8230;<\/p>\n","protected":false},"author":53,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"_acf_changed":false,"footnotes":""},"categories":[569],"tags":[954,955,956,592,957,953],"class_list":["post-7844","post","type-post","status-publish","format-standard","hentry","category-corso-completo-di-c","tag-array-in-c","tag-liste-concatenate-in-c","tag-liste-in-c","tag-programmare-in-c","tag-programmazione-in-c","tag-strutture-dati-in-c"],"acf":[],"aioseo_notices":[],"_links":{"self":[{"href":"https:\/\/www.devapp.it\/wordpress\/wp-json\/wp\/v2\/posts\/7844","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.devapp.it\/wordpress\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.devapp.it\/wordpress\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.devapp.it\/wordpress\/wp-json\/wp\/v2\/users\/53"}],"replies":[{"embeddable":true,"href":"https:\/\/www.devapp.it\/wordpress\/wp-json\/wp\/v2\/comments?post=7844"}],"version-history":[{"count":15,"href":"https:\/\/www.devapp.it\/wordpress\/wp-json\/wp\/v2\/posts\/7844\/revisions"}],"predecessor-version":[{"id":7913,"href":"https:\/\/www.devapp.it\/wordpress\/wp-json\/wp\/v2\/posts\/7844\/revisions\/7913"}],"wp:attachment":[{"href":"https:\/\/www.devapp.it\/wordpress\/wp-json\/wp\/v2\/media?parent=7844"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.devapp.it\/wordpress\/wp-json\/wp\/v2\/categories?post=7844"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.devapp.it\/wordpress\/wp-json\/wp\/v2\/tags?post=7844"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}