5

こんにちは、親と子の間の双方向参照を保持するツリーを作成したいと考えています。しかし、最初のオブジェクトを作成したときに他のオブジェクトをまだ持っていないため、それを参照できないため、達成することは不可能に思えます。ここにいくつかのサンプルコードがあります。

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

この問題の別の例は、二重リンク リスト (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.

この種の構造を実装する方法はありますか。

4

5 に答える 5

3

いいえ、すべてのデータは不変であるため、Erlang で双方向リンク リストを直接実装する方法はありません。また、設定できたとしても（できません）、すべてのデータが不変であるため、何もできませんでした。ここで紹介する他の解決策は、二重にリンクされたリスト形式で動作するデータ構造を構築することで、これを回避する方法を示しています。しかし、そうではありません。

于 2012-12-17T00:34:22.640 に答える
3

次のようなレコードを定義できます

-record(my_node,{leftchild,rightchild,parent,value}.

ツリーをetsテーブルに保存し、

ets:new(my_tree,[named_table, ordered_set, public]),
...

そして、テーブルキーを「ポインタ」として使用してリンクを管理できます

Root = {make_ref(),#my_node{value=somevalue}}
ets:insert(my_tree,Root),
A_child = {make_ref(),#my_node{value=othervalue}},
addchild(Root,A_child,left),
...

addchild(Parent={Pref,Pval},Child={Cref,Cval},left) ->
    ets:insert(my_tree,{Pref,Pval#my_node{leftchild=Cref}}),
    ets:insert(my_tree,{Cref,Cval#my_node{parent=Pref}});
addchild(Parent={Pref,Pval},Child={Cref,Cval},right) ->
    ets:insert(my_tree,{Pref,Pval#my_node{rightchild=Cref}}),
    ets:insert(my_tree,{Cref,Cval#my_node{parent=Pref}}).

しかし、問題を解決するには、より多くの "erlang スタイル" のデータ表現を検討する必要があるかもしれません。ツリーの更新はアトミックではないため、複数のプロセスがツリーにアクセスしている場合、私が提案するソリューションにも問題があります。この場合、アトミック トランザクションをもたらす ets の上のデータベース レイヤーである mnesia を使用する必要があります。

于 2012-12-16T15:30:10.157 に答える
3

これがferdのzippersライブラリでどのように実装されているかを調べることができます

于 2012-12-16T07:52:54.200 に答える
3

「リンク」（ポインターなど）がある場合は、二重リンクリストを作成できます。erlang では、そのようなリンクはなく、実際の変数さえもありません。それらを変更することはできません。以下に循環リストの例をいくつか示しますが、これらは注意して実装する必要があります: Erlang で循環リストを定義できますか?

二重にリンクされたツリーが必要な理由を教えてください。たぶん、erlang にはもっと良い解決策があります。

編集: digraphを使用できます。ツリーは、A から B および B から A への頂点を持つ巡回グラフとして表すことができます。ルート ノード A と子 B および 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).

結果：["vertexB","vertexA","vertexC"]

于 2012-12-15T21:15:57.110 に答える
2

本当にそのようなことをする必要がある場合は、ノードを参照するためにある種のIDを使用できます。例えば

A = #node{name="node-A",
      children=["node-B"],
      parent=nil},
B = #node{name="node-B",
      children=[],
      parent="node-A"},
NodeDict = dict:from_list([{A#node.name, A}, {B#node.name, B}]),
Tree = #tree{root=A#node.name, nodes=NodeDict}.
于 2012-12-16T07:47:00.893 に答える