P140108PZ0708 < Programmazione1

<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 - 14 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>long *IndMax(const int V[], long n, long *nMax)</tt>, 
che preso in input un vettore <tt>V</tt> di dimensione <tt>n</tt>, ritorna un vettore di 
<tt>long</tt> allocato dinamicamente contenente gli indici degli elementi di <tt>V</tt> che hanno
valore uguale al massimo intero presente in <tt>V</tt> e in <tt>*nMax</tt> restituisce il 
numero di tali elementi. Il vettore ritornato non deve usare pi&ugrave;
memoria di quella strettamente necessaria. Se <tt>V = [-1, 2, 7, -5, 7]</tt> allora la funzione 
ritorna il vettore <tt>[2, 4]</tt> e in <tt>*nMax</tt> restituisce <tt>2</tt>.
</dd>
<b>Soluzione</b>
<dd>
<tt><pre>
long *IndMax(const int  V[], long n, long  *nMax)
{
    long *ind = NULL;            //Inizializza i valori di ind e *nMax cosicche'
    *nMax = 0;                   //se n <= 0 ritorna NULL e in *nMax restituisce 0.
    if (n > 0) {                 
        long i, k;
        int max = V[0]; 
        for (i = 1 ; i < n ; i++)             //Calcola il valore massimo di V
            if (V[i] > max) max = V[i];
        for (i = 0 ; i < n ; i++)             //Calcola il numero di elementi di V
            if (V[i] == max) (*nMax)++;       //con valore massimo.
        ind = malloc((*nMax)*sizeof(long));   //Alloca il nuovo vettore
        for (k = 0, i = 0 ; i < n ; i++)      //Scrivi nel nuovo vettore gli indici
            if (V[i] == max) ind[k++] = i;    //degli elementi con valore massimo.
    }
    return ind;
}
</pre></tt>
</dd>
</dl>
<dl><b>Esercizio 2</b>
<dd>Scrivere una funzione che presi in input tre interi non negativi <tt>nA</tt>, <tt>nB</tt>, 
<tt>nC</tt>, restituisce una stringa allocata dinamicamente che consiste di <tt>nA</tt> caratteri 
<tt>'A'</tt> seguiti da <tt>nB</tt> caratteri <tt>'B'</tt> seguiti da <tt>nC</tt> caratteri <tt>'C'</tt>. 
Il prototipo della funzione &egrave; <tt>char *ABCStringa(int nA, int nB, int nC)</tt>.
Ad esempio se <tt>nA = 2</tt>, <tt>nB = 1</tt> e <tt>nC = 4</tt> la funzione deve restituire la stringa <tt>"AABCCCC"</tt>.
</dd>
<b>Soluzione</b>  
<dd>
<tt><pre>
char *ABCStringa(int nA, int nB, int nC)
{
    char *stringa = malloc((nA + nB + nC + 1)*sizeof(char));   //Alloca la stringa
    int n, i = 0;                //La variabile i conterra' sempre l'indice del
                                 //prossimo carattere (non ancora scritto).
    for (n = nA ; n > 0 ; n--) stringa[i++] = 'A';       //Scrivi le A
    for (n = nB ; n > 0 ; n--) stringa[i++] = 'B';       //Scrivi le B
    for (n = nC ; n > 0 ; n--) stringa[i++] = 'C';       //Scrivi le C
    stringa[i] = '\0';
    return stringa;
}
</pre></tt>
</dd>
</dl>

<dl><b>Esercizio 3</b>
<dd>Scrivere una funzione che preso in input un vettore di interi ordinato in senso non decrescente e 
la sua dimensione, elimina dal vettore tutti i duplicati compattandolo e ritorna il numero di elementi eliminati (la dimensione del vettore comunque non cambia). Il prototipo della funzione &egrave;
<tt>long</tt> <tt>EliminaDuplicati(int V[], long dim)</tt>.
Ad esempio se <tt>V = [2, 4, 4, 5, 7, 7, 7]</tt> la funzione modifica il vettore in modo tale che 
i primi 4 elementi del vettore siano <tt>[2, 4, 5, 7]</tt> e ritorna <tt>3</tt>.
</dd>
<b>Soluzione</b> 
<dd>
<tt><pre>
long EliminaDuplicati(int V[], long dim)
{
    long k = 0, i;
    for (i = 1 ; i < dim ; i++) {
        if (V[i] != V[k]) {
            k++;
            V[k] = V[i];
        }
    }
    return dim - (k + 1);
} 
</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 preso in input una lista di interi, per ogni elemento della lista 
modifica l'intero in esso contenuto in modo tale che contenga la somma di tutti gli interi 
contenuti nella lista a partire da quel elemento. Il tipo degli elementi
della lista &egrave;:
<tt><pre>
typedef struct Elem {
    int          intero;
    struct Elem *next;
} Elem, *List;
</pre></tt>
Il prototipo della funzione &egrave; <tt>void</tt> <tt>SomList(List)</tt>. Ad esempio se 
la lista &egrave; <tt>2 -> 5 -> 3 -> 13</tt> allora
la funzione modifica la lista cos&igrave; <tt>23 -> 21 -> 16 -> 13</tt>.
</dd>
<b>Soluzione</b>   
<dd>
<tt><pre>
/* Funzione ausiliaria che ritorna la somma degli interi della lista a partire
   dall'elemento e.                                                           */
int Somma(const Elem *e)
{
    int s = 0;
    while (e != NULL) {
        s += e->intero;
        e = e->next;
    }
    return s;
}

void SomList(List L)
{
    while (L != NULL) {
        L->intero = Somma(L);
        L = L->next;
    }
} 
</pre></tt>
</dd>
</dl>
<dl><b>Esercizio 5</b>
<dd>Si consideri il seguente tipo:
<tt><pre>
typedef struct VStr {
    long         val;
    char *       str;        //stringa allocata dinamicamente
    struct VStr *next;
} VStr, *LStr;
</pre></tt>
Scrivere una funzione, con prototipo <tt>int Comp(LStr L)</tt>, che presa in input la lista 
<tt>L</tt>, ordinata in senso non decrescente rispetto al campo <tt>val</tt>, la modifica in modo 
tale che elementi consecutivi che hanno lo stesso valore del campo <tt>val</tt> sono sostituiti 
da un elemento il cui valore del campo <tt>val</tt> &egrave; lo stesso e il campo <tt>str</tt> 
&egrave; 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 <tt>val</tt>. Inoltre la funzione
non deve modificare il puntatore al primo elemento. La memoria non pi&ugrave; usata deve essere 
rilasciata e i nuovi blocchi di memoria non devono essere pi&ugrave; grandi del necessario. 
Ad esempio se la lista &egrave;
<tt>{5, "AA"} -> {5, "BBB"} -> {7, "C"} -> {8, "D"} -> {8, "GG"} -> {8, "F"}</tt> allora la 
funzione la modifica cos&igrave; <tt>{5, "AABBB"} -> {7, "C"} -> {8, "DGGF"}</tt> e ritorna <tt>3</tt>.
</dd>
<b>Soluzione</b>   
<dd>
<tt><pre>
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;
}
</pre></tt>
</dd>
</dl>
<dl><b>Esercizio 6</b>
<dd>Scrivere una funzione, con prototipo <tt>void</tt> <tt>InvFile(char *nameF, char  *newF)</tt>, che legge 
il file di tipo testo il cui nome &egrave; nella stringa <tt>nameF</tt>, contenente una sequenza 
di numeri interi separati da spazi, e crea un nuovo file di testo, con nome dato dalla stringa 
<tt>newF</tt>, e vi scrive la sequenza inversa. Ad esempio, se il file <tt>nameF</tt> contiene 
la sequenza <tt>3 7 -2 15</tt> allora il nuovo file creato dalla funzione deve contenere 
<tt>15 -2 7 3</tt>.
</dd>
<b>Soluzione</b>   
<dd>
<tt><pre>
void  InvFile(char *nameF, char  *newF)
{
    FILE *f = fopen(nameF, "r");                //Apri il file in lettura
    int n, lenF = 0;
    while (fscanf(f, "%d", &n) == 1) lenF++;    //Conta gli interi nel file
    int k = 0, v[lenF];  //Vettore a dimensione variabile atto a contenere gli interi del file
    rewind(f);           //Riporta il cursore del file all'inizio
    while (fscanf(f, "%d", &(v[k])) == 1) k++;  //Copia gli interi del file nel vettore v
    fclose(f);
    FILE *nF = fopen(newF, "w");                //Crea ed apri il nuovo file
    for (k = lenF - 1 ; k >= 0 ; k--)           //Scrivi nel nuovo file gli interi in
        fprintf(nF, "%d ", v[k]);               //ordine inverso.
    fclose(nF);
}
</pre></tt>
</dd>
</dl>
This topic: Programmazione1 > WebHome > Prog1PZ > EsprepPZ0708 > P140108PZ0708
Topic revision: r1 - 2008-01-14 - TizianaCalamoneri