Коллекция (абстрактный тип данных) - Collection (abstract data type)

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

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

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

Линейные коллекции

Смотрите также: Линейная структура данных

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

Списки

Основная статья: Список (абстрактный тип данных)

В списке важен порядок элементов данных. Разрешены повторяющиеся элементы данных. Примерами операций со списками являются поиск элемента данных в списке и определение его местоположения (если оно присутствует), удаление элемента данных из списка, добавление элемента данных в список в определенном месте и т. Д. операции в списке должны включать добавление элементов данных на одном конце и удаление элементов данных на другом, это обычно будет называться очередь или же ФИФО. Если основными операциями являются добавление и удаление элементов данных только на одном конце, это будет называться куча или же LIFO. В обоих случаях элементы данных поддерживаются в коллекции в одном и том же порядке (если они не удаляются и не вставляются в другое место), поэтому это особые случаи коллекции списков. Другие специализированные операции со списками включают сортировку, где, опять же, большое значение имеет порядок элементов данных.

Стеки

Основная статья: Стек (абстрактный тип данных)

Стек - это структура данных LIFO с двумя основными операциями: толкать, который добавляет элемент в «верх» коллекции, и поп, который удаляет верхний элемент.

Очереди

Основная статья: Очередь (абстрактный тип данных)

Приоритетные очереди

Основная статья: Приоритетная очередь

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

Двусторонние очереди

Основная статья: Двусторонняя очередь

Двусторонние очереди с приоритетом

Основная статья: Двусторонняя приоритетная очередь

Ассоциативные коллекции

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

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

Наборы

Основная статья: Набор (информатика)

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

Мультимножества

Основная статья: Мультимножество (абстрактный тип данных)

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

Ассоциативные массивы

Основная статья: Ассоциативный массив

В ассоциативном массиве (или карте, словаре, таблице поиска), как и в словаре, поиск по ключ (как слово) дает ценить (как определение). Значение может быть ссылкой на составную структуру данных. А хеш-таблица обычно является эффективной реализацией, поэтому этот тип данных часто называют «хешем».

Графики

Основная статья: График (абстрактный тип данных)

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

Деревья

Основная статья: Дерево (структура данных)

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

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

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

Абстрактная концепция против реализации

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

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

Реализации

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

Рекомендации

  1. ^ Фейерштейн, Стивен; Прибыл, Билл; Доус, Чип (2007) [1999]. «Коллекции в PL / SQL». Карманный справочник по языку Oracle PL / SQL. Карманный справочник (4-е изд.). Севастополь, Калифорния: O'Reilly Media, Inc., стр. 63. ISBN  9780596551612. Получено 2017-06-26. Коллекции реализованы как ТИПЫ. Как и в случае с любым типом, определяемым программистом, вы должны сначала определить тип; тогда вы можете объявить экземпляры этого типа.

внешняя ссылка