пытаясь реализовать вставку сортировки в просто связанный список, в Аде - PullRequest
Новая
       10

пытаясь реализовать вставку сортировки в просто связанный список, в Аде

0 голосов
/ 03 мая 2018

название кажется само собой разумеющимся ... Я изучаю Аду уже несколько месяцев. Сначала я ничего не знал о программировании в целом, затем я постепенно начал свой путь. Фрагмент ниже является компилируемым и имеет результат:

5 2 16 20 8

2 5 8

Первая строка - это просто содержимое списка, не отсортированное. Вторая строка после сортировки: отсортирована, но не завершена! И я не совсем понимаю, почему конкретно 16 и 20 были проигнорированы. Прочитайте «selection» как «вставка», «suivant» как «следующий». 

with ada.text_io;
use ada.text_io;
procedure MAIN is
   subtype T_ELEMENT is NATURAL;
   type T_Cellule;
   type T_Liste is access T_Cellule;
   type T_Cellule is record
      Valeur  : T_Element;
      Suivant : T_Liste;
   end record; 

type TAB is array (Positive range <>) of Natural;

function Create_Liste (T : Tab) return T_Liste is
      L : T_Liste := new T_Cellule;
   begin
      if T'Length = 0 then return null; end if;
      L.Valeur := T (T'First);
      declare
     C : constant T_Liste := L;
      begin
     for I in T'First + 1 .. T'Last loop
        L.suivant := new T_Cellule;
        L := L.Suivant;
        L.Valeur := T (I);
     end loop;
     return C;
      end;
   end Create_Liste;

   procedure SELECTION
      (Liste : in out T_Liste; 
       Less_Than : access function 
          (ELEMENT, Element2 : in T_ELEMENT) return BOOLEAN) 
   is
      Head : constant T_Liste := new T_Cellule '(Suivant => Liste, others => <>); -- meant as something to affect to "Liste" at last.
      Iter : T_Liste := Head; -- that which will iterate through the list each time a new element needs to be tested against the ones before it.
      Pred : T_Liste := Liste; -- that before the "current", which has the element to be inserted. Needed so as to sew properly elements with each other.
   begin
      Liste := Liste.Suivant;
      while Liste /= null loop
         declare
            Suivant : constant T_Liste := Liste.Suivant; -- so as to record the next element to be inserted.
         begin
            Iter := Head;
            while Iter /= Liste loop
               if Less_Than (Liste.Valeur, Iter.Suivant.Valeur) then
                  Pred.Suivant := Liste.Suivant;
                  Liste.Suivant := Iter.Suivant;
                  Iter.Suivant := Liste;
               end if;
               Iter := Iter.Suivant;
            end loop;
            Liste := Suivant;
            Iter := Head;
         end;
      end loop;
      Liste := Head.Suivant; -- Liste is set to the beginning of the newly sewn list.
   end SELECTION;

   LISTE_SELECTION : T_LISTE := Create_Liste ((5, 2, 16, 20, 8));
   function Less_Than (A, B : Natural) return Boolean is ( A < B);

   Iter : T_Liste;
begin
   for I in 1 .. 2 loop
      ITER := LISTE_SELECTION;
      while Iter /= null loop
         Put (Iter.VALEUR'IMG & ' ');
         Iter := Iter.Suivant;
      end loop;
      New_Line (2);
      SELECTION (LISTE_SELECTION, Less_Than'ACCESS);
   end loop;
end Main;

Спасибо за помощь

1 Ответ

0 голосов
/ 03 мая 2018

Ваша проблема (и этот список может быть неполным): 

Head : constant T_Liste := new T_Cellule '(Suivant => Liste, others => <>); -- meant as something to affect to "Liste" at last.
Pred : T_Liste := Liste; -- that before the "current", which has the element to be inserted. Needed so as to sew properly elements with each other.

Оба из которых никогда не обновляются, поэтому

  • Head.Suivant всегда будет указывать на узел 5 (это не удастся для более сложного ввода),
  • Pred всегда будет указывать на узел 5 (поэтому всякий раз, когда включается ваш тест на Less_Than, он обновляет 5.Suivant, независимо от того, какой узел находится под рукой)

Edit: Я бы сделал что-то вроде этого (убрав необходимость в Pred): 

   Head : T_Liste;
   Suivant : T_Liste := Liste;
begin
   while Suivant /= null loop
      Suivant := Liste.Suivant;
      if Head = null 
         or else Less_Than (Liste.Valeur, Head.Valeur) 
      then
         Liste.Suivant := Head;
         Head := Liste;
      else
         declare
            Iter : T_Liste := Head;
         begin
            while Iter /= null loop
               if Iter.Suivant = null 
                  or else Less_Than (Liste.Valeur, Iter.Suivant.Valeur) 
               then
                  Liste.Suivant := Iter.Suivant;
                  Iter.Suivant := Liste;
                  exit;
               end if;
               Iter := Iter.Suivant;     
            end loop;
         end;
      end if;
      Liste := Suivant;
   end loop;
   Liste := Head;
...