对于双向链表复制构造函数，不存在从 "const DListNode" 到 "DListNode *" 的合适转换函数

Question

我目前正在为双向链表 class 编写复制 constructor/assignment 运算符，但遇到了问题。

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 = &trailer; trailer.prev = &header; }
  DoublyLinkedList(const DoublyLinkedList& dll); // copy constructor
  ~DoublyLinkedList(); // destructor
  DoublyLinkedList& operator=(const DoublyLinkedList& 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 &trailer; }
  // return if the list is empty
  bool isEmpty() const { return header.next == &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
ostream& operator<<(ostream& out, const DoublyLinkedList& dll);

这是一个补充 header 文件，其中声明了节点和链表 classes。我注意到 DoublyLinkedList 的受保护 class 成员（header 和尾部）不是 DListNode 指针，而是实际的 DListNode 值；稍后会详细介绍。

我在 DoublyLinkedList.cpp

中的复制构造函数

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

我已经尝试通过多种不同的方式解决问题，包括编辑和不编辑 header 文件。我无法将 header 和 trailer 更改为 DListNode*，因为不允许更改它们，将 iter 更改为 non-pointer 将意味着我无法遍历链表；所以我现在陷入了僵局。因为我无法更改操作数的数据类型，所以我不确定如何修复错误。我认为这可能与 dll 作为常量引用传递有关，但即使摆弄它也无济于事。我已经看了几个小时了，但似乎无法让它发挥作用。提前感谢您的帮助！

Answer 1

这个列表看起来与通常的双向链表实现有点不同，但它可以工作。

从您显示的代码来看，两个 non-pointer 成员 header 和 trailer 似乎仅用于跟踪列表的两端，但是实际上不在列表中。上面的代码片段中的一些内容支持这一点：

一个空列表有 header 和 trailer 相互指向，没有为这两个节点设置值，它们之间也没有其他节点
getFirst()，根据上面的评论，它应该 return 指向第一个节点的指针，实际上 return 是 header 之后的节点，而不是 header本身
你有一个 getAfterLast() 函数，根据它的名字判断应该 return 列表中最后一个节点之后的标记，并且 returns trailer。

如果以上是正确的并且 header 和 trailer 实际上不是列表的一部分，那么您对复制构造函数的实现是错误的。它应该只从输入列表中复制实际值节点，不包括 header 和尾部。这意味着您从以 getFirst() 开始的节点复制节点值，并在到达 getAfterLast().

时停止

代码中类似这样的内容：

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

请注意，这也可以优雅地处理源列表为空的情况。如果 dll 为空，dll.getFirst() 实际上会 return 预告片，这也是 getAfterLast() return 的内容。所以 while 循环将不会被执行，列表将保持为空。

Answer 2

您的列表有两个单元格需要管理，即使它是空的。您可以采用不同的设计选择

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 DoublyLinkedList& dll)
{
  // Initialize the list
  header.next = &trailer; trailer.prev = &header;
  if (this != &dll) {
      DListNode* iter = dll.header.next;
      while (iter != &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 除了第一个空节点。

对于双向链表复制构造函数，不存在从 "const DListNode" 到 "DListNode *" 的合适转换函数

no suitable conversion function from "const DListNode" to "DListNode *" exists for doubly linked list copy constructor

c++

linked-list

copy-constructor

doubly-linked-list