动态分配的双向循环列表 class 实例段错误 C++

Question

当 main 使用 constructed dlring 类型的变量时，使用此模板 class 工作得很好，但我的目标是允许 动态分配，所以我可以处理非预定义数量的双向链接循环列表，以允许使用以下函数：

使用节点位置将列表分成两部分（通过
迭代）或值输入。
将两个列表链接成一个列表也是如此 head/tail 对.
节点从一个列表（实例）导出到另一个。
等等

我非常确定有一个我还不知道的优雅的解决方法，但我认为如果你没有足够的努力来向社区提出问题是件好事解决。（勾选 google

因此，为了实现该目标，我应该使用某种指针对指针 AFAIK 动态分配内存（通过构造函数调用）。如果有更聪明的方法来实现这些，请告诉我。我的解决方案尝试在这个 snippet 的末尾给出。欢迎批评以下所有内容。

双向循环列表class头（简化）

template <typename T>
class dlring
{
    struct node
    {
        T data;
        node* prev;
        node* next;
        node(T t, node* p, node* n) : data(t), prev(p), next(n) {}
    };
    node* head;
    node* tail;
public:
    dlring():head(nullptr), tail(nullptr){}
    bool empty() const { return ( !head || !tail ); }
//operator bool() const { return !empty(); }
    void Push(T);
    T pop_back();
    ~dlring()
    {
        while(head)
        {
            node* temp(head);
            head=head->next;
            delete temp;
        }
    }
};

我应该使用注释掉的 operator bool 重载吗？

pop_back 和推送方法：

template <typename T>
void dlring<T>::Push(T data)
{
    head = new node(data, tail, head); 
    if( head->next )
    {
        head->next->prev = head;
        tail->next = head;
    }
    if( empty() )
    {
        tail = head;
        head->next=tail;
        head->prev=tail;
        tail->next=head;
        tail->prev=head;
    }
}
template<typename T>
T dlring<T>::pop_back()
{
    if( empty() )
        std::cout<<"List empty";
    node* temp(tail);
    T data( tail->data );
    tail = tail->prev ;
    if (tail != temp)
    {
        tail->next->next = head; 
        head->prev = tail;
    }
    else
    {
        head = nullptr;
        tail = nullptr;
    }
    delete temp;
    temp = nullptr;
    return data;
}

我的尝试没有正确的行为：当我试图通过迭代显示所有列表时，代码失败，头部出现段错误-> dlist 的数据访问尝试[0]，其中 0 是 k 的迭代。这是片段：

   int main()
    {
    int k;
      std::cout<<"Rings count?"<<std::endl;
      std::cin>>k;
        dlring<int>* dlist = new dlring<int>[k]; //I suppose I'm allocating *k*
     //dlring<int> elements. this line is not confirmed to call the constructor.
    (dlist[0]).Push(10);
    (dlist[0]).Push(13);
    (dlist[1]).Push(99);
    /*{
    while(!dlist[0].empty())
    std::cout<<(dlist[0]).pop_back()<<" ";
    std::cout<<std::endl;
    while(!dlist[1].empty())
    std::cout<<(dlist[1]).pop_back()<<" ";
    }*/
    //this section works perfectly fine, while this
      for(int i=0;i<k;i++)
      {
        while(!dlist[k].empty())
        std::cout<<(dlist[k]).pop_back()<<" ";
        std::cout<<std::endl;
      }
    //is causing a segmentation fault while attempting to access dlist[*0*].tail->data.
    std::cout<<(dlist[0]).head->data;
    //line was checked and is confirmed to be functional, 
    //I suppose dlist[variable] has some trick I don't know yet.
    //what I wish to look like an instance call would be *
    return 0;
    }

此致。再次，请随时批评我的 code/logics.

中的任何

Answer 1

  for(int i=0;i<k;i++)
  {
    while(!dlist[k].empty())
    std::cout<<(dlist[k]).pop_back()<<" ";
    std::cout<<std::endl;
  }

没有使用迭代器i。应该是：

  for(int i=0;i<k;i++)
  {
    while(!dlist[i].empty())
    std::cout<<(dlist[i]).pop_back()<<" ";
    std::cout<<std::endl;
  }

由于 dlist 是一个大小为 k 的数组，因此原始代码会产生越界访问。

由于上述循环使 dlist 数组中的每个列表都为空，因此所有列表的 head 都将是一个空指针。请注意，您根本无法访问它，因为它是私有成员。如果这样做，取消引用时会出现段错误：

std::cout<<(dlist[0]).head->data;

如果编译成功，此时在程序中，dlist[0].head == nullptr，因此出现段错误。

另请注意，您正在泄漏内存，因为您没有释放动态分配的 dlist。附加到程序末尾：

delete[] dlist;

通过这些更改，我没有收到任何段错误、问题或来自 clang 的地址清理程序的报告。

另一个问题（在您的 main 中没有出现）是 pop_back 中 tail 的设置。我将尝试使用一些 ASCII 艺术来说明。一盒

   D ->
<- D

表示一个带有数据的节点，一个next指针和一个prev指针。所有箭头都是指针。

一个非空列表：

   +-----------------------------+
   v                             |
   D ->    D -> ..    D ->    D -+
+- D    <- D    .. <- D    <- D
|                             ^
+-----------------------------+
   ^                          ^
   |head                      |tail

head->prev与tail指向同一个对象，类似地，tail->next与head指向同一个对象。

现在，pop_back 函数的 "animation"。

template<typename T>
T dlring<T>::pop_back()
{
    if( empty() )
        std::cout<<"List empty";
    node* temp(tail);

    /*
       +-----------------------------+
       v                             |
       D ->    D -> ..    D ->    D -+
    +- D    <- D    .. <- D    <- D
    |                             ^
    +-----------------------------+
       ^                          ^
       |head                      |tail
                                  |temp
    */

    T data( tail->data );
    tail = tail->prev ;

    /*
       +-----------------------------+
       v                             |
       D ->    D -> ..    D ->    D -+
    +- D    <- D    .. <- D    <- D
    |                             ^
    +-----------------------------+
       ^                  ^       ^
       |head              |tail   |temp
    */

    if (tail != temp)
    {
        tail->next->next = head; 

        /*
           +-----------------------------+
           v                             |
           D ->    D -> ..    D ->    D -+  (A)
        +- D    <- D    .. <- D    <- D
        |                             ^
        +-----------------------------+
           ^                  ^       ^
           |head              |tail   |temp

        The pointer (A) is what is changed when writing to tail->next->next.
        Yes, nothing has actually changed in the list!
        */

        head->prev = tail;

        /*
           +-----------------------------+
           v                             |
           D ->    D -> ..    D ->    D -+
        +- D    <- D    .. <- D    <- D
        |                     ^
        +---------------------+
           ^                  ^       ^
           |head              |tail   |temp
        */

    }
    else
    {
        head = nullptr;
        tail = nullptr;
    }
    delete temp;

    /*
       D ->    D -> ..    D ->
    +- D    <- D    .. <- D
    |                     ^
    +---------------------+
       ^                  ^       ^
       |head              |tail   |temp
    */

    temp = nullptr;
    return data;
}

注意在最后的"picture"中，tail->next是一个无效的指针。

相反，它应该是：

    if (tail != temp)
    {
        tail->next = head; 

        /*
           +---------------------+-------+
           v                     |       |
           D ->    D -> ..    D -+    D -+
        +- D    <- D    .. <- D    <- D
        |                             ^
        +-----------------------------+
           ^                  ^       ^
           |head              |tail   |temp

删除 temp 后（没有进一步更改），它将如下所示：

        /*
           +---------------------+
           v                     |
           D ->    D -> ..    D -+
        +- D    <- D    .. <- D
        |                     ^
        +---------------------+
           ^                  ^       ^
           |head              |tail   |temp

最后但同样重要的是，请注意您违反了 Rule of Three。

动态分配的双向循环列表 class 实例段错误 C++

Dynamically allocated doubly linked circular list class instances segfault C++

c++11

linked-list

segmentation-fault

dynamic-programming

双向循环列表class头（简化）

pop_back 和推送方法：