0

私はProject Euler Problem 18に取り組んでいました(私は問題を解決しました。ごまかしているわけではありません。「証明」はここにあります)、パスカルの三角形のように見えるデータ構造を表現する方法が必要であることに気付きましたが、値は異なります。 . 二分木に非常によく似ていますが、非常に重要な違いがあります。ノードの子は、ノードの子だけではありません。したがって、最初の 3 行は次のようになります。

    75
   /  \
  95  64
 /  \ / \
17  47  82

47 には 2 つの親があることに注意してください。

これをリンクされた構造や 2 次元配列として表現するのは非常に簡単ですが、もっと洗練された方法があることを願っています。私は二分木が大好きです。主に、単一のメモリ チャンクを割り当て、それを配列として扱い、いくつかの算術演算または整数除算を使用して子と親の間を移動する方法です。このデータ構造に対して同じことを行う方法はありますか?

私の最善の解決策は、2 次元配列を使用することでした (子と親を見つけるのは非常に簡単です)。私はこの実装が嫌いです (少なくとも私が行った方法では)malloc構造がどれだけ大きくなるかを事前に知っていたにもかかわらず、すべての行を呼び出したからです。

私の質問はこれと非常によく似ていますが、受け入れられた回答には満足できませんでした。コメントは私が求める解決策をほのめかしていますが、説明はありません。

編集:明確にするために、配列に (1 から始まる) バイナリ ツリーが順番に詰め込まれるのと同じ方法で、1 次元配列にインデックスを付ける方法を探しています。インデックス 2 * iおよび 2 * i + 1 にあります。また、親を見つけることができるかどうかについてもあまり心配していないので、奇妙な 2 つの親についてはあまり心配しないでください。

4

2 に答える 2

1

はい、三角形のデータ構造を 1 次元配列に格納することは可能です (Java の例)。

class Triangle<T> {
  private T[] triangle;

  public Triangle(T[] array, int rows) {
    if (array.length != triangleNumber(rows)) {
      throw new IllegalArgumentException("Array wrong size");
    }
    triangle = array;
  }

  public T get(int row, int col) {
    return triangle[index(row, col)];
  }

  public void set(int row, int col, T val) {
    triangle[index(row, col)] = val; 
  }

  private int triangleNumber(int rows) {
    return rows * (rows + 1) / 2;
  }

  private int index(int row, int col) {
    if (row < 0 || col < 0 || col > row) {
      throw new IndexOutOfBoundsException("Trying to access outside of triangle");
    }
    return triangleNumber(row) + col;
  }
}

コンストラクターに渡される配列は、三角形の行を 1 つずつ配列に連結することによって形成されます: [t(0,0), t(1,0), t(1,1), t(2, 0), t(2,1), t(2,2), ... , t(rows-1, rows-1)]、ここで、t(R, C) は三角形の行 R と三角形の三角形のセルです。 C列。

任意のセル (行、列) の場合:

  • 左の子は行+1、列になります
  • 右の子は行 + 1、列 + 1 になります
  • 左の親はrow-1、col-1になります
  • 右の親はrow-1、colになります

2 つの親と 2 つの子は、三角形の外側にあるため、すべてのセルに存在しません。index メソッドの例外チェックを参照してください。

于 2015-09-29T18:43:10.297 に答える
0

はい、あります。2次元配列のアイデアから始めますが、行の長さは不規則です。したがって、各要素は2次元インデックス（r、c）でインデックス付けされます。（1,1）（2,1）（2,2）（3,1）（3,2）（3,3）（4,1）（4,2）（4,3）（4,4）

関係は規則的であるため、次の位置を表すことができます。
ノード（r、c）の場合、子は（r + 1、min（1、c））、（r + 1、max（c + 1、r）です。 ））と彼の親は：（r-1、min（1、c-1））、（r-1、max（c、r））

于 2012-11-05T14:40:59.437 に答える