Rangement d'une liste

Rangement d'une liste - Ada - Programmation

Marsh Posté le 02-06-2009 à 19:47:43    

Bonsoir,
 
C'est encore moi, avec une nouvelle fois un problème sur les listes. J'explique mon sujet. Je cherche à écrire un programme qui range des valeurs saisies par un utilisateur au fur et à mesure dans une liste chaînée. Les valeurs négatives sont rangées en début de liste, et les valeurs positives sont rangées en fin de liste; la valeur 0 n'est pas rangée dans la liste, la saisie se termine quand l'utilisateur rentre 0.
 
Par exemple:
 
Si l'utilisateur fournit successivement les valeurs 4, -5, 8, 2, -3, -9, 1, 0, on cherche à obtenir l'affichage suivant:
 
"La liste contient les valeurs suivantes: -9 -3 -5 4 8 2 1."
 
Pour l'instant, voici ce que j'ai fait (je n'ai pas encore fait la procédure de saisie, il faut d'abord que le reste fonctionne, c'est plus important à mon avis):
 

Code :
  1. with Ada.Text_IO, Ada.Integer_Text_IO;
  2. use Ada.Text_IO, Ada.Integer_Text_IO;
  4. procedure Prog is
  5.  
  6.    -- Déclaration des types et sous-types
  7.  
  8.    subtype Entiers is Integer range -50..50;
  9.  
  10.    type Element;
  11.  
  12.    type Liste is access Element;
  13.  
  14.    type Element is record
  15.      
  16.       Valeur: Entiers;
  17.       Suivant: Liste;
  18.      
  19.    end record;
  20.  
  22.    -- Sous-programme qui range une valeur donnée dans une liste: les élements négatifs à gauche, les positifs à droite
  23.  
  24.    procedure Ranger_Dans_Liste (Ma_Valeur: in Entiers; Ma_Liste: in out Liste) is
  25.      
  26.       Aux: Liste := Ma_Liste;
  27.      
  28.    begin
  29.      
  30.       if Ma_Liste = null then
  31.        
  32.          Ma_Liste := new Element'(Ma_Valeur,null);
  33.        
  34.       else
  35.        
  36.          if Ma_Valeur < 0 then
  37.            
  38.             if Aux.All.Valeur > 0 then
  39.              
  40.                Aux := new Element'(Ma_Valeur,Aux);
  41.              
  42.             elsif Aux.All.Valeur < 0 then
  43.              
  44.                Aux := new Element'(Ma_Valeur, Aux.All.Suivant);
  45.              
  46.             end if;
  47.            
  48.          elsif Ma_Valeur > 0 then
  49.            
  50.             if Aux.All.Valeur > 0 then
  51.              
  52.                Aux := new Element'(Ma_Valeur, Aux.All.Suivant);
  53.              
  54.             elsif Aux.All.Valeur < 0 then
  55.              
  56.                Aux := new Element'(Ma_Valeur, Aux);
  57.              
  58.             end if;
  59.            
  60.          end if;
  61.        
  62.       end if;
  63.      
  64.    end Ranger_Dans_Liste;
  65.  
  67.    -- Sous-programme d'affichage de la liste (ordre de saisie)
  68.  
  70.    procedure Afficher_Liste (Ma_Liste: in Liste) is
  71.      
  72.       Aux: Liste := Ma_Liste;
  73.  
  74.    begin
  75.      
  76.       Put("Valeurs contenues dans la liste: " );
  77.       new_line(2);
  78.      
  79.       while Aux /= null loop
  80.        
  81.          Put(Aux.All.Valeur,0);
  82.          new_line;
  83.          Aux := Aux.All.Suivant;
  84.        
  85.       end loop;
  86.      
  87.    end Afficher_Liste;
  88.  
  92.    -- Declaration du programme general
  93.  
  95.    Ma_Liste: Liste;
  96.  
  97. begin
  98.  
  99.    Ma_Liste := new Element'(-3,new Element'(-1, new Element'(4,null)));
  100.    Ranger_Dans_Liste(-2, Ma_Liste);
  101.    Afficher_Liste(Ma_Liste);
  102.  
  103. end Prog;


 
Pour une liste vide, pas de problèmes, ça fonctionne! :bounce:  
Dans le cas contraire, ça ne va plus du tout par contre: j'ai par exemple essayé de ranger une valeur négative (-2), dans une liste donnée: -3 -1 4, en vain. Voyez-vous où sont les problèmes? J'ai essayé de m'illustrer le problème, mais je ne parviens pas à voir ce qui ne va pas. Si vous avez des questions relatives à mon code, n'hésitez surtout pas! En espérant que vous pourrez me guider, merci d'avance! ;)

Reply

Marsh Posté le 02-06-2009 à 19:47:43   

Reply

Marsh Posté le 11-06-2009 à 12:49:07    

Pourquoi ne pas utiliser les conteneurs standard de Ada.Containers comme par exemple Ada.Containers.Ordered_Sets qui est triéée?
 
Bah je me doute que c'est dans un but pédagogique, alors ok.

Reply

Marsh Posté le 11-06-2009 à 13:51:07    

Ton erreur viens du fait que ta procédure Ranger_Dans_Liste, ne parcours pas ta liste en profondeur, elle se limite à visiter le 1er ou le 2ème élement de ta liste. Il faut utiliser une boucle ou faire de ta procédure une procédure récursive.
 
A part cela, ta procédure Ranger_Dans_Liste fais trop usine-à-gaz, il y a plus simple. Tu as aussi la version procédure récursive, que je n'indique pas ici tellement elle est simple (c'est un cas d'école), je pense que tu pourras la faire facilement une fois que tu auras compris le principe de ma version ci-dessous.
 
Petite remarque: Comment aie-je pu écrire mon exemple ci-dessous? Simple l'idée est la même que la procédure Afficher_Liste.
 

Code :
  1. with Ada.Text_IO, Ada.Integer_Text_IO;
  2. use Ada.Text_IO, Ada.Integer_Text_IO;
  4. procedure Prog is
  5.  
  6.    -- Déclaration des types et sous-types
  7.  
  8.    subtype Entiers is Integer range -50..50;
  9.  
  10.    type Element;
  11.  
  12.    type Liste is access Element;
  13.  
  14.    type Element is record
  15.      
  16.       Valeur: Entiers;
  17.       Suivant: Liste;
  18.      
  19.    end record;
  20.  
  22.    -- Sous-programme qui range une valeur donnée dans une liste: les élements négatifs à gauche, les positifs à droite
  23.  
  24.    procedure Ranger_Dans_Liste (Ma_Valeur: in Entiers; Ma_Liste: in out Liste) is
  26.       type Adr_Liste is not null access all Ma_Liste;
  27.      
  28.       Res: aliased Liste := Ma_Liste;
  29.       Aux: Adr_Liste := Res'Access;
  30.      
  31.    begin
  32.      
  33.       if Ma_Liste = null then
  34.        
  35.          Ma_Liste := new Element'(Ma_Valeur,null);
  36.        
  37.       else
  38.        
  39.          while (Aux.All /= null) and (Aux.All.All.Valeur < 0) loop
  41.             Aux := Aux.All.All.Suivant'Access;
  42.        
  43.          end loop;
  45.          Aux.All := new Element'(Ma_Valeur, Aux.All);
  47.          Ma_Liste := Res;
  49.       end if;
  50.      
  51.    end Ranger_Dans_Liste;
  52.  
  54.    -- Sous-programme d'affichage de la liste (ordre de saisie)
  55.  
  57.    procedure Afficher_Liste (Ma_Liste: in Liste) is
  58.      
  59.       Aux: Liste := Ma_Liste;
  60.  
  61.    begin
  62.      
  63.       Put("Valeurs contenues dans la liste: " );
  64.       new_line(2);
  65.      
  66.       while Aux /= null loop
  67.        
  68.          Put(Aux.All.Valeur,0);
  69.          new_line;
  70.          Aux := Aux.All.Suivant;
  71.        
  72.       end loop;
  73.      
  74.    end Afficher_Liste;
  75.  
  79.    -- Declaration du programme general
  80.  
  82.    Ma_Liste: Liste;
  83.  
  84. begin
  85.  
  86.    Ma_Liste := new Element'(-3,new Element'(-1, new Element'(4,null)));
  87.    Ranger_Dans_Liste(-2, Ma_Liste);
  88.    Afficher_Liste(Ma_Liste);
  89.  
  90. end Prog;


 
Ce qui est beau ce que le nombre de comparaison est limité à la liste, nul besoin de tester la valeur de l'argument Ma_Valeur passé à la procédure Ranger_Dans_Liste. Mais j'avoue l'utilisation d'un type accès d'un accès (type Adr_Liste) est un peu limite, et propose donc une solution qui peut être pris pour de l'Ada bon marché et peut mal passer pour des puristes de l'Ada, car cette solution est plus inspirée du langage C ou du C++.
 
La meilleure solution est d'utiliser des objets et de convertir le type Liste en tagged record. La manipulation de la liste chainée gagnerai en simplicité du code et permettrait au code d'etre plus dans la philosophie Ada en évitant ce type Adr_Liste.
 
sinon une autre version tout aussi simple serait:

Code :
  1. if négatif then
  2.   mettre au début;
  3. else
  4.   aller à la fin de la liste;
  5.   mettre à la fin;
  6. end if;


 
ou

Code :
  1. Res: Liste := Ma_Liste;
  2.    Aux: Liste := Ma_Liste;
  4. begin
  6.    ( .... )
  8.    if Ma_Valeur < 0 then
  9.       Ma_Liste:= new Element'(Ma_Value, Res);
  10.    else
  11.       while Aux.All.Suivant /= null loop
  12.          Aux:= Aux.All.Suivant;
  13.       end loop;
  14.      
  15.       Aux.All.Suivant:= new Element'(Ma_Valeur, null);
  17.       Ma_Liste:= Res;
  18.    end if;
  20.    ( .... )
  21.  
  22. end;


Message édité par Corebreaker le 11-06-2009 à 14:04:23
Reply

Sujets relatifs:

Leave a Replay

Make sure you enter the(*)required information where indicate.HTML code is not allowed