Recherche d'un élément dans une table

      

Les problèmes de recherche sont modélisés à l'aide de structures contenant deux champs : key et info. Le champ key est souvent une chaîne de caractères (un nom) qui permet de désigner de façon unique un objet. Les autres champs contiennent toutes sortes d'informations relatives à cet objet. On représentera ces objets à l'aide du type struct :  

#define L 16
typedef struct {
  char key[L];
  int info1;
  double info2;
  ...
} data;

Ces enregistrements doivent à leur tour être placés dans une structure de données appropriée, que l'on appellera une table ou dictionnaire . Les deux opérations principales sont l'insertion d'un objet et la recherche d'un objet désigné par sa clé. Une autre opération qui peut être demandée est la suppression d'un objet désigné par sa clé. Ces trois opérations ne sont pas réalisées avec la même fréquence. Dans le cas d'un annuaire, les interrogations (ou recherches) sont beaucoup plus fréquentes que les insertions ou les suppressions. On peut donc chercher à optimiser les recherches plutôt que les deux autres opérations.