Все ли типы данных сводятся к узлам с указателями?

Массив или вектор - это просто последовательность значений. Они, безусловно, могут быть реализованы с помощью связанного списка. Это просто набор узлов с указателями на следующий узел.

Стеки и очереди - это два абстрактных типа данных, которые обычно преподаются на курсах Intro CS. Где-то в классе ученикам часто приходится реализовывать стеки и очереди, используя связанный список в качестве базовой структуры данных, что означает, что мы вернулись к той же идее «набора узлов».

Приоритетные очереди могут быть созданы с помощью кучи. Куча может рассматриваться как дерево с минимальным значением в корне. Деревья всех видов, включая BST, AVL, кучи можно рассматривать как совокупность узлов, соединенных ребрами. Эти узлы связаны между собой, где один узел указывает на другой.

Кажется, что каждая концепция данных всегда может сводиться к узлам с указателями на другой подходящий узел. Это правильно? Если это так просто, почему в учебниках не объясняется, что данные - это просто набор узлов с указателями? Как нам перейти от узлов к двоичному коду?

Ну, это в основном то, к чему сводятся все структуры данных. Данные с подключениями. Узлы все искусственные - на самом деле они не существуют физически. Вот где вступает бинарная часть. Вы должны создать несколько структур данных в C ++ и проверить, где ваши объекты попадают в память. Это может быть очень интересно узнать о том, как данные размещаются в памяти.

Основная причина стольких различных структур заключается в том, что все они специализируются на том или ином предмете. Например, как правило, быстрее выполнять итерацию по вектору, а не по связанному списку, из-за того, как страницы извлекаются из памяти. Связанный список лучше хранить для типов большего размера, потому что векторы должны выделять дополнительное пространство для неиспользуемых слотов (это требуется при проектировании вектора).

Как примечание, интересная структура данных, которую вы можете рассмотреть, - это Hash Table. Он не совсем соответствует системе узлов и указателей, которую вы описываете.

TL; DR: контейнеры в основном все узлы и указатели, но имеют очень специфическое использование и лучше для чего-то и хуже для других.

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

О, дорогой нет. Ты делаешь мне больно.

Как я пытался объяснить в другом месте («В чем разница между двоичным деревом поиска и двоичной кучей?»). »), Даже для фиксированной структуры данных есть несколько уровней, чтобы понять это.

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

А также, например, для графиков, которые, безусловно, выглядят как узлы и указатели (ребра), у вас есть два основных представления: массив смежности и списки смежности. Не все указатели я представляю.

Когда вы действительно пытаетесь понять структуры данных, вы должны изучить их достоинства и недостатки. Иногда представление использует массив для эффективности (пространства или времени), иногда есть указатели (для гибкости). Это верно даже тогда, когда у вас есть хорошие «консервированные» реализации, такие как C ++ STL, потому что там вы также можете иногда выбирать базовые представления. Там всегда есть компромисс.

$f:\mathbb{R} \rightarrow \mathbb{R}$

Никто не ожидает, что вы скажете все это просто для определения непрерывной функции, иначе никто не сможет выполнить какую-либо работу вообще. Мы просто «верим», что кто-то сделал скучную работу для нас.

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

Мы используем абстракции, потому что они освобождают наш разум от тривиальных вопросов, позволяя нам говорить о более сложных проблемах. Вполне разумно просто «довериться» работе этих структур: скручивание в каждую деталь - это, если у вас нет особых причин для этого, бесполезное упражнение, которое ничего не добавляет к вашему аргументу.

Вот контрпример: в λ-исчислении каждый тип данных сводится к функциям. λ-исчисление не имеет узлов или указателей, единственное, что у него есть - это функции, поэтому все должно быть реализовано с использованием функций.

Это пример кодирования логических значений в виде функций, написанных на ECMAScript:

const T   = (thn, _  ) => thn,
      F   = (_  , els) => els,
      or  = (a  , b  ) => a(a, b),
      and = (a  , b  ) => a(b, a),
      not = a          => a(F, T),
      xor = (a  , b  ) => a(not(b), b),
      iff = (cnd, thn, els) => cnd(thn, els)();

И это список минусов:

const cons = (hd, tl) => which => which(hd, tl),
      first  = list => list(T),
      rest   = list => list(F);

Натуральные числа могут быть реализованы как функции итератора.

Набор - это то же самое, что и его характеристическая функция (т. Е. containsМетод).

Обратите внимание, что вышеприведенное церковное кодирование логических выражений на самом деле представляет собой то, как условные выражения реализованы в ОО-языках, таких как Smalltalk, которые не имеют логических выражений, условных выражений или циклов в качестве языковых конструкций и реализуют их исключительно как библиотечную функцию. Пример в Scala:

sealed abstract trait Boolean {
  def apply[T, U <: T, V <: T](thn: => U)(els: => V): T
  def ∧(other: => Boolean): Boolean
  def ∨(other: => Boolean): Boolean
  val ¬ : Boolean

  final val unary_! = ¬
  final def &(other: => Boolean) = ∧(other)
  final def |(other: => Boolean) = ∨(other)
}

case object True extends Boolean {
  override def apply[T, U <: T, V <: T](thn: => U)(els: => V): U = thn
  override def ∧(other: => Boolean) = other
  override def ∨(other: => Boolean): this.type = this
  override final val ¬ = False
}

case object False extends Boolean {
  override def apply[T, U <: T, V <: T](thn: => U)(els: => V): V = els
  override def ∧(other: => Boolean): this.type = this
  override def ∨(other: => Boolean) = other
  override final val ¬ = True
}

object BooleanExtension {
  import scala.language.implicitConversions
  implicit def boolean2Boolean(b: => scala.Boolean) = if (b) True else False
}

import BooleanExtension._

(2 < 3) { println("2 is less than 3") } { println("2 is greater than 3") }
// 2 is less than 3

Многие (большинство?) Структуры данных построены из узлов и указателей. Массивы являются еще одним критическим элементом некоторых структур данных.

В конечном счете, каждая структура данных - это просто набор слов в памяти или просто набор битов. Важно то, как они структурированы и как мы их интерпретируем и используем.

Реализация структур данных всегда сводится к узлам и указателям, да.

Но зачем останавливаться на достигнутом? Реализация узлов и указателей сводится к битам.

Реализация битов сводится к электрическим сигналам, магнитным накопителям, возможно, оптоволоконным кабелям и т. Д. (Одним словом, физика.)

Это сокращение до абсурда : «Все структуры данных сводятся к узлам и указателям». Это правда, но это относится только к реализации.

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

Мы можем пойти немного дальше, если поймем, что единой разделительной линии между моделью и реализацией. Это похоже (если не идентично) на понятие «слои абстракции».

На данном уровне абстракции слои «ниже» вас (слои, на которых вы строите) являются просто «деталями реализации» для абстракции или модели, к которой вы обращаетесь.

Однако нижние слои абстракции сами по себе имеют детали реализации.

Если вы читаете руководство по программному обеспечению, вы узнаете об уровне абстракции, «представленном» этим программным обеспечением, на котором вы можете создавать свои собственные абстракции (или просто выполнять такие действия, как отправка сообщений).

Если вы изучите детали реализации реализации части программного обеспечения, вы узнаете, как создатели подкрепили построенные ими абстракции. «Детали реализации» могут включать, помимо прочего, структуры данных и алгоритмы.

Однако вы не рассматриваете измерение напряжения как часть «деталей реализации» для какого-либо конкретного программного обеспечения, даже если это лежит в основе того, как «биты», «байты» и «память» фактически работают на физическом компьютере.

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

Большая часть реального понимания системы заключается в понимании того, как слои абстракции сочетаются друг с другом. Поэтому важно понимать, как реализованы структуры данных . Но тот факт , что они будут реализованы, не означает , что абстракция структур данных не существует.

Массив или вектор - это просто последовательность значений. Они, безусловно, могут быть реализованы с помощью связанного списка. Это просто набор узлов с указателями на следующий узел.

Массив или вектор могут быть реализованы с помощью связанного списка, но почти никогда не должно быть.

Это потому, что доступ к $n$-ый элемент в связанном списке требует прохождения цепочки $n$ указатели, и, следовательно, требует $\Theta(n)$время. Основанная на дереве реализация (все еще сделанная только из узлов и указателей) является немного более эффективной, требующей только$\Theta(\log n)$ время, чтобы получить доступ к произвольному листу, но это все еще далеко от $\Theta(1)$время доступа обеспечивается с использованием фактического массива (то есть последовательного блока оперативной памяти). Кроме того, в ЦП доступ к фактическому массиву гораздо проще реализовать и быстрее выполнить, а его хранение занимает меньше памяти из-за того, что не нужно тратить пространство на указатели между отдельными узлами.

Конечно, у реальных физических массивов есть и свои отрицательные стороны: $\Theta(n)$ время для вставки нового элемента, что может сделать связанный список $\Theta(1)$время, если у вас уже есть указатель на соседний элемент. Вставки в конце физического массива могут быть амортизированы до$\Theta(1)$в среднем, за счет не более чем постоянного коэффициента дополнительной памяти, просто округляя фактический выделенный размер массива до, например, ближайшей степени 2. Но если вам нужно сделать много вставок и / или удалений элементы в середине вашего списка, физический массив не может быть лучшей реализацией для вашей структуры данных. Довольно часто, однако, вы можете заменить вставки и удаления на свопы, которые стоят дешево.

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

На самом деле, изо всех сил, я не могу представить себе какую-либо общую структуру данных, которая могла бы нуждаться в чем-то еще, хотя в некоторых случаях можно потратить немного пространства или времени, выйдя за пределы этой парадигмы. В качестве иллюстративного примера такого случая рассмотрим связанный список XOR , который позволяет реализовать двусторонний перемещаемый связанный список, используя (асимптотически) не больше места, чем односторонний связанный список, заменив отдельный следующий и предыдущий узел указатели по битовому XOR, а также имеет несколько других удобных функций (таких как$\Theta(1)$операция разворота). На практике, однако, эти функции редко бывают достаточно полезными для преодоления его недостатков, которые включают дополнительную сложность реализации и несовместимость со стандартными схемами сборки мусора .

Если это так просто, почему в учебниках не объясняется, что данные - это просто набор узлов с указателями?

Потому что это не то, что означает «данные». Вы смешиваете абстрактные идеи с реализациями. «Данные» - это очень абстрактная идея: это просто другое название слова «информация». Группа связанных узлов с указателями (иначе говоря, «связанная структура данных») - гораздо более конкретная идея: это особый способ представления и организации информации.

Некоторые абстракции данных очень хорошо подходят для «связанных» реализаций. Существует не так много хороших способов реализовать разветвленную природу полностью общего дерева без использования явных узлов и указателей (или некоторого изоморфизма узлов и указателей). Но тогда есть другие абстракции, которые вы никогда бы не реализовали, используя узлы и указатели. Числа с плавающей точкой приходят на ум.

Стеки и очереди падают где-то посередине. Бывают случаи, когда имеет смысл делать связанную реализацию стека. В других случаях гораздо разумнее использовать массив и один «указатель стека».