list - 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

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

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