无限数量的类成员变量(C++)

Question

我正在研究的C++程序旨在通过利用无限数量的节点结构指针创建一个C++自定义双链接列表类,其中包含数据值和内部两个指针.这是该计划的前提.不能使用STL LinkedList类,必须自己创建.

这就是说,如何创建一个没有特定指针数量的类成员变量？我不想在声明类时初始化50个节点,但是只使用其中的10个.同时,我不想只初始化5,然后必须使用超过5.有一种方法可以在C++中动态地将节点指针添加到链表类,当节点指针被认为是成员变量时？

我是否正确地走这条路？如果是这样,我将如何做到这一点？

Answer 1

想象一下:

+----------+-------+------+  
| Previous | Data  | Next |  
| Node     | Field | Node |  
+----------+-------+------+  

具有两个链接字段和数据字段的节点.
(绘制链接列表时总是更容易理解.)

我们可以有两个:

+----------+-------+------+  
| Previous | Data  | Next |  
| Node     | Field | Node |  
+----------+-------+------+  
    ^                  |  
    |                  V  
+----------+-------+------+  
| Previous | Data  | Next |  
| Node     | Field | Node |  
+----------+-------+------+  

Previous Node第二个节点的字段指向第一个节点.第一个节点没有前导,因此它的Previous Node字段为空.

类似地,Next Node第一节点的字段指向第二节点.第二个节点没有后继节点,因此Next Node第二个节点的字段为空.

这就是我认为需求的要求:使用指针的双向链表.

编辑1:三个节点

+----------+-------+------+  
| Previous | Data  | Next |  
| Node     | Field | Node |  
+----------+-------+------+  
    ^                  |  
    |                  V  
+----------+-------+------+  
| Previous | Data  | Next |  
| Node     | Field | Node |  
+----------+-------+------+  
    ^                  |  
    |                  V  
+----------+-------+------+  
| Previous | Data  | Next |  
| Node     | Field | Node |  
+----------+-------+------+  

如您所见,要以转发方式访问(遍历)节点,请按照一个节点的链接字段转到下一个节点.同样,要以向后的方式进行操作,请按照Previous Node链接访问节点的前任.

关于链接的一个很好的问题是,您只需要更改链接字段,以便在列表中间插入一个节点.插入过程的绘制留给读者练习.

编辑2:容器类
链表是一个容器的节点.对于简单实现,Container类不应该是Node.

Container 具有指向第一个节点的指针,并且可选地指向最后一个节点的指针:

+------+-------+  
| Last | First |  
| Node |  Node |  
+------+-------+  
  |        |  
  |        +---------------+  
  |                        |
  |                        V
  |  +----------+-------+------+  
  |  | Previous | Data  | Next |  
  |  | Node     | Field | Node |  
  |  +----------+-------+------+  
  |      ^                  |  
  |      |                  V  
  |  +----------+-------+------+  
  |  | Previous | Data  | Next |  
  |  | Node     | Field | Node |  
  |  +----------+-------+------+  
  |      ^                  |  
  |      |                  V  
  |  +----------+-------+------+  
  |  | Previous | Data  | Next |  
  +->| Node     | Field | Node |  
     +----------+-------+------+  

通过使用容器类,您无需担心使用空节点作为第一个节点.在这里,我们使用一个简单的指针指向第一个节点.此外,还有一个指向最后一个节点的指针.

指向最后一个节点的指针加快了将节点附加到列表的操作.如果没有此指针,则必须遍历所有节点才能找到最后一个节点,这需要花费大量时间.