type VersElement: ^Element;
procedure InsertionDebut(var Debut: VersElement;
Information: InfoType);
var Nouveau: VersElement;
begin
new(Nouveau); {1:crée un nouvel élém. }
with Nouveau^ do begin
Info := Information; {2:y met l'info }
Suivant := Debut; {3:le relie à la }
end; { with } { chaîne existante }
Debut := Nouveau; {4:le nouvel element devient le 1-er}
end; { InsertionDebut } {5:la var. locale disparaît }
On peut illustrer les quatre étapes de cette procédure à
l'aide de la figure 7.1.
L'insertion en début de chaîne a l'inconvénient de stocker les éléments dans l'ordre inverse de traitement. Si l'on désire que l'ordre de stockage corresponde à l'ordre d'insertion, il faut insérer les éléments à la fin de la chaîne. En conservant les déclarations faites plus haut, l'algorithme d'insertion en fin de chaîne peut être décrit par la procédure InsertionFin1 de la page suivante.
procedure InsertionFin1(var Debut: VersElement;
Information: Info);
var Courant: VersElement;
begin { InsertionFin1 }
if Debut = nil then begin {chaîne vide}
{ création du premier élément }
new(Debut);
with Debut^ do begin
Info := Information;
Suivant := nil;
end; { with }
end
else begin
{ recherche du dernier élément }
Courant := Debut;
while Courant^.Suivant <> nil do
Courant := Courant^.Suivant;
{ crée un élément après le dernier }
new(Courant^.Suivant)
with Courant^.Suivant^ do begin
Info := Information;
Suivant := nil;
end; { with }
end;
end; { InsertionFin1 }
Cet algorithme d'insertion en fin de chaîne est assez inefficace car il faut
à chaque fois parcourir toute la chaîne pour trouver le dernier élément. Si
l'on doit renouveler cette opération à plusieurs reprises, on a intérêt à avoir
un pointeur indiquant la fin de la chaîne, en plus du pointeur de début. Il
est à noter que cette solution complique un peu les autres manipulations de
chaînes car il faut s'assurer, à chaque modification, que le pointeur Fin est
mis à jour s'il y a lieu.
type Chaine: record
Debut, Fin: VersElement;
end; { Chaine }
procedure InsertionFin2(var LaChaine:Chaine;
Information: Info);
var Nouveau: VersElement;
begin { InsertionFin2 }
new(Nouveau); { créer le nouvel élém. }
with Nouveau^ do begin
{ remplir le nouvel élément }
Info := Information;
Suivant := nil;
end; { with }
with LaChaine do begin
{ mise-à-jour de la str. de chaîne}
if Debut = nil then
{ chaîne vide } Debut := Nouveau
else Fin^.Suivant := Nouveau;
Fin := Nouveau;
end; { with }
end; { InsertionFin2 }
Il est clair que, pour de telles chaînes (avec pointeur Fin), l'ensemble des
opérations effectuées devra tenir à jour ce pointeur Fin.
Si l'on désire stocker les éléments dans un ordre indépendant de l'ordre d'insertion (par exemple triés), on peut être amené à faire des insertions après ou avant un élément donné.
procedure InsertionApres(Courant: VersElement;
Information: InfoType);
{ cette procédure ne fonctionne que pour
des chaînes spécifiées par un pointeur
Debut (pas de pointeur Fin) }
var Nouveau: VersElement;
begin { InsertionApres }
new(Nouveau);
with Nouveau^ do begin
Info := Information;
Suivant := Courant^.Suivant;
end; { with }
Courant^.Suivant := Nouveau;
end; { InsertionApres }
Pour une insertion avant un élément donné, il est généralement plus simple
de faire une insertion après, puis d'échanger les informations du nouvel
élément et de l'élément donné. Cela évite de devoir parcourir toute la chaîne depuis son début pour retrouver le prédécesseur de l'élément à insérer.
7.2. modification
Table des
matières.