В информатике , А коллекция или контейнер представляет собой группировка некоторого переменного числа элементов данных (возможно , нулевой) , которые разделяют некоторые значения для решаемых задачи и необходимости работать на вместе в каком - то контролируемый образе. Как правило, элементы данных будут одного типа или, на языках, поддерживающих наследование, производными от некоторого общего типа предка. Коллекция - это концепция, применимая к абстрактным типам данных , и не предписывает конкретную реализацию в качестве конкретной структуры данных , хотя часто существует традиционный выбор (см. Контейнер для обсуждения теории типов ).
Примеры коллекций включают списки , множества , мультимножества , деревья и графы .
Массивы (или таблицы) фиксированного размера обычно не считаются коллекцией, потому что они содержат фиксированное количество элементов данных, хотя обычно они играют роль в реализации коллекций. Массивы переменного размера обычно считаются коллекциями. [ необходима цитата ]
Линейные коллекции
Многие коллекции определяют конкретный линейный порядок с доступом к одному или обоим концам. Фактическая структура данных, реализующая такую коллекцию, не обязательно должна быть линейной - например, очередь с приоритетами часто реализуется в виде кучи , которая является своего рода деревом. Важные линейные коллекции включают:
- списки ;
- стеки ;
- очереди ;
- приоритетные очереди ;
- двусторонние очереди ;
- двусторонние приоритетные очереди .
Списки
В списке важен порядок элементов данных. Разрешены повторяющиеся элементы данных. Примерами операций со списками являются поиск элемента данных в списке и определение его местоположения (если оно есть), удаление элемента данных из списка, добавление элемента данных в список в определенном месте и т. Д. операции в списке должны включать добавление элементов данных на одном конце и удаление элементов данных на другом, это обычно будет называться очередью или FIFO . Если основными операциями являются добавление и удаление элементов данных только на одном конце, это будет называться стеком или LIFO . В обоих случаях элементы данных поддерживаются в коллекции в одном и том же порядке (если они не удаляются и не вставляются в другое место), поэтому это особые случаи коллекции списков. Другие специализированные операции со списками включают сортировку, где, опять же, большое значение имеет порядок элементов данных.
Стеки
Стек - это структура данных LIFO с двумя основными операциями: push , которая добавляет элемент в «верх» коллекции, и pop , которая удаляет верхний элемент.
Очереди
Приоритетные очереди
В очереди с приоритетом следы минимального или максимального элемента данных в коллекции сохраняются в соответствии с некоторым критерием упорядочения, а порядок других элементов данных не имеет значения. Можно представить себе очередь с приоритетом как список, который всегда хранит минимум или максимум в начале, в то время как остальные элементы хранятся в сумке.
Двусторонние очереди
Двусторонние очереди с приоритетом
Ассоциативные коллекции
Вместо этого другие коллекции можно интерпретировать как своего рода функцию: при наличии ввода коллекция дает результат. Важные ассоциативные коллекции включают:
Набор можно интерпретировать как специализированный мультимножество, которое, в свою очередь, является специализированным ассоциативным массивом, в каждом случае путем ограничения возможных значений, считая набор представленным его индикаторной функцией .
Наборы
В наборе порядок элементов данных не имеет значения (или не определен), но дублирование элементов данных не допускается. Примерами операций над наборами являются добавление и удаление элементов данных и поиск элемента данных в наборе. Некоторые языки поддерживают наборы напрямую. В других случаях наборы могут быть реализованы с помощью хеш-таблицы с фиктивными значениями; только ключи используются для представления набора.
Мультимножества
В мультимножестве (или сумке), как и в наборе, порядок элементов данных не имеет значения, но в этом случае разрешены повторяющиеся элементы данных. Примерами операций с мультимножествами являются добавление и удаление элементов данных и определение количества дубликатов определенного элемента данных в мультимножестве. Мультимножества можно преобразовать в списки действием сортировки.
Ассоциативные массивы
В ассоциативном массиве (или карте, словаре, таблице поиска), как и в словаре, поиск по ключу (например, слову) предоставляет значение (например, определение). Значение может быть ссылкой на составную структуру данных. Хэш - таблица , как правило , эффективная реализация, и , таким образом , этот тип данных часто называют как «хэш».
Графики
На графике элементы данных связаны с одним или несколькими другими элементами данных в коллекции и чем-то похожи на деревья без концепции корня или родительско-дочерних отношений, так что все элементы данных являются одноранговыми. Примерами операций с графами являются обходы и поиск, которые исследуют ассоциации элементов данных в поисках определенного свойства. Графики часто используются для моделирования реальных ситуаций и решения связанных проблем. Примером является протокол связующего дерева , который создает графическое (или сетчатое) представление сети передачи данных и определяет, какие ассоциации между коммутирующими узлами необходимо разорвать, чтобы превратить его в дерево и, таким образом, предотвратить циклическое перемещение данных.
Деревья
В дереве, которое является особым типом графа, корневой элемент данных связал с ним некоторое количество элементов данных, которые, в свою очередь, связали с ними некоторое количество других элементов данных в том, что часто рассматривается как отношение родитель-потомок . Каждый элемент данных (кроме корня) имеет единственного родителя (корень не имеет родителя) и некоторое количество потомков, возможно, ноль. Примерами операций с деревьями являются добавление элементов данных для поддержания определенного свойства дерева для выполнения сортировки и т. Д. И обходы для посещения элементов данных в определенной последовательности.
Коллекции деревьев могут использоваться для естественного хранения иерархических данных, которые представлены в виде дерева, например, системы меню и файлы в каталогах в системе хранения данных.
Специализированные деревья используются в различных алгоритмах. Например, сортировка кучи использует разновидность дерева, называемого кучей .
Абстрактная концепция против реализации
Как описано здесь, коллекция и различные виды коллекций являются абстрактными понятиями. В литературе существует значительная путаница между абстрактными концепциями информатики и их конкретной реализацией на различных языках или типах языков. Утверждения о том, что коллекции, списки, наборы, деревья и т. Д. Являются структурами данных, абстрактными типами данных или классами, следует читать с учетом этого. Коллекции - это прежде всего абстракции, которые полезны при формулировании решений вычислительных проблем. В этом свете они сохраняют важные связи с лежащими в основе математическими концепциями, которые могут быть потеряны, когда основное внимание уделяется реализации.
Например, приоритетная очередь часто реализуется как куча, в то время как ассоциативный массив часто реализуется как хэш-таблица, поэтому эти абстрактные типы часто упоминаются в этой предпочтительной реализации как «куча» или «хеш», хотя это не совсем правильно.
Реализации
Некоторые коллекции могут быть примитивными типами данных на языке, например списками, в то время как более сложные коллекции реализованы как составные типы данных в библиотеках, иногда в стандартной библиотеке . Примеры включают:
- C ++: известный как « контейнеры », реализованный в стандартной библиотеке C ++ и более ранней стандартной библиотеке шаблонов.
- Java: реализовано в структуре коллекций Java
- Oracle PL / SQL реализует коллекции как типы, определяемые программистом [1]
- Python: некоторые встроены, другие реализованы в библиотеке коллекций
Рекомендации
- ^ Feuerstein, Стивен ; Прибыл, Билл; Доус, Чип (2007) [1999]. «Коллекции в PL / SQL». Карманный справочник по языку Oracle PL / SQL . Карманный справочник (4-е изд.). Севастополь, Калифорния: O'Reilly Media, Inc., стр. 63. ISBN 9780596551612. Проверено 26 июня 2017 .
Коллекции реализованы как ТИПЫ. Как и в случае с любым типом, определяемым программистом, вы должны сначала определить тип; тогда вы можете объявить экземпляры этого типа.
Внешние ссылки
- Коллекции Apache Commons .
- AS3Commons Collections Framework Реализация наиболее распространенных коллекций в ActionScript3.
- CollectionSpy - профилировщик для Java Collections Framework.
- Гуава .
- Библиотека Mango Java .