1

わかりました、この質問はあなたの側で少し読む必要があります. これを短くシンプルにしようと思います。

各ノードに関連付けられたデータを持つツリー (バイナリ ツリーではなく、単なるツリー) があります (バイナリ データ、それらが何であるかわからない、そしてそれらがどれくらいの長さかわかりません)

ツリーの各ノードには、ツリーでの表示方法とは関係のないインデックスもあります。短くするために、次のようになります。

ここに画像の説明を入力

インデックス番号は、ユーザーがナビゲートするツリーの順序を表し、複製することはできません。

この構造をディスク上のファイルに保存する必要があります。

私の問題は、ツリーのロードと作業をできるだけ簡単にする柔軟なディスク格納フォーマットをどのように設計するかです。

実際、ユーザーは許可されるべきです

  • 要素に子ブロックを作成します (これは簡単なはずです。インデックスの重複を避けるように注意してファイルにデータを追加するだけで十分です)。
  • 子を削除します (ユーザーに「このノードのすべての子も削除しますか? または、その子を親に追加する必要がありますか?」というプロンプトを表示する必要があります)。これに関するトリッキーな部分は、ノードを削除するとインデックスも解放される可能性があり、別のノードを追加するときにユーザーにそのインデックスを再度使用させることはできません (または、ユーザーが設定した順序が台無しになる可能性があります)。更新する必要があります。木全体！
  • インデックスを別のものと交換する

私は C++ と Qt を使用していますが、今ではこのような多くのフィールドを持つ多くの構造を考えています

struct dataToBeStoredInTheFile
{
    long data_size;
    byte *data; //... the data here

    int index;
    int number_of_children;
    int *children_indices; // ... array of integers
}

これには、各ノードをそれぞれのインデックスで識別するという利点がありますが、2 つのノード間でインデックスを交換したり、ノードを削除して他のノードのインデックスを更新したりする場合は、すべてのノードとそのすべての「children_indices」配列をトラバースする必要があるため、非常に遅くなります。

各ノードを識別するために「ハッシュ」のようなものを使用すると、より柔軟になりますか? ツリー内の位置用とユーザーのインデックス用の 2 つのインデックスを使用する必要がありますか? データを保存するためのより良いアイデアがあれば、大歓迎です

4

3 に答える 3

2

boost.serializationのようなものを使用することをお勧めします。そうすれば、ディスクに保存するときに実際の形式を気にする必要がなくなり、効果的なメモリ内ソリューションに集中できます。

編集：あなたの質問を再読すると、Qtを使用しているようです。その場合、使用できる独自のシリアル化フレームワークが必要です。

于 2012-07-24T10:48:05.680 に答える
1

  1. 単一のファイルである必要がない場合は、ファイル/ディレクトリ構造を使用してツリーを表すことができます。ここで、各ノードは単一のファイルに対応します (内部ノードごとにディレクトリがあります)。最も効率的ではないかもしれませんが、信じられないほど簡単に実行できます。

  2. 繰り返しますが、ファイル数にある程度の柔軟性がある場合 (ただし、上記ほどではありません)、ツリー構造用に 1 つのファイルを作成し (各ノードが固定サイズになり、操作が簡単になるように)、別のファイルを保存用に作成できます。ノードの内容。「コンテンツ ファイル」の処理を高速化するには、ガベージ コレクション システムのように扱うことができます。最後に新しいノードや更新されたノードを追加し続け、古いノードを使用されていないものとしてマークし、定期的にクリアします。

  3. いっそのこと、@JoachimPileborgのアドバイスに従ってください:)

于 2012-07-24T10:49:53.010 に答える
1

ユーザー指定のインデックスを使用してノードを識別する必要はないと思います。これは、ツリーを格納する方法とは直接関係がなく、インデックスでノードにアクセスする効率的な方法がないためです。ノードごとに 2 つのインデックスを保持する必要があります。1 つはユーザー指定のもので、もう 1 つは実装に依存します。または、ユーザー指定のインデックスを実装に使用しているインデックスにマッピングする配列を維持します。

また、別の構造を使用してツリーを格納した方がよい場合もあります。ノードごとに、次を保存します。

  • 親のインデックス
  • 一番左の息子のインデックス
  • 左の兄弟のインデックス
  • 右の兄弟のインデックス

このように、ノードを追加して 2 つのノードを交換することは、単純なポインター操作で実行できます (明示的なポインターという意味ではありません。いずれにせよ、インデックスはポインターのようなものです)。すべての子にアクセスする必要があるため、ノードの削除はおそらく遅くなります。

おまけとして、この構造を使用すると、すべてのノードのサイズが固定されます (提案しているリンク リストとは異なります)。これは、ファイルをシークすることでノードに直接アクセスできることを意味します。

また、ユーザーが新しいノードに使用できる最小のインデックスを維持する必要があります。たとえば、最大のインデックスが 5 であり、それが削除された場合でも、次の空きインデックスとして 6 を保持するため、5 を再利用することはできません。

于 2012-07-24T11:45:04.827 に答える