Войти
В информатике контейнер collection или - это группировка некоторого переменного числа элементов данных (возможно, нуля), которые имеют некоторое общее значение для решаемой проблемы и должны обрабатываться вместе контролируемым образом. Как правило, элементы данных будут одного типа или, на языках, поддерживающих наследование, производными от некоторого общего типа предка. Коллекция - это концепция, применимая к абстрактным типам данных, и не предписывает конкретную реализацию как конкретную структуру данных , хотя часто существует традиционный выбор (см. Контейнер для обсуждения теории типов ).
Примеры коллекций включают списки, наборы, мультимножества, деревья и графики.
Фиксированный -size массивы (или таблицы) обычно не считаются коллекцией, потому что они содержат фиксированное количество элементов данных, хотя обычно они играют роль в реализации коллекций. Массивы переменного размера обычно считаются коллекциями.
Многие коллекции определяют конкретный линейный порядок с доступом к одному или обоим концам. Фактическая структура данных, реализующая такую коллекцию, не обязательно должна быть линейной - например, очередь с приоритетами часто реализуется как куча, которая является своего рода деревом. Важные линейные коллекции включают:
в виде списка, порядок элементов данных имеет значение. Разрешены повторяющиеся элементы данных. Примеры операций со списками: поиск элемента данных в списке и определение его местоположения (если оно есть), удаление элемента данных из списка, добавление элемента данных в список в определенном месте и т. Д. операции в списке должны включать добавление элементов данных на одном конце и удаление элементов данных на другом, это обычно будет называться очередью или FIFO. Если основными операциями являются добавление и удаление элементов данных только на одном конце, он будет называться стеком или LIFO. В обоих случаях элементы данных поддерживаются в коллекции в одном и том же порядке (если они не удаляются и не вставляются в другое место), поэтому это особые случаи коллекции списков. Другие специализированные операции со списками включают сортировку, где, опять же, большое значение имеет порядок элементов данных.
Стек - это структура данных LIFO с двумя основными операциями: push, которая добавляет элемент в «верх» коллекции, и pop, которая удаляет верхний элемент.
В приоритетной очереди сохраняются треки минимального или максимального элемента данных в коллекции в соответствии с некоторым критерием упорядочения и порядком других элементов данных не имеет значения. Можно думать о очереди с приоритетом как о списке, который всегда хранит минимум или максимум в начале, а остальные элементы хранятся в сумке.
Вместо этого другие коллекции можно интерпретировать как своего рода функцию: учитывая ввод, коллекция дает результат. К важным ассоциативным коллекциям относятся:
Набор можно интерпретировать как специализированный мультимножество, которое, в свою очередь, является специализированным ассоциативным массивом, в каждом случае путем ограничения возможных значений - учитывая набор, представленный его функцией индикатора .
В наборе порядок элементов данных не имеет значения (или не определен), но дублирование элементов данных не допускается. Примерами операций над наборами являются добавление и удаление элементов данных и поиск элемента данных в наборе. Некоторые языки поддерживают наборы напрямую. В других случаях наборы могут быть реализованы с помощью хэш-таблицы с фиктивными значениями; только ключи используются для представления набора.
В мультимножестве (или сумке), как и в наборе, порядок элементов данных не имеет значения, но в этом случае разрешены повторяющиеся элементы данных. Примерами операций с мультимножествами являются добавление и удаление элементов данных и определение количества дубликатов определенного элемента данных в мультимножестве. Мультимножества могут быть преобразованы в списки действием сортировки.
В ассоциативном массиве (или карте, словаре, таблице поиска), как и в словаре, поиск по ключу (например, слову) предоставляет значение (например, определение). Значение может быть ссылкой на составную структуру данных. Хеш-таблица обычно является эффективной реализацией, поэтому этот тип данных часто называют «хеш-таблицей».
В графе элементы данных связаны с одним или несколькими другими элементами данных в коллекции и чем-то похожи на деревья без концепции корня или отношений родитель-потомок, так что все элементы данных равноправны. Примерами операций с графами являются обходы и поиск, которые исследуют ассоциации элементов данных в поисках определенного свойства. Графики часто используются для моделирования реальных ситуаций и решения связанных проблем. Примером является протокол связующего дерева, который создает графическое (или сетчатое) представление сети данных и определяет, какие ассоциации между коммутирующими узлами необходимо разорвать, чтобы превратить его в дерево и, таким образом, предотвратить передачу данных. вокруг в петлях.
В дереве, которое представляет собой особый вид графа, корневой элемент данных связал с ним некоторое количество элементов данных, которые, в свою очередь, связали с ними некоторое количество других данных. элементы в том, что часто рассматривается как родительско-дочерние отношения. Каждый элемент данных (кроме корня) имеет единственного родителя (корень не имеет родителя) и некоторое количество потомков, возможно, ноль. Примерами операций с деревьями являются добавление элементов данных для поддержания определенного свойства дерева для выполнения сортировки и т. Д. И обходы для посещения элементов данных в определенной последовательности.
Древовидные коллекции могут использоваться для естественного хранения иерархических данных, которые представлены в древовидной форме, например, системы меню и файлы в каталогах в системе хранения данных.
Специализированные деревья используются в различных алгоритмах. Например, сортировка кучи использует своего рода дерево, называемое кучей.
Как описано здесь, коллекция и различные виды коллекций являются абстрактные понятия. В литературе существует значительная путаница между абстрактными концепциями информатики и их конкретной реализацией на различных языках или типах языков. Утверждения о том, что коллекции, списки, наборы, деревья и т. Д. Являются структурами данных, абстрактными типами данных или классами, следует читать с учетом этого. Коллекции - это прежде всего абстракции, которые полезны при формулировании решений вычислительных проблем. В этом свете они сохраняют важные связи с лежащими в основе математическими концепциями, которые могут быть потеряны, когда акцент делается на реализации.
Например, приоритетная очередь часто реализуется как куча, в то время как ассоциативный массив часто реализуется как хэш-таблица, поэтому эти абстрактные типы часто упоминаются в этой предпочтительной реализации как «куча» или "хеш", хотя это не совсем правильно.
Некоторые коллекции могут быть примитивными типами данных на языке, например списками, в то время как более сложные коллекции реализованы как составные типы данных в библиотеках, иногда в стандартной библиотеке . Примеры включают:
