13.1. Notion de clé

Lorsqu'on manipule une série d'objets du même type, il faut pouvoir distinguer ces objets les uns des autres. La distinction entre ces objets se fait souvent grâce à une partie ou à la totalité de leur contenu.

Par exemple, si l'on travaille sur une série d'enregistrements d'étudiants, le numéro d'étudiant nous permettra de retrouver les informations associées à un étudiant donné. Le nom et le prénom pourrait aussi servir à retrouver l'enregistrement d'un étudiant donné, mais il y a toujours le risque d'avoir deux étudiants ayant le même nom et le même prénom.

Définition : une clé est une partie d'un objet (enregistrement) qui permet de désigner le contenu de cet objet de manière non-ambiguë.

D'une manière générale un tableau pourra être formé de composantes de la forme

(K, I)

avec :

k = valeur de la clé
I = information associée.

En Pascal :

  type Composante = record
                      K : TypeClef;
                      I : TypeInfo;
                      end; { Composante }

       Tableau=array[0..max] of composante;

La recherche d'une information dans le tableau peut se faire sur la base de sa clé étant donné qu'il n'a alors pas d'ambiguïté.

N.B. Il arrive que l'on fasse référence au terme de clé pour désigner la partie d'un élément sur laquelle on se base pour effectuer une recherche dans une suite d'éléments même si cette partie de l'élément n'est pas suffisante pour désigner un élément précis sans ambiguïté. On parlera alors de la recherche de la première occurrence, ou de la dernière, ou même de toutes les occurrences.

Description en terme de type abstrait :

• le rôle d'une structure adressable par son contenu est de stocker un ensemble d'informations de manière à pouvoir les retrouver le plus rapidement possible à partir d'une partie du contenu de ces informations appelée "clé". Ces clés doivent toutes être différentes les unes des autres.

• la déclaration d'une telle structure doit spécifier le type de la clé ainsi que celui de l'information associée à cette clé.

• primitives de manipulation :
  1. initialiser la structure à vide,
  2. ajouter un élément (insertion d'un couple (K,I)),
  3. prédicat indiquant la présence d'un élément avec une clé donnée,
  4. accès à l'information associée à une clé donnée pour utilisation ou modification,
  5. parcours séquentiel des éléments de la structure dans un ordre quelconque.

N.B. certaines implantations pourront imposer une taille limite à la structure pour raison d'efficacité.

13.2 Recherche séquentielle

Table des matières.

Site Hosting: Bronco