7. Structures récursives linéaires : les chaînes

Définition : une chaîne est une suite finie de n éléments du même type. Elle sera notée : C = (e1 e2 . . . en)

N.B. si n=0, C=( ) est la chaîne vide

Une chaîne est une structure dont chaque élément possède un et un seul pointeur vers un autre élément du même type. Les chaînes sont parfois appelées listes linéaires.

Exemple

  type Element = record
                   Info: InfoType;
                   Suivant: ^Element;
                   end; { Element }

  var Debut: ^Element;

  {initialisation:}Debut:=NIL;{chaîne vide}

Les principales opérations sur les chaînes sont :

- construction:: insertion au début, à la fin, avant ou après un élément donné.
- modification:: suppression d'un élément donné, du premier ou du dernier élément.
- utilisation:: recherche d'un élément, parcours de la chaîne, détermination de la longueur.

Nous n'aborderons pas de manière détaillée le changement de valeur d'un élément donné, car cela revient quasiment à effectuer une recherche de l'élément à changer.

On peut décrire les chaînes en terme de type abstrait de la manière suivante:

le rôle d'une chaîne est de stocker un nombre indéterminé d'éléments de même type dans un certain ordre. Cet ordre pourra dépendre de la chronologie d'insertion des éléments, de la valeur des éléments insérés ou d'un quelconque autre critère fixé par l'utilisateur.
la déclaration d'une chaîne doit spécifier le type de base des éléments qu'elle pourra contenir.
primitives de manipulation :
1. initialiser une chaîne à vide.
2. insérer un élément en début de chaîne.
3. insérer un élément en fin de chaîne.
4. insérer un élément avant un élément de la chaîne auquel on a accès.
5. insérer un élément après un élément de la chaîne auquel on a accès.
6. détruire l'élément en début de chaîne.
7. détruire l'élément en fin de chaîne.
8. détruire un élément de la chaîne auquel on a accès.
9. permettre l'accès au premier élément de la chaîne.
10. fournir la valeur de type de base contenue dans un élément auquel on a accès.
11. indiquer si l'élément auquel on a accès possède un successeur.
12. permettre l'accès à l'élément suivant un élément auquel on a déjà accès
13. indiquer si la chaîne est vide.

On pourrait encore énumérer d'autres primitives de manipulation de chaîne basées sur la position des éléments dans la chaîne. Par exemple, insérer un élément en N-ème position de la chaîne (si cette position existe), détruire le N-ème élément de la chaîne (si cette position existe), trouver la position du premier élément contenant une valeur donnée (si un tel élément existe), fournir la longueur de la chaîne . . .

7.1. Construction

Table des matières.

Site Hosting: Bronco