简单的 C++ 链表

Simple C++ Linked List

提问by LordByron

I have plenty of previous experience with linked lists in Java, but I seem to have confused myself with this simple attempt in C++. I am getting a segmentation fault at runtime, which from what I understand has to do with assigning a null pointer, but I am at a loss for a solution.

我以前有很多在 Java 中使用链表的经验，但我似乎对 C++ 中的这种简单尝试感到困惑。我在运行时遇到分段错误，据我所知，这与分配空指针有关，但我对解决方案感到茫然。

Edit: Thank you all for the very helpful responses. The code is now working, but trying to use

编辑：感谢大家非常有帮助的回答。代码现在正在运行，但尝试使用

delete p;

在linkedList::addNode 的末尾会导致运行时出现分段错误。只是好奇是否有人知道这是为什么？

Here is my updated code:

这是我更新的代码：

#include <iostream>
using namespace std;

class Node{
    public:
        int data;
    Node * next;
    Node(int x){
        data = x;
        next = NULL;
        }
    Node(int x, Node * y){
        data = x; 
        next = y;
        }
    };


class linkedList{
Node *head;
public:
    linkedList(){
        head = NULL;
        }
    void addNode(int value){
        Node *p;
        if(head == NULL)
            head = new Node (value, NULL);
        else{
            p=head;
            while(p->next !=NULL)
                p=p->next;
            p->next = new Node (value, NULL);
            }
        }
    void print(){
        Node * p;
        p = head;
        while(p != NULL){
            cout << p->data << "\n";
            p = p->next;
            }
        }
};


int main(void){
linkedList test;
test.addNode(4);
test.addNode(76);
test.addNode(12);
test.print();
return(0);
}

回答by John Calsbeek

First, in linkedList::addNodemethod, you have the construction if (head = NULL), which will wind up assigningto head; you want the ==operator.

首先，在linkedList::addNode方法中，您有构造if (head = NULL)，它将最终分配给head; 你想要==运营商。

Second, about the line:

二、关于线路：

head = &(Node (value, NULL));

For somewhat unintuitive reasons, this won't work. You'll get a reference to a Node, but that node will go out of scope as soon as the method ends, and attempts to reference it will lead to a segmentation fault. You need to use the newoperator (same with the other similar line):

出于一些不直观的原因，这行不通。您将获得对 a 的引用Node，但该节点将在方法结束后立即超出范围，并且尝试引用它会导致分段错误。您需要使用new运算符（与其他类似行相同）：

head = new Node(value, NULL);

If you add a method for removing a node, make sure to deletethe node then—it won't get automatically garbage-collected like it will in Java.

如果添加删除节点的方法，请确保delete该节点然后 - 它不会像在 Java 中那样被自动垃圾收集。

Sidebar:Think of what happens like this: when you do Node(value, NULL), you're using a temporary variable that's declared like this:

Node hiddenTempNode(value, NULL);

This doesn't allocate space for an object anywhere except on the stack—it's very similar to allocating space for an intand a Node *on the stack as separate variables. As a result, as soon as you leave the method, the object disappears and the pointer to it will do weird things when used.

边栏：想想会发生这样的事情：当你这样做时Node(value, NULL)，你正在使用一个这样声明的临时变量：

Node hiddenTempNode(value, NULL);

这不会在堆栈上以外的任何地方为对象分配空间——这int与Node *在堆栈上为 an和 a分配空间作为单独的变量非常相似。结果，只要你离开这个方法，对象就消失了，指向它的指针在使用时会做一些奇怪的事情。

Third, beware: you may want to set next = NULLin your single-parameter constructor, to ensure that it always has a value. Similarly for your default constructor.

第三，注意：您可能希望next = NULL在单参数构造函数中进行设置，以确保它始终具有值。对于您的默认构造函数也是如此。

Fourth: your linkedList::printmethod is looping until p->nextis NULLand printing the value of p->next; those occurrences of p->nextshould probably be changed to just pif you want to get the first and last items.

第四：您的linkedList::print方法循环直到p->nextisNULL并打印p->next; 如果您想获取第一个和最后一个项目，p->next则可能应该将这些出现更改为 just pif you want to get the first and last items。

回答by jcopenha

you are taking the address of variables on the stack

您正在获取堆栈上变量的地址

head = &(Node (value, NULL));

should be changed to

应该改为

head = new Node(value, NULL);

same for the p->next code. Then you will want to delete these nodes in your destructor.

p->next 代码相同。然后你会想要在你的析构函数中删除这些节点。

As for the printing try

至于印刷尝试

while(p != NULL)
{
   cout << p->data << "\n";
   p = p->next;
}

回答by eduffy

For starters

对于初学者

if(head = NULL)

is an assignment, not a check for equality. Change it to

是一项任务，而不是检查相等性。将其更改为

if(head == NULL)

Secondly,

其次，

head = &(Node (value, NULL));

Doesn't make sense* change this to

没有意义*将其更改为

head = new Node (value, NULL);

*this actually creates a temporary object, gives you the address, then destroys that newly created object.

*这实际上创建了一个临时对象，为您提供地址，然后销毁该新创建的对象。

Thirdly,

第三，

Node(int x) { data = x; }

Leave nextwithout a value, change this line to

离开next没有值，改变这一行

Node(int x) { data = x; next = NULL; }

回答by Mehrdad Afshari

You are allocating space for nodes on stack and grabbing its address, which will go away as soon as the block ends and consequently, the address will be rendered invalid. You should allocate nodes using newoperator on the heap instead:

您正在为堆栈上的节点分配空间并获取其地址，一旦块结束，地址就会消失，因此地址将变为无效。您应该new在堆上使用运算符分配节点：

Node* node = new Node(value, NULL);

You should free everything you allocate on the heap as soon as you don't need it to prevent memory leak:

您应该在不需要时立即释放在堆上分配的所有内容以防止内存泄漏：

delete node;

回答by anand

You are not allocating memory.You should use new to allocate it.

您不是在分配内存。您应该使用 new 来分配它。

One more error in if(head = NULL) , it should be if(head == NULL)

if(head = NULL) 中的另一个错误，应该是 if(head == NULL)

void addNode(int value){
            Node *p;
            if(head == NULL)
                    head =  new Node (value, NULL);
            else{
                    p=head;
                    while(p->next !=NULL)
                            p=p->next;
                    p->next = new Node (value, NULL);
                    }
            }

回答by Ralph

I'd like to add two issues that were not mentioned, yet:

我想补充两个尚未提及的问题：

• when you 'new' objects, you must 'delete' them at some point.
• all three of your constructors should initialize both member variables.

• 当您“新建”对象时，您必须在某个时候“删除”它们。
• 所有三个构造函数都应该初始化两个成员变量。

回答by csj

Your delete statement is not actually doing any cleanup. By the time you call it p==null. If you want to cleanup the list, you will need to implement a separate method to iterate through, and delete each and every node.

您的删除语句实际上并未进行任何清理。当你称它为 p==null 时。如果要清理列表，则需要实现一个单独的方法来迭代并删除每个节点。

Something like this:

像这样的东西：

void ClearList ()
{
    Node * c = head;
    Node * n;

    while (c != NULL)
    {
        n = c->next;
        delete c;
        c = n;
    }
}

回答by DeusAduro

The code is now working, but trying to use

delete p;

at the end of linkedList::addNode results in a segmentation fault at runtime. Just curious if anyone knew why that is?

代码现在正在运行，但尝试使用

delete p;

在linkedList::addNode 的末尾会导致运行时出现分段错误。只是好奇是否有人知道这是为什么？

Well this is an issue because the purpose of the add node function was to dynamically allocate a new node at the end of the LinkedList. So you do that correctly, now by putting 'delete p;' you are deleting the newly added node (something I imagine you don't actually want). However, to answer your question which is why this causes a segmentation fault:

嗯，这是一个问题，因为添加节点函数的目的是在 LinkedList 的末尾动态分配一个新节点。所以你可以正确地做到这一点，现在通过放置 'delete p;' 您正在删除新添加的节点（我想您实际上并不想要）。但是，要回答您的问题，这就是为什么会导致分段错误：

You add a node, you tell head to point to this new node. Now you delete this new node without telling head that it should once again point to NULL. Thus next time you add a node, or try to print your list, it will immediately attempt to look at what head is pointing to, which is in fact released (deleted) memory, kaboom?

你添加一个节点，你告诉 head 指向这个新节点。现在你删除这个新节点而不告诉 head 它应该再次指向 NULL。因此，下次您添加节点或尝试打印您的列表时，它会立即尝试查看 head 指向的内容，这实际上是释放（删除）的内存，kaboom？

The correct (or at least one correct) usage of delete in your list is in a destructor, remember in C++ we always want to clean up the dynamic memory that we have allocated, your destructor might look like:

列表中 delete 的正确（或至少一种正确）用法是在析构函数中，请记住在 C++ 中我们总是希望清理我们分配的动态内存，您的析构函数可能如下所示：

~linkedList()
{
    Node* p = head;
    while ( p!=NULL )
    {
        Node* nextNode = p->next;
        delete p;
        p = nextNode;
    }
}

By using a destructor like this you guarantee that your linkedList will be cleaned up appropriately when it goes out of scope, or is deleted.

通过使用这样的析构函数，您可以保证您的linkedList 在超出范围或被删除时会被适当地清理。

回答by jalf

Solution: Don't implement your own linked list. Use the one supplied by the standard library.

解决方案：不要实现自己的链表。使用标准库提供的那个。