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

Prova scritta del 25 gennaio 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 Book {
long codB;
long codP;
struct Book *next;
} Book, *LBook;

typedef struct Pub {
long codP;
long info;
struct Pub *next;
} Pub, *LPub;

typedef struct BP {
long codP;
long codB;
long info;
struct BP *next;
} BP, *LBP;

Scrivere una funzione, con prototipo LBP Join(LBook Lb, LPub Lp), che crea una nuova lista con elementi di tipo BP contenente
tutti e soli gli elementi bp per cui esistono un elemento b nella lista Lb e un elemento p nella lista Lp tali che
bp.codP = b.codP = p.codP, bp.codB = b.codB e bp.info = p.info.
Si assume che nella lista Lb non ci siano due elementi con lo stesso valore del campo codB e che nella lista Lp non ci siano due elementi
con lo stesso valore del campo codP. Questo implica che nella lista creata non ci saranno due elementi con la stessa coppia di valori nei
campi codB e codP. Ad esempio se la lista Lb è {13, 233} -> {7, 345} -> {15, 233} e la lista Lp è
{432, 1006} -> {233, 1245} -> {345, 1450} allora la lista creata sarà
{233, 13, 1245} -> {345, 7, 1450} -> {233, 15, 1245}.

Soluzione Esercizio Obbligatorio

LBP Join(LBook Lb, LPub Lp)
{
    LBP L = NULL;
    Book *b = Lb;
    while (b != NULL) {                        //Scorri la lista Lb e per ogni suo
        Pub *p = Lp;                             //elemento scorri la lista Lp alla
        while (p != NULL && p->codP != b->codP) //ricerca di un elemento con lo
            p = p->next;                        //stesso codP.
        if (p != NULL) {                    //Se esiste allora
            BP *bp = malloc(sizeof(BP));    //aggiungi un elemento alla nuova lista.
            bp->codP = p->codP;
            bp->codB = b->codB;
            bp->info = p->info;
            bp->next = L;
            L = bp;
        }
        b = b->next;
    }
    return L;
}

Esercizio 1 (max 8 punti)

Si consideri il seguente tipo:
typedef struct Elem {
long val;
struct Elem *next;
} Elem, *List;
Scrivere una funzione, con prototipo void Agg(List L), che modifica i valori dei campi val degli elementi della lista L in modo tale
che il valore del campo val di un elemento m sia pari alla somma dei (vecchi) valori dei campi val dell'elemento m e degli elementi
successivi che sono interi dispari. Ad esempio se la sequenza dei valori dei campi val della lista era 2, 5, 8, 3, 2, 4 allora la
funzione la modifica così 10, 8, 11, 3, 2, 4.

Soluzione Esercizio 1

/* Funzione ausiliaria che ritorna la somma dei valori dei campi val degli elementi della
lista L che sono interi dispari.                                                    */
long Som(List L)
{
    if (L == NULL) return 0;
    else return (L->val % 2 == 1 ? L->val : 0) + Som(L->next);
}

void Agg(List L)
{
    while (L != NULL) {
        L->val += Som(L->next);
        L = L->next;
    }
}

Esercizio 2 (max 10 punti)

Scrivere una funzione, con prototipo int Inv(char *nameF, char *invF), che legge il file di tipo testo il cui nome è nella
stringa nameF, contenente una sequenza di stringhe separate da spazi, e crea un nuovo file di testo, con nome dato dalla stringa invF,
scrivendoci la sequenza inversa e ritorna la massima lunghezza delle stringhe. Le stringhe hanno una lunghezza non superiore a 100.
Ad esempio se il file nameF contiene la sequenza giallo verde blu allora il nuovo file deve contenere
blu verde giallo e la funzione deve ritornare 6.

Soluzione Esercizio 2

/* Funzione ausiliaria che ritorna la k-esima stringa del file f. Se tale stringa
non esiste ritorna NULL                                                        */
const char *KthStr(FILE *f, int k)
{
    static char str[101];
    rewind(f);
    while (k > 0 && fscanf(f, "%s", str) == 1) k--;
    return (k == 0 ? str : NULL);
}
int Inv(char *nameF, char *invF)
{
    FILE *f = fopen(nameF, "r");        //Apri il file in lettura
    FILE *newF = fopen(invF, "w+");     //Crea ed apri il nuovo file
    int nStr = 0, max = 0;
    char str[101];                            //Calcola il numero di stringhe
    while (fscanf(f, "%s", str) == 1) nStr++;
    while (nStr > 0) {                        //A partire dall'ultima stringa,
        const char *s = KthStr(f, nStr);    //leggi le stringhe in ordine inverso
        int len = strlen(s);                //e scrivile nel nuovo file,
        if (len > max) max = len;            //aggiornando il calcolo della
        fprintf(newF, "%s ", s);            //lunghezza massima.
        nStr--;
    }
    fclose(f);
    fclose(newF);
    return max;
}

Esercizio 3 (max 12 punti)

Scrivere una funzione, con prototipo char *Coll(char **strVec, long n, long *newN), che preso in input
un vettore di n stringhe strVec elimina da esso compattandolo tutte le stringhe s per cui c'è almeno una stringa successiva t tale
che strcmp(s, t) <= 0, crea e ritorna una stringa formata dalla concatenazione di tutte le stringhe eliminate ma senza
ripetizioni e restituisce in *newN il numero di stringhe rimaste nel vettore. La memoria delle stringhe eliminate deve essere
rilasciata e la stringa ritornata non deve usare più memoria del necessario. Ad esempio se strVec è
["red", "green", "red", "redskin", "blu", "green", "blu"] (quindi n = 7) allora la funzione
lo modifica così ["redskin", "green", "blu"], ritorna la stringa "redgreenblu" e restituisce 3 in *newN.

Soluzione Esercizio 3

/* Funzione ausiliaria che ritorna vero se la stringa in posizione k e' da
   eliminare. */
short IsDel(char **V, long n, long k)
{
    long i = k + 1;
    while (i < n && strcmp(V[k], V[i]) > 0) i++;
    return (i < n);
}
/* Funzione ausiliaria che ritorna vero se la stringa in posizione k ha un
duplicato in una posizione precedente. */
short IsDup(char **V, long k)
{
    long i = 0;
    while (i < k && strcmp(V[k], V[i]) == 0) i++;
    return (i < k);
}
/* Funzione ausiliaria che elimina dal vettore V la stringa in posizione k
   e compatta il vettore. */
void Compact(char **V, long n, long k)
{
    free(V[k]);
    for ( ; k < n - 1 ; k++) V[k] = V[k + 1];
}

char *Coll(char **strVec, long n, long *newN)
{
    long k, len = 0;                                //Calcola la somma delle
    for (k = 0 ; k < n ; k++)                     //lunghezze delle stringhe
        if (IsDel(strVec, n, k) && !IsDup(strVec, k)) //da eliminare senza
            len += strlen(strVec[k]);                //ripetizioni.
    char *newStr = malloc((len + 1)*sizeof(char));    //Alloca la nuova stringa e
    newStr[0] = '\0';                                //concatena le stringhe da
    for (k = 0 ; k < n ; k++)                        //eliminare senza ripetizioni.
       if (IsDel(strVec, n, k) && !IsDup(strVec, k))
           strcat(newStr, V[k]);
    k = 0;
    while (k < n) {                                    //Scorri il vettore ed
        if (IsDel(strVec, n, k)) {                    //elimina le stringhe
            Compact(strVec, n, k);                    //compattando il vettore.
            n--;
        } else k++;
    }
    *newN = n;
    return newStr;
}

Ritorna alla pagina del corso