Cette remise à niveau en C prend la forme de séances de TP dans lesquelles trois types d’activités sont à considérer :

1. lecture et compréhension du cours du semestre précédent ;
2. réflexion sur des exercices du semestre précédent ;
3. réalisation de quelques TP du semestre précédent.

Les explications et les corrections se font sur demande.

Au moindre doute, ne pas hésiter à poser des questions.

Cours

Voici le matériel de cours proposé au second semestre de la L2 d’informatique. Il donne une bonne idée du niveau attendu pour continuer l’apprentissage du C en L3. Il faut travailler en priorité les chapitres

• “1. Bases” ;
• “2. Habitudes” ;
• “3. Modules” ;
• “9. Opérateurs > Opérateurs bit à bit” ;
• “10. Pointeurs de fonction”.

Et voici quelques remarques issues des examens des années précédentes.

Exercices

Voici un ensemble d’exercices partitionné selon les thèmes les plus saillants. Il est n’est pas demandé de tout faire mais il faut avoir une idée précise de ce qui est demandé, exercice par exercice.

Les exercices les plus importants sont les

• 1.4. (représentation des entiers) ;
• 2.1. (expressions, instructions, effets de bord) ;
• 2.2. (fonctions à effets de bord) ;
• 5.1. (pré-assertions) ;
• 5.2. (fonctions à gestion d’erreurs) ;
• 6.1. (compilation séparée) ;
• 7.1. (pointeurs) ;
• 7.6. (valeurs en mémoire) ;
• 8.2. (pointeurs de fonctions et tableaux) ;
• 8.3. (pointeurs de fonctions et tris) ;
• 9.2. (test d’égalité générique) ;
• 9.3. (tableaux génériques).

Il est aussi possible de travailler sur le sujet d’examen de l’année dernière.

Structures de données usuelles

Contrairement à d’autres langages modernes, le C ne fournit pas directement de structures de données complexes mais seulement les outils pour les construire. Étant donnée un type de donnée T (int, char, int*, struct S…), il est attendu de savoir implémenter les structures de données suivantes.

Tableau dynamique

Habituellement de la forme :

struct TabDynT {
   T *elements;  // Pointeur vers la zone mémoire contenant les éléments
   int capacite; // Capacité de la zone
   int taille;   // Nombre d'éléments présents dans la zone
};
typedef struct TabDynT TabDynT;

Les fonctionnalités attendus sont :

• Créer un tableau dynamique vide de capacité donnée
• Redimensionner un tableau dynamique (et changer sa capacité)
• Ajouter un élément en fin de tableau
• Tester si un tableau est vide
• Détruire un tableau dynamique (en libérant la zone mémoire)

Liste chainée

Habituellement définie comme une succession de nœuds reliés entre eux :

struct CelluleT {
    T valeur;                 // Valeur stocké dans la cellule
    struct CelluleT *suivant; // Chainage
};
typedef struct CelluleT CelluleT;
typedef CelluleT *ListeT;

Les fonctionnalités attendues sont :

• Créer une liste vide
• Insérer un élément en tête ou en fin de liste
• Supprimer un élément (en tête, en fin, ou par valeur)
• Rechercher un élément donné
• Tester si la liste est vide
• Détruire toute la liste

Note : La suppression par valeur et la recherche nécessite une fonction pour comparer deux valeurs de type T.

Arbre binaire

Défini comme une structure récursive où chaque nœud pointe vers deux sous-arbres :

struct NoeudT {
    T valeur;
    struct NoeudT *gauche;
    struct NoeudT *droite;
};
typedef struct NoeudT NoeudT;
typedef NoeudT *ArbreT;

Les fonctionnalités attendues sont :

• Créer un arbre vide
• Insérer un élément (selon les règles de l’arbre binaire de recherche si applicable)
• Rechercher un élément
• Parcourir l’arbre (préfixe, infixe, suffixe, en largeur)
• Détruire l’arbre

Pile

Structure respectant le principe LIFO (Last In, First Out).

Les fonctionnalités attendues sont :

• Créer une pile vide
• Empiler un élément (ajout sur le sommet)
• Dépiler un élément (retrait du sommet)
• Consulter l’élément au sommet sans le retirer
• Tester si la pile est vide
• Détruire la pile

File

Structure respectant le principe FIFO (First In, First Out).

Les fonctionnalités attendues sont :

• Créer une file vide
• Enfiler un élément (ajout en fin)
• Défiler un élément (retrait en tête)
• Consulter l’élément en tête sans le retirer
• Tester si la file est vide
• Détruire la file

File de priorité

Structure où chaque élément est associé à une priorité, l’extraction se fait toujours sur l’élément de plus haute priorité.

Les fonctionnalités attendues sont :

• Créer une file de priorité vide
• Insérer un élément avec une priorité donnée
• Extraire l’élément de priorité maximale (ou minimale selon la convention)
• Consulter l’élément prioritaire sans l’extraire
• Tester si la structure est vide
• Détruire la file de priorité

Table de hachage

Voir le mini-projet.

Sujets de TP

Voici une sélection de cinq sujets de TP.

La bibliothèque ncurses est utilisée en L2 pour construire des applications et des interfaces graphiques. Ici, il est parfaitement autorisé d’utiliser d’autres bibliothèques graphiques comme la MLV ou encore la SDL. Des versions de ce qui est attendu simplement en mode texte sont par ailleurs parfaitement acceptables.

Contrairement à ce qui peut être indiqué dans les énoncés de ces TP, il est demandé ici d’utiliser toutes les méthodes de bonne conduite de projet : modularisation, documentation, pré-assertions, etc.

1. Partir sur de bonnes bases (pdf) — Cette fiche contient divers exercices de base qu’il est impératif de de maîtriser avant de passer aux suivantes.

2. Introduction aux outils de débogage (pdf) — Cette fiche présente les outils de débogage simple à mettre en place pour déboguer un programme C. Il est important de les avoir dans sa trousse à outils pour diagnostiquer aisément un large spectre de problèmes couramment rencontrés quand on programme en C.

3. Le jeu du Chomp (pdf) — L’objectif est de programmer pas à pas un jeu à deux joueurs au tout par tour.

4. Le jeu du serpent (pdf) — L’objectif est de programmer pas à pas le célèbre jeu du serpent. Le jeu est cette fois-ci en temps réel Il s’agit aussi de respecter les bonnes méthodes de modularisation et d’écriture de programmes

5. Compter les mots (pdf) — L’objectif est de programmer un utilitaire permettant de poser des questions sur un fichier texte comme par exemple le nombre d’occurrences d’un mot qu’il contient.

Mini-projets

En complément des sujets de TP, voici quelques mini-projets réalisable pendant les séances de remise à niveau.

Ces sujets sont peu spécifiés (à différents niveaux), il est donc important de commencer par une phase de modélisation avant de se plonger dans l’écriture de code. De manière générale, il faut :

• déterminer les objets et données abstraites que le programme va manipuler
• définir les opérations qui seront effectuées avec ces objets
• écrire et documenter les fichiers d’entêtes
• coder les opérations

Signature 2D de fichier

L’objectif est de produire à partir d’un fichier une image en niveau de gris de 256×256 pixels telle que plus la séquence de deux octets 0xXX 0xYY est fréquente dans le fichier, plus le pixel aux coordonnées (0xXX, 0xYY) est clair dans l’image.

Par exemple, dans un fichier source, la majorité des octets correspond à des caractères ASCII, donc compris entre 0 et 127. L’image obtenue sera claire sur un petit carré dans le coin supérieur gauche, et globalement noire ailleurs.

Travail demandé

Écrire un programme prenant en argument deux noms de fichier, réalise la signature du premier fichier et l’écrit sous la forme d’une image PGM dans le second fichier.

Notes

Le fichier PBM sera sous la forme :

P2 # Format niveau de gris ASCII
# Dimensions Largeur Hauteur
256 256
# Valeur maximum : Noir=0, Blanc=255
255
0 0 142 6 255 ...
...

Améliorations possibles

• Nommer automatiquement le fichier PGM en fonction du nom du fichier d’entrée
• Permettre de lire le fichier sur le flux standard d’entrée

Compétences mobilisées

• la lecture/écriture de fichier

Jeu de la vie et autres automates cellulaires.

L’objectif de ce mini-projet est de réaliser un programme implémentant un automate cellulaire. Un des automates cellulaires les plus connus est celui du Jeu de la vie de Conway.

Principe

On dispose d’une grille de cellules de dimensions Largeur x Hauteur où chacune des cellules est soit vivante, soit morte (il s’agit de l’état de la cellule). L’état de ces cellules évoluent simultanément suivant la règle locale suivante, pour chaque cellule

• on compte le nombre de ces 8 voisines qui sont vivantes
• si ce nombre est 2, la cellule conserve son état
• s’il est 3, la cellule devient vivante
• sinon la cellule devient morte.

On peut décrire cette règle aussi sous la forme :

• une cellule meurt si elle est isolée ou bien en cas de surpopulation
• une cellule naît si elle est entourée d’exactement 3 cellules vivantes.

À chaque étape, toutes les cellules évoluent en même temps (en changeant d’état ou en conservant leur état précédent).

Travail demandé

Écrire un programme qui prend en argument les dimensions de la grille, puis simule le jeu de la vie en affichant la grille étape par étape toutes les secondes. La grille initiale pourra être tirée aléatoirement.

Notes et conseils

• il peut être nécessaire d’allouer plusieurs tableaux
• isoler la fonction de transition (état de la cellule + états des cellules voisines -> nouvel état) permet d’envisager d’autres automates cellulaires

Améliorations possible

Le programme peut être enrichi avec différentes fonctionnalités :

• affichage graphique via ncurses ou MLV
• configuration initiale depuis un fichier
• changement d’état d’une cellule par un clic de souris
• choix du délai entre deux étapes
• implémentation d’autres automates cellulaires (plus d’états)

Compétences mobilisées

• la ligne de commande
• l’allocation dynamique
• les tableaux à deux dimensions

Convertisseur d’images dans les formats Portable pixmap

Il existe 6 variations de ce format correspondant à une combinaison d’un choix parmi noir/blanc, niveau de gris et couleur, avec un choix parmi textuel et binaire.

Travail demandé

Écrire un programme convertissant un fichier depuis un format vers un autre. Les options du programme seront contrôlées par les arguments dans la ligne de commande.

Notes

• On pourra supposer qu’aucun commentaire n’est présent dans le fichier
• Le format binaire noir/blanc P4 est plus exigeant que les autres.

Compétences mobilisées

• la ligne de commande
• la lecture/écriture de fichier
• l’allocation dynamique
• la manipulation de bits pour le format noir et blanc en binaire

Taille de fichier en UTF8

On souhaite déterminer si un fichier utilise l’encodage UTF-8 et combien de caractère Unicode il comporte le cas échéant.

Compétences mobilisées

• la lecture/écriture de fichier
• les opérations bits à bits

Arbre binaire de hachage

L’objectif est de créer un module permettant de représenter une structure d’ensemble (tel le premier TP d’algorithmique des arbres) en utilisant un arbre binaire de recherche. Les opérations devant être raisonnablement efficace, on utilisera le hachage des chaines de caractères dans les comparaisons plutôt que d’utiliser la chaine de caractère directement.

On pourra utiliser la fonction de hachage présentée dans le cours d’algorithmique et des structures de données du S3.

La suppression n’est pas demandé mais on s’attachera a libéré la mémoire allouée avant la fin du programme.

Compétences mobilisées

• la modélisation
• les opérations bits à bits
• l’allocation dynamique et la manipulation de pointeurs

Moteur physique pour particules

L’objectif est de proposer une simulation de déplacement de particules interagissant entre elles et avec la souris.

Une particule est caractérisé par sa position et sa vitesse. Une force peut être appliqué à une particule et impacte alors sa vitesse. La force exercée sur une particule peut provenir de la souris ou d’autres particules.

Par exemple, deux particules trop proches pourraient exercer l’une sur l’autre une force de répulsion. On pourrait avoir plusieurs types de particules (positive et négative, poule/renard/vipère…).

Formellement, le moteur fonctionne alors ainsi. À chaque mise à jour de l’affichage :

• Soit t le temps écoulé depuis le dernier affichage
• Pour chaque particule p :
  • force = interaction de la souris sur p
  • Pour chaque particule q :
    • force += interaction de q sur p
  • p.vitesse += force * t
• Pour chaque particule p :
  • p.position += p.vitesse * t

Compétences mobilisées

• la modélisation
• l’utilisation d’une bibliothèque externe (MLV, SDL, OpenGL)

Allocateur de mémoire

Une des difficultés (mais aussi un des avantages) de la programmation en C est la possibilité de gérer finement la mémoire. Cela passe souvent par l’écriture d’allocateurs mémoires qui ajoutent une surcouche aux classiques malloc/free.

Dans ce mini projet, on propose l’écriture d’un allocateur capable de libérer tous les objets dont il a connaissance, sans avoir à le faire à la main.

Travail demandé

Définir le type Allocator permettant de retenir les adresses des zones mémoires alloués dans une liste chainée.

// Réserve une zone mémoire de `sz` octets, stocke son adresse dans la liste chainé de `ator` et la renvoie
void *alloc_reserve(Allocator *ator, size_t sz);

// Libère toutes les zones réservées dont les adresses sont stockées dans la liste chainée de `ator`.
void alloc_destroy(Allocator *ator);

Il doit permettre l’écriture du code suivant :

// Initialise un nouvel allocateur
Allocator ator = {0};
// Exemple d'allocation
int *tab = alloc_reserve(&ator, sizeof (int) * 8);
// Partage de l'allocateur avec une fonction appelée
fonction_faisant_des_allocations(&ator, autres, arguments);
// Libération de toutes les zones mémoires allouées avec cet allocateur depuis son initialisation
alloc_destroy(&ator);

Notes

• Les fonctions alloc_reserve et alloc_destroy utilise malloc et free.
• On peut, dans un premier temps, se permettre deux allocations pour chaque appel à alloc_reserve.
• Sur nos systèmes actuelles, il n’est plus nécessaire de libérer la mémoire au moment où le programme s’arrête. Cependant, il est important de le faire pendant l’exécution. Exemple: un navigateur alloue de la mémoire pour chaque page visitée. Il est inconcevable de ne pas libérer cette mémoire au fur et à mesure. Même si les stratégies réelles sont plus complexes, on peut ici imaginer l’utilisation d’un allocateur par page afin de libérer en une seule fois tous les objets allouées lors de la navigation.
• Certains langages modernes intègrent dans leur cœur le concept d’allocateur (Zig, C++, Rust)

Compétences mobilisées

• Liste chainée
• Allocation dynamique

Table de hachage

L’objectif est proche de celui du TP Compteur les mots (voir plus bas) mais est axé sur l’implémentation (guidée) d’une table de hachage.

Le sujet se trouve ici et les fichiers complémentaires sont dans l’archive suivante.

Compétences mobilisées

• la modularisation
• l’allocation dynamique
• les pointeurs de fonction
• la lecture de fichier

Compléments

1. Introduction à Ncurses (pdf) — Cette fiche contient divers exercices de découverte de la bibliothèque ncurses.