Deprecated: Function ereg() is deprecated in /home/demetres/public_html/didattica/ae/libs/Wakka.class.php on line 648 Ingegneria degli Algoritmi: Esercizi sul linguagggio C

Deprecated: Assigning the return value of new by reference is deprecated in /home/demetres/public_html/didattica/ae/3rdparty/core/safehtml/classes/safehtml.php on line 308 Deprecated: Assigning the return value of new by reference is deprecated in /home/demetres/public_html/didattica/ae/3rdparty/core/safehtml/classes/HTMLSax.php on line 159 Deprecated: Assigning the return value of new by reference is deprecated in /home/demetres/public_html/didattica/ae/3rdparty/core/safehtml/classes/HTMLSax.php on line 161 Deprecated: Assigning the return value of new by reference is deprecated in /home/demetres/public_html/didattica/ae/3rdparty/core/safehtml/classes/HTMLSax.php on line 162 Deprecated: Assigning the return value of new by reference is deprecated in /home/demetres/public_html/didattica/ae/3rdparty/core/safehtml/classes/HTMLSax.php on line 163 Deprecated: Assigning the return value of new by reference is deprecated in /home/demetres/public_html/didattica/ae/3rdparty/core/safehtml/classes/HTMLSax.php on line 165 Deprecated: Assigning the return value of new by reference is deprecated in /home/demetres/public_html/didattica/ae/3rdparty/core/safehtml/classes/HTMLSax.php on line 166 Deprecated: Assigning the return value of new by reference is deprecated in /home/demetres/public_html/didattica/ae/3rdparty/core/safehtml/classes/HTMLSax.php on line 167 Deprecated: Assigning the return value of new by reference is deprecated in /home/demetres/public_html/didattica/ae/3rdparty/core/safehtml/classes/HTMLSax.php on line 243 Deprecated: Assigning the return value of new by reference is deprecated in /home/demetres/public_html/didattica/ae/3rdparty/core/safehtml/classes/HTMLSax.php on line 250 Deprecated: Assigning the return value of new by reference is deprecated in /home/demetres/public_html/didattica/ae/3rdparty/core/safehtml/classes/HTMLSax.php on line 259 Deprecated: Assigning the return value of new by reference is deprecated in /home/demetres/public_html/didattica/ae/3rdparty/core/safehtml/classes/HTMLSax.php on line 266 Deprecated: Assigning the return value of new by reference is deprecated in /home/demetres/public_html/didattica/ae/3rdparty/core/safehtml/classes/HTMLSax.php on line 273 Deprecated: Assigning the return value of new by reference is deprecated in /home/demetres/public_html/didattica/ae/3rdparty/core/safehtml/classes/HTMLSax.php on line 280 Deprecated: Assigning the return value of new by reference is deprecated in /home/demetres/public_html/didattica/ae/3rdparty/core/safehtml/classes/HTMLSax.php on line 467 Deprecated: Assigning the return value of new by reference is deprecated in /home/demetres/public_html/didattica/ae/3rdparty/core/safehtml/classes/HTMLSax.php on line 469 Deprecated: Assigning the return value of new by reference is deprecated in /home/demetres/public_html/didattica/ae/3rdparty/core/safehtml/classes/HTMLSax.php on line 471

Esercizi sul linguagggio C

Esercizio 1

Scrivere una funzione alloc_array che alloca dinamicamente un blocco di memoria di dimensione in byte specificata dal chiamante. Il puntatore al blocco allocato deve essere passato al chiamante per indirizzo come primo parametro. La funzione deve restituire 0 se l'allocazione è andata a buon fine (malloc restituisce un puntatore diverso da NULL), e -1 altrimenti. Scrivere il programma in modo da poter compilare con successo il seguente programma di prova:

#include <stdio.h>

#include <stdlib.h>

// inserire qui la definizione della funzione alloc_array

int main() {

    char* p;

    int errcode = alloc_array(&p, 256); // alloca blocco di 256 byte

    if (!errcode) free(p);

    return errcode;

}

Esercizio 2

Dopo aver consultato gli specificatori di formato della funzione printf∞, dire cosa stampa il seguente programma e perché:

#include <stdio.h>

int main(){

    unsigned short x = 65535;

    printf("%hu\n", x);

    printf("%hd\n", x);

    return 0;

}

Esercizio 3

Si compili ed esegua il seguente programma C:

main.c

#include <stdio.h>

int main(){

    printf("char %u\n", (unsigned)sizeof(char));

    printf("short %u\n", (unsigned)sizeof(short));

    printf("int %u\n", (unsigned)sizeof(int));

    printf("long %u\n", (unsigned)sizeof(long));

    printf("long long %u\n", (unsigned)sizeof(long long));

    printf("float %u\n", (unsigned)sizeof(float));

    printf("double %u\n", (unsigned)sizeof(double));

    printf("long double %u\n", (unsigned)sizeof(long double));

    printf("void* %u\n", (unsigned)sizeof(void*));

    printf("int* %u\n", (unsigned)sizeof(int*));

    printf("int** %u\n", (unsigned)sizeof(int**));

    return 0;

}

riportare il modello di computer (CPU, sistema operativo e compilatore) e i risultati ottenuti.

Esercizio 4

Usare il seguente programma per determinare il verso di crescita della stack dei record di attivazione della propria piattaforma di calcolo:

#include <stdio.h>

void r(int n) {

    if (n < 1) return;

    printf("%lu\n", (unsigned long)&n);

    r(n-1);

}

int main() {

    r(10);

    return 0;

}

Compilare il programma in gcc con l'opzione -O0 e riportare l'output dell'esecuzione del programma.

Esercizio 5

Sia x una variabile di tipo int, p una variabile di tipo int* e q una variabile di tipo int**. Per ciascuna delle seguenti espressioni C:

x
x+1
&x
&(x+1)
&&x
*x
*&x
&*q
*&*&x
&p
*p
*p+x
**q
&**q
&q

dire:

se è una espressione valida
in caso affermativo determinarne:
- la categoria (LValue o RValue∞).
- il tipo (es. int, int*, ecc.)

Ad esempio, l'espressione *p-5 è un Rvalue di tipo int.

Esercizio 6

Scrivere una funzione C get_min che, dato un array di interi e la sua dimensione, restituisce l'indirizzo del primo byte della cella contenente il minimo dell'array. La funzione deve avere il seguente prototipo:

int* get_min(int* v, int n);

Dove v è l'array e n la sua dimensione.

Scrivere inoltre un main di prova che alloca dinamicamente un array di n=1000 elementi, lo inizializza in modo tale che v[i]=55+(n-i) % 100, chiama la funzione get_min e stampa il valore del minimo calcolato. Verificare con memcheck che non ci siano errori nell'uso della memoria.

Esercizio 7

Scrivere una funzione get_bit_array che, dato un numero x a 64 bit senza segno, restituisce un array v di 64 char allocato dinamicamente tale che v[i] vale 1 se e solo il bit i-esimo di x, con i compreso tra 0 (bit meno significativo) e 63 (bit più significativo), è settato a 1, e 0 altrimenti. Scrivere il programma in modo da poter compilare correttamente il seguente programma di prova:

#include <stdio.h>

#include <stdlib.h>

// inserire qui la definizione della funzione get_bit_array

int main() {

    int i;

    unsigned long x = 5234971543233487563;

    char* v = get_bit_array(x);

    for (i=63; i>=0; i--) printf("%d", v[i]);

    printf("\n");

    free(v);

    return 0;

}

Il programma deve stampare: 0100100010100110010110101110000111101011101101011110001011001011.

Esercizio 8

Scrivere una funzione int cerca(int* v, int n, int x) che, dato un array ordinato di interi v di dimensione n e un intero x, restituisce 1 se x è presente nell'array, e 0 altrimenti. La funzione deve richiedere tempo O(log n). Scrivere un main di prova per testare la correttezza della funzione realizzata. Produrre una variante iterativa e una ricorsiva della funzione.

Esercizio 9

Scrivere una funzione void bubblesort(int* v, int n) che ordina l'array v di n interi passato come parametro usando l'algoritmo di ordinamento a bolle (bubblesort∞). Scrivere un main di prova per testare la correttezza della funzione realizzata.

Esercizio 10

Scrivere una funzione void merge(int* v, int i, int m, int j, int* temp) che, dato un array v, fonde le due porzioni da v[i] a v[m-1] e da v[m] a v[j-1], che si assume siano internamente ordinate, in modo che i j-i interi inizialmente presenti nelle due porzioni appaiano alla fine ordinati nella porzione dell'array che va da v[i] a v[j-1]. Usare come appoggio l'array temp, che si assume sia di dimensione almeno j-i. La realizzazione di questo esercizio è preliminare all'esercizio 8. Scrivere un main di prova per testare la correttezza della funzione realizzata.

Ad esempio, consideriamo l'array:

v={5, 6, 9, 12, 1, 4, 7}

e gli indici i=0, m=4 e j=7. Le due porzioni internamente ordinate sono {5, 6, 9, 12} (indici da 0 a 3) e {1, 4, 7} (indici da 4 a 6). Dopo l'esecuzione della funzione merge, l'array deve essere:

v={1, 4, 5, 6, 7, 9, 12}

La funzione deve richiedere tempo O(j-i).

Esercizio 11

Scrivere una funzione void mergesort(int* v, int n) che ordina l'array v di n interi passato come parametro usando l'algoritmo di ordinamento per fusione (mergesort∞). Scrivere un main di prova per testare la correttezza della funzione realizzata.

Esercizio 12

Scrivere una funzione void get_freq(int* v, int n, int* most_freq, int* less_freq) che, dato un array v di interi di dimensione n, restituisce in most_freq l'elemento più frequente di v (cioè quello che occorre il maggior numero di volte) e in less_freq l'elemento meno frequente. L'algoritmo deve essere il più possibile efficiente asintoticamente e certamente meno che quadratico. Scrivere un programma di prova per testare la correttezza della funzione scritta.

Esercizio 13

Confrontare sperimentalmente il tempo richiesto dalla soluzione all'esercizio 8 compilata:

senza ottimizzazioni
con ottimizzazione -O1
con ottimizzazione -O2

usare il comando time per misurare le prestazioni, facendo la media dei tempi real ottenuti su esecuzioni diverse e verificando che il tempo speso da processi in background è il più basso possibile. L'array di input dovrebbe contenere almeno 1 milione di interi. Riportare insieme alle misurazioni le caratteristiche software/hardware della piattaforma usata (CPU, memoria, sistema operativo, compilatore, ecc.)

Esercizio 14

Scrivere una funzione int codifica(short a, short b) che, dati due short a e b, restituisce un opportuno int da cui sia possibile in seguito ricostruire i due interi a e b. Scrivere poi una seconda funzione void decodifica(int x, short* ap, short* bp) che, dato un intero x precedentemente restituito da codifica, restituisce in *ap e in *bp gli interi a e b originari codificati in x.

Si assuma che sizeof(int)==2*sizeof(short).

Si consideri ad esempio il seguente programma di prova:

main.c

#include <stdio.h>

int main(){

    short a, b;

    int x = codifica(971, 1080);

    decodifica(x, &a, &b);

    printf("a=%hd, b=%hd\n", a, b); // stampa a=971, b=1080

}

Esercizio 15

Scrivere una funzione int** allocaMatriceInt(unsigned int r, unsigned int c) che alloca dinamicamente una matrice di interi con r righe e c colonne e restituisce l'indirizzo della matrice. Allocare separatamente le righe e restituire un array di puntatori alle righe. Scrivere la corrispondente funzione void deallocaMatriceInt(int** m, int r) che libera la memoria precedentemente allocata con allocaMatriceInt, assumendo che la matrice abbia r righe. Scrivere un programma di prova per verificare la correttezza delle funzioni scritte.

Esercizio 16

Si scrivano le seguenti funzioni per la gestione di matrici di oggetti di dimensione arbitraria:

void* newMatrix(unsigned r, unsigned c, unsigned k) che alloca dinamicamente una matrice con r righe e c colonne avente celle di k byte e restituisce l'indirizzo della matrice. I byte della matrice devono essere consecutivi (rappresentazione row-major∞) e devono essere inizializzati a zero.
void deleteMatrix(void* m) che libera la matrice m precedentemente allocata con newMatrix;
void setCell(void* m, unsigned i, unsigned j, const void* buf) che, data una matrice m, assegna alla cella (i,j) il valore all'indirizzo buf;
void getCell(void* m, unsigned i, unsigned j, void* buf) che, data una matrice m, assegna all'indirizzo buf il valore della cella (i,j);
void* cellAt(void* m, unsigned i, unsigned j) che, data una matrice m, restituisce l'indirizzo della cella (i,j).

Si consideri ad esempio il seguente programma di prova:

testMatrici.c

int main(){

    void* m = newMatrix(10, 20, sizeof(double));

    double x = 3.14, y;

    setCell(m, 2, 4, &x);

    getCell(m, 2, 4, &y);

    printf("la cella (2,4) contiene il valore: %f\n", y);

    printf("la cella (2,4) contiene il valore: %f\n", *(double*)cellAt(m, 2, 4));

    *(double*)cellAt(m, 3, 1) = 2.56;

    getCell(m, 3, 1, &y);

    printf("la cella (3,1) contiene il valore: %f\n", y);

    deleteMatrix(m);

    return 0;

}

Suggerimento: in newMatrix allocare un unico blocco contiguo di 2*sizeof(unsigned)+r*c*k byte contenente:

primi sizeof(unsigned) byte: numero c di colonne della matrice;
successivi sizeof(unsigned) byte: numero k di byte per cella;
a seguire le celle della matrice disposte in ordine row-major∞.

Nota: unsigned è equivalente in C a unsigned int.

Esercizio 17

Scrivere una funzione C che, data una stringa, restituisce una nuova stringa ottenuta da quella di partenza rovesciandola. Si consideri ad esempio il seguente programma di prova:

main.c

#include <stdio.h>

int main(){

    char* s = rovescia("roma");

    printf("%s\n", s); // stampa amor

    free(s);

}

Nota: lo specificatore di formato %s serve per stampare una stringa il cui indirizzo è passato come argomento alla printf.

Esercizio 18

Modificare la funzione scritta nell'esercizio 17 in modo che non dia l'indirizzo della nuova stringa come valore restituito, ma come parametro passato per riferimento. Si veda il seguente programma di prova:

main.c

#include <stdio.h>

int main(){

    char* s;

    rovescia("roma", &s);

    printf("%s\n", s); // stampa amor

    free(s);

}

Esercizio 19

Scrivere una funzione void concat(char* s1, char* s2, char** p) per concatenare due stringhe in un nuovo blocco restituito per parametro.

Esercizio 20

Scrivere una funzione C void occorrenze(char* s, char c, char*** occp, int* np) che, data una stringa s e un carattere c, conta il numero di occorrenze di c in s, che viene restituito in *np, e restituisce in *occp l'indirizzo di un nuovo array di char* contentente gli indirizzi di ciascuna delle occorrenze di c in s.

Si consideri ad esempio il seguente programma di prova:

main.c

#include <stdio.h>

int main(){

    int i, n;

    char** occ;

    occorrenze("ingegneria", 'g', &occ, &n);

    for (i=0; i<n; ++i) printf("%s\n", occ[i]); // stampa gegneria e gneria

    free(occ);

}

Esercizio 21

Scrivere una funzione int tokenize(char* s, char* f, char*** tp, int* np) che, data una stringa s, crea un array di stringhe che contiene tutti i token di s separati da un qualche carattere della stringa f. La funzione deve passare al chiamante in *tp l'indirizzo dell'array dei token creato e in *np la sua dimensione. Inoltre, deve restituire 0 se l'operazione ha avuto successo e -1 altrimenti. La funzione deve richiedere tempo O(strlen(s)*strlen(f)) e usare spazio O(strlen(s)+strlen(f)).

Si consideri ad esempio il seguente programma di prova:

#include <stdio.h>

#include <stdlib.h>

int main() {

    char** t;

    int n, i;

    if (tokenize("uno, due, tre:\n fante cavallo e re", " ,:\n", &t, &n)==-1)

        exit((fprintf(stderr, "error in tokenize\n"), 1));

    for (i=0; i<n; i++) { printf("%s\n", t[i]); free(t[i]); }

    free(t);

    return 0;

}

Il programma dovrebbe stampare:

uno
due
tre
fante
cavallo
e
re

Esercizio 22

Scrivere una funzione void short2binary(short x, char* s) che, dato uno short x e un puntatore s a un buffer (cioè zona di memoria libera) di almeno 8*sizeof(short)+1 byte, scrive in quel buffer una stringa C formata dai caratteri '0' e '1' corrispondenti ai bit di x, con s[0] il bit più significativo di x.

Si consideri ad esempio il seguente programma di prova:

short2binary.c

#include <stdio.h>

#include <stdlib.h>

int main(){

    char* s = malloc(8*sizeof(short)+1);

    short2binary(22971, s);

    printf("%s\n", s); // stampa: 0101100110111011

    free(s);

}

Esercizio 23

In base alle regole di precedenza e associatività degli operatori C∞, scrivere per ciascuna delle seguenti espressioni un'espressione equivalente che usa parentesi per esplicitare l'ordine di valutazione degli operatori (es: x+y*z => x+(y*z)):

*p++
y = ~x - x + z / 2 * k ^ w
x = y = z
x < y + z
x == y < z
x + y << z ? 1 : x, y
x < y <= z
*p == NULL ? -1 : 0
p = malloc(n*sizeof(int)) == NULL

Esercizio 24

Completare il seguente programma in modo che stampi su schermo i parametri passati al programma (ad esempio da riga di comando):

main.c

int main(int argc, char** argv) {

    ...

    return 0;

}

Si tenga presente che:

argv è un array di stringhe che contiene i parametri passati al programma;
argc è la dimensione di argv.

Sctrivere la soluzione in modo da ottenere il seguente risultato:

$ gcc main.c
$ ./a.out pippo paperino pluto
pippo
paperino
pluto

Esercizio 25

Si consideri la seguente dichiarazione di un nodo di una lista collegata di interi:

typedef struct node {

    int elem;

    struct node* next;

} node;

Scrivere una funzione nodo* add(int elem, node* list) che, dato un puntatore al primo nodo di una lista, o NULL per indicare una lista vuota, inserisce in testa alla lista un nuovo nodo contenente il dato elem, e restituisce il puntatore al nodo creato.
Scrivere una funzione void print(node* list) che, data una lista, ne stampa il contenuto nel formato: [elem1, elem2, elem3, ...].
Scrivere una funzione void delete(node* list) che, data una lista, ne dealloca tutti i nodi.

Usare il seguente programma di prova:

main.c

#include <stdio.h>

typedef struct node {

    int elem;

    struct node* next;

} node;

// mettere qui la definizione delle funzioni add, print e delete

int main() {

    node* list = add(5, add(3, add(2, add(7, add(4, add(1, add(6, NULL)))))));

    print(list); // stampa: [5, 3, 2, 7, 4, 1, 6]

    delete(list);

    return 0;

}

Verificare con memcheck (Valgrind) che il programma usi la memoria correttamente.

Esercizio 26 (espressioni di tipo)

Si traduca in C la seguente dichiarazione di variabile usando le regole sulla specifica di espressioni di tipo (si veda [P2∞]):

"v è un array di 64 puntatori a puntatori a funzione che prende come parametro un puntatore a funzione senza argomenti che restituisce un puntatore a un array di 16 float, e restituisce un puntatore a funzione con due argomenti int che restituisce void."

Esercizio 27 (espressioni di tipo)

Si traduca in italiano la seguente dichiarazione C:

int (*(*p)[7])(int *(*f[20])(float** m, int r), void* q[20]);

Esercizio 28 (espressioni di tipo)

Si traducano in italiano le seguenti dichiarazioni C:

char ****q[30];
char **(**q)[30];
int (x)[];
long (*a[])( char, char );
int *(*(*(*b)())[10])();
char *strprt( char (*)( int ), unsigned char );
int (*ab[])( unsigned int );

Esercizio 29 (puntatori a funzione)

Si fornisca una propria definizione della funzione standard qsort∞ di ordinamento, usando un algoritmo a scelta. La funzione ha il seguente prototipo dichiarato nella header stdlib.h:

void qsort(void *base, size_t nel, size_t width, int (*compar)(const void *, const void *));

dove:

base è l'indirizzo del primo byte di un array di oggetti da ordinare
nel è il numero di oggetti nell'array
width è la dimensione di un oggetto in byte
compar è l'ìndirizzo di una funzione di confronto che restituisce:
- un intero < 0 se l'oggetto puntato dal primo parametro è minore dell'oggetto puntato dal secondo parametro
- 0 se l'oggetto puntato dal primo parametro è uguale all'oggetto puntato dal secondo parametro
- un intero > 0 se l'oggetto puntato dal primo parametro è maggiore dell'oggetto puntato dal secondo parametro

Esercizio 29 (preprocessore)

Cosa stampa il seguente programma e perché?

#include <stdio.h>

#define STAMPA_SE_POSITIVO(x) if ((x) > 0) printf("%d\n", x)

int main() {

    int x = 0;

    STAMPA_SE_POSITIVO(++x);

    return 0;

}

Si ricordi che, se una variabile intera x vale k, l'espressione ++x vale k+1 e la sua valutazione incrementa x di 1 come effetto collaterale (side-effect).

Esercizio 30 (preprocessore)

Cosa stampa questo programma?

scambia1.c

#include <stdio.h>

#define SCAMBIA(a, b)  temp=a; a=b; b=temp;

int x = 5, y = 10, temp;

int main() {

    if (x > y) SCAMBIA(x, y);

    printf("x=%d, y=%d\n", x, y);

    return 0;

}

Il risultato è quello che ci si aspetta? In caso contrario, correggere il programma senza toccare il main.

Esercizio 31 (preprocessore)

Si provi a compilare il seguente programma:

scambia2.c

#define SCAMBIA(a, b)  { int temp=a; a=b; b=temp; }

int x = 10, y = 5, z = 4;

int main() {

    if (x < 0)

        SCAMBIA(x, y);

    else

        SCAMBIA(x, z); 

    return 0;

}

Che errore viene segnalato? Correggere il programma senza toccare il main.

Esercizio 32 (preprocessore)

Fornire una soluzione alternativa all'esercizio 14 in cui codifica e decodifica sono macro piuttosto che funzioni C. Usare il seguente programma di prova che misura il tempo necessario per 100 milioni di invocazioni di codifica e decodifica:

main.c

#include <stdio.h>

#include <time.h>

int main(){

    int i;

    long start = clock();

    for (i=0; i<100000000; i++){

        short a, b;

        int x = codifica(971, 1080);

        decodifica(x, &a, &b);

    }

    printf("elapsed time: %f sec\n", (clock()-start)/(double)CLOCKS_PER_SEC);

}

Che differenze di tempi si riscontrano definendo codifica e decodifica come macro C piuttosto che come funzioni C?

Nota: è possibile usare il backslash (\) immediatamente seguito da ritorno a capo per definire macro su più linee di testo.

Esercizio 33 (tipi di dato astratti)

Realizzare in C un tipo di dato astratto pila di interi (stack) definendo un opportuno tipo intstack, con le seguenti operazioni:

intstack* intstack_new(): crea un nuovo oggetto pila di interi e ne restituisce l'indirizzo;
void intstack_delete(intstack* s): dealloca un oggetto pila precedentemente creato;
void intstack_push(intstack* s, int elem): aggiunge un elemento in cima alla pila;
int intstack_pop(intstack* s): se la pila non è vuota, ne rimuove l'elemento in cima e restituisce 0, altrimenti restituisce -1.
int intstack_top(intstack* s, int* elem): se la pila non è vuota, ne copia l'elemento in cima in *elem (senza toglierlo dalla pila) e restituisce 0, altrimenti restituisce -1.
int intstack_is_empty(intstack* s): restituisce 1 se la pila è vuota, e 0 altrimenti.

In particolare:

Creare una header intstack.h contenente:
- la dichiarazione di un tipo intstack come alias di una struttura incompleta struct intstack
- i prototipi delle funzioni del tipo di dato matrice previste dall'esercizio
Creare un file intstack.c contenente:
- la dichiarazione del tipo struct intstack completo di tutti i campi richiesti da un oggetto intstack
- la definizione delle funzioni che operano su oggetti intstack usando una lista collegata semplice
Creare un file intstack_test.c contenente un programma di prova per testare il funzionamento del codice scritto

Esercizio 34 (tipi di dato astratti)

Realizzare in C un tipo di dato astratto stack analogo a quello definito nell'esercizio 9, ma in cui il tipo degli elementi è generico:

stack* stack_new(unsigned elem_size): crea un nuovo oggetto pila di oggetti di dimensione elem_size e ne restituisce l'indirizzo;
void stack_delete(stack* s): dealloca un oggetto pila precedentemente creato;
void stack_push(stack* s, void* elem): aggiunge l'oggetto puntato da elem in cima alla pila;
int stack_pop(stack* s): se la pila non è vuota, ne rimuove l'elemento in cima e restituisce 0, altrimenti restituisce -1.
int stack_top(stack* s, void* elem): se la pila non è vuota, ne copia all'indirizzo elem l'elemento in cima (senza toglierlo dalla pila) e restituisce 0, altrimenti restituisce -1.
int stack_is_empty(stack* s): restituisce 1 se la pila è vuota, e 0 altrimenti.

Scrivere un programma di prova per testare il funzionamento del codice scritto.

Suggerimento: usare la funzione memcpy∞ definita in <string.h> per copiare i byte dei valori da leggere/scrivere nella pila.

Esercizio 35 (tipi di dato astratti)

Realizzare in C un tipo di dato astratto matrice di interi definendo un opportuno tipo intmat, con le seguenti operazioni:

costruttore: intmat* intmat_new(unsigned rows, unsigned cols) che alloca una nuova matrice di int con rows righe e cols colonne
distruttore: void intmat_delete(intmat* m) che, data la matrice m, la dealloca
void intmat_set_cell(intmat* m, unsigned i, unsigned j, int val) che assegna alla cella (i,j) della matrice m il valore val
void intmat_get_cell(intmat* m, unsigned i, unsigned j, int* val) che assegna all'indirizzo val il contenuto della cella (i,j) della matrice m
unsigned intmat_get_num_rows(intmat* m) che restituisce il numero di righe della matrice m
unsigned intmat_get_num_cols(intmat* m) che restituisce il numero di colonne della matrice m
void intmat_transpose(intmat* m) che traspone la matrice m
intmat* intmat_copy(intmat* m) che crea una copia identica della matrice m
intmat* intmat_sum(intmat* a, intmat* b) che produce una nuova matrice ottenuta come somma delle matrici a e b
intmat* intmat_prod(intmat* a, intmat* b) che produce una nuova matrice ottenuta come prodotto delle matrici a e b

In particolare:

Creare una header intmat.h contenente:
- la dichiarazione di un tipo intmat come alias di una struttura incompleta struct intmat
- i prototipi delle funzioni del tipo di dato matrice previste dall'esercizio
Creare un file intmat.c contenente:
- la dichiarazione del tipo struct intmat completo di tutti i campi richiesti da un oggetto intmat (es. numero righe, numero colonne, puntatore alla matrice dei dati)
- la definizione delle funzioni che operano su oggetti intmat
Creare un file intmat_test.c contenente un programma di prova per testare il funzionamento del codice scritto

Suggerimento: la matrice deve essere allocata dinamicamente, usando un array di puntatori alle righe della matrice, ciascuna allocata indipendentemente come array di interi (come avviene in Java).

Esercizio 36 (tipi di dato astratti, puntatori a funzione)

Realizzare in C un tipo di dato astratto matrice analogo a quello definito nell'esercizio 10, ma in cui il tipo degli elementi è generico:

costruttore: mat* mat_new(unsigned rows, unsigned cols, unsigned itemSize, void (*sum)(void*, void*, void*), void (*prod)(void*, void*, void*)) che alloca una nuova matrice con rows righe, cols colonne, celle di dimensione itemSize byte e definisce come operazioni somma e prodotto sugli elementi della matrice le funzioni sum e prod, rispettivamente. Le operazioni prendono tre parametri: l'indirizzo del primo operando, l'indirizzo del secondo operando, e l'indirizzo a cui deve essere scritto il risultato dell'operazione.
distruttore: void mat_delete(mat* m) che, data la matrice m, la dealloca
void mat_set_cell(mat* m, unsigned i, unsigned j, void* val) che assegna alla cella (i,j) della matrice m il valore all'indirizzo val
void mat_get_cell(mat* m, unsigned i, unsigned j, void* val) che assegna all'indirizzo val il contenuto della cella (i,j) della matrice m
unsigned mat_get_num_rows(mat* m) che restituisce il numero di righe della matrice m
unsigned mat_get_num_cols(mat* m) che restituisce il numero di colonne della matrice m
unsigned mat_get_item_size(mat* m) che restituisce la dimensione in byte dell'elemento generico della matrice m
void mat_transpose(mat* m) che traspone la matrice m
mat* mat_copy(mat* m) che crea una copia identica della matrice m
mat* mat_sum(mat* a, mat* b) che produce una nuova matrice ottenuta come somma delle matrici a e b
mat* mat_prod(mat* a, mat* b) che produce una nuova matrice ottenuta come prodotto delle matrici a e b

Esercizio 37

Si scriva un makefile per compilare in modo incrementale un programma formato dai seguenti file, in modo che ogni modifica a un file implichi il minimo numero di passi di ricompilazione dell'intero programma. Il file eseguibile di output deve chiamarsi versione1.

F.h

#ifndef _F_

#define _F_

#ifndef MESSAGE

#define MESSAGE "[versione 1] "

#endif

#define PRINT(x) printf("%s%s", MESSAGE, x)

#endif

A.h

#ifndef _A_

#define _A_

#include "F.h"

void a();

#endif

A.c

#include <stdio.h>

#include "A.h"

#include "B.h"

void a() {

    PRINT("a\n");

    b();

}

B.h

#ifndef _B_

#define _B_

#include "F.h"

void b();

#endif

B.c

#include <stdio.h>

#include "B.h"

void b() {

    PRINT("b\n");

}

main.c

#include <stdio.h>

#include "A.h"

int main() {

    PRINT("main\n");

    a();

    return 0;

}

Esercizio 38

Senza modificare in alcun modo i file .c e .h dell'esercizio 1, si estenda il makefile in modo che vengano create due versioni del programma:

versione1: in cui tutte le stampe effettuate dal programma iniziano per "[versione 1] "
versione2: in cui tutte le stampe effettuate dal programma iniziano per "[versione 2] "

Esercizio 39

Si crei una directory di lavoro progetto con la seguente struttura contenente i file dell'esercizio 2:

progetto
- include
  - A.h
  - B.h
  - F.h
- src
  - A.c
  - B.c
  - main.c
- bin
  - directory inizialmente vuota, conterrà i file oggetto e i file eseguibili prodotti dalla compilazione del programma
- makefile

Senza modificare in alcun modo i file .c e .h, si estenda quindi il makefile dell'esercizio 2 adattandolo alla nuova struttura in modo che i file oggetto (.o) e i file eseguibili prodotti vengano a trovarsi nella directory bin.

Ingegneria degli Algoritmi

Corso di Laurea in Ingegneria Informatica e Automatica - A.A. 2014-2015

Esercizi sul linguagggio C

Esercizio 1

Esercizio 2

Esercizio 3

Esercizio 4

Esercizio 5

Esercizio 6

Esercizio 7

Esercizio 8

Esercizio 9

Esercizio 10

Esercizio 11

Esercizio 12

Esercizio 13

Esercizio 14

Esercizio 15

Esercizio 16

Esercizio 17

Esercizio 18

Esercizio 19

Esercizio 20

Esercizio 21

Esercizio 22

Esercizio 23

Esercizio 24

Esercizio 25

Esercizio 26 (espressioni di tipo)

Esercizio 27 (espressioni di tipo)

Esercizio 28 (espressioni di tipo)

Esercizio 29 (puntatori a funzione)

Esercizio 29 (preprocessore)

Esercizio 30 (preprocessore)

Esercizio 31 (preprocessore)

Esercizio 32 (preprocessore)

Esercizio 33 (tipi di dato astratti)

Esercizio 34 (tipi di dato astratti)

Esercizio 35 (tipi di dato astratti)

Esercizio 36 (tipi di dato astratti, puntatori a funzione)

Esercizio 37

Esercizio 38

Esercizio 39