C++将数据插入(并将其移入)数组
我试图将数据插入B树的叶节点(数组)。这里是我到目前为止的代码:C++将数据插入(并将其移入)数组
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()
行前值[POS] = NUM,我认为需要编写一些代码,而不是转移覆盖它的现有数据。我试图使用memmove,但有一个问题。其第三个参数是要复制的字节数。如果我在64位机器上移动一个int,这是否意味着我会在这里放置一个“4”?如果我对这个完全错误的任何帮助将不胜感激。谢谢
最简单的方法(也许是最有效的)将是使用标准库预定义结构之一来实现“值”。我建议list或vector。这是因为列表和矢量都有一个插入函数可以帮你。我特别建议vector类是因为它具有与数组相同类型的接口。但是,如果您想专门针对此操作的速度进行优化,那么我会建议列表类,因为它实施的方式。
如果你宁可给它的硬盘的方式,那么在这里去... 首先,你需要确保你有空间的工作,你可以动态地分配:
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处的元素的时间。
另外,这段代码是在写的时候...使用它时要小心。在最后一段代码中可能会出现一个奇怪的边缘情况。
干杯! Ned
感谢您的彻底!真的很感激它 – sbru 2013-04-28 04:30:05
如果数据是[std :: vector ](http://en.cppreference.com/w/cpp/container/vector),[std :: deque ](http: //en.cppreference.com/w/cpp/container/deque)或[std :: list ](http://en.cppreference.com/w/cpp/container/list),只需使用迭代器找到正确的插槽,然后使用[insert()](http://en.cppreference.com/w/cpp/container/vector/insert)。复印等,都将为您照顾。 – WhozCraig 2013-04-28 04:08:54
数据位于数组中。 – sbru 2013-04-28 04:10:55