Appunti di Fondamenti di informatica - Modulo B

Università degli Studi di Messina

Corso di laurea in Ingegneria Elettronica ed Informatica A.A. 2020/21

Fondamenti di Informatica (Modulo B)

Strutture dati

Indice

• Strutture dati elementari
  • Introduzione
  • Liste concatenate
  • Liste doppiamente concatenate
  • Liste tramite array collegati
• Tipi di dati astratti (ADT)
  • Pila
  • Coda
  • Liste di liste
  • Strumenti utili per un programmatore C
• La ricorsione
  • Introduzione
• Algoritmi di ordinamento e di ricerca
  • Problemi della ricerca
  • Problemi dell’ordinamento
  • Ordinamento di strutture complesse e algoritmi di ordinamento esterno
• Grafi
  • Terminologia
  • Rappresentazione di grafi
  • Attraversamento di grafi
• Alberi
  • Classificazione
  • Proprietà matematiche degli alberi binari
  • Rappresentazione degli alberi
  • Attraversamento degli alberi
  • Alberi binari di ricerca

Strutture dati elementari

Studio delle tecniche di base per l'organizzazione dei dati che devono essere elaborati dai programmi. La scelta delle strutture dati e quella degli algoritmi sono strettamente correlate:

• Per uno stesso insieme di dati vi sono strutture dati che richiedono più spazio di altre.
• Per uno stesso insieme di operazioni sui dati, alcune strutture dati portano ad implementare algoritmi più efficienti di altri.

Una struttura dati non è un oggetto passivo; bisogna sempre tenere in considerazione le operazioni che devono essere eseguite su di essa, e quindi gli algoritmi necessari.

• Le strutture dati più efficienti sono:
  • Liste
  • Pile
  • Code
  • Grafi
  • Alberi

Una struttura dati è un meccanismo per immagazzinare dati e recuperarli. Si ha una dicotomia tra tempo e spazio. Lo spazio è l’occupazione di memoria. Il tempo è l’efficienza degli algoritmi.

Costrutti di base

Tutti i dati elaborati su un calcolatore alla fine sono scomposti in singoli bit. Scrivere programmi che elaborano direttamente questi bit risulta quanto meno noioso. I tipi ci consentono di specificare come andremo a usare un particolare insieme di bit. Le funzioni permettono di definire le operazioni che verranno eseguite sui dati.

In C i programmi sono costituiti a partire da pochi tipi di dati di base:

• Numeri interi (int)
• Numeri in virgola mobile (float, double)
• Caratteri (char)

Usiamo, inoltre, le strutture per raggruppare dati eterogenei e i puntatori per riferirci in modo indiretto ai dati. Un tipo di dato è definito da un insieme di valori e da una collezione di operazioni su questi valori. Molte delle operazioni associate a tipi di dati standard sono già incorporate nel linguaggio C (ad esempio le operazioni aritmetiche), altre operazioni sono implementate sotto forma di funzioni in librerie di funzioni standard (ad esempio la gestione delle stringhe), altre ancora sono costituite dalle funzioni definite nei programmi che scriviamo.

Esempio: Nozione astratta di un punto nel piano

struct point {
    float x;
    float y;
}
struct point a, b;
a.x=1.0; a.y=1.0; b.x=4.0; b.y=5.0;

float distance(struct point a, struct point b) {
    float dx=a.x-b.x, dy=a.y-b.y;
    return sqrt(dx*dx+dy*dy);
}

float d = distance(a,b); // d sarà uguale a 5

Struttura dati

Fino a questo punto abbiamo trattato principalmente la definizione di frammenti individuali di informazioni da elaborare. In molti casi dovremo, invece, lavorare con enormi quantità di dati: è giunto, allora, il momento di vedere le modalità in cui possiamo organizzarli.

Con il termine struttura dati ci si riferisce ad un meccanismo di organizzazione delle informazioni per la fornitura di efficienti operazioni di accesso e manipolazione. Molte strutture dati importanti si basano su almeno uno dei due seguenti approcci:

• Utilizzo di array, dove organizziamo i dati secondo una modalità sequenziale fissa, rendendo l'accesso più facile della manipolazione;
• Utilizzo di liste, dove i dati sono organizzati in modo logicamente sequenziale, rendendo la manipolazione più agevole dell'accesso.

Array

Un array è un insieme fissato di oggetti dello stesso tipo memorizzati in modo contiguo e accessibili per mezzo di un indice. L'uso corretto degli indici, i quali dovranno essere numeri interi non negativi, minori della dimensione dell'array, è lasciato, in C, al programmatore.

L'importanza degli array deriva dal fatto che, su quasi tutti gli elaboratori, questi hanno una corrispondenza diretta con la memoria centrale.

Gestione statica e dinamica

int a[20];
int *a = (int*) malloc (20*sizeof(int));

In C il nome dell'array è, in effetti, un puntatore al primo elemento dell'array. La dimensione dell’array è definita con:

• Costanti definite con #define;
• Costanti definite con const;
• Costanti esplicite, es: V[10].

Le caratteristiche principali di un array sono:

• Ad accesso casuale: non tutte le strutture hanno questa caratteristica
• Accesso in scrittura: V[0]=2;
• Accesso in lettura: V[1]=V[0]+1;
• Allocazione statica o dinamica di un array:
  • Allocazione statica, si ha quando si definisce il nostro array, nome e tipo come una variabile, con una propria dimensione. Se viene allocata nel main vive per tutta la vita del programma. Se, invece, è allocata in una funzione essa ha la stessa vita della funzione in cui si trova.
  • Allocazione dinamica si ha usando malloc(), in questo caso viene allocata nell’heap. La sua vita, ovunque questa variabile viene allocata, continua ad esistere e per deallocarla serve free().
• Dimensione fissa: la dimensione di un array può essere fisica o logica:
  • La dimensione logica è quella effettivamente usata.
  • La dimensione fisica sono gli spazi che formano il nostro array, sia occupati che vuoti.

Avere la dimensione fissa porta ad uno spreco di memoria e ad una impossibilità di variare la dimensione dell’array.

Array multidimensionali

Se gli array unidimensionali corrispondono ai vettori, quelli bidimensionali (con due indici) corrispondono alle matrici, e sono molto usati nelle applicazioni matematiche. Gli array multidimensionali sono, in effetti, solo una convenienza notazionale, poiché i dati sono, alla fine, scritti nella memoria del calcolatore, che è essenzialmente unidimensionale.

In molti ambienti di programmazione gli array bidimensionali sono ordinati per righe in un array unidimensionale: in un array a[M][N] le prime N posizioni sono occupate dalla prima riga (gli elementi da a[0][0] ad a[0][N-1]), le seconde N posizioni dalla seconda riga (gli elementi da a[1][0] ad a[1][N-1]) e così via. In questo caso per accedere all'elemento a[i][j] verrà effettuata l'operazione a[i*N+j].

Nel caso di passaggio di un array bidimensionale ad una funzione è necessario, quindi, esplicitare almeno la seconda dimensione dell'array. Estendendo il discorso agli array multidimensionali è necessario esplicitare tutte le dimensioni escluso la prima.

Come si fa ad allocare memoria per array multidimensionali la cui dimensione non è nota al tempo di compilazione?

Si consideri, per semplicità, un array bidimensionale a[N][M] nel caso in cui i valori di N e M non siano noti. Esistono due metodi:

1. Si alloca un vettore monodimensionale di dimensione pari al prodotto delle dimensioni di riga e colonna (N*M): in questo caso però non è più possibile utilizzare la notazione a[i][j], ma devo accedere agli elementi calcolando la loro posizione effettiva: a[i*N+j];
2. Si utilizza un array di puntatori: in questo caso è possibile utilizzare la notazione b[i][j] per accedere agli elementi. Un ulteriore vantaggio è dato dalla possibilità di avere diverse lunghezze per le righe.

Si noti la differenza tra le due modalità: date le definizioni precedenti di a e b, a[i][j] e b[i][j] sono entrambi, dal punto di vista sintattico, riferimenti corretti ad un singolo intero. Ma a è un vettore bidimensionale vero e proprio (sono state riservate M*N locazioni della grandezza di un intero e l'elemento a[i][j] si trova nella posizione N*i+j). L'array di puntatori b, invece, stanzia M*N interi più N locazioni per i puntatori e per accedere all'elemento b[i][j] si deve accedere al primo array di puntatori selezionare la riga giusta e quindi accedere al secondo array. In tal caso non serve più conoscere la dimensione N (ad esempio nel passaggio a funzione potrei scrivere f(int**b){ ...}).

Liste

Struttura dati che rappresenta un insieme finito ed ordinato di n oggetti (a1, a2, ..., an) dello stesso tipo.

Proprietà:

• Ciascun elemento della lista è contraddistinto da una posizione in base alla quale è possibile individuare relazioni di precedenza e di successione tra gli elementi;
• La lista vuota è una lista che non presenta alcun elemento.

Ci sono diversi tipi di rappresentazione per le liste:

• Concatenata:
  • Basata su puntatori e allocazione dinamica;
  • Da utilizzare se ci sono modifiche (inserimenti, cancellazioni) frequenti;
  • Ogni elemento della lista è una coppia denominata Node = (Object, *Node)
• Tramite array collegati:
  • Basata su array monodimensionale;
  • Caratterizzata dalla definizione della capacità massima;
  • Comporta la gestione anche della lista libera, cioè dell’insieme degli elementi dell’array che non vengono utilizzati.

Operazioni sulle liste

• Creazione di una lista
• Ricerca di un elemento
• Calcolo della lunghezza della lista
• Inserimento di un elemento (in testa, in coda, in maniera ordinata)
• Cancellazione di un elemento

Liste concatenate

Ogni oggetto (nodo) della lista contiene le informazioni proprie più un puntatore all'oggetto successivo.

Esempio:

Definizione

• Tipo lista:
  • Data: costituisce l’elemento contenuto nella lista;
  • Next: puntatore all'elemento successivo.
• Puntatori di base:
  • Head: alla testa della lista;
• Commenti:
  • Una lista vuota è caratterizzata da head uguale a NULL.

Vantaggi e Svantaggi

Vantaggi:

• Non è necessario spostare elementi per realizzare operazioni di inserimento e cancellazione, perché basta modificare i riferimenti;
• Non è necessario imporre a priori un limite massimo alla dimensione della lista;
• La lista può essere gestita in modo che lo spazio di memoria da essa occupata sia proporzionale al numero dei suoi elementi.

Svantaggi:

• Le operazioni di accesso agli elementi sono costose, perché bisogna scandire gli elementi della lista che precedono quello voluto.

Creazione di una lista

Si crea una nuova lista che ha come unico elemento l'elemento da inserire.

NOTA: il puntatore head individua la testa della lista; infatti, punta l’elemento appena inserito che è l’unico elemento della lista.

Ricerca di un elemento

Si scorre tutta la lista fino a quando non si trova l’elemento oppure non si arriva alla fine della lista.

Inserimento in testa

Si deve fare puntare il puntatore alla testa della lista (head) all'elemento da inserire e si deve creare un collegamento tra l'elemento inserito ed il resto della lista.

Inserimento in coda

Si scorre tutta la lista fino a quando non si trova l’ultimo elemento (campo next dell’elemento uguale a NULL) e quindi si effettua l’inserimento del nuovo elemento.

Inserimento ordinato

Si scorre tutta la lista fino a quando non si trova un elemento maggiore di quello da inserire o non si arriva alla fine della lista e quindi si effettua l’inserimento. È necessario memorizzare un puntatore all'elemento corrente ed uno all'elemento precedente.

Cancellazione di un elemento

Si scorre tutta la lista fino a quando non si trova l'elemento da cancellare o non si arriva alla fine della lista. È necessario memorizzare un puntatore all'elemento corrente ed uno all'elemento precedente.

Lista doppiamente concatenata

Estendono la struttura delle liste concatenate inserendo in ogni nodo un puntatore al nodo precedente, oltre quello al nodo successivo.

NOTA: In questo modo è possibile scorrere la lista in entrambe le direzioni. Si possono implementare in maniera più semplice alcune operazioni e invece ne complica altre.

Creazione di una lista

Si crea una nuova lista che ha come unico elemento l'elemento da inserire. La differenza tra la lista concatenata e doppiamente concatenata, e abbiamo un puntatore che mettiamo a NULL. Si passano due puntatori proprio perché la lista è gestita da due puntatori.

Inserimento in testa

Si deve fare puntare il puntatore alla testa della lista (head) all'elemento da inserire e si deve creare un collegamento tra l'elemento inserito ed il resto della lista.

Cambia ma in meglio, infatti non c’è più il ciclo, mi baso su tail.

Inserimento in coda

Si inserisce l'elemento in ultima posizione utilizzando direttamente il puntatore alla coda della lista.

Inserimento ordinato

Si scorre tutta la lista fino a quando non si trova un elemento maggiore di quello da inserire o si arriva alla fine della lista e quindi si effettua l’inserimento. Nonostante non ci sono due puntatori essa è più complicato perché la presenza del puntatore tail e del prec mi forzano a gestire più casi:

• Il caso in cui la lista è vuota lo devo gestire a parte;
• Inserimento in testa;
• Inserimento in coda;
• Inserimento intermedio.

Nel caso di una lista concatenata il caso in cui la lista era vuota e l’inserimento in testa venivano gestite contemporaneamente, e l’inserimento in coda e l’inserimento intermedio erano gestiti nello stesso modo.

Cancellazione di un elemento

Si scorre tutta la lista fino a quando non si trova l'elemento da cancellare o non si arriva alla fine della lista.

Nota: questo codice contiene un bug che si manifesta quando l’elemento da cancellare è l’unico ovvero quando q==*head && q==*tail

Liste tramite array collegati

Consiste nell’associare ad ogni elemento della lista una componente dell’array che individua l’elemento successivo. Gli elementi dell’array appartengono alla lista in esame oppure alla lista libera.

Se dovevo usare gli array abbiamo visto che avevamo molti svantaggi. Ma se so quanti elementi ci sono nella lista in quel momento e devo fare un inserimento in coda, è più efficiente di un inserimento in coda in una lista concatenata. Questo perché l’array mi dà un accesso casuale, mentre la lista è sequenziale e la devo scorrere tutta. Il problema arriva se devo inserire in testa o nel mezzo, perché devo spostare gli elementi che seguono.

In una lista implementata con array collegati si risolve il problema dello spostamento degli elementi, però non ha più il vantaggio del fatto che io ho un accesso casuale, ma è sequenziale. In una lista concatenata o doppiamente concatenata non è limitato il numero di elementi che posso mettere, è limitata la memoria del calcolatore.

Definizione

• Tipo lista:
  • Data: costituisce l’elemento contenuto nella lista;
  • Next: valore dell’indice dell’array in cui si trova l’elemento successivo.
• Variabili di base:
  • Lista: array che contiene la lista;
  • Inizio: indice del primo elemento della lista;
  • Inizio_ll: indice del primo elemento della lista libera.
• Commenti:
  • Gli elementi dell’array che non appartengono alla lista in esame devono essere contenuti nella lista libera.

Vantaggi e Svantaggi

Vantaggi:

• Non è necessario spostare elementi per realizzare operazioni di inserimento e cancellazione, perché basta modificare i riferimenti;

Svantaggi:

• Le dimensioni dell’array sono fisse, per cui la lista non può crescere oltre certe dimensioni;
• Si può avere spreco di memoria perché le componenti dell’array devono essere allocate indipendentemente dalla dimensione della lista;
• Le operazioni di accesso agli elementi sono costose, perché bisogna scandire gli elementi della lista che precedono quello voluto.

Inserimento in testa

Si crea una nuova lista che ha come unico elemento l'elemento da inserire.

Cancellazione di un elemento

Si scorre tutta la lista fino a quando non si trova l'elemento da cancellare o non si arriva alla fine della lista.

Tipi di dati astratti (ADT)

Il programmatore mette a disposizione dei tipi di dati per i seguenti motivi:

• Il programma non si preoccupa della codifica e dell’occupazione di memoria e dell’accesso in memoria.
• Il programmatore non si preoccupa delle operazioni su quei tipi di dati, che a seconda se interi o fratti ecc... hanno un’implementazione diversa l’una rispetto all’altra.

Il tipo di dato astratto dà la possibilità al programmatore di decidere la loro codifica, occupazione in memoria e anche con le operazioni che lui vuole che si facciano. In C noi possiamo definire il tipo di dato, perché il programmatore ha:

• Int
• Char
• Float
• Double
• E loro variazioni...
• Array
• Struct
• Enum
• Union
• E loro combinazioni
• Typedef (dare un nome a un tipo di dato che abbiamo creato noi)

Il programmatore inoltre può fornire le operazioni che lui prevede per i tipi di dato.