Algorithmique et Structures de Données

Spécification abstraite

Répertorions les fonctionnalités d’une liste en soulignant les verbes d'actions et les noms, à partir d’une description semi-formalisée:

• C’est une structure de donnée séquentielle dans laquelle les données peuvent être traitées les unes à la suite des autres.

• Il est possible dans une telle structure d’ajouter ou de retirer des éléments en n’importe quel point de la liste.
• L’ordre des éléments est primordial. Cet ordre est construit, non sur la valeur des éléments de la liste, mais sur les places (rangs) de ces éléments dans la liste.
• Chaque place a un contenu de type T₀.
• Le nombre d’éléments d’une liste l est appelé longueur de la liste. Si la liste est vide nous dirons que sa longueur est nulle (longueur = 0 ).
• On doit pouvoir effectuer au minimum (non exhaustif) les actions suivantes sur les éléments d’une liste l : accéder à un élément de place fixée, supprimer un élément de place fixée, insérer un nouvel élément à une place fixée, etc ....

Signification des opérations : (spécification abstraite)

• acces(L,k) : opération générale d’accès à la position d’un élément de rang k de la liste L.
• supprimer(L,k) : suppression de l’élément de rang k de la liste L.
• inserer(L,k,e) : insérer l’élément e de T₀ , à la place de l’élément de rang k dans la liste L.
• kième(L,k) : fournit l’élément de rang k de la liste.

Spécification opérationnelle concrète

• La liste est représentée en mémoire par un tableau et un attribut de longueur.
• Le kème élément de la liste est le kème élément du tableau.
• Le tableau est plus grand que la liste (il y a donc dans cette interprétation une contrainte sur la longueur. Notons Longmax cette valeur maximale de longueur de liste).

Il faut donc, afin de conserver la cohérence, ajouter deux préconditions :

long(L) def_ssi long(L) ≤ Longmax
inserer(L,k,e) def_ssi (1 ≤ k ≤ long(L)+1) et (long(L) ≤ Longmax)

D’autre part la structure de tableau choisie permet un traitement itératif de l’opération kème ( une autre spécification récursive de cet opérateur est possible dans une autre spécification opérationnelle de type dynamique).

kème(L,k) = contenu(acces(L,k) )