Structures de données

Introduction

Les programmes ont vocation à manipuler des données. Stocker ces dernières de façon sûre est essentiel, autant pour l’efficacité du programme que pour la lisibilité du code source. Le choix de certaines structures de données est évident, et nous pourrons citer les entiers, les nombres à virgule flottante ou les chaînes de caractères. Mais dès qu’il s’agit de listes de données, nous hésiterons sur le type de tableau à adopter ou même nous nous demanderons si le tableau est le plus adapté. Les recettes suivantes montrent certaines structures de données à partir de besoins génériques et indiquent en quoi elles sont adaptées.

Ce chapitre fait beaucoup appel aux structures de données définies dans la bibliothèque glib. Rappelons que les options du compilateur peuvent être obtenues avec glib-config --cflags ou pkg-config glib-2.0  --cflags, et les options de l’éditeur de liens avec glib-config --libs ou pkg-config glib-2.0 --libs. Dans le code source, veillez à inclure l’en-tête nécessaire de cette manière :

#include <glib.h>
 

Étant donné le nombre de fonctions de glib utilisées dans ce chapitre, nous n’y avons pas inclus les prototypes de ces fonctions. Vous pourrez les obtenir...

Choisir une structure pour une liste de données

Problème

Vous avez une liste de données et vous souhaitez connaître les structures de données les plus appropriées pour effectuer le bon choix.

Solution

Vous pouvez choisir entre les structures suivantes :

Structures de données

Discussion

Tableaux statiques

Un tableau statique est la structure de données la plus simple à créer. En voici deux exemples :

int tableau1[10]; 
struct tableau_t 
{ 
  int entier; 
  char *chaine; 
  float flottant; 
} tableau2[20]; 
int i; 
 
for (i = 0; i < 10; i++) 
  tableau1[i] = i; 
 
for (i = 0; i < 20; i++) 
  { 
    tableau2[i].entier = i; 
    tableau2[i].chaine = malloc (10 * sizeof *tableau2->chaine); 
    snprintf (tableau2[i].chaine, 10, "%d", i); 
    tableau2[i].flottant = i; 
  }
 

Le tableau statique ne peut pas être redimensionné et impose donc que la liste de données ait un nombre d’éléments connu à l’avance.

Tableaux dynamiques

Un tableau dynamique s’utilise presque de la même manière qu’un tableau statique. La différence avec celui-ci est que l’espace qu’il occupe doit être alloué par une fonction de type malloc(). L’exemple précédent se code ainsi avec un tableau dynamique :

int *tableau1; 
struct tableau_t 
{ 
  int entier; 
  char *chaine; 
  float flottant; 
} *tableau2; 
int i; 
int n; 
 
n = 10; 
if (NULL == (tableau1 = malloc (n * sizeof *tableau1))) 
  { 
    fprintf (stderr, "Problème avec malloc()\n"); 
    exit (EXIT_FAILURE); 
  } 
for (i = 0; i < n; i++) 
  tableau1[i] = i; 
 
n = 20; 
if (NULL == (tableau2 = malloc (n * sizeof *tableau2))) 
  { 
    fprintf (stderr, "Problème avec malloc()\n"); 
    exit (EXIT_FAILURE); 
  } 
for (i = 0; i < n; i++) 
  { 
    tableau2[i].entier = i; 
    tableau2[i].chaine = malloc (10 * sizeof *tableau2->chaine); 
    snprintf (tableau2[i].chaine, 10, "%d", i); 
    tableau2[i].flottant = i; 
  }
 

Avec glib, utilisez...

Choisir une structure pour des données sous forme clé-valeur

Problème

Vous avez une série de données sous forme clé-valeur et vous souhaitez connaître les structures de données les plus appropriées pour effectuer le bon choix.

Solution

Vous pouvez choisir entre les structures suivantes :

Discussion

Liste de structures

L’utilisation de deux tableaux dont les index correspondent ne fait pas partie des solutions. Préférez plutôt un tableau de structures qui facilite l’écriture du code et revient à peu près au même au niveau du programme.

Une liste de structures consiste à implémenter une liste (voir la recette précédente) dont l’élément est composé d’une chaîne de caractères et du reste des données, par exemple :

typedef struct 
{ 
  char *key; 
  int key_int; 
  float value_float; 
  /* ... */ 
} data_t;
 

En utilisant un tableau dynamique, vous pouvez chercher une valeur ainsi :

data_t *tableau; 
int nb_elements; 
int i; 
 
/* Initialisation et remplissage du tableau. */ 
for (i = 0; i < nb_elements; i++) 
  { 
    if (!strcmp (tableau[i].key, "clé") &&...

Choisir une structure pour des données sous forme de graphe

Problème

Vous avez des données sous forme de graphe et vous souhaitez connaître les structures de données les plus appropriées pour les stocker.

Solution

Un graphe peut être codé sous forme de structure contenant une liste chaînée des nœuds pères et une autre des nœuds fils :

typedef struct list_t 
{ 
  void *node; 
  struct list_t *next; 
  struct list_t *prev; 
} list_t; 
 
typedef struct node_t 
{ 
  void *data; 
  list_t *parent; 
  list_t *child; 
}
 

Les arbres sont un cas particulier de graphes où le nombre de parents est 0 pour le nœud dit racine, et 1 pour tous les autres. Plusieurs bibliothèques proposent une implémentation de structure d’arbre et de fonctions utiles pour travailler avec, en particulier glib et libxml2.

Discussion

Les graphes forment un outil très utile pour résoudre des problèmes mathématiques parfois complexes. Chaque problème donne lieu à la création d’outils particuliers. Nous indiquerons seulement ici que pour parcourir un graphe quelconque, nous choisissons un nœud et nous parcourons récursivement ses fils en marquant ceux que nous avons déjà vus. Pour parcourir un graphe orienté quelconque, inventez un nœud...

Coder un tableau dont l’index est une chaîne de caractères

Problème

Vous voulez coder vous-même une structure de données, ainsi que les fonctions pour y accéder, afin de simuler un tableau dont l’index est une chaîne de caractères.

Solution

Utilisez une table de hachage comme GHashTable de glib.

Discussion

Une table de hachage s’initialise avec g_hash_table_new(), de cette manière, lorsque la clé est une chaîne de caractères :

GHashTable *table = g_hash_table_new (g_str_hash, g_str_equal); 
GHashTable *table = g_hash_table_new_full (g_str_hash,  
                                      g_str_equal, NULL, free);
 

La fonction g_hash_table_new_full() permet de fournir deux arguments supplémentaires qui sont des fonctions pour libérer la mémoire lorsqu’un élément est supprimé. Si les clés sont des chaînes de caractères statiques, nous ne libérons pas la mémoire et indiquons NULL pour le destructeur de clés. Si la valeur est simplement une zone de mémoire allouée avec malloc(), free() en argument pour le destructeur de valeur suffit. Sinon, programmez son propre destructeur.

Pour ajouter un élément, recourez à g_hash_table_insert() ou à g_hash_table_replace(). La différence entre ces deux fonctions est qu’avec la première, lorsque la clé existe déjà...

Choisir une structure pour un tableau dont l’index est un entier

Problème

Vous voulez coder vous-même une structure de données et les fonctions pour y accéder afin de simuler un tableau dont l’index est un entier. Notez que les entiers ne sont pas forcément consécutifs.

Solution

Si les entiers sont consécutifs et que le premier est zéro ou proche de zéro, tirez profit de cette particularité et utilisez un tableau. Vous pouvez lire à ce sujet la première recette de ce chapitre.

Si les entiers ne sont pas consécutifs, préférez une table de hachage ou un arbre binaire balancé.

Discussion

Lorsque les entiers sont consécutifs et que le premier est zéro, le tableau a cette particularité que la clé et l’index de chaque élément correspondent. Utiliser un tableau comme décrit dans la recette "Choisir une structure pour une liste de données" de ce chapitre. Si le premier entier n’est pas zéro mais proche de zéro, vous pouvez malgré tout utiliser un tableau, donc les premiers éléments ne seront pas gérés.

Dans les autres cas, les tables de hachage et les arbres binaires balancés proposés par glib sont une bonne solution. Il est possible de convertir un entier en pointeur et inversement grâce aux deux macros suivantes...

Optimiser la recherche d’une aiguille dans une botte de foin

Problème

Vous devez rechercher une donnée dans un jeu de données et souhaitez l’optimiser afin d’obtenir le résultat au plus vite.

Solution

Lorsque les données ne se trouvent pas dans une structure de données de glib, vous pouvez soit parcourir la structure de données jusqu’à trouver l’aiguille, ou pré-trier la structure de données. Lorsque les données sont triées, effectuez une recherche dichotomique.

Avec une structure de données de glib, utilisez la fonction adéquate :

Fonctions de recherche d’aiguilles dans une botte de foin des structures de données de glib

Discussion

Certaines structures de données sont optimisées pour la recherche d’aiguilles dans une botte de foin. C’est le cas des tables de hachage et des arbres binaires balancés. Lorsque la recherche d’une donnée est souvent réalisée, placez-la dans une telle structure, en choisissant pour clé les données utilisées dans le critère de recherche.

Lorsque la recherche n’est pas primordiale, un simple parcours de la structure...

Trier une liste selon un critère donné

Problème

Vous voulez implémenter un algorithme permettant de trier une liste de données codées d’une manière particulière, avec un critère de tri particulier.

Solution

Renseignez-vous pour savoir si une fonction de tri n’est pas associée à la structure de données. Un tableau dynamique et un tableau de pointeurs peuvent être triés à l’aide de la fonction qsort(). Les structures suivantes de glib peuvent aussi être triées.

Fonctions de tri des structures de données de glib

Discussion

Les arguments des fonctions de tri consistent en général en la structure de données à trier (sur un argument ou plus) et en un pointeur sur une fonction de comparaison. La fonction de comparaison prend deux arguments qui sont du même type que celui d’un élément de la liste de données à trier. La valeur de retour est 0 s’il y a égalité entre ces deux arguments, négative si le premier est inférieur au second, et positive si le premier est supérieur au second. Pour les chaînes de caractères, la fonction strcmp() convient....

Supprimer les doublons dans une structure de données

Problème

Vous souhaitez supprimer les éléments en double d’une liste de données afin de garantir l’unicité de chaque élément.

Solution

Deux méthodes permettent d’atteindre ce résultat. Vous pouvez choisir de ne pas insérer ou de remplacer un élément lorsqu’il existe déjà dans la liste de données. L’unicité de chaque élément est alors garantie par construction de la liste. Vous pouvez aussi choisir de rechercher les éléments en double et les supprimer. Préférez néanmoins pré-trier les éléments de la liste, puis parcourir la liste à la recherche d’éléments consécutifs en double pour les supprimer.

Discussion

L’insertion d’un élément peut être précédée par une recherche de la présence de cet élément dans la liste. Lisez la recette "Optimiser la recherche d’une aiguille dans une botte de foin" à ce propos. Si l’élément existe déjà dans la liste, choisissez soit de le remplacer, soit de ne pas effectuer l’insertion. La liste ne contient ainsi pas d’élément en double.

Lorsque vous disposez déjà de la structure...