Algorithme -3-

Structure de données

L’identificateur qui permet de nommer une information par le moyen d’une variable contenat une valeur, sert de rangement temporaire ou définitif à cette valeur. Dans un schéma, la valeur rangée dans une variable est essentiellement dynamique et varie au cours de l’exécution de l’algorithme.

On rappelle que lors d’une affectation:

  • L’ancienne valeur de la variable est perdue après l’opération d’affectation
  • La valeur contenue dans une variable peut être Simple ou Structurée
  • La valeur peut être le résultat d’une expression arithmétique ou logique
  • La variable peut apparaître dans une expression

Les valeurs simples sont des données de type booléen, caractère ou numérique. Les valeurs structurées comme un ensemble de données sont parmi les plus courantes:

  • Les files séquentielles
  • Les vecteurs
  • Les listes linéaires
  • Les piles
  • Les tables
  • Les arbres
Notion d’accès à une information

Pour un ensemble de données structurées organisées, les ensembles de valeurs sont finis et rangés suivant un ordre donné. La notion d’accès à une valeur rangée sur cet ensemble devient fondamentale, on distingue principalement deux types d’accès

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

A ces ensembles finis de valeurs sont naturellement associés des algorithmes différents suivant la nature de l’accès. 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 par dichotomie alors qu’il nous faut dérouler le rouleau de parchemin pour trouver une information se trouvant au bas de celui-ci.
Il faut donc organiser les ensembles de valeurs sur leur support en fonction des accès possibles pour rendre, réalisables, les opérations d’accès couramment pratiquées en informatique sur ces ensembles.

On étudiera dans de futurs articles comment organiser un ensemble d’informations sur leur support en fonction des accès afin de permettre les opérations usuelles en informatique sur ces ensembles comme:

  • 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)
File séquentielle

la première structure d’information que nous étudierons est la structure de file séquentielle . Elle permet d’introduire la notion de d’accès séquentiel à une information. On définira par la suite une file séquentielle de manière abstraite comme un collection de données afin de faciliter la conception d’algorithmes. Par conséquent on ne parle pas de la représentation concrète de cette structure puisqu’elle dépend des langages de programmation utilisés.

L’algorithme de parcours d’une file séquentielle, étudié précédemment met en œuvre les primitives d’accès:

  • Premier: Initialise la lecture au début de la file
  • Prendre: Lit l’élément courant
  • Dernier: Signale la fin de la lecture
  • Avancer: Déplace le curseur d’une position
Schéma Algorithme Enumération
    Description 
        Objectif: Présenter un algorithme générique de parcours séquentiel
        Résultat: Enumération de tous les éléments de la file            
        Remarque: La File n'est pas modifiée
    Action 
        Premier(File)  
        TantQue Non Dernier(File)
        Faire
            Prendre(File,Val)
            "suite d'instruction de traitement de la valeur Val"
            PrAvancer(File)
        Fin-Faire
    Fin-Action
Fin-Schéma
Vecteur

Un vecteur est un ensemble fini dont les valeurs sont des données simples ou complexes rangées suivant une relation d’ordre. Chaque élément est accessible par un indice ou index. Un vecteur est défini par un ensemble fini de N ‘éléments de valeur V et d’un ensemble d’entiers I appelé ensemble des index.

Pour un vecteur T de longueur N que l’on notera T(1:N), l’opération d’indexation notée T(i) délivre la valeur de l’élément d’indice i, à condition que l’ensemble des valeurs de i soit inclus dans [1,N]

On peut rechercher un élément d’un vecteur directement sans avoir à examiner tous les élément à partir du premier. A la manière d’un dictionnaire on peut accéder directement à n’importe quel mot d’une page grâce à l’accès direct ce qui n’est pas possible de réaliser avec un structure de file séquentielle.

Si l’on veut énumérer les éléments d’un vecteur on le considère comme une file séquentielle dont l’ensemble des places est i. Le vecteur est parcouru dans l’ordre croissant et l’on fait abstraction de la possibilité de l’accès direct. Pour cela on peut réutiliser le schéma d’algorithme précédent à condition de redéfinir les primitives d’accès suivantes:

  • Premier: Initialise le Vecteur de dimension N en donnant à l’index i la valeur 1
  • Prendre: Lit l’élément courant Vecteur(i)
  • Dernier: Signale la fin de la lecture quand la valeur de l’index i est supérieure à N
  • Avancer: Ajoute 1 à l’index courant

D’un point de vue purement algorithmique il n’y a pas de différence enter un parcours séquentiel pour un vecteur et une file séquentielle. Le niveau d’abstraction de la représentation algorithmique nous permet de modéliser un parcours séquentiel de la même façon car les changements de comportement sont implémentés dans les primitives d’accès.

Pour mieux appréhender ce qui se passe lors d’un parcours séquentiel d’un vecteur, écrivons un schéma de programme qui va nous permettre d’expliciter la sémantique des primitives d’accès.

Schéma Programme Enumération
    Interface  
        Objectif: Présenter un algorithme de parcours séquentiel d'un vecteur
        Résultat: Énumération de tous les éléments du vecteur             
        Remarque: La Vecteur n'est pas modifiée
    Fin-Interface 

    Principal Enumération 
        Déclaration
            Variable i : Nombre     -- Le nombre à choisir
            Variable Val : Element  -- Un élement du vecteur de type Element
            Variable V : Vecteur    -- Un vecteur V de type Vecteur
            Variable n : Nombre     -- la Taille n du vecteur de type Nombre
        Instruction
            i = 0
            TantQue (i < n) -- non Dernier (V)
            Faire 
                i = i + 1   -- Avancer (V, val) 
                val = V(i)  -- Prendre la valeur 
                Afficher(val)
            Fin-Faire    
        Fin-Instruction
    Fin-Principal 
Fin_Schéma
Liste linéaire
Une liste linéaire est définie comme un ensemble d’éléments. Chaque élément contient deux informations la valeur de la donnée et l’adresse de l’élément suivant . On définit ainsi un couple composé d’une information et d’une adresse, que l’on désigne généralement par le nom de cellule. L’information comme pour les vecteurs et les files séquentielles pourra être simple ou structurée. L’élément de début contient l’adresse de de la première cellule, l’élément de fin contient par définition l’adresse NIL.
Pour réaliser une énumération de tous les éléments de la liste nous pouvons réutiliser comme précédemment le schéma d’algorithme de parcours séquentiel. Tout comme pour la structure de Vecteur il faut redéfinir les primitives d’accès de la façon suivante.
  • Premier(File) est défini comme: Premier(Liste,Adresse) qui initialise l’adresse de la première cellule
  • Dernier(File) est défini comme: Adresse = NIL
  • Prendre(File,Val) se décompose en deux primitives Adresse=Suivant (Adresse) et Val=Valeur(Adresse)
Schéma Programme Enumération
    Interface 
        Objectif: Présenter un algorithme de parcours séquentiel d'une liste
                  d'élement de type generique "Element"
        Résultat: Énumération de tous les éléments de la liste           
        Remarque: La liste  n'est pas modifiée
    Fin-Interface 

    Principal Enumération 
        Déclaration
            Variable element : Adresse ) -- La variable element est de type Adresse
            Variable val : Element       -- La variable val est de type Element
            Variable (liste,Liste)     -- La variable liste est de type Liste
        Instruction
            Premier (liste,element)  -- Assigne l'adresse du premier élément
                                     -- de la Liste à la variable element
            TantQue (element # nil)  -- Adresse non nulle
            Faire 
                Val = Valeur(element)
                Afficher (Val)
                element = Suivant(element)
            Fin-Faire    
        Fin-Instruction
    Fin-Principal 
Fin_Schéma
Table

Une table est un ensemble fini de N éléments tels que chaque élément est un couple Indicatif-Attribut. On associe donc le nom I de l’indicatif à une valeur d’un élément. On accède à la valeur d’un élément à l’aide du nom de l’indicatif. Un exemple de table: la table des prix des articles dans un stock, le nom du produit ( indicatif) permet de retrouver son prix (attribut)

Les opérations d’accès que l’on peut réaliser sur un élément au moyen de l’indicatif sont:

  • Consultation: Accès à l’information d’un élément au moyen de l’indicatif
  • Modification: Mise à jour de l’information d’un élément
  • Création et la suppression d’une entrée comprenant la clé et l’information

Les opérations sur la structure d’une table, à savoir l’accès direct ou séquentiel à un élément d’une table dépend de l’organisation choisie:

  • Les éléments de la table sont contiguë ( File, Vecteur ou Liste) l’accès est séquentiel
  • Les éléments de la table sont contiguë ( Vecteur) l’accès est direct
  • Les éléments de la table sont chainés (Liste) ’accès est séquentiel

Pour réaliser une énumération de tous les éléments d’une table nous pouvons réutiliser comme précédemment le schéma d’algorithme de parcours séquentiel.

Pile

Pour donner un image du fonctionnement d’une cette structure prenons l’exemple d’une pile de livres. On peut ajouter ou enlever des livres au sommet de la pile. On ne doit pas, au risque de détruire la pile, retirer un livre en son milieu. Plus précisément les deux seules opérations que l’on défini pour une structure de pile sont

  • Empiler un élément qui consiste à ranger une élément au sommet de la pile
  • Dépiler un élément qui consiste à Prendre et enlever un élément du sommet de la pile

Une pile peut être représentée comme une suite d’élément contiguë à la manière d’un vecteur ou sous forme chainée à la manière d’une liste.

On définit les deux primitives suivantes:

  • Empiler (Element) qui ajoute un nouvel élément au sommet de la pile.
  • Dépiler (Element) qui supprime un élément au sommet et range sa valeur dans Element
Arbre

L’arbre est une structure de donnée qui est une généralisation de la liste, alors qu’une cellule de liste a un seul suivant, un arbre peut en avoir plusieurs. On ne parle plus de cellule mais de Nœud. Un nœud dit père peut avoir plusieurs nœud dits fils. Un fils n’a qu’un seul père, et tous les nœuds ont un ancêtre commun appelé la racine de l’arbre (le seul nœud qui n’a pas de père).

Lorsqu’un arbre admet, pour chaque nœud, au plus N fils il est dit n-aire. Si N est égal à deux l’arbre est dit binaire. Nous étudions par la suite essentiellement les arbres binaires dont les deux descendants sont appelés fils droit et fils gauche.

Les primitives d’accès à la valeur d’un nœud dépendent de l’organisation choisie. Les primitives Premier(),Dernier(),Prendre() Ranger() sont redéfinies comme vue précédemment en fonction de la représentation d’un arbre à l’aide d’un structure de donnée de type Vecteur ou Liste.

Il y a plusieurs manière d’énumérer tous les nœuds un arbre. Nous nous limiterons dans nos articles aux trois parcours classiques: préfixé, infixé et postfixé.

Pour un parcours préfixé, on effectue dans l’ordre

  1. Le traitement de la racine
  2. Le parcours du sous arbre gauche
  3. Le parcours du sous arbre droit

Pour un parcours infixé, on effectue dans l’ordre

  1. Le parcours du sous arbre gauche
  2. Le traitement de la racine
  3. Le parcours du sous arbre droit

Pour un parcours postfixé, on effectue dans l’ordre

  1. Le parcours du sous arbre gauche
  2. Le parcours du sous arbre droit
  3. Le traitement de la racine