Algorithme -9-

Schéma d’algorithme insertion à une position

On veut construire, à partir d’une file de n élément, une nouvelle file de longueur n+1 comprenant un nouvel élément inséré à une position k. L’algorithme est formé de trois actions:

• Copie des k-1 premiers élément de la file dans la nouvelle file
• Insertion du nouvel élément à la position k dans la nouvelle file
• Copie des derniers élément de la file dans la nouvelle file

Le schéma de programme est un prédicat délivrant VRAI si l’insertion est possible, FAUX sinon.

Schéma programme InsertPosition  (file: File
                                 ,position: Entier
                                 ,element: Entier
                                 ,file1: File)
    Interface
        Objectif:       Insérer un élément à la position 
        Variable file1 : File       -- La nouvelle File
        Variable file : File        -- La file piloteVariable position : Nombre  -- La position d'insertionVariable element : Nombre   -- L'élément à insérer
        Résultat:       La valeur du Prédicat InsertPosition VRAI ou FAUX 
        Remarque:       file n'est pas modifiée. 
                        file1 est créée si l'insertion est possible
    Fin-Interface
    Prédicat
        Variable  valeur, index : Nombre 
        InsertPosition : Booléen  = Faux
        index = 1 
        
        Premier (file)
        Premier (file1)
        TantQue NON Dernier(File) ET (index < position)
        Faire
            Prendre(file, valeur)
            Ranger (file1,valeur)
            index = index +  1 
            Avancer(file)
        Fin-Faire
        
        Si Egal(Index,Position) 
        Alors 
           Ranger (file1,element)   -- Insertion du nouvel élémentTantQue NON Dernier(file)
           Faire
               Prendre(file,valeur)
               Ranger (file1,valeur)
               Avancer (file)
           Fin-Faire 
           InsertPosition = Vrai
        Fin-Si
     Fin-Prédicat 
Fin-Schéma

Schéma d’algorithme insertion après un élément donné

Dans cet algorithme on retrouve un élément par accès associatif, après lequel on veut effectue l’insertion d’un nouveau élément.

Schéma algorithme Insertion (file: File, valeur: Nombre
                            ,element: Nombre, file1: File)
    Interface
        Objectif:         -- Insérer un élément à la position après
                          -- l'élément dont la valeur est valeur
        variable file1    -- La nouvelle file
        variable file     -- La file pilote
        variable valeur   -- Insertion d'un élément après cette Valeur
        variable element  -- L'élément à insérer
        Résultat:         -- La valeur du Prédicat Insertion VRAI ou FAUX 
        Remarque:         -- file n'est pas modifiée. 
                          -- file1 est créée si l'insertion est possible
    Fin-Interface
    Prédicat
        variable Trouvé: booléen = Faux
        variable val, valeur, element : Nombre
        Premier (file)
        Premier (file1)
        TantQue Non Dernier(file) ET NON Trouvé
        Faire
            Prendre(file,val)
            Trouvé = Egal(val,valeur)
            Ranger (File1,Val)
            Avancer (File,Val)
        Fin-Faire
        Si Trouvé 
        Alors 
           Ranger (file1,element) 
           TantQue NON Dernier(file)
           Faire
               Prendre (file,val)
               Ranger (file1,val)
               Avancer (file,val)
           Fin-Faire
        Fin-Si 
        Insertion = Trouvé
     Fin-Action 
Fin-Schéma

Remarques

1. Pour simplifier les schémas de programme, on choisi de n’insérer qu’un seul élément à la fois
2. On retrouve ici le problème d’accès à un élément d’une file dont les deux cas évoqués précédemment sont sa position ou sa valeur dans la file
3. Les schémas présentés nécessitent la création d’une nouvelle file