Лекция 6. Лекция 6 Абстрактные типы данных Список Стек Очередь Ассоциативный массив
 Скачать 391.5 Kb.
|
Структуры и алгоритмы обработки данных1 Июнь, 2022 АТД Лекция 6 Абстрактные типы данных
Стек Очередь Ассоциативный массив Очередь с приоритетом Список1 Июнь, 2022 АТД это абстрактный тип данных, представляющий собой упорядоченный набор значений, в котором некоторое значение может встречаться более одного раза. Экземпляр списка является компьютерной реализацией математического понятия конечной последовательности — кортежа. Экземпляры значений, находящихся в списке, называются элементами списка (англ. item, entry либо element); если значение встречается несколько раз, каждое вхождение считается отдельным элементом. Связный список1 Июнь, 2022 АТД структура данных, состоящая из узлов, каждый из которых содержит как собственно данные, так и одну или две ссылки («связки») на следующий и/или предыдущий узел списка Односвязный список (Однонаправленный связный список)1 Июнь, 2022 АТД В односвязном списке можно передвигаться только в сторону конца списка. Узнать адрес предыдущего элемента, опираясь на содержимое текущего узла невозможно. Двусвязный список (Двунаправленный связный список)1 Июнь, 2022 АТД По двусвязному списку можно передвигаться в любом направлении Кольцевой связный список1 Июнь, 2022 АТД В каждом кольцевом списке есть указатель на первый элемент. В этом списке константы NULL не существует. Свойства связных списков1 Июнь, 2022 АТД Размер списка — количество элементов в нём, исключая последний «нулевой» элемент, являющийся по определению пустым списком. Тип элементов — тот самый тип , над которым строится список; все элементы в списке должны быть этого типа. Отсортированность — список может быть отсортирован в соответствии с некоторыми критериями сортировки (например, по возрастанию целочисленных значений, если список состоит из целых чисел). Возможности доступа — некоторые списки в зависимости от реализации могут обеспечивать программиста селекторами для доступа непосредственно к заданному по номеру элементу. Сравниваемость — списки можно сравнивать друг с другом на соответствие, причём в зависимости от реализации операция сравнения списков может использовать разные технологии. Недостатки1 Июнь, 2022 АТД сложность определения адреса элемента по его индексу (номеру) в списке на поля-указатели (указатели на следующий и предыдущий элемент) расходуется дополнительная память (в массивах, например, указатели не нужны) работа со списком медленнее, чем с массивами, так как к любому элементу списка можно обратиться, только пройдя все предшествующие ему элементы элементы списка могут быть расположены в памяти разреженно, что окажет негативный эффект на кэширование процессора над связными списками гораздо труднее (хотя и в принципе возможно) производить параллельные векторные операции, такие как вычисление суммы Достоинства1 Июнь, 2022 АТД лёгкость добавления и удаления элементов размер ограничен только объёмом памяти и разрядностью указателей динамическое добавление и удаление элементов Стек1 Июнь, 2022 АТД Стек (англ. stack — стопка) — структура данных, в которой доступ к элементам организован по принципу LIFO (англ. last in — first out, «последним пришёл — первым вышел»). Добавление элемента, называемое также проталкиванием (push), возможно только в вершину стека (добавленный элемент становится первым сверху). Удаление элемента, называемое также выталкиванием (pop), тоже возможно только из вершины стека, при этом второй сверху элемент становится верхним Представления стэков1 Июнь, 2022 АТД 1 Июнь, 2022 АТД МАССИВ_ВВЕРХ: представляет стек посредством массива representation и целого числа count, с диапазоном значений от 0 (для пустого стека) до capacity - размера массива representation, элементы стека хранятся в массиве и индексируются от 1 до count. МАССИВ_ВНИЗ: похож на МАССИВ_ВВЕРХ, но элементы помещаются в конец стека, а не в начало. Здесь число, называемое free, является индексом верхней свободной позиции в стеке или 0, если все позиции в массиве заняты и изменяется в диапазоне от capacity для пустого стека до 0 для заполненного. Элементы стека хранятся в массиве и индексируются от capacity до free +1. СПИСОЧНОЕ: при списочном представлении каждый элемент стека хранится в ячейке с двумя полями: item, содержащем сам элемент, и previous, содержащем указатель на ячейку с предыдущим элементом. Для этого представления нужен также указатель last на ячейку, содержащую вершину стека. Очередь1 Июнь, 2022 АТД Очередь — структура данных с дисциплиной доступа к элементам «первый пришёл — первый вышел» (FIFO, First In — First Out). Добавление элемента (принято обозначать словом enqueue — поставить в очередь) возможно лишь в конец очереди, выборка — только из начала очереди (что принято называть словом dequeue — убрать из очереди), при этом выбранный элемент из очереди удаляется. Способы реализации очереди1 Июнь, 2022 АТД Массив Первый способ представляет очередь в виде массива и двух целочисленных переменных start и end. Связный список Реализация на двух стеках Ассоциативный массив1 Июнь, 2022 АТД Ассоциативный массив (словарь) — абстрактный тип данных (интерфейс к хранилищу данных), позволяющий хранить пары вида «(ключ, значение)» и поддерживающий операции добавления пары, а также поиска и удаления пары по ключу Реализации ассоциативного массива1 Июнь, 2022 АТД Самая простая реализация может быть основана на обычном массиве, элементами которого являются пары (ключ, значение). Для ускорения операции поиска можно упорядочить элементы этого массива по ключу и осуществлять нахождение методом бинарного поиска. Но это увеличит время выполнения операции добавления новой пары, так как необходимо будет «раздвигать» элементы массива, чтобы в образовавшуюся пустую ячейку поместить новую запись Очередь с приоритетом1 Июнь, 2022 АТД (priority queue) — абстрактный тип данных в программировании поддерживающий три операции: InsertWithPriority: добавить в очередь элемент с нaзначенным приоритетом GetNext: извлечь из очереди и вернуть элемент с минимальным приоритетом (другие названия "PopElement(Off)" или "GetMinimum") PeekAtNext (необязательная операция): просмотреть элемент с наивысшим приоритетом без извлечения Коллекции объектов Javaреализованы различными классами пакета java.util Коллекции обладают одним важным свойством — их размер не ограничен 1 Июнь, 2022 АТД Интерфейс Collection1 Июнь, 2022 АТД Итератор - объект, абстрагирующийся за единым интерфейсом доступ к элементам коллекции. Итератор это паттерн позволяющий получить доступ к элементам любой коллекции без вникания в суть ее реализации. List - Представляет собой неупорядоченную коллекцию, в которой допустимы дублирующие значения. Иногда их называют последовательностями (sequence ). Элементы такой коллекции пронумерованы, начиная от нуля, к ним можно обратиться по индексу. Set - описывает неупорядоченную коллекцию, не содержащую повторяющихся элементов. Это соответствует математическому понятию множества (set). Queue - очередь. Сразу запоминаем как правильно произносится: Queue - Это коллекция, предназначенная для хранения элементов в порядке, нужном для их обработки. В дополнение к базовым операциям интерфейса Collection, очередь предоставляет дополнительные операции вставки, получения и контроля. 1 Июнь, 2022 АТД Реализации интерфейса ListArrayList - пожалуй самая часто используемая коллекция. ArrayList инкапсулирует в себе обычный массив, длина которого автоматически увеличивается при добавлении новых элементов. Так как ArrayList использует массив, то время доступа к элементу по индексу минимально (В отличии от LinkedList). При удалении произвольного элемента из списка, все элементы находящиеся «правее» смещаются на одну ячейку влево, при этом реальный размер массива (его емкость, capacity) не изменяется. Если при добавлении элемента, оказывается, что массив полностью заполнен, будет создан новый массив размером (n * 3) / 2 + 1, в него будут помещены все элементы из старого массива + новый, добавляемый элемент. LinkedList - Двусвязный список. Это структура данных, состоящая из узлов, каждый из которых содержит как собственно данные, так и две ссылки («связки») на следующий и предыдущий узел списка. Доступ к произвольному элементу осуществляется за линейное время (но доступ к первому и последнему элементу списка всегда осуществляется за константное время — ссылки постоянно хранятся на первый и последний, так что добавление элемента в конец списка вовсе не значит, что придется перебирать весь список в поисках последнего элемента). В целом же, LinkedList в абсолютных величинах проигрывает ArrayList и по потребляемой памяти и по скорости выполнения операций. 1 Июнь, 2022 АТД Реализации интерфейса SetHashSet - коллекция, не позволяющая хранить одинаковые объекты(как и любой Set). HashSet инкапсулирует в себе объект HashMap (то-есть использует для хранения хэш-таблицу). Хеш-таблица хранит информацию, используя так называемый механизм хеширования, в котором содержимое ключа используется для определения уникального значения, называемого хеш-кодом. Этот хеш-код затем применяется в качестве индекса, с которым ассоциируются данные, доступные по этому ключу. Преобразование ключа в хеш-код выполняется автоматически — вы никогда не увидите самого хеш-кода. Также ваш код не может напрямую индексировать хеш-таблицу. Выгода от хеширования состоит в том, что оно обеспечивает константное время выполнения методов add(), contains(), remove() и size() , даже для больших наборов. LinkedHashSet - поддерживает связный список элементов набора в том порядке, в котором они вставлялись. Это позволяет организовать упорядоченную итерацию вставки в набор. То есть, когда идет перебор объекта класса LinkedHashSet с применением итератора, элементы извлекаются в том порядке, в каком они были добавлены. TreeSet - коллекция, которая хранит свои элементы в виде упорядоченного по значениям дерева. TreeSet инкапсулирует в себе TreeMap, который в свою очередь использует сбалансированное бинарное красно-черное дерево для хранения элементов. TreeSet хорош тем, что для операций add, remove и contains потребуется гарантированное время log(n). 1 Июнь, 2022 АТД Реализации интерфейса QueuePriorityQueue - единственная прямая реализация интерфейса Queue (не считая LinkedList, который больше является списком, чем очередью). Эта очередь упорядочивает элементы либо по их натуральному порядку (используя интерфейс Comparable), либо с помощью интерфейса Comparator, полученному в конструкторе. 1 Июнь, 2022 АТД Реализации интерфейса MapИнтерфейс Map соотносит уникальные ключи со значениями. Ключ — это объект, который используется для последующего извлечения данных. Задавая ключ и значение, можно помещать значения в объект карты. После того как это значение сохранено, можно получить его по ключу. 1 Июнь, 2022 АТД HashMap — основан на хэш-таблицах, реализует интерфейс Map (что подразумевает хранение данных в виде пар ключ/значение). Ключи и значения могут быть любых типов, в том числе и null. Данная реализация не дает гарантий относительно порядка элементов с течением времени. LinkedHashMap - расширяет класс HashMap. Он создает связный список элементов в карте, расположенных в том порядке, в котором они вставлялись. Это позволяет организовать перебор карты в порядке вставки. То есть, когда происходит итерация по коллекционному представлению объекта класса LinkedHashMap, элементы будут возвращаться в том порядке, в котором они вставлялись. Вы также можете создать объект класса LinkedHashMap, возвращающий свои элементы в том порядке, в котором к ним в последний раз осуществлялся доступ. TreeMap - расширяет класс AbstractMap и реализует интерфейс NavigatebleMap. Он создает коллекцию, которая для хранения элементов применяет дерево. Объекты сохраняются в отсортированном порядке по возрастанию. Время доступа и извлечения элементов достаточно мало, что делает класс TreeMap блестящим выбором для хранения больших объемов отсортированной информации, которая должна быть быстро найдена. WeakHashMap - коллекция, использующая слабые ссылки для ключей (а не значений). Слабая ссылка (англ. weak reference) — специфический вид ссылок на динамически создаваемые объекты в системах со сборкой мусора. Отличается от обычных ссылок тем, что не учитывается сборщиком мусора при выявлении объектов, подлежащих удалению. Ссылки, не являющиеся слабыми, также иногда именуют «сильными». 1 Июнь, 2022 АТД 1 Июнь, 2022 АТД 1 Июнь, 2022 АТД КОНЕЦ ЛЕКЦИИ |