On considère les cinq procédures sur les Objets :
Lire_Objet | |
| reçoit : | M = le rang logique de lecture |
| renvoie : | X = l'élément lu |
Ecrire_Objet | |
| reçoit : | M = le rang logique d'écriture |
X = l'élément à écrire | |
Inserer_Objet | |
| reçoit : | M = le rang logique d'insertion |
X = l'élément à insérer | |
| renvoie : | men = C.R.(0 si tout va bien, 1 en cas d'erreur – pas de modification) |
Supprimer_Objet | |
| reçoit : | M = le rang logique de suppression |
| renvoie : | men = C.R. |
Rechercher_Objet | |
| reçoit : | X = l'élément recherché |
XC = partie utile de l'élément utilisée pour la recherche | |
| renvoie : | men = C.R.M = le rang logique de cet élément, quand celui-ci existe (men=0)M = le rang logique d'insertion de l'élément, si celui-ci n'a pas été trouvé (men=1) |
Toutes ces procédures connaissent :
RG = | le rang physique des éléments logiquement triés : |
RG( rang_logique ) = rang_physique | |
LM = | le nombre d'éléments existants |
= | le nombre d'éléments significatifs des tableaux |
On considère ensuite quatre structures de données différentes (qu'on appelle dans la suite les contextes d'utilisation) :
contexte [1] | ||||||||||
| éléments : | X1 | = chaîne de 50 caractères | ||||||||
X1C | = partie utile de X1 utilisée pour le tri | |||||||||
| = les 40 premiers caractères de X1 | |||||||||
| rang : | RG1 | = tableau | ||||||||
| table : | fichier1, ouvert sous le numéro logique 1 | |||||||||
| bornes : | 0 < M ≤ LM1 | |||||||||
contexte [2] | ||||||||||
| éléments : | X2 | = chaîne de 10 caractères | ||||||||
X2C | = partie utile de X2 utilisée pour le tri = X2 | |||||||||
| rang : | rang habituelle des entiers | |||||||||
| table : | TX2 = tableau d'éléments de type X2 indicé par M | |||||||||
| bornes : | 0 < M ≤ LM2 | |||||||||
contexte [3] | ||||||||||
| éléments : | X3 | = chaîne de 50 caractères | ||||||||
X3C | = partie utile de X3 utilisée pour le tri (40 car.) | |||||||||
X3NB | = conversion en entier du premier caractère de X3 | |||||||||
| rang : | RG3 | = tableau | ||||||||
| table : | fichier3, ouvert sous le numéro logique 3 | |||||||||
| bornes : | LM3 = tableau | |||||||||
| ||||||||||
contexte [4] | ||||||||||
| éléments : | X4 | = chaîne de 50 caractères | ||||||||
X4C1 | = partie utile de X4 utilisée pour le tri (4 car.) | |||||||||
X4C2 | = idem, si égalité sur X4C1 (40 car.) | |||||||||
X4C3 | = idem, si égalité sur X4C1 et X4C2 (6 car.) | |||||||||
| rang : | RG4 | = tableau | ||||||||
| table : | fichier4, ouvert sous le numéro logique 4 | |||||||||
| bornes : | 0 < M ≤ LM4 | |||||||||
Le contexte [1] représente le cas général :
- les éléments sont lus dans un fichier,
- une table des rangs permet une lecture par indirection,
- les bornes des rangs des éléments significatifs sont 0 et LM.
Pour le contexte [2], la lecture est réalisée non dans un fichier mais dans un tableau.
Pour le contexte [3], ce sont les bornes qui diffèrent, par l'introduction du tableau LM3 (ceci pour permettre un accès beaucoup plus rapide à l'information contenue dans le fichier).
Pour le contexte [4], c'est le critère de tri qui diffère (on introduit un ordre lexicographique sur trois composantes des éléments à comparer).
Remarque :
On utilise la notation X... pour le paramètre du type des éléments, et Y... pour nommer une variable locale ayant mêmes propriétés.
On trouvera en annexe le texte des quatre procédures de recherche, ainsi que leur forme « textuelle ».