Programmazione I    (canale P-Z) a.a. 2007-2008
Docente: R. Silvestri     Esercitatore: A. Carosi     Tutor: J. Stefa
Esercizi di preparazione all'esame - 17 gennaio 2008

Prima parte

Esercizio 1
Scrivere una funzione, con prototipo char *PadString(const char *str, unsigned start, unsigned end, char pad), che ritorna una stringa, allocata dinamicamente, formata da start caratteri pad seguiti dai caratteri della stringa str ed infine seguiti da end caratteri pad. Ad esempio PadString("giorno", 3, 2, '*') ritorna la stringa "***giorno**".
Soluzione
char *PadString(const char *str, unsigned start, unsigned end, char pad)
{
    int k;                                               //Alloca la nuova stringa
    char *newStr = malloc((strlen(str) + start + end + 1)*sizeof(char));
    for (k = 0 ; k < start ; k++) newStr[k] = pad;       //Scrivi i caratteri pad iniziali
    for ( ; *str != '\0' ; str++, k++) newStr[k] = *str; //Copia i caratteri di str
    for ( ; end > 0 ; end--, k++) newStr[k] = pad;       //Scrivi i caratteri pad finali
    newStr[k] = '\0';
    return newStr;
}
Esercizio 2
Scrivere una funzione, con prototipo char *Coll(char **strVec, long n), che preso in input un vettore di n stringhe strVec elimina da esso 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. 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ì [NULL, NULL, NULL, "redskin", NULL, "green", "blu"] e ritorna la stringa "redgreenredblu".
Soluzione
/* 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);
}

char *Coll(char **strVec, long n)
{
    long k, len = 0;                                  //Calcola la somma delle
    for (k = 0 ; k < n ; k++)                         //lunghezze delle stringhe
        if (IsDel(strVec, n, k))                      //da eliminare.
            len += strlen(strVec[k]);
    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 e rilascia la
        if (IsDel(strVec, n, k)) {                    //memoria delle stringhe
            strcat(newStr, V[k]);                     //eliminate.
            free(V[k]);
            V[k] = NULL;
        }
    return newStr;
}

Esercizio 3
Scrivere una funzione che presi in input due vettori di interi A e B e le loro dimensioni, elimina dal vettore A compattandolo tutti i valori che non sono presenti anche in B e ritorna il numero di valori rimasti in A (la dimesione di A rimane invariata). Il prototipo della funzione è long Com(int A[], long dimA, int B[], long dimB). Ad esempio se A = [2, 7, 2, 4, 9, 9, 5] (dimA = 7) e B = [5, 5, 4, 6, 2] (dimB = 5) allora la funzione modifica il vettore A in modo tale che nelle prime 4 posizioni di A vi sia [2, 2, 4, 5] e ritorna 4.
Soluzione
long Com(int A[], long dimA, int B[], long dimB)
{
    long k = 0, i;         //La variabile k manterra' l'indice della prima
                           //posizione disponibile del vettore A.
    for (i = 0 ; i < dimA ; i++) {
        long j = 0;
        while (j < dimB && A[i] != B[j]) j++;  //Controlla se A[i] appare in B
        if (A[i] == B[j]) {                    //Se e' cosi' sposta A[i] nella
            A[k] = A[i];                       //prima posizione disponibile,
            k++;                               //compattando cosi' il vettore.
        }
    }
    return k;
}


Seconda parte
Esercizio 4
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
/* 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 5
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
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;
} 
Esercizio 6
Si considerino i seguenti tipi:
typedef struct {
    short            str;    //1 se e' valido il campo s, 0 se e' valido il campo n
    union {
        char  s[101];        //se valido contiene una stringa di lunghezza <= 100
        int   n;             //se valido contiene un numero
    }                val;
} Rec;

typedef struct Elem {
    char *       string;
    struct Elem *next;
} Elem, *List;
Scrivere una funzione, con prototipo List Update(List L, char *nameF), che presa in input una lista di stringhe ordinata L vi inserisce, mantenendo la lista ordinata, le stringhe contenute nel file binario il cui nome  nella stringa nameF e che contiene una sequenza di record di tipo Rec. La funzione non deve inserire stringhe che sono già presenti nella lista e l'ordinamento delle stringhe è quello dato dalla funzione della libreria standard strcmp. Siccome la lunghezza media delle stringhe nel file è molto minore di 100, l'allocazione delle stringhe nella lista non deve sprecare memoria. La funzione ritorna il puntatore al primo elemento della lista aggiornata. La lista di input pu˜ anche essere vuota (L = NULL). Se la lista è "cane" -> "gatto" -> "lupo" e il file contiene {1, "leone"}, {0, 13}, {1, "cane"}, {1, "leone"}, {1, "aquila"} allora la funzione ritorna la lista "aquila" -> "cane" -> "gatto" -> "leone" -> "lupo".
Soluzione
/* Funzione ausiliaria che, se la stringa str non e' presente nella lista L, inserisce
   la stringa str nella lista ordinata L mantenendola ordinata.                        */
List InsOrd(List L, const char *str)
{
    Elem **prec = &L;    //Indirizzo della locazione che eventualmente dovra' contenere
                         //il puntatore all'elemento inserito.
    while (*prec != NULL && strcmp(str, (*prec)->string) > 0)   //Scorri la lista finche'
        prec = &((*prec)->next);                       //o la lista e' finita o trovi una
                                                       //stringa maggiore od uguale a str.
    if (*prec == NULL || strcmp(str, (*prec)->string) != 0) {    //Se non e' stata trovata
                                                                 //una stringa uguale a str...
        Elem *new = malloc(sizeof(Elem));                     //alloca un nuovo elemento
        new->string = malloc((strlen(str) + 1)*sizeof(char)); //Alloca memoria per la stringa
        strcpy(new->string, str);                             //Copia la stringa
        new->next = *prec;                                    //Inserisci il nuovo elemento
        *prec = new;                                          //nella lista.
    }
    return L;
}

List Update(List L, char *nameF)
{
    FILE *f = fopen(nameF, "rb");    //Apri il file binario in lettura
    Rec r;
    while (fread(&r, sizeof(Rec), 1, f) == 1)    //Leggi ogni record del file...
        if (r.str == 1)                     //Se il record contiene una stringa
            L = InsOrd(L, r.val.s);         //tenta di inserirla nella lista
    fclose(f);
    return L;
}
Topic revision: r1 - 2008-01-17 - TizianaCalamoneri






 
Questo sito usa cookies, usandolo ne accettate la presenza. (CookiePolicy)
Torna al Dipartimento di Informatica
This site is powered by the TWiki collaboration platform Powered by PerlCopyright © 2008-2024 by the contributing authors. All material on this collaboration platform is the property of the contributing authors.
Ideas, requests, problems regarding TWiki? Send feedback