Stucture de données

En programmation , un Type Abstrait définit un type de données et les opérations sur les données de ce type, indépendamment de toute implémentation.

C’est la spécification formelle:

  • d’un type de données que le programme devra manipuler
  • des opérations que l’on devra pouvoir effectuer sur les données de ce type.

Le langage algorithmique Schema est basé sur le type Abstrait Ensemble. Les opérations associées à ce type sont appelées Primitives.

C’est la spécification formelle:

  • du type des éléments qu’un algorithme devra manipuler
  • de l’abstraction des structures de données classiques
  • des primitives ou opérations définies sur un ensemble

la première structure d’information que nous étudierons est la structure d’ensemble séquentiel .
Un ensemble séquentiel est une suite finie d’éléments ayant les caractéristiques suivantes:

  • Un ensemble de positions organisé de telle façon que l’on peut distinguer le premier élément, un élément quelconque et le dernier
  • Un ensemble d’éléments rangés dans une position nommée index
  • Un parcours séquentiel permet de trouver chaque élément.
  • Un parcours séquentiel débute par la détection de la première position

Notion d’accès à une information

Un ensemble est une collection d’éléments rangés suivant un ordre donné. On distingue principalement deux types d’accès à un élément:

  • Accès séquentiel
  • Accès direct.

Prenons l’exemple de la recherche d’information dans un parchemin ou dans un dictionnaire. L’accès à une information dans un dictionnaire est directe ou presque puisque principalement réalisée par une recherche dichotomique alors qu’il nous faut dérouler le rouleau de parchemin pour trouver une information se trouvant au bas de celui-ci dans le cas d’une recherche séquentielle. Il faut donc organiser un ensemble en fonction des accès possibles pour rendre, réalisables, les primitives couramment pratiquées sur ces ensembles, parmi lesquelles:

  • Accès à une élément
  • Recherche d’un élément
  • Insertion d’un élément
  • Suppression d’un élément
  • Copie d’une partie d’un ensemble
  • Éclatement de l’ensemble en plusieurs sous-ensemble
  • Fusion de plusieurs ensemble en un seul
  • Tri (ordonner les élément de l’ensemble suivant une relation d’ordre)

Accès aux éléments d’un ensemble

Pour donner un modèle de comportement dynamique d’un ensemble, on définit des primitives d’accès séquentiel:

  • Par analogie avec une bande magnétique défilant devant une tête de lecture: On n’a accès à une valeur que lorsque l’élément correspondant est en position de lecture.
  • L’élément en position d’être lu est dit élément courant
  • Seul l’accès à l’élément courant à un instant donné est possible

d’accès direct ou indexé

  • L’accès à un élément est réalisé grâce  à un index indiquant sa position dans l’ensemble.
  • Pour un ensemble  E de longueur N, l’opération d’indexation notée E(i) délivre la valeur de l’élément d’indice i, à condition que l’ensemble des valeurs de i soit inclus dans l’intervalle [1,N].
  • L’accès direct permet de rechercher un élément d’un ensemble directement sans avoir à examiner tous les éléments à partir du premier

Parcours d’un ensemble

il consiste à lire tous les élément d’un ensemble. Pour parcourir tous les éléments d’un ensemble on définit un objet particulier appelé itérateur. Un itérateur permet de parcourir tous les éléments contenus dans un autre objet, le plus souvent une structure de données  (file, liste, arbre, etc). On dit qu’un ensemble est itérable lorsqu’il est possible de parcourir ses éléments au moyen d’un itérateur  .

En Schema un itérateur de parcours séquentiel se compose de 4 primitives:

  • Initialiser: permet l’accès aux éléments
  • Enumerer: contrôle le parcours
  • Element_Suivant: permet l’accès à un élément dit courant
  • Element_Courant : délivre la valeur de  élément courant

Accès sequentiel

  • Initialiser  est une action rendant possible l’accès aux éléments de l’ensemble. Cette action positionne le curseur au début de l’ensemble. Si l’ensemble est vide la primitive Enumerer délivre la valeur « FAUX » pour indiquer que la fin de l’ensemble est atteinte. Cette primitive  positionne le curseur au début pour préparer l’accès à un élément de l’ensemble. Cette action doit être obligatoirement exécutée pour initier le parcours de l’ensemble.
  • Element_Courant est une primitive d’accès à un élément de l’ensemble, ce qui permet de prendre la valeur de la donnée pointée par Element_Suivant.
  • Element_Suivant est une primitive permettant de faire avancer vers la position suivante. Son fonctionnement est le suivant:
    • Positionner le curseur sur l’élément suivant de l’ensemble.
    • Si la fin de l’ensemble  est atteinte, la valeur  de la primitive Enumerer devient Faux.
    • Cette action est définie si et seulement si la primitive Enumerer ou la primitive Element_Courant à été exécutée.
  • Enumerer délivre la valeur FAUX si les primitives Element_Courant ou Initialiser ont essayé de lire la marque de fin de l’ensemble. Il délivre VRAI dans tous les autres cas.

Note sur la syntaxe des primitives

En langage Schema les primitives d’accès séquentiel aux éléments d’un ensemble s’écrivent de la façon suivante pour une collection de données nommée ensemble.

  • Initialiser ensemble
  • element >- Element_Courant ensemble
  • Element_Suivant -> ensemble
  • Enumerer ensemble

Accès indexé ou direct

  • PremierIndex(ensemble)  retourne l’index du premier élément d’un ensemble.
  • DernierIndex(ensemble) retourne l’index du dernier élément d’un ensemble.
  • Accéder à un élément retourne la valeur d’un element marqué par son index ou sa position dans l’ensemble.
AccesIndexé
   ensemble >- [11 12 16]
   index <- 1
   element <- ensemble[index]
   Afficher element #element
   element <- ensemble[2]
   Afficher element #element
Fin

Primitives de création d’un ensemble

Les mots réservés pour la création d’un ensemble File, Liste et []

  • File ou [] pour  la création d’un ensemble dont la structure est une file séquentielle indexée
  • Liste pour la création d’un ensemble dont la structure représente une liste chainée.
Ensemble d'éléments de type  Texte: ensemble  <- File("1"  "2"  "3")
ensemble d'éléments de type  Entier: ensemble  <- [1 2 3]
ensemble d'éléments de type  Reel:ensemble  <- Liste(1.0 2.6 3.5

Parcours dans un ensemble

Modèle de parcours séquentiel

Parcours_1 ensemble Ensemble 
   Initialiser -> ensemble
   Enumerer -> ensemble
      element >- Element_Courant ensemble 
      Afficher -> element = #element
      Element_Suivant -> ensemble
   Fin
Fin

Note: l'itération s'arrête lorsque la condition booléenne Enumerer est "Faux"

Modèle de parcours indexé

Parcours ensemble Ensemble
   index <- PremierIndex(ensemble)
   index <= DernierIndex(ensemble) 
      element <- ensemble[index]
      Afficher element #element
      index <- index + 1  
   Fin
Fin

Calcul du nombre d’éléments d’un ensemble

L’algorithme de calcul du cardinal d’un ensemble est composé:

  • d’un élément en entrée de type Ensemble: ensemble
  • du type de élément à retourne: Entier
  • de deux instructions d’affectation
  • d’une instruction répétitive
  • de primitives de parcours de ensemble
cardinal ensemble Ensemble -> Entier
   nombreElement <- 0
   Initialiser ensemble 
   Enumerer ensemble
      nombreElement <- nombreElement + 1
      Element_Suivant ensemble
   Fin
   <- nombreElement
Fin

copyright A rchitectures A pplicatives A vancées A3-Soft

A3soft