我如何在 C++ 中创建一个列表?

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

如何在 C++ 中创建列表?我需要它来创建一个链表.我该怎么做呢?有没有我可以遵循的好的教程或示例?

How can I create a list in C++? I need it to create a linked list. How would I go about doing that? Are there good tutorials or examples I could follow?

推荐答案

我认为您知道 C++ 已经有一个链表类，并且您想实现自己的，因为您想学习如何去做.

I take it that you know that C++ already has a linked list class, and you want to implement your own because you want to learn how to do it.

首先，阅读为什么我们使用数组而不是其他数据结构?，其中包含基本数据结构的一个很好的答案.然后想想如何用C++对它们建模:

First, read Why do we use arrays instead of other data structures? , which contains a good answer of basic data-structures. Then think about how to model them in C++:

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

基本上这就是实现列表所需的全部内容！(一个非常简单的).然而它没有抽象，你必须每手链接项目:

Basically that's all you need to implement a list! (a very simple one). Yet it has no abstractions, you have to link the items per hand:

Node a={1}, b={20, &a}, c={35, &b} d={42, &c};

现在，你有一个节点的链表，全部分配在堆栈上:

Now, you have have a linked list of nodes, all allocated on the stack:

d -> c -> b -> a
42   35   20   1

下一步是编写一个指向起始节点的包装类List，并允许根据需要添加节点，跟踪列表的头部(以下非常简化):

Next step is to write a wrapper class List that points to the start node, and allows to add nodes as needed, keeping track of the head of the list (the following is very simplified):

class List {
    struct Node {
        int data;
        Node * next;
    };

    Node * head;

public:
    List() {
        head = NULL;
    }

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

    void add(int value) {
        Node * n = new Node;
        n->data = value;
        n->next = head;
        head = n;
    }

    // ...
};

下一步是使列表成为模板，以便您可以填充其他值(不仅仅是整数).

Next step is to make the List a template, so that you can stuff other values (not only integers).

如果您熟悉智能指针，则可以将使用的原始指针替换为智能指针.我经常发现人们向初学者推荐智能指针.但在我看来，您应该首先了解为什么需要智能指针，然后再使用它们.但这要求您首先需要了解原始指针.否则，您会使用一些神奇的工具，却不知道为什么需要它.

If you are familiar with smart pointers, you can then replace the raw pointers used with smart pointers. Often i find people recommend smart pointers to starters. But in my opinion you should first understand why you need smart pointers, and then use them. But that requires that you need first understand raw pointers. Otherwise, you use some magic tool, without knowing why you need it.

相关文章