Probleme de tri par insertion dans une liste chainée
cs_greg505
Messages postés
12
Date d'inscription
mercredi 8 mai 2002
Statut
Membre
Dernière intervention
24 mai 2006
-
24 mai 2006 à 14:56
cs_Forman Messages postés 600 Date d'inscription samedi 8 juin 2002 Statut Membre Dernière intervention 6 avril 2010 - 25 mai 2006 à 23:37
cs_Forman Messages postés 600 Date d'inscription samedi 8 juin 2002 Statut Membre Dernière intervention 6 avril 2010 - 25 mai 2006 à 23:37
1 réponse
cs_Forman
Messages postés
600
Date d'inscription
samedi 8 juin 2002
Statut
Membre
Dernière intervention
6 avril 2010
1
25 mai 2006 à 23:37
25 mai 2006 à 23:37
procedure tri_insertion(var p:pointeur_ligne_top);
var
q,r,s:pointeur_ligne_top;
begin
q:=p;
while Assigned(q.suivant) do begin
r:=q.suivant;
s:=r;
while Assigned(r.precedent) and (r.precedent.compteur>s.compteur) do
r:=r.precedent;
if r<>s then begin
q.suivant:=s.suivant;
if Assigned(s.suivant) then
s.suivant.precedent:=q;
if Assigned(r.precedent) then begin
r.precedent.suivant:=s;
s.precedent:=r.precedent;
end else begin
p:=s;
s.precedent:=nil;
end;
r.precedent:=s;
s.suivant:=r;
end else
q:=q.suivant;
end;
end;
Ca devrait marcher. Le problème de ton code, c'est que tu avançais dans la liste même si le dernier élément dont tu t'es occupé (temp) avait été déplacé vers la tête. Or, si c'est le cas, tu ne dois pas avancer dans la liste car en ayant déplacé un élément vers la tête, ça t'a déjà fait avancer (je ne sais pas si c'est très clair)...
Dans ma fonction, c'est le test
if r<>s
qui s'occupe de vérifier si c'est le cas ou non.
var
q,r,s:pointeur_ligne_top;
begin
q:=p;
while Assigned(q.suivant) do begin
r:=q.suivant;
s:=r;
while Assigned(r.precedent) and (r.precedent.compteur>s.compteur) do
r:=r.precedent;
if r<>s then begin
q.suivant:=s.suivant;
if Assigned(s.suivant) then
s.suivant.precedent:=q;
if Assigned(r.precedent) then begin
r.precedent.suivant:=s;
s.precedent:=r.precedent;
end else begin
p:=s;
s.precedent:=nil;
end;
r.precedent:=s;
s.suivant:=r;
end else
q:=q.suivant;
end;
end;
Ca devrait marcher. Le problème de ton code, c'est que tu avançais dans la liste même si le dernier élément dont tu t'es occupé (temp) avait été déplacé vers la tête. Or, si c'est le cas, tu ne dois pas avancer dans la liste car en ayant déplacé un élément vers la tête, ça t'a déjà fait avancer (je ne sais pas si c'est très clair)...
Dans ma fonction, c'est le test
if r<>s
qui s'occupe de vérifier si c'est le cas ou non.
