Exercices (pc 4) Corrigé

1.

procedure Supprimer(x: Element; var a: Liste);
var b,c: Liste;
begin
if a <> nil then
 if a^.contenu= x then
   a:=a^.suivant
 else begin
  b:=a;c:=a^.suivant;
  while c <> nil do
   if c^.contenu <> x then begin
     b:=c;
     c:=c^.suivant;
   end
   else begin
    b^.suivant:=c^.suivant;
    c:=nil
   end
end
end;

2. Il suffit d’inserer en tete :

procedure retourner(a:Liste;var b: Liste);
var c: Liste;
begin
c:= a;
while c <> nil do begin
 Inserer(c^.contenu,b);
 c:= c^.suivant
end
end;

3. On utilise une version fonctionnelle de Inserer :

function Inserer(x: Element;   a: Liste): Liste;
var b: Liste;
begin
new(b);
b^.contenu:= x;
b^.suivant:= a;
Inserer:= b
end;

function concat(a: Liste; b: Liste): Liste;
 begin
  if a= nil then
   concat:= b
  else
   concat:= Inserer( a^.contenu, concat(a^.suivant,b));
 end;

Pour une execution en temps constant, il faut utiliser des listes gardées en tête et en queue.