スタックのデストラクタでダブルフリーまたは破損

Question

私はそれがコメントアウトした後、問題がwhile (!empty()) pop();にあると確信しています。すべて正常に動作します。それはdeleteheadではありません。この部分に何が問題なのですか？

次のとおりです。LinkedListには、headとtailという2つのデータメンバーがあります。リストが空の場合、これらは両方とも0に等しくなければなりません。リストが空でない場合、headとtailは両方とも0でなく、それぞれリストの最初と最後の項目を参照する必要があります。そしてnext_ポインターを経由してheadからtailまでのパスが存在しなければならない。リストに項目が1つしかない場合は、head == tail。

#include <iostream> 
//stack using linked list 
class LinkedList { 
public: 
    LinkedList() : head(0), tail(0) {} 
    ~LinkedList() { 
    while (!empty()) pop(); 
    std::cout<< "~LinkedList" << std::endl; 
    } 
    void pop() { 
    node* temp; 
    temp = head; 
    for (; temp->next_ != 0; temp = temp->next_) { 
     tail = temp; 
    } 
    delete temp; 
    tail->next_ = 0; 
    std::cout << "pop()" << std::endl; 
    } //removes, but does not return, the top element 
    int top() { 
    return tail->value_; 
    } //returns, but does not remove, the top element 
    bool empty() { 
    return head == 0; 
    } 
    void push(const int& value) { 
    node* element = new node(value); 
    if (empty()) { 
     head = tail = element; 
    } else { 
     tail->next_ = element; 
     tail = element; 
    } 
    } //place a new top element 
private: 
    class node { 
    public: 
    node(const int& input) : value_(input), next_(0) {}; 
    int value_; //store value 
    node* next_; //link to the next element 
    }; 
    node* head; 
    node* tail; 
}; 
int main() { 
    LinkedList list; 
    list.push(1); 
    list.push(2); 
    std::cout << list.top() << std::endl; 
    list.pop(); 
    std::cout << list.top() << std::endl; 
    return 0; 
} 

は、次のコードにデストラクタを変更することで、問題を修正：あなたの場合

~LinkedList() { 
    while (head != tail) pop(); 
    delete head; 
    std::cout<< "~LinkedList" << std::endl; 
    } 

Answer 1

あなたpop()リストでpop()最後の要素this->headは修正されません。

Answer 2

headは0（NULL）に設定されている場合はあなたがここに

bool empty() { 
    return head == 0; 
} 

あなたの問題の一部を持っていますか？決して？

Answer 3

pop()が間違っています。要素が1つだけ残っている場合は、headとtailの両方がポイントされます。あなたdelete tempは、あなたがheadとtailの両方を削除することにしているときに、あなたは以下のとおりです。

• は現在割り当て解除のポインタである、tailへのアクセス、および

• は戻って0からtailまたはheadを設定しません

Answer 4

これらのチェックは、最初に追加できます。これは退屈な解決策であり、全体的なデザインを変更する必要がありますが、このコードでは現在のアルゴリズムpopを修正する必要があります。特に、最後のアイテムをポップするときは、headとtailの両方をゼロに設定する必要があります。

また、それだけで私はこれをテストしていませんtail->next_ = 0;

void pop() { 
    if(head == 0) { 
     // the list is empty, there's nothing to pop. This should be an error! 
    } 
    if((head != 0 && head == tail) { 
     // there is only one item in the list 
     delete head; 
     head = 0; 
     tail = 0; 
    } 
    node* temp; 
    temp = head; 
    for (; temp->next_ != 0; temp = temp->next_) { 
     tail = temp; 
    } 
    delete tail->next_; 
    tail->next_ = 0; 
    std::cout << "pop()" << std::endl; 
    } 

前に、delete tail->next_;、ないdelete temp;する必要がありますが、それは問題の一部を修正する必要があります。