0

DBに格納されているノードの階層があります。すべてを選択し、それらを配列に格納してから、それらを繰り返し処理して、メモリ内にネストされた配列を作成します。

入力は次のようになります。

[{名前：A}、{名前：B}、{名前：X、親：A}、{名前：Y、親：A}、{名前：C}]

出力は次のようになります。

[{名前：A、子：[{名前：X}、{名前：Y}]}、{B}、{C}]

入れ子の深さに制限はありません。

私が抱えている問題は、レコードの1つに無効な親参照がある場合、そのレコードを階層に配置できず、スクリプトが無限ループで終了し、親を見つけようとすることです。

いつ無限ループに陥ったかを知る方法があるに違いない。記録のために、ループ内でアイテムを挿入する親がないことに気付いたとき、親が行の下流に存在する可能性があるため、配列の最後にアイテムをプッシュします。

同じアイテムを何度もサイクリングしていることに気付くはずだと思いますか？

編集1-コードこれは重要なビットです：

    $cnt = count($array);
    do {
        $item = array_shift($array);
        if ($this->push($item)) {
            $cnt--;
        } else {
            array_push($array, $item);
        }
    } while ($cnt > 0);

（$ this-> push（）は親を見つけようとするメソッドであり、成功した場合は、その階層に$ itemを挿入します）

4

1 に答える 1

1

未処理のノードを格納するために、キュー (前から削除し、後ろに追加) のようなデータ構造を使用しているようです。ノードが出力データ構造に挿入されると、ノードはキューから削除されます。ノードを出力に追加できない場合 (「親」がまだ出力データ構造に移動されていないため)、再キューイングされます。「親」が存在しないノード (孤立ノード) がない限り、キューは最終的に空になります。

あなたのアルゴリズムは次のように見えると思います

 Do While not QueueEmpty()
    node = Dequeue() ' Remove from the front
    if not AddNodeToTree(node) then Queue(node) 'add to the back
 end

はノードを受け取りAddNodeToTree、それを出力に正常に追加して を返す関数ですTrue。False それ以外の場合は、ノードがリサイクルされて返されます。

あなたがしなければならない唯一のことは、キューの後ろにセンティナル ノードを追加し、それを介して 1 つの完全なサイクル中に少なくとも 1 つのノードがキューから消費されたことを示すフラグです。上記のアルゴリズムは次のようになります。

set NodeProcessed to False
Queue(SentinalNode) ' marker to identify cycle through queue
Do while not QueueEmpty()
  node = Dequeue()
  if isSentinalNode(node) then
     if NodeProcessed then 
        Queue(node)
        set NodeProcessed to False
     else
        ' Queue contains only orphans or is empty
     end
  end
  if AddNodeToTree(node) then
     set NodeProcessed to True
  else
     Queue(node)
  end
end

はSentinalNode、キューのループを検出するために使用するマーカーです。

出力データ構造には、木の「森」が含まれているように見えます。つまり、いくつかの異なるツリーが含まれています。特定のノードが 2 つ以上のツリーで共有される可能性がある場合、上記のアルゴリズムは適切に機能しません。ノードが「フォレスト」内の最大 1 つのツリーに表示される場合は、上記で問題ありません。

于 2010-06-04T17:46:50.027 に答える