Реализация с помощью массива

Реализация с помощью массива: процедуру увеличения индекса на единицу определим так: i  i mod(n  1) rear front 1 ... Первый элемент front rear n Последний элемент 1 ... Последний элемент n Первый элемент а) б) Реализация очереди с помощью «циклического массива». Операции характерные для стека, дека и очереди реализуются на массиве за O(1). Отображения (Mapping) - ставит в соответствие элементам некоторого множества (D) значения другого множества (R). Основные операторы: Присвоить: установить M(d) = r; Удалить: сделать M(d) неопределенным; Вычислить(in M, in d, out r) – возвращает значение «истина», и присваивает r значение M(d), если оно определено, возвращает «ложь» в противном случае. При реализации на массиве операции можно выполнять за O(1). Для этого каждому значению аргумента должен соответствовать уникальный индекс в массиве. В ячейке по этому индексу будет либо реальное значение, либо специальное значение – признак того, что ячейка пуста. Ассоциативный массив = отображение Деревья Распространенные определения: Дерево – это связный ациклический граф. Дерево – множество, состоящее из элемента, называемого корнем, и конечного (возможно пустого) множества непересекающихся деревьев, называемых поддеревьями данного дерева. Дерево – это совокупность элементов (один из которых определен как корень), называемых узлами (или вершинами), и отношений, образующих иерархическую структуру узлов. Древовидная структура с тремя потомками root A D B C J H E F I G Реализация использующая список: root B A C D С произвольным количеством потомков. Дерево как АТД в самом общем смысле: ROOT(T) возвращает узел, являющимся корнем T; LEFTMOST__CHILD(n, Т) – возвращает самого левого сына узла n в дереве Т; RIGHT_SIBLING(n, Т). – возвращает правого брата узла n в дереве Т; PARENT(n, Т) – возвращает родителя узла n в Т; LABEL(n, Т) получения метки узла n в дереве Т . Реализация дерева с помощью массива index : 0 1 2 3 4 5 6 7 A 1 B 0 C 0 D 1 E 1 F 2 G 2 H 2 A B D E C F H G Обходы деревьев в глубину на примере двоичных деревьев выражений, метки внутренних узлов таких деревьев соответствуют операциям, метки листьев – операндам.   * A B E / C D Дерево выражений. Префиксный (прямой) обход: сначала обрабатывается текущий узел, затем его левое и правое поддеревья: +*AB-/CDE Постфиксный (обратный) обход: сначала левое и правое поддеревья текущего узла, затем сам узел: AB*CD/E-+ Инфиксный (симметричный) обход: сначала левое поддерево текущего узла, затем сам узел, затем правое поддерево: A*B+C/D-E Обход в ширину выводит узлы по уровням: A,B,C,D,E,F,G. A C B D E F G Первоначально в очередь помещается корень, затем, пока очередь не пуста, выполняются следующие действия: 1. Из очереди выталкивается очередной узел; 2. Этот узел обрабатывается; 3. В очередь добавляются сыновья обработанного узла; 4. Переход к шагу 1. Пирамида / частично упорядоченное дерево / куча - сбалансированное двоичное дерево, в котором значения дочерних узлов всегда меньше (max-heap или всегда больше min-heap) родительского. «частично»: порядок, в котором расположены потомки, не важен, важно только взаимное расположение потомков и родителя. «сбалансированное»: высоты левого и правого поддеревьев любого узла отличаются не более чем на единицу. Вставка нового и извлечение из вершины выполняются за время O(log n), где n – количество узлов. 14 3 18 21 10 а 12 8 15 7 5 10 25 2 7 4 3 1 Примеры пирамид, а – min-heap, б – max-heap. 6 б Работа с пирамидой Хранение элементов: индекс родителя для i-того элемента = i/2 левый дочерний элемент от i-того = 2*i правый дочерний элемент от i-того = (2*i + 1) Index: 0 1 2 3 4 5 11 5 8 3 4 3 8 1 2 4 3 11 5 5 4 Работа с пирамидой Хранение элементов: Index: 0 1 2 3 4 5 11 5 8 3 4 3 8 индекс родителя для i-того элемента = i/2 левый дочерний элемент от i-того = 2*i правый дочерний элемент от i-того = (2*i + 1) Добавление: 1. Добавляем в самый низ (конец массива). 2. Сравниваем добавленный элемент с родительским; если порядок верный — конец. 3. Меняем элементы местами, и переходим к шагу 2. 1 2 4 3 11 5 5 4 Работа с пирамидой Хранение элементов: Index: 0 1 2 3 4 5 11 5 8 3 4 3 8 индекс родителя для i-того элемента = i/2 левый дочерний элемент от i-того = 2*i правый дочерний элемент от i-того = (2*i + 1) Добавление: 1. Добавляем в самый низ (конец массива). 2. Сравниваем добавленный элемент с родительским; если порядок верный — конец. 3. Меняем элементы местами, и переходим к шагу 2. 1 2 4 3 11 5 5 4 Удаление: 1. Заменить корневой элемент самым нижним. 2. Сравнить значение перемещенного элемента с дочерними; если порядок верный — конец. 3. Меняем перемещенный элемент на одного из дочерних (меньший для min-heap, больший для max-heap), и переходим к шагу 2. Нагруженное дерево / префиксное дерево / бор Используется для представления множеств символьных строк. Основные операторы: INSERT(x, T), DELETE(x, T), FIND(x, T), где T – префиксное дерево, x – строка. Время выполнения операций O(|x|). Элементу множества соответствует путь, пройденный от корня к листу, либо (в других реализациях) к узлу со специальной меткой. h s e i h m s e $ $ $ $ а h s r e e i h m s s $ r s б Префиксное дерево для строк he, she, his, him, her, hers. При изображении таких деревьев принято писать символы не в узлах, а на ребрах. Узлы префиксных деревьев можно рассматривать как отображение множества символов в указатели на узел. При реализации отображения на массиве, это позволит переходить между вершинами за O(1) независимо от размера алфавита. Графы Граф слишком широкое понятие, все рассмотренные выше структуры являются частными случаями графа. Основные способы реализации графов: Многосвязные списковые структуры - на одном множестве элементов данных определено несколько списков: head I II III IV Схеме соответствует граф: I II VI III IV V V VI Список смежности 1 a 2 e 3 d 4 1 2 a 1 b 3 3 b 2 c 4 4 c 3 d 1 a 2 e d b 4 c 3 Каждой вершине соответствует список номеров связанных вершин. Список ребер Элемент содержит номера или указатели на начальную и конечную вершины, может включать метку ребра. a 1 c 2 4 3 a 2 1 b 2 3 b 4 d 4 1 e 1 d 1 c 3 4 3 2 3 1 a 2 e d b 4 c 3 Список ребер, реализованный как односвязный список. Список ребер с помощью трех массивов: start : 1 1 1 2 2 3 3 4 4 end : 2 3 4 1 3 2 4 1 3 label : a e d a b b c d c 1 a 2 e d b 4 c 3 матрица смежности 0  1 0  1 1 1 1 1 1 1  0 1  0  или $  a $  d a $ b $ e b $ c d  $ c  $  1 a 2 e d b 4 c 3 При реализации через массив: Требует (n2 ) памяти, где n - количество вершин; проверка наличия ребра O(1); чтение ~ (n2). матрица инцидентности 1 2 3 4 a 1 1 b 1 1 c 1 1 d e 1 1 0 0 0 1 1 0 Чтение O(nm), проверка существования ребра O(m), где m – количество ребер. 1 a 2 e d b 4 c 3