0

我试图在双向链表的末尾插入一个值，我成功地将值插入到头或第一个节点，但第二个值没有被插入

这里的问题是在输入第二个值时

class d_list
{
private:

    struct node
    {
        double data;
        node *next;
        node *previous;
    };

    node *first;
    node *last ;
public:
    d_list(void)
    {
        first = nullptr;
        last = nullptr;
    };
    void append(double);

};

void d_list::append(double num)
{
    node *ptr;
    node *toinsert;
    if(!first)
    {
        first = new node;
        first->previous= nullptr;
        first->data = num;
        last= new node;
        first->next= last->previous;
        last->previous = first->next;
        last->next= nullptr;

    }
    else
    {
        if(last->next == nullptr)
        {
            ptr = new node;
            ptr->next =last->previous;
            ptr->data=num;
            last->previous = ptr->next  ;
        }


        last->next= nullptr;
    }

}


int _tmain(int argc, _TCHAR* argv[])
{
    d_list aa;
    cout<<"going to append first"<<endl;
    aa.append(44);
    cout<<"going to append second"<<endl;
    aa.append(50.5);

    return 0;
}
4

5 回答 5

3

您的代码中有许多问题：

  • 您的node下一个和上一个成员永远不会在任何地方初始化，因此在使用时是未定义的。要么添加构造函数，node要么确保它们在分配后被初始化。
  • 将节点添加到空列表是不正确的。first->next未定义，为什么要创建两个节点，第一个和最后一个？在一个包含一个元素的列表中 then first == last。first/last 中的 next/previous 设置也没有任何意义。
  • 在格式良好的双链表中，thenlast->next应该始终为 null，就像first->previous.
  • 将节点添加到非空列表中也是不正确的。
  • 虽然您没有在示例中显示它，但您最终将需要一个析构函数以及一个复制运算符和复制构造函数（三个规则）。目前您正在泄漏内存，如果您尝试删除节点，您可能会导致双重释放和崩溃。

我建议您从代码中退后一步，以确保您正确理解双向链表背后的概念。在纸上用下一个/上一个箭头画出一个列表，看看在将节点添加到空/非空列表时需要如何更改它们，以及如何删除和移动节点。一旦您弄清楚应该如何设置下一个/上一个，那么将其转换为代码应该相对简单。

编辑回答评论：要添加一个新节点，您可以在技术上将它添加到任何地方，但它通常是在最后添加的（至少从我所见）。有关在空列表和非空列表中添加新节点的完整且正确的代码，请参阅其他答案。

于 2012-02-26T14:49:27.887 回答
2 
...
if(last->next == nullptr)
{
  ptr = new node;
  ptr->next =last->previous; // <- is not correct
  ptr->data=num;
  last->previous = ptr->next  ; // <- does not do anything useful
  ...

您不会将新节点附加到列表中。

...
if(!last->next)
{
  ptr = new node;
  ptr->previous=last->previous;
  ptr->next =last;
  ptr->data=num;
  last->previous = ptr  ;
  ...

应该更好。顺便说一句：在析构函数中删除分配的内存！

于 2012-02-26T14:44:52.727 回答
2

我会用下面的代码写你的双链表：

    #include <iostream>
    using namespace std;
    class d_list
    {
    private:

        struct node
        {
            double data;
            node *next;
            node *previous;
        };

        node *first;
        // node *last ; no need for bidirectional list
    public:
        d_list(void)
        {
            first = nullptr;
            //last = nullptr;
        };
        void append(double);

    };

    void d_list::append(double num)
    {
        node *ptr = new node;
        ptr->data = num;
        node *toinsert;
        if(!first)
        {
            first = ptr;
            first->previous=first->next=first;
        }
        else
        {
            if(first->next == first)
            {
                ptr->next = ptr->previous = first;
                first->next = first->previous = ptr;
            }
            else{
                node *last = first->previous;
                ptr->next = first;
                ptr->previous = last;
                last->next = ptr;
                first->previous = ptr;
            }
        }
    }


    int _tmain(int argc, _TCHAR* argv[])
    {
        d_list aa;
        cout<<"going to append first"<<endl;
        aa.append(44);
        cout<<"going to append second"<<endl;
        aa.append(50.5);

        return 0;
    }
于 2012-02-26T14:45:59.570 回答
1

试试这个代码... 

class d_list 
{


private:
      struct node
      {
         double data;
         node *next;
         node *previous;
     };
      node *first;
     node *last ;

 public:
     d_list(void)
     {
         first = nullptr;
         last = nullptr;
     };

     void append(double);
  }; 

 void d_list::append(double num)
 {
     node *ptr;
     node *toinsert;
     if(!first)
     {
         first = last = new node;
         first->previous= nullptr;
         first->next = nullptr;
         first->data = num;
     }
     else
     {
             ptr = new node;
             ptr->next =last->previous;
             ptr->data=num;
             last->previous = ptr->next  ;
     }
  }


 int _tmain(int argc, _TCHAR* argv[])
 {
     d_list aa;
     cout<<"going to append first"<<endl;
     aa.append(44);
     cout<<"going to append second"<<endl;
     aa.append(50.5);
      return 0;
 }
于 2012-03-07T11:12:56.513 回答
1

你为什么要插入声明node *ptr;， node *toinsert;如果你不使用它们？同样很明显，如果您在最后插入一个节点，则只应创建一个新元素（如果第一个为空，则调用 new 两次）。

于 2012-02-26T14:47:27.153 回答