c++ - 指针可以是数据结构吗？

Question

指针可以被认为是一种高效的语义数据结构吗？它如何与链表、哈希、队列、堆栈叠加？

Answer 1

不，指针只是一种类型，而不是结构。有一些结构的实现是类型（std::vector, std::map, ...），但指针不是。

它们通常在您枚举的结构的实现内部使用，但就其本身而言，指针不是结构。

Answer 2

指针是一种数据类型，而不是数据结构（尽管一些术语相当松散的书籍会将诸如指针之类的基本类型定义为更大数据结构集的元素；无论如何，指针肯定不是抽象数据结构的示例.)

更相关的是，大多数 C++ 实现的抽象数据结构（如链表、队列、堆栈、树等）都使用指针作为数据成员；也就是说，指针将构成实现的一部分；它们不是实现本身。

例如，如果您正在考虑实现自己的链表，您可能会选择双重链接版本，其中列表中的每个元素都由包含指向前一个和下一个节点的指针的节点表示：

template <typename T>
class DLList
{
public:
    // Lots of things
private:
    Node* _head; // Pointer to the head of the list
    Node* _tail; // Pointer to the tail of the list
};

您的节点可能会像这样实现：

template <typename T>
struct Node {
    Node* _prev;
    Node* _next;
    T     _data;
};

Answer 3

数据结构是一种在计算机中存储和组织数据的特殊方式，以便可以有效地使用它。指针确实是一种非常有效的存储和组织数据的方式，并且是当今寻址内存的主要方式。不过，这不是唯一的方法。例如，CPU 寄存器的寻址方式不同。所以第一个问题的答案是肯定的。

至于您的第二个问题，您无法真正将指针与哈希、队列、堆栈等高级数据结构进行比较。这是两个不同的抽象层次。更高级别的容器是使用指针等较低级别的数据结构来实现的。