问题与双向链接列表中的添加方法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