配列を使ったグラフの実装

Question

私はグラフを生成するツールを実装したいと思います。そのグラフのメモリは "Tape"というデータ構造に割り当てられます。テープは、「ノードID」を保持する要素の配列として考えることができ、その「親ノード」とその「子ノード」へのリンクです。

私が探しているのは、新しいノードを追加するときに空のスロットをすばやく識別できるように、アレイ内の使用可能なスロットを識別することが安価な方法です。

ダイナミックアレイを使用してテープを実装した場合はどうなりますか？配列のサイズを変更する必要がある状況では、テープ全体を新しく割り当てられた配列にコピーすることはできませんか？

誰でもここにご意見がありますか？

Answer 1

私はあなたに事前に大きな「テープ」を割り当てると仮定します。何千ものノード。

• まずストアテープ上の最後に使用されたエントリ：

  あなたは2つの概念を組み合わせる必要があります。次に新しいエントリが必要なときは、最後に使用したエントリの直後のエントリを選択するだけです。

• 2番目はフリーリストです。次の空きエントリへのポインタとして、テープエントリの最初の4バイト（または64ビットの8バイト）を使用します。テープの先頭は、最初の空きエントリを指す必要があります。

テープ上のエントリが解放されるたびに、空きリストに追加します。

新しいエントリがテープに必要とされるたびに：フリーリスト内の要素があるかどうかを

• チェック。最初のエントリを取り出して空きリストから削除する場合
• 空きリストが空の場合は、最後に使用したエントリを使用し、直後のエントリを使用します。

また、テープの合計割り当てサイズを保持し、最後に使用されたエントリがテープの最後に達した場合に再割り当てする再配置スキームと組み合わせることもできます。