c++ - 双向链表 C++ 中的 add 方法问题

Question

我正在学习数据结构类(class)，当前的任务是创建一个简单的队列类，它是从现有的双向链表类构建的。

听起来很简单，但我有点生疏，尤其是使用 C++ 时，我很难从书中获得双向链表代码。代码是有道理的(add 方法除外)，但是当我尝试调用 addFront() 时程序崩溃了。

我觉得我犯了一个愚蠢的错误，但如果我无法让示例代码正确运行，我显然需要一些帮助和解释。

教授建议我们使用的代码位于 Michael T. Goodrich 的 Data Structures and Algorithms in C++ 第 127 页。您实际上可以使用亚马逊的内部查看功能查看此页面。 http://amzn.com/0470383275

我要编译的文件可以在这里找到: https://dl.dropboxusercontent.com/u/12660663/DLinkedList.zip

这是作者的add前端方法，它调用了我认为问题所在的add()方法。

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

这正是书中和教授的 MS Word 文档中充满示例代码的添加函数(顺便说一句，完全是 Comic Sans):

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

除了最后一行，这段代码很有意义，我觉得很难理解。

这就是我在 main 中为使程序崩溃所做的全部工作(请记住，该项目实际上是使用此类创建另一个类，所以我只想让它运行):

#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;
}