链表中的运行时错误

Question

我一直在使用链表（出于学习目的，使用 class）。这次我决定使用 friend 函数。该程序生成 2 linked 列表对象并调用 friend void mergeAlternate(LL LL1, LL LL2); 函数。（LL 是我的 class 的名字）

mergeAlternate 函数从两个 linked 列表中获取节点并交替放置它们。例如：

LL1: 1->2->3

LL2: 4->5->6

答案：1->4->2->5->3->6

这是我的代码::

#include <iostream>
using namespace std;

class Node {
public:
    int data;
    Node *next;
    Node(int data) {
        this->data = data;
        this->next = NULL;
    }
};
class LL {
private:
    Node *head;
public:

    LL() : head(NULL) {
        createLL();
    }

    void printLL(Node *head) {
        if(head == NULL)
            head = this->head;
        Node *temp = head;
        while (temp != NULL) {
            cout << temp->data << "-->";
            temp = temp->next;
        }
        cout << "NULL" << endl;
    }

    void createLL() {
        head = new Node(2);
        head->next = new Node(7);
        head->next->next = new Node(8);
        head->next->next->next = new Node(1);
        head->next->next->next->next = new Node(4);
        head->next->next->next->next->next = new Node(9);
    }

    friend void mergeAlternate(LL LL1, LL LL2);

    ~LL() {
        Node *temp = NULL;
        while (head != NULL) {
            temp = head;
            head = head->next;
            delete temp;
        }
    }
};

void mergeAlternate(LL LL1, LL LL2) {
        Node *head1 = LL1.head, *head2 = LL2.head;
        Node *temp1, *temp2;
        while ((head1 != NULL) && (head2 != NULL)) {
            temp1 = head1->next;
            temp2 = head2->next;
            head1->next = head2;
            head2->next = temp1;
            if (temp1 == NULL)
                break;
            head1 = temp1;
            head2 = temp2;
        }
        if (head2 != NULL) {
            head1->next = head2;
        }
        LL2.head = NULL;
        LL1.printLL(LL1.head);
    }

int main() {
LL newLL, newLL2;
    newLL2.printLL(NULL);
    mergeAlternate(newLL, newLL2);
    newLL2.printLL(NULL);
}

我有一个 printLL 函数用于打印 linked 列表。

问题是，在我的 mergeAlternate 中，我按值传递了 2 个链表。因此，我希望链表 newLL 和 newLL2 保持不变。但是，在 main 中，在执行 mergeAlternate 之后，当我打印链表时，出现运行时错误，并打印出类似这样的内容。

155672576-->155672672-->155672592-->155672688-->155672608-->155672704-->155672624-->155672720-->155672640-->155672736-->155672656-->NULL

尽管我希望再次打印相同的输入链表。为什么会这样？？有什么我想念的吗？感谢您的帮助:)

ideone link :: http://ideone.com/apRCTw

Answer 1

您按值传递 LL，但由于 class 只是指向您的节点的指针的包装器，您实际上将两个指针传递给各自 lists.And 的头部由于您随后要修改这些指针指向的节点，这些节点与调用者的 LL 实例正在使用的节点相同，因此您实际上是在修改调用者 lists.Just 考虑有多少个不同的节点调用你的函数后应该有：

LL1: 1->2->3
LL2: 4->5->6
Ans: 1->4->2->5->3->6

这是 LL1 和 LL2 的 3 个节点的 2 倍加上答案的 6 个节点，总共有 12 个节点。在构建 LL1 和 LL2 时分配了 6 个节点。

要解决此问题，您需要在合并列表时制作（分配）节点副本，仅修改这些副本。

Answer 2

我看到了一些陷阱。

您正在按值传递列表，包括它们的内部指针。这意味着通过在函数内复制创建的列表指向与原始列表相同的数据结构。因此，您在函数内部所做的任何更改都将在原始列表中 "seen"。

您完成了列表中的 "shallow copy"。您没有复制列表的内容。

要解决此问题，您需要对列表进行深度复制。创建一个创建列表副本的函数，或者在迭代节点时创建节点的副本。不过，第一个解决方案可能不太容易出错。

Answer 3

您的函数 void mergeAlternate(LL LL1, LL LL2) 创建了两个新的局部变量 LL 和 LL2，其成员 head 也将指向与 newLL 和 newLL 相同的内存地址newLL2分别指向。因为LL1和LL2是函数的局部变量，所以当函数结束时，会调用它们各自的析构函数。根据你的析构函数定义：

~LL() {
    Node *temp = NULL;
    while (head != NULL) {
        temp = head;
        head = head->next;
        delete temp;
    }
}

它将取消分配 LL1 和 LL2 的 Nodes，但是因为这些是与 newLL 和 newLL2 相同的内存地址意味着当函数结束时，这最后两个对象将在其成员 head 和后续引用中具有垃圾值，这将在尝试访问它们的值时导致错误。

链表中的运行时错误

Runtime error in Linked List

c++

runtime-error