Partie 1 - Bases de C

Pour l’organisation des fichiers (dossier p1/) et les options de compilation, voir les consignes. Pour l’utilisation de valgrind (et de l’option -g), voir la page Outils.

p1e1 : pointeurs simples, pointeurs et tableaux

Avant de commencer, relire le récapitulatif du passage par adresse (quand écrire * et &).

Écrire une fonction division_et_reste qui effectue la division entière de deux entiers a >= 0 et b > 0 :

void division_et_reste(int a, int b, int *quotient, int *reste);

La fonction ne retourne rien, mais stocke le quotient et le reste dans deux variables passées par adresse.

Écrire une fonction min_et_max qui recherche, dans un tableau d’entiers de taille taille (avec taille >= 1), le plus petit et le plus grand élément :

void min_et_max(const int *tab, size_t taille, int *min, int *max);

Les résultats seront renvoyés par deux variables passées par adresse.

Tester avec a = 17, b = 5 et le tableau {5, 9, 2, 7, 3} déclaré dans le main.

Résultat attendu (afficher le tableau avec ses éléments séparés par des virgules, puis le minimum et le maximum, chacun précédé d’une tabulation, \t) :

17 / 5 = 3, reste = 2

Tableau : 5, 9, 2, 7, 3
        - min : 2
        - max : 9

p1e2 : pointeurs et structures

Définir un type Duration (typedef struct { ... } Duration;) contenant 3 entiers non signés (unsigned int) : heures, minutes, secondes.

Dans le main, déclarer et initialiser :

  • d1 à 0h150min500s (valeur volontairement non normalisée, qui donne 2h38min20s une fois normalisée) ;

  • d2 à 5h35min58s ;

  • d3 à 2h45min06s.

Implémenter :

  • void print_duration(const Duration *d), qui affiche la durée au format hh:mm:ss (ex. 05:35:58, 02:45:06), sans retour à la ligne (le main ajoute le texte autour). Utiliser %02u : au moins 2 chiffres, complétés par des 0 (une valeur plus grande, comme 150, est affichée en entier) ;

  • void normalize_duration(Duration *d), qui normalise la durée (ex. 75s → 1min15s, 70min130s → 1h12min10s). Les heures ne sont pas limitées à 24. Indice : normaliser d’abord les secondes (la retenue s’ajoute aux minutes), puis les minutes ;

  • void add_duration(const Duration *d1, const Duration *d2, Duration *result), qui calcule result = d1 + d2, puis normalise result.

Les structures sont ici passées par adresse pour s’entraîner à -> et à const (voir le schéma d’une structure en mémoire).

Tester ces fonctions avec d1, d2, d3 et une variable Duration sum; (une structure, pas un pointeur : on passe &sum aux fonctions) pour stocker les résultats : afficher d1 brut, le normaliser puis l’afficher, afficher d2 et d3, puis les trois sommes.

Résultat attendu :

d1 brut      : 00:150:500
d1 normalisé : 02:38:20
d2           : 05:35:58
d3           : 02:45:06
d1 + d2 = 08:14:18
d2 + d3 = 08:21:04
d1 + d3 = 05:23:26

p1e3 : création de tableau dynamique

Écrire un programme C qui :

  • demande une taille de tableau (qui doit être > 0, sinon le programme se termine) ;

  • alloue dynamiquement un tableau d’entiers de cette taille (voir Gestion mémoire / Allocation dynamique) ;

  • remplit le tableau avec des valeurs aléatoires (voir Aléatoire ; srand ne doit être appelé qu’une seule fois) comprises dans l’intervalle [50, 100[ ;

  • affiche le contenu du tableau avec une fonction void print_table(const int *tab, size_t n).

Vérifier qu’il n’y a pas de fuites mémoire (voir Analyse à l’exécution).

Résultat attendu :

$ gcc -std=c2x -Wall -Wextra -pedantic -g p1/p1e3.c && valgrind ./a.out
... affichage de valgrind
Taille du tableau (>0) : 20
Contenu du tableau : 66 81 75 64 77 73 66 83 59 99 72 83 72 65 98 69 59 99 79 93
... affichage de valgrind sans fuites mémoire

p1e4 : modification de tableau dynamique

Reprendre le code précédent. Demander une nouvelle taille à l’utilisateur, puis redimensionner le tableau avec realloc en conservant les valeurs existantes (utiliser un pointeur temporaire, voir le schéma de realloc dans Gestion mémoire / Allocation dynamique). Si la nouvelle taille est plus grande, remplir les nouvelles cases avec des valeurs aléatoires : elles ne sont pas initialisées par realloc. Garder l’ancienne taille dans une variable pour savoir à partir de quel indice remplir. Si l’une des deux tailles saisies est <= 0, le programme se termine (en libérant la mémoire déjà allouée).

Afficher ensuite le nouveau tableau.

Vérifier qu’il n’y a pas de fuites mémoire (voir Analyse à l’exécution).

Résultat attendu :

$ gcc -std=c2x -Wall -Wextra -pedantic -g p1/p1e4.c && valgrind ./a.out
... affichage de valgrind
Taille du tableau (>0) : 20
Tableau initial : 57 75 71 71 99 91 73 73 81 87 65 76 94 73 78 80 51 56 67 79
Nouvelle taille (>0) : 10
Nouveau tableau : 57 75 71 71 99 91 73 73 81 87
... affichage de valgrind sans fuites mémoire
$ gcc -std=c2x -Wall -Wextra -pedantic -g p1/p1e4.c && valgrind ./a.out
... affichage de valgrind
Taille du tableau (>0) : 10
Tableau initial : 51 72 71 50 66 81 55 96 55 83
Nouvelle taille (>0) : 20
Nouveau tableau : 51 72 71 50 66 81 55 96 55 83 90 90 92 50 76 66 87 56 98 58
... affichage de valgrind sans fuites mémoire

p1e5 : tableau de chaînes de caractères

Le programme lit n chaînes au clavier, les range dans un tableau alloué dynamiquement, cherche la chaîne "coucou" puis affiche toutes les chaînes. En mémoire, on veut obtenir la même organisation que dans l’exemple Tableau de chaînes du cours : un tableau de n pointeurs, chacun vers sa propre copie de la chaîne saisie.

Étapes :

  1. Demander le nombre n de chaînes, qui doit être > 0 (sinon le programme se termine). Lire n avec read_line (donnée ci-dessous) puis atoi : mélanger scanf et fgets laisse un \n dans le buffer d’entrée, que le fgets suivant lirait comme une ligne vide.

  2. Allouer dynamiquement un tableau arr de n pointeurs char * (char **arr).

  3. Pour chaque case i : lire la chaîne dans un buffer de taille fixe (char buf[256]) avec read_line, allouer strlen(buf) + 1 octets pour arr[i] (+ 1 pour le \0), puis copier buf dans arr[i] avec strcpy. Une ligne trop longue pour le buffer est coupée : fgets lira la suite comme la chaîne suivante, ce qui est acceptable ici.

    Question : pourquoi ne peut-on pas simplement écrire arr[i] = buf; ? (Essayez, et regardez l’affichage final.)

  4. Parcourir le tableau et afficher l’indice (à partir de 0) de la première occurrence de "coucou" (comparer avec strcmp, pas avec ==).

  5. Afficher les chaînes du tableau.

  6. Libérer la mémoire avec une fonction void free_strings(char **arr, int n) : chaque chaîne, puis le tableau de pointeurs.

Fonctions utiles (inclure <string.h> et <stdlib.h>, ainsi que <stdbool.h> pour le type bool de read_line) :

  • strlen(chaine) pour obtenir la longueur d’une chaîne ;

  • strcpy(destination, source) pour copier une chaîne ;

  • fgets(buffer, taille, flux), qui, contrairement à scanf, lit aussi les espaces. Dans notre cas, le flux d’entrée (flux) sera stdin ;

  • atoi(chaine) pour convertir une chaîne en entier ;

  • strcmp(s1, s2) pour comparer deux chaînes (renvoie 0 si elles sont égales).

Voici une fonction read_line qui lit une entrée utilisateur et retire le \n :

/**
* @brief Lit une ligne (y compris les espaces) dans buffer et retire le '\n'
*
* @param buffer tableau dans lequel écrire les données
* @param taille nombre maximal de caractères (taille du tableau)
* @return true si la lecture a réussi, false sinon (fin de l'entrée ou erreur)
*/
bool read_line(char *buffer, int taille) {
    if (fgets(buffer, taille, stdin) == NULL) {
        buffer[0] = '\0';
        return false;
    }
    buffer[strcspn(buffer, "\n")] = '\0';
    return true;
}

Vérifier qu’il n’y a pas de fuites mémoire (voir Analyse à l’exécution).

Résultat attendu :

$ gcc -std=c2x -Wall -Wextra -pedantic -g p1/p1e5.c && valgrind ./a.out
... affichage de valgrind
Nombre de chaînes (>0) : 3
Chaîne 1 : hello
Chaîne 2 : hey
Chaîne 3 : hej

À la recherche de coucou...
coucou n'est pas dans le tableau

Affichage final :
[0] hello
[1] hey
[2] hej
... affichage de valgrind sans fuites mémoire
$ valgrind ./a.out
... affichage de valgrind
Nombre de chaînes (>0) : 3
Chaîne 1 : hello
Chaîne 2 : coucou
Chaîne 3 : hej

À la recherche de coucou...
coucou est trouvé à l'indice 1

Affichage final :
[0] hello
[1] coucou
[2] hej
... affichage de valgrind sans fuites mémoire

p1e6 : création de matrice dynamique

Écrire un programme C qui :

  • demande à l’utilisateur un nombre de lignes rows et de colonnes cols (strictement positifs) ;

  • alloue dynamiquement une matrice (int **, voir Gestion mémoire / Allocation dynamique, cas 1 : tableau de pointeurs) d’entiers de taille rows × cols à l’aide d’une fonction int **alloc_matrix(size_t rows, size_t cols) ;

  • la remplit avec des valeurs aléatoires dans l’intervalle [20, 60[ ;

  • l’affiche avec une fonction void print_matrix(int **matrix, size_t rows, size_t cols), qui affiche d’abord Matrice <rows>x<cols> :, puis les éléments séparés par une tabulation (\t), et revient à la ligne à chaque nouvelle ligne ;

  • calcule les sommes par ligne avec une fonction int *sum_rows(int **matrix, size_t rows, size_t cols), qui renvoie un tableau de rows sommes (une par ligne) alloué dynamiquement ;

  • calcule les sommes par colonne avec une fonction int *sum_columns(int **matrix, size_t rows, size_t cols), qui renvoie un tableau de cols sommes (une par colonne) alloué dynamiquement ;

  • affiche ces sommes dans le main ;

  • libère la matrice avec une fonction void free_matrix(int **matrix, size_t rows), sans oublier les tableaux renvoyés par sum_rows et sum_columns.

Prototypes à placer avant le main :

int **alloc_matrix(size_t rows, size_t cols);
void print_matrix(int **matrix, size_t rows, size_t cols);
int *sum_rows(int **matrix, size_t rows, size_t cols);
int *sum_columns(int **matrix, size_t rows, size_t cols);
void free_matrix(int **matrix, size_t rows);

Indices :

  • dans alloc_matrix, si l’allocation d’une ligne échoue, libérer ce qui a déjà été alloué (comme dans l’exemple du cours), puis renvoyer NULL ;

  • les sommes doivent partir de 0 : calloc alloue et met à zéro ;

  • les tableaux renvoyés par sum_rows et sum_columns sont alloués dans ces fonctions, mais c’est le main qui doit les libérer (voir Propriété de la mémoire) ;

  • free_matrix libère chaque ligne, puis le tableau des lignes (voir l’ordre des free sur le schéma du cours).

Vérifier qu’il n’y a pas de fuites mémoire (voir Analyse à l’exécution).

Résultat attendu :

$ gcc -std=c2x -Wall -Wextra -pedantic -g p1/p1e6.c && valgrind ./a.out
... affichage de valgrind
Nombre de lignes (>0) : 5
Nombre de colonnes (>0) : 3
Matrice 5x3 :
41      54      24
51      57      23
41      32      36
28      39      47
23      33      30
Somme des lignes :
119     131     109     114     86
Somme des colonnes :
184     215     160
... affichage de valgrind sans fuites mémoire