WikiDer > Коллекция (абстрактный тип данных) - Википедия

Эта статья нужны дополнительные цитаты для проверка. Пожалуйста помоги улучшить эту статью к добавление цитат в надежные источники. Материал, не полученный от источника, может быть оспорен и удален Найдите источники: Абстрактный тип данных "Коллекция" – Новости · газеты · книги · ученый · JSTOR (Октябрь 2014 г.) (Узнайте, как и когда удалить этот шаблон сообщения)

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

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

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

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

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

• списки;
• стеки;
• очереди;
• приоритетные очереди;
• двусторонние очереди;
• двусторонние очереди приоритетов.

Списки

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

Стеки

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

Очереди

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

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

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

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

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

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

• наборы;
• мультимножества;
• ассоциативные массивы.

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

Наборы

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

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

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

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

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

Графики

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

Деревья

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

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

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

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

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

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

Реализации

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

• C ++: известный как "контейнеры", реализованный в Стандартная библиотека C ++ и раньше Стандартная библиотека шаблонов
• Java: реализовано в Фреймворк коллекций Java
• Oracle PL / SQL реализует коллекции как типы, определенные программистом^[1]
• Python: некоторые встроены, другие реализованы в коллекции библиотека

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

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

• Коллекции Apache Commons.
• Фреймворк коллекций AS3Commons Реализация наиболее распространенных коллекций в ActionScript3.
• Коллекция - Профилировщик для Java Collections Framework.
• Гуава.
• Библиотека Java Mango.