P170108PZ0708 < Programmazione1

Tags: view all tags
<div align="center"><big><b>Programmazione I &nbsp; &nbsp;(canale P-Z) a.a. 2007-2008<br>
</b></big>
Docente: R. Silvestri &nbsp; &nbsp; Esercitatore: A. Carosi &nbsp; &nbsp;
Tutor: J. Stefa<br>
Esercizi di preparazione all'esame - 17 gennaio 2008
</div>
<br>
<div align="center"><big><b>Prima parte</b></big></div>

<dl><b>Esercizio 1</b>
<dd>Scrivere una funzione, con prototipo <tt>char *PadString(const char *str, unsigned start, 
unsigned end, char pad)</tt>, che ritorna una stringa, allocata dinamicamente, 
formata da <tt>start</tt> caratteri <tt>pad</tt> seguiti dai caratteri della stringa <tt>str</tt> 
ed infine seguiti da <tt>end</tt> caratteri <tt>pad</tt>. Ad esempio 
<tt>PadString("giorno", 3, 2, '*')</tt> ritorna la stringa <tt>"***giorno**"</tt>.
</dd>
<b>Soluzione</b>
<dd>
<tt><pre>
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;
}</pre></tt>
</dd>
</dl>
<dl><b>Esercizio 2</b>
<dd>Scrivere una funzione, con prototipo <tt>char *Coll(char **strVec, long n)</tt>, che preso in input
un vettore di <tt>n</tt> stringhe <tt>strVec</tt> elimina da esso tutte le stringhe <tt>s</tt> per cui c'&egrave; almeno una stringa successiva <tt>t</tt> tale che <tt>strcmp(s, t) <= 0</tt>, 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&ugrave; memoria del necessario.  Ad esempio se <tt>strVec</tt> 
&egrave; <tt>["red", "green", "red", "redskin", "blu", "green", "blu"]</tt> (quindi <tt>n = 7</tt>) allora 
la funzione lo modifica cos&igrave; <tt>[NULL, NULL, NULL, "redskin", NULL, "green", "blu"]</tt> e 
ritorna la stringa <tt>"redgreenredblu"</tt>.
</dd>
<b>Soluzione</b>  
<dd>
<tt><pre>
/* 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;
}
</pre></tt>
</dd>
</dl>

<dl><b>Esercizio 3</b>
<dd>Scrivere una funzione che presi in input due vettori di interi <tt>A</tt> e <tt>B</tt> e le loro 
dimensioni, elimina dal vettore <tt>A</tt> compattandolo tutti i valori che non sono presenti anche in 
<tt>B</tt> e ritorna il numero di valori rimasti in <tt>A</tt> (la dimesione di <tt>A</tt> rimane invariata). 
Il prototipo della funzione &egrave; <tt>long Com(int A[], long dimA, int B[], long dimB)</tt>. Ad esempio
se <tt>A = [2, 7, 2, 4, 9, 9, 5]</tt> (<tt>dimA = 7</tt>)  e  <tt>B = [5, 5, 4, 6, 2]</tt> (<tt>dimB = 5</tt>) 
allora la funzione modifica il vettore <tt>A</tt> in modo tale che nelle prime 4 posizioni di <tt>A</tt> vi sia 
<tt>[2, 2, 4, 5]</tt> e ritorna <tt>4</tt>.
</dd>
<b>Soluzione</b> 
<dd>
<tt><pre>
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;
}
</pre></tt>
</dd>
</dl>
<hr width="100%" size="2"><br>
<div align="center"><big><b>Seconda parte</b></big></div>
<dl><b>Esercizio 4</b>
<dd>Scrivere una funzione che presa in input una lista di interi e un intero positivo <tt>k</tt>, 
restituisce un vettore allocato dinamicamente che contiene i <tt>k</tt> interi pi&ugrave; piccoli 
della lista. Il tipo degli elementi della lista &egrave; cos&igrave; definito:
<tt><pre>
typedef struct Elem {
    int          val;
    struct Elem *next;
} Elem;
</pre></tt>
Il prototipo della funzione &egrave; <tt>int *Piccoli(const Elem *L, unsigned k)</tt>. Si assume che 
gli interi della lista sono tutti distinti e che sono in numero maggiore di <tt>k</tt>. Si richiede 
che il vettore sia ordinato in senso crescente. Ad esempio se la lista &egrave; 
<tt>6 -> 2 -> 7 -> 9 -> 5 -> 3 -> 10</tt> e <tt>k = 3</tt> allora la funzione deve restituire il 
vettore <tt>[2, 3, 5]</tt>.
</dd>
<b>Soluzione</b>   
<dd>
<tt><pre>
/* 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;
}
</pre></tt>
</dd>
</dl>
<dl><b>Esercizio 5</b>
<dd>Scrivere una funzione che presa in input una lista e un intero positivo <tt>k</tt> modifica la lista 
spostando il <tt>k</tt>-esimo elemento in coda alla lista e ritorna il puntatore alla lista 
modificata. Se la lista ha meno di <tt>k</tt> elementi la funzione non fa nulla. Il tipo degli elementi della 
lista &egrave;
<tt><pre>
typedef struct Elem {
    int          info;
    struct Elem *next;
} Elem, *List;
</pre></tt>
Il prototipo della funzione &egrave; <tt>List Sposta(List L, unsigned k)</tt>. Ad esempio se la lista &egrave; 
<tt>7 -> 4 -> 2 -> 8 -> 9</tt> e <tt>k = 3</tt> allora la funzione modifica la lista cos&igrave; 
<tt>7 -> 4 -> 8 -> 9 -> 2</tt>.
</dd>
<b>Soluzione</b>   
<dd>
<tt><pre>
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;
} 
</pre></tt>
</dd>
</dl>
<dl><b>Esercizio 6</b>
<dd>Si considerino i seguenti tipi:
<tt><pre>
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;
</pre></tt>
Scrivere una funzione, con prototipo <tt>List Update(List L, char *nameF)</tt>, che presa in input una 
lista di stringhe ordinata <tt>L</tt> vi inserisce, mantenendo la lista ordinata, le stringhe contenute 
nel file binario il cui nome &#143; nella stringa <tt>nameF</tt> e che contiene una sequenza di record di tipo 
<tt>Rec</tt>. La funzione non deve inserire stringhe che sono gi&agrave; presenti nella lista e
l'ordinamento delle stringhe &egrave; quello dato dalla funzione della libreria standard <tt>strcmp</tt>. 
Siccome la lunghezza media delle stringhe nel file &egrave; molto minore di <tt>100</tt>, 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&#152; anche 
essere vuota (<tt>L = NULL</tt>). Se la lista &egrave; <tt>"cane" -> "gatto" -> "lupo"</tt> e il file contiene
<tt>{1, "leone"},  {0, 13},  {1, "cane"},  {1, "leone"},  {1, "aquila"}</tt>
allora la funzione ritorna la lista <tt>"aquila" -> "cane" -> "gatto" -> "leone" -> "lupo"</tt>.
</dd>
<b>Soluzione</b>   
<dd>
<tt><pre>
/* 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;
}
</pre></tt>
</dd>
</dl>