Tri de liste (pointeurs)

**m@tix** · 14/05/2009, 00h50

Bonsoir,

Je cherche à réaliser un petit programme, dont voici les spécificités:

- Saisir des valeurs entières comprises dans un certain intervalle fournies par l'utilisateur. Rentrer 0 met fin à la saisie;
- Ranger ces valeurs dans une liste chaînée dans l'ordre croissant: valeur négatives en début de liste, positives en fin;
- Afficher la liste.

Je pense avoir réussi à faire le premier point. De plus, l'insertion des valeurs dans une liste ainsi que son affichage semble fonctionner (test unitaire réalisé). En revanche, j'ai des difficultés à faire le tri des valeurs dans la liste. J'essaye de me représenter la situation avec des schémas, un peu en vain. Pourriez-vous m'expliquer comment faire svp?

Je vous poste ce que j'ai déjà fait, afin d'utiliser les mêmes notations lors des éventuelles explications:

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
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
procedure Prog_1 is

   -- Declaration des types et sous-types

   subtype Entiers is Integer range -50..50;

   type Element;
   type Liste is access Element;

   type Element is
      record
         Val  : Entiers;
         Suiv : Liste;
      end record;


   procedure Saisir (
         Ma_Liste :    out Liste) is

      N         : Entiers;
      Continuer : Boolean := False;

   begin

      Continuer := True;

      Put("Veuillez rentrer les valeurs de votre liste, comprises entre -50 et 50; taper 0 terminera la saisie.");

      while Continuer = True loop

         New_Line(2);
         Get(N);
         Skip_Line;

         if N = 0 then

            Continuer := False;

         end if;

      end loop;

   end Saisir;


   procedure Inserer (
         Ma_Liste : in out Liste;
         Valeur   : in     Entiers) is

      Aux : Liste := Ma_Liste;

   begin

      if Ma_Liste = null then

         Ma_Liste := new Element'(Valeur, null);

      else

         Inserer(Aux.All.Suiv, Valeur);
         Ma_Liste := Aux;

      end if;

   end Inserer;


   procedure Afficher (
         Ma_Liste : in     Liste) is

      Aux : Liste := Ma_Liste;

   begin

      Put("La liste que vous venez d'entrer est la suivante: ");

      New_Line(2);

      while Aux /= null loop

         Put(Aux.All.Val,1);
         New_Line;
         Aux := Aux.All.Suiv;

      end loop;

   end Afficher;


   -- Structure du programme principal

   Ma_Liste : Liste;
   Valeur: Entiers;

begin

   --Ma_Liste := new Element'(3,new Element'(-5,null));   <==TEST D'AFFICHAGE OK

   Saisir(Ma_Liste);
   Inserer(Ma_Liste, Valeur);
   Afficher(Ma_Liste);

end Prog_1;

Par ailleurs, si je constate que l'affichage fonctionne correctement avec l'exemple 3,-5 pour le test, je remarque qu'il n'en est pas de même lorsque je fais passe par la procédure de saisie: en effet, un nombre très grand s'affiche à la place de mes valeurs rentrées: d'où vient le problème?

Merci d'avance!

**m@tix** · 17/05/2009, 03h01

Personne n'a d'idées..?

Invité · 17/05/2009, 16h01

Envoyé par m@tix

Personne n'a d'idées..?

Salut,

Dans inserer, tu fait appel à inserer pour inserer ta valeur

A ta place, je relirais l'énoncé du problème, et je recommencerais à zéro.

**m@tix** · 17/05/2009, 17h43

Envoyé par jovalise

Salut,

Dans inserer, tu fait appel à inserer pour inserer ta valeur

A ta place, je relirais l'énoncé du problème, et je recommencerais à zéro.

Ben, pourquoi pas, c'est du récursif..

Invité · 17/05/2009, 19h15

Envoyé par m@tix

Ben, pourquoi pas, c'est du récursif..

Ah pardon.

Dans saisir tu sorts une liste qui n'est jamais affectée en tout cas.

**m@tix** · 17/05/2009, 19h55

Que faudrait-il faire alors?

Invité · 17/05/2009, 20h41

Envoyé par m@tix

Que faudrait-il faire alors?

Ne pourrais-tu pas stocker les valeurs dans un tableau dans un premier temps ?
Pour les insérer dans l'ordre dans la liste en suite.
Et finir par afficher la liste.

**m@tix** · 17/05/2009, 23h23

Et bien justement non, on m'impose de ne pas utiliser de tableaux, contraints ou non contraints, uniquement la gestion de liste à travers les pointeurs. Et justement, je ne vois pas tellement comment faire pour effectuer un tri de cette façon..

Invité · 18/05/2009, 08h06

Par exemple... Pour construire la liste

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
 
procedure Inserer (
                      Ma_Liste : in out Liste;
                      Valeur   : in     Entiers) is
 
 
   begin
 
      Ma_Liste := new Element'(Valeur, Ma_liste);
 
   end Inserer;
 
 
 
   procedure Saisir (
         Ma_Liste :    out Liste) is
 
      N         : Entiers;
      Continuer : Boolean := False;
 
   begin
 
      Continuer := True;
 
      Put("Veuillez rentrer les valeurs de votre liste, comprises entre -50 et 50; taper 0 terminera la saisie.");
 
      while Continuer = True loop
 
         New_Line(2);
         Get(N);
         Skip_Line;
 
         if N = 0 then
 
            Continuer := False;
 
         end if;
         Inserer(Ma_Liste, N);
      end loop;
 
   end Saisir;

**m@tix** · 18/05/2009, 10h05

Ok, je viens de tester, ça fonctionne très bien! Merci, je pense avoir compris mes erreurs.

Par contre, en rajoutant au programme la procédure d'affichage suivante:

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
procedure Afficher (
         Ma_Liste : in     Liste) is

      Aux : Liste := Ma_Liste;

   begin

      Put("La liste que vous venez d'entrer est la suivante: ");

      New_Line(2);

      while Aux /= null loop

         Put(Aux.All.Val,1);
         New_Line;
         Aux := Aux.All.Suiv;

      end loop;

   end Afficher;

L'affichage de la liste se fait bel et bien, mais le premier élément de la liste rentré est le dernier affiché, et le dernier le premier, etc.. Comment cela se fait-il? Il me semble pourtant qu'avec la procédure d'affichage que j'ai faite, cela devrait balayer la liste du début jusqu'à la fin, et pas le contraire...

Enfin, concernant le "tri" de cette liste comme j'en avais parlé au début, une idée?

Encore merci.

Invité · 18/05/2009, 10h35

Envoyé par m@tix

L'affichage de la liste se fait bel et bien, mais le premier élément de la liste rentré est le dernier affiché, et le dernier le premier, etc.. Comment cela se fait-il? Il me semble pourtant qu'avec la procédure d'affichage que j'ai faite, cela devrait balayer la liste du début jusqu'à la fin, et pas le contraire...

Parce que j'insère les élément en tête de liste.
Pour les avoir dans l'ordre de saisie, il faudrait les insérer en queue. Mais puisque tu dois trier la liste peut importe non ?

**m@tix** · 18/05/2009, 13h03

Envoyé par jovalise

Parce que j'insère les élément en tête de liste.
Pour les avoir dans l'ordre de saisie, il faudrait les insérer en queue. Mais puisque tu dois trier la liste peut importe non ?

Oui en effet, mais puisque je suis loin de tout maîtriser, c'était par simple curiosité. Ainsi, je suppose qu'on peut les insérer en queue de liste assez facilement?

**Fate_B** · 18/05/2009, 15h50

Pour les insérer en fin, tu parcours la liste jusqu'à ce que la derniere case soit nulle, ensuite tu rajoute un élément à cette liste (càd la case suivante pointe sur null):

while aux.all.suiv/=null loop
aux:=aux.all.suiv;
end loop;

aux.all.suiv:=new Element'(Nombre, null);

**m@tix** · 18/05/2009, 16h48

D'accord, merci pour l'info!

C'est souvent que je parviens à percevoir l'algorithme, mais le "traduire" dans le langage est parfois plus difficile...

Concernant le tri, je suppose qu'il doit falloir comparer chaque élément rentré avec tous les autres...? Mais avant de faire ça, j'aurais voulu faire un cas plus simple: en admettant qu'on ait déjà une liste de rentrée triée par ordre croissant, je cherche donc en premier lieu à faire un sous-programme d'insertion d'un élément dans cette liste déjà triée, pour mettre ce nouvel élément à la "bonne" place. Déjà, deux cas à distinguer il me semble: si l'élément à rajouter est plus petit que le premier élément de la liste, alors on l'insère en début de liste, s'il est plus grand que le dernier, on l'insère en fin de liste... non? Par contre, dans un cas quelconque...

Tri de liste (pointeurs)

Ada

Discussions similaires

Partager

Partager