Matrices

Cours/Système et réseau/C pour le système/Exercices/Matrices

On souhaite créer un module permettant de gérer des matrices d'entiers.

Implémentation v1 : double indirection

Si l'on considère une matrice comme un tableau de lignes, implémentez une fonction de signature :

int **matrice_create(size_t nombre_lignes, size_t nombre_colonnes);

Qui crée dynamiquement une matrice où chaque élément vaut 0.

On va ajouter une fonction pour afficher la matrice à l'écran :

Créez une fonction qui affiche à l'écran une matrice crée par la fonction matrice_create. Elle devra afficher par exemple :

1  2   3
11 4 111

Sa signature sera :

void matrice_show(int **matrice, size_t nombre_lignes, size_t nombre_colonnes);

Vous pourrez utiliser le formatage des entiers de printf pour justifier les entiers à droite (en supposant par exemple qu'ils ont tous au plus 3 chiffres).

Utilisons les matrices :

Le programme principal crée une matrice à 4 lignes et 6 colonnes et affecte $i+j$ à l'élément de ligne $i$ et de colonne $j$. Puis affichez là.

Il nous rest à créer la fonction qui supprime la matrice :

Créez une fonction de signature :

void matrice_destroy(int **matrice, size_t nombre_lignes, size_t nombre_colonnes);

Qui supprime une matrice précédemment crée avec la fonction matrice_create.

Peut-on simplifier la fonction précédente en :

supprimant le paramètre nombre_colonnes ?
supprimant le paramètre nombre_lignes ?

Si oui, le faire.

corrigé

Comme la matrice est crée comme un tableau de ligne, le nombre de colonnes est superflu : on libère juste chaque ligne une à une.

Implémentation v2 : simple indirection

L'implémentation précédente va créer des lignes qui peuvent êtres à des endroits différents de la mémoire. On veut ici créer une matrice à un seul endroit de la mémoire (pour éviter les défauts de cache potentiels) et rassembler les lignes et les connes en un seul tableau où les lignes sont mises bout à bout.

Réimplémentez les fonctions de création et de suppression de la matrice avec cette nouvelle structure. Les signatures des fonctions seront maintenant :

int *matrice_create(size_t nombre_lignes, size_t nombre_colonnes);
void matrice_destroy(int *matrice);
void matrice_show(int *matrice, size_t nombre_lignes, size_t nombre_colonnes);

Il est cependant maintenant plus dur d'accéder directement à un élément de la matrice. Créons des fonctions pour nous aider :

Faire des fonctions permettant d'accéder et de modifier un élément de la matrice et utilisez les dans vos fonctions. Ces fonctions doivent être de signature :

int matrice_get(int *matrice, size_t ligne, size_t colonne, size_t nombre_colonnes);
int matrice_set(int *matrice, int element, size_t ligne, size_t colonne, size_t nombre_colonnes);

Implémentation v3 : pointeur opaque

Manipuler une matrice devient très lourd puisqu'il faut connaître et stocker les dimension de la matrice. Améliorons ça :

Proposez une structure permettant de stocker la matrice et tous ses paramètres

corrigé

struct matrice {
  int *matrice;
  size_t lignes;
  size_t colonnes;
}

Utilisez cette structure dans toutes les fonctions. Elles deviennent de signature :

matrice *matrice_create(size_t nombre_lignes, size_t nombre_colonnes);
void matrice_destroy(matrice *m);
void matrice_affiche(matrice *m);
int matrice_get(matrice *m, size_t ligne, size_t colonne);
void matrice_set(matrice *m, int element, size_t ligne, size_t colonne);

Pour que les utilisateurs ne puissent pas connaître le contenu de la structure on peut organiser les fichiers de telle sorte de cacher la structure proprement dite.

On appelle cette façon de faire :

Technique du pointeur opaque

Pour que la technique du pointeur opaque fonctionne, il faut séparer les déclarations des fonctions (les .h) et leurs implémentations (les .c) :

Séparer le fichier unique en trois fichiers : matrice.h, matrice.c et main.c et créez un fichier Makefile pour compiler le projet.

Pour le pointeur opaque on doit modifier les .h pour qu'ils connaissent un pointeur sur la structure mais pas la structure. Ce qui donne pour notre matrice :

Fichier matrice.h :

#ifndef FILE_MATRICE
#define FILE_MATRICE

typedef struct matrice* matrice_t;

// déclaration des fonctions

#endif

Fichier matrice.c :

#define "matrice.h"

struct matrice {
  int *matrice;
  size_t lignes;
  size_t colonnes;
}

// corps des fonctions

Implémentez cette nouvelle (et dernière) façon d'utiliser des matrices.

Pourquoi appelle-t-on ce pattern de création de structure "pointeur opaque" ?
en quoi cela peut-il faire penser à de la programmation objet ?

corrigé

On connaît un pointeur sur la structure mais pas la structure elle-même. On est obligé de manipuler la structure via les fonctions, comme en programmation objets où l'on manipule les objets via leurs méthodes.

Les types opaques sont une façon très utilisée d'implémenter des structures en C.

Ce type de structure à un autre avantage, il permet de modifier la matrice sans modifier le pointeur opaque ! Pour s'en convaincre :

Ajouter à l'unité fonctionnelle une fonction de signature :

void matrice_transpose(matrice_t m);

Qui transpose la matrice.

Vous pourrez :

créer une nouvelle matrice m2 avec le même nombre de lignes et de colonnes que m
effectuer la transposition en plaçant les ligne de la matrice originelle dans la nouvelle matrice
terminer en affectant m2->matrice à m->matrice
libérer la mémoire allouée par m2 (sans libérer la matrice en elle même).

Dans le programme principale, après avoir affiché la matrice, transposez là et affichez la à nouveau.