1

これは 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; }
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->nextv

フロント要素を取得しようとするvと、番兵ノードである element が取得されます。

次の 2 つの割り当てを別々に行う必要があります。

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 コンパイラで問題なく実行され、コードブロックを使用して 0 ではなく 23 を返しました....

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 に答える