Пробелы в копировании Пропустить Список

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 не кажется правильным, любой может получить некоторые предложения, как сделать эту работу?

Answer 1

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

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; 
     } 
    } 
}