2

類似した番号付けを作成する非再帰的な方法を作成したい -

1
1.1
1.2
1.2.1
1.3
2
2.1  etc etc (these items can be infinitely deep)

私が持っている唯一の識別情報は、2 桁の ID です。最初の ID はアイテムを識別する ID で、2 番目の ID はそのアイテムが何に属しているかを識別し、0 は常にドキュメント ルートです。

例えば：

123,0
456,123
789,123
777, 789
999, 123
888,0
444,888

-- に翻訳されます。

1
1.1
1.2
1.2.1
1.3
2
2.1

データはインラインで読み取られます。その先にあるものだけで、その後に何があるかはわかりません。これは簡単なはずですが、何らかの理由で効率的な解決策を思い付くのに苦労しています。注: アイテムは常に順番に届きます。たとえば、アイテム 1.1 を取得する前にアイテム 1.2 を取得することはありません。

4

2 に答える 2

0

アイテムが正しい順序で配置されている場合、スタックは問題ありません。

public class Item {
    private int id;
    private int parentId;

    public Item(int id, int parentId) {
        this.id = id;
        this.parentId = parentId;
    }

    public int getId() { return id; }
    public int getParentId() { return parentId; }
}

public class NumberedItem {
    private Item item;
    private int childCount;
    private String number;

    public NumberedItem(Item item, String number) {
        this.item = item;
        this.childCount = 0;
        this.number = number;
    }

    public Item getItem() { return item; }
    public String getNumber() { return number; }

    /* package */ int incrementChildCount() {
        return ++childCount;
    }
}

public NumberedItemIterator implements Iterable<NumberedItem> {
    private Iterator<Item> items;
    private Stack<NumberedItem> numberStack;

    public NumberedItemIterator(Iterable<Item> itemsIterable) {
        items = itemsIterable.iterator();
        numberStack = new Stack<NumberedItem>();
        numberStack.push(new NumberedItem(null, null));
    }

    public boolean hasNext() {
        return items.hasNext();
    }

    public NumberedItem next() {
        Item current = items.next();
        int parentId = current.getParentId();

        NumberedItem parent = null;
        while (!numberStack.empty()) {
            NumberedItem candidate = numberStack.peek();
            if (candidate.getItem().getId() == parentId) {
                parent = candidate;
                break;
            }
            numberStack.pop();
        }

        if (parent == null) throw new RuntimeException("Inconsistent ordering");

        String number = Integer.toString(parent.incrementChildCount());
        if (parent.getNumber() != null) {
            number = parent.getNumber() + "." + number;
        }

        NumberedItem result = new NumberedItem(current, number);

        numberStack.push(result);

        return result;
    }

    public void remove() {
        throw new UnsupportedOperationException();
    }
}
于 2012-10-24T07:35:38.460 に答える
0

ここでの私のアルゴリズムは次のようになります。

  • 各ペアを読み取るときに、の子としてツリー(x, y)に挿入しますxy
  • 印刷するには、ツリーに対して深さ優先の再帰を実行します。再帰なしでこれを行いたい場合は、代わりにスタック実装を使用できます。

もちろん、これは非常に一般的なスケッチです。特定の実装に関する限り、多くの選択肢があります。

于 2012-10-23T19:51:32.507 に答える