Che materia stai cercando?

Programmazione e Strutture Dati

Appunti di Programmazione e strutture dati basati su appunti personali del publisher presi alle lezioni del prof. Fuccella dell’università degli Studi di Salerno - Unisa, facoltà di Scienze matematiche fisiche e naturali. Scarica il file in formato PDF!

Esame di Programmazione e Strutture Dati docente Prof. V. Fuccella

Anteprima

ESTRATTO DOCUMENTO

ELIMINAZIONE DI UN ELEMENTO IN UN ARRAY

Il primo passo da compiere per eliminare un array è quello di individuare in che posizione si trova

l’elemento, successivamente shiftare gli elementi verso sinistra.

Dati di ingresso: array di n interi, posizione elemento da eliminare

• Precondizione: 0 ≤ pos ≤ n-1

Dati di uscita: array senza l’elemento specificato

• ∀ i Є [0, pos-1], a1[i] = a[i] AND

Postcondizione:

◦ ∀ j Є [pos, n-1], a[j] = a[j+1] AND

n1 = n-1

Identificatore Tipo Descrizione

a array Array di interi in input

n intero Numero di elementi

nell’array a

pos intero Indice dell’elemento da

eliminare

a1 array Array di interi in output

n1 intero Numero di elementi

nell’array a1

Algoritmo in C

void elimina_elemento(int *a, int *n, int pos)

{ int i;

for (i = pos; i < (*n)-1; i++)

{ a[i] = a[i+1];

}

(*n)--;

} RICERCA IN UN ARRAY ORDINATO

Ricerca lineare

Per ricercare un elemento in un array ci basta scorrerlo tutto fino a quando non troviamo l’elemento

specificato o fino a quando non finisce l’array.

Esistono diversi algoritmi per la ricerca in un array ed ora ne vedremo qualcuno.

Il modo più semplice che viene subito in mente è proprio quello citato sopra, cioè di scorrere tutto

l’array fino a quando non troviamo il numero.

Dati in ingresso: array di n interi, elemento da ricercare

• Precondizione: n > 0

Dati in uscita: intero positivo (indice del numero trovato)

• Postcondizione: Se è stato trovato allora pos sarà l’indice della prima

◦ occorrenza, altrimenti sarà -1

Identificatore Tipo Descrizione

a array Array di interi in input

n intero Numero di elementi

nell’array

el intero Elemento da ricercare

pos intero Indice dell’elemento trovato o

-1

Algoritmo in C

int ricerca_lineare(int *a, int n, int elemento) {

int i;

for (i = 0; i < n; i++)

{ if (a[i] == elemento)

return i;

}

return -1;

}

Ricerca dicotomica (o binaria)

La ricerca dicotomica (o ricerca binaria), consiste nel dividere l’array in due parti, in modo tale da

capire in quale delle due parti si trova l’elemento che stiamo cercando.

In poche parole si confronta l’elemento che vogliamo trovare con quello che sta al centro dell’array,

così facendo avremo tre possibilità:

1. Il numero è uguale a quello che cercavamo, abbiamo finito

2. Il numero che cerchiamo è maggiore

3. Il numero che cerchiamo è minore

Visto che l’array è ordinato (ipotizzeremo in questo caso in modo crescente), se il nostro numero è

minore di quello che sta al centro, significa che dobbiamo cercare nella parte a destra dell’array, se

invece è maggiore dobbiamo cercare nella parte sinistra.

↓ metà

0 4 9

4 6 7 10 12 15 18 20 24 30

Ipotizziamo di voler cercare il numero 7, notiamo che 7 < 12, quindi significa che dobbiamo cercare

nella prima metà dell’array, quella che va dall’indice 0 all’indice 3.

↓ metà

0 1 3

4 6 7 10

Prendendo in considerazione solo dall’indice 0 all’indice 3, eseguiamo la stessa operazione. 3 / 2 =

1,5, quindi questa volta controlliamo il numero in indice 1, ma siamo sfortunati perché questa volta

7 > 6, quindi ripetiamo la stessa operazione, prendendo questa volta in considerazione l’array che

va dall’indice 1 all’indice 2.

1 2

6 7

A questo punto è diventato molto più semplice, abbiamo il 50% di possibilità di trovare il numero

che cerchiamo (sempre ammesso che ci sia, in questo caso si).

A questo punto in 3 passaggi abbiamo trovato il nostro numero.

Algoritmo in C

int ricerca_dicotomica(int *a, int n, int elemento) {

int inizio = 0, fine = n-1, centro;

while (inizio <= fine)

{ centro = (inizio+fine) / 2;

if (a[centro] == elemento)

return centro;

else if (elemento > a[centro])

inizio = centro+1;

else fine = centro-1;

}

return -1;

} TEST E DEBUGGING

Dopo aver scritto un programma è necessario effettuare test e debugging per verificare che funzioni

correttamente e non presenti errori.

Diremo oracolo l’output atteso, cioè quello che ci si aspetta che il programma ci restituisca, diremo

invece malfunzionamento un comportamento del programma diverso da quello atteso.

In generale è impossibile dimostrare la correttezza di qualunque programma, per cui l’obiettivo del

testing è quello di individuare malfunzionamenti.

Un malfunzionamento di un programma è causato da un difetto (errore, bug) nel codice, e può

essere introdotto in fase di analisi, specifica, progettazione o codifica.

Il debugging consiste nell’individuare e correggere il difetto che ha causato il malfunzionamento.

Più è alta la fase in cui si introduce il difetto, maggiore è la difficoltà nel rimuoverlo.

L’errore può essere trovato inserendo nel programma delle printf per conoscere il valore delle

variabili in determinati punti. Una volta corretto l’errore è bene rieseguire tutti i casi di test.

Testare ogni possibile input è impossibile, per cui staremo attenti a scegliere i casi più adeguati,

seguendo il buon senso ed evitando test ridondanti.

Aspetti da tener conto nella scelta dei casi di test:

Il numero n di elementi dell’array:

• Caso generale: array con n > 1

◦ Caso particolare n = 1

La disposizione degli elementi

• Caso generale: array non ordinato

◦ Array già ordinato in modo crescente

◦ Array già ordinato in senso decrescente

Testing ordinamento

Test case 1 (un solo elemento):

• array di input: 5

◦ oracolo: 5

Test case 2 (input ordinato in maniera crescente):

• array di input: 1 2 3 4 5 6 7 8 9

◦ oracolo: 1 2 3 4 5 6 7 8 9

Test case 3 (input ordinato in maniera decrescente):

• array di input: 10 9 8 7 6 5 4 3 2 1

◦ oracolo: 1 2 3 4 5 6 7 8 9 10

Test case 4 (non ordinato):

• array di input: 5 8 2 9 10 1 4 7 3 6 12 11

◦ oracolo: 1 2 3 4 5 6 7 8 9 10 11 12

Possiamo utilizzare i file per automatizzare il testing e fare in modo che l’input venga preso da un

file “input.txt”, dopo che è stato ordinato verrà confrontato con la corrispondente riga presente nel

file “oracle.txt”.

Per fare ciò avremmo bisogno di sapere come aprire e chiudere uno stream con C.

Per prima cosa dobbiamo includere la libreria <stdlib.h> e inizializzare una variabile puntatore di

tipo FILE:

#include <stdlib.h>

FILE *stream;

La prima cosa che dobbiamo fare dopo aver dichiarato uno stream è dirgli dove deve puntare, a che

file: stream = fopen(“file.txt”, “r”);

Nella funzione fopen dobbiamo inserire il percorso del file, possiamo anche inserire solo il nome se

il file si trova nella stessa cartella dell’eseguibile. Come secondo parametro invece va inserita la

modalità di apertura del file, in questo caso scegliamo di aprirlo in lettura (la r sta per read).

Modalità di apertura

r Apre il file in lettura (il file deve esistere)

w Apre il file in scrittura (non è necessario che il file esista)

a Apre il file in accodamento (non è necessario che il file esista)

r+ Apre il file in lettura e scrittura (il file deve esistere)

w+ Apre il file in lettura e scrittura (tronca il file se esiste)

a+ Apre il file in lettura e scrittura (accoda al file se esiste)

Funzioni lettura da stream

char *fgets(char *s, int size, FILE *stream);

int fscanf(FILE *stream, const char *format, …);

int fprintf(FILE *stream, const char *format, …);

fgets() legge da stream fino al carattere newline o fino alla fine del file, e salva la stringa in s

• fscanf() legge da stream fino ad un carattere di spazio (non memorizza lo spazio)

• fprintf() scrive sullo stream

Funzioni lettura da stringa

int sprintf(char *restrict buffer, const char *restrict format, …);

int sscanf(const char *str, const char *format, …);

Queste funzioni possono leggere e scrivere dati usando una stringa come se fosse un flusso.

Sprintf() scrive caratteri in una stringa. Restituisce il numero di caratteri memorizzati

• sscanf() legge i caratteri da una stringa. Restituisce il numero di dati letti e scritti con

• successo.

Esempio:

fgets(str, sizeof(str), stdin); //legge una riga dall’input

sscanf(str, “%d%d”, &i, &j); //legge due interi

Testing

Strategia big-bang: Integra il programma con tutti i sotto programmi, non adatto per

• programmi grandi, lento ed è difficile da capire dov’è il problema.

Strategie incrementali: testare e integrare i sottoprogrammi uno alla volta.

In programmi con più funzioni è meglio utilizzare la strategia bottom-up, cioè partire dalle funzioni

più in “basso”, quelle che non contengono altre chiamate a funzione, per poi passare a quelle in cui

vengono chiamate per poi piano piano salire sempre di più.

Strategia bottom-up e driver

Per ogni sottoprogramma da verificare è necessario costruire un programma main (detto driver) che:

acquisisca i dati di ingresso necessari al sottoprogramma

• invoca il sottoprogramma passandogli i dati di ingresso e ottenendo i dati di uscita

• visualizza i dati di uscita del sottoprogramma

• Usare la specifica del sottoprogramma per individuare i casi di test… (lo vedremo più

• avanti)

Automatizzare il test

Per automatizzare il test, utilizzeremo 2 file di input: “input.txt” che conterrà i vari input da

controllare, e “oracle.txt” che conterrà i risultati che ci aspettiamo dal programma.

Verrà generato un file “output.txt” che ci dirà se i test sono andati a buon fine.

N.B: in questa prova utilizzeremo un file “utils.h” dove saranno contenute funzioni generiche

(per il momento solo la funzione scambia) e il file “array.h” dove saranno contenute le

funzioni relative agli array.

vettore.h

void bubble_sort(int *a, int n);

int leggi_stringa(char *a, int *b);

int confronta_righe(int *s1, int *s2, int lunghezzaS1, int lunghezzaS2);

utils.h

void swap(int *a, int *b);

La funzione bubble_sort l’abbiamo già vista, ci servirà per ordinare gli elementi.

Leggi_stringa ci servirà per trasformare la stringa ottenuta in array di interi, e ci restituirà la

lunghezza della stringa, confronta_righe invece servirà per controllare se l’output del programma è

uguale a quello nel file “oracle.txt”

vettore.c

void bubble_sort(int *a, int n) {

int i, j;

for (i = 0; i < n; i++)

{ for (j = 0; j < n-1; j++)

{ if (a[j] > a[j+1])

scambia(&a[j], &a[j+1]);

}

}

}

int leggi_stringa(char *a, int *b) {

int i = 0, offset = 0;

while ((sscanf(a, "%d%n", &b[i], &offset)) == 1)

{ a += offset;

i++;

}

return i;

}

*il segnaposto %n restituisce il numero di caratteri presi fino a quel momento, se ad a non si

somma l’offset ad ogni ciclo, verrebbe presa sempre la stessa parola.

int confronta_righe(int *s1, int *s2, int lunghezzaS1, int lunghezzaS2) {

int i;

if (lunghezzaS1 != lunghezzaS2)

return 0;

for (i = 0; i < lunghezzaS1; i++)

{ if (s1[i] != s2[i])

return 0;

}

return 1;

}

makefile

driver: driver.o utils.o vettore.o

gcc driver.o utils.o vettore -o driver

.o

utils.o:

gcc -c utils.c

driver.o:

gcc -c driver.c

vettore.o:

gcc -c vettore.c

clean:

rm -f driver.o utils.o vettore.o driver

Adesso possiamo scrivere finalmente il main (driver.c).

Iniziamo con l’inizializzazione degli stream (file). Ce ne serviranno 3, 1 per input.txt, uno per

oracle.txt e uno per output.txt.

Per poter utilizzare gli stream bisogna importare la libreria <stdlib.h>

driver.c

#include <stdio.h>

#include <stdlib.h>

#include "utils.h"

#include "vettore .h"

#define N 50

int main ()

{ FILE *fp_input, *fp_oracle, *fp_output;

return 0;

}

Con questa prima operazione abbiamo inizializzato le tre variabili di tipo file che ci occorreranno,

ora bisogna vedere se ci generano errore. Errori sui file sono frequenti, perché un file che viene

aperto in lettura potrebbe non esistere, oppure potrebbe non esserci abbastanza spazio sul pc per

poter salvare un file.

Siccome la funzione fopen restituisce un puntatore vuoto nel caso in cui non trova il file,

terminiamo con EXIT_FAILURE, una macro definita in <stdlib> e indica una non corretta

terminazione del programma, viene utilizzata in genere con la funzione exit(). I controlli da eseguire

sono i seguenti:

driver.c

int main ()

{ FILE *fp_input, *fp_oracle, *fp_output;

if ((fp_input = fopen("input.txt", "r")) == NULL)

{ fprintf(stderr, "Errore apertura file input.txt\n");

exit(EXIT_FAILURE);

}

if ((fp_oracle = fopen("oracle.txt", "r")) == NULL)

{ fprintf(stderr, "Errore apertura file oracle.txt\n");

exit(EXIT_FAILURE);

}

if ((fp_output = fopen("output.txt", "w")) == NULL)

{ fprintf(stderr, "Errore apertura file oracle.txt\n");

exit(EXIT_FAILURE);

}

...

Ora dobbiamo fare un ciclo che legge riga per riga, dopodichè dobbiamo trasformare la riga in array

di interi con la funzione che abbiamo creato prima, grazie a quella funzione avremo anche la

lunghezza della stringa, così da poter utilizzare bubble_sort (che necessita della lunghezza della

stringa per funzionare), ripeteremo l’operazione con la stringa corrispondente nel file oracle.txt e

stamperemo l’esito sul file output.txt.

Non riscriverò tutto il codice per evitare confusione, il codice che scriverò adesso va messo

subito dopo il terzo if.

driver.c

...

char riga[N] = {'\0'};

int s1[N] = {'\0'}, s2[N] = {'\0'}, lunghezzaS1, lunghezzaS2, confronto, i = 1;

while ((fgets(riga, N, fp_input)) != NULL)

{ lunghezzaS1 = leggi_stringa(riga, s1);

bubble_sort(s1, lunghezzaS1);

fgets(riga, N, fp_oracle);

lunghezzaS2 = leggi_stringa(riga, s2);

confronto = confronta_righe(s1, s2, lunghezzaS1, lunghezzaS2);

fprintf(fp_output, "%d riga: %d\n", i, confronto);

i++;

}

fclose(fp_input);

fclose(fp_output);

fclose(fp_oracle);

return 0;

}

input.txt

5

10 9 8 7 6 5 4 3 2 1

1 2 3 4 5 6 7 8 9 10

7 4 5 3 10 8 6 9 2 1

oracle.txt

5

1 2 3 4 5 6 7 8 9 10

1 2 3 4 5 6 7 8 9 10

1 2 3 4 5 6 7 8 9 10

Come possiamo vedere dal file output.txt tutto funziona correttamente, il programma restituirà

come stato 0 se c’è stato un errore, 1 se è andato tutto bene.

output.txt

1 riga: 1

2 riga: 1

3 riga: 1

4 riga: 1

ESERCIZIO:

Implementare e testare l’aggiunta alla libreria vettore delle seguenti funzioni:

1. Funzione che prende in input un array di interi e restituisce la somma degli elementi

dell’array

2. Funzione che prende in ingresso due array di interi e restituisce in uscita l’array che contiene

come elemento di posizione i la somma degli elementi di posizione i degli array di input

3. Funzione che prende in ingresso due array di interi e restituisce il prodotto scalare dei due

∑ a[i]*b[i]

array. Il prodotto scalare di due array a e b è definito come: i

Scrivere un unico makefile per compilare tutti i driver per il testing

File del progetto:

utils.h

• vettore.h

• utils.c

• vettore.c

• driver_somma.c

• driver_somma_v.c

• driver_prodotto.c

Gli ultimi 3 sono i driver, cioè i programmi che testano la singola funzione.

File di input (creati a mano)

input_somma.txt

• input_somma_v.txt

• input_prodotto.txt

Oracoli (creati a mano)

Oracle_somma.txt

• Oracle_somma_v.txt

• Oracle_prodotto.txt

Output (creato dal programma)

Output_somma.txt

• Output_somma_v.txt

• Output_prodotto.txt

Makefile

driver_somma.exe: utils.o vettore.o driver_somma.o

gcc utils.o vettore.o driver_somma.o -o driver_somma.exe

driver_somma_v.exe: utils.o vettore.o driver_somma_v.o

gcc utils.o vettore.o driver_somma_v.o -o driver_somma_v.exe

driver_prodotto.exe: utils.o vettore.o driver_prodotto.o

gcc utils.o vettore.o driver_prodotto.o -o driver_prodotto.exe

utils.o:

gcc -c utils.c

vettore.o:

gcc -c vettore.c

driver_somma.o:

gcc -c driver_somma.c

driver_somma_v.o:

gcc -c driver_somma_v.c

driver_prodotto.o:

gcc -c driver_prodotto.c

clean:

rm -f utils.o vettore.o driver_somma.o driver_somma_v.o

driver_prodotto.o driver_somma.exe driver_somma_v.exe

driver_prodotto.exe

Ovviamente se su usa ubuntu, tutte le estensioni “.exe” dovranno essere rimosse.

Con questo unico makefile riusciamo a compilare tutti i file, se eseguiamo il comando “make”

verrà compilato “driver_somma.exe” (perché è il primo), per compilare invece

“driver_somma_v.exe” oppure “driver_prodotto.exe” dovremmo lanciare rispettivamente i

comandi: “make driver_somma_v.exe” e “make driver_prodotto.exe”. Per eliminare tutti i file,

eseguiamo l’unico comando “make clean”.

I driver dovranno prendere l’input da riga di comando. Esempio:

./driver_somma.exe input_somma.txt oracle.txt output_somma.txt

output_somma.txt è il file che verrà creato.

ARGOMENTI SU RIGA DI COMANDO

Il main ha due parametri, int argc e char argv (solitamente si chiamano così, ma possono essere

chiamati in qualunque modo).

Argc contiene il numero di argomenti passati da riga di comando, argv è un puntatore a stringa, e

contiene il testo scritto da riga di comando. Esempio:

./main.c file1.txt

In questo caso argc sarà 2, e argv[0] conterrà la stringa “./main.c”, argv[1] conterrà la stringa

“file1.txt”.

PUNTATORI E ALLOCAZIONE DINAMICA DELLA MEMORIA

Normalmente per poter raccogliere dei dati avremmo bisogno di creare un vettore di lunghezza N,

dove N è definito come costante. N potrebbe essere anche un numero molto elevato, ma noi

potremmo aver bisogno di un numero molto più piccolo rispetto ad N.

Mettiamo il caso che N sia uguale a 100, e a noi servano solo 10 elementi, utilizzeremo molta

memoria che non ci serve, come possiamo fare quindi per essere più efficienti e sprecare meno

memoria? Esistono delle funzioni specifiche per l’allocazione della memoria che ci permettono di

allocare solamente la memoria che ci serve per l’array.

La libreria stdlib mette a disposizione tali funzioni:

void *malloc(size_t size);

Alloca un blocco di memoria di size senza inizializzarlo

bytes

size_t è un tipo intero senza segno definito nella libreria del C.

Restituisce il puntatore al blocco.

void *calloc(size_t nelements, size_t elementSize);

Alloca un blocco di memoria di (nelements * elementSize) bytes e lo inizializza a 0 (clear).

Restituisce un puntatore al blocco.

void *realloc(void *pointer, size_t size);

Cambia la dimensione del blocco di memoria precedentemente allocato puntato da pointer.

Restituisce il puntatore ad una zona di memoria di dimensione size, che contiene gli stessi dati della

vecchia regione indirizzata da pointer. Nel caso in cui la nuova dimensione sia minore della

vecchia, viene troncata alla fine.

Vediamo come si usano:

main

int main(int argc, char *argv[])

{ int lunghezza;

char line[30];

int *a;

printf("Inserisci il vettore:\n");

scanf("%[^\n]", line);

a = input_array_dyn(&lunghezza, line);

bubble_sort(a, lunghezza);

stampa(a, lunghezza);

n 0;

retur

}

*Il segnaposto [^\n] legge tutto l’input fino a \n e in questo caso lo salva in line.

La funzione input_array_dyn prende in input l’indirizzo della lunghezza dell’array e la stringa da

cui leggere. Prende l’indirizzo perché il suo valore verrà modificato a seconda di quanto sarà grande

l’array creato dinamicamente. Questa funzione conta quanti elementi contiene line, dopodichè

alloca la memoria per l’array in base a quanti elementi ci sono. Restituisce l’indirizzo di memoria

del blocco allocato. A questo punto possiamo utilizzare le funzioni già create in precedenza per

l’ordinamento e la stampa.

Vediamo come è fatta la funzione input_array_dyn:

int *input_array_dyn(int *size, char *line) {

int i = 0, n = 0;

*size = conta_spazi(line) + 1;

int *array = malloc((*size) * sizeof(int));

if (array == NULL)

{ fprintf(stderr, "Impossibile allocare la memoria specificata\n");

exit(EXIT_FAILURE);

}

while(sscanf(line, "%d%n", &array[i], &n) == 1)

{ line += n;

i++;

}

return array;

}

Possiamo notare che questa funzione ne utilizza a sua volta un altra, conta_spazi, che conta quanti

spazi ci sono in un array, noi la utilizzeremo per contare quanti elementi ci sono semplicemente

aggiungendo 1.

int conta_spazi(char *a) {

int count = 0, i;

for (i = 0; a[i] != '\0'; i++)

{ if (a[i] == ' ')

count++;

}

return count;

} AREE DI ALLOCAZIONE

Il sistema operativo riserva ad ogni processo un segmento di RAM, che in generale è

suddiviso in quattro distinte aree di memoria:

1. L’area del programma, che contiene le istruzioni macchina del programma;

2. L’area globale, che contiene le costanti e le variabili globali;

3. Lo stack, che contiene la pila dei record di attivazione creati durante ciascuna

chiamata delle funzioni;

4. L’heap, che contiene le variabili allocate dinamicamente.

VARIABILI

Le variabili in C possono essere dichiarate in vari modi con diverse priorità di visualizzazioni.

Una variabile può essere globale, locale o automatica.

Le variabili globali vengono dichiarate esternamente alle funzioni e sono visibili a tutte le funzioni

la cui definizione segue la dichiarazione nel file sorgente. Sono dette statiche perché la loro

allocazione in memoria avviene all’atto del caricamento del programma, e la loro deallocazione al

termine.

Le variabili locali sono dichiarate e visibili solo all’interno di una funzione.

Le variabili automatiche sono dichiarate in blocchi interi alle funzioni e vengono allocate in

memoria a tempo di esecuzione dell’istruzione dichiarativa, e deallocate al termine del blocco.

Ogni variabile ha uno scope, una visibilità e una durata.

Cosa sono:

Scope: parte del programma in cui è attiva una dichiarazione (dice quando può essere usato

• un identificatore)

Visibilità: parte del programma in cui è accessibile una variabile (non sempre coincide con

• lo scope)

Durata: periodo durante il quale una variabile è allocata in memoria.

Int n;

int main() int n (globale)

{ scope: intero file

long n; visibilità: non è visibile nel main

… long l (locale)

{ scope: main

double n; visibilità: non è visibile nel blocco interno

… double n (automatica)

} scope: blocco interno

… visibilità: coincide con lo scope

}

Variabili globali definite in un file F1 possono essere usate in un file F2 dichiarandole extern in F2:

extern int n;

Con la dichiarazione extern non si definisce una variabile e non si alloca memoria.

Le variabili static sono private al file in cui vengono dichiarate.

static int n;

In C è possibile la dichiarazione static di variabili locali, in questo modo la classe di allocazione

della variabile cambia, trasforma una variabile locale in una statica, di conseguenza cambia la

durata della variabile, ma non lo scope, che rimane confinato alla funzione, o blocco, in cui la

variabile è dichiarata. Si ha che il valore della variabile “sopravvive” all’esecuzione della funzione

in cui è stato definito.

Le variabili static possono servire per l’information hiding.

Dichiarare una funzione come static la rende privata al file in cui è dichiarata, e quindi ne modifica

lo scope. Per esempio, nel modulo vettore, la funzione minimo viene usata solo localmente dalla

funzione ordina_array. Per renderla privata basta aggiungere static:

static int minimo(int *a, int n);

Così facendo però dobbiamo rimuovere la dichiarazione della funzione dal file vettore.h e metterla

nel file vettore.c. TIPI DI DATI ASTRATTI (ADT)

L’obiettivo delle ADT è quello di evidenziare le caratteristiche pregnanti di un problema, e

offuscare gli aspetti che si ritengono secondari rispetto ad un determinato obiettivo.

Ma non solo, in questo modo possiamo anche ampliare l’insieme dei modi di operare sui tipi di dati

già esistenti, con la definizione di altri operatori.

Una funzionalità di un programma è delegata ad un sottoprogramma (funzione o procedura).

Una funzione è definita e utilizzabile indipendentemente dall’algoritmo usato.

Ogni tipo di dati è definito in un dominio e su un insieme di operazioni, esempio:

n-1 n-1 –

[-2 , 2 1]

il tipo int è definito da , e le operazioni aritmetiche/logiche elementari sono

{+, -, *, / %, ==, !=, >, <, <=, >=} .

Nel linguaggio c esistono i tipi di dati primitivi, forniti direttamente dal linguaggio: int, char, float,

double;

Dati aggregati: array, strutture, enumerazioni, unioni;

Puntatori.

E’ buona norma quando si scrive un programma avere una tabella, dove scriveremo le

caratteristiche di ogni funzione senza fare riferimento ad alcun linguaggio di programmazione, in

forma molto generica, così possiamo dopo implementarlo nel linguaggio che ci piace di più.

Sintattica Semantica

Tipi di dati Nome dell’ADT Insieme dei valori

• •

tipi di dati già usati

Operatori: Nome dell’operatore Funzione associata

Per ogni operatore Tipi di dati di input e di all’operatore

• output Precondizioni:

• definiscono quando

l’operatore è applicabile

Postcondizioni:

• definiscono relazioni tra

dati di input e output

Esempio programma punto:

In questo programma utilizzeremo un tipo di dati chiamato struct.

STRUTTURE

Una struttura contiene delle dichiarazioni di variabili che non necessariamente devono essere dello

stesso tipo, a differenza degli array. Gli array infatti possono contenere più dati dello stesso tipo, e

per accedervi si utilizza l’indicizzazione array[i]. Per accedere ad una struttura invece si utilizza un

punto seguito dal nome della variabile.

Esempio:

struct punto {

float x;

float y;

};

Posso accedere agli elementi x e y della struttura semplicemente scrivendo punto.x e punto.y.

La parola che segue subito struct sarà il nome della struttura. Con il pezzo di codice appena scritto

non si allocano ancora variabili in memoria, stiamo solo definendo come sarà il tipo di struttura che

vogliamo usare, nel momento in cui dichiareremo una variabile di tipo struct punto, verranno

allocate due variabili float per quella struttura.

Ci sono due modi per dichiarare una struttura:

Possiamo definire la struttura, come fatto prima, e successivamente dichiarare una variabile, in

questo modo

struct punto {

float x;

float y;

};

int main()

{ struct punto point;

}

Oppure possiamo dichiarare una variabile in contemporanea alla definizione della struttura:

struct punto {

float x;

float y;

} punto1, punto2;

Per inizializzarla invece possiamo fare così:

struct punto {

float x;

float y;

} punto1 = {15.4, 28.7},

punto2 = {.x = 15.4, .y = 28.7};

Notiamo subito che c’è la possibilità di scrivere i numeri senza specificare la variabile, in questo

caso verranno assegnati in ordine così come sono dichiarate le variabili (punto1), oppure possiamo

specificare la variabile che deve assumere quel valore sempre con la notazione con il punto

(punto2). Sono valide le operazioni di designazione utilizzate anche per gli array. Esempio:

struct inventario {

char nome[20];

int quant:

float prezzo:

} inv1 = {.quant = 20, 20.99};

In questo caso verrà assegnato il valore 20 a quantità e 20.99 al prezzo, se le successive variabili

non sono specificate verranno inserite subito dopo quella specificata, in questo caso la stringa nome

resta invariata. Tutti i membri per i quali non si definisce un valore vengono inizializzati a 0.

struct punto {

float x;

float y;

};

int main()

{ struct punto point = {15.5, 28.7};

struct punto point2 = {.y = 28.7};

}

Le regole viste prima, quelle dell’assegnazione con il punto, valgono anche quando si dichiara point

nel main:

In point2 la x rimane invariata.

A differenza dei vettori è possibile assegnare una struttura ad un altra tramite l’operatore uguale.

Esempio:

struct punto {

float x;

float y;

};

int main()

{ struct punto point = {50.8, 24.2};

struct punto point2 = {789, 410};

point2 = point;

}

Adesso point2 sarà uguale a point, cioè le variabili x ed y varranno quanto quelle di point.

Questo stratagemma è spesso usato per copiare due array molto velocemente, visto che questa

operazione non è disponibile per gli array.

Esempio:

struct array{

int arr[5];

} element1 = {10, 20, 30, 40, 50},

element2 = {0, 0, 0, 0, 0};

int main()

{ element2 = element1;

}

Adesso i vettori di element1 e di element2 sono uguali. Verranno copiati tutti i valori di tutte le

variabili. Questa operazione non è possibile sempre, è possibile solo su tipi di strutture compatibili,

cioè lo stesso tipo di struttura.

Come per gli array però non è possibile eseguire confronti come ==, !=, > ecc, l’unico operatore

disponibile è quello dell’assegnamento.

Notiamo che per dichiarare la struttura nel main abbiamo bisogno della dicitura struct, se non

vogliamo scriverla ogni volta, possiamo utilizzare un typedef.

1° esempio 2° esempio 3° esempio

typedef struct array{ typedef struct array{ typedef struct array{

int arr[5]; int arr[5]; int arr[5];

} array; } struttura; } nome;

int main() int main() int main()

{ { {

array arr1; struttura arr1; nome arr1;

} } }

Così facendo però non potremo più dichiarare le variabili in contemporanea con la dichiarazione

della struttura, le parole evidenziate in giallo indicano il nome che useremo per creare una nuova

struttura, e NON il nome di una variabile di tipo struttura.

Il typedef sostituisce la dicitura struct array con array, struttura o nome, nel nostro caso.

E’ possibile allocare memoria per una struttura tramite malloc e calloc. Possiamo dichiarare un

puntatore e allocargli una dimensione di sizeof(struct array), oppure sizeof(array) se abbiamo

utilizzato typedef.

typedef senza typedef

typedef struct array { struct array {

int arr[5]; int arr[5];

}array; };

array *p = malloc(sizeof(array)); struct array *p = malloc(sizeof(struct array));

Se usiamo i puntatori, per accedere a un elemento dovremo fare (*p).x oppure una freccetta p -> x

Ritorniamo alla nostra tabella.

Sintattica Semantica

Nome del tipo: Punto Dominio: insieme delle coppie (ascissa,

Tipi usati: Reali ordinata) dove ascissa e ordinata sono numeri

reali

creaPunto(reale, reale) → punto creaPunto(x, y) = p

prec: true

ascissa(punto) → reale postc: p = (x, y)

ordinata(punto) → reale ascissa(p) = x

prec: true

distanza(Punto a, punto b) → reale postc: p = (x, y)

ordinata(p) = y

prec: true

• postc: p = (x, y)

distanza(p1, p2) = d

prec: true

• 2

postc: sqrt{[ascissa(p1) - ascissa(p2)] +

• 2

[ordinata(p1) - ordinata(p2)] }

In questa tabella è importante identificare quelle funzioni primarie delle quali non si può fare a

meno.

Le funzioni creaPunto, ascissa, ordinata e distanza infatti sono quelle funzioni che ci vengono

subito in mente se pensiamo a cosa possiamo fare con una coppia di punti, potremmo avere la

necessità di avere la distanza tra due punti, l’ascissa o l’ordinata di un punto e quant’altro.

La funzione creaPunto è la funzione principale, perché senza di essa non avremmo un punto con il

quale poter lavorare.

Passiamo all’implementazione del codice:

lib.h

typedef struct point *point;

point creaPunto(float x, float y);

float ascissa(point s);

float ordinata(point s);

float distanza(point p1, point p2);

lib.c

#include <stdio.h>

#include <stdlib.h>

#include <math.h>

#include "lib.h"

struct point {

float x;

float y;

};

point creaPunto(float x, float y) {

point s = malloc(sizeof(struct point));

s -> x = x;

s -> y = y;

return s;

}

float ascissa(point s) {

return s -> x;

}

float ordinata(point s) {

return s -> y;

}

float distanza(point p1, point p2) {

float dx = p1 -> x - p2 -> x;

float dy = p1 -> y - p2 -> y;

return sqrt((dx*dx)+(dy*dy));

} typedef struct point *point

Con la dichiarazione nell’header file, il tipo punto è

implementato come un puntatore alla struttura, nel file .c invece è definita l’implementazione della

struttura punto. In questo modo la struttura del punto sarà invisibile al client. Se non facessimo così

il compilatore non saprebbe quanta memoria allocare per la struttura, essendo invece punto un

puntatore, sa quanta memoria allocare.

ESERCITAZIONE:

Realizzare un programma che prende in ingresso una sequenza di punti e un numero reale d e

restituisca il numero di m coppie di punti che hanno distanza minore di d.

Abbiamo bisogno di includere una nuova funzione

lib.c

int controllo(point *punti, int n, float d) {

int i, j, cont = 0;

for (i = 0; i < n; i++)

{ for (j = i+1; j < n; j++)

{ if (distanza(punti[i], punti[j]) < d)

cont++;

}

}

return cont;

}

lib.h

int controllo(point *punti, int n, float d);

main.c

#include <stdio.h>

#include "lib.h"

int main()

{ int i, n, k;

float d, x, y;

printf("Inserire numero reale d:\n");

scanf("%f", &d);

printf("Quanti punti vuoi inserire?\n");

scanf("%d", &n);

point punti[n];

input(punti, n);

printf("Le distanze inferiori a %.2f metri sono %d\n", d, controllo(punti, n, d));

return 0;

}

Con point punti[n] stiamo dichiarando un array di strutture di lunghezza n. Abbiamo incluso lib.h

perché all’interno c’è la dichiarazione della struttura point insieme a typedef, se non la includessimo

il compilatore ci darebbe errore perché non conosce point.

ESERCIZIO:

Realizzare un programma che preda in ingresso una sequenza di punti e restituisca la distanza

massima fra le coppie di punti della sequenza.

Per questo programma abbiamo bisogno di una funzione che calcola la distanza di ogni punto e

tiene traccia della distanza più lunga man mano:

lib.c

float dist_max(point *punti, int n) {

int i, j;

float max = 0, temp;

for (i = 0; i < n; i++)

{ for (j = i+1; j < n; j++)

{ if ((temp = distanza(punti[i], punti[j])) > max)

max = temp;

}

}

return max;

}

main.c

#include <stdio.h>

#include "lib.h"

int main()

{ int i, n, k;

float d, x, y;

printf("Inserire numero reale d:\n");

scanf("%f", &d);

printf("Quanti punti vuoi inserire?\n");

scanf("%d", &n);

point punti[n];

input(punti, n);

printf("Le distanze inferiori a %.2f metri sono %d\n", d, controllo(punti, n, d));

printf("La distanza massima è: %.2f\n", dist_max(punti, n));

return 0;

}

Estendere l’ADT in modo da includere le seguenti funzionalità:

Spostamento del punto dati due numeri reali deltaX e deltaY

• Calcolo del centroide (posizione media) di un insieme

void spostaPunto(point p, float x, float y) {

p -> x += x;

p -> y += y;

}

point centroide(point *punti, int n) {

int i;

float sommaX = 0, sommaY = 0;

for (i = 0; i < n; i++)

{ sommaX += punti[i] -> x;

sommaY += punti[i] -> y;

}

return creaPunto(sommaX/n, sommaY/n);

} ANALISI

Dati di ingresso: sequenza di punti e un numero reale d

• Precondizione: n >= 2, d >= 0

Dati di uscita: intero m

• Postcondizione: m è il numero di coppie di punti p1 e p2 in s tali che

◦ distanza(p1, p2) < d

Identificatore Tipo Descrizione

s sequenza Sequenza di punti in input

n intero Numero di elementi della sequenza

d reale Distanza massima tra una coppia

m intero Numero di punti a distanza d

p1, p2 punti Punti tra cui valutare la distanza

PSEUDO-GENERICS

Questa tecnica consiste nel dichiarare una variabile void, in modo tale che possa essere utilizzata

con qualsiasi valore, sia int che char, float ecc. In fase di compilazione decideremo noi se

compilare il programma per utilizzarlo con interi, con float, con strutture o altro.

E’ possibile dichiarare un puntatore ad un tipo non specificato

void *p_void;

E poi assegnarlo al tipo desiderato

int *p_int = p_void;

char *p_char = p_void;

typedef struct studente {

char nome[20];

int matricola;

} Studente;

Studente p_studente = p_void;

In questo modo possiamo implementare algoritmi che siano funzionanti in ogni tipo di situazione

con ogni tipo di dato desiderato. Con l’ordinamento per esempio abbiamo il problema di voler

ordinare interi, stringhe o caratteri.

Utilizzeremo per lo scopo una libreria chiamata item.h creata da noi, vediamo come:

item.h

typedef void Item;

Item inputItem();

void outputItem(Item);

int cmpItem(Item, Item);

Così facendo abbiamo detto che con Item facciamo riferimento a una variabile void, nella funzione

dovremo rimpiazzare tutte le variabili dei prototipi (int, char ecc) con Item. Dovremo creare un

file .c per ogni tipo di dato, in questo caso ne faremo 3, uno per gli interi, uno per i caratteri e uno

per le strutture.

item-int.c

#include <stdio.h>

#include <stdlib.h>

#include "item.h"

Item inputItem() {

int *pt = malloc(sizeof(int));

scanf("%d", pt);

return pt;

}

void outputItem(Item it) {

int *pt = it;

printf("%d ", *pt);

}

int cmpItem(Item it1, Item it2) {

if (it1 == NULL && it2 != NULL)

return -1;

if (it1 == NULL && it2 == NULL)

return 0;

if (it1 != NULL && it2 == NULL)

return 1;

int *pt1 = it1, *pt2 = it2;

if (*pt1 < *pt2)

return -1;

else if (*pt1 == *pt2)

return 0;

else return 1;

}

main.c

#include <stdio.h>

#include "vettore.h"

#include "item.h"

int main(){

int i, n = 5;

Item arr[5];

printf("Introduci il vettore:\n");

input_array(arr, n);

selection_sort(arr, n);

printf("Vettore ordinato:\n");

output_array(arr, n);

return 0;

}

Possiamo notare che nel main l’array che verrà utilizzato è definito come Item, cioè void, tutte le

funzioni invece prendono come argomenti parametri Item. I parametri Item verranno convertiti al

tipo che serve dalla funzione, visto che stiamo facendo le funzioni per i tipi int, verranno create

delle variabili int alle quali sarà attribuito il valore della variabile Item, quando lavoreremo per i

caratteri o per le strutture utilizzeremo variabili char o struct. Le funzioni restano identiche, cambia

solo il tipo di variabile al quale viene attribuito il valore di Item, come detto prima

char

int cmpItem(Item it1, Item it2) {

char *pt1 = it1, *pt2 = it2;

return strcmp(pt1, pt2);

}

struct

int cmpItem(Item it1, Item it2) {

if (it1 == NULL && it2 != NULL)

return -1;

if (it1 == NULL && it2 == NULL)

return 0;

if (it1 != NULL && it2 == NULL)

return 1;

Studente s1 = it1, s2 = it2;

if (matricola(s1) < matricola(s2))

return -1;

else if (matricola(s1) == matricola(s2))

return 0;

else return 1;

}

float

int cmpItem(Item it1, Item it2) {

if (it1 == NULL && it2 != NULL)

return -1;

if (it1 == NULL && it2 == NULL)

return 0;

if (it1 != NULL && it2 == NULL)

return 1;

float *pt1 = it1, *pt2 = it2;

if (*pt1 < *pt2)

return -1;

else if (*pt1 == *pt2)

return 0;

else return 1;

}

Notiamo che in base al tipo, viene creata una variabile alla quale viene subito assegnato un valore e

successivamente vengono eseguite le operazioni.

Per quanto riguarda il makefile, basta farne uno con più label, in base al tipo di dato che vogliamo

utilizzare scriveremo make int, make float, make struttura ecc.

int: main.o utils.o item-int.o vettore.o

gcc main.o utils.o vettore.o item-int.o -o vettore

str: main.o utils.o item-str.o vettore.o

gcc main.o utils.o vettore.o item-str.o -o vettore

studente: main.o utils.o vettore.o item-studente.o studente.o

gcc main.o utils.o vettore.o item-studente.o studente.o -o vettore

main.o:

gcc -c main.c

utils.o:

gcc -c utils.c

item-int.o:

gcc -c item-int.c

studente.o:

gcc -c studente.c

item-str.o:

gcc -c item-str.c

item-studente.o:

gcc -c item-studente.c

vettore.o:

gcc -c vettore.c

clean:

rm -f *.o *.bin

Con make int compileremo per gli interi, con make str per le stringhe e con make studente per le

strutture di tipo studente in questo caso.

LISTE CONCATENATE

La lista è una sequenza di elementi di un determinato tipo in cui è possibile aggiungere o togliere

elementi.

Ogni elemento di una lista concatenata contiene un campo puntatore che punta alla prossima

struttura e serve da collegamento per il record successivo.

Si accede alla struttura tramite un puntatore al primo record. Come è possibile notare

dall’immagine, ogni elemento ha un puntatore all’elemento successivo, l’ultimo ha un puntatore

nullo.

Le principali differenze tra liste e array, oltre al fatto che l’array può contenere solo elementi dello

stesso tipo (tutti interi o tutti char ecc), sono:

L’array ha dimensione fissa, ma è possibile accedervi direttamente tramite l’indicizzazione;

Le liste hanno dimensione variabile, ed è più semplice aggiungere o rimuovere elementi, ma per

raggiungere un determinato elemento occorrono più iterazioni, specie se la lista è grande e

l’elemento che vogliamo si trova nel mezzo, questo perché abbiamo il puntatore solo al primo

record, da li in poi dobbiamo controllare se il puntatore al successivo (next) è quello che ci serve.

Vediamo come inserire un elemento in una lista.

AGGIUNTA IN TESTA

Il modo più semplice per aggiungere un elemento in una lista è quello di aggiungerlo in testa,

vediamo come:

Creiamo un nuovo nodo e lo facciamo puntare al primo nodo della lista, successivamente cambiamo

il puntatore al primo elemento della lista, facendolo puntare a quello appena creato.

*nodo_t è un puntatore che punta sempre al primo elemento della lista, senza di esso non potremmo

aggiungere o rimuovere elementi, per cui è importante avere un puntatore che punti sempre al primo

elemento. Il nostro si chiama *nodo_t.

Notiamo che *nodo_t punta ad un altro nodo, che a sua volta punta ad un altro nodo ecc ecc.

Nel momento in cui creiamo un nuovo nodo, abbiamo la necessità di inserirlo tra quelli che esistono

già, nello specifico vogliamo inserirlo come primo elemento della lista.

Visto che sarà il primo elemento della lista, il suo puntatore a next lo facciamo puntare a quello che

attualmente è il primo elemento, e che diventerà secondo.

Fatto ciò il primo nodo sarà quello appena creato.

A questo punto però *nodo_t punta al secondo elemento, perché non abbiamo ancora modificato il

suo valore, siccome noi vogliamo che punti sempre al primo elemento non ci resta che cambiare il

suo valore e farlo puntare al nodo appena creato.

ELIMINAZIONE IN TESTA

Il modo più semplice per eliminare un elemento da una lista è eliminarlo dalla testa, vediamo come:

Si crea un puntatore temporaneo temp e si fa puntare al record da eliminare;

Si aggiorna il puntatore al primo elemento facendolo puntare al successivo (next);

Si elimina il nodo puntato da temp per liberare la memoria;

Nell’immagine non è illustrata la creazione del puntatore temporaneo, ma è un operazione molto

semplice.

Si crea il puntatore temp che punta al primo nodo, successivamente si cambia il puntatore di

*nodo_t (che in questo caso è sempre il puntatore al primo elemento), e lo si fa puntare al secondo

elemento.

Successivamente tramite il puntatore temp è possibile eliminare il record che si voleva eliminare,

liberando la memoria con free(temp).

IMPLEMENTAZIONE IN C

Potrebbe essere utile sapere quanti record sono presenti nella lista, un modo per riuscire a saperlo

potrebbe essere quello di scansionare tutta la lista e incrementare un contatore. In alternativa

possiamo tenerne traccia man mano.

Per questo motivo utilizzeremo due strutture:

Una struttura lista, che conterrà il numero di record e il puntatore al primo elemento del

• nodo.

Una struttura node, che conterrà la variabile value e la variabile puntatore al prossimo

• elemento del nodo.

Iniziamo col creare la nostra tabella con le principali funzioni:

Sintattica Semantica

Nome del tipo: list Dominio: insieme di sequenze L=a ,…,a di tipo Item,

1 n

Tipi usati: Item, boolean L’elemento nil rappresenta la lista vuota

newList() → List NewList() → l

post: l = nil

isEmpty(List) → boolean isEmpty() → b

post: se n = nil b = true altrimenti b = false

• 1

addHead(List, Item) → List addHead(l, el) → l 1

post: l = {a , a , … a } AND l = {e, a , … , a }

• 1 2 n 1 n

1

removeHead(List) → List removeHead(l) → l

pre: l = {a , a , … a } n > 0

• 1 2 n

1

post: l = {a , a }

• 2 n

getFirst(List) → Item getFirst(List) → e

pre: l = {a , a , … , a } n > 0

• 1 2 n

post: e = a

• 1

Per prima cosa creiamo due file chiamati list.h e list.c all’interno dei quali inseriremo i prototipi e le

funzioni che useremo, e qualche typedef che può tornarci utile:

list.h

typedef struct list *List;

List newList();

List addHead(List lista);

void removeHead(List lista);

int getFirst(List lista);

int isEmpty(List lista);

Passiamo al file list.c che è un po' più lungo, per cui verrà commentato dove opportuno.

Iniziamo con l’includere tutte le librerie che ci serviranno: in item.h (che io ho in un altra cartella)

c’è la definizione di Item che abbiamo già visto, list.h è la libreria che stiamo creando ora, la

importiamo perché così possiamo utilizzare il typedef di List per creare una struttura di tipo lista.

list.c

#include <stdlib.h>

#include <stdio.h>

#include "../librerie/item.h"

#include "list.h"

struct list {

int size;

struct node *head;

};

struct node {

Item value;

struct node *next;

};

...

Definiamo le due liste che utilizzeremo. ATTENZIONE! Con il typedef abbiamo semplicemente

detto che con la dicitura List facciamo riferimento a struct list, però il compilatore non sa come è

fatta List, per cui la definiamo così sarà a conoscenza di quanta memoria dovrà allocare.

Come già detto, la struct list ci servirà per tenere conto dei record, con la variabile size, e per tenere

struct node *head

traccia del primo nodo, con la struttura .

La struttura node invece, conterrà il valore per ogni record e il puntatore al record successivo.

Notiamo che entrami i puntatori di entrambe le strutture sono di tipo struttura, nello specifico

struct node .

Andiamo avanti e vediamo come sono fatte le funzioni che abbiamo elencato prima nella tabella.

List newList(){

List new_list = malloc(sizeof(struct list));

new_list -> size = 0;

new_list -> head = NULL;

return new_list;

}

Questa funzione alloca uno spazio di memoria della grandezza di struct list, successivamente

imposta il valore di size a 0, perché stiamo creando solo la lista che conterrà i nostri nodi e non

il nodo in sé, imposterà il valore del puntatore head a NULL, per lo stesso motivo di prima.

Abbiamo creato solo la lista, non c’è ancora nessun nodo all’interno.

Vediamo ora come creare un nodo.

List addHead(List lista, Item item){

struct node *nodo = malloc(sizeof(struct node));

nodo -> value = item;

nodo -> next = lista -> head;

lista -> head = nodo;

lista -> size++;

} …

Questa funzione crea un nodo e gli alloca uno spazio di memoria di grandezza struct node,

successivamente nel suo campo item mette il valore item che è stato passato alla funzione, nel suo

campo next (il puntatore al prossimo record) mette quello che è attualmente in lista → head perché

in questo momento è ancora il primo elemento, dopo questa operazione diventerà il secondo. Nel

caso in cui sia la prima volta che crea un nodo, verrà messo nel campo next il valore NULL, perché

lista → head = NULL. Lista → head invece punterà al nodo appena creato, perché diventerà il

primo record, e come abbiamo detto dobbiamo avere sempre un puntatore al primo elemento, che

nel nostro caso si trova nella struttura lista ed è *head (lista → head). Con quest’ultima operazione

il nodo appena creato è diventato il primo. Successivamente viene incrementato il valore di size che

ci serve per tenere conto di quanti record ci sono.

Vediamo ora la funzione per rimuovere un record dalla testa.

void removeHead(List lista) {

struct node *temp = lista -> head;

lista -> head = temp -> next;

free(temp);

lista -> size--;

}

removeHead rimuove un elemento dalla testa della lista.

Crea un puntatore al primo elemento della lista, quindi a lista → head, successivamente fa puntare

lista → head a temp → next.

Con l’assegnamento temp = lista → head diciamo che l’indirizzo di memoria di temp deve essere

lista → head, cioè l’indirizzo del primo nodo, quindi se ora facciamo temp → next avremo

l’indirizzo di memoria del secondo record.

Quindi con l’assegnamento lista → head = temp → next stiamo dicendo che il secondo elemento

della lista deve diventare il primo.

Con free(temp) invece liberiamo l’area di memoria puntata da temp. Liberare la memoria è molto

importante visto che è una risorsa limitata.

Non ci resta che decrementare size con lista → size--.

Passiamo alle ultime due funzioni

Item getHead(List lista){

return lista -> head -> value;

}

int isEmpty(List lista){

return lista -> head == NULL;

}

Visto che abbiamo messo in conto la necessità di sapere di quanti record ci sono nella nostra lista,

scriviamo una funzione molto semplice che ci restituisca il numero di record che abbiamo:

int sizeList(List lista){

return lista -> size;

}

Scriviamo anche una funzione che ci stami tutti gli elementi della lista

void printList(List lista){

struct node *p;

for (p = lista -> head; p != NULL; p = p -> next)

{ outputItem(p -> value);

}

puts("");

}

Per scorrere tra i nodi, creiamo un puntatore di tipo struct node e lo facciamo puntare a

lista → head, cioè al primo nodo.

L’iterazione continua fino a che p != NULL, perché il puntatore dell’ultimo nodo sarà NULL.

Il valore che dovrà assumere il puntatore sarà p = p → next, cioè il puntatore al nodo successivo,

che appunto se è l’ultimo nodo allora p → next = NULL. Per stampare utilizziamo la funzione

outputItem(Item item) presente in item.h, la richiamiamo perché la variabile p → value è di tipo

Item (cioè void) e quindi deve essere convertita in un tipo, in questo caso in int, prima di essere

stampata.

Puts(""), è una funzione che stampa una stringa con lo \n alla fine, l’ho usata solo per lo \n.

Non dimentichiamo di aggiungere i prototipi delle funzioni nell’header file.

list.h

typedef struct list *List;

List newList();

List addHead(List lista);

void removeHead(List lista);

int getFirst(List lista);

int isEmpty(List lista);

void printList(List lista);

int sizeList(List lista);

Abbiamo utilizzato il tipo Item perché vogliamo estendere il programma a ogni tipo di dato (int,

char ecc), quindi dobbiamo scrivere un make file che ci renda possibile la compilazione del

programma per ogni tipo di dato.

make file

int: main.o lib-int.o item-int.o

gcc main.o lib-int.o item-int.o -o main

str: main.o lib-str.o item-str.o

gcc main.o lib-str.o item-str.o -o main

main.o:

gcc -c main.c

lib-int.o:

gcc -c lib-int.c

lib-str.o:

gcc -c lib-str.c

item-int.o:

gcc -c ../librerie/item-int.c

item-str.o:

gcc -c ../librerie/item-str.c

clean:

rm -f *.o *.bin

Per ora abbiamo visto solo l’implementazione del programma con gli interi.

Per chi non ha mai utilizzato le liste, gli header file e il tipo Item, può risultare complicato

comprendere il perché dei loro utilizzi e soprattutto il loro funzionamento, per cui ora vedremo il

loro funzionamento con calma, all’inizio escludendo il tipo Item e riaggiungendolo dopo.

Prendiamo in considerazione la funzione newList(). Cos’è newList? A cosa serve?

La funzione newList serve per creare una nuova lista (vuota). Bisogna fare distinzione tra la lista e i

nodi della lista, i nodi sono gli elementi che compongono la lista, quindi quando creiamo una lista

all’inizio non avremo nessun nodo al suo interno, per aggiungere nodi (cioè elementi) utilizziamo la

funzione addHead() (perché gli elementi della lista sono nodi, e addHead() aggiunge un nodo in

testa alla lista) oppure altre funzioni che vedremo, come addItem() che aggiunge un elemento in un

punto che vogliamo.

La funzione newList() non contiene il tipo Item. Vediamo come funziona.

Questa funzione si occupa solo di allocare uno spazio di memoria della dimensione di struct list e

di impostare il campo size a 0 e il campo head a NULL, anche se di default i campi di una struttura

vengono inizializzati a 0. Ci restituisce l’indirizzo di memoria della lista. Il campo head è NULL

perché non ci sono ancora nodi nella lista.

struct list { List newList(){

int size; List new_list = malloc(sizeof(struct list));

struct node *head; new_list -> size = 0;

}; new_list -> head = NULL;

return new_list;

struct node { }

int value;

struct node *next;

};

Ora che abbiamo creato la lista vediamo come creare un nodo.

struct list { List addHead(List lista, int item) {

int size; struct node *nodo = malloc(sizeof(struct node));

struct node *head; nodo -> value = item;

}; nodo -> next = lista -> head;

lista -> head = nodo;

struct node { lista -> size++;

int value; }

struct node *next;

};

Per creare il nodo utilizzeremo la funzione addHead(). Di cosa si occupa la addHead()?

Deve allocare uno spazio di memoria della grandezza di un nodo, successivamente deve riempire il

campo value e il campo struct, che sono gli unici due campi che possiede. Nel campo value

dobbiamo impostare il valore di item che passiamo alla addHead(), invece il campo next

dobbiamo farlo puntare al prossimo nodo (cioè al prossimo elemento della lista). Visto che la

funzione aggiunge dalla testa, significa che l’ultimo elemento aggiunto sarà il primo.

Con

struct node *nodo = malloc(sizeof(struct node));

stiamo dichiarando una variabile di tipo struct node che si chiama nodo.

Allocare spazio per un nodo con la malloc, significa dire al compilatore che per quella struttura ci

serve una zona di memoria abbastanza grande da poter contenere un intero e un puntatore di tipo

node.

Con

nodo -> value = item;

stiamo assegnando alla variabile value del nodo che abbiamo appena creato, il valore value che

abbiamo passato alla funzione.

Con

nodo -> next = lista -> head;

Stiamo dicendo che il puntatore al prossimo elemento del nodo appena creato (next) deve puntare al

primo nodo, perché come abbiamo già detto prima gli elementi inseriti per ultimi diventano primi,

per cui il primo elemento dovrà diventare il secondo. Con questa istruzione abbiamo fatto il primo

passo, abbiamo detto che l’elemento successivo a questo nodo è quello che attualmente è il primo.

Non ci rimane far diventare il nodo appena creato primo elemento della lista (primo nodo), lo

facciamo così:

lista -> head = nodo;

Con

lista -> size++;

Aumentiamo la taglia della lista. La variabile size che si trova nella lista ci serve per sapere

velocemente quanti elementi ci sono nella lista.

Proviamo ora a riscrivere la stessa funzione utilizzando gli Item.

struct list { List addHead(List lista, Item item) {

int size; struct node *nodo = malloc(sizeof(struct node));

struct node *head; nodo -> value = item;

}; nodo -> next = lista -> head;

lista -> head = nodo;

struct node { lista -> size++;

Item value; }

struct node *next;

};

La funzione rimane praticamente identica in questo caso, perché la variabile value del nodo è di tipo

Item, e noi alla addHead passiamo un tipo Item, che è esattamente lo stesso tipo, quindi non ci sono

cambiamenti. Quello che cambia è la chiamata a funzione.

Se prima chiamavamo la funzione in questo modo:

addHead(lista, 10);

Ora non possiamo più farlo, perché 10 non è di tipo Item ma di tipo intero.

Possiamo convertire un intero in Item in questo modo:

int *p = malloc(sizeof(int));

*p = 125;

Item x = p;

addHead(lista, x);

Dobbiamo dichiarare un puntatore di tipo intero, perché un puntatore? Perché il tipo Item non è

altro che un puntatore a void (typedef void *Item). L’indirizzo di memoria di un puntatore a void

può essere assegnato a qualunque puntatore, e l’indirizzo di memoria di un qualunque puntatore può

essere assegnato a un puntatore a void.

Quindi dichiariamo un puntatore a intero e gli allochiamo della memoria, perché? Perché altrimenti

non potremmo sapere a quale locazione di memoria sta puntando, se non lo facessimo potrebbe

puntare a una variabile già in uso nel nostro programma e modificarne il valore senza che noi lo

volessimo, oppure peggio puntare a una variabile di sistema mandare il crash il sistema operativo

(anche se ormai quasi tutti i sistemi operativi hanno protezioni sulle variabili di sistema).

Dopo aver allocato il puntatore, dobbiamo assegnargli il valore che vogliamo inserire nella lista (in

questo caso scegliamo un valore fisso perché stiamo facendo una prova).

Una volta assegnato anche il valore abbiamo il puntatore a intero e il puntatore a void, come già

detto prima l’indirizzo di memoria di un puntatore a void può essere assegnato a qualunque

puntatore e viceversa.

Assegniamo l’indirizzo del puntatore int all’Item e a questo punto siamo pronti per chiamare la

funzione addHead() e passarle l’Item per l’aggiunta.

Per evitare ogni volta di fare questa conversione ci creiamo una funzione, alla quale non passiamo

nessun parametro. Cosa farà questa funzione? Scansionerà l’intero (o una stringa, o una struttura

addirittura, vedremo più avanti come scrivendo solo differenti funzioni per l’input a seconda del

fatto che il dato che ci serve sia intero, una stringa, una struttura ecc potremmo utilizzare il

programma con ogni tipo di dato), lo assegna in un puntatore a intero (nel nostro caso) e lo

restituisce. Il valore che ci verrà restituito lo assegneremo a un tipo Item.

Questa funzione in realtà l’abbiamo già creata un po' di tempo fa, ora però la vediamo nel dettaglio.

Item inputItem() {

int *pt = malloc(sizeof(int));

scanf("%d", pt);

return pt;

}

Questa funzione fa la stessa operazione che abbiamo fatto prima:

dichiara un puntatore a intero e lo alloca, successivamente scansiona da tastiera un intero e lo

assegna al puntatore, e lo restituisce.

Vi ricordo che l’indirizzo di memoria di un puntatore a intero può essere assegnato tranquillamente

a un tipo void, quindi queste due righe di codice sono corrette:

Item it = inputItem();

addHead(lista, it);

Se volessimo aggiungere 5 elementi alla lista (quindi 5 nodi) potremmo fare un ciclo

for (i = 0; i < 5; i++)

{ Item it = inputItem();

addHead(lista, it);

}

La funzione outputItem() è molto importante. Per via dell’information hiding abbiamo scritto le

definizioni delle strutture in degli header file, per cui dal main non possiamo stampare un elemento

facendo

printf(“%d\n”, nodo -> value);

perché il main non sa cosa sia nodo, non lo conosce, quindi per poterlo stampare abbiamo bisogno

di una funzione che prende in input l’Item e lo stampa:

void outputItem(Item it) {

int *pt = it;

printf("%d ", *pt);

}

Questa funzione per poter essere utilizzata però ha bisogno di un Item, che comunque dal main non

riusciamo a passargli per lo stesso motivo detto prima. Non possiamo passare ad outputItem()

lista -> head perché non sa che cos’è, non lo conosce.

Perciò ci serve un altra funzione che ci stampi la lista:

void printList(List lista){

struct node *p;

for (p = lista -> head; p != NULL; p = p -> next)

{ outputItem(p -> value);

}

}

senza la funzione outputItem() avremmo dovuto fare

void printList(List lista){

struct node *p;

for (p = lista -> head; p != NULL; p = p -> next)

{ int *pt = malloc(sizeof(int));

pt = p -> value;

printf("%d", *pt);

}

}

Senza il tipo Item avremmo dovuto fare

void printList(List lista){

struct node *p;

for (p = lista -> head; p != NULL; p = p -> next)

{ printf("%d", p -> value);

}

}

In questo caso p -> value ci è consentito, perché la funzione si trova nello stesso file dove è scritta

la definizione della struttura. Notate che la variabile value che si trova dentro node non è Item ma è

int (abbiamo ipotizzato che il tipo Item non esistesse), per questo motivo abbiamo potuto stamparla

come intero con il segnaposto %d.

La cosa positiva di avere più header è quella di poter apportare modifiche al codice senza che

l’utente se ne accorga, potremmo cambiare l’algoritmo di un solo codice e l’utente non lo saprebbe

nemmeno, perché il programma farebbe sempre quello per cui è stato progettato.

ALTRI OPERATORI

Vediamo ora come estendere il nostro ADT con altri tipi, in particolare creeremo una nuova

funzione chiamata sortList().

Sintattica Semantica

Nome del tipo: List Dominio: insieme di nodi non ordinati di tipo

Tipi usati: Item Item

sortList() → List sortList → lista

prec: deve esistere almeno un elemento

• postc: lista ordinata

Vediamo la funzione come è fatta.

void sortList(List lista){

struct node *p = lista -> head, *min;

for (; p != NULL; p = p -> next)

{ min = minimo(p);

swapItems(min, p);

}

}

Per lo scopo è stata scritta la funzione swapItems() identica alla funzione swap(), con la sola

differenza che questa funzione con gli Item, scambia gli indirizzi di memoria di due Item.

Vediamo come è fatta la funzione swapItems():

void swapItems(struct node *it, struct node *it2){

Item temp = it -> value;

it -> value = it2 -> value;

it2 -> value = temp;

} ESERCIZIO PLAYLIST

Creare una struttura playlist composta da una variabile nome e una lista di canzoni (struttura).

Le canzoni sono caratterizzate dal titolo, dal nome del cantante o gruppo musicale e dalla durata

espressa in secondi.

Inserire una canzone in testa ad una playlist;

• Rimuovere una canzone dalla testa di una playlist;

• Ordinare una playlist in base al titolo delle canzoni;

Sviluppare un programma che istanzia e popola una nuova playlist chiamata Rock con 5 pezzi a

scelta dell’utente. Successivamente stampa la playlist con le canzoni ordinate.

ADT PLAYLIST

Sintattica Semantica

Nome del tipo: playlist Dominio: insieme delle coppie <name, song>

Tipi usati: Song, String, Boolean name è una stringa, song una lista di song

newPlaylist() -> Playlist newPlaylist() -> pl

postc: pl = <name, nill>

addSong() -> Playlist addSong() -> pl’

postc: pl= < a , a , … , a > e

• 1 2 n

pl’ = <s, a , a , … , a >

1 2 n

removeSong() -> Playlist removeSong() -> pl’

prec: pl = <a , a , … , a > n > 0

• 1 2 n

postc: pl’ = <a , … , a >

• 2 n

sortSong() -> Playlist sortSong() -> pl’

prec: pl = <a , a , … , a > n > 0

• 1 2 n

postc: pl’ = <a , a , … , a >

• 1 2 n

titolo(a ) < titolo(a ) i : 1 <= i <= n

i i+1

Avremo bisogno di due nuovi header, playlist.h e song.h. Non è obbligatorio farli, però è

consigliabile.

playlist.h song.h

#include "song.h" typedef struct song *Song;

typedef struct playlist *Playlist; Song newSong(char *titolo, char *autore, int durata);

Playlist newPlaylist(char *name); char *titolo(Song);

void addSong(Playlist, Song); char *autore(Song);

void removeSong(Playlist); int durata(Song);

void sortPlaylist(Playlist);

void printPlaylist(Playlist);

In playlist.h abbiamo incluso song.h perché c’è addSong() che utilizza la struttura Song che è

definita con il typedef dentro song.h.

playlist.c

#include <string.h>

#include <stdlib.h>

#include <stdio.h>

#include "../librerie/list.h"

#include "song.h"

#include "playlist.h"

struct {

char *nome;

List songs;

};

Questa funzione non fa altro che creare una playlist, analogamente a come fatto per newList().

La playlist contiene una lista, quindi nel momento in cui creiamo la playlist, verrà creata anche la

lista di canzoni, che per il momento sarà vuota, ma abbiamo già una funzione che lo fa, ovvero

newList().

Playlist newPlaylist(char *name){

Playlist new_playlist = malloc(sizeof(struct playlist));

new_playlist -> nome = strdup(name);

new_playlist -> songs = newList();

}

Per aggiungere una canzone ci serviamo di addSong che abbiamo già creato. Aggiungere una

canzone vuol dire aggiungere un elemento alla lista, ma abbiamo già scritto una funzione che

aggiunge un elemento a una lista, dobbiamo solo passarle la lista e l’Item da aggiungere.

void addSong(Playlist playlist, Song song){

addHead(playlist -> songs, song);

}

Stessa cosa valer per la rimozione di una canzone.

void removeSong(Playlist playlist){

removeHead(playlist -> songs);

}

Anche per l’ordinamento abbiamo già una funzione.

void sortPlaylist(Playlist playlist){

sortList(temp -> songs);

}

Per stampare le canzoni:

void printPlaylist(Playlist playlist){

printf("Playlist: %s\n", playlist -> nome);

printList(playlist -> songs);

}

Fin qui nulla di complicato, abbiamo solo creato delle funzioni che utilizzano altre funzioni che

abbiamo già creato. Ora vediamo il file song.c.

song.c

#include <stdlib.h>

#include <string.h>

#include "song.h"

struct song {

char *titolo;

char *autore;

int durata;

};

La seguente funzione serve per creare una Song. La struttura song ha un titolo, un autore e una

durata, quindi la chiameremo passandole questi tre parametri, e lei li metterà al posto giusto.

Song newSong(char *titolo, char *autore, int durata){

struct song *new_song = malloc(sizeof(struct song));

new_song -> titolo = strdup(titolo);

new_song -> autore = strdup(autore);

new_song -> durata = durata;

return new_song;

}

Abbiamo poi bisogno di tre funzioni, una che ci restituisce il titolo, una che ci restituisce l’autore e

una che ci restituisce la durata.

Per il titolo:

char *titolo(Song song){

char *t = malloc(sizeof(char) * (strlen(song -> titolo) +1));

strcpy(t, song -> titolo);

return t;

}

Per l’autore:

char *autore(Song song){

char *t = malloc(sizeof(char) * (strlen(song -> autore) +1));

strcpy(t, song -> autore);

return t;

}

Per la durata:

int durata (Song song){

return song -> durata;

}

Notiamo che per il titolo e per l’autore restituiamo un puntatore copia. In questo modo impediamo

all’utente di modificare il valore.

Se restituissimo direttamente l’indirizzo di memoria del titolo o dell’autore, sarebbe facilmente

modificabile e noi non vogliamo che questo accada.

Ci resta da scrivere solo il main e item-song, che farà funzionare il programma con le strutture.

#include <stdio.h>

#include "../librerie/playlist.h"

#include "../librerie/song.h"

#include "../librerie/item.h"

int main()

{ char nomePlaylist[100];

int i = 5;

printf("Nome playlist: ");

scanf("%[^\n]", nomePlaylist);

getchar();

Playlist my_playlist = newPlaylist(nomePlaylist);

for (i = 0; i < 5; i++)

{ printf("Canzone %d\n", i+1);

Song new_song = inputItem();

addSong(my_playlist, new_song);

puts("");

}

sortPlaylist(my_playlist);

printPlaylist(my_playlist);

return 0;

}

item-song ci permette di utilizzare il programma con le strutture, perché fin’ora ipotizzavamo che i

dati fossero interi, quindi il file item.c era scritto in modo tale da trattare i dati come interi e

stamparli come interi.

Ora questo file dobbiamo riscriverlo in modo tale che possa trattare i dati come struttura song.

item-song.c

#include <stdio.h>

#include <string.h>

#include <stdlib.h>

#include "item.h"

#include "song.h"

Item inputItem() {

char titolo[20], autore[20];

int durata;

printf("Titolo: ");

scanf("%[^\n]", titolo);

getchar();

printf("Autore: ");

scanf("%[^\n]", autore);

getchar();

printf("Durata: ");

scanf("%d", &durata);

getchar();

return newSong(titolo, autore, durata);

}

void outputItem(Item it) {

Song temp = it;

printf("%s %s (%d secondi)\n", titolo(it), autore(it), durata(it));

}

int cmpItem(Item it1, Item it2) {

Song s = it1, s2 = it2;

return strcmp(titolo(s), titolo(s2));

}

La difficoltà in questo esercizio sta nell’utilizzare le librerie, ci sono molte funzioni annidate, ma se

si segue con calma il percorso che fanno si riesce a capire il meccanismo.

Per esempio inputItem() chiede il titolo, l’autore e la durata, dopodichè chiama la newSong() che

crea una nuova struttura di tipo song e restituisce l’indirizzo di memoria alla inputItem(), che a sua

volta lo restituisce a chi l’aveva chiamata. Nel main veniva chiamata cosi

Song new_song = inputItem();

quindi l’indirizzo di memoria viene restituito a new_song.

Ora possiamo utilizzare addSong() per inserire la canzone. Abbiamo già visto che la addSong()

chiama a sua volta la addHead(), perché aggiungere una canzone significa aggiungere una lista,

perché la struttura Song è di tipo List. A questo punto il giro è terminato e la canzone è stata

aggiunta. Questo meccanismo può sembrare confuso, specialmente se non si è mai avuto a che fare

con questa tipologia di programmi, ma una volta capito il meccanismo bisogna solo applicarlo.

Ricapitolando ci sono più funzioni che richiamano altre funzioni. Lo scopo è quello di scrivere

quanto meno codice possibile nel main, quindi mettiamola così: usando inputItem() rendiamo

generico il programma e contemporaneamente ci mettiamo eventuali printf che informano l’utente

del tipo di input che si vuole, a questo punto visto che abbiamo già l’input, chiamiamo la funzione

che utilizza quell’input (nel nostro caso che crea la canzone) e restituiamo direttamente il valore di

questa funzione, che in questo caso è un indirizzo di memoria di una struttura. Bisogna sempre

ricordare che inputItem() restituisce un Item, e che sarà quindi necessario creare una variabile di

tipo Item che accoglierà l’indirizzo di memoria “trasformato” in Item. A questo punto possiamo

chiamare la addHead().

Se in futuro avremo la necessità di modificare qualche funzione potremmo farlo senza toccare il

main, inoltre il nostro codice sarà invisibile all’utente che non potrà vedere come è composta la

struttura e non potrà modificarla.

OPERATORI AGGIUNTIVI (PROGRAMMA LIST)

Proviamo ora ad aggiungere altri operatori aggiuntivi che potrebbero esserci utili come la ricerca, la

rimozione tramite Item, la rimozione tramite posizione, l’inserimento tramite posizione, il reverse,

l’inserimento dalla coda e la rimozione dalla coda.

Iniziamo col definire l’ADT sotto forma di tabella generale:

Sintattica Semantica

Nome del tipo: List Dominio: Insieme di sequenze l <a , … , a > di ti po Item l’elemento

1 n

Tipi usati: int, List, boolean nill rappresenta la lista vuota

searchItem(List, Item) → int searchItem(List, Item) → pos

postc: se Item è contenuto pos = posizione di Item

• pos = -1 altrimenti.

removeITem(List, Item) → List removeItem(List, Item) → List’

prec: List’ = <a , a , … , a > n > 0

• 1 2 n

postc: List’ = <a , … , a >

• 2 n

removePos(List, pos) → List removePos(List, pos) → List’

prec: List’ = <a , a , … , a > n > 0 & 0 <= pos <= size(List)

• 1 2 n

postc: List’ = <a , … , a >

• 2 n

insertItem(List, Item, int) → List insertItem(List, Item, pos) → List

prec: l’ = <a , a , … , a > n > 0 & pos 0 <= pos <= size(List)

• 1 2 n

postc: l’ = <a , a , a , … , a >

• 1 2 <pos> n

reverse(List) → List reverse(List) → List

postc: l = <a , a , … , a > & l’ = <a , … , a a >

• 1 2 n n 2, 1

addTail(List) → List addTail(List) → List

postc: l’ = <a , a , … , a , a >

• 1 2 n <pos>

removeTail(List) → List removeTail(List) → List

prec: l’ = <a , a , … , a a > n > 0

• 1 2 n-1, n

postc: l’ = <a , a , … , a >

• 1 2 n-1

Vediamo ora come implementarle, per semplicità vedremo direttamente le funzioni, non scriveremo

l’implementazione nell’header file.

Item searchItem(List lista, Item item, int *pos){

struct node *p;

*pos = 0;

for (p = lista -> head; p; (*pos)++, p = p -> next)

{ if (cmpItem(p -> value, item) == 0)

return p -> value;

}

*pos =- 1;

return NULL;

}

Notiamo che questa funzione restituisce un Item mentre avevamo detto che restituiva in intero, cioè

la posizione dell’elemento. In realtà la posizione dell’elemento viene passata come puntatore nei

parametri e incrementa ad ogni ciclo, quando trova l’elemento restituisce l’elemento e

contemporaneamente pos sarà uguale alla posizione in cui si trova l’elemento, se invece non trova

nulla restituisce NULL, e imposta pos a -1.

Prima di scrivere l’algoritmo per l’aggiunta da una posizione, vediamo come funziona

graficamente.

int insertItem(List lista, Item item, int pos){

if (pos == 0)

{ addHead(lista, item);

return 1;

}

if (pos > sizeList(lista))

return 0;

struct node *p;

int i;

for (p = lista -> head, i = 0; p; i++, p = p -> next)

{ if (i == pos-1)

{ struct node *new = malloc(sizeof(struct node));

new -> next = p -> next;

p -> next = new;

new -> value = item;

lista -> size++;

return 1;

}

}

return 0;

}

Questi due controlli

if (pos == 0)

{ addHead(lista, item);

return 1;

}

if (pos > sizeList(lista))

return 0;

Servono per i casi particolari.

Il primo controllo controlla che la grandezza della lista non sia minore della posizione inserita

dall’utente, perché se così fosse allora non sarebbe possibile inserire l’elemento in quella posizione.

Il secondo invece controlla se la posizione inserita dall’utente è uguale a 0, perché se così fosse

allora si sta facendo un assegnamento in testa e quindi chiamiamo la addHead().

Vediamo ora cosa succede graficamente per la rimozione dal centro

Item removeItem(List lista, Item item){

if (isEmpty(lista)){

fprintf(stderr, "Lista vuota\n");

return NULL;

}

struct node *curr, *prev;

Item removed;

for (curr = lista -> head, prev = NULL; curr; prev = curr, curr = curr -> next)

{ if (cmpItem(curr -> value, item) == 0)

{ if (curr == lista -> head)

return removeHead(lista);

else

{ removed = curr -> value;

prev -> next = curr -> next;

free(curr);

lista -> size--;

return removed;

}

}

}

return NULL;

}

Questa funzione ha come controllo

if (isEmpty(lista)){

fprintf(stderr, "Lista vuota\n");

return NULL;

}

Perché per rimuovere un elemento da una lista deve esserci, Quindi se isEmpty() restituisce uno,

significa che la lista è vuota e viene eseguito il codice all’interno. Il codice per la rimozione dalla

testa lo abbiamo già fatto quindi lo riutilizzeremo, quello per la rimozione da altre posizione è

praticamente identico a quello della rimozione dalla testa.

Reverse:

void reverseList(List lista){

struct node *p, *prev, = NULL, *temp;

for (p = lista -> head; p; prev = p, p = temp)

{ temp = p -> next;

p -> next = prev;

}

lista -> head = prev;

}

Questa funzione scambia tutti i puntatori della struttura in modo che risulti inversa. Fa puntare il

nodo al suo predecessore (reperibile tramite prev), poi reimposta la head e imposta il next del primo

nodo, che poi diventerà ultimo, uguale a NULL.

Un

alternativa a questa funzione di reverse, potrebbe essere quella di creare una struttura e di clonarla

aggiungendo dalla head, in questo modo avremo l’effetto desiderato, ma creeremmo una nuova

lista, una lista clone, che non è esattamente la stessa cosa del reverse. Certo potremmo assegnare

alla lista originale l’indirizzo della lista reverse ottenuta, ma sarebbe un operazione in più da

compiere. Di seguito è riportato il codice per questa funzione, ma è bene utilizzare quello visto

sopra.

void reverseList(List lista){

List reverse = newList();

struct node *p;

for (p = lista -> head; p; p = p -> next)

{ addHead(reverse, p -> value);

}

printList(reverse);

}

Questa funzione in realtà stampa la lista inversa, se volessimo ottenere l’indirizzo di memoria della

nuova lista basterebbe fare return reverse e cambiare il tipo di elemento restituito dalla funzione da

void a List.

Per quanto riguarda la rimozione di un elemento da una posizione

Item removePos(List lista, int pos){

if (isEmpty(lista))

{ fprintf(stderr, "Lista vuota\n");

return NULL;

}

if (pos == 0)

return removeHead(lista);

struct node *curr = lista -> head, *prev = NULL;

Item removed;

int i;

for (i = 0; curr && i <= pos; prev = curr, i++, curr = curr -> next)

{ if (pos == i)

{ removed = curr -> value;

prev -> next = curr -> next;

free(curr);

return removed;

}

}

return NULL;

}

E’ molto simile a removeItem(), abbiamo scambiato addHead() con removeHead() e abbiamo

messo l’algoritmo per la rimozione anzicchè quello per l’aggiunta nell’if.

Le funzioni per l’aggiunta e la rimozione dalla coda sono molto simili a quelle per la testa.

Ci sono due modi per farlo, possiamo scorrere tutta la lista dalla head fino al NULL, oppure

possiamo aggiungere nella struttura List il puntatore all’ultimo elemento.

struct node *tale;

Se inseriamo il puntatore alla coda bisogna ricordarsi di fare bene l’assegnamento all’ultimo

elemento quando si aggiunge dalla testa, dal centro o dalla coda e anche quando si rimuove dalla

testa, dal centro o dalla coda.

Siccome noi abbiamo nella struttura la size della stessa, utilizzeremo la funzione sizeList() insieme

alla funzione insertItem() per aggiungere o rimuovere un elemento nella coda di una lista.

List addTail(List lista, Item item){

return insertItem(lista, item, sizeList(lista));

}

Per rimuovere invece

List removeTail(List lista){

if (removePos(lista, sizeList(lista)-1))

return 1;

else return 0;

}

Per la rimozione utilizziamo sizeList(lista)-1 perché la size della lista inizia a contare da 1, mentre

la funzione removePos() inizia a contare le posizioni dallo 0.

Se volessimo scorrere tutta la lista per l’aggiunta in coda dovremmo fare così:

List addTale(List lista, Item item){

if (isEmpty(lista))

{ addHead(lista, item);

}

else

{ struct node *p;

for (p = lista -> head; p; p = p -> next)

{ if (p -> next == NULL)

{ struct node *new = malloc(sizeof(struct node));

new -> value = item;

p -> next = new;

new -> next = NULL;

lista -> size++;

break;

}

}

}

}

Se invece volessimo rimuovere dalla coda scorrendo tutta la lista:

List removeTale(List lista){

if (!isEmpty(lista))

{ struct node *p;

for (p = lista -> head; p; p = p -> next)

{ if (p -> next -> next == NULL)

{ free(p -> next -> next);

p -> next = NULL;

break;

}

}

}

} CLONARE UNA LISTA

In certi casi abbiamo la necessità di clonare una lista, e possiamo farlo in diversi modi, possiamo

copiare solo la lista, senza i nodi, ma in questo modo se viene cambiato l’ordine delle strutture

cambierebbe anche nella copia.

Possiamo scegliere di clonare sia la lista che i nodi (assegnando ai nodi della lista copia l’indirizzo

dei nodi della lista originale), ma in questo modo se venisse modificato il valore di un elemento,

verrebbe modificato anche nella copia.

Oppure possiamo copiare tutto, la lista, i nodi, e gli Item al suo interno.

Per cui scriviamo una funzione chiamata cloneList() che si occupa di copiare una lista e ci

restituisce il puntatore alla lista copiata.

Visto che dobbiamo copiare l’item, e non sappiamo l’item che tipo è, abbiamo bisogno di una

funzione in item.h che copia l’item, e sceglieremo il file adatto al tipo di dato utilizzato come

abbiamo già fatto in precedenza.

Item cloneItem(Item item){

int *pt = item;

return pt;

}

List cloneList(List lista){

List clone = newList();

struct node *p;

for (p = lista -> head; p; p = p -> next)

{ Item item = cloneItem(p -> value);

addTail(clone, item);

}

return clone;

}

Così facendo viene creata una copia dell’item e ci viene restituita. Con gli interi si vede poco

l’utilità di creare una funzione apposta che clona l’item, perciò ora faremo un esempio con una

struttura di tipo Studente.

La struttura Studente, ha al suo interno il campo nome e il campo matricola, quindi la nostra

funzione dovrà creare una struttura Studente, copiare il contenuto della struttura originale contenuta

nel nodo della lista, e restituirci l’indirizzo di memoria che poi verrà aggiunto alla lista clone con

una addTail(), usiamo addTail() perché se aggiungessimo gli elementi dalla testa otterremmo la

lista inversa.

Item cloneItem(Item item){

Studente s = item;

return creaStudente(nome(s), matricola(s));

}

In questa funzione la struttura Studente viene utilizzata come “appoggio”, ci serve solo per passare

come parametri a creaStudente() il nome e la matricola. La funzione creaStudente() sappiamo già

come funziona, le diamo un nome e una matricola e lei alloca lo spazio necessario per creare uno

studente, successivamente assegna il nome e la matricola e ci restituisce l’indirizzo di memoria

della struttura creata. Questa nuova struttura verrà restituita nella funzione cloneList() creando un

altra lista indipendente da quella originale, perché gli indirizzi di memoria non sono uguali.

Se invece della funzione cloneItem() avessimo fatto un normale assegnamento con gli operatori ->

avremmo assegnato l’indirizzo di memoria della struttura originale a quella clone, quindi

modificando un elemento nella struttura originale lo avremmo modificato anche in quella clone e

viceversa.

Da notare che la funzione cloneList() resta uguale, in fase di compilazione sceglieremo il file item

adatto al tipo di dati che vogliamo utilizzare.

ESERCIZIO LIBRETTO

Creare un programma per la gestione di libretti universitari degli studenti.

Il programma dovrà consentire di aggiungere e ricercare esami.

Ogni libretto tiene traccia del nome, del cognome e della matricola dello studente e gli esami

sostenuti.

Ogni esame tiene traccia del nome dell’esame, della data e del voto.

Dobbiamo creare una ADT libretto, che contiene i campi nome e matricola, e un ADT esame che

contiene i campi nome, data e voto. Possiamo scegliere di avere il nome e il cognome in due array

diversi o nello stesso, in questo caso li avremo nello stesso array. Utilizzeremo le liste per svolgere

le operazioni di aggiunta e di ricerca. Iniziamo col definire la tabella:

Sintattica Semantica

Nome del tipo: libretto Insieme delle coppie <nome, matricola> di tipo

Tipi usati: Stringa, intero, List string, int

newLibretto() → Libretto newLibretto() → l

postc: l = <nome, matricola>

nome(libretto) → string nome(libretto) → n

postc: n = nome studente

matricola(libretto) → int matricola(libretto) → m

postc: m = matricola studente

addEsame(Libretto, Esame) → int addEsame(Libretto, Esame) → i ∃

postc: 0 ≤ i ≤ sizeList se Esame,

• i = NULL altrimenti

printLibretto(Libretto) → void printLibretto(Libretto) → void

postc: stampa di tutti gli esami

Ecco come si presenta la struttura libretto

struct libretto {

char *nome;

int matricola;

List lista;

}

Le funzioni per questo ADT sono molto semplici

Libretto newLibretto(char *nome, int matricola){

Libretto new_libretto = malloc(sizeof(struct libretto));

new_libretto -> nome = strdup(nome);

new_libretto -> matricola = matricola;

new_libretto -> lista = newList();

return new_libretto;

}

char *nome(Libretto libretto){

char *nome = strdup(libretto -> nome);

return nome;

}

int matricola(Libretto libretto){

return libretto -> matricola;

}

int addEsame(Libretto libretto, Esame esame){

addTail(libretto -> lista, esame);

}

void printLibretto(Libretto libretto){

printList(libretto -> lista);

}

Nella funzione nome() restituiamo l’indirizzo di memoria di una copia del nome, in questo modo

l’utente non può modificare il nome.

La struttura libretto, contiene il nome, la matricola e un puntatore a una struttura lista. Quella

struttura lista è la lista di tutti gli esami. Gli esami non sono altro che nodi della lista. Il campo item

di ogni nodo è una struttura esame.

Come possiamo vedere ci appoggiamo sempre alle dure strutture List e Node. Dobbiamo vedere

l’esame come un nodo.

Detto questo passiamo alla creazione della tabella esame

Sintattica Semantica

Nome del tipo: Esame Insieme delle triple <materia, data, voto> di tipo

Tipi usati: Stringa, intero stringa, data e intero

newEsame() → Esame newEsame() → e

prec: 18 ≤ 0 ≤ 31

• postc: e = <nome, data, voto>

searchEsame(Libretto, materia) → Esame searchEsame(Libretto, Esame) → e ∃

postc: e = <materia, data, voto> se

• esame, e = NULL altrimenti

materia(Esame) → string materia(Esame) → m

postc: m = materia

data(Esame) → string data(Esame) → d

postc: d = data

voto(Esame) → int voto(Esame) → v

postc: v = voto

Vediamo come implementare queste funzioni:

Esame newEsame(char *materia, char *data, int voto){

struct esame *new_esame = malloc(sizeof(struct esame));

new_esame -> materia = strdup(materia);

new_esame -> data = strdup(data);

new_esame -> voto = voto;

return new_esame;

}

Esame searchEsame(Libretto libretto, char *materia){

int pos;

Item mat = materia;

return searchList(libretto -> lista, mat, &pos);

}

char *materia(Esame esame){

char *materia = strdup(esame -> materia);

return materia;

}

char *data(Esame esame){

char *data = strdup(esame -> data);

return data;

}

int voto(Esame esame){

return esame -> voto;

}

Queste funzioni sono molto semplici, abbiamo solamente richiamato adeguatamente le funzioni che

avevamo già scritto per le liste.

ATTENZIONE! Non dimenticare di importare tutte le librerie che ti servono nei vari file header!

Vediamo invece il main come è fatto:

#include <stdio.h>

#include "../librerie/list.h"

#include "libretto.h"

int main()

{ int i;

char nome[40];

int matricola, scelta;

Libretto libretto = inputLibretto();

Item item;

Esame es;

while (1)

{ printf("Che cosa vuoi fare?\n");

printf("[1] Aggiungi esame\n");

printf("[2] Stampa esami\n");

printf("[3] Ricerca esame\n");

printf("[0] Esci\n");

scanf("%d", &scelta);

getchar();

switch (scelta)

{ case 0: return 0;

break;

case 1:

{ item = inputItem();

addEsame(libretto, item);

}

break;

case 2: printLibretto(libretto);

break;

case 3:

{ printf("Inserisci esame da cercare: ");

char materia[40];

scanf("%[^\n]", materia);

getchar();

if (es = searchEsame(libretto, materia))

{ printf("Esame trovato\n");

outputItem(es);

}

else printf("Esame non trovato\n");

}

break;

default: printf("Errore di input\n");

break;

}

} return 0;

}

A cosa servono queste righe di codice?

scanf("%[^\n]", materia);

;

getchar()

La prima prende tutto quello che c’è scritto fino al carattere \n, l’operatore %[^\n], serve a questo,

prende tutto quello che c’è nel buffer, fino allo \n (\n escluso) e lo mette in materia.

La seconda riga serve a togliere lo \n dal buffer, altrimenti la prossima scanf non farà quello che

deve, visto che l’operatore %[^\n], legge fino allo \n (\n escluso), rimarrà ancora 1 carattere nel

buffer, cioè proprio lo \n. getchar() prende un carattere dal buffer e lo “brucia”, è possibile

assegnarlo a una variabile

char ch = getchar();

In questo modo ch assumerà il valore del primo carattere presente nel buffer. Il carattere preso dalla

getchar() verrà eliminato dal buffer.

Esempio:

Ipotizziamo che nel buffer ci sia “ciao”, con ch = getchar(), ch sarà uguale a “c” e nel buffer

rimarrà “iao”.

In questo caso non assegniamo il valore della getchar() a una variabile perché non ci interessa

averne il valore, vogliamo solo eliminare lo \n dal buffer.

ADT STACK (PILA)

Uno stack è una sequenza di elementi di un determinato tipo, dalla quale è possibile rimuovere o

aggiungere elementi da un solo lato (top dello stack). Lo stack è una struttura dati lineare a

dimensione variabile dalla quale è possibile accedere esclusivamente al primo elemento. E’

possibile accedere agli altri elementi solamente una volta che sono stati rimossi tutti quelli prima.

Ci sono due tipi di stack:

LIFO (Last in, first out)

• FIFO (First in, first out)

Per ora vedremo lo stack LIFO.

L’operazione di aggiunta su uno stack si chiama push, mentre quella di rimozione si chiama pop.

Sono entrambe molto semplici, push aggiunge un elemento in testa, pop rimuove un elemento dalla

testa. Sintattica Semantica

Nome del tipo: Stack Insieme di sequenza s <a , …, a > di tipo Item

1 n

Tipi usati: Item, boolean l’elemento NULL rappresenta la pila vuota

newStack() → Stack newStack() → s

postc: s = NULL

push(Stack, el) → Stack push(Stack, el) → s

postc:s <a , … ,a >

• 1 n

1

AND s <el, a , … ,a >

1 n

pop(Stack) → Stack pop(Stack) → s

prec: s <a , a , … ,a > n > 0

• 1 2 n

1

postc: s <a , … , a >

• 2 n

isEmptyStack(Stack) → boolean isEmptyStack(Stack) → b

prec: se Stack = NULL b = true,

• altrimenti b = false

topStack(Stack) → Item topStack(Stack) → Item

prec: a <a , a , … , a > n > 0

• 1 2 n

postc: item = a1

E’ possibile fare l’implementazione sia con gli array che con le liste concatenate (sono le più

utilizzate).

L’implementazione con gli array prevede un array di maxstack elementi, e un contatore pos che

indica in quale indice dell’array siamo, quando si raggiunge la fine non è più possibile eseguire

l’operazione di push.

L’implementazione con le liste prevede l’utilizzo delle liste, quindi non abbiamo bisogno più di una

grandezza maxstack, e possiamo aggiungere quanti elementi vogliamo.

IMPLEMENTAZIONE CON ARRAY

Con gli array la struttura stack contiene un array di Item di grandezza MAXSTACK che conterrà gli

Item. Gli item potranno essere liste, nodi, studenti ecc…

Inoltre contiene un intero top, che servirà per sapere dove si trova l’elemento in testa allo stack.

L’elemento in testa allo stack sarà l’ultimo inserito, cioè quello in posizione items[top].

#define MAXSTACK 10

struct stack {

Item items[MAXSTACK];

int top;

};

Stack newStack(){

Stack stack = malloc(sizeof(struct stack));

if (stack == NULL)

return NULL;

stack -> top = 0;

return stack;

}

Il costruttore newStack() alloca lo spazio di memoria disponibile per uno stack, l’if serve per

controllare se c’è stato un errore nell’allocazione della memoria. Se per esempio non c’è più spazio

disponibile in memoria la malloc() restituisce un puntatore nullo. Successivamente impostiamo il

top dello stack a 0. Il top dello stack dovrà puntare al prossimo elemento da aggiungere, infatti in

items[0] non c’è nessun Item ancora, nel momento in cui si eseguirà una push(), verrà aggiunto

l’elemento e verrà aumentato il top al prossimo elemento da allocare.

int push(Stack stack, Item item){

if (stack -> top == MAXSTACK)

stack -> items[stack -> top] = item;

stack -> top++;

return 1;

}

La funzione push() controlla innanzitutto se il top dello stack è uguale a MAXSTACK, se così

fosse significa che l’array è finito, perché abbiamo definito MAXSTACK = 10, significa che gli

indici dell’array vanno da 0 a 9, perciò se top = 10 significa che l’array è finito e restituiamo 0 per

segnalare che c’è stato un errore. Se invece top ≠ MAXSTACK mette l’item passato alla funzione

dentro items[pos] dello stack che gli viene passato, tutto si traduce in

stack -> items[stack -> top] = item;

stack -> top++;

Subito dopo viene incrementato il top perché deve puntare al prossimo elemento da allocare

int isEmptyStack(Stack stack){

return stack -> top == 0 ? 1 : 0;

}

isEmptyStack() restituisce 1 se lo stack è vuoto, 0 altrimenti.

L’espressione

return stack -> top == 0 ? 1 : 0;

equivale a

if (stack -> top == 0)

return 1;

else return 0;

La parte evidenziata in verde corrisponde all’elemento da restituire nel caso in cui l’espressione

stack -> top == 0 sia vera, quella in rosso corrisponde all’elemento da restituire nel caso in cui

l’espressione stack -> top == 0 sia falsa.

Perché controlliamo se il top è uguale a 0 per verificare che lo stack sia vuoto? Perché abbiamo

detto che il top punta all’indice dove verrà inserito il nuovo elemento, quindi se top == 0 significa

che non ci sono ancora elementi nello stack, perché l’indice 0 è l’indice nel quale verrà inserito il

primo elemento quando si eseguirà una push().

int pop(Stack stack){

if (isEmptyStack(stack))

return 0;

stack -> top--;

return 1;

}

La funzione pop() controlla se lo stack è vuoto, se lo è restituisce 0, altrimenti decrementa top di 1.

ATTENZIONE! La memoria non va liberata, non va eseguita la free() di nessun elemento

dell’array, perché a questi elementi abbiamo assegnato lo stesso indirizzo di memoria degli Item che

contengono, quindi se eseguissimo una free() perderemmo anche i dati originali che sono stati

copiati nell’array.

Item topStack(Stack stack){

if(isEmptyStack(stack))

return NULL;

Item it = stack -> items[stack -> top-1];

return it;

}

Questa funzione controlla che lo stack non sia vuoto, se non è vuoto crea un Item e gli assegna il

valore che c’è nell’array items all’indice top-1.

Perché top-1? Perché in top metteremo il nuovo elemento quando faremo la push(), quindi l’ultimo

elemento inserito si trova in top-1.

void printStack(Stack stack){

int i;

for (i = 0; i < stack -> top; i++)

outputItem(stack -> items[i]);

}

Questa funzione è una funzione aggiuntiva che non è presente nella tabella, ed è molto semplice,

esegue un ciclo da 0 a stack -> top e stampa l’elemento.

Come sempre non bisogna dimenticare di implementare le librerie necessarie al funzionamento del

programma, che in questo caso, per questo file contenente le funzioni appena viste, che si chiama

stack.c, saranno:

#include <stdlib.h>

#include "stack.h"

#include "item.h"

#include "list.h"

#define MAXSTACK 10

Il file stack.h è molto semplice da realizzare:

stack.h

#include "item.h"

typedef struct stack *Stack;

Stack newStack();

int push(Stack stack, Item item);

int pop(Stack stack);

int isEmptyStack(Stack stack);

Item topStack(Stack stack);

void printStack(Stack stack);

Ecco un semplice main di test di tutte le funzioni

#include <stdio.h>

#include "../librerie/stack.h"

int main()

{ Item it;

Stack stack = newStack();

int i;

for (i = 0; i < 3; i++)

{ printf("Inserire numero: ");

it = inputItem();

push(stack, it);

}

printStack(stack);

printf("\n");

it = topStack(stack);

outputItem(it);

printf("\n");

pop(stack);

printStack(stack);

printf("\n");

it = topStack(stack);

outputItem(it);

printf("\n");

printf("%d\n", isEmptyStack(stack));

return 0;

}

makefile

arr: main.o stack-arr.o list.o item-int.o

gcc main.o stack-arr.o list.o item-int.o -o main

main.o:

gcc -c main.c

stack-arr.o:

gcc -c ../librerie/stack-arr.c

list.o:

gcc -c ../librerie/list.c

item-int.o:

gcc -c ../librerie/item-int.c

clean:

rm -f *.o *.bin IMPLEMENTAZIONE CON LISTE

In questo caso la struttura contiene una lista, quindi utilizzeremo tutte le funzioni sulle liste che

abbiamo già creato, nulla di difficile.

struct stack {

List items;

};

Stack newStack(){

Stack stack = malloc(sizeof(struct stack));

stack -> items = newList();

return stack;

}

In questo caso la funzione newStack() alloca memoria per uno stack, e poi su stack -> items

richiama la newList() perché bisogna allocare memoria anche per la lista, in questo modo potremo

utilizzare le funzioni sulle liste come addHead() ecc…

La lista appena allocata sarà vuota, quindi lo stack sarà vuoto.

Le restanti funzioni sono praticamente già fatte, bisogna chiamarle nel modo adeguato.

int push(Stack stack, Item item){

addHead(stack -> items, item);

return 1;

}

int pop(Stack stack){

if (removeHead(stack -> items) != NULL)

return 1;

else return 0;

}

Item topStack(Stack stack){

return getHead(stack -> items);

}

int isEmptyStack(Stack stack){

return isEmpty(stack -> items);

}

void printStack(Stack stack){

printList(stack -> items);

}

makefile

stack: main.o stack.o list.o item-int.o

gcc main.o stack.o list.o item-int.o -o main

main.o:

gcc -c main.c

stack.o:

gcc -c ../librerie/stack.c

list.o:

gcc -c ../librerie/list.c

item-int.o:

gcc -c ../librerie/item-int.c

clean:

rm -f *.o *.bin

Come main di prova va bene lo stesso scritto prima.

STACK CON ARRAY E ALLOCAZIONE DINAMICA

Nello scorso paragrafo abbiamo visto come implementare uno stack con un array, e abbiamo visto

anche che abbiamo un problema nel momento in cui lo spazio a disposizione dell’array termina. Ora

vedremo come rendere quell’array dinamico, in modo che la grandezza dell’array possa adattarsi al

numero di elementi presenti.

Questa volta quindi non avremo bisogno della costante MAXSTACK perché la dimensione

dell’array cambierà in base a quanta ce ne serve. Avremo bisogno di altre due costanti che

chiameremo START_DIM e ADD_DIM, entrambe dal valore di 1.

Quando inizializzeremo la struttura stack allocheremo memoria per START_DIM elementi di tipo

Item al nostro array di Item. Quando aggiungeremo un elemento, riallocando la memoria,

aggiungeremo ADD_DIM elementi a quello che già esistono.

La struttura stack quindi cambia, oltre alla variabile top avremo la variabile dim, che terrà conto di

quanti elementi ci sono nell’array. All’inizio la variabile dim sarà 1 perché ci sarà un solo elemento

(per essere precisi sarà uguale a START_DIM), e la variabile top sarà 0, perché il prossimo

elemento verrà aggiunto in posizione 0.

#define START_DIM 1

#define ADD_DIM 1

struct stack{

Item *items;

int top;

int dim;

};

Anche la dichiarazione dell’array è cambiata, ma di fatto non è molto diversa, prima era

Item items[MAXSTACK];

Ricordiamo che il tipo Item è un *void, quindi con questa riga di codice stiamo dichiarando un

array di *void elementi, se facciamo invece

Item *items;

Stiamo comunque dichiarando un array di *void elementi, è come se facessimo

void **items;

Il primo asterisco indica che è un array, il secondo indica che il tipo di elementi presenti nell’array è

puntatore a *void.

Abbiamo quindi creato un array di puntatori ti tipo *void (o Item) che conterrà gli indirizzi di

memoria dell’elemento generico che vorremo usare, potrà contenere interi, stringhe, caratteri,

strutture, praticamente di tutto.

Detto ciò vediamo la funzione newStack().

Stack newStack(){

Stack stack = malloc(sizeof(struct stack));

stack -> items = malloc(sizeof(Item) * (START_DIM));

stack -> top = 0;

stack -> dim = START_DIM;

return stack;

}

Come abbiamo sempre fatto allochiamo la memoria necessaria allo stack.

L’istruzione successiva ci è nuova stiamo usando la malloc su un array di puntatori di tipo Item.

Abbiamo detto che inizialmente vogliamo che questo array contenga solo 1 elemento.

Sappiamo come funziona la malloc, prende in input la grandezza in byte di un tipo e viene

moltiplicata per il numero di elementi di quel tipo che si vogliono allocare.

In questo caso vogliamo allocare memoria per una variabile di tipo Item, quindi con sizeof(Item)

stiamo dicendo che il tipo di elementi che vogliamo allocare è un Item, subito dopo diciamo che

vogliamo un solo elemento.

Allochiamo elementi di tipo Item perché l’array conterrà Item.

Quindi questa espressione

stack -> items = malloc(sizeof(Item) * (START_DIM));

serve per allocare spazio per 1 solo elemento di tipo Item.

Le successive due righe sappiamo già cosa fanno, impostano il top = 0 e la dimensione =

START_DIM, cioè 1.

La funzione push()cambia un po' rispetto a quella già vista.

Viene sempre effettuato il controllo tra top e dim per verificare se la memoria a disposizione è

terminata. Se top == dim significa che la memoria a disposizione è terminata, perché top potrà

assumere valori compresi tra 0 e dim-1 (se dim = 10, gli indici dell’array vanno da 0 a 9).

Contrariamente all’altra funzione però, dove in questo caso veniva restituito 0, si rialloca la

memoria in modo tale che ci sia sempre spazio per l’aggiunta di elementi nell’array.

Come si fa? Con la realloc().

void *realloc(void *ptr, size_t size);

La realloc() ci restituisce un indirizzo di memoria di grandezza size all’interno del quale vengono

copiate tutti i dati che avevamo prima nell’indirizzo di memoria precedente. Se la realloc() non

riesce ad allocare memoria ci restituisce un puntatore nullo, perciò se non vogliamo correre il

rischio di perdere i dati dovremo creare un array di Item temporaneo nel quale andremo ad allocare

la nuova memoria, se l’allocazione della memoria andrà a buon fine allora assegneremo l’indirizzo

dell’array temporaneo a quello in cui ci sono i nostri dati, aumenteremo la variabile dim perché la

grandezza dell’array è aumentata, inseriremo l’elemento nello spazio appena creato e aumenteremo

il top dello stack. Restituiremo 0 altrimenti.

int push(Stack stack, Item item){

if (stack -> top == stack -> dim)

{ Item *temp;

temp = realloc(stack -> items, sizeof(Item) * (stack -> dim + ADD_DIM));

if (temp == NULL)

return 0;

else

{ stack -> items = temp;

stack -> dim += ADD_DIM;

}

} stack -> items[stack -> top] = item;

stack -> top++;

return 1;

}

Le altre funzioni restano praticamente identiche. La funzione pop() potrebbe accorciare l’array

quando si eliminano elementi, ma noi non lo faremo per lo stesso motivo dell’altra volta, ovvero

che potrebbero esserci variabili che utilizzano quell’indirizzo di memoria e potremmo perdere dati.

“La memoria non va liberata, non va eseguita la free() di nessun elemento dell’array, perché a

questi elementi abbiamo assegnato lo stesso indirizzo di memoria degli Item che contengono,

quindi se eseguissimo una free() perderemmo anche i dati originali che sono stati copiati

nell’array.”

ESERCIZIO:

CREARE UN PROGRAMMA CHE CONTROLLA SE LE PARENTESI IN UN

ESPRESSIONE SONO BILANCIATE

Esempio: (4 + a) * {[1-(2/x)] * (8-a)} è bilanciata

[x-(4y + 3] * (1-x)) non è bilanciata

Per semplicità supponiamo che non ci siano precedenze sulle parentesi:

(a + {b-1}) / [b+2] è ammessa come valida

Vogliamo che data un espressione venga controllato che ad ogni parentesi aperta corrisponda la

rispettiva parentesi chiusa, perciò di tutti i caratteri considereremo solo le parentesi, non ci interessa

dei numeri presenti all’interno.

L’utilizzo di uno stack è perfetto per questo programma, perché l’ultima parentesi ad entrare nello

stack dovrà essere la prima ad uscirne.

Se in cima allo stack c’è ‘(‘ ci aspetteremo di trovare la rispettiva ‘)’ per far si che siano bilanciate,

se invece troveremo un altra parentesi chiusa, per esempio ‘]’ allora le parentesi non saranno

bilanciate.

Procediamo con l’analisi del problema

Dati in ingresso: una stringa exp

• Precondizione: true

Dati di uscita: Un valore booleano

• Postcondizione: Se exp è vuota ris = true, se non è vuota, ris = true se le parentesi

◦ sono bilanciate, ris = false altrimenti

Identificatore Tipo Descrizione

exp stringa Espressione in input

ris booleano Risultato valutazione in output

Analizziamo il programma step per step

step 1: Prendere in input una stringa exp

step 2: se exp è vuota dare in input exp

step 3: Sia s uno stack di caratteri inizialmente vuoto

step 5: Per ogni carattere dello stack

se car == ‘(‘ or car == ‘[‘ or car == ‘{‘

inserisci il carattere nello stack

se car == ‘)’ or car == ‘]’ or car == ‘}’

se lo stack è vuoto dai in output false

estrarre un elemento dallo stack e metterlo in t

se t non è la corrispondente parentesi chiusa dai in output false

step 6: Se s è vuoto dare in output true

altrimenti dare in output false

Per questo programma avremo bisogno delle seguenti funzioni:

int isBalanced(char *exp);

int isOpenBracket(char ch);

int isClosedBracket(char ch);

int isCorresponding(char ch1, char ch2);

isBalanced() prende in input una stringa e controlla se le parentesi sono bilanciate. Restituisce true

se lo è.

isOpenBracket() prende in input un carattere e controlla se è una parentesi aperta. Restituisce true

se lo è.

isClosedBracket() prende in input un carattere e controlla se è una parentesi chiusa. Restituisce

true se lo è.

isCorresponding() prende in input due caratteri, una parentesi aperta e una chiusa, e controlla se

sono le rispettive parentesi aperte e chiuse. Restituisce true se lo sono.

int isOpenBracket(char ch){

if (ch == '(' || ch == '[' || ch == '{')

return 1;

else return 0;

}

int isClosedBracket(char ch){

if (ch == ')' || ch == ']' || ch == '}')

return 1;

else return 0;

}

int isCorresponding(char ch1, char ch2){

if (ch2 - ch1 >= 1 && ch2 - ch1 <= 2)

return 1;

else return 0;

}

Queste funzioni sono molto semplici. Quella che può destare un po' di dubbi è isCorresponding(),

ma se ci si ragiona si nota che non è difficile. In questa funzione abbiamo utilizzato i caratteri ascii

per controllare se le parentesi sono le corrispettive.

Carattere Ascii Carattere Ascii Carattere Ascii

( 40 [ 91 { 123

) 41 ] 93 } 125

Questa tabella raffigura le parentesi con i rispettivi codici ascii, possiamo notare che le parentesi

tonde si trovano a distanza 1 l’una dall’altra, mentre le quadre e le graffe si trovano a distanza 2.

Per cui se il risultato della sottrazione dei due caratteri passati come argomenti è compresa tra 1 e 2

allora le parentesi saranno sicuramente bilanciate.

ATTENZIONE! Il dubbio che può sorgere subito è il caso in cui una parentesi sia ‘[‘ e l’altra sia ‘}’

ma si può notare molto facilmente che la sottrazione del codice ascii della parentesi ‘[‘ con il codice

ascii della parentesi ‘}’ non è compreso tra 1 e 2. 123 – 91 = 32.

Potrebbe sembrare strano effettuare la sottrazione tra due caratteri ascii, ma in questo caso il c

esegue un cast automatico al tipo intero, convertendo il carattere nel rispettivo codice ascii ed

eseguendo la sottrazione.

int isBalanced(char *exp){

int len = strlen(exp);

if (len == 0)

return 1;

int i;

Stack stack = newStack();

Item it;

for (i = 0; i < len; i++)

{ if (isOpenBracket(exp[i]))

{ it = &exp[i];

push(stack, it);

}

else if (isClosedBracket(exp[i]))

{ if (isEmptyStack(stack))

return 0;

it = topStack(stack);

char *ch = it;

if (!isCorresponding(*ch, exp[i]))

return 0;

pop(stack);

}

}

if (isEmptyStack(stack))

return 1;

else return 0;

}

main.c

#include <stdio.h>

#include "../librerie/stack.h"

#include "../librerie/brackets.h"

#define MAX_EXP 100

int main()

{ char exp[MAX_EXP];

printf("Inserisci un espressione\n");

scanf("%[^\n]", exp);

getchar();

if (isBalanced(exp))

printf("Bilanciate\n");

else printf("Non bilanciate\n");

return 0;

} CODE (FIFO, First In – First Out)

Fin’ora abbiamo visto il funzionamento della lista LIFO.

La lista FIFO è leggermente diversa, gli elementi vengono aggiunti da un lato e rimossi dall’altro.

Nello specifico gli elementi vengono aggiunti dalla tail e rimossi dalla head. Il primo elemento

aggiunto alla sequenza sarà il primo ad essere eliminato.

Si può accedere direttamente solo alla head della lista. Non si può accedere ad altri elementi senza

rimuovere quelli che sono avanti

↓ ↓

head tail

15 20 46 89 50

In questo esempio possiamo accedere solo all’elemento della head, cioè a 15, se volessimo

l’elemento 20, dovremmo rimuovere 15 dalla lista, solo allora potremmo ottenere il 20.

Anche in questo caso vedremo due implementazioni, una con le liste e una con gli array.

Iniziamo con lo scrivere la tabella dell’ADT coda

Sintattica Semantica

Nome del tipo: Queue Queue = <a ,a , … , a > di tipo Item, il nil

1 2 n

Tipi usati: item, boolean rappresenta la lista vuota

newQueue() → Queue newQueue() → q

postc: q = nil

isEmptyQueue(Queue) → boolean isEmptyQueue(q) → i

postc: i = 1 se q = nil, i = 0 altrimenti

enQueue(Queue, Item) → Queue enQueue(q, it) → q’

postc: q = <a ,a , … , a > e

• 1 2 n

q’ = <a ,a , … , a it>

1 2 n,

deQueue(Queue) → Queue deQueue(q) → q’

prec: q = <a ,a , … , a > n > 0

• 1 2 n

postc: q’ = <a , … , a >

• 2 n

Per questa implementazione con le liste bisogna modificare la struttura list in modo che contenga un

puntatore alla head della lista, uno alla coda e il solito intero size che conta gli elementi.

Queste modifiche comportano alcune accortenze da parte nostra, ovvero, visto che ora abbiamo un

puntatore che dovrà puntare sempre alla coda, dobbiamo modificare le funzioni in modo tale che sia

per l’aggiunta che per la rimozione il puntatore alla coda punti sempre all’ultimo elemento.

Abbiamo inoltre un altro vantaggio, cioè possiamo utilizzare il puntatore alla coda per richiamare la

addTail() senza dover scorrere tutta la lista.

Modifica addTail

Dobbiamo innanzitutto distinguere due casi: il caso in cui la lista sia vuota e quindi stiamo

inserendo il primo elemento e il caso in cui la lista non sia vuota.

Nel primo caso dobbiamo impostare il puntatore alla head sul nodo che creeremo, nel secondo caso

no.

Lista vuota:

Lista non vuota: Nel

caso

in cui

la lista

non

sia vuota bisogna far puntare prima tail → next al nuovo nodo e poi cambiare l’indirizzo di tail con

quello del nuovo nodo. Se facessimo al contrario, cioè se assegnassimo prima l’indirizzo di tail al

nuovo nodo, quando poi faremo tail → next otterremo il puntatore nullo, perché il nuovo nodo non

ha un successivo.

Modifica removeHead

Per la removeHead() dobbiamo creare un puntatore temporaneo e farlo puntare al primo elemento,

successivamente facciamo scorrere in avanti la head e deallochiamo la memoria del puntatore

temporaneo. Se nella lista c’era un solo elemento allora adesso la lista è vuota.

AddTail() e removeHead() sono le uniche funzioni che utilizzeremo per le code. Come abbiamo

detto prima nella coda possiamo aggiungere gli elementi solo da un lato e possiamo rimuoverli solo

dall’altro.

IMPLEMENTAZIONE CON GLI ARRAY

Per quanto riguarda gli array invece la struttura Queue è composta da un array di Item di

MAX_QUEUE elementi, un intero che tiene conto dell’indice di testa e un intero che tiene conto

dell’indice di coda. Mentre con le liste possiamo aggiungere elementi fino ad esaurimento memoria,

con questa implementazione abbiamo dei limiti, ovvero la dimensione massima dell’array. In realtà

questo problema potrebbe anche essere risolto, ma risulterebbe comunque troppo costoso in termini

di prestazioni, ci ritorneremo. Un altro problema che salta all’occhio è che se noi aggiungiamo dalla

coda e rimuoviamo dalla testa, gli spazi che rimuoviamo li perdiamo e man mano l’array si accorcia

sempre di più.

↓ ↓

head tail

10 45 23 18 65 89 76 43 22

Durante la rimozione della head, succede questo:

↓ ↓

head tail

10 45 23 18 65 89 76 43 22

↓ ↓

head tail

10 45 23 18 65 89 76 43 22

Man mano che rimuoviamo elementi l’array diventa sempre più corto, come possiamo fare per

risolvere il problema?

L’idea che a tutti viene in mente subito è quella di eseguire uno shift per spostare tutti gli elementi,

ma non è esattamente la migliore, perché nel caso in cui avessimo 1000 elementi dovremmo

eseguire 1000 shift.

Una soluzione corretta è quella di utilizzare l’array in modo circolare, cosa significa:

significa che una volta che la tail è arrivata alla fine, controlla se nella posizione 0 è possibile

aggiungere un elemento, se non è possibile non lo aggiunge, se invece è possibile aggiunge

l’elemento e sposta l’indice sullo 0.

Possiamo eseguire l’operazione descritta sopra aggiungendo 1 modulo MAX_QUEUE.

Se MAX_QUEUE = 10 e i = 9, allora (9 + 1) % MAX_QUEUE = 0.

Come facciamo a controllare se l’elemento successivo è vuoto? Controlliamo se quell’indice è

diverso dalla head, se è diverso significa che è vuoto.

Bisogna prestare attenzione al fatto che non necessariamente l’indice head verrà prima dell’indice

tail, potrebbero capitare situazioni del genere.

↓ ↓

tail head

100 41 32 48 65 74 216 33 468 77

E’ importante notare che la tail punta al prossimo elemento al quale assegnare un elemento.

Abbiamo appena detto che il controllo che effettuiamo è: vedere prima se il successivo modulo

MAX_QUEUE è vuoto, e solo se lo è assegniamo il valore nella posizione corrente e aumentiamo il

valore del contatore tail. Se eseguissimo questa operazione anche nel caso dell’esempio sopra

riportato, succederebbe che l’elemento verrebbe assegnato dove attualmente c’è il 65 e

successivamente verrebbe aumentato il valore di tail, avendo che head == tail. Vedremo tra poco

che questo controllo lo utilizzeremo per controllare se una Queue è vuota, infatti appena viene

creata la Queue head e tail avranno lo stesso indice (che non dovrà essere necessariamente 0), per

cui se sono uguali allora la Queue sarà vuota.

ATTENZIONE! In questo esempio il numero 65 è scritto in rosso perché è il valore che era presente

nel vecchio array, ed è un valore che a noi non interessa e di cui non ne terremo conto. Per capire

meglio osserviamo il passaggio precedente all’esempio sopra

↓ ↓

tail head

100 41 32 18 65 74 216 33 468 77

In questo passaggio cosa succede? Viene controllato se lo spazio dove c’è il 65 è disponibile per

essere sovrascritto, il risultato è positivo e quindi viene messo il nuovo valore al posto di 18, in

questo caso 48, e tail viene mandato avanti.

Nel passaggio dopo lo stesso controllo sarà falso e quindi il 65 resterà li perché era presente

nell’array iniziale, ma è un valore estraneo a questa nuova sequenza.

Come dicevamo prima il problema della memoria potrebbe essere risolto con delle realloc, ma la

soluzione non sarebbe comunque facile perché quando ne avremo bisogno dovremo riallocare la

memoria, e nel caso in cui l’elemento da aggiungere sta nel mezzo, come nell’esempio fatto prima,

allora dovremo anche spostare tutti gli elementi che si trovano dopo tail di una posizione in avanti

eseguendo uno shift. In questo modo se abbiamo 1000 elementi eseguiremo 500 shift, potrebbe però

capitare un caso del genere:

↓ ↓

tail head

10 45 23 18 65 89 76 43 22 56

In questo caso anche se riallocassimo la memoria eseguiremo comunque n-1 spostamenti, ciò

significa che in un array di 1000 elementi eseguiremo 999 shift. Questa soluzione è comunque

migliore di quella di spostare tutti gli elementi a prescindere e senza utilizzare l’array in modo

circolare, perché potrebbero capitare casi in cui eseguiremo la metà degli spostamenti o anche di

meno.

Il modo migliore per implementare questa funzione è con le liste.

Iniziamo a vedere l’implementazione con le liste.

#include <stdlib.h>

#include "queue.h"

#include "list.h"

#include "item.h"

struct queue{

struct node *head;

struct node *tail;

List items;

};

Queue newQueue(){

Queue queue = malloc(sizeof(struct queue));

queue -> head = queue -> tail = NULL;

queue -> items = newList();

return queue;

}

int isEmptyQueue(Queue q){

return q -> head == q -> tail;

}

int enQueue(Queue q, Item it){

return addTail(q -> items, it);

}

Item deQueue(Queue q){

return removeHead(q -> items);

}

void printQueue(Queue q){

printList(q -> items);

}

Queste sono le funzioni che ci servono per utilizzare le liste come code. Abbiamo solamente

chiamato le funzioni che già avevamo creato riguardanti le liste, nulla di complicato.

Vediamo ora l’implementazione con gli array.

#include <stdlib.h>

#include "queue.h"

#include "list.h"

#include "item.h"

#define MAX_QUEUE 6

struct queue{

int head;

int tail;

List items[MAX_QUEUE];

};

Queue newQueue(){

Queue queue = malloc(sizeof(struct queue));

if (!queue)

return NULL;

queue -> head = queue -> tail = 0;

return queue;

}

int isEmptyQueue(Queue q){

return q -> head == q -> tail;

}

int enQueue(Queue q, Item it){

if ((q -> tail + 1) % MAX_QUEUE == q -> head)

return 0;

q -> items[q -> tail] = it;

q -> tail = (q -> tail + 1) % MAX_QUEUE;

return 1;

}

Nella funzione enQueue() incrementiamo tail su un insieme di 10 numeri (da 10 a 9), dove 9

+ 1 = 0, lo possiamo fare grazie all’operatore modulo.

Item deQueue(Queue q){

if (isEmptyQueue(q))

return 0;

int removed = q -> head;

q -> head = (q -> head + 1) % MAX_QUEUE;

return q -> items[removed];

}

Per la funzione deQueue() non liberiamo la memoria ne eliminiamo l’elemento, perché non ne

terremo comunque conto e verrà sovrascritto quando ne avremo bisogno, inoltre inizializzarlo a 0

sarebbe inutile perché in ogni caso quell’indirizzo di memoria conterrebbe qualcosa, perderemo

solo tempo.

void printQueue(Queue q){

int i;

for (i = q -> head; i != q -> tail; i = (i + 1) % MAX_QUEUE)

outputItem(q -> items[i]);

}

Per il ciclo di stampa va effettuato un controllo un po' diverso dal solito, non va bene più i !=

lunghezza perché potrebbero esserci elementi che sono stati aggiunti in modo circolare, utilizziamo

quindi il controllo i != q -> tail per capire quando fermarci.

RECORD DI ATTIVAZIONE

Ogni volta che viene invocata una funzione viene creata automaticamente una struttura dati

chiamata record di attivazione.

Viene creata una nuova attivazione (istanza) della funzione chiamata

• viene allocata memoria per i parametri e per le variabili locali

• si effettua il passaggio dei parametri

• si esegue il codice della funzione

• Il record di attivazione contiene

i parametri formali

• le variabili locali

• l’indirizzo di ritorno (RA) che contiene

• l’indirizzo al quale tornare una volta

terminata l’esecuzione

un collegamento al record di attivazione

• del chiamante (link dinamico DL)

l’indirizzo del codice della funzione

• (puntatore alla prima istruzione del

codice).

Il record di attivazione associato a una funzione f è creato nel momento in cui viene chiamata f,

permane tutto il tempo che f è in esecuzione e viene distrutto (deallocato) al termine

dell’esecuzione.

La dimensione del record di attivazione varia da una funzione all’altra. E’ possibile per una data

funzione calcolarne la grandezza.

STACK

L’area di memoria nella quale vengono allocati i record di attivazione è uno stack LIFO e viene

gestito tramite le operazioni di push e di pop. Ogni elemento dello stack è una struttura come quella

vista sopra.

In cima viene aggiunta l’ultima funzione eseguita, una volta eseguita il suo return address ci porterà

all’indirizzo del main o di un altra funzione (funzioni annidate o ricorsive). L’ultima funzione

chiamata dovrà essere la prima a terminare. Nel caso di funzioni annidate, il return address ci

porterà all’indirizzo dove è contenuta la prima istruzione della funzione chiamante e verrà eseguita.

Così succede anche per le altre funzioni chiamanti, se ce ne sono, se non ce ne sono allora

torneremo nel main.


PAGINE

169

PESO

1.82 MB

PUBBLICATO

5 mesi fa


DETTAGLI
Corso di laurea: Corso di laurea in informatica
SSD:
Università: Salerno - Unisa
A.A.: 2018-2019

I contenuti di questa pagina costituiscono rielaborazioni personali del Publisher mariooffertucci di informazioni apprese con la frequenza delle lezioni di Programmazione e Strutture Dati e studio autonomo di eventuali libri di riferimento in preparazione dell'esame finale o della tesi. Non devono intendersi come materiale ufficiale dell'università Salerno - Unisa o del prof Fuccella Vittorio.

Acquista con carta o conto PayPal

Scarica il file tutte le volte che vuoi

Paga con un conto PayPal per usufruire della garanzia Soddisfatto o rimborsato

Recensioni
Ti è piaciuto questo appunto? Valutalo!

Altri appunti di Corso di laurea in informatica

Architettura degli elaboratori
Appunto
Fondamenti di programmazione - Appunti
Appunto
Esame programmazione 1
Appunto
Calcolo Numerico - nozioni
Appunto