如何在 C++ 中创建列表？我需要它来创建一个链表。我该怎么做呢？有没有我可以学习的好教程或示例？
jesse
问问题
184021 次
8 回答
43
我认为你知道 C++ 已经有一个链表类，并且你想实现你自己的，因为你想学习如何去做。
一、阅读为什么我们使用数组而不是其他数据结构？，其中包含基本数据结构的一个很好的答案。然后考虑如何在 C++ 中对它们进行建模：
struct Node {
int data;
Node * next;
};
基本上这就是实现列表所需的全部内容！（一个非常简单的）。然而它没有抽象，你必须手动链接项目：
Node a={1}, b={20, &a}, c={35, &b} d={42, &c};
现在，您有一个节点链表，全部分配在堆栈上：
d -> c -> b -> a
42 35 20 1
下一步是编写一个List指向起始节点的包装类，并允许根据需要添加节点，跟踪列表的头部（以下非常简化）：
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;
}
// ...
};
下一步是使 List 成为模板，以便您可以填充其他值（不仅是整数）。
如果您熟悉智能指针，则可以将使用的原始指针替换为智能指针。我经常发现人们向初学者推荐智能指针。但在我看来，您应该首先了解为什么需要智能指针，然后再使用它们。但这需要您首先了解原始指针。否则，你会使用一些神奇的工具，却不知道你为什么需要它。
于 2008-12-29T15:51:56.180 回答
22
你真的应该使用标准的 List 类。当然，除非这是一个家庭作业问题，或者您想知道 STL 是如何实现列表的。
你会通过谷歌找到很多简单的教程，比如这个。如果您想知道链表是如何“在幕后”工作的，请尝试搜索 C 列表示例/教程而不是 C++。
于 2008-12-29T15:23:41.010 回答
15
如果要使用std::list，则需要传递一个类型参数：
list<int> intList;
list<int>* intListPtr = new list<int>;
如果您想了解列表的工作原理，我建议您搜索一些 C/C++ 教程以了解该主题。下一步将学习足够的 C++ 来创建一个列表类，最后是一个列表模板类。
如果您有更多问题，请在此处提问。
于 2008-12-29T15:33:06.280 回答
9
为什么要重新发明轮子。只需使用 STL 列表容器。
#include <list>
// in some function, you now do...
std::list<int> mylist; // integer list
于 2008-12-29T15:23:56.753 回答
0
我猜这是一个家庭作业问题，所以你可能想去这里。它有一个解释链表的教程，给出了很好的伪代码，还有一个可以下载的 C++ 实现。
我建议在盲目使用实现之前通读解释并理解伪代码。如果您想继续学习 CS，这是一个您真正应该深入了解的主题。
于 2008-12-29T15:38:12.713 回答
0
于 2008-12-29T17:00:09.087 回答
0
使用C++ 模板创建列表
IE
template <class T> struct Node
{
T data;
Node * next;
};
template <class T> class List
{
Node<T> *head,*tail;
public:
void push(T const&); // push element
void pop(); // pop element
bool empty() // return true if empty.
};
然后你可以编写如下代码：
List<MyClass>;
该类型T在运行时不是动态的。它仅适用于编译时。
有关完整示例，请单击此处。
有关 C++ 模板教程，请单击此处。
于 2017-02-07T20:44:01.847 回答
-3
我们已经进入21世纪了！！不要试图实现已经存在的数据结构。尝试使用现有的数据结构。
使用 STL 或 Boost 库
于 2008-12-29T15:25:44.783 回答