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