Проблемы с копированием списка пропусков

Question

Проблемы с копированием списка пропусков

Я столкнулся с проблемой при попытке написать функцию копирования для моего списка пропуска. Поскольку большая часть занятий уже выполнена, я бы предпочел не менять свой дизайн.

Каждый узел имеет два указателя, один на следующий узел на том же уровне, другой на эквивалентный узел на уровень ниже.
В моем классе есть вектор, в котором хранятся указатели на головной узел каждого уровня.

struct Node
{
int key;
Node* next;
Node* below;
}
vector<Node*> levels;

Моя личная функция копирования:

void copyAll(const SkipList& s)
{
for(unsigned int i = 0; i < s.level.size(); ++i)
{
Node* curr = s.level[i];
Node* copy = new Node(curr->key, nullptr, curr->below);
level.push_back(copy);
curr = curr->next;
while(curr != nullptr)
{
copy->next = new Node(curr->key, nullptr, curr->below);
copy = copy->next;
curr = curr->next;
}
}
}

Функция прекрасно работает по горизонтали с каждым отдельным узлом, скопированным и связанным друг с другом, но она не устанавливает никаких ссылок по вертикали.
curr->below не кажется правильным, кто-нибудь может получить некоторые предложения, как сделать эту работу?

0

c++copy-constructor skip-lists

Решение

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

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

Источник

Accepted Answer

Вместо того, чтобы идти вниз от верхних уровней, вы можете сделать это снизу вверх. Таким образом, всякий раз, когда вы собираетесь создать копию узла, у вас уже есть копия соответствующего ему «ниже»:

void copyAll(const SkipList& s)
{
level.resize(s.level.size());
for(unsigned int i = s.level.size(); i > 0; --i)
{
Node* curr = s.level[i-1]; // Note the intended change in the range of i
Node* curBelowCopy = // If not the bottom, ptr to start of the row below
curr->below ? level[i] : nullptr;

Node* copy = new Node(curr->key, nullptr, curBelowCopy);
level[i-1] = copy;
curr = curr->next;
while(curr != nullptr)
{
if (curBelowCopy) {
// Not the last level: advance curBelowCopy to the
// corresponding copy of cur->below
while (curBelowCopy->key != curr->below->key)
curBelowCopy = curBelowCopy->next;
}

copy->next = new Node(curr->key, nullptr, curBelowCopy);
copy = copy->next;
curr = curr->next;
}
}
}

0