Programmazione I a.a. 2002/2003 (Canale P-Z) R. Silvestri e A. Sterbini

Scritto del 15 gennaio 2003 con Soluzioni

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 1 (max 12 punti)

Si consideri il tipo Record così definito:
typedef struct {
    char                 descr[40];
    long                 inv;
    struct {
        long     prot;
        short    ind;
    }                    sub;
} Record;
Scrivere una funzione che prese in input due stringhe fArch ed fAgg aggiunge al file di nome fArch tutti i record del file di nome
fAgg che non sono già presenti nel file fArch e ritorna il numero di record aggiunti. Si assume che entrambi i file siano di tipo binario
e che contengano record di tipo Record. Il prototipo della funzione è long AggArchivio(char *fArch, char *fAgg).
La funzione deve garantire che se il file fArch non conteneva inizialmente duplicati anche dopo l'esecuzione della funzione AggArchivio
il file arch non deve contenere duplicati. Due record si considerano uguali solo se campo per campo hanno lo stesso valore. Si tenga
presente che il campo descr contiene sempre una stringa.

Soluzione Esercizio 1

/* Funzione ausiliaria che ritorna un intero diverso da 0 se i due *
* record r1 ed r2 sono uguali e 0 altrimenti.                     */
short RecUguali(const Record *r1, const Record *r2)
{
    if (strcmp(r1->descr, r2->descr) != 0) return 0;
    else if (r1->inv != r2->inv) return 0;
    else if (r1->sub.prot != r2->sub.prot) return 0;
    else if (r1->sub.ind != r2->sub.ind) return 0;
    else return 1;
}

/* Funzione ausiliaria che ritorna un intero diverso da 0 se il record *
* r e' presente nel file f e 0 altrimenti.                            */
short TrovaRec(FILE *f, Record *r)
{
    short trovato = 0;
    fseek(f, 0, SEEK_SET);       /* Imposta la posizione del file all'inizio */
    while (!feof(f) && !trovato) { /* Finche' non e' stata raggiunta la fine del file */
        Record r;                   /* e il record di input non e' stato trovato.      */
        fread(&r, sizeof(r), 1, f);    /* Leggi il prossimo record e confrontalo */
        trovato = RecUguali(p, &r);    /* con il record di input.                */
    }
    return trovato;
}

/* Funzione ausiliaria che aggiunge il record r al file f */
void AggRec(FILE *f, const Record *r)
{
fseek(f, 0, SEEK_END); /* Imposta la posizione del file alla fine */
fwrite(r, sizeof(Record), 1, f); /* Scrivi il record */
}

long AggArchivio(char *fArch, char *fAgg)
{
    long nRecAgg = 0;
    FILE *arch = fopen(fArch, "r+b");    /* Apri il file archivio */
    FILE *agg = fopen(fAgg, "rb");       /* Apri il file di aggiornamento */
    while (!feof(agg)) {
        Record rec;
                 /* Leggi il prossimo record del file di aggiornamento */
        fread(&rec, sizeof(rec), 1, agg);
        if (!TrovaRec(arch, &rec)) { /* Se il record non e' presente nel file archivio, */
            AggRec(arch, &rec);       /* aggiungilo al file archivio.                    */
            nRecAgg++;
        }
    }
    fclose(arch);
    fclose(agg);
    return nRecAgg;
}

Esercizio 2 (max 10 punti)

Scrivere una funzione che preso in input il nome di un file, contenente una sequenza di stringhe, alloca dinamicamente un vettore di stringhe
che contiene le stesse stringhe del file e nello stesso ordine, e restituisce il vettore e la sua dimensione. Il file è di tipo testo e la lunghezza
massima delle stringhe è 100. Però la lunghezza media è 7 per cui il vettore allocato non deve sprecare memoria. Il prototipo della funzione
è char **FileStr2VetStr(const char *fStr, long *dim). La funzione quindi ritorna il puntatore al vettore di stringhe
e in dim restituisce la dimensione del vettore (cioè il numero delle stringhe). Si sottolinea che sia il vettore che le stringhe (i cui puntatori
sono contenuti nel vettore) devono essere allocati dinamicamente.

Soluzione Esercizio 2

char **FileStr2VetStr(const char *fStr, long *dim)
{
    char **vetStr;
    FILE *f = fopen(fStr, "r");    /* Apri il file (di tipo testo) in sola lettura */
    long i, nStr = 0;
    while (!feof(f)) {            /* Leggi il file per calcolare il numero di */
        char str[101];            /* stringhe in esso contenute.              */
        fscanf(f, "%100s", str);
        nStr++;
    }
    vetStr = malloc(nStr*sizeof(char *));    /* Alloca il vettore di stringhe */
    rewind(f);                               /* Riporta il file all'inizio */
    i = 0;
    while (!feof(f)) {                    /* Leggi di nuovo le stringhe del file */
        char str[101];
        fscanf(f, "%100s", str);
        vetStr[i] = malloc((strlen(str) + 1)*sizeof(char)); /* Alloca la i-esima stringa */
        strcpy(vetStr[i], str);
        i++;
    }
    fclose(f);
    *dim = nStr;
    return vetStr;
}

Esercizio 3 (max 11 punti)

Scrivere una funzione che presa in input una lista di interi e un intero positivo k, restituisce un vettore allocato dinamicamente che
contiene i k interi più piccoli della lista. Il tipo degli elementi della lista è così definito:
typedef struct Elem {
    int          val;
    struct Elem *next;
} Elem;
Il prototipo della funzione è int *Piccoli(const Elem *L, unsigned k). Si assume che gli interi della lista sono
tutti distinti e che sono in numero maggiore di k. Si richiede che il vettore sia ordinato in senso crescente. Ad esempio se la lista
è 6 -> 2 -> 7 -> 9 -> 5 -> 3 -> 10   e   k = 3 allora la funzione deve restituire il vettore [2, 3, 5].

Soluzione Esercizio 3

/* Funzione ausiliaria che ritorna il piu' piccolo intero strettamente maggiore di x *
* contenuto nella lista L (se non esiste ritorna x).                                */
int MinMagg(int x, const Elem *L)
{
    int mm = x;
    while (L != NULL) {
        int v = L->val;
        if (v > x && (mm == x || v < mm)) mm = v;
        L = L->next;
    }
    return mm;
}

int *Piccoli(const Elem *L, unsigned k)
{
    int *vet = malloc(k*sizeof(int)); /* Alloca il vettore */
    const Elem *p = L;
    int i, min = L->val;               /* Scorri la lista per trovare il minimo */
    while (p != NULL) {
        if (p->val < min) min = p->val;
        p = p->next;
    }
    vet[0] = min;
    for (i = 1 ; i < k ; i++)             /* Trova il prossimo intero piu' piccolo */
        vet[i] = MinMagg(vet[i - 1], L); /* tramite la funzione MinMagg.          */
    return vet;
}

Esercizio 4 (max 9 punti)

Scrivere una funzione che presa in input una lista e un intero positivo k modifica la lista spostando il k-esimo elemento in coda alla lista
e ritorna il puntatore alla lista modificata. Se la lista ha meno di k elementi la funzione non fa nulla. Il tipo degli elementi della lista è
typedef struct Elem {
int info;
struct Elem *next;
} Elem, *List;
Il prototipo della funzione è List Sposta(List L, unsigned k). Ad esempio se la lista è 7 -> 4 -> 2 -> 8 -> 9 e
k = 3 allora la funzione modifica la lista così 7 -> 4 -> 8 -> 9 -> 2.

Soluzione Esercizio 4

List Sposta(List L, unsigned k)
{
    List *p = &L;                  /* Vai al k-esimo elemento mantenendo in */
    while (*p != NULL && k > 1) { /* p l'indirizzo della locazione che      */
        p = &((*p)->next);         /* contiene il puntatore a tale elemento. */
        k--;
    }
    if (*p != NULL) {                        /* Se il k-esimo elemento esiste */
        Elem *e = *p;                        /* toglilo dalla lista,          */
        *p = e->next;
        while (*p != NULL) p = &((*p)->next); /* arriva alla fine della lista */
        *p = e;                                /* e aggancia l'elemento.        */
        e->next = NULL;
    }
    return L;
}

Ritorna alla pagina del corso