1

这是一个 DLinkedList 实现，使用 addFront() 将 int 类型的元素添加到其中，但使用 front() 未检索到它。没有显示错误。不知道为什么？？这是完整的实现。代码在 xCode4.5 上运行。

int main(int argc, const char * argv[])
{
    DLinkedList listOne;

    if(listOne.empty()){
        cout<<"Empty";
    }
    const int num=23;
    listOne.addFront(num);

    //Here 0 is returned from front(), while it should be 23;
    cout<<listOne.front()<<endl;

    return 0;
}

//Node Defination
class DNode {                   // doubly linked list node
private:
    int elem;                   // node element value
    DNode* prev;                // previous node in list
    DNode* next;                // next node in list
    friend class DLinkedList;           // allow DLinkedList access
};

class DLinkedList {             // doubly linked list
public:
    DLinkedList();              // constructor
    ~DLinkedList();             // destructor
    bool empty() const;             // is list empty?
    const int front() const;            // get front element
    const int back() const;         // get back element
    void addFront(const int e);     // add to front of list
    void addBack(const int 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 int e);        // insert new node before v
    void remove(DNode* v);          // remove node v
};

void listReverse(DLinkedList& L) {      // reverse a list
    DLinkedList T;              // temporary list
    while (!L.empty()) {            // reverse L into T
        int s = L.front();  L.removeFront();
        T.addFront(s);
    }
    while (!T.empty()) {            // copy T back to L
        int s = T.front();  T.removeFront();
        L.addBack(s);
    }
}

void DLinkedList::remove(DNode* v) {        // remove node v
    DNode* u = v->prev;             // predecessor
    DNode* w = v->next;             // successor
    u->next = w;                // unlink v from list
    w->prev = u;
    delete v;
}

void DLinkedList::removeFront()     // remove from font
{ remove(header->next); }

void DLinkedList::removeBack()      // remove from back
{ remove(trailer->prev); }

// insert new node before v
void DLinkedList::add(DNode* v, const int e) {
    DNode* u = new DNode;  u->elem = e;     // create a new node for e
    std::cout<<u->elem<<std::endl;
    u->next = v;                // link u in between v
    u->prev = v->prev;              // ...and v->prev
    v->prev->next = v->prev = u;
}

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

void DLinkedList::addBack(const int e)  // add to back of list
{ add(trailer, e); }

DLinkedList::~DLinkedList() {           // destructor
    while (!empty()) removeFront();     // remove all but sentinels
    delete header;              // remove the sentinels
    delete trailer;
}

DLinkedList::DLinkedList() {            // constructor
    header = new DNode;             // create sentinels
    trailer = new DNode;
    header->next = trailer;         // have them point to each other
    trailer->prev = header;
    std::cout<<"DLinkedListConstructor"<<std::endl;
}

bool DLinkedList::empty() const     // is list empty?
{ return (header->next == trailer); }

const int DLinkedList::front() const    // get front element
{ return header->next->elem; }

const int DLinkedList::back() const     // get back element
{ return trailer->prev->elem; }
4

3 回答 3

3

问题出在您的add功能上：

// insert new node before v
void DLinkedList::add(DNode* v, const int e) {
    DNode* u = new DNode;  u->elem = e;     // create a new node for e
    std::cout<<u->elem<<std::endl;
    u->next = v;                // link u in between v
    u->prev = v->prev;              // ...and v->prev
    v->prev->next = v->prev = u;
}

让我们一起来看看吧。您从以下情况开始（我已将v->prev指向的节点称为p）：

┌───────────┐
│           ▼
p ◀──────── v

      u

然后您设置u->next为v：

┌───────────┐
│           ▼
p ◀──────── v
            ▲
      u─────┘

然后u->prev到v->prev：

┌───────────┐
│           ▼
p ◀──────── v
▲           ▲
└─────u─────┘

下一行是问题所在。首先它分配u给v->prev：

┌───────────┐
│           ▼
p     ┌──── v
▲     ▼     ▲
└─────u─────┘

然后它将相同的指针分配给v->prev->next。但是v->prev现在是u，所以你只是设置u->next指向v并且它已经这样做了。所以没有变化。

现在，当您尝试获取最前面的元素时，您只会得到 element v，这是您的哨兵节点。

您需要分别完成这两项任务：

v->prev->next = u;
v->prev = u;
于 2013-02-02T13:44:25.793 回答
2

首先，您没有为所有节点初始化prev和next指针。构造列表时，列表的构造函数会：

header = new DNode;             // create sentinels
trailer = new DNode;
header->next = trailer;         // have them point to each other
trailer->prev = header;

这意味着header->prev并且trailer->next未初始化。这些指针不会NULL自动初始化，所以要小心。

但是您观察到的根本原因是在您的add_front()函数中，您正在调用一个add()最终执行此操作的函数：

// Replacing v with header->next, which is the actual argument of the call
...
u->next = header->next;          // u->next = trailer      
u->prev = header->next->prev;    // u->prev = trailer->prev; // Uninitialized!
header->next->prev = u;          // trailer->prev = u;
header->next->prev->next = u;    // u->next = u

由于最后一条语句，这显然是错误的，并且因为您从未分配header->next = u.

顺便说一句，我建议您考虑使用智能指针而不是原始指针，并根据所需的所有权语义进行适当的选择。除此之外，智能指针会自动初始化为nullptr.

于 2013-02-02T13:37:46.170 回答
1

代码在 windows 中的 Mingw 编译器上运行得很好，并且使用代码块给出了 23，而不是 0....但是，我建议进行以下更改，因为一些编译器从右到左分配值，堆栈的东西....

void DLinkedList::add(DNode* v, const int e) {
    DNode* u = new DNode;  u->elem = e;     // create a new node for e
    std::cout<<u->elem<<std::endl;
    u->next = v;                // link u in between v
    u->prev = v->prev;              // ...and v->prev
    v->prev->next = u;              // do this first......
    v->prev = u;                    // then this.
}
于 2013-02-02T13:37:30.333 回答