В информатике неявная структура данных или структура данных, эффективная с точки зрения пространства, — это структура данных , которая хранит очень мало информации, кроме основных или требуемых данных: структура данных, требующая низких накладных расходов . Они называются «неявными», потому что положение элементов несет смысл и взаимосвязь между элементами; это контрастирует с использованием указателей для указания явной взаимосвязи между элементами. Определения «низких накладных расходов» различаются, но обычно означают постоянные накладные расходы; в нотации big O — накладные расходы O (1). Менее ограничительное определение — это сжатая структура данных , которая допускает большие накладные расходы.
Неявная структура данных — это структура с постоянными накладными расходами O (1) (выше нижней границы теории информации ).
Исторически Манро и Суванда (1980) определили неявную структуру данных (и алгоритмы, действующие на нее) как такую, «в которой структурная информация неявно содержится в способе хранения данных, а не явно в указателях». Они несколько расплывчаты в определении, определяя ее наиболее строго как один массив, с сохранением только размера (единичное число накладных расходов), [1] или более свободно как структуру данных с постоянными накладными расходами ( O (1) ). [2] Это последнее определение сегодня более стандартно, и еще более свободное понятие структуры данных с непостоянными, но небольшими накладными расходами o (n) сегодня известно как сжатая структура данных , как определено Якобсоном (1988); Манро и Суванда (1980) называли ее полунеявной . [3]
Фундаментальное различие существует между статическими структурами данных (только для чтения) и динамическими структурами данных (которые могут быть изменены). Простые неявные структуры данных, такие как представление отсортированного списка в виде массива, могут быть очень эффективны как статическая структура данных, но неэффективны как динамическая структура данных из-за неэффективности операций модификации (таких как вставка в случае отсортированного списка).
Тривиальным примером неявной структуры данных является структура данных массива , которая является неявной структурой данных для списка и требует только постоянных накладных расходов длины; в отличие от связанного списка , который имеет указатель, связанный с каждым элементом данных, который явно задает связь от одного элемента к другому. Аналогично, строка с нулевым завершением является неявной структурой данных для строки (списка символов). Они считаются очень простыми, поскольку являются статическими структурами данных (только для чтения) и допускают только простую операцию итерации по элементам.
Аналогично просто представить многомерный массив как один одномерный массив вместе с его измерениями. Например, представление массива m × n как одного списка длины m·n вместе с числами m и n (вместо одномерного массива указателей на каждый одномерный подмассив). Элементы не обязательно должны быть одного типа, и таблица данных (список записей ) может быть аналогично представлена неявно как плоский (одномерный) список вместе с длиной каждого поля , пока каждое поле имеет одинаковый размер (поэтому можно использовать один размер для каждого поля, а не для каждой записи).
Менее тривиальный пример — представление отсортированного списка отсортированным массивом , что позволяет выполнять поиск за логарифмическое время с помощью бинарного поиска . Сравните с деревом поиска , в частности с бинарным деревом поиска , которое также позволяет выполнять поиск за логарифмическое время, но требует указателей. Отсортированный массив эффективен только как статическая структура данных, поскольку изменение списка происходит медленно — в отличие от бинарного дерева поиска — но не требует дополнительных затрат пространства, как у дерева.
Важным примером неявной структуры данных является представление идеального бинарного дерева в виде списка в порядке возрастания глубины, то есть корень, первый левый потомок, первый правый потомок, первый левый потомок первого левого потомка и т. д. Такое дерево встречается, в частности, в диаграмме предков до заданной глубины, а неявное представление известно как Ahnentafel (таблица предков).
Это можно обобщить до полного двоичного дерева (где последний уровень может быть неполным), что дает самый известный пример неявной структуры данных, а именно двоичную кучу , которая является неявной структурой данных для очереди с приоритетом . Это сложнее, чем предыдущие примеры, поскольку допускает множественные операции и является эффективной динамической структурой данных (она допускает эффективную модификацию данных): не только top , но также insert и pop .
Более сложные неявные структуры данных включают в себя кучу (двухродительскую кучу).
Тривиальные примеры списков или таблиц значений относятся к доисторическим временам, в то время как исторически нетривиальные неявные структуры данных относятся по крайней мере к Ahnentafel, который был введен Михаэлем Эйтцингером в 1590 году для использования в генеалогии. В формальной информатике первой неявной структурой данных обычно считается отсортированный список, используемый для бинарного поиска, который был введен Джоном Мочли в 1946 году в лекциях школы Мура , первом в истории наборе лекций, касающихся любой компьютерной темы. [4] [5] Двоичная куча была введена Уильямсом (1964) для реализации пирамидальной сортировки . [5] Понятие неявной структуры данных было формализовано Манро и Сувандой (1980) в рамках введения и анализа кучи . [5]
См. публикации Эрве Бренниманна, Дж. Яна Манро и Грега Фредериксона.
![{\displaystyle [0,N]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/703d57dca548a7f9d927247c2a27b67666aebdd5)