Problème pour trier (par insertion) une liste chainée

**gregb34** · 24/05/2006, 06h09

Bonjour,

ca fait 6h que je me prend la tête pour essayer de trier une liste chainée avec un tri par insertion.

J'ai une liste chainée constitué de :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
  pointeur_ligne_top = ^t_ligne_top;
  t_ligne_top=record
    page:string[100];
    compteur:integer;
    suivant:pointeur_ligne_top;
    precedent:pointeur_ligne_top;
  end;

Je cherche à la trier à l'aide d'un tri par insertion, cette liste chainée selon COMPTEUR par ordre decroissant.

J'ai crée cette fonction :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
function top_min_insertion(var tete_top:pointeur_ligne_top;val:integer):pointeur_ligne_top;
var
  objet_top_min : pointeur_ligne_top;
begin
  objet_top_min := tete_top;
 
  while (objet_top_min^.compteur < val) do
    begin
      objet_top_min := objet_top_min.suivant;
    end;
 
  result := objet_top_min;
end;

La fonction principale est :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
procedure top_tri_insertion(var tete_top:pointeur_ligne_top;var fin_top:pointeur_ligne_top);
var
  tmp : pointeur_ligne_top;
  objet_top_min : pointeur_ligne_top;
begin
 
  tmp := tete_top^.suivant;
  while tmp <> nil do
    begin
 
      if tmp^.compteur > tmp^.precedent^.compteur then
        begin
          objet_top_min := top_min_insertion(tete_top,fin_top,tmp^.compteur);
 
          tmp^.precedent^.suivant := tmp^.suivant;
 
          if tmp^.compteur > tete_top.compteur then
            begin
              tmp^.suivant := tete_top;
              tmp^.precedent := nil;
              tete_top^.precedent := tmp;
              tete_top := tmp;
            end
          else
            begin
              tmp^.precedent := objet_top_min;
              tmp^.suivant := objet_top_min^.suivant;
 
              objet_top_min^.suivant^.precedent := tmp;
              objet_top_min^.suivant := tmp;
            end;
        end;
      tmp := tmp^.suivant;
    end;
end;

J'ai 2 petites liste chainée pour lequel ca marche mais une 3eme beaucoup plus volumineuse avec qui cela foire totalement. Si qqu a une idée, MERCI de votre aide.

**gregb34** · 24/05/2006, 07h55

Bon apparement le < n'etait pas bon dans la fonction "[FONT=monospace][/FONT]function top_min_insertion"

Mais, dans ma grande liste chainée, il y a des données qui sont zappées. Je comprends pas.

**LadyWasky** · 24/05/2006, 09h24

Salut

Déjà, j'ai détecté une erreur là dedans :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
function top_min_insertion(var tete_top:pointeur_ligne_top;val:integer):pointeur_ligne_top;
var objet_top_min : pointeur_ligne_top;
begin
  objet_top_min := tete_top;
 
  while (objet_top_min^.compteur < val) do
  begin
    objet_top_min := objet_top_min.suivant;
  end;
 
     result := objet_top_min;
end;

J'écrirais plutôt ceci

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

objet_top_min := objet_top_min^.suivant;

ensuite il faudrais tester, si on arrive pas en bout de liste dans le while

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
while ((objet_top_min^.compteur < val) and (objet_top_min^.suivant<>nil)) do
      objet_top_min := objet_top_min^.suivant;

Déclare ta grosse fonction comme ceci (ce sera plus concis) :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

 procedure top_tri_insertion(var tete_top,fin_top:pointeur_ligne_top);

Dans ta grosse procédure, tu écris :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

 objet_top_min := top_min_insertion(tete_top,fin_top,tmp^.compteur);

là, tu passe trois paramètres, alors que ta fonction n'en prend que deux...

Evite d'utiliser des variables qui ont le même nom que certaines fonctions standard, en particulier val, qui, normalement est une fonction qui convertit une chaine de caractères en nombre

Je regarde le reste

**LadyWasky** · 24/05/2006, 09h26

Le reste ne m'a pas l'air correct :
- dans ta grosse fonction, tu insère quoi au juste ? fin_top ?

**gregb34** · 24/05/2006, 12h32

La grosse fonction, me permet de mettre a jour les liens pour inserer la valeur actuellement lue au bon endroit. Je sais pas si tu arrives a voir

J'ai fait 2-3 modifs en corrigeant ce que tu m'as dit, plus d'autres petit trucs.

J'arrive à ca :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
 
function top_min_insertion(var tete_top:pointeur_ligne_top;val:integer):pointeur_ligne_top;
var
  tmp : pointeur_ligne_top;
begin
  tmp := tete_top;
 
while ((tmp^.compteur > val) and (tmp^.suivant<>nil)) do
  begin
    tmp := tmp^.suivant;
  end;
 
  result := tmp^.precedent;
end;
 
procedure top_tri_insertion(var tete_top:pointeur_ligne_top);
var
  tmp: pointeur_ligne_top;
  objet_top_min : pointeur_ligne_top;
begin
 
  tmp := tete_top^.suivant;
 
  while tmp <> nil do
    begin
 
      if tmp^.compteur > tmp^.precedent^.compteur then
        begin
 
          objet_top_min := top_min_insertion(tete_top,tmp^.compteur);
 
          tmp^.precedent^.suivant := tmp^.suivant;
 
          if ((tmp^.compteur > tete_top.compteur) or (objet_top_min = nil)) then
            begin
              tmp^.suivant := tete_top;
              tmp^.precedent := nil;
              tete_top^.precedent := tmp;
              tete_top := tmp;
            end
          else
            begin
              tmp^.suivant := objet_top_min^.suivant;
              tmp^.precedent := objet_top_min;
 
              objet_top_min^.suivant^.precedent := tmp;
              objet_top_min^.suivant := tmp;
            end;
        end;
 
      //Form1.Memo1.Lines.Add(tmp^.page);
      tmp := tmp^.suivant;
 
    end;
    ShowMessage('Fin du tri');
end;

Et voila le resultat d'un tri. En 1er, il y a la liste non triée puis à la suite, il y a la liste "triée" (tout en bas...), Vous verrez que ca a zappé les 3/4 des valeurs...

http://www.gregserveur.com/test/stats_1.html (218 Ko)

MERCI de votre aide, car la je desespère. J'y ai passé la nuit et je trouve toujours pas.

**LadyWasky** · 24/05/2006, 12h43

Envoyé par gregb34

La grosse fonction, me permet de mettre a jour les liens pour inserer la valeur actuellement lue au bon endroit. Je sais pas si tu arrives a voir

heuuu non, je ne vois pas, quelle valeur ? compteur ?

**gregb34** · 24/05/2006, 12h49

Le tri se fait par rapport au compteur.

Donc, si le compteur de la valeur actuelle (tmp^.compteur) est superieur au compteur precedent (tmp^.precedent^.compteur)

Alors, il va faloir refaire les liens de l'enregistrement actuelle (tmp) pour l'inserer au bon endroit.

Pour cela, j'appelle ma 2eme fonction qui detecte cette endroit (objet_top_min) dans la partie basse de la liste.... puis je refais les liens.

Si tmp^.compteur est superieur a tous les compteurs de la partie basse, alors, je l'inserer au tout debut et je redefinie la tete de la liste (tete_top) sinon, je l'inserer entre 2 valeurs.

**LadyWasky** · 24/05/2006, 12h58

Attends, attends

Cette une fonction de tri, pas d'ajout de nouvel objet par insertion

Je comprends mieux...

Bon je regarde ton code et je te dis

**gregb34** · 24/05/2006, 13h07

Merci bien

**gregb34** · 24/05/2006, 14h57

**LadyWasky** · 24/05/2006, 14h59

Bon, voilà ce à quoi j'ai abouti

J'ai mis le temps...

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
 
function top_min_insertion(var tete_top:pointeur_ligne_top;val:integer):pointeur_ligne_top;
var
  tmp : pointeur_ligne_top;
begin
  tmp := tete_top;
 
while ((tmp^.compteur > val) and (tmp^.suivant<>nil)) 
do tmp := tmp^.suivant;
 
  result := tmp^.precedent;
end; 
 
 
procedure insert(tete_top,ApresQuoi,Lequel : pointeur_ligne_top);
begin
  if tetetop=nil 
  then begin
           tetetop:=Lequel;
           exit;
         end;
  Lequel ^.precedent:=ApresQuoi;       
  if ApresQuoi=nil 
   then begin   { insertion début de liste}
             Lequel ^.suivant:=tete_top;
             tete_top:=Leque;
             exit;
          end
  //insertion normale
  Lequel ^.suivant:=ApresQuoi^.suivant; 
  ApresQuoi^.next:=Lequel ;       
end;
 
procedure detache(lequel : pointeur_ligne_top);
begin
     if Lequel^.precedent<>nil then Lequel^.precedent^.suivant:=Lequel^.suivant;
     if Lequel^.suivant<>nil then  Lequel^.suivant^.precedent:=Lequel^.precedent;        
 Lequel^.suivant:=nil;
 Lequel^.precedent:=nil;
end;
 
procedure top_tri_insertion(var tete_top:pointeur_ligne_top);
var
  tmp,tmp2: pointeur_ligne_top;
  objet_top_min : pointeur_ligne_top;
begin
  tmp := tete_top;  
  if tmp<>nil then
  while tmp^.suivant<>nil do
    begin
      if tmp^.compteur<tmp^.suivant^.compteur then
        begin
            tmp2:=tmp^.suivant;
            detache(tmp2);
            objet_top_min := top_min_insertion(tete_top,tmp2^.compteur);
            insert(tete_top,objet_top_min,tmp2);
        end  
        else tmp:= tmp^.suivant;
    end;     
    ShowMessage('Fin du tri');
end;

**gregb34** · 24/05/2006, 15h04

Waaaaa

Je regarde ca...

C'est quoi le [FONT=monospace]le type [/FONT]pMycircqueue ?

**LadyWasky** · 24/05/2006, 15h07

Envoyé par gregb34

Waaaaa

Je regarde ca...

C'est quoi le [FONT=monospace]le type [/FONT]pMycircqueue ?

Un mauvais copié collé d'un vieux code que j'avais dans mes archives

J'ai corrigé (+un petit bug (appel à insert))

Le tri s'éffectue comme ceci :
0)courant=tete

Tant qu'on est pas en fin de liste :
1) on compare le courant avec le suivant
2) si le suivant est "mal placé" dans la liste :
- on le détache de la liste
- on lui cherche une place dans la liste
- on le réinsère à cette place
3) sinon courant=courant.suivant

**gregb34** · 24/05/2006, 15h12

J'ai corrigé les fautes de frappes

Alors, deja, toutes les valeurs sont prises en comptes contrairement a moi mais la liste obtenue n'est pas triée

Pourvu que je vois...

**LadyWasky** · 24/05/2006, 15h15

J'avais zappé un else

c'est pour ça que ça ne triait pas

**gregb34** · 24/05/2006, 15h21

Le ELSE c'est celui dans tri_top_insertion ?

Car la ca bloque

**LadyWasky** · 24/05/2006, 15h25

Envoyé par gregb34

Le ELSE c'est celui dans tri_top_insertion ?

Oui (else tmp:=tmp^.suivant

Envoyé par gregb34

Car la ca bloque

ha ? (on va y arriver...)

**gregb34** · 24/05/2006, 15h29

Thanks de ton aide, je cherche aussi.

Mais je sèche. En plus, les erreurs avec les pointeurs sont pas precises... c'est le bordel.

Erreur dans detache() a ce niveau la apparement

if Lequel^.precedent<>nil then Lequel^.precedent^.suivant:=Lequel^.suivant;

**LadyWasky** · 24/05/2006, 16h08

Bon, là j'ai pu tester le code (pc en panne) et maintenant ça marche (sur sur sur) :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
function top_min_insertion(var tete_top:pointeur_ligne_top;val:integer):pointeur_ligne_top;
var
  tmp : pointeur_ligne_top;
begin
  tmp := tete_top;
 
while ((tmp^.compteur > val) and (tmp^.suivant<>nil))
do tmp := tmp^.suivant;
 
  result := tmp^.precedent;
end;
 
 
 
procedure insert(var tete_top,ApresQuoi,Lequel : pointeur_ligne_top);
begin
  if tete_top=nil
  then begin
           tete_top:=Lequel;
           exit;
         end;
  Lequel ^.precedent:=ApresQuoi;
  if ApresQuoi=nil
   then begin   { insertion début de liste}
             Lequel ^.suivant:=tete_top;
             tete_top^.precedent:=Lequel;
             tete_top:=Lequel;
             exit;
          end;
  //insertion normale
  Lequel^.suivant:=ApresQuoi^.suivant;
  ApresQuoi^.suivant:=Lequel ;
end;
 
procedure detache(var lequel : pointeur_ligne_top);
begin
 if Lequel^.precedent<>nil then Lequel^.precedent^.suivant:=Lequel^.suivant;
 if Lequel^.suivant<>nil then  Lequel^.suivant^.precedent:=Lequel^.precedent;
 Lequel^.suivant:=nil;
 Lequel^.precedent:=nil;
end;
 
 
 
procedure top_tri_insertion(var tete_top:pointeur_ligne_top);
var
  tmp,tmp2: pointeur_ligne_top;
  objet_top_min : pointeur_ligne_top;
begin
  tmp := tete_top;
  if tmp<>nil then
  while tmp^.suivant<>nil do
    begin
      if tmp^.compteur<tmp^.suivant^.compteur then
        begin
            tmp2:=tmp^.suivant;
            detache(tmp2);
            objet_top_min := top_min_insertion(tete_top,tmp2^.compteur);
            insert(tete_top,objet_top_min,tmp2);
        end
        else tmp:= tmp^.suivant;
    end;
    ShowMessage('Fin du tri');
end;

**LadyWasky** · 24/05/2006, 16h10

Envoyé par gregb34

Thanks de ton aide, je cherche aussi.

Mais je sèche. En plus, les erreurs avec les pointeurs sont pas precises... c'est le bordel.

Erreur dans detache() a ce niveau la apparement

if Lequel^.precedent<>nil then Lequel^.precedent^.suivant:=Lequel^.suivant;

- manquait un var pour passer le parametre comme reference !
- et une ligne dans insert pour linker l'ancien liste_top au nouveau

pas facile sans PC

Problème pour trier (par insertion) une liste chainée

Delphi

Discussions similaires

Partager

Partager