我必须存储一个通用树的每个节点,它可以由任何类型组成。我必须在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;
所以我尝试了递归和迭代版本。 在迭代版本中,我有这样的东西,我已经使用了我的案例允许的堆栈
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容器。
再次感谢大家的帮助。 问候。