1

B ツリーのリーフ ノード (配列) にデータを挿入しようとしています。これが私がこれまでに持っているコードです:

void LeafNode::insertCorrectPosLeaf(int num)
{
  for (int pos=count; pos>=0; pos--)   // goes through values in leaf node
  {
    if (num < values[pos-1])    // if inserting num < previous value in leaf node
    {continue;}                 // conitnue searching for correct place
    else                        // if inserting num >= previous value in leaf node
    {
      values[pos] = num;        // inserts in position
      break;
    }               
  }
  count++;
} // insertCorrectPos()

values[pos] = num の行の前に、既存のデータを上書きするのではなく、シフトするコードを書く必要があると思います。memmove を使用しようとしていますが、それについて質問があります。3 番目のパラメーターは、コピーするバイト数です。64 ビット マシンで 1 つの int を移動する場合、ここに "4" を入れるということですか? 私がこれについて完全に間違っている場合は、どんな助けでも大歓迎です。ありがとう

4

1 に答える 1

2

最も簡単な (そしておそらく最も効率的な) 方法は、標準ライブラリの定義済み構造の 1 つを使用して「値」を実装することです。listまたはvectorのいずれかをお勧めします。これは、リストとベクターの両方に挿入機能があるためです。特にベクトルクラスは、配列と同じ種類のインターフェイスを持っているためだと思います。ただし、特にこのアクションの速度を最適化したい場合は、実装方法から list クラスをお勧めします。

難しい方法を希望する場合は、次のようになります...まず、作業するためのスペースがあることを確認する必要があります。動的に割り当てることができます。

int *values = new int[size];

または静的に

int values[MAX_SIZE];

静的に割り当てる場合は、MAX_SIZE が絶対に超えない巨大な値であることを確認する必要があります。さらに、要素を追加するたびに、割り当てられたスペースの量に対して配列の実際のサイズを確認する必要があります。

if (size < MAX_SIZE-1)
{
    // add an element
    size++;
}

動的に割り当てる場合は、要素を追加するたびに配列全体を再割り当てする必要があります。

int *temp = new int[size+1];
for (int i = 0; i < size; i++)
    temp[i] = values[i];
delete [] values;
values = temp;
temp = NULL;

// add the element
size++;

新しい値を挿入するときは、すべての値をシフトする必要があります。

int temp = 0;
for (i = 0; i < size+1; i++)
{
    if (values[i] > num || i == size)
    {
        temp = values[i];
        values[i] = num;
        num = temp;
    }
}

これはまったく最適化されていないことに注意してください。真に魔法のような実装では、必要以上のスペースを動的に割り当て、スペースが不足したときに配列をブロック単位で拡張することにより、2 つの割り当て戦略を組み合わせることができます。これはまさにベクター実装が行うことです。

リストの実装では、構造上、値を挿入するのに O(1) 時間かかるリンク リストを使用します。ただし、スペースの非効率性ははるかに低く、位置 n の要素にアクセスするのに O(n) 時間かかります。

また、このコードはオンザフライで書かれています...使用するときは注意してください。最後のコード セグメントで見落としている奇妙なエッジ ケースがある可能性があります。

乾杯！ネッド

于 2013-04-28T04:25:43.400 に答える