c++ - head->next 不为空

Question

我不明白为什么我的单项列表“_head->next”没有被设置为 null (nullptr)。我会混淆我的尾部和头部指针吗？这是一个双向链表。大多数其他指针都可以工作，但此错误/错误会在遍历列表时引发段错误。

#pragma once
class dlist {
  public:
    dlist() { }

  struct node {
    int value;
    node* next;
    node* prev;
  };


  node* head() const { return _head; }
  node* tail() const { return _tail; }


void insert(node* prev, int value){
     //if empty
     if(prev == nullptr)
       {
       //create node/prepare to insert into head ptr
        _head = new node{value, _head, nullptr};

        if(_tail == nullptr)
        {
         _tail = _head;
         _tail->next = nullptr;
        }
        //set head
        if(_head->next != nullptr)
          {
           _head->prev = _head;

           _head->next = nullptr;
           //_head->next->next = nullptr;
           //above doesn't work  
          }
       }
 //if not empty
     else
       {
       //create and set new node
        node* node1 = new node{value, prev->next, nullptr};
        prev->next = node1;

        //check if null, to make sure inserting after a filled "space"
         if(node1->next != nullptr)
           {
            node1->next->prev = node1;

            //set to end or tail
            if(prev == _tail)
              {
               _tail = node1;
               _tail->next = nullptr;
              }
           }
       }
  }


 private:
   node* _head = nullptr;
   node* _tail = nullptr;

};

Answer 1

考虑到您发布的初始代码以及您使用 prev 作为 insert 的参数时的歧义，这有点难以理解。

首先，insert 是 dlist 的成员函数，可以直接访问 _head 和 _tail . insert 不需要 node* 参数，因为您对链表唯一关心的是检查 _head 是否为 nullptr 并为 _head 分配/分配 value，否则您将迭代直到您的 iter->next 为 nullptr 并将分配的节点添加为 iter->next setting _tail 到新分配的节点。

坦率地说，您现有的大部分代码都让我摸不着头脑。此外，class 的默认值是 private，因此通常您只需指定 public 成员即可。

将逻辑放在一起，您可以执行以下操作:

class dlist {

    struct node {
        int value;
        node* next;
        node* prev;
    };

    node* _head = nullptr;
    node* _tail = nullptr;

  public:
    dlist() { }

    node* head() const { return _head; }
    node* tail() const { return _tail; }

    void insert (int value)
    {
        node *newnode = new node {value, nullptr, nullptr};

        if (_head == nullptr)
            _head = newnode;
        else {
            node* iter = _head;
            for (; iter->next; iter = iter->next) {}
            newnode->prev = iter;
            _tail = iter->next = newnode;
        }
    }
};

当你在一个类中分配内存时，为了防止像筛子一样泄漏内存，你还需要声明一个析构函数，当类的实例超出范围时，它会释放你分配的内存。不需要任何花哨的东西，只需从 _head 迭代到列表的末尾，然后 delete 节点。

(注意:在保存对下一个节点的引用之前，您不得删除对当前节点的引用，因此请使用一个单独的、适当命名的victim 节点执行delete)

你可以这样做:

    ~dlist() {
        node* iter = _head;
        while (iter) {
            node* victim = iter;
            iter = iter->next;
            delete victim;
        }
    }

将其放在一起并向 print 和 reverse 或 rprint 列表添加几个函数，您可以执行如下操作:

#include <iostream>

using namespace std;

class dlist {

    struct node {
        int value;
        node* next;
        node* prev;
    };

    node* _head = nullptr;
    node* _tail = nullptr;

  public:
    dlist() { }
    ~dlist() {
        node* iter = _head;
        while (iter) {
            node* victim = iter;
            iter = iter->next;
            delete victim;
        }
    }

    node* head() const { return _head; }
    node* tail() const { return _tail; }

    void insert (int value)
    {
        node *newnode = new node {value, nullptr, nullptr};

        if (_head == nullptr)
            _head = newnode;
        else {
            node* iter = _head;
            for (; iter->next; iter = iter->next) {}
            newnode->prev = iter;
            _tail = iter->next = newnode;
        }
    }

    void print () {
        for (node* iter = _head; iter; iter = iter->next)
            cout << " " << iter->value;
        cout << "\n";
    }

    void rprint() {
        for (node* iter = _tail; iter; iter = iter->prev)
        cout << " " << iter->value;
        cout << "\n";
    }
};

int main (void) {

    dlist list;
    int tmp;

    while (cin >> tmp)
        list.insert(tmp);

    list.print();
    list.rprint();
}

示例使用/输出

$ echo "2 3 4 6 8 10" | ./bin/dlist
 2 3 4 6 8 10
 10 8 6 4 3 2

内存使用/错误检查

在您编写的任何动态分配内存的代码中，您对分配的任何内存块负有 2 个责任:(1) 始终保留指向起始地址的指针或引用 对于内存块，(2) 它可以在不再需要时被释放。

您必须使用内存错误检查程序来确保正确使用您分配的内存，并确认您释放了所有已分配的内存。

对于 Linux valgrind 是正常的选择。每个平台都有类似的内存检查器。它们都易于使用，只需通过它运行您的程序即可。

$ echo "2 3 4 6 8 10" | valgrind ./bin/dlist
==18878== Memcheck, a memory error detector
==18878== Copyright (C) 2002-2017, and GNU GPL'd, by Julian Seward et al.
==18878== Using Valgrind-3.13.0 and LibVEX; rerun with -h for copyright info
==18878== Command: ./bin/dlist
==18878==
 2 3 4 6 8 10
 10 8 6 4 3 2
==18878==
==18878== HEAP SUMMARY:
==18878==     in use at exit: 0 bytes in 0 blocks
==18878==   total heap usage: 9 allocs, 9 frees, 77,968 bytes allocated
==18878==
==18878== All heap blocks were freed -- no leaks are possible
==18878==
==18878== For counts of detected and suppressed errors, rerun with: -v
==18878== ERROR SUMMARY: 0 errors from 0 contexts (suppressed: 0 from 0)

始终确认您已释放所有分配的内存并且没有内存错误。