Fondamenti di Programmazione a.a. 2009-2010 (canale E-O)

Informazioni sul corso. Cenni sull'architettura di un calcolatore: CPU, memoria primaria e secondaria, input/output. Struttura logica della memoria. Linguaggio macchina, linguaggio assembly. Linguaggi ad alto livello e compilatori. Cenni storici sul linguaggio C. Primo programma in C: stampa di una stringa di testo. Programma che stampa la somma di due numeri: specifica di conversione della printf per gli interi.

Memoria, locazioni di memoria, indirizzi e variabili. Dichiarazioni di variabili di tipo int. Lettura dallo standard input tramite la funzione scanf(). L'operatore di indirizzo &. Assegnamenti. Operatori aritmetici: +, -, *, /, %. Esempi:

• Programmi che leggono un intero n e stampano il quadrato e la sedicesima potenza di n
• Programma che legge due interi n e m e stampa il quoziente e il resto della divisione di n per m
• Programma che legge un intero s che rappresenta un numero di secondi e stampa l'equivalente in giorni, ore, minuti e secondi (ad es. se s = 100000 allora l'output è 1 giorni 3 ore 46 minuti e 40 secondi).

Instruzioni di selezione: if () - else. Operatori relazionali: <, >, <=, >=, ==, !=. Esempi: Programmi che leggono due o tre numeri e ne stampano il massimo.
Esercizio 1    Scrivere un programma che prende in input tre numeri e li stampa in ordine crescente.
Esercizio 2    Scrivere un programma legge due date nel formato g/m/a (ad es. 17/4/2009) e le confronta stampando se la prima data è anteriore, posteriore o uguale alla seconda. Ad esempio, se le date sono 12/5/2009 e 10/7/2009, il programma deve stampare la prima data è anteriore alla seconda.

Discussione degli esercizi 1 e 2. Operatori logici || (OR) && (AND). Istruzioni iterative: for ( ; ; ). Esempi:

• Programma che stampa 50 volte una stringa ("Repetita iuvant").
• Programma che prende in input un intero n e stampa le prime n potenze di 2.
• Programma che stampa il massimo di n numeri.
• Programma che legge n e stampa un quadrato di n righe e n colonne riempito con il carattere '*'.

Operatori di postincremento ++, postdecremento -- e gli operatori +=, -=, *=, /=, %=.
Tipi primitivi. Tipi per valori interi: short, int, long, long long e versioni unsigned. Tipi per valori in virgola mobile: float, double, long double. Il tipo carattere char: codici ASCII. Le corrispondenti specifiche di conversione per le funzioni printf() e scanf(): %hd, %d, %ld, %lld, %hu, %u, %lu, %llu, %f, %c.
Esercizio 3    Scrivere un programma che prende in input n numeri in virgola mobile (float) e stampa la media di tali numeri.
Esercizio 4    Scrivere un programma che legge un intero n e un carattere c e stampa un triangolo di altezza n fatto con caratteri c. Ad esempio, se n = 5 e c = 'a' allora il programma stampa:

a
aa
aaa
aaaa
aaaaa

Discussione degli esercizi 3 e 4. Comportamento dell'operatore di divisione / in funzione del tipo degli operandi. Istruzioni iterative: while (). Equivalenza con il for ( ; ; ). Esempi:

• Programma che determina se un numero intero è un numero primo (diverse versioni).
• Programma che prende in input un intero n e stampa il numero di cifre di n.

Istruzioni iterative: do - while (). Equivalenza con il while (). Esempi:

• Programma che legge una linea di testo (una sequenza di caratteri terminata dal carattere '\n') e conta il numero di vocali e di consonanti.
• Programma che legge una linea di testo e conta il numero di parole. Per parola si intende una sequenza di caratteri alfabetici di lunghezza massimale.

Esercizio 5    Scrivere un programma che prende in input un intero n e stampa la somma delle cifre di n. Ad esempio, se n = 1205 allora il programma stampa 8.
Esercizio 6    Scrivere un programma che legge una linea di testo e stampa la lunghezza della più lunga parola contenuta nella linea di testo. Ad esempio, se la linea di testo è "Qual'e' la parola piu' lunga? allora il programma stampa 6 se invece la linea di testo è "Una parola lunghissima", stampa 11.

Discussione degli esercizi 5 e 6. Dichiarazione e inizializzazione di vettori (arrays) (di dimensione costante). Rappresentazione in memoria dei vettori. Esempi:

• Programma che legge una linea di testo e stampa la parola più lunga contenuta nella linea.
• Programma che legge una linea di testo e calcola e poi stampa le frequenze dei caratteri stampabili contenuti nella linea di testo. Ad esempio, se la linea di testo è "Questa frase contiene 48 (quarantotto) caratteri", il programma stampa:

    5
  ( 1
  ) 1
  4 1
  8 1
  Q 1
  a 6
  c 2
  e 5
  f 1
  i 2
  n 3
  o 3
  q 1
  r 4
  s 2
  t 7
  u 2
  

Alcune funzione in ctype.h: isalpha(), isprint().
Esercizio 7    Scrivere un programma che legge una linea di testo e per ogni carattere che è l'iniziale di una parola stampa il numero di parole che iniziano con quel carattere. Ad esempio, se la linea di testo è "Una parola, due parole, tre parole", il programma stampa:

U 1
p 3
d 1
t 1

Esercizio 8    Scrivere un programma che legge un intero n (si può assumere che sia minore di 100) e poi legge n numeri in virgola mobile (float) e se ci sono due numeri la cui differenza (in valore assoluto) è minore di 0.001 stampa "Ci sono numeri vicini", altrimenti stampa "NON ci sono numeri vicini". Ad esempio, se i numeri letti sono 1.03, 0.056, 1.0305, allora il programma stampa "Ci sono numeri vicini".

Discussione degli esercizi 7 e 8. Discussione sullo stile e la buona struttura del codice: evitare l'uscita "brutale" da un ciclo iterativo. Definizione di funzioni: tipo del valore ritornato, lista dei parametri. Chiamata di una funzione. Il tipo void. Esempi: funzione che ritorna la terza potenza di un numero in virgola mobile, funzione che ritorna il massimo di due interi. Passaggio dei parametri per valore e il caso dei vettori. Esempi: funzione che ritorna la somma dei valori di un vettore di float, funzione che imposta gli elementi di un vettore ad un valore dato. Discussione sull'importanza di una adeguata decomposizione del codice di un programma in moduli (o funzioni). Principali vantaggi: migliora la leggibilità; riduce la duplicazione del codice; facilita l'individuazione degli errori; facilita le eventuali modifiche e estensioni; rende possibile la riusabilità del codice (librerie). Cenni sulla possibilità di scrivere programmi su più files, prototipo di una funzione. Esempio di una funzione che può essere utile in più programmi: funzione con prototipo int input_linea(char chA[], int maxchars) che legge dallo standard input una sequenza di caratteri e li scrive nel vettore chA fino a che non legge EOF, il carattere '\n' o sono stati letti maxchars caratteri, ritorna il numero di caratteri letti. Uso della funzione getchar().
Esercizio 9    Scrivere una funzione void ruota(char C[], int n, int k) che ruota i caratteri del vettore C di k posizioni a destra. Ad esempio, se i caratteri nel vettore C sono "programma" (n = 9) e k = 3, allora la funzione modifica il vettore in modo che contenga "mmaprogra". Scrivere anche un programma che provi la funzione.
Esercizio 10    Scrivere una funzione int incluso(int A[], int n, int B[], int m) che ritorna 1 se tutti i valori nel vettore A (di dimensione n) sono anche contenuti nel vettore B (di dimensione m), altrimenti ritorna 0. Ad esempio, se A = [2, 1, 3, 2, 1] e B = [5, 1, 3, 2] allora la funzione ritorna 1, se invece B = [5, 3, 2, 0] allora la funzione ritorna 0. Scrivere anche un programma che provi la funzione.

Discussione degli esercizi 9 e 10. Esempio di un programma che può essere convenientemente decomposto in funzioni: programma che legge dall'input due frazioni positive (nel formato numeratore/denominatore) e stampa la somma delle due frazioni, sempre nello stesso formato. Ad esempio, se il programma legge le frazioni 8/15 e 3/10, stampa 5/6. Funzioni per il calcolo del massimo comun divisore e per il calcolo del minimo comune multiplo di due interi positivi. Passaggio di parametri per valore e per indirizzo. Tipi puntatore. L'operatore di indirezione *. Esempio: funzione che prende in input il numeratore e il denominatore di una frazione e la riduce ai minimi termini. Test di correttezza di una funzione tramite la generazione di input pseudo-casuali. Le funzioni int rand() e void srand(unsigned seed) in stdlib.h.
Esercizio 11    Scrivere una funzione, int parola(char chA[], int n, int k, int *plung), che ritorna la posizione della k-esima parola contenuta nell'array chA (di dimensione n) e restituisce in *plung la lunghezza di tale parola. Se il numero di parole contenute nell'array chA è minore di k, la funzione ritorna -1 e *plung è lasciato invariato. Ad esempio, se chA contiene la sequenza di caratteri "La seconda parola" (quindi n = 17) e k = 2, allora la funzione ritorna 3 e in *plung restituisce il valore 7.
Esercizio 12    Scrivere un programma (usando la funzione dell'esercizio precedente ed eventualmente altre funzioni) che legge dall'input due linee di testo e stampa tutte le parole della prima linea che appaiono anche nella seconda. Ad esempio, se le due linee di testo sono "Le cose non sono solo cose" e "sono tante cose", allora il programma stampa:

cose
sono
cose

Discussione degli esercizi 11 e 12. Le stringhe: carattere di terminazione '\0', inizializzazione. Principali funzioni della libreria standard (string.h) per le stringhe: strcpy(), strlen(), strcmp(). Specifica di conversione %s per scanf() e printf(). Esempi:

• programma che legge n stringhe e stampa la minima, rispetto all'ordine lessicografico dato dalla funzione strcmp().
• programma che legge due stringhe e determina se sono l'una un anagramma dell'altra (ad es. "lavagna" e "valanga"). Definizione di una funzione int anagramma(char *s1, char *s2) che ritorna true o false a seconda che le stringhe s1 e s2 siano l'una un anagramma dell'altra. Uso di una funzione int occorrenze(char *s, char c) che ritorna il numero di volte che il carattere c occorre nella stringa s.

Esercizio 13    Scrivere una funzione, char *strpar(char *s, int k, char *par), che copia la k-esima parola contenuta nella stringa s in par, come stringa, e ritorna il puntatore par. Se s contiene meno di k parole, allora la funzione ritorna NULL. Sostanzialmente, strpar() è una versione per stringhe della funzione parola() dell'esercizio 11.
Esercizio 14    Scrivere un programma (usando le funzioni anagramma() e strpar()) che prende in input una linea di testo e poi una stringa e stampa tutte le parole contenute nella linea di testo che sono anagrammi della stringa. Ad esempio, se la linea di testo è "Il ratto ha mangiato la torta" e la stringa è "trota", allora il programma stampa:

ratto
torta

Discussione degli esercizi 13 e 14. Semplici algoritmi di ordinamento: selection-sort e bubble-sort. Iniziata la spiegazione dell'algoritmo della ricerca binaria.
Esercizio 15    Scrivere una funzione void ordinastr(char *str) che ordina i caratteri della stringa str. Ad esempio, se str = "ordina char" allora la funzione modifica la stringa str così " aacdhinorr".
Esercizio 16    Scrivere un programma che mette a confronto le funzioni selectionsort() e bubblesort() per ordinare vettori di interi. Misurare i rispettivi tempi di esecuzione variando i vettori da ordinare. Ad esempio, vettori già ordinati, vettori con ordinamento inverso, vettori quasi ordinati (ottenuti facendo qualche scambio in vettori ordinati) e vettori disordinati (ottenuti generando interi pseudo-casuali con la funzione rand()). Il tempo di esecuzione può essere misurato usando la funzione della libreria standard clock() in time.h che ritorna il numero corrente di clocks. Un clock è una unità di misura del tempo che è dipendente dalla piattaforma. La costante CLOCKS_PER_SEC (sempre in time.h) fornisce il numero di clocks per secondo. Così se si vuole misurare il numero di millisecondi dell'esecuzione di selectionsort() si può scrivere:

clock_t start, end;
start = clock();        // numero di clocks subito prima della chiamata
selectionsort(V, n);
end = clock();          // numero di clocks subito dopo la chiamata
        // tempo di esecuzione in millisecondi
double tempoEsecuzione = 1000*(((double)(end - start))/CLOCKS_PER_SEC);

Il tipo clock_t è un tipo intero senza segno definito in time.h.

Discussione degli esercizi 15 e 16. L'algoritmo della ricerca binaria: implementazione iterativa. Definizione ricorsiva di funzioni: fattoriale e ricerca binaria. Cenni sulla esecuzione di chiamate (ricorsive) di funzioni e sullo stack.
Allocazione dinamica della memoria: confronto con allocazione statica. Principali funzioni della libreria standard (stdlib.h): malloc(), free() e realloc(). Il tipo void *. L'operatore sizeof. Esempi:

• funzione char *duplicastr(char *str) che ritorna una copia (allocata dinamicamente) della stringa str.
• funzione char *inputlinestr() che ritorna in una stringa allocata dinamicamente la sequenza di caratteri letti dall'input (fino a EOF o '\n'). Uso di realloc().

Esercizio 17    Scrivere una funzione long long mcd(long long a, long long b) che ritorna il M.C.D. di a e b. La funzione deve implementare in modo ricorsivo l'algoritmo di Euclide per il calcolo del M.C.D.
Esercizio 18    Scrivere una funzione char *concat(char *s1, char *s2) che ritorna una nuova stringa che contiene la concatenazione delle stringhe s1 e s2. Ad esempio, se s1 = "Prima parte" e s2 = "Seconda parte" allora la funzione ritorna la stringa "Prima parteSeconda parte".

Discussione degli esercizi 17 e 18. Array multidimensionali: inizializzazione e rappresentazione in memoria. Esempi:

• funzione void maxrighe(int nr, int nc, float M[nr][nc], float maxR[]) che ritorna nell'array maxR i valori massimi delle righe della matrice M (che ha nr righe e nc colonne).
• funzione void magicsquare(int n, int Q[n][n]) che riempe la matrice nxn Q con un quadrato magico di ordine n (solo nel caso in cui n è dispari). La semplice regola per la costruzione di quadrati magici di ordine dispari è descritta qui.

Array di stringhe: funzione char **wordarray(char *text, int *pwords) che ritorna un array di stringhe, allocato dinamicamente, che contiene le parole contenute nella stringa text.
Esercizio 19    Scrivere una funzione int ismagicsquare(int n, int Q[n][n]) che verifica se Q è un quadrato magico. Se lo è ritorna la somma magica, altrimenti ritorna 0. La funzione non deve solamente verificare che le somme di tutte le righe, colonne e diagonali coincidono ma anche che tutti gli interi da 1 a n2 appaiono in Q.
Esercizio 20    Scrivere una funzione int *duparray(int V[], int n) che ritorna una copia dell'array V.
Esercizio 21    Scrivere una funzione void sortstrings(char *sA[], int n) che ordina (tramite strcmp()) l'array di stringhe sA.

Simulazione di prova intermedia: esercizi con soluzioni.

Prova intermedia: esercizi con soluzioni.

Aritmetica dei puntatori. Somma puntatore + intero: rappresentazione nella memoria. Sintassi delle parentesi quadre ed espressione equivalente nell'aritmetica dei puntatori. Tipi array e tipi puntatori. Conversione automatica del tipo array nel corrispondente tipo puntatore: le eccezioni dell'operatore di indirizzo & e dell'operatore sizeof. Array multidimensionali e interpretazione nell'aritmetica dei puntatori delle espressioni con parentesi quadre: puntatori ad array. I tipi T [n] (array di n elementi di tipo T), T [n][m] (array di n array ognuno di m int) e T (*)[n] (puntatore ad array di n int). Allocazione dinamica di matrici. Esempio,

• funzione int **allocmatrix(int nr, int nc) che ritorna l'indirizzo di una matrice di interi, allocata dinamicamente, con nr righe e nc colonne.

Come si disalloca la matrice allocata tramite la funzione allocmatrix().
Esercizio 22    Scrivere una funzione int **alloctrimatrix(int n, int val) che ritorna una matrice triangolare di interi, allocata dinamicamente, riempita con il valore val. Ad esempio, se n = 5 e val = 2 la matrice allocata deve essere:

2 2 2 2 2
2 2 2 2
2 2 2
2 2
2

Esercizio 23    Scrivere una funzione void freetrimatrix(int n, int **M) che disalloca la matrice M, precedentemente allocata tramite la funzione alloctrimatrix().

Discussione esercizi 22 e 23. Aritmetica dei puntatori: sottrazione puntatore - intero, differenza di puntatori e confronto di puntatori. Esempio: implementazione della funzione void *memmove(void *dst, void *src, int count) che copia il blocco di count bytes puntato da src nel blocco puntato da dst e ritorna dst.
Tipi aggregati: struct. Inizializzazione di struct, accesso ai campi (o membri). Rinominare tipi tramite typedef. Esempi, struct Carta { char seme; int valore; }:

• funzione void inizmazzo(Mazzo M) che inizializza il mazzo di carte M, dove Mazzo è il tipo dato da typedef Carta Mazzo[52];
• funzione void stampamazzo(Mazzo M) che stampa il mazzo di carte M.

Esercizio 24    Scrivere una funzione void mescolamazzo(Mazzo M, int ns) che mescola il mazzo M effettuando ns scambi di coppie di carte (scelte in modo pseudo-casuale tramite la funzione rand()).
Esercizio 25    Definire una struct Studente con campi: matricola, nome, cognome, num_esami. Scrivere una funzione int cerca(Studente stu[], int n, char *cog) che ritorna l'indice dello studente con cognome dato dalla stringa cog nell'array di Studente di dimensione n. Se non c'è nessun studente con quel cognome, ritorna -1.

Discussione esercizi 24 e 25. Esempi di struct che contengono altre struct. Assegnamento di struct. L'operatore sizeof applicato a struct. Puntatori a struct e la sintassi "freccia" per accedere ai campi. Le unioni (union): definizione e inizializzazione. Il sizeof di una union e rappresentazione in memoria. Enumerazioni (enum). L'istruzione di selezione switch - case e l'operatore condizionale ( ? : ). Esempio: funzione che stampa il valore e il seme di una struct Carta usando enumerazioni e switch - case.
Iniziata la discussione di un programma che gestisce (in memoria primaria) un piccolo archivio relativo ai dipendenti di una ipotetica azienda. Il programma dovrà permettere di effettuare almeno le seguenti operazioni: inserimento dei dati di un nuovo dipendente, stampa dei dati relativi a tutti i dipendenti e ricerca di un dipendente in base al cognome. Definizione della struct che rappresenta i dati relativi ad un dipendente:

typedef struct {
    int g, m, a;
} Data;

typedef enum {
    IMP,          // impiegato
    DIR,          // dirigente
    DIRSUP        // dirigente superiore
} Ruolo;    // ogni dipendente appartiene ad uno dei ruoli sopra specificati

#define MAXL_NOM    20      // massima lunghezza del nome
#define MAXL_COG    40      // massima lunghezza del cognome
#define MAXL_SEZ    20      // massima lunghezza del nome di una sezione
#define MAXL_DIP    30      // massima lunghezza del nome di un dipartimento

typedef struct {
    char      nome[MAXL_NOM + 1];         // stringa
    char      cognome[MAXL_COG + 1];      // stringa
    Data      nascita;
    Ruolo     ruolo;
    union {
        int     livello;       // solo per impiegati
        char    sezione[MAXL_SEZ + 1]; // solo per dirigenti (nome della sezione diretta)
        char    dipart[MAXL_DIP + 1];  // solo per dirigenti superiori (nome del dipartimento diretto)
    }         info;
} Dipendente;

Esercizio 26    Scrivere una funzione Dipendente inputDipendente() che legge dallo standard input i valori dei campi di una struct Dipendente e la ritorna.

Struttura del programma per gestire l'archivio dei dipendenti. Decomposizione del programma in due moduli:

• modulo che gestisce la memorizzazione dell'archivio (funzioni: void open_archivio(), void add_dipendente(Dipendente d), int num_dipendenti(), Dipendente get_dipendente(int i), void close_archivio())
• modulo che gestisce l'interazione con l'utente (funzioni: int main(), void inizio(), void aggiungi(), void stampa(), void ricerca(), void fine())

Vi è anche un modulo che contiene alcune funzioni di utilità (int input_line(char line[], int maxlen), int input_int(), char input_char()). Discussione dei vantaggi offerti da una tale decomposizione in moduli. Cenni sulla separazione interfaccia-implementazione. Uso delle direttive #ifndef - #endif per evitare che il contenuto di un file header (file .h) possa essere incluso più di una volta nello stesso file. Implementazione del modulo di memorizzazione (tramite un array, allocato dinamicamente). Implementazione dell'operazione che aggiunge un nuovo dipendente all'archivio (funzione aggiungi()) e di una funzione che stampa i dati di un singolo dipendente (void stampadip(Dipendente d)). Uso di puntatori ai campi di una struct.
Esercizio 27    Implementare la funzione void stampa(), usando la funzione stampadip() e le funzioni del modulo di memorizzazione. La funzione deve stampare i dati di tutti dipendenti presenti nell'archivio.
Esercizio 28    Implementare la funzione void ricerca(), usando la funzione stampadip() e le funzioni del modulo di memorizzazione. La funzione deve leggere un cognome dallo standard input e cercare nell'archivio un dipendente con quel cognome. Se è presente stampa tutti i dati di quel dipendente, altrimenti stampa "Non trovato".

Discussione degli esercizi 27 e 28. Le liste: rappresentazione in memoria, vantaggi e svantaggi rispetto agli array. Operazioni fondamentali sulle liste relativamente a liste di interi:

typedef struct Elem {
    int          val;
    struct Elem *next;
} Elem, *List;

Implementazione delle funzioni:

• List add_head(List L, int val) aggiunge un nuovo elemento con valore val in testa alla lista L (L è il puntatore al primo elemento della lista) e ritorna il puntatore alla lista così modificata.
• List add_tail(List L, int val) aggiunge un nuovo elemento con valore val in coda alla lista L e ritorna il puntatore alla lista così modificata.
• Elem *find(List L, int val) cerca nella lista L il primo elemento con valore val, se lo trova ritorna il puntatore all'elemento, altrimenti ritorna NULL.
• List delete(List L, int val) elimina dalla lista L, se presente, il primo elemento con valore val e ritorna il puntatore alla lista così modificata.

Implementazione del modulo di memorizzazione del programma che gestisce l'archivio dei dipendenti tramite una lista.
Esercizio 29    Scrivere una funzione List insord(List L, int val) che inserisce un nuovo elemento con valore val nella lista ordinata (in senso crescente) L, mantenendo l'ordinamento. Ritorna il puntatore alla lista dopo l'inserimento. Ad es., se L è la lista 1 -> 3 -> 6 -> 8 e val = 5 allora la funzione modifica la lista così 1 -> 3 -> 5 -> 6 -> 8.
Esercizio 30    Scrivere una funzione List inverti(List L) che inverte la lista L e ritorna il puntatore alla lista invertita. Ad es., se L è la lista 1 -> 2 -> 3 -> 4 allora la funzione la trasforma così 4 -> 3 -> 2 -> 1.

Discussione degli esercizi 29 e 30: versione iterativa e ricorsiva della funzione List inverti(List L). Algoritmo insertion-sort per ordinare una lista di interi. Funzione che disalloca una lista.
Esempio di uso di liste: programma che conta le parole distinte lette dallo standard input. Possibilità di usare la redirezione (operatore di redirezione < da terminale) per ridirigere lo standard input da file. Il programma usa una lista per mantenere le parole distinte finora trovate durante la lettura dell'input. Per migliorare l'efficienza le parole lette dall'input sono preliminarmente mantenute in un buffer (un array di stringhe) non troppo grande. Quando il buffer diventa pieno, le parole in esso contenute sono riversate nella lista. Per rendere efficiente quest'ultima operazione (che comporta, per ogni parola del buffer, il controllo che non sia già presente nella lista), la lista e il buffer sono mantenuti ordinati. In questo modo, l'operazione di riversamento è eseguita tramite una fusione delle stringhe del buffer con quelle della lista. Decomposizione del programma in funzioni:

#define WORDMAXLEN      100    // Massima lunghezza ammessa per le parole
#define BUFFERSIZE      150    // Dimensione del buffer delle parole

typedef struct WordElem {
    char *           word;   // Una stringa (parola)
    struct WordElem *next;
} WordElem, *WordList;

/* Legge una parola dallo standard input, la scrive nell'array word e ne ritorna
 * la lunghezza. Se la parola e' piu' lunga di maxlen, solamente i primi
 * maxlen caratteri sono scritti nell'array word, gli altri caratteri sono letti
 * ed ignorati. I caratteri scritti in word sono sempre terminati dal carattere
 * '\0', percio' l'array word deve avere dimensione almeno maxlen + 1. */
int input_word(char word[], int maxlen);
/* Inserisce nel array di stringhe wordBuf, ordinato e contenente n stringhe
 * (distinte), la stringa w, se non e' gia' presente. L'inserimento mantiene
 * l'ordinamemnto. Ritorna il numero di stringhe dopo l'inserimento. */
int insert(char *wordBuf[], int n, char *w);
/* Fonde le stringhe dell'array wordBuf, contenente n stringhe (parole) ordinate
 * e distinte, nella lista ordinata di stringhe (parole) L e ritorna il puntatore
 * alla lista dopo la fusione. La fusione mantiene la lista ordinata. */
WordList merge(WordList L, char *wordBuf[], int n);
/* Conta il numero di parole contenute nella list L */
int count(WordList L);

Implementazione del main del programma usando le funzioni sopra descritte.
Esercizio 31    Scrivere una funzione int uguali(WordList L1, WordList L2) che ritorna 1 o 0 a seconda che le due liste L1 e L2 siano uguali o meno. Uguali significa che le due liste hanno la stessa lunghezza e elementi in posizioni corrispondenti contengono stringhe uguali.
Esercizio 32    Scrivere una funzione WordList mergeList(WordList L1, WordList L2) che ritorna la fusione delle due liste ordinate L1 e L2. La funzione non deve né creare nuovi elementi né cancellare elementi esistenti. Ad esempio, se L1 = "a" -> "c" -> "hh" e L2 = "bb" -> "c" -> "m" -> "z" allora la lista ritornata è "a" -> "bb" -> "c" -> "c" -> "hh" -> "m" -> "z".

Discussione degli esercizi 31 e 32. Completata l'implementazione del programma che conta le parole distinte lette dallo standard input: implementazione delle funzioni int input_word(char word[], int maxlen), int insert(char *wordBuf[], int n, char *w), WordList merge(WordList L, char *wordBuf[], int n) e int count(WordList L). Dai siti Progetto Manuzio e Project Gutenberg si possono scaricare tantissimi libri, italiani e stranieri, in file di testo che possono essere dati in input al programma.
Il main con argomenti: int main(int argc, char *argv[]). Esempio: programma che prende come parametri una sequenza di numeri interi e ne stampa la somma. La funzione sscanf().
Puntatori a funzioni: definizione e spiegazione iniziale.
Esercizio 33    Modificare il programma che conta le parole distinte in modo tale che prenda come parametro (tramite il main) un intero k e stampi le k parole (distinte) più frequenti del testo letto dallo standard input.

Discussione esercizio 33. Puntatori a funzioni: definizione e uso (operatore &). Esempi:

• La funzione qsort() (in stdlib.h) e suo uso per ordinare array di int e array di stringhe.
• Funzione void apply(List L, void (*op)(Elem *)) che applica la funzione op() ad ogni elemento della lista di interi L.
• Uso dei puntatori a funzioni per la gestione di un menu testuale:

  typedef void (*OpFunc)();
  
  void menu(char *m[], OpFunc op[], int n)
  

Esercizio 34    Considerando il tipo:

typedef struct {
    char cognome[40];    //stringa
    char nome[20];
} Persona;

scrivere una funzione void sort_pers(Persona P[], int n) che ordina l'array P (di n elementi) tramite la funzione qsort().
Esercizio 35    Scrivere una funzione List filtro(List L, int (*f)(Elem *)) che elimina dalla lista di interi L gli elementi p tali che f(p) ≠ 0 e ritorna il puntatore alla lista modificata.

Discussione esercizi 34 e 35. File ad accesso sequenziale (file di testo) e file ad accesso casuale (file binari). Rappresentazione, da un punto di vista logico, di un file: il cursore e l'effetto delle operazioni di lettura/scrittura su di esso. Il riferimento ad un file aperto: la struct FILE. Le principali funzioni, della libreria standard (stdio.h), per la manipolazione dei files: fopen() (modalità di apertura), fclose(), rewind(), fgetc(), fputc(), fscanf(), fprintf(), fgets(). I riferimenti allo standard input (stdin) e allo standard output (stdout). Esempio: programma che prende come argomento del main il nome di un file (di testo) e permette all'utente di stampare a video le linee del file pagina per pagina (uso di fopen(), fgets() e fclose()).
Esercizio 36    Scrivere un porogramma che prende come argomenti i nomi di due file (di testo), legge tutte le parole contenute nel primo file memorizzandole in un array di stringhe, ordina l'array tramite qsort() e scrive nel secondo file le parole distinte (senza ripetizioni) e ordinate, una per linea. Si metta un limite di 100 caratteri sulla lunghezza delle parole.
Suggerimenti: il primo file va aperto in lettura ("r"), il secondo in scrittura ("w"), per leggere le parole modificare la funzione input_word() del programma che conta le parole distinte.

Discussione esercizio 36. Implementazione del modulo di memorizzazione del programma che gestisce un archivio di dipendenti tramite file di testo. Funzioni per il posizionamento del cursore dei files aperti: ftell(), fseek() e le costanti SEEK_SET, SEEK_CUR e SEEK_END. Differenze tra file binari e file di testo. Cenni sull'uso delle funzioni ftell() e fseek() in un programma che cerca una stringa in un file di testo.
Esercizio 37    Scrivere un funzione int filenumocc(FILE * f, char *s) che ritorna il numero di occorrenze della stringa s nel file di testo f.
Esercizio 38    Scrivere un programma che prende come argomenti (del main) i nomi di due file di testo e appende il contenuto del secondo file al primo file. Ad esempio, se il primo file contiene Testo primo file e il secondo file contiene Testo secondo file allora il programma modifica il primo file così Testo primo fileTesto secondo file.
Esercizio 39    Scrivere un programma che prende come argomenti (del main) i nomi di due file di testo e scrive nel secondo file una tabella delle frequenze dei caratteri del primo file. Ad esempio, se il primo file contiene "i promessi sposi" (file i_promes.txt sul sito Progetto Manuzio) allora il programma scrive la seguente tabella nel secondo file:

   0        0 |  32   217652 |  64 @      1 |  96 `      1 | 128        0 | 160        0 | 192        0 | 224     2003 |
   1        0 |  33 !   1497 |  65 A   1298 |  97 a 114953 | 129        0 | 161        0 | 193        0 | 225        1 |
   2        0 |  34 "    396 |  66 B    255 |  98 b   9793 | 130        0 | 162        0 | 194        0 | 226        0 |
   3        0 |  35 #      0 |  67 C   1119 |  99 c  47033 | 131        0 | 163        0 | 195        0 | 227        0 |
   4        0 |  36 $      0 |  68 D    730 | 100 d  37532 | 132        0 | 164        0 | 196        0 | 228        0 |
   5        0 |  37 %      0 |  69 E   1038 | 101 e 120014 | 133        0 | 165        0 | 197        0 | 229        0 |
   6        0 |  38 &      0 |  70 F    395 | 102 f  10422 | 134        0 | 166        0 | 198        0 | 230        0 |
   7        0 |  39 '   9958 |  71 G    412 | 103 g  17191 | 135        0 | 167        1 | 199        0 | 231        0 |
   8        0 |  40 (    190 |  72 H     80 | 104 h  13763 | 136        0 | 168        0 | 200       92 | 232     1365 |
   9        0 |  41 )    190 |  73 I    921 | 105 i  95745 | 137        0 | 169        0 | 201        0 | 233     1262 |
  10     2990 |  42 *     57 |  74 J      3 | 106 j     20 | 138        0 | 170        0 | 202        0 | 234        0 |
  11        0 |  43 +      0 |  75 K      1 | 107 k      1 | 139        0 | 171        0 | 203        0 | 235        0 |
  12        0 |  44 ,  26324 |  76 L   1199 | 108 l  56023 | 140        0 | 172        0 | 204        0 | 236     1435 |
  13     2990 |  45 -   4416 |  77 M   1034 | 109 m  23272 | 141        0 | 173        0 | 205        0 | 237        0 |
  14        0 |  46 .   9565 |  78 N    495 | 110 n  74385 | 142        0 | 174        0 | 206        0 | 238        0 |
  15        0 |  47 /     19 |  79 O    409 | 111 o  95944 | 143        0 | 175        0 | 207        0 | 239        0 |
  16        0 |  48 0     25 |  80 P    737 | 112 p  29741 | 144        0 | 176        0 | 208        0 | 240        0 |
  17        0 |  49 1     79 |  81 Q    373 | 113 q   7638 | 145        0 | 177        0 | 209        0 | 241        1 |
  18        0 |  50 2     48 |  82 R    916 | 114 r  66912 | 146        0 | 178        0 | 210        0 | 242     2743 |
  19        0 |  51 3     32 |  83 S    945 | 115 s  55175 | 147        0 | 179        0 | 211        0 | 243        0 |
  20        0 |  52 4     21 |  84 T    406 | 116 t  62265 | 148        0 | 180        0 | 212        0 | 244        0 |
  21        0 |  53 5     35 |  85 U    162 | 117 u  34650 | 149        0 | 181        0 | 213        0 | 245        0 |
  22        0 |  54 6     35 |  86 V    409 | 118 v  23183 | 150        0 | 182        0 | 214        0 | 246        0 |
  23        0 |  55 7     15 |  87 W      4 | 119 w     15 | 151        0 | 183        0 | 215        0 | 247        0 |
  24        0 |  56 8     18 |  88 X     62 | 120 x     16 | 152        0 | 184        0 | 216        0 | 248        0 |
  25        0 |  57 9     15 |  89 Y      0 | 121 y      8 | 153        0 | 185        0 | 217        0 | 249     1817 |
  26        0 |  58 :   2663 |  90 Z     15 | 122 z   7788 | 154        0 | 186        0 | 218        0 | 250        0 |
  27        0 |  59 ;   4017 |  91 [      0 | 123 {      0 | 155        0 | 187        0 | 219        0 | 251        0 |
  28        0 |  60 <      0 |  92 \      0 | 124 |      0 | 156        0 | 188        0 | 220        0 | 252        0 |
  29        0 |  61 =      0 |  93 ]      0 | 125 }      0 | 157        0 | 189        0 | 221        0 | 253        0 |
  30        0 |  62 >      0 |  94 ^      0 | 126 ~      0 | 158        0 | 190        0 | 222        0 | 254        0 |
  31        0 |  63 ?   1335 |  95 _      0 | 127        0 | 159        0 | 191        0 | 223        0 | 255        0 |

Discussione esercizi 37, 38 e 39. Funzioni per leggere e scrivere file binari: fread() e fwrite(). Implementazione del modulo di memorizzazione del programma che gestisce un archivio di dipendenti tramite file binari.
Descrizione generale delle strutture dati pila (stack) e coda (queue): usi tipici, operazioni fondamentali, implementazioni.
Esercizio 40    Scrivere un programma che prende come argomento il nome di un file e se non esiste lo crea e vi scrive il primo milione di numeri primi (in ordine crescente). Poi permette all'utente di inserire interi k e per ogni k stampa il k-esimo numero primo, leggendolo dal file. Il file è binario e i numeri primi sono memorizzati come int. Ad esempio, se l'utente inserisce k = 1 il programma stampa 2, se k = 1000 il programma stampa 7919 e se k = 1000000 il programma stampa 15485863.

Discussione esercizio 40. Esempio di uso di pile: valutazione di semplici formule booleane. Realizzazione di una piccola libreria per pile di caratteri: separazione interfaccia-implementazione. Implementazione tramite liste. Implementazione di una funzione int boolformula(char *formula), che valuta la formula booleana contenuta nella stringa formula, usando una pila di caratteri.
Esercizio 41    Modificare la funzione int boolformula(char *formula) per implementare una funzione int mod10formula(char *formula) che valuta semplici formule nell'aritmetica modulo 10. Tali formule sono formate dai caratteri '(', ')', '+', '*', '0', '1', ..., '9', dove gli operatori '+' e '*' sono la somma e la moltiplicazione modulo 10. Ad esempio, la formula 3 + (4*(2 + 6 + 9)*(1 + 9) + 6) ha valore 9.

Esercizi di preparazione alla prova scritta: esercizi con soluzioni.

Simulazione prova scritta: esercizi con soluzioni.