C++中的简单链表

2022-01-01 00:00:00 linked-list c++

我即将创建一个可以插入并显示到现在的链接:

I am about to create a linked that can insert and display until now:

struct Node {
    int x;
    Node *next;
};

这是我的初始化函数，只会为第一个 Node 调用:

This is my initialisation function which only will be called for the first Node:

void initNode(struct Node *head, int n){
    head->x = n;
    head->next = NULL;
}

添加Node，我认为我的链表不能正常工作的原因在于这个函数:

To add the Node, and I think the reason why my linked list isn't working correct is in this function:

void addNode(struct Node *head, int n){
    struct Node *NewNode = new Node;
    NewNode-> x = n;
    NewNode -> next = head;
    head = NewNode;
}

我的main函数:

int _tmain(int argc, _TCHAR* argv[])
{
    struct Node *head = new Node;

    initNode(head, 5);
    addNode(head, 10);
    addNode(head, 20);
    return 0;
}

让我按照我认为可行的方式运行该程序.首先，我将头部 Node 初始化为 Node，如下所示:

Let me run the program as I think it works. First I initialise the head Node as a Node like this:

head = [ 5 |  NULL ]

然后我添加一个 n = 10 的新节点并将 head 作为我的参数传递.

Then I add a new node with n = 10 and pass head as my argument.

新节点 = [ x |next ] next 指向头部.然后我更改 head 指向 NewNode 的位置，因为 NewNode 现在是 LinkedList 中的第一个节点.

NewNode = [ x | next ] where next points at head. And then I change the place where head is pointing to NewNode, since NewNode is the first Node in LinkedList now.

为什么这不起作用?我将不胜感激任何可以使我朝着正确方向前进的提示.我觉得 LinkedList 有点难理解.

Why isn't this working? I would appreciate any hints that could make me move in the right direction. I think LinkedList is a bit hard to understand.

当我打印这个时，它只返回 5:

When I'm printing this, it only returns 5:

推荐答案

这是我能想到的最简单的例子，没有经过测试.请注意，这使用了一些不好的做法，并且与您通常使用 C++ 的方式不同(初始化列表、声明和定义的分离等).但这些是我无法在此涵盖的主题.

This is the most simple example I can think of in this case and is not tested. Please consider that this uses some bad practices and does not go the way you normally would go with C++ (initialize lists, separation of declaration and definition, and so on). But that are topics I can't cover here.

#include <iostream>
using namespace std;

class LinkedList{
    // Struct inside the class LinkedList
    // This is one node which is not needed by the caller. It is just
    // for internal work.
    struct Node {
        int x;
        Node *next;
    };

// public member
public:
    // constructor
    LinkedList(){
        head = NULL; // set head to NULL
    }

    // destructor
    ~LinkedList(){
        Node *next = head;
        
        while(next) {              // iterate over all elements
            Node *deleteMe = next;
            next = next->next;     // save pointer to the next element
            delete deleteMe;       // delete the current entry
        }
    }
    
    // This prepends a new value at the beginning of the list
    void addValue(int val){
        Node *n = new Node();   // create new Node
        n->x = val;             // set value
        n->next = head;         // make the node point to the next node.
                                //  If the list is empty, this is NULL, so the end of the list --> OK
        head = n;               // last but not least, make the head point at the new node.
    }

    // returns the first element in the list and deletes the Node.
    // caution, no error-checking here!
    int popValue(){
        Node *n = head;
        int ret = n->x;

        head = head->next;
        delete n;
        return ret;
    }

// private member
private:
    Node *head; // this is the private member variable. It is just a pointer to the first Node
};

int main() {
    LinkedList list;

    list.addValue(5);
    list.addValue(10);
    list.addValue(20);

    cout << list.popValue() << endl;
    cout << list.popValue() << endl;
    cout << list.popValue() << endl;
    // because there is no error checking in popValue(), the following
    // is undefined behavior. Probably the program will crash, because
    // there are no more values in the list.
    // cout << list.popValue() << endl;
    return 0;
}

我强烈建议您阅读一些有关 C++ 和面向对象编程的内容.一个好的起点可能是这样的:http://www.galileocomputing.de/1278?GPP=opoo

I would strongly suggest you to read a little bit about C++ and Object oriented programming. A good starting point could be this: http://www.galileocomputing.de/1278?GPP=opoo

添加了弹出功能和一些输出.如您所见，程序推送了 3 个值 5、10、20，然后将它们弹出.之后顺序颠倒了，因为这个列表在堆栈模式下工作(LIFO，后进先出)

added a pop function and some output. As you can see the program pushes 3 values 5, 10, 20 and afterwards pops them. The order is reversed afterwards because this list works in stack mode (LIFO, Last in First out)

相关文章