Глубокое копирование и деконструкция дозорного связанного списка с использованием узлов
В настоящее время я делаю связанную программу List, используя Nodes (не то, что я знаю о каком-либо другом способе), и я столкнулся с проблемой создания глубокой копии и избавления от всех моих Узлов и Sentinels с помощью моего ~ List (). Удаление узлов не является проблемой, но часовые так как первому не присвоено значение индекса.
List::~List()
{
for(size_t i=0; i<size; i++)
{
_setCurrentIndex(i);
if(current && curent->next == NULL)
{
Node *temp = current->next;
delete temp;
delete current;
}
else
{
Node *old = current;
current = current->next;
delete old;
}
}
}
List::List(const List & orig)
{
for(size_t i=0; i<size; i++)
{
if(i==0)
{
Node *copyFront = new Node; //the first sentinel
copyFront->data = orig.front->data; //front is defined in private in list.h
copyFront->prev = NULL; // it is defined as a Node (same for rear)
}
else if(0<=i && i<size) //put in i<size b/c 0<=i would always be true
{
_setCurrentIndex(i) //sets what current is and currentIndex which pts to diff Nodes
Node *copy = new Node;
copy->data = current->data;
copy->next = current->next;
current = current->next;
}
else if(i+1 == size)
{
Node *copyRear = new Node; //making the last sentinel, but it has to be
copyRear->data = orig.rear->data; //after data Node
copyRear->next = NULL;
}
}
}
Я ищу советы и комментарии к этому коду о том, как действовать дальше или что изменить, если что-то ужасно неправильно!
Решение
Связанные списки — это шаблоны, позволяющие использовать в них переменные любого типа. По моему честному мнению, вам лучше всего использовать std::list который требует #include <list> заголовочный файл
Конечно, если вам действительно нужен опыт написания класса связанного списка, то следующий код делает глубокую копию списка:
List::List( const List& other) {
if( other.head_ != nullptr) {
head_ = new Node( other.head_->item_); // copy first node
assert( head_ != nullptr); // ensure that the memory was allocated correctly
// copy the rest of the list
Node* pnew = head_;
// loop through the list until you reach the end (i.e. a node that's nullptr)
for( Node* porig( other.head_->next_); porig != nullptr; porig = porig->next_) {
// assign the next node in the destination list to the next node in the paramter's list
pnew->next_ = new Node( porig->item_);
assert( pnew->next_ != nullptr); // ensure that the memory was allocated correctly
pnew = pnew->next_; // move onto the newly created node in the destination list
}
}
else
// if the parameter is empty then the destination list will be empty as well
head_ = nullptr;
}
Что касается деструктора, вам просто нужно пройти по списку, удаляя узлы по ходу:
List::~List() {
while( head_ != nullptr) { // keep looping until the list gets to the end
// make a second pointer to the node you are about to delete (so you don't lose track of it)
Node* pn( head_);
// move the head_ onto the next node essentially "removing" the first node from your list
head_ = head_->next_;
// delete the node that you've just "removed" from your list
delete pn;
}
}
Я пытался прояснить комментарии, которые могут быть неясными.
Другие решения
Других решений пока нет …