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

Prova scritta del 23 febbraio 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 consideri il seguente tipo:
typedef struct VStr {
    long         val;
    char *       str;        //stringa allocata dinamicamente
    struct VStr *next;
} VStr, *LStr;
Scrivere una funzione, con prototipo int Comp(LStr L), che presa in input la lista L, ordinata in senso non decrescente rispetto
al campo val, la modifica in modo tale che elementi consecutivi che hanno lo stesso valore del campo val sono sostituiti da un
elemento il cui valore del campo val è lo stesso e il campo str è la stringa prodotta dalla concatenazione, nell'ordine, delle stringhe
degli elementi sostituiti. La funzione ritorna il numero massimo di elementi con lo stesso valore del campo val. Inoltre la funzione
non deve modificare il puntatore al primo elemento. La memoria non più usata deve essere rilasciata e i nuovi blocchi di memoria non
devono essere più grandi del necessario. Ad esempio se la lista è
{5, "AA"} -> {5, "BBB"} -> {7, "C"} -> {8, "D"} -> {8, "GG"} -> {8, "F"} allora la funzione
la modifica così {5, "AABBB"} -> {7, "C"} -> {8, "DGGF"} e ritorna 3.

Soluzione Esercizio Obbligatorio

int Comp(LStr L)
{
    int max = 0, count = 0;
    LStr prev = NULL;                    //Manterra' il puntatore al primo elemento
    long val;                            //di una sequenza di elementi da sostituire.  
    while (L != NULL) {
        if (prev != NULL && val == L->val) {     //Se e' un elemento  di una sequenza
            int newLen = strlen(prev->str) + strlen(L->str);   //di elementi da sost.
            prev->str = realloc(prev->str, (newLen + 1)*sizeof(char));
            strcat(prev->str, L->str);           //Rialloca un blocco sufficiente per
            prev->next = L->next;                //mantenere la concatenazione.
            free(L->str);                        //Sgancia l'elemento dalla lista e
            free(L);                             //rilascia la memoria della stringa
            L = prev->next;                      //e dell'elemento.
            count++;
        } else {
            if (count > max) max = count;
            count = 1;
            val = L->val;
            prev = L;
            L = L->next;
        }
    }
    if (count > max) max = count;
    return max;
}

Esercizio 1    (max 9 punti)

Scrivere una funzione, con prototipo int Cm(long A[], long B[], int n), che ritorna il numero di valori distinti che
sono presenti sia nel vettore A che nel vettore B (entrambi i vettori hanno dimensione n). Ad esempio se n = 7 e
A = [3,4,3,5,2,2,8] e  B = [7,4,4,2,6,3,5] allora la funzione ritorna 4.

Soluzione Esercizio 1

int Cm(long A[], long B[], int n)
{
    int i, count = 0;
    for (i = 0 ; i < n ; i++) {
        int j = 0, found = 0;
        while (j < i && !found) {          //Controlla che sia la prima occorrenza
            if (A[j] == A[i]) found = 1;   //del valore A[i] nel vettore A.
            j++;
        }
        if (!found) {                      //Se e' la prima occcorrenza controlla
            j = 0;                         //se e' presente anche in B.
            while (j < n && !found) {
                if (B[j] == A[i]) {
                    count++;
                    found = 1;
                }
                j++;
            }
        }
    }
    return count;
}

Esercizio 2    (max 9 punti)

Scrivere una funzione, con prototipo long Clean(char *srcF, char *dstF), che preso in input un file di tipo testo, il cui
nome è nella stringa srcF, contenente una sequenza di numeri interi separati da spazi, crea un nuovo file, il cui nome è nella stringa
dstF, e vi scrive, nell'ordine, i numeri del file srcF ma senza ripetizioni. La funzione ritorna la somma dei numeri scritti nel nuovo file.
La funzione non deve copiare in memoria il contenuto del file. Ad esempio se il file srcF contiene 5 -3 11 5 8 8 -3 allora la
funzione scrive nel nuovo file 5 -3 11 8 e ritorna 21.

Soluzione Esercizio 2

/* Funzione ausiliaria che ritorna vero se nel file f è presente l'intero n. */
short IsPresent(FILE *f, int n)
{
    rewind(f);
    int k;
    while (fscanf(f, "%d", &k) == 1)
        if (k == n) return 1;
    return 0;
}
long Clean(char *srcF, char *dstF)
{
    FILE *src = fopen(srcF, "r");        //Apri il file in lettura
    FILE *dst = fopen(dstF, "w+");       //Crea ed apri il nuovo file
    long sum = 0;
    int n;
    while (fscanf(src, "%d", &n) == 1) {    //Leggi uno ad uno i numeri dal file
        if (!IsPresent(dst, n)) {        //Se il numero non e' gia' stato scritto
            fseek(dst, 0, SEEK_END);     //Posizionati alla fine del nuovo file
            fprintf(dst, "%d ", n);      //Scrivi il numero
            sum += n;
        }
    }
    fclose(src);
    fclose(dst);
    return sum;
}

Esercizio 3    (max 12 punti)

Si consideri il seguente tipo:  
typedef struct Elem {
    int          num;
    struct Elem *next;
} Elem, *List;
Scrivere una funzione, con prototipo int SymDiff(List *pA, List B), che modifica la lista *pA così che diventi uguale
alla differenza simmetrica delle liste di partenza *pA e B. Vale a dire che la lista modificata deve contenere esattamente quegli elementi
che appartenevano a *pA ma non appartengono a B uniti con quegli elementi che appartengono a B ma che non appartenevano a *pA.
La funzione ritorna il numero di elementi che appartenevano ad entrambe le liste di partenza. Si assuma che tutti gli elementi di *pA
sono distinti e che lo stesso valga per la lista B. La funzione non deve modificare la lista B. La memoria degli elementi eliminati deve
essere rilasciata. Ad esempio se la lista *pA è 8 -> 5 -> 2 -> 7 -> 9 e la lista B è 3 -> 8 -> 7 allora la funzione
modifica la lista *pA così 5 -> 2 -> 9 -> 3 (l'ordine non ha importanza) e ritorna 2.

Soluzione Esercizio 3

/* Funzione ausiliaria che ritorna vero se nella lista L e' presente un elemento con
   valore del campo num pari ad n.                                                  */
short IsPresent(List L, int n)
{
    while (L != NULL && L->num != n) L = L->next;
    return (L != NULL);
}
int SymDiff(List *pA, List B)
{
    List BnoA = NULL;
    List L = B;
    int count = 0;
    while (L != NULL) {                        //Costruisci la lista degli elementi
        if (!IsPresent(*pA, L->num)) {         //che appartengono a B ma che non
            Elem *e = malloc(sizeof(Elem));    //appartengono a *pA.
            e->num = L->num;                   //Nel comtempo conta gli elementi
            e->next = BnoA;                    //in comune tra le due liste.
            BnoA = e;
        } else count++;
        L = L->next;
    }
    List *p = pA;
    while (*p != NULL) {                       //Elimina da *pA gli elementi che
        if (IsPresent(B, (*p)->num)) {         //appartengono anche a B.
            Elem *e = *p;
            *p = (*p)->next;
            free(e);
        } else p = &((*p)->next);
    }
    p = pA;                                    //Concatena cio' che rimane di *pA
    while (*p != NULL) p = &((*p)->next);      //con la lista precedentemente
    *p = BnoA;                                 //costruita.  
    return count;                               
}



 Ritorna alla pagina del corso