Хранить каждый узел дерева в массиве

Question

Я должен хранить каждый узел общего дерева, которое может состоять из любого типа. Я должен сделать это в ADA, но мне просто нужен способ думать.

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

Array3:=Array1+Array2;

оператор "+" очень полезен, например, для рекурсивного подсчета.

Есть способ сделать это рекурсивно, сохранив каждый результат в массиве без использования какого-либо оператора?

Или алгоритм удобнее делать итеративно?

Заранее спасибо.

РЕДАКТИРОВАТЬ Код в ADA, который я пробовал с конкатенацией операторов массивов

function Get_all_nodes (Current_Node : in Tree) return Something_Concatenation.Element_Array is 
array_of_results:Something_Concatenation.Element_Array(1..50);
begin
if (Tree_is_null(Current_Node)) then
    return array_of_results;
else
array_of_results(1):=Get_value_of_node(Current_Node);
array_of_results:= array_of_results & Get_all_nodes(Get_access_to_parent1(Current_Node));
array_of_results:= array_of_results & Get_all_nodes(Get_access_to_parent1(Current_Node));
end if;
return array_of_results;
end Get_all_nodes;

Привет

Answer 1

Итак, я попробовал рекурсивную и итеративную версию. В итерационной версии я получил что-то вроде этого, я использовал стеки, которые разрешены в моих случаях

function get_all_nodes(Current_Node:in Tree) return Stack is
--declarations
My_Stack: Stack;
copy:Tree;
finished: Boolean:=False;
begin
--Initialisation

copy:=Current_Node;
My_Stack:=Initialisation;
--beginning by pushing the first node on the stack

push_on_stack(stack,copy.all.elt);

while(copy/=null or finished =False) loop
--check that we can put the first parent on stack
    if(copy.all.parent1/=null and not Found_in_Stack(My_Stack,copy.all.parent1.all.elt)) then
        copy:=copy.all.parent1;
        push_on_stack(stack,copy.all.elt);
    end if;
--check that we can put the second parent on stack
    if(copy.all.parent2/=null and not Found_in_Stack(My_Stack,copy.all.parent2.all.elt)) then
        copy:=copy.all.parent2;
        push_on_stack(stack,copy.all.elt);
    end if;
--check we are on case where both parents are already on stack or both null
    if(copy.all.parent1=null and copy.all.parent2=null) or 
    (Found_in_Stack(My_Stack,copy.all.parent1.all.elt) and (Found_in_Stack(My_Stack,copy.all.parent2.all.elt))) then
    --check we are on case where we are back to first node and then it's finished 
        if(copy.all.elt=Current_Node.all.elt) then
            finished:=True;
        else
        --go back to previous node thanks to stack
            copy:= First_Element_after_top_of_stack(My_Stack);
        end if;
    end if;
end loop;
return My_Stack;
end get_all_nodes;

И у меня есть некоторые ошибки где-то в этот момент

copy.all.parent2/=null and not Found_in_Stack(My_Stack,copy.all.parent2.all.elt)

Там, где кажется, что выполняется второе условие после первого, и я получаю ошибку, потому что copy.all.parent2.all.elt = null вместо универсального элемента, который находится в стеке и в дереве.

Я попробовал рекурсивную версию по этому коду:

function get_all_nodes (Current_Node : in Tree) return Integer_Concatenation.Element_Array is
use Integer_Concatenation;
use type Element_Array;
begin
if(Tree_is_null(Current_Node)) then
return (1..0 => <>);
else
return Element_Array'(1 => Get_node_value(Current_Node)) & get_all_nodes(Current_Node.all.parent1) & get_all_nodes(Current_Node.all.parent2);
end if;
end get_all_nodes;

У меня не получена одна проверка CONSTRAINT_ERROR длины.

Сейчас я проверю, как минимизировать проблему длины, прочитав ссылку на trashgod, в противном случае я проверю, могу ли я использовать контейнеры Ada.

Еще раз спасибо за вашу помощь всем. Привет.

Answer 2

В Ada оператор объединения является символом &. Массивы могут быть объединены вместе. Вы можете использовать это, чтобы делать рекурсивные вызовы, если хотите, но я бы не рекомендовал это из-за использования стека. Возможно, компилятор мог бы оптимизировать его, но поскольку вы возвращали бы неограниченный тип, он не может.

Вы не указали тип дерева или не предоставили какой-либо код, поэтому я не могу помочь вам с тем, как получить элементы из вашего типа дерева, но вот пример конкатенации массивов с использованием обобщений:

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

    -- Generic, since you asked about it in a generic context
    generic
        type Element_Type is limited private;
    package Concatenation is
        type Element_Array is array(Positive range <>) of Element_Type;
    end Concatenation;

    -- Integer example
    package Integer_Concatenation is new Concatenation(Integer);
    use type Integer_Concatenation.Element_Array;

    a1 : Integer_Concatenation.Element_Array(1..4) := (others => 1);
    a2 : Integer_Concatenation.Element_Array(1..5) := (others => 2);
    a3 : Integer_Concatenation.Element_Array := a1 & a2;
    a4 : Integer_Concatenation.Element_Array := 1 & 2 & 3 & 4 & 5;

    -- Custom record type
    type Something is null record;
    package Something_Concatenation is new Concatenation(Something);
    use type Something_Concatenation.Element_Array;

    a5 : Something_Concatenation.Element_Array(1..4) := (others => <>);
    a6 : Something_Concatenation.Element_Array(1..5) := (others => <>);
    a7 : Something_Concatenation.Element_Array := a5 & a6;

    s1,s2,s3,s4,s5 : Something;
    a8 : Something_Concatenation.Element_Array := s1 & s2 & s3 & s4 & s5;
begin
    -- Show the integer array results
    Put_Line("Hello, world!");
    for E of a3 loop
        Put(Integer'Image(E));
    end loop;
    New_Line;
    for E of a4 loop
        Put(Integer'Image(E));
    end loop;
    New_Line;
end Hello;

РЕДАКТИРОВАТЬ: Вы отредактировали свой вопрос с попыткой рекурсии. Вот альтернативный пример рекурсии, поэтому вы можете увидеть некоторые опции, которые у вас есть для синтаксиса и настройки. Мне пришлось ошарашить кучу вещей, так как ты мало что дал. Кроме того, ранее я предоставлял тип массива через шаблон, потому что ваш первоначальный вопрос задавался в контексте шаблонов. В реальной жизни я бы не создавал Generic только для типа массива (это можно сделать где угодно). Вместо этого у вас будет обобщение для вашего дерева, и все, что упомянуто в этом ответе, будет сделано в контексте этого обобщенного. Поскольку вы не предоставили никакого общего кода для скелета, я не хотел составлять целый пример. Я просто хотел показать вам, что объединение будет работать с типами, созданными с помощью шаблонов.

    function Get_all_nodes (Current_Node : in Tree) return 
        Something_Concatenation.Element_Array 
    is 
        use Something_Concatenation;
        use type Element_Array;
        Next_Node : Tree;
    begin
        if (Tree_is_null(Current_Node)) then
            return (1..0 => <>);  -- returns a null array
        else
            -- for the next call, get the node after this one
            -- or replace this with a call for the previous one
            -- or whatever your mechanism for getting a new
            -- node is.  You can also call Get_Next_Node
            -- in the return statement.  I Pulled it out
            -- here so you would see the step
            Next_Node := Get_Next_Node(Current_Node);

            -- here you need to figure out the order of nodes
            -- and how you want to traverse them.  This is
            -- just a basic (probably logically wrong) example
            -- to show you the syntax you were trying to emulate.
            -- you might also have to alter the order of these
            -- elements to get the array element order you want
            return Element_Array'(1 => Get_Value_of_Node(Current_Node))
                & Get_All_Nodes(Next_Node);

            -- Alternate with no "Next_Node" variable:
            -- return Element_Array'(1 => Get_Value_of_Node(Current_Node))
            --    & Get_All_Nodes(Get_Next_Node(Current_Node));
        end if;
    end Get_all_nodes;