C ++ вставка (и смещение) данных в массив

Question

C ++ вставка (и смещение) данных в массив

Я пытаюсь вставить данные в листовой узел (массив) 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()

Прежде чем значения строки [pos] = num, я думаю, нужно написать некоторый код, который сдвигает существующие данные, а не перезаписывает их. Я пытаюсь использовать memmove, но у меня есть вопрос по этому поводу. Третий параметр — это количество байтов для копирования. Если я перемещаю одно целое на 64-битной машине, значит ли это, что я бы поставил здесь «4»? Если я пойду по этому поводу совершенно неправильно, любая помощь будет принята с благодарностью. Спасибо

1

arrays b-tree c++

Решение

Другие решения

Других решений пока нет …

Источник

Accepted Answer

Самый простой способ (и, вероятно, самый эффективный) — использовать одну из предопределенных структур стандартных библиотек для реализации «значений». Я предлагаю либо список или же вектор. Это потому, что и список, и вектор имеют функцию вставки, которая делает это за вас. Я полагаю, что векторный класс именно потому, что он имеет тот же интерфейс, что и массив. Однако, если вы хотите оптимизировать скорость этого действия, я бы предложил класс списка из-за способа его реализации.

Если ты предпочитаешь трудный путь, то здесь …
Во-первых, вам нужно убедиться, что у вас есть место для работы. Вы можете выделить динамически:

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

1