C++上的链表

Question

我在学校学习链表，但我的教授没有具体说明很多事情。。

首先，链表是内置库吗？程序员需要创建一个节点类吗？

这是我唯一的例子：

class node;
typedef node*  nodeptr;
class node {
   public:
      int number;
      nodeptr next;
 };
//--------------------------------
int main ( ) 
{
   nodeptr top;

我也不知道"typedef"是什么意思。。我知道指针是什么。如果有人能解释一下指针上的内容，我将不胜感激。。

Answer 1

首先，链表是内置库吗？

不。链表是一个数据结构。标准库在std::list和std::forward_list中有两种不同的实现方式。

---

程序员需要创建一个节点类

从上面的例子来看，你的教授似乎希望你这样做

---

我也不知道"typedef"是什么意思。

typedef是一个关键字。其目的是为现有类型指定替代名称。例如，用另一个名称(比如x(调用double，您可以使用以下内容：

typedef double x

现在您可以申报：

x name = 13.2

将被翻译成：

double name = 13.2

---

我知道指针是什么。

指针是一种数据类型，其值可以是特定内存空间的地址。在C++中，要获得特定已分配变量的地址，可以使用&x，其中x是已分配变量。打印&a将以0x...的形式打印存储器地址。如果声明类型为T*的变量，则可以使该变量包含相同类型T的变量的内存地址。指针前面的*符号表示推迟指针，这意味着获取其指向的内存空间值。

int x = 10
int* y = &x
std::cout << (*y);

在上面的例子中，输出是10。

---

如果有人能解释一下，我将不胜感激。

最简单形式的链表可以实现如下：

struct node {
      node( x, y = 0 ) : field(x), next(y) {}
      int field;
      node* next;
};

链接列表的目的是拥有一个动态容器，该容器包含完全需要的单元格。它背后的想法是，主node结构应该包含一个成员变量field，它将存储一个特定值，以及一个指向下一个node的指针，它将包含另一个值，依此类推

图形表示可以如下：

[ a:10 ] ---> [ b:3 ] ---> [ c:7 ]

在上面的例子中，节点结构是：

node c = node(7, 0);
node b = node(3, &c);
node a = node(10, &b);

其中0表示空指针，是一个特殊值，表示"不指向任何东西"。

Answer 2

typedef关键字提供了一种从现有类型创建新类型名称的方法。typedef通常用于通过创建一个新的类型名称来简化代码，该名称比原始类型的名称不那么令人困惑。

在您的情况下，现有类型node *用于创建新的类型名称nodeptr。由于typedef语句，nodeptr可以代替node *用作类型名称。

typedef node* nodeptr;

下面的node类具有数据成员next，该数据成员具有类型名称nodeptr。下一个具有node指针(AKA nodeptr(的类型。

class node 
{ public: 
     int number; 
     nodeptr next; 
};