從「常量DListNode」沒有合適的轉換功能「DListNode *」存在雙向鏈表拷貝構造函數

Question

我目前正在編寫拷貝構造函數/賦值運算符的雙向鏈表類和有問題。

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

這是一個補充的頭文件，這裏節點和鏈接列表類都被聲明。我注意到DoublyLinkedList（header和trailer）的受保護類成員不是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; 
     } 
    } 
} 

我的拷貝構造函數我試圖解決這個問題很多不同的方式，有和沒有編輯的頭文件。我不能將標題和預告片更改爲DListNode *，因爲它們不允許進行更改，並且將其更改爲非指針將意味着我無法遍歷鏈接列表;所以我現在處於僵局。因爲我無法更改操作數的數據類型，所以我不知道如何解決錯誤。我認爲這可能與dll被作爲常量引用傳遞有關，但即使擺弄這些也沒有多大作用。我一直在看這幾個小時，似乎無法讓它工作。感謝您提前提供任何幫助！

Answer 1

您的列表中有兩個單元來管理，即使它是空的。 你可以採取不同的設計選擇與

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。

Answer 2

這份名單看起來比通常的雙向鏈表實現稍有不同，但它可以工作。

從你已經顯示的代碼看起來，兩個非指針成員header和trailer僅用於跟蹤列表的兩端，但實際上不是列表的一部分。這是由幾件事情從上面的代碼片段支持：

• 空列表具有header和trailer指向對方，與他們
• getFirst()之間的這兩個節點沒有設定值，並沒有其他節點，其中根據評論它上面應該返回一個指向第一個節點，header後實際返回節點，而不是header本身
• 你有一個getAfterLast()功能，通過它的名字來看，應在列表中的最後一個節點後返回一個標記，並且返回trailer。

如果上面是正確的，header和trailer實際上不是列表的一部分，那麼你的拷貝構造函數的實現是錯誤的。它應該只複製輸入列表中的實際值節點，不包括標題和預告片。這意味着您從以getFirst()開始的節點複製節點值，並在到達getAfterLast()時停止。

事情是這樣的代碼：

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

注意，這也處理客客氣氣的情況下，當源列表爲空。如果dll爲空，則dll.getFirst()實際上將返回預告片，這也是getAfterLast()返回的結果。所以while循環將不會執行，列表將保持爲空。