C ++：尝试将新节点添加到链接列表会产生“线程1：EXC_BAD_ACCESS（代码= 1，地址= 0x0）”错误

I'm writing a program for a homework assignment that creates and manipulates a linked list. I am encountering an "EXC_BAD_ACCESS" error with the Node::SetData function in Node.cpp, as well as with a line in List::Add_End in List.cpp (specifically "current->SetData(data);") and a line in main.cpp for some reason (specifically "// Add_End nodes to the list"). I assume that once the Node::SetData error is fixed, these other errors will resolve themselves.

我正在编写一个用于创建和操作链表的家庭作业的程序。我在Node.cpp中遇到Node :: SetData函数的“EXC_BAD_ACCESS”错误,以及List.cpp中的List :: Add_End中的一行(特别是“current-> SetData(data);”)和由于某种原因,在main.cpp中的行(特别是“// Add_End节点到列表”)。我假设一旦Node :: SetData错误得到修复,这些其他错误将自行解决。

After searching through Stack Overflow and Google, I cannot determine why this error is occurring. I thought this question (New to C++, "EXC_BAD_ACCESS" error I don't understand) would help, but I'm still having issues.

在搜索Stack Overflow和Google之后,我无法确定为什么会出现此错误。我认为这个问题(C ++新手,我不明白的“EXC_BAD_ACCESS”错误)会有所帮助,但我仍然遇到问题。

What coding error(s) have I made?

我做了什么编码错误?

main.cpp

#include <iostream>
#include <cstddef>
using namespace std;

#include "List.h"

int main()
{
    // New list
    List list;
    Node *answer;

    // Add_End nodes to the list
    list.Add_End(111);
    list.Print();
    list.Add_End(222);
    list.Print();
    list.Add_End(333);
    list.Print();
    list.Add_End(444);
    list.Print();
    list.Add_End(555);
    list.Print();

    // Delete nodes from the list
    list.Delete(444);
    list.Print();
    list.Delete(333);
    list.Print();
    list.Delete(222);
    list.Print();
    list.Delete(555);
    list.Print();
    list.Delete(111);
    list.Print();

    cout << "Testing Add_Front: and others" << endl;
    list.Add_Front(888);
    list.Print();
    list.Add_Front(999);
    list.Print();
    list.Add_Front(49);
    list.Print();

    cout << "Checking find function" << endl;
    answer = list.Find(888);
    cout << "Value for node returned by find function call with 888 is " << answer->Data() << "." << endl;
    cout << "Checking find function" << endl;
    answer = list.Find(999);
    cout << "Value for node returned by find function call with 888 is " << answer->Data() << "." << endl;
    cout << "Checking find function" << endl;
    answer = list.Find(49);
    cout << "Value for node returned by find function call with 888 is " << answer->Data() << "." << endl;
    cout << "Call find function with value not in list." << endl;
    answer = list.Find(7);
    if (answer == NULL)
    {
        cout << "returned null pointer since 7 not found" << endl;
    }
    else
    {
        cout << "in else of answer == NULL where Value for node returned by find function call with 7 is " << answer->Data() << "." << endl;
    }

    cout << "testing delete_front: " << endl;
    list.Delete_Front();
    list.Print();
    cout << "testing delete_end: " << endl;

    list.Delete_End();
    list.Print();

    return 0;
}

List.h

#ifndef LIST_H
#define LIST_H

#include <cstddef>

#include "Node.h"

class List
{
private:
    Node* head;

public:
    List();
    void Add_End(int data);
    void Delete(int data);
    void Delete_Front();
    void Add_Front(int data);
    void Delete_End();
    Node* Find(int data);
    void Print();    
};

#endif

List.cpp

#include <iostream>
#include <cstddef>
using namespace std;

#include "List.h"

List::List()
{
    head = NULL;
    return;
}

void List::Add_End(int data)
{
    Node* current;
    Node* newEnd = new Node();

    for (current = head; current != NULL; current = current->Next())
    {}
    current->SetData(data);
    current->SetNext(newEnd);
    newEnd->SetData(NULL);
    newEnd->SetNext(NULL);

    return;
}

void List::Delete(int data) {
    /*
     FILL IN CODE (will do later)
     */


    return;
}

void List::Delete_Front()
{
    /*
     FILL IN CODE (will do later)
     */

    return;
}

void List::Add_Front(int data)
{
    Node* newNode = new Node();
    newNode->SetData(data);
    newNode->SetNext(head);
    head = newNode;
    return;
}

void List::Delete_End()
{
    if (head == NULL)
    {
        cout << "List has no member so cannot delete end" << endl;
        return;
    }

    // check if one in length
    if (head->Next() == NULL)
    {
        head = NULL;
        return;
    }
    // 2 or greater in length

    Node* current;
    Node* prev;
    prev = head;
    for (current = head->Next(); current->Next() != NULL; current = current->Next())
    {
        prev = current;
    }
    prev->SetNext(NULL);
    return;
}

Node* List::Find(int data)
{
    Node* current;

    for (current = head; current != NULL && current->Data() != data; current = current->Next())
    {}
    if(current == NULL)
    {
        cout << "Did not find " << data << "." << endl;
        return NULL;
    }
    else // found
    {
        cout << "Found " << data << "." << endl;
        return current;
    }
}

void List::Print()
{
    Node* current;
    for (current = head; current != NULL; current = current->Next())
    {
        cout << current->Data() << " ";
    }
    cout << endl;

    return;
}

Node.h

#ifndef NODE_H
#define NODE_H

class Node
{
private:
    int data;
    Node* next;

public:
    Node();
    void SetData(int aData);
    void SetNext(Node* aNext);
    int Data();
    Node* Next();
};

#endif

Node.cpp

#include <cstddef>

#include "Node.h"

Node::Node()
{
    this->SetData(NULL);
    this->SetNext(NULL);
    return;
}

void Node::SetData(int aData)
{
    this->data = aData;
    return;
}

void Node::SetNext(Node* aNext)
{
    this->next = aNext;
    return;
}

int Node::Data()
{
    return data;
}

Node* Node::Next()
{
    return next;
}

2 个解决方案

#1

While calling current->SetData for the first time (see below) current is NULL and so you get page fault when accessing it (page fault is the error modern OSes give you if you try to access unallocated memory. Under wndows the term usually is Access violation.)

在第一次调用current-> SetData时(见下文),当前为NULL并因此在访问时出现页面错误(页面错误是现代操作系统在您尝试访问未分配的内存时给出的错误。在wndows下,该术语通常是访问违规。)

void List::Add_End(int data)
{
    Node* current;
    Node* newEnd = new Node();

    for (current = head; current != NULL; current = current->Next())
    {}
    current->SetData(data);
    current->SetNext(newEnd);
    newEnd->SetData(NULL);
    newEnd->SetNext(NULL);

    return;
}

#2

I managed to correct the code, so I'll explain what I did in case someone else encounters the same problem.

我设法纠正了代码,所以我会解释我做了什么以防其他人遇到同样的问题。

ALTERATION: Before I explain the fix, let me explain a change I made. The last node of the linked list can hold a data value itself, not just NULL (i.e., the last node's data does not need to be NULL, but its next should be NULL), so I thought this would be better. The code reflects this in every location where it matters, such as the List::Add_End(int data) function.

更改:在我解释修复之前,让我解释一下我所做的改变。链表的最后一个节点本身可以​​保存一个数据值,而不仅仅是NULL(即,最后一个节点的数据不需要为NULL,但其下一个应该是NULL),所以我认为这样会更好。代码在每个重要的位置反映了这一点,例如List :: Add_End(int data)函数。

---

THE FIX: I modified the List constructor to create a head node for the list. So, the linked list will always have at least one node, even if the list is empty. I will explain how the program discerns between empty and nonempty lists later.

修复:我修改了List构造函数,为列表创建了一个头节点。因此,即使列表为空,链表也始终至少有一个节点。我将解释程序如何在以后清空空和非空列表之间进行辨别。

Here is the original constructor:

这是原始构造函数:

    List::List()
    {
        head = NULL;
        return;
    }

Here is the new constructor:

这是新的构造函数:

    List::List()
    {
        Node* headNode = new Node();
        head = headNode;

        return;
    }

Why make this modification? As far as I can tell, I encountered the EXC_BAD_ACCESS error because the List::Add_End(int data) function tried to manipulate the linked list's head as if it were a node object, when actually it was not. (I believe this is what marom meant in his answer to this question.) This is why I altered the coding such that the list always contains a head node, even when the list is empty.

为什么要进行此修改?据我所知,我遇到了EXC_BAD_ACCESS错误,因为List :: Add_End(int data)函数试图操纵链表的头部,好像它是一个节点对象,实际上它不是。 (我相信这是marom在回答这个问题时的意思。)这就是为什么我改变了编码,使得列表总是包含一个头节点,即使列表是空的。

Discerning between empty and nonempty lists. I altered the Node constructor to set data to the integer -1122334455, instead of NULL like I originally did. So, if the list is empty, then head->Data() (i.e., the head node's data) is -112233455 and head->Next() (i.e., the head node's next) is NULL. The downside to this approach is that it's impossible to have a one-item list containing the integer -1122334455, but I figure this number is likely to be unneeded. As long as the list has at least two items, head->Data() can be -1122334455.

区分空列表和非空列表。我改变了Node构造函数,将数据设置为整数-1122334455,而不像我最初那样设置NULL。因此,如果列表为空,则head-> Data()(即头节点的数据)为-112233455,head-> Next()(即头节点的下一个)为NULL。这种方法的缺点是,不可能有一个包含整数-1122334455的单项列表,但我认为这个数字很可能是不需要的。只要列表至少有两个项目,head-> Data()可以是-1122334455。

---

NEW CODE: The rest of the code reflects these modifications. Since I only made significant changes to List.cpp and Node.cpp, I have reproduced only them below. The other three program files are essentially unchanged. FYI, there are many redundant return's and this's that I didn't bother to delete.

新代码:其余代码反映了这些修改。由于我只对List.cpp和Node.cpp进行了重大更改,因此我在下面只复制了它们。其他三个程序文件基本没有变化。仅供参考,有许多冗余的返回,这是我没有费心去删除。

List.cpp

    #include <iostream>
    #include <cstddef>
    using namespace std;

    #include "List.h"

    // -1122334455 is an arbitrary integer that is likely to never be needed by the user

    List::List()
    {
        Node* headNode = new Node();
        head = headNode;

        return;
    }

    Node* List::Add_End(int data)
    {
        // if list is empty (i.e., list has only head node with data == -1122334455 & next == NULL)
        if (head->Data() == -1122334455 && head->Next() == NULL)
        {
            head->SetData(data);

            return head;
        }
        // if list is nonempty
        else
        {
            Node* current;
            Node* newEnd = new Node();

            for (current = head; current->Next() != NULL; current = current->Next())
            {}
            current->SetNext(newEnd);
            newEnd->SetData(data);
            newEnd->SetNext(NULL);

            return newEnd;
        }
    }

    void List::Delete(int data)
    {
        Node* prev;
        Node* current;

        // if list is empty
        if (head->Data() == -1122334455 && head->Next() == NULL)
        {
            cout << "Cannot delete this datum because list is empty." << endl;
            return;
        }

        // if list contains 1 element
        if (head->Data() == data && head->Next() == NULL)
        {
            head->SetData(-1122334455);
            return;
        }
        else if (head->Data() != data && head->Next() == NULL)
        {
            cout << "Datum not found in list." << endl;
            return;
        }

        // if list contains 2 or more elements
        prev = head;

        for (current = head->Next(); current->Data() != data && current->Next() != NULL; current = current->Next())
        {
            prev = prev->Next();
        }
        if (current->Data() == data && current->Next() != NULL)
        {
            prev->SetNext(current->Next());
            delete current;
            return;
        }
        else if (current->Data() == data && current->Next() == NULL)
        {
            prev->SetNext(NULL);
            delete current;
            return;
        }
        else
        {
            cout << "Datum not found in list." << endl;
            return;
        }
    }

    void List::Delete_Front()
    {
        Node* origHead = head;
        Node* newHead = head->Next();

        head = newHead;
        delete origHead;

        return;
    }

    void List::Add_Front(int data)
    {
        // if list is empty
        if (head->Data() == -1122334455 && head->Next() == NULL)
        {
            head->SetData(data);
            return;
        }

        // if list is nonempty
        Node* newNode = new Node();
        newNode->SetData(data);
        newNode->SetNext(head);
        head = newNode;
        return;
    }

    void List::Delete_End()
    {
        if (head->Data() == -1122334455 && head->Next() == NULL)
        {
            cout << "List has no member so cannot delete end" << endl;
            return;
        }

        // check if one in length
        else if (head->Data() != -1122334455 && head->Next() == NULL)
        {
            head->SetData(-1122334455);
            return;
        }

        // 2 or greater in length
        else
        {
            Node* current;
            Node* prev;
            prev = head;
            for (current = head->Next(); current->Next() != NULL; current = current->Next())
            {
                prev = current;
            }
            prev->SetNext(NULL);
            return;
        }
    }

    Node* List::Find(int data)
    {
        Node* current;

        for (current = head; current != NULL && current->Data() != data; current = current->Next())
        {}
        if (current == NULL)
        {
            cout << "Did not find " << data << "." << endl;
            return NULL;
        }
        else // found
        {
            cout << "Found " << data << "." << endl;
            return current;
        }
    }

    void List::Print()
    {
        if (head->Data() == -1122334455 && head->Next() == NULL)
        {
            cout << "List is empty." << endl;
            return;
        }

        Node* current;
        for (current = head; current != NULL; current = current->Next())
        {
            cout << current->Data() << " ";
        }
        cout << endl;

        return;
    }

Node.cpp

    #include <cstddef>

    #include "Node.h"

    Node::Node()
    {
        // -1122334455 is an arbitrary integer that is likely to never be needed by the user
        this->SetData(-1122334455);
        this->SetNext(NULL);
        return;
    }

    void Node::SetData(int aData)
    {
        this->data = aData;
        return;
    }

    void Node::SetNext(Node* aNext)
    {
        this->next = aNext;
        return;
    }

    int Node::Data()
    {
        return this->data;
    }

    Node* Node::Next()
    {
        return this->next;
    }