Fondamenti di Programmazione     a.a. 2011-2012
Esercizi di preparazione alla prova scritta
Avvertenze: non usare variabili globali; definire tutte le funzione ausiliarie usate; è consentito usare le funzioni della libreria standard; se una soluzione non è scritta in modo chiaro ed ordinato non sarà presa in considerazione.
Per chi fa solamente una parte: i punteggi degli esercizi sono da intendersi raddoppiati.
Per chi fa entrambe le parti: per raggiungere la sufficienza deve ottenere almeno 8 punti sulla Prima Parte e almeno 8 punti sulla Seconda Parte.

PRIMA PARTE
Esercizio 1 (max 6 punti)
Scrivere una funzione void nearest(double val[], int n, int *pi, int *pj) che preso in input un array val di n valori numerici restituisce in *pi e *pj gli indici della coppia di valori più vicini. Si può assumere che n è almeno 2. Se c'è più di una coppia a distanza minima, la funzione ne ritorna una qualsiasi. Ad esempio, se val = {-4.7, 1.5, 2.0, -6.1, 0.8, 2.4, -5.9, -3.5} (n = 8), allora la funzione restituisce la coppia di indici 3, 6. Se val = {1.2, 5.6, 1.2, 5.6}, restituisce o la coppia 0, 2 o la coppia 1, 3.
Esercizio 2 (max 8 punti)
Scrivere una funzione int subpal(char *str) che ritorna la lunghezza della più lunga sottostringa palindroma della stringa str. Ad esempio, se str = "usa radar astrali", ritorna 11 (la lunghezza della sottostringa "sa radar as"), se invece str = "antina", ritorna 1.
Esercizio 3 (max 10 punti)
Scrivere una funzione int *eqrowcol(int n, char M[n][n], int *cnt) che presa in input una matrice M di n×n caratteri, ritorna, in un array allocato dinamicamente, gli indici i tali che la riga i e la colonna i della matrice M sono uguali, inoltre in *cnt restituisce il numero di tali indici. L'array ritornato non deve essere più grande del necessario. Ad esempio se la matrice M è
    TORTA
    OLOIM
    ROTTA
    TUTTA
    ASAIR
(quindi n = 5), allora la funzione ritorna un array con due elementi contenente {0, 2} e in *cnt restituisce 2.
SECONDA PARTE
Esercizio 4 (max 6 punti)
Si consideri il seguente tipo:
typedef struct Elem {
    int          val;
    struct Elem *next;
} Elem, *List;
Scrivere una funzione List insarray(List L, int k, int A[], int n) che modifica la lista di interi L inserendo, immediatamente prima del k-esimo elemento di L, n nuovi elementi con valori dati dall'array A e ritorna la lista modificata. La numerazione degli elementi della lista inizia da zero, se la lista non ha il k-esimo elemento, i nuovi elementi sono aggiunti in coda. Ad esempio, se L è 10 -> 11-> 12 -> 13 e A = {1, 2} (quindi n = 2), ecco come è modificata la lista per diversi valori di k:
k = 0     1 -> 2 -> 10 -> 11-> 12 -> 13
k = 2     10 -> 11-> 1 -> 2 -> 12 -> 13
k = 6     10 -> 11-> 12 -> 13 -> 1 -> 2
Esercizio 5 (max 8 punti)
Scrivere una funzione void fcutlines(char *fname1, char *fname2, int i, int n) che presi in input i nomi di due file di testo (nelle stringhe fname1 e fname2), scrive nel secondo file il contenuto del primo file eccetto le n linee consecutive che iniziano dalla i-esima linea del primo file. La numerazione delle linee inizia da zero. Se il primo file ha meno di i+1 linee, il file è scritto tale e quale nel secondo file. Si assume che ogni linea abbia al più 100 caratteri (compreso il carattere newline). Ecco alcuni esempi:
Primo file       i = 0, n = 2    i = 2, n = 2    i = 2  n = 6    i = 5  n = 2
linea zero       linea due       linea zero      linea zero      linea zero
linea uno        linea tre       linea uno       linea uno       linea uno
linea due        linea quattro   linea quattro                   linea due
linea tre                                                        linea tre
linea quattro                                                    linea quattro
Esercizio 6 (max 10 punti)
Si consideri il tipo:
typedef struct MElem {
    int           val;
    long          count;
    struct MElem *next;
} MElem, *MSet;
Scrivere una funzione void compact_ms(MSet M) che elimina dalla lista M ogni elemento x per cui esiste un elemento y che precede x e che ha lo stesso valore del campo val (cioè x.val = y.val), inoltre ogni elemento y non eliminato dovrà contenere nel campo count la somma dei campi count di tutti gli elementi che nella lista originale hanno lo stesso valore del campo val di y. L'ordine degli elementi non deve essere cambiato, il puntatore al primo elemento non deve essere modificato e la memoria degli elementi elminati deve essere rilasciata. Ad esempio, se la lista M è
{123, 2} -> {456, 1} -> {123, 1} -> {222, 5} -> {222, 3} -> {123, 8}
allora la funzione modifica la lista così
{123, 11} -> {456, 1} -> {222, 8}