Ada 中的反向链表

Question

所以你可以看到我正在尝试制作一个程序来反转链表，这是列表和节点的代码和记录，我只获取列表的第一个数字，我想这可能是因为 pre 为 null 并且 head (Current) 指向 null 但我不确定，我不知道如何解决这个问题，谢谢。

Type Node;
Type List is access Node;
Type Node is record
    Info: Integer;
    nx: List;
end record;


 procedure reverselist (L: in out List) is
      Current: List:=L ;
      Pre: List:=null;
      Next: List:=null;
   begin
      if Current.nx /= null then
         while Current.nx /= null loop
            Next:= Current.nx;
            Current.nx:= Pre;
            Pre:= Current;
            Current:= Next;
         end loop;
      end if;
      
   end reverselist;

Answer 1

if Current /= null then
         while Current.nx /= null loop
            Next:= Current.nx;
            Current.nx:= Pre;
            Pre:= Current;
            Current:= Next;
         end loop;
         Next:= null;
         Current.nx:= Pre;
         L:= Current;
end if;

Answer 2

我会先从列表中反复弹出头部，然后以相反的顺序重新构建它：

procedure Reverse_List (L : in out list) is 
    Temp : List := null;  -- Holds a "popped" head
    Head : List := null;  -- This is the head of the reversed list
begin
    while L /= null loop
        Temp := L;        -- Pop the head of the list off
        L := L.nx;        -- Set the list head to the next item
        Temp.nx := Head;  -- Attach the popped node to the reversed head
        Head := Temp;     -- Reset the reverse head to the new node
    end loop;
    L := Head; -- Now set the input list pointer to the newly reversed list
end Reverse_List;

完整测试程序：

with Ada.Text_IO; use Ada.Text_IO;
procedure Hello is

    Type Node;
    Type List is access Node;
    Type Node is record
        Info: Integer;
        nx: List;
    end record;

    procedure Reverse_List (L : in out list) is 
        Temp : List := null;  -- Holds a "popped" head
        Head : List := null;  -- This is the head of the reversed list
    begin
        while L /= null loop
            Temp := L;        -- Pop the head of the list off
            L := L.nx;        -- Set the list head to the next item
            Temp.nx := Head;  -- Attach the popped node to the reversed head
            Head := Temp;     -- Reset the reverse head to the new node
        end loop;
        L := Head; -- Now set the input list pointer to the newly reversed list
    end Reverse_List;

    nodes : array (1..5) of List := 
        (new Node'(Info => 1, nx =>null),
         new Node'(Info => 2, nx =>null),
         new Node'(Info => 3, nx =>null),
         new Node'(Info => 4, nx =>null),
         new Node'(Info => 5, nx =>null));
         
         
    procedure Print(L : List) is
        C : List := L;
    begin
        while C /= null loop
            Put_Line(C.Info'Image);
            C := C.nx;
        end loop;
    end Print;
    
    L : List := nodes(1);

begin
    Put_Line("Hello, world!");
    nodes(1).nx := nodes(2);
    nodes(2).nx := nodes(3);
    nodes(3).nx := nodes(4);
    nodes(4).nx := nodes(5);
    
    Put_Line("Before:");
    Print(L);
    New_Line(2);
    Put_Line("After:");
    Reverse_List(L);
    Print(L);
end Hello;

输出：

$gnatmake -o hello *.adb
gcc -c hello.adb
gnatbind -x hello.ali
gnatlink hello.ali -o hello
$hello
Hello, world!
Before:
 1
 2
 3
 4
 5


After:
 5
 4
 3
 2
 1

Answer 3

展望未来，还要考虑 doubly linked list such as Ada.Containers.Doubly_Linked_Lists 的便利性。给定 Integer、

的包实例

package Integer_Lists is new Doubly_Linked_Lists (Integer);
use Integer_Lists;

Reverse_List 过程可以遍历 reverse 中的列表，如 Iteration, to create a new reversed list. Compare this approach to @Jere's 中所述。

procedure Reverse_List (L : in out List) is
   T : List;
begin
   for E of reverse L loop
      T.Append (E);
   end loop;
   L := T;
end Reverse_List;

作为复制元素的替代方法，该包还提供 Reverse_Elements，它“以相反的顺序重新排列 Container 的元素。”

Reverse_Elements (L);

完整示例：

with Ada.Containers.Doubly_Linked_Lists; use Ada.Containers;
with Ada.Text_IO;                        use Ada.Text_IO;

procedure DLL is

   package Integer_Lists is new Doubly_Linked_Lists (Integer);
   use Integer_Lists;

   procedure Reverse_List (L : in out List) is
      T : List;
   begin
      for E of reverse L loop
         T.Append (E);
      end loop;
      L := T;
   end Reverse_List;

   procedure Print (L : List) is
   begin
      for E of L loop
         Put_line (Integer'Image (E));
      end loop;
   end Print;

   L : List;

begin

   L.Append (1);
   L.Append (2);
   L.Append (3);

   Put_line ("Before:");
   Print (L);
   --Reverse_List(L);
   Reverse_Elements (L);
   Put_line ("After:");
   Print (L);
end DLL;

控制台：

Before:
 1
 2
 3
After:
 3
 2
 1

Ada 中的反向链表

Reverse linked list in Ada

list

ada