雙向鏈表：前面沒有插入值

Question

這是一個DLinkedList實現，int類型的一個元素使用addFront（）添加到它，但是它沒有使用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; } 

Answer 1

問題是與您的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─────┘ 

下一行是問題所在。首先，它分配給uv->prev：

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

然後將其分配相同的指針v->prev->next。但v->prev現在u，所以你只是設置u->next指向v它已經這樣做。所以沒有改變。

現在，當您嘗試獲取前端元素時，您只需獲取元素v，它是您的哨兵節點。

您需要單獨做這兩個任務：

v->prev->next = u; 
v->prev = u; 

Answer 2

的代碼在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. 
} 

Answer 3

首先，你是不是初始化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。