Блог

В настоящее время я работаю над написанием конструктора копирования / оператора присваивания для класса двусвязного списка и у меня возникают проблемы.

DoublyLinkedList.h

 #include <cstdlib>
#include <iostream>
using namespace std;
class DoublyLinkedList; // class declaration

// list node
class DListNode {
private: int obj;
  DListNode *prev, *next;
  friend class DoublyLinkedList;
public:
  DListNode(int e=0, DListNode *p = NULL, DListNode *n = NULL)
    : obj(e), prev(p), next(n) {}
  int getElem() const { return obj; }
  DListNode * getNext() const { return next; }
  DListNode * getPrev() const { return prev; }
};

// doubly linked list
class DoublyLinkedList {
protected: DListNode header, trailer;
public:
  DoublyLinkedList() : header(0), trailer(0) // constructor
  { header.next = amp;trailer; trailer.prev = amp;header; }
  DoublyLinkedList(const DoublyLinkedListamp; dll); // copy constructor
  ~DoublyLinkedList(); // destructor
  DoublyLinkedListamp; operator=(const DoublyLinkedListamp; dll); // assignment operator
  // return the pointer to the first node
  DListNode *getFirst() const { return header.next; } 
  // return the pointer to the trailer
  const DListNode *getAfterLast() const { return amp;trailer; }
  // return if the list is empty
  bool isEmpty() const { return header.next == amp;trailer; }
  int first() const; // return the first object
  int last() const; // return the last object
  void insertFirst(int newobj); // insert to the first of the list
  int removeFirst(); // remove the first node
  void insertLast(int newobj); // insert to the last of the list
  int removeLast(); // remove the last node
};
// output operator
ostreamamp; operator<<(ostreamamp; out, const DoublyLinkedListamp; dll);
  

Это был дополнительный заголовочный файл, в котором объявлены классы node и linked list. Я заметил, что защищенные члены класса DoublyLinkedList (заголовок и трейлер) являются не указателями DListNode, а фактическими значениями DListNode; подробнее об этом чуть позже.

Мой конструктор копирования в DoublyLinkedList.cpp

 DoublyLinkedList::DoublyLinkedList(const DoublyLinkedListamp; dll)
{
  // Initialize the list
  header.next = amp;trailer; trailer.prev = amp;header;
  DListNode* iter = dll.header; // PROBLEM LINE
  if (this != amp;dll) {
      while (iter != nullptr) {
          insertLast(iter->obj);
          iter = iter->next;
      }
  }
}
  

Я пытался решить проблему множеством разных способов, с редактированием файла заголовка и без него. Я не могу изменить заголовок и трейлер на DListNode *, поскольку их нельзя изменять, а изменение iter на не указатель означало бы, что я не могу пройти связанный список; так что я сейчас в тупике. Поскольку я не могу изменить типы данных операндов, я не уверен, что делать, чтобы исправить ошибку. Я подумал, что это может иметь какое-то отношение к dll, передаваемой как постоянная ссылка, но даже возня с этим мало что дала. Я смотрел на это пару часов и, похоже, просто не могу заставить его работать. Заранее спасибо за любую помощь!

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

 class DoublyLinkedList {
protected:
  DListNode *header;
public:
  DoublyLinkedList() : header(nullptr) {} // constructor
  ...
  bool isEmpty() const { return header == nullptr; }
  void insertLast(int val)
     {  if (header == nullptr) {
            header = new DListNode(val);
            header->next = header->prev = header;
        }
        else {
            header->prev->next = new DListNode(val, header->prev, header);
            header->prev = header->prev->next;
        }
     }
};
  

Тем не менее, с вашим выбором дизайна (одна пустая ячейка в начале и одна пустая ячейка в конце), вы можете определить свой конструктор копирования как

 DoublyLinkedList::DoublyLinkedList(const DoublyLinkedListamp; dll)
{
  // Initialize the list
  header.next = amp;trailer; trailer.prev = amp;header;
  if (this != amp;dll) {
      DListNode* iter = dll.header.next;
      while (iter != amp;dll.trailer) { // no insertion if dll is empty
          insertLast(iter->obj);
          iter = iter->next;
      }
  }
}
  

Вы должны рисовать свою структуру данных до и после каждой операции, чтобы быть уверенным в том, как работает ваш алгоритм.

Вы также можете реализовать инвариант (метод bool isValid() const ) для проверки цепочки между ячейками: cell->next->prev должно быть cell , кроме последнего пустого узла, и cell->prev->next должно быть cell , кроме первого пустого узла.

Этот список выглядит немного иначе, чем обычные реализации двусвязного списка, но он может работать.

Из кода, который вы показали, похоже, что два элемента, не являющиеся указателями, header и trailer , используются только для отслеживания двух концов списка, но на самом деле не являются частью списка. Это подтверждается несколькими моментами из приведенного выше фрагмента кода:

• пустой список имеет header и trailer , указывающие друг на друга, без значений, установленных для этих двух узлов, и никаких других узлов между ними
• getFirst() , который, согласно приведенному выше комментарию, должен возвращать указатель на первый узел, фактически возвращает узел после header , а не header сам
• у вас есть getAfterLast() функция, которая, судя по ее имени, должна возвращать маркер после последнего узла в списке и которая возвращает trailer .

Если приведенное выше верно header и trailer на самом деле не является частью списка, то ваша реализация конструктора копирования неверна. Он должен копировать только узлы фактического значения из входного списка, исключая заголовок и трейлер. Это означает, что вы копируете значения узлов из узлов, начинающихся с getFirst() и останавливающихся при достижении getAfterLast() .

Что-то вроде этого в коде:

 if (this != amp;dll) {
    const DListNode* iter = dll.getFirst();
    while (iter != dll.getAfterLast()) {
        insertLast(iter->obj);
        iter = iter->next;
    }
}
  

Обратите внимание, что это также любезно обрабатывает случай, когда исходный список пуст. Если dll пусто, dll.getFirst() фактически вернет трейлер, который также getAfterLast() возвращает. Таким while образом, цикл не будет выполнен, список останется пустым.