1

リンク リストの先頭要素を削除し、削除された要素の次の要素にヘッド ポインタを設定する関数を作成しようとしています。

これが私のコードです：

void LinkedList::delete_front(){
    if(head != NULL){
            if(head->next != NULL){
                    ListNode *tmp = head;
                    delete head;
                    head = tmp->next;
            }
            else {delete head; head = NULL;}
    }
    size--;
}

そして、ここに私のクラス定義があります:

class ListNode{

    public:
            Item data;
            ListNode *next;
};
class LinkedList{

    private:
            ListNode *head;
            int size;

    public:
            LinkedList();
            ~LinkedList(); 
            bool empty();
            void insert_front(Item i);
            void insert_back(Item i);
            void delete_front();
            void delete_back();
            void print();
};

Annddddd .....これが問題です。valgrind で実行すると、最初の delete_front() 呼び出しの直前にこのエラーがポップアップします。

==4738== Invalid read of size 8
==4738==    at 0x400B3C: LinkedList::delete_front() (in /home/jon/jball2_lab06/linkedlist)
==4738==    by 0x400E59: main (in /home/jon/jball2_lab06/linkedlist)
==4738==  Address 0x5a03f98 is 8 bytes inside a block of size 16 free'd
==4738==    at 0x4C2A4BC: operator delete(void*) (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)
==4738==    by 0x400B37: LinkedList::delete_front() (in /home/jon/jball2_lab06/linkedlist)
==4738==    by 0x400E59: main (in /home/jon/jball2_lab06/linkedlist)
4

4 に答える 4

3

ここでの問題:

if(head->next != NULL){
    ListNode *tmp = head;
    delete head;
    head = tmp->next;
}

ヘッドに temp を割り当ててから、ヘッドを削除します。その後、再度アクセスしてみてください。

于 2013-10-11T20:27:40.153 に答える
2

要素を削除していて、その後、それにアクセスしようとしています。それはこれらの行です：

ListNode *tmp = head;
delete head;
head = tmp->next; // tmp was initialized to head, but head was just deleted!

これは次のようになります。

ListNode *tmp = head->next;
delete head;
head = tmp;

更新:上記を使用すると、メソッド全体がはるかに簡単になることに気付きました:

void LinkedList::delete_front()
{
    if(head != NULL) {
        ListNode *tmp = head->next;
        delete head;
        head = tmp;
        --size;
    }
}

すべてのケースで機能するはずです。head->next == NULL上記でも同様に処理されるため、確認する必要はありません。sizeまた、リストが空の場合でもブロック--size内を移動するコードのバグが修正されます。if(head != NULL)

これにより、「リストが空の場合は何もしない」という元のセマンティクスが保持されることに注意してください。これは通常、必要なものではありません。例外をスローすることを検討してください。

void LinkedList::delete_front()
{
    if(head == NULL) {
        throw std::runtime_exception( "LinkedList::delete_front() "
                                      "called with empty list" );
    }

    ListNode *tmp = head->next;
    delete head;
    head = tmp;
    --size;
}
于 2013-10-11T20:27:27.083 に答える
1

あなたの問題はここにあります：

                ListNode *tmp = head;
                delete head;
                head = tmp->next;

tmp を head に設定し、次に head を削除してから、tmp を使用します。tmp は、削除したメモリを指しています。

代わりに、tmp を head に設定し、head を head->next に設定してから、tmp を削除します。

于 2013-10-11T20:27:18.687 に答える
1

スマート ポインターを使用すると、次のようになります。

void LinkedList::delete_front() {
    if(head != NULL) {
        head = head->next;
        --size;
    }
}

どこ：

class ListNode{
    public:
        Item data;
        unique_ptr<ListNode> next;
};

class LinkedList{
    private:
        unique_ptr<ListNode> head;
//.. etc

また、 であってもサイズが減少していたバグを修正しましheadたNULL。

于 2013-10-11T20:39:39.453 に答える