Programmazione I a.a. 2004/2005 (Canale P-Z) R. Silvestri e I. Salvo

Prova scritta - 8 settembre 2005

Per superare la prova è necessario (ma non sufficiente) ottenere almeno 7 punti per la soluzione dell'esercizio
obbligatorio. Gli altri tre esercizi sono a scelta. Il voto è la somma dei punti ottenuti.
Avvertenze: non usare variabili globali; definire tutte le eventuali funzioni ausiliarie usate; è consentito usare le
funzioni della libreria standard; se una soluzione non è scritta in modo chiaro ed ordinato non sarà presa
in considerazione.

Esercizio Obbligatorio (max 10 punti)

Si considerino i seguenti tipi:

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

typedef struct Odd {
int num;
long count;
struct Odd *next;
} Odd, *OList;

Scrivere una funzione, con prototipo OList GetOdd(List *pL), che rimuove dalla lista *pL tutti gli elementi che hanno
il campo num con valore dispari e crea una lista di tipo OList che per ogni numero dispari n presente nella lista di input ha un
elemento d tale che d.num = n e d.count è uguale al numero di elementi della lista di input che avevano il campo num con
valore n. Inoltre, la lista creata deve essere ordinata in senso crescente rispetto al campo num. La funzione ritorna il puntatore
alla lista creata, restituisce in *pL il puntatore alla lista di input modificata e rilascia la memoria non più usata.
Ad esempio, se la lista di input è {13} -> {24} -> {27} -> {11} -> {18} -> {27}, allora la funzione la
modifica così {24} -> {18} e crea la lista: {11, 1} -> {13, 1} -> {27, 2}.

Soluzione Esercizio Obbligatorio

/* Funzione ausiliaria che aggiorna la lista *pL con un valore x */

void Update(OList *pL, int x)
{
    while (*pL != NULL && (*pL)->num < x)    //Cerca la posizione per x
        pL = &((*pL)->next);
    if (*pL != NULL && (*pL)->num == x) //Se x e' gia' presente
        (*pL)->count++;                    //allora incrementa count.
    else {
        Odd *d = malloc(sizeof(Odd));        //Altrimenti, alloca un nuovo
        d->num = x;                        //elemento e inseriscilo nella
        d->count = 1;                        //lista.
        d->next = *pL;
        *pL = d;
    }
}

OList GetOdd(List *pL)
{
    OList oL = NULL;
    while (*pL != NULL) {        //Scorri gli elementi della lista
        if (((*pL)->num) % 2) == 1) {    //Se e' un elemento con numero dispari
            Elem *e = *pL;                //Salva il puntatore all'elemento
            Update(&oL, e->num);         //Aggiorna la nuova lista
            *pL = e->next;                //Sgancia l'elemento dalla lista
            free(e);                    //Rilascia la memoria dell'elemento
        } else pL = &((*pL)->next);
    }
    return oL;
}

Esercizio 1 (max 10 punti)

Scrivere una funzione, con prototipo void Chg(char *fname), che preso in input il nome (contenuto nella stringa fname) di
un file di tipo testo contenente una sequenza di caratteri 'A' e 'B', lo modifica sostituendo ogni carattere 'B' il cui carattere precedente
e quello successivo sia 'A' con un carattere 'A'. Siccome il file può essere molto grande la funzione non deve copiarlo in memoria.
Ad esempio se il file contiene la sequenza BAABABBAABAB allora la funzione lo modifica così BAAAABBAAAAB.

Soluzione Esercizio 1

/* Funzione ausiliaria che che scrive un carattere 'A' nella posizione p del file f
   e posiziona il cursore del file pronto per leggere il carattere in posizione p + 2 */
void WriteA(FILE *f, int p)
{
    rewind(f);
    while (p > 0) {    //Leggi i primi p - 1 caratteri
        fgetc(f);    //per arrivare alla posizione p
        p--;
    }
    fflush(f);
    fputc('A', f);    //Scrivi il carattere 'A'
    fflush(f);
    fgetc(f);           //Avanza di una posizione
}

void Chg(char *fname)
{
    int c, c1 = 'X', c2 = 'X', p = 0;
    FILE *f = fopen(fname, "r+");
    while ((c = fgetc(f)) != EOF) {
        if (c1 == 'A' && c2 == 'B' && c == 'A')
            WriteA(f, p - 1);
        c1 = c2;            //Aggiorna i due caratteri precedenti
        c2 = c;
        p++;                //incrementa la posizione
    }
    fclose(f);
}

Esercizio 2 (max 9 punti)

Scrivere una funzione, con prototipo void Frame(int n, char M[][n]), che presa in input una matrice quadrata nxn
di char, la riempe con cornici concentriche alternate di caratteri 'X' e 'O'. La cornice più esterna è sempre fatta con il carattere 'X'.
Ad esempio per n = 4 ed n = 5 la funzione produce, rispettivamente le seguenti matrici:

XXXX
XOOX
XOOX
XXXX

XXXXX
XOOOX
XOXOX
XOOOX
XXXXX

Soluzione Esercizio 2

void Frame(int n, char M[][n])
{
    int k = n;            //Dimensione della cornice piu' esterna
    int nC = (n + 1)/2; //Numero di cornici
    int i, j;
    char c = 'X';         //Carattere della cornice piu' esterna
    for (i = 0 ; i < nC ; i++) {
        for (j = i ; j < i + k ; j++) { //Scrivi l'i-esima cornice
            M[i][j] = c;
            M[i + k - 1][j] = c;
            M[j][i] = c;
            M[j][i + k - 1] = c;
        }
        k -= 2;                        //Dimensione della prossima cornice
        c = (c == 'X' ? 'O' : 'X');    //Carattere della prossima cornice
    }
}

Esercizio 3 (max 11 punti)

Si consideri il seguente tipo:
typedef struct Rec {
    char * info;            //stringa allocata dinamicamente
    int join;
    struct Rec *next;
} Rec, *RList;
Scrivere una funzione, con prototipo RList MJ(RList A, RList B), che modifica la lista A in modo tale che
per ogni elemento r di A se non ci sono elementi in B con valore del campo join uguale a r.join allora l'elemento r è rimosso,
altrimenti r è sostituito da tanti elementi quanti sono gli elementi s in B con s.join = r.join, il nuovo elemento t che
corrisponde all'elemento s in B è tale che t.join = r.join e t.info conterrà la concatenazione delle stringhe r.info
ed s.info. La funzione ritorna il puntatore alla lista A così modificata. La memoria non più usata deve essere rilasciata.
Ad esempio, se la lista A è {"blu", 3} -> {"red", 8} -> {"y", 3} -> {"verde", 5} e la lista B è
{"KM", 8} -> { "M", 3} -> {"L", 7} -> {"G", 8} -> {"KG", 3} allora la lista A è così modificata:
{"bluM", 3} -> {"bluKG", 3} -> {"redKM", 8} -> {"redG", 8} -> {"yM", 3} -> {"yKG", 3}.

Soluzione Esercizio 3

/* Funzione ausiliaria che cerca il primo elemento della lista L che ha il campo
join uguale a j. Se lo trova ne ritorna il puntatore, altrimenti ritorna NULL */

Rec *Find(RList L, int j)
{
    while (L != NULL && L->join != j) L = L->next;
    return L;
}

RList MJ(RList A, RList B)
{
    RList *pA = &A;       //pA e' il puntatore alla locazione contenente il puntatore
                          //all'elemento corrente.
    while (*pA != NULL) {    //Scorri gli elementi della lista A
        Rec *r, *cur = *pA, *s = B;
       while ((r = Find(s, cur->join)) != NULL) { //Finche' ci sono elementi in B
                                                   //con lo stesso valore di join.
            Rec *t = malloc(sizeof(Rec));    //Alloca un nuovo elemento
                                               //Alloca il campo info per contenere la
            t->info = malloc(strlen(cur->info) + strlen(r->info) + 1); //concatenazione.
            strcpy(t->info, cur->info);        //Copia la stringa cur->info
            strcat(t->info, r->info);        //Concatena la stringa r->info
            t->join = cur->join;
            t->next = cur->next;               //Aggancia il nuovo elemento alla lista A
            *pA = t;
            pA = &(t->next);
            s = r->next;
        }
        *pA = cur->next;                //Sgancia l'elemento corrente dalla lista A
        free(cur->info);                //Rilascia la memoria dell'elemento corrente
        free(cur);
    }
    return A;
}

Ritorna alla pagina del corso