Могут ли указатели быть структурой данных?

Question

Может ли указатель считаться эффективной и семантической структурой данных? Как это можно связать с связанным списком, хешем, queus, stack?

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 адресуются по-разному. Поэтому ответ на первый вопрос - да.

Что касается вашего второго вопроса, вы действительно не можете сравнить указатели с структурами данных более высокого уровня, такими как хэш, очереди, стопки и другие. Это два разных уровня абстракции. Контейнеры более высокого уровня реализуются с использованием структур данных более низкого уровня, таких как указатели.