在erlang中双重链接的数据结构 [英] Doubly linked data structures in erlang

问题描述

我想制作一个树，保持父和子之间的双向引用。但是，由于当我创建第一个对象时，我没有其他对象，因此不能引用它，这似乎是不可能的。这里是一些示例代码。

  -record（node，{name，children，root}）。 
 
 main（） - > 
 A = #node {name =node-A，
 children = [B]，％变量B为未绑定
 root = nil}，
 B = #node { name =node-B，
 children = []，
 root = A}，
 Tree = A. 
  

这个问题的另一个例子是实现双向链接列表（http://en.wikipedia.org/wiki/Doubly_linked_list）

  -record（node，{prev，name，next}）。 
 
 main（） - > 
 A = #node {prev = nil，
 name =node-A，
 next = B}，％变量B未绑定
 B = #node {prev = A，
 name =node-B，
 next = nil}，
 LinkedList = A. 
  

有没有办法实现这种结构。

解决方案

链接列表（如指针）。在erlang你没有这样的链接，你甚至没有真正的变量，你不能改变它们。以下是循环列表的一些示例，但应谨慎实施：可以循环列表在Erlang中定义？

也许你可以告诉我们为什么你需要双重链接的树？也许Erlang有更好的解决方案。

编辑：您可以使用有向图。您的树可以表示为循环图，其中有从A到B和B到A的顶点。具有根节点A和子节点B和C的树的示例：

 主（） - > 
 Tree =图：new（[cyclic]），
 A =有向图：add_vertex（Tree，vertexA），
 B =有向图：add_vertex（Tree，vertexB），
 C =有向图：add_vertex（Tree，vertexC），
 digraph：add_edge（Tree，A，B），
 digraph：add_edge（Tree，B，A），
图：add_edge（Tree，A，C），
 digraph：add_edge（Tree，C，A），
 digraph：get_path（Tree，B，C） 
  

结果： [vertexB，vertexA，vertexC

Hi I want to make a tree that keeps two-way references between parent and children. But it seems impossible to achive since when I create first object I do not have the other one yet therefore cannot have a reference to it. Here is some sample code.

-record(node,{name,children,root}).

main()->
    A = #node{name="node-A",
          children=[B], %variable B is  unbound
          root=nil},
    B = #node{name="node-B",
          children=[],
          root=A},
    Tree = A.

Another example to this problem would be implementing a doubly linked list (http://en.wikipedia.org/wiki/Doubly_linked_list)

-record(node,{prev,name,next}).

main()->
    A = #node{prev=nil,
          name="node-A",
          next=B}, % variable B is unbound
    B = #node{prev=A,
          name="node-B",
          next=nil},
    LinkedList = A.

Is there a way to implement this kind of structure.

解决方案

You can make doubly linked lists when you have "links" (like pointers). In erlang you don't have such links and you don't have even real variables, you can't change them. Here are some examples for circular lists, but they should be implemented with caution: Can Circular Lists be defined in Erlang?

Maybe you could tell us why you need doubly linked tree? Maybe there is a better solution in erlang.

Edit: You could use digraph. Your tree can be represented as cyclic graph where you have vertices from A to B and from B to A. Example of a tree with root node A and children B and C:

main()->
    Tree = digraph:new([cyclic]),
    A = digraph:add_vertex(Tree,"vertexA"),
    B = digraph:add_vertex(Tree,"vertexB"),
    C = digraph:add_vertex(Tree,"vertexC"),
    digraph:add_edge(Tree, A, B),
    digraph:add_edge(Tree, B, A),
    digraph:add_edge(Tree, A, C),
    digraph:add_edge(Tree, C, A),
    digraph:get_path(Tree, B, C).

Result: ["vertexB","vertexA","vertexC"]

这篇关于在erlang中双重链接的数据结构的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！