1- Liste linéaire (spécifications abstraite et concrète)

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 T0.
  • 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 T0 , à 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(Ldef_ssi long(L Longmax
inserer(L,k,edef_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) )

آخر تعديل: Tuesday, 9 February 2021, 12:06 PM