Le problème d’accès à un élément d’un file, classique en gestion, est formulé habituellement de deux manières:
- Soit on connait la position de l’élément à trouver, on recherche , depuis le début de la file jusqu’au ixième élément.
- Soit on ne connait pas la position de l’ élément et l’on recherche le premier élément dont la valeur est la valeur donnée.
On distingue donc deux types de recherche dans une file séquentielle:
- Un accès par position:
- Un accès par valeur ou associatif
Accès Associatif
On veut parcourir une file séquentielle depuis le début pour trouver le lus petit index d’une élément dont on cherche une valeur égale à une valeur donnée. Le schéma de programme est un Prédicat délivrant Vrai si la valeur choisie appartient à l’ensemble des valeurs de la file, Faux sinon.
Schéma Programme Accès_Associatif Interface Objectif: Recherche par valeur lors d'un parcours séquentiel d'une file de Nombre Variable valeur : Nombre -- La variable valeur est de type Nombre Variable file : File -- La variable file est de type File Résultat: Lecture de tous les éléments de la file Remarque: La file n'est pas modifiée, le predicat retourne Vrai si la valeur est trouvée, Faux sinon Fin-Interface Prédicat Accès_Associatif (file: File, valeur : Nombre) Déclaration Variable val: Nombre -- la variable val est de type Nombre Instruction Premier (file) -- Initialise l'adresse du premier élément TantQue Non (Dernier(file)) ET (NON Egal(val,valeur)) Faire Prendre(file,val) Avancer(file) Fin-Faire Accès_Associatif = Egal(val,valeur) Fin-Instruction Fin-Prédicat Fin_Schéma
Vérifions la cohérence de ce schéma. Il s’avère que dans lorsque la condition Dernier(file) est vraie à l’entrée du schéma( lorsque le file est vide) la condition TantQue est incohérente puisque le prédicat Egal reçoit en paramètre une valeur non définie pour val.
Pour corriger ce problème nous allons introduire une nouvelle variable de type booléen, appelons la Ok pour indiquer que l’on a trouvé une valeur correspondant à la condition de recherche. Le test de la variable Ok va donc remplacer le condition Egal(val, valeur), elle assure la cohérence du schéma en plaçant l’affectation Ok = Faux avant le test d’itération. Une autre amélioration consiste à n’exécuter l’instruction Prendre(file, val) que si la variable Ok a la valeur Faux.
Schéma Programme Accès_Associatif
Interface
Objectif: Recherche par valeur lors d'un parcours séquentiel
d'une file de Nombres
Variable valeur : Nombre -- La variable valeur est de type Nombre
Variable laFile : File -- La variable laFile est de type File
Résultat: Lecture de tous les éléments de la file
Remarque: La file n'est pas modifiée, le prédicat retourne Vrai
si la valeur est trouvée, Faux sinon
Fin-Interface
Prédicat Accès_Associatif (file: File, valeur : Nombre)
Déclaration
Variable val: Nombre -- la variable val est de type Nombre
Variable ok: Booléen
Instruction
ok = Faux
Premier(file)
TantQue NON (Dernier(file)) ET (NON ok)
Faire
Prendre(file,val)
ok = Egal(val, valeur) -- ok reçoit une valeur booléenne
Avancer(file)
Fin-Faire
Accès_Associatif = ok
Fin-Instruction
Fin-Prédicat
Fin_Schéma
Accès Associatif dans un file ordonnée
Si l’on considère une file dont les éléments sont munis d’une relation d’ordre, le schéma ci-dessus put être optimisé. Les deux principales relation d’ordre couramment utilisées sont représentées par:
- une fonction croissante, la file est ordonnée en ordre croissant
- une fonction décroissante, la file est ordonnée en ordre décroissant
L’accès par position dans une file ordonnée n’est pas concerné par la relation d’ordre puisque le schéma d’accès par position n’utilise pas de relation d’ordre. Dans le cas de l’accès associatif la relation d’ordre permet d’éviter un énumération complète des éléments de la file pour trouver une occurrence de la valeur cherchée.
Schéma Programme Accès_Associatif Interface Objectif: Recherche par valeur lors d'un parcours séquentiel d'une file ordonnée croissante de Nombres Variable valeur : Nombre -- La variable valeur est de type Nombre Variable file : File -- La variable file est de type File Résultat: Lecture de tous les éléments de la file Remarque: La file n'est pas modifiée, le prédicat retourne Vrai si la valeur est trouvée, Faux sinon Fin-Interface Prédicat Accès_Associatif (file: File, valeur : Nombre) Déclaration Variable val: Nombre -- la variable val est de type Nombre Variable ok: Booléen Variable énumération: Booléen Instruction ok = Faux énumération = Vrai Premier(file,val) TantQue Non (Dernier(file)) ET (NON ok) ET énumération Faire Prendre(file,val) ok = Egal(val,valeur) Si Inferieur(valeur,val) -- valeur est plus petit que val Alors énumération = Faux Fin-Si Avancer(file) Fin-Faire Accès_Associatif = ok Fin-Instruction Fin-Prédicat Fin_Schéma