尝试在 Ada 中的简单链表上实现插入排序

Question

标题好像self-explanatory... 我已经研究 Ada 几个月了。起初，我对编程一无所知，然后我逐渐走上了自己的道路。下面的代码片段是可编译的，结果是：

5 2 16 20 8

2 5 8

第一行只是列表的内容，未排序。第二行在排序之后：已排序，但不完整！而且我不太明白为什么忽略了 16 和 20。将 "selection" 读为 "insertion"，将 "suivant" 读为 "next"。

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;

感谢帮助

Answer 1

您的问题是（此列表可能不完整）：

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，而不管手头的节点是什么）

编辑：我会做这样的事情（删除 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;

尝试在 Ada 中的简单链表上实现插入排序

trying to implement insertion sort on a simply linked list, in Ada

sorting

algorithm

ada

insertion-sort