問題與雙向鏈接列表中的添加方法C++

Question

我正在採取數據結構課程，目前的任務是創建一個簡單的隊列類，它是從現有的雙向鏈表列類構建的。

聽起來很容易，但我相當生疏，尤其是使用C++，而且我很難從書中獲取雙鏈表代碼。代碼有意義（除了add方法），但是當我嘗試調用addFront（）時程序崩潰。

我有一種感覺，我犯了一個愚蠢的錯誤，但我顯然需要一些幫助和解釋，如果我不能得到示例代碼來正確運行。

教授建議我們使用的代碼在Michael T. Goodrich的C++數據結構和算法的第127頁。您可以使用亞馬遜的外觀功能實際查看此頁面。 http://amzn.com/0470383275

我試圖編譯的文件可以在這裏找到： https://dl.dropboxusercontent.com/u/12660663/DLinkedList.zip

這是筆者的前面添加方法，它要求在那裏我認爲問題出在add（）方法。

void DLinkedList::addFront(const Elem& e) // add to front of list 
{ add(header->next, e); } 

這是它究竟是如何（順便說完全Comic Sans字體）寫在書和教授MS Word文檔完整的示例代碼的附加功能：

// Insert new node before v 
void DLinkedList::add(DNode* v, const Elem& e) 
{ 
DNode* u = new DNode; u->elem = e; // create a new node for e 
u->next = v;       // link u in between v 
u->prev = v->prev;      // ...and v->prev 
v->prev->next = v->prev = u; 

}

這段代碼有意義，除了最後一行，我發現很難遵循。

這是我做的主，使程序崩潰（記住，該項目實際上是使用這個類來創建另一個類，所以我只是想獲得它的工作）：

#include "DLinkedList.h" 

int main() 
{ 
    DLinkedList list; 

    Elem s; 
    s = "Jim"; 

    list.addFront(s); // This and addBack(s) causes the program to crash, 
         // doesn't crash if I remove this line 
    return 0; 
} 

這裏是頭文件：

#include <string> 
#include <iostream> 
using namespace std; 

#ifndef DLINKEDLIST_H_ 
#define DLINKEDLIST_H_ 

// Code Fragment 3.22 
typedef string Elem;    // list element type 
class DNode {     // doubly linked list node 
private: 
    Elem elem;     // node element value 
    DNode* prev;    // previous node in list 
    DNode* next;    // next node in list 
    friend class DLinkedList;   // allow DLinkedList access 
}; 

// Code Fragment 3.32 
class DLinkedList {    // doubly linked list 
public: 
    DLinkedList();    // constructor 
    ~DLinkedList();    // destructor 
    bool empty() const;    // is list empty? 
    const Elem& front() const;   // get front element 
    const Elem& back() const;   // get back element 
    void addFront(const Elem& e);  // add to front of list 
    void addBack(const Elem& e);  // add to back of list 
    void removeFront();    // remove from front 
    void removeBack();    // remove from back 
private:     // local type definitions 
    DNode* header;    // list sentinels 
    DNode* trailer; 
protected:     // local utilities 
    void add(DNode* v, const Elem& e);  // insert new node before v 
    void remove(DNode* v);   // remove node v 
}; 

#endif /* DLINKEDLIST_H_ */ 

我試圖與「功課」這個標籤，但顯然這不是個東西了。

儘管這是作業，我的任務是重用這個已經寫好的代碼來創建一個新類。

在此先感謝，我非常感謝任何建議和解釋。

邁克爾

Answer 1

GCC 4.7.3會爲您覺得令人困惑的代碼生成警告。您可以簡化它（並刪除警告）如下：

void DLinkedList::add(DNode* v, const Elem& e) { 
    DNode* u = new DNode; u->elem = e;  // create a new node for e 
    u->next = v;       // link u in between v 
    u->prev = v->prev;      // ...and v->prev 
    v->prev->next = u; 
    v->prev = u; 
} 

最後，你的代碼段錯誤，因爲你沒有如實地複製Goodrich的析構函數。它應該是：

DLinkedList::~DLinkedList() 
{ 
    while (!empty()) removeFront(); 
    delete header; 
    delete trailer; 
} 

Answer 2

只是回答您的問題之一，現在：

void DLinkedList::add(DNode* v, const Elem& e) 
{ 
    DNode* u = new DNode; u->elem = e; // create a new node for e 
    u->next = v;       // link u in between v 
    u->prev = v->prev;      // ...and v->prev 
    v->prev->next = v->prev = u; 
} 

此代碼是有道理的，除了最後一行，我覺得很難效仿。

想象*v是鏈表中的節點：

... <--[-prev NODE next-]--> <--[-prev *v next-]--> <--[-prev NODE next-]--> ... 

什麼上面的代碼確實是準備一個新的節點*u：

[-prev *u next-]   // DNode* u = new DNode; 
[-prev *u elem=e next-] // u->elem = e; 

      [-prev *u elem=e next=v-]- // u->next = v; 
            \ 
             v 
... <--[-prev NODE next-]--> <--[-prev *v next-]--> <--[-prev NODE next-]--> ... 

     [-prev *u elem=e next=v-]--> // u->prev = v->prev; 
      \      \ 
       v      v 
... <--[-prev NODE next-]--> <--[-prev *v next-]--> <--[-prev NODE next-]--> ... 


     [-prev *u elem=e next=v-]--> // v->prev->next = v->prev = u; 
      \  ^^  \ 
       v   \ \  v 
... <--[-prev NODE next-]-\ \-[-prev *v next-]--> <--[-prev NODE next-]--> ... 

所以，最後v->prev->next = v->prev = u;斷鏈接在節點*v和列表中的節點之間，製作：

• v->prev指向*u使得*u向後遍歷期間發現以前到*v，和
• v->prev->next（一度先前TO- *v的鏈接到下一節點）指向*u

因此，通過列表的新排序是：即將使用的節點即將到達*v→*u→*v ......

Answer 3

這是令人困惑我的add()最後一行：

void DLinkedList::add(DNode* v, const Elem& e) { 
    // ... 
    v->prev->next = v->prev = u; 
} 

根據裁定分配權進行到左，應該簡化爲：

void DLinkedList::add(DNode* v, const Elem& e) { 
    // ... 
    v->prev = u; 
    v->prev->next = u; 
} 

而不是亞當巴里說：

void DLinkedList::add(DNode* v, const Elem& e) { 
    //... 
    v->prev->next = u; 
    v->prev = u; 
} 

但在我看來我錯了。谷歌一段時間後我發現，在C++做一個鏈接分配時：

a = b = c = d; 
// simplify to: 
// a = d 
// b = d 
// c = d 

而且不

// c = d 
// b = c 
// a = b