将链接列表插入链接列表

I wrote this function that inserts another linked list to the existing linked list. The output is correct when I print out the value of "this" object in the function. However, the program encounters run time error when the destructor gets invoked in the end. I figured that the run time error is caused by having 2 pointers pointing to the same address; therefore when one gets de-allocated, another one becomes the dangling pointer.

我写了这个函数，将另一个链表插入到现有的链表中。当我在函数中打印出“this”对象的值时，输出是正确的。但是，当最终调用析构函数时，程序会遇到运行时错误。我认为运行时错误是由2个指针指向同一个地址引起的;因此当一个人被解除分配时，另一个人成为悬空指针。

Is there any ways I can insert another linked list to the existing linked list (in the middle) without causing this problem?

有没有什么方法可以将另一个链表插入到现有链表（中间）而不会导致此问题？

void List::insert(const List& otherList, const int &index)
{
    Node* insertion = head;
    int x = index;
    while (x > 0){
        insertion = insertion->next;
        x--;
    }

    if (index == 0){  //this works fine
        otherList.tail->next = insertion;
        *this = otherList;  /*I implemented a copy ctor 
                              that performs deep copy 
                              so this is also fine */
    }
    else{ // this block causes problems
        Node* tmp = insertion->next;
        insertion->next = otherList.head;
        otherList.tail->next = tmp;
    }
    cout << "after the copy\n" << (*this) << endl;
}

1 个解决方案

#1

There are some problems with your code.

您的代码存在一些问题。

One problem is that it is unclear what you expect from the insert-function.

一个问题是，您不清楚您对插入函数的期望。

Where is the other list to be inserted? I would assume that index should mean that the head of otherList would become the Node at position index (counting from zero). That is also what your code is doing for index=0 but for index=1 you actually insert after the current element number 1. This can be fixed by changing the while, i.e.

要插入的其他列表在哪里？我认为索引应该意味着otherList的头部将成为位置索引处的节点（从零开始计数）。这也是你的代码为index = 0所做的事情，但是对于index = 1，你实际上是在当前元素编号1之后插入的。这可以通过改变while来修复，即

while (x > 1)

Another problem is that you don't check for nullptr before using the pointers. That must be fixed.

另一个问题是在使用指针之前不检查nullptr。那必须修复。

Third problem is that you don't get a copy when index > 0.

第三个问题是当index> 0时你没有得到副本。

I'm not sure if your copy ctor is ok as you didn't provide the code.

我不确定你的副本ctor是否正常，因为你没有提供代码。

Here is another approach (insert-function renamed to insert_list_copy_at):

这是另一种方法（插入函数重命名为insert_list_copy_at）：

class Node
{
public:
    Node() : next(nullptr) {};

    Node(const Node& other)
    {
        next = other.next;

        // Copy other members
    };

    Node* next;

    // other members
};

class List
{
public:
    Node* head;
    Node* tail;

    void insert_list_copy_at(const List& otherList, int index);
    void insert_node_at(Node* node, int index);
};

void List::insert_node_at(Node* node, int index)
{
    if (index == 0)
    {
        node->next = head;
        head=node;
        if (tail == nullptr)
        {
            tail=node;
        }
            return;
    }

    if (head == nullptr) {/*throw exception - index out of range*/};

    Node* t = head;
    while(index>1)
    {
        t = t->next;
        if (t == nullptr) {/*throw exception - index out of range*/};
    }

    // Insert node after t
    node->next = t->next;
    t->next = node;
    if (tail == t)
    {
        tail=node;
    }
}

void List::insert_list_copy_at(const List& otherList, int index)
{
    Node* t = otherList.head;
    while(t != nullptr)
    {
        // Create new node as copy of node in otherList
        Node* tmp = new Node(*t);

        // Insert in this list
        insert_node_at(tmp, index);

        // Increment index and pointer
        index++;
        t = t->next;
    }
}

BTW - consider using std::vector instead of creating your own list.

顺便说一句 - 考虑使用std :: vector而不是创建自己的列表。

#1