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，但对此有疑问。它的第三个参数是要复制的字节数。如果我在 64 位机器上移动单个 int，这是否意味着我会在这里放一个“4”？如果我完全错误地解决这个问题，任何帮助将不胜感激。谢谢

4

1 回答 1

2

最简单的方法（也可能是最有效的）是使用标准库中的一种预定义结构来实现“值”。我建议list或vector。这是因为 list 和 vector 都有一个 insert 函数可以为你做这件事。我建议向量类具体是因为它具有与数组相同的接口。但是，如果您想专门针对此操作的速度进行优化，那么我会建议使用 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;
    }
}

请记住，这根本没有优化。一个真正神奇的实现将通过动态分配比您需要的更多空间来结合这两种分配策略，然后在空间用完时按块增长数组。这正是矢量实现所做的。

列表实现使用一个链表，由于它的结构，它有 O(1) 时间来插入一个值。但是，它的空间效率要低得多，并且有 O(n) 时间来访问位置 n 处的元素。

此外，此代码是即时编写的……使用时要小心。我在最后一个代码段中可能缺少一个奇怪的边缘情况。

干杯! 内德

于 2013-04-28T04:25:43.400 回答