Les listes simplements chainées -

 Quelques procédures de gestion des  listes simplement chainées

La déclaration de la cellule :

Type Liste = ^Cellule ;

Type Cellule = enregistrement

 Info : typeqcq ;

Suivant : Liste ;

Fin ;

Procedure CréationListeNombreConnu ;

Procedure CréationListeNombreConnu( Tete, :Liste, NombreElt : entier) ;

Var p :liste ; i: entier

DEBUT

 Tete Nil ;

POUR i← 1 à NombreElt FAIRE

debut

   Allouer(P) ;

   Lire(P^.Info) ;

  P^.Suivant ← Tete ;

  Tete←  P ;

Fin ;

FIN ;

-Procédure d’insertion en tête de liste chaînée :

procédure insererEnTete(Tête : Liste, val : typeqcq) ;

Var : p : Liste ;

Début

allouer(p) ;             /* Création de la nouvelle cellule dans la liste*/

p^.info ← val ;

p^.suivant ← Tête

Tête ← p ;

Fin ;

-Procédure d’insertion en queue de liste chaînée :

procedure InsererEnQueue( Tête : Liste, val : typeqcq) ;

Var der, p : Liste ;

Début

si Tête = Nil alors                                              /* La liste est vide */

                    insererEnTete(Tête, val)

  sinon

début                                                     

der ← Tête ;

tantque der^.suivant ≠ Nil der ← der^.suivant ;   /* on récupère l’adresse du dernier élément */          

 allouer(p) ;                                            

 p^.info ← val ;                                     

 p^.suivant ← Nil ;

der^.suivant ← p

 fin

Fin ;          

        

- Procédure d’insertion à une position donnée :

procedure insererDansListe(Tête : Liste, val : typeqcq, pos : entier) ;

Variables pre : Liste ;

Début

si pos = 1 alors                                                   /* on souhaite insérer en tête de liste */

insererEnTete(Tête, val)

        sinon

debut 

pre  ← Tête ;

 tantque pre ≠ Nil ET pos > 2 faire debut pos ← pos - 1 ;pre ← pre^.suivant fin ;

si pre ≠ Nil alors     /* la position existe */ 1

allouer(p)                                                

 p^.info ← val

 p^.suivant ← pre^.suivant

pre^.suivant ← p fin

 Fin ;         

 

Procédure de suppression d’un élément d’une liste chaînée à une position donnée     

 

procedure supprimerDansListe(Tête : Liste, pos : entier) ;

Variables sauve, pre : Liste ;

Début

si Tête ≠ Nil alors                  /* liste non vide */

debut          

si pos = 1 alors  

debut                               /* on souhaite supprimer en tête */

 sauve ← Tête ;

Tête ← Tête^.suivant ;

desallouer(sauve) ;

fin 

 sinon

debut

pre  ← Tête ;

 tantque pre ≠ Nil ET pos >2 faire debut pos ← pos - 1 ;pre ← pre^.suivant fin ;

si pre ≠ Nil alors sauve ← pre^.suivant               /* adresse élt à supprimer */

si sauve ≠ Nil alors           /* l'élément à supprimer existe */

                           debut

                           pre^.suivant ← sauve^.suivant

                           desallouer(sauve)

                           fin ;

/* libère espace de l'élt supprimé */

Fin ;

Fin ;

Fin ;