Programmazione 1   (canale P-Z) a.a. 2007-08

Informazioni sul corso: programma, testi, modalità d'esame. 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: operatori aritmetici + e *, specifica di conversione della printf per gli interi.

Il tipo int. Variabili e memoria. Assegnamenti. Programma che calcola la 100-esima potenza di un numero. Istruzione di selezione: if () else. Operatori relazionali: <, <=, >, >=, ==, =. Programmi che stampano il massimo di due e di tre numeri: diverse versioni. Operatori logici: &, ||, !. Istruzioni per iterare: for ( ; ; ). Programma che stampa il massimo di 10 numeri.
Esercizio 1    Scrivere un programma che prende in input 3 numeri e li stampa in ordine crescente.
Esercizio 2    Scrivere un programma che prende in input 20 numeri e ne stampa la somma.

Discussione esercizi 1 e 2. Il tipo float. Programma che stampa la media di 10 numeri (in virgola mobile). Specifiche di conversione %f e %.2f. Operatore di divisione / e conversione automatica degli operandi. I tipi primitivi (int, short, long, unsigned, long long, char, unsigned char, float, double, long double) e loro proprietà (limits.h). Operatore sizeof(). Annidamento di cicli for: programma che stampa una matrice di nxn caratteri e alcune variazioni. Operatore di postincremento ++.
Esercizio 3    Scrivere un programma che prende in input un intero n e stampa una matrice nxn con una cornice di zeri e l'interno di uni.

Discussione esercizio 3. Istruzioni per iterare: while () e do while (). Equivalenza con il for. Programma che determina se un numero è primo (diverse versioni). Operatori %, +=, *=, /=, -=. Programma che prende in input interi positivi (termina non appena viene letto un intero non positivo) e stampa quanti di questi sono minori di 100, quanti compresi tra 100 e 1000 e quanti sono maggiori di 1000. Vettori (o array): dichiarazione ed inizializzazione. Programma che stampa le frequenze di 20 numeri.
Esercizio 4    Scrivere un programma che prende in input un intero n e lo stampa in base 2. Ad esempio, se n = 23 deve stampare 10111 (oppure 11101).

Discussione esercizio 4. Stringhe e carattere terminatore '\0'. Programma che prende in input una stringa e la stampa invertita. Specifica di conversione %s per scanf e per printf. Preprocessore C e la direttiva #define. Costanti simboliche. Programma che stampa le frequenze relative al lancio di un dado (simulato). Funzioni rand e srand in stdlib.h. Funzione time in time.h.
Esercizio 5    Scrivere un programma che prende in input 20 interi e determina se sono stati inseriti valori ripetuti. In caso affermativo stampa uno qualsiasi dei valori ripetuti, altrimenti stampa "non ci sono doppioni".

Discussione esercizio 5. Funzioni: definizione, prototipo, parametri, chiamate. Vari esempi di funzioni che prendono in input interi, vettori e stringhe. Files header, programmi su più files, la direttiva #include.
Esercizio 6    Scrivere una funzione che prende in input una stringa e un carattere e ritorna il numero di occorrenze del carattere nella stringa.

Discussione esercizio 6. Esempi di funzioni: ricerca lineare in un vettore, funzione che scambia i valori di due variabili. Passaggio di parametri per valore e per indirizzo. Operatore di indirizzo & e operatore di indirezione *. Tipi puntatore. Macro. Funzione che legge in input una stringa tramite getchar.
Esercizio 7    Scrivere una funzione che prende in input due stringhe s1 e s2 e ritorna 1 se s1 è un anagramma di s2 e ritorna 0 altrimenti. Ad esempio, "torre" è un anagramma di "retro".

Discussione esercizio 7. Funzione che ritorna il numero di parole in una stringa: funzione isalpha in ctype.h e uso di una variabile flag. Programma che legge in input una stringa e stampa il numero di parole della stringa: uso di funzioni in un programma e leggibilità del codice. Istruzione break. Operatore condizionale ( ? ; ). Cenni sulla conversione forzata dei tipi, cast.
Esercizio 8    Scrivere una funzione che prende in input una stringa e ritorna la lunghezza della più lunga parola nella stringa (se non ci sono parole ritorna 0). Ad esempio se la stringa è "C'e' un errore nel programma", la funzione ritorna 9.

Discussione esercizio 8. Ordinamento: selection-sort e bubble-sort. Funzioni ricorsive: fattoriale, potenza, fibonacci, selection-sort.
Esercizio 9    Scrivere un programma che prende in input una stringa, ne ordina i caratteri e stampa il risultato. Ad esempio, se la stringa è "trova errore" allora il programma stampa " aeeoorrrrtv".

Discussione esercizio 9. Insertion-sort: versione iterativa e ricorsiva. Ricerca binaria: versione iterativa e ricorsiva. Vettori multidimensionali ovvero vettori di vettori: dichiarazione, inizializzazione, rappresentazione in memoria. Passaggio di vettori multidimensionali a funzioni.
Esercizio 10    Scrivere una versione modificata della ricerca binaria che, nel caso il valore cercato non appaia nel vettore di input, ritorna la posizione in cui tale valore andrebbe inserito per mantenere ordinato il vettore.

Discussione esercizio 10. Esempi di uso di vettori multidimensionali: funzione che costruisce quadrati magici di ordine dispari. Vettori di stringhe. Allocazione dinamica della memoria: il tipo void *, le funzioni malloc() e free() la costante NULL. Esempio: programma che prende in input un testo e lo memorizza tramite un vettore di stringhe, una stringa per ogni linea del testo. Uso della costante EOF e il comando di redirezione di Linux < per fornire un file come input al programma.
Esercizio 11    Scrivere una funzione che prende in input una matrice nxn di interi e ritorna 1 se è un quadrato magico e 0 altrimenti.
Esercizio 12    Scrivere un programma che prende in input un testo e stampa le linee del testo ordinate alfabeticamente (si usi la funzione strcmp() per confrontare due stringhe).

Discussione esercizi 11 e 12. Esempi di allocazione dinamica. Funzione che duplica una stringa. Funzione che legge in input una stringa di lunghezza arbitraria: la funzione realloc(). Aritmetica dei puntatori: addizione e sottrazione di un puntatore e un intero, differenza tra due puntatori. La sintassi delle parentesi quadre per i vettori espressa tramite l'aritmetica dei puntatori.

Aritmetica dei puntatori: confronto di puntatori. Esempio: implementazioni della funzione memmove(). Il tipo "vettore di T" e il tipo "puntatore a T": conversione automatica e comportamento degli operatori sizeof e &. L'aritmetica dei puntatori per i vettori multidimensionali. Allocazione dinamica di matrici. Rinominare tipi tramite typedef.

Discussione soluzioni esercizi della prova intermedia. Tipi aggregati: struct. Dichiarazione e inizializzazione di struct. Uso di typedef. Esempio: mazzo di carte.
Esercizio 13    Scrivere una funzione, int ControllaMazzo(Mazzo M), che controlla che le carte del mazzo M siano giuste (cioè, ci siano tutte e senza ripetizioni).

Discussione esercizio 13. Tipi aggregati: union. Dichiarazione ed inizializzazione di unioni. Il tipo enumerativo enum. Il costrutto switch - case. Esempio che illustra l'uso di struct, union, enum, switch - case e variabili globali: programma che gestisce un archivio dei dati relativi a dipendenti tramite le operazioni di inserimento, stampa, ricerca, eliminazione e modifica.
Esercizio 14    Completare l'implementazione della funzione void Inserisci(void).

Discussione esercizio 14. Completata l'implementazione del programma archivio. Strutture dati dinamiche: liste. Possibili applicazioni delle liste e vantaggi rispetto ai vettori. Esempi relativamente a liste di interi: inserimento in testa, ricerca ed eliminazione di un elemento.
Esercizio 15    Scrivere una funzione che inserisce un nuovo elemento in una lista di interi ordinata.

Discussione esercizio 15. Implementazione della funzione dell'esercizio tramite la tecnica del "doppio puntatore". Cenni sulla progettazione e realizzazione di librerie: interfaccia, e indipendenza dell'interfaccia dall'implementazione. Esempio: piccola libreria per gestire insiemi di stringhe: interfaccia (funzioni SetCreate, SetAdd, SetFind, SetDel, SetDestroy. Implementazione tramite liste: SetCreate e SetAdd).
Esercizio 16    Implementare SetFind.

Discussione esercizio 16. Implementazione di SetFind, SetDel, SetDestroy. Funzione che permette di scandire un insieme di stringhe: uso di variabili locali static. Esempio di utilizzo della libreria: funzione che stampa le stringhe in comune tra due insiemi di stringhe. Inversione di una lista: versione ricorsiva e iterativa.
Esercizio 17    Utilizzare la libreria per scrivere una funzione che prende in input due insiemi di stringhe e ritorna 1 se i due insiemi sono uguali e 0 altrimenti.

Discussione esercizio 17. I file: file di testo (sequenziali) e file binari (ad accesso casuale). Posizione del cursore e operazioni di lettura e scrittura. Apertura di un file: funzioni fopen e fclose. Funzioni per leggere e scrivere in file di testo: fgetc, fgets, fscanf, fputs, fprintf. Standard input stdin e standard output stdout. Funzioni per il riposizionamento e la lettura del cursore: rewind, fseek, ftell. Esempio: programma che prende in input il nome di un file di testo, lo apre (se non esiste lo crea), stampa a video il contenuto del file e poi prende in input una stringa e la aggiunge come ultima linea nel file.
Esercizio 18    Scrivere un programma che prende in input il nome di un file e una stringa, e poi cerca la stringa nel file, se la trova stampa "trovata" altrimenti stampa "non trovata".

Discussione esercizio 18. Varie versioni di una funzione che cerca una stringa in un file di testo e se la trova ne ritorna la posizione. File binari: uso di fseek, le funzioni di lettura e scrittura fread e fwrite.
Esercizio 19    Scrivere una funzione che prende in input il puntatore ad un file e una stringa e ritorna il numero di occorrenze della stringa nel file.

Discussione esercizio 19. File binari (o ad accesso casuale): usi tipici e portabilità. Esempio: programma che gestisce un archivio mantenuto in un file binario con operazioni: STAMPA, INSERISCI, RICERCA, MODIFICA e ELIMINA. Iniziata implementazione: main, dichiarazioni dei tipi, funzione che conta i records nel file-archivio e funzione che apre il file-archivio.
Esercizio 20    Scrivere la funzione che implementa la stampa dei records dell'archivio in forma tabellare.

Discussione esercizio 20. Implementazione delle operazioni INSERISCI, RICERCA e MODIFICA.
Esercizio 21    Scrivere la funzione che implementa l'operazione ELIMINA.

Discussione esercizio 21. Ricapitolazione delle regole di visibilità delle variabili e delle funzioni. Programmi su più files: qualificatore static usato in riferimento a funzioni, qualificatore extern. Rispiegazione di alcuni concetti: allocazione dinamica (malloc, realloc e free), liste e la tecnica del "doppio puntatore".