♥
Insider.NET 会議室
アルゴリズムパズル(リンクリスト)
私なりに考えてみました。
たどったノードのハッシュコードでも保存していって、同じコードが現れたらループしているとかでどうでしょう?
有限個数のノードで、マルチスレッド非対応、スタックメモリーは十分にあるなら。
(VB風の言語で)
Class Node
NextNode as Node '一方向リンク
'ノード数カウント関数
'循環していたら-1を返す
Public Function NodeCount(byval n as Long) as Long
static flgLoop as Boolean
If flgLoop=True then
n=-1
Else
flgLoop=true
If Node is not nothing then n=NextNode.NodeCount(n+1)
flgLoop=false
Endif
NodeCount=n
End Function
End Class
でも、どちらも問題文の条件を満たしてないような気もするので、やっぱ違いますねっ。
っていうか、バグもあるかも。
ツリービューの中にあるノードを別のノードの子に移動する時にも、この循環参照チェックの問題が出てきました。
自分の子ノードの子に自分自身を移動しようとしてしまったら大変ですからね。
この時はツリービューの各ノードのフルパスを使って簡単にチェックできました♪
関連記事
♥
諸悪の根源は物理的 さんの記事
アルゴリズムパズル(リンクリスト)
♥
is BUG ready ? さんの記事
循環参照した短方向リンクリストを O(n) で検出する
『というアルゴリズムに対して循環参照をしているリストを投げると、1パス目で n を求めようとして無限ループして終わる、ということだ。』
ってことで、いちおnを求める途中で循環参照を検知してみました。
というかこの方法で個数を求めるときはこういう措置を講じるべきかも。
Recent Comments