Esercizio 1 (max 6 punti)

Scrivere una funzione, con prototipo int nochar(char *str, char x), che ritorna la lunghezza della più lunga sottostringa (sequenza di caratteri consecutivi) di str che non contiene il carattere x. Ad esempio, se str = "stringa di esempio" e x = 'i' allora la funzione ritorna 6.

Soluzione

int nochar(char *str, char x)
{
    int max = 0, i, k;
    for (i = 0 ; str[i] != '\0' ; i++) {
        k = 0;
        while (str[i + k] != x && str[i + k] != '\0') k++;
        if (k > max) max = k;
    }
    return max;
}

Esercizio 2 (max 8 punti)

Scrivere una funzione, con prototipo int eqfreq(int A[], int B[], int n), che presi in input due vettori A e B di eguale dimensione n ritorna il numero di valori distinti che hanno la stessa frequenza positiva sia in A che in B. Per frequenza di un valore si intende il numero di volte che il valore appare nel vettore. Ad esempio, se A = [3, 5, 3, 1, 2, 5, 5] e B = [4, 3, 5, 2, 3, 5, 4] allora la funzione ritorna 2 perché il valore 3 ha frequenza 2 in entrambi i vettori, il valore 2 ha frequenza 1 in entrambi i vettori e tutti gli altri valori hanno frequenze differenti nei due vettori.

Soluzione

/* Funzione ausiliaria che ritorna la frequenza del valore v nel vettore X
   di dimensione n.                                                       */
in freq(int X[], int n, int v)
{
    int f = 0, i;
    for (i = 0 ; i < n ; i++) if (X[i] == v) f++;
    return f;
}

int eqfreq(int A[], int B[], int n)
{
    int ef = 0, i;
    for (i = 0 ; i < n ; i++)                          //per ogni valore in A
        if (freq(A, i, A[i]) == 0)                     //se e' la prima occorrenza di A[i] in A
            if (freq(A, n, A[i]) == freq(B, n, A[i]))  //allora controlla le frequenze in entrambi i vettori
                ef++;                                  
    return ef;
}

Esercizio 3 (max 10 punti)

Scrivere una funzione, con prototipo char *replacex(char *str, char *rep), che ritorna una stringa allocata dinamicamente ottenuta sostituendo ogni occorrenza del carattere 'X' nella stringa str con la stringa rep. Il blocco di memoria allocato per la stringa ritornata non deve essere più grande del necessario. Ad esempio, se str = "XXena e Xla vuota" e rep ="la pi" allora la funzione ritorna la stringa "la pila piena e la pila vuota".

Soluzione

char *replacex(char *str, char *rep)
{
    long lrep = strlen(rep), len = strlen(str);
    long i, j, k;
    for (i = 0 ; str[i] != '\0' ; i++) 
        if (str[i] == 'X') len += lrep - 1;
    char *strep = malloc(sizeof(char)*(len + 1));
    for (k = i = 0 ; str[i] != '\0' ; i++)
        if (str[i] == 'X') {
            for (j = 0 ; rep[j] != '\0' ; j++)
                strep[k++] = rep[j];
        } else strep[k++] = str[i];
    strep[k] = '\0';
    return strep;
}

Esercizio 4 (max 6 punti)

Si consideri il seguente tipo:

typedef struct Elem {
    int          val;
    struct Elem *next;
} Elem, *List;

Scrivere una funzione, con prototipo void fiblist(List L), che presa in input una lista di interi L aggiunge in coda alla lista un nuovo elemento con valore nel campo val pari alla somma dei valori degli ultimi due elementi di L. Se la lista ha meno di due elementi la funzione non fa nulla. Ad esempio, se la lista L è 3 -> 13 -> 11 -> 25 allora la funzione modifica la lista così 3 -> 13 -> 11 -> 25 -> 36.

Soluzione

void fiblist(List L)
{
    if (L == NULL || L->next == NULL) return;   //Se ha meno di due elementi non fa nulla
    Elem *e1 = L, *e2 = L->next;                //Manteniamo in e1 ed e2 i puntatori ai
    L = e2;                                     //due elementi precedenti durante
    while (L->next != NULL) {                   //la scansione della lista.
        e1 = e2;
        e2 = L->next;
        L = e2;
    }                                           //Quando il while termina in L c'e'
    Elem *e = malloc(sizeof(Elem));             //il puntatore all'ultimo elemento
    e->val = e1->val + e2->val;                 //della lista.
    e->next = NULL;
    L->next = e;                                //aggancia il nuovo elemento in coda
}

Esercizio 5 (max 8 punti)

Scrivere una funzione, con prototipo void flines(char *infile, char *outfile), che prende in input il nome di un file di tipo testo (nella stringa infile) che contiene linee di testo terminate dal carattere newline '\n' e crea un nuovo file di tipo testo, il cui nome è nella stringa outfile, e vi scrive, per ogni linea del file di input, una linea che contiene linea k: n, dove k è l'indice di linea (la prima linea ha indice 1) e n è il numero di caratteri della linea k. Si assume che le linee del file di input abbiano al più 100 caratteri. Ad esempio,

        file di input                                            file di output

        Quant'è bella giovinezza                                 linea 1: 24
        che si fugge tuttavia!                                   linea 2: 22
        Chi vuol esser lieto, sia:                               linea 3: 26
        di doman non c'è certezza.                               linea 4: 26

Soluzione

void flines(char *infile, char *outfile)
{
    FILE *in = fopen(infile, "r");                 //apri in lettura il file di input
    FILE *out = fopen(outfle, "w");                //crea e apri in scrittura il file di output
    char linea[101];                               //array per mantenere una linea letta
    int k = 1;
    while (fgets(linea, 101, in) != NULL) {                    //leggi le linee del file di input
        fprintf(out, "linea %d: %d\n", k, strlen(linea));
        k++;
    }
    fclose(in);
    fclose(out);
}

Esercizio 6 (max 10 punti)

Si consideri il seguente tipo:

typedef struct Estr {
    char *       str;      //stringa allocata dinamicamente
    struct Estr *next;
} Estr, *Strlist;

Scrivere una funzione, con prototipo Strlist update(Strlist L, char c), che presa in input una lista di stringhe rimuove da essa tutti gli elementi che hanno nel campo str una stringa che contiene il carattere c, aggiunge in testa alla lista un nuovo elemento che nel campo str ha una stringa formata concatenando tutte le stringhe rimosse e ritorna il puntatore alla lista modificata. Se non ci sono elementi che hanno nel campo str una stringa che contiene il carattere c allora la funzione non fa nulla. Ad esempio, se L è "verde" -> "rosso" -> "nero" -> "verde" -> "giallo" -> "viola" e c = 'e' allora la funzione modifica la lista così "verdeneroverde" -> "rosso" -> "giallo" -> "viola".

Soluzione

/* Funzione ausiliaria che ritorna true se la stringa str contiene il carattere c,
   altrimenti ritorna false.                                                     */
int inchar(char *str, char c)
{
    int i;
    for (i = 0 ; str[i] != '\0' && str[i] != c ; i++) 
    return (str[i] == c);
}

Strlist update(Strlist L, char c)
{
    Strlist p = L;
    long size = 0;
    while (p != NULL) {              //scorri la lista per calcolare la somma delle
        if (inchar(p->str, c))       //lunghezze delle stringhe da rimuovere
            size += strlen(p->str);
        p = p->next;
    }
    if (size == 0) return L;          //se non ci sono stringhe da rimuovere non fare nulla
    char *concat = malloc(sizeof(char)*(size + 1));   //alloca il blocco per la concatenazione
    concat[0] = '\0';                                 //delle stringhe da rimuovere 
    Strlist *pL = &L;
    while (*pL != NULL) {                //scorri la lista
        if (inchar((*pL)->str, c)) {     //se l'elemento ha una stringa che contiene c
            strcat(concat, (*pL)->str);  //concatena la stringa da rimuovere
            free((*pL)->str);            //libera la memoria della stringa
            Estr *next = (*pL)->next;    //salva il puntatore al prossimo elemento
            free(*pL);                   //libera la memoria dell'elemento
            *pL = next;                  //sgancia l'elemento dalla lista
        } else pL = &((*pL)->next);
    }
    p = malloc(sizeof(Estr));            //alloca il nuovo elemento
    p->str = concat;
    p->next = L;                         //aggiungi il nuovo elemento in testa
    return p;
}

-- RiccardoSilvestri - 07 Feb 2008