Многоключевые деревья

Б-деревья могут считаться частным случаем многоключевых деревьев (с переменным числом ключей). Ещё один такой частный случай – Декартово дерево. Это древовидная структура данных, в каждом узле которой содержится 2 ключа, по одному ключу она является двоичной пирамидой, а по второму ключу – двоичным деревом поиска.

Более простая ситуация – двухключевое дерево, которое является двоичным деревом поиска либо только по одному из ключей, либо по сумме ключей (именно в этом случае возможно повторение сумм ключей). Такое дерево может использоваться для описания рёбер графа. При этом также возможно повторение ключей в дереве, в зависимости от структуры графа.

Общее применение

управление иерархией данных;

упрощение поиска информации (см. обход дерева);

управление сортированными списками данных;

синтактический разбор арифметических выражений (англ. parsing), оптимизация программ;

в качестве технологии компоновки цифровых картинок для получения различных визуальных эффектов;

форма принятия многоэтапного решения (см. деловые шахматы).

21. Динамические типы данных – деки, стеки, очереди. Виды, структура, основные свойства. Стек - такой последовательный список с переменной длиной, включение и исключение элементов из которого выполняются только с одной стороны списка, называемого вершиной стека. Применяются и другие названия стека - магазин и очередь, функционирующая по принципу LIFO (Last - In - First- Out - "последним пришел - первым исключается"). Примеры стека: винтовочный патронный магазин, тупиковый железнодорожный разъезд для сортировки вагонов.Основные операции над стеком - включение нового элемента (английское название push - заталкивать) и исключение элемента из стека (англ. pop - выскакивать).Полезными могут быть также вспомогательные операции:• определение текущего числа элементов в стеке;• очистка стека;• неразрушающее чтение элемента из вершины стека, которое может быть реализовано, как комбинация основных операций:x:=pop(stack); push(stack,x);Некоторые авторы рассматривают также операции включения/исключения элементов для середины стека, однако структура, для которой возможны такие операции, не соответствует стеку по определению.Для наглядности рассмотрим небольшой пример, демонстрирующий принцип включения элементов в стек и исключения элементов из стека. На рис. (а,б,с) изображены состояния стека:• а). пустого;• б-г). после последовательного включения в него элементов с именами 'A', 'B', 'C';• д, е). после последовательного удаления из стека элементов 'C' и 'B';• ж). после включения в стек элемента 'D'. Как видно из рис. С.1, стек можно представить, например, в виде стопки книг (элементов), лежащей на столе. Присвоим каждой книге свое название, например A,B,C,D... Тогда в момент времени, когда на столе книг нет, про стек аналогично можно сказать, что он пуст, т.е. не содержит ни одного элемента. Если же мы начнем последова-тельно класть книги одну на другую, то получим стопку книг (допустим, из n книг), или получим стек, в котором содержится n элементов, причем вершиной его будет являться элемент n+1. Удаление элементов из стека осуществляется аналогичным образом т. е. удаляется последовательно по одному элементу, начиная с вершины, или по одной книге из стопки.Очередью FIFO (First - In - First- Out - "первым пришел - первым исключается"). называется такой последова-тельный список с переменной длиной, в котором включение элементов выполняется только с одной стороны списка (эту сторону часто называют концом или хвостом очереди), а исключение - с другой стороны (называемой началом или головой очереди). Те самые очереди к прилавкам и к кассам, которые мы так не любим, являются типичным бытовым примером очереди FIFO.Основные операции над очередью - те же, что и над стеком - включение, исключение, определение размера, очистка, неразрушающее чтение.Динамическая реализация очереди аналогична реализации стека.Дек - особый вид очереди. Дек (от англ. deq - double ended queue,т.е очередь с двумя концами) - это такой последовательный список, в котором как включение, так и исключение элементов может осуществляться с любого из двух концов списка. Частный случай дека - дек с ограниченным входом и дек с ограниченным выходом. Логическая и физическая структуры дека аналогичны логической и физической структуре кольцевой FIFO-очереди. Однако, применительно к деку целесообразно говорить не о начале и конце, а о левом и правом конце.Операции над деком:• включение элемента справа;• включение элемента слева;• исключение элемента справа;• исключение элемента слева;• определение размера;• очистка.Физическая структура дека в статической памяти идентична структуре кольцевой очереди. Динамическая реализация является очевидным объединением стека и очереди.Задачи, требующие структуры дека, встречаются в вычислительной технике и программировании гораздо реже, чем задачи, реализуемые на структуре стека или очереди. Как правило, вся организация дека выполняется программистом без каких-либо специальных средств системной поддержки.Примером дека может быть, например, некий терминал, в который вводятся команды, каждая из которых выполняется какое-то время. Если ввести следующую команду, не дождавшись, пока закончится выполнение предыдущей, то она встанет в очередь и начнет выполняться, как только освободится терминал. Это FIFO очередь. Если же дополнительно ввести операцию отмены последней введенной команды, то получается дек. 22. Работа с файлами: представление файлов, наборы функций для работы с файлами

Чтобы спроецировать данные из файла в виртуальную память процесса, Вы должны создать представление файла. Функции MapViewOfFile и MapViewOfFileEx используют дескриптор объекта "проецируемый файл", возвращенный CreateFileMapping, чтобы создать представление файла или его части в виртуальном адресном пространстве процесса. Эти функции завершаются ошибкой, если флажки доступа находятся в противоречии с флажками определенными тогда, когда CreateFileMapping создавала объект "проецируемый файл".

Функция MapViewOfFile возвращает указатель на представление файла. При помощи разыменования (получения значения объекта, к которому отсылает данный указатель) указателя в диапазоне адресов, определенных в функции MapViewOfFile, приложение может читать данные из файла и писать данные в файл. Запись в представление файла происходит в результате изменений в объекте "проецируемый файл ". Фактическая запись в файл на диске обрабатывается системой. Данные в действительности не перемещаются, когда идет запись в объект "проецируемый файл". Вместо этого, большая часть файлового ввода и вывода (I/O) данных кэшируется, чтобы улучшить общую производительность системы. Приложения могут отменить этот режим работы при помощи вызова функции FlushViewOfFile, чтобы заставить систему выполнять дисковые транзакции (групповые операции) немедленно.

Функция MapViewOfFileEx работает в точном соответствии с функцией MapViewOfFile за исключением того, что она дает возможность процессу в параметре lpvBase установить базовый адрес представления файла в его виртуальном адресном пространстве. Если по указанному адресу недостаточно места, вызов завершается ошибкой. Поэтому, если Вы должны проецировать файл, по одному и тому же адресу в несколько процессов, процессы должны договориться о соответствующем адресе:

· Windows NT/2000 или выше: Параметром lpvBase должно быть целое число, кратное степени дробления распределенной оперативной памяти, или вызов завершается ошибкой. Чтобы получить степень дробления распределенной оперативной памяти, используйте функцию GetSystemInfo, которая заполняет поля в членах структуры SYSTEM_INFO.

· Windows 95/98/Me: Адрес округляется вниз до ближайшего целого числа, кратного степени дробления распределенной оперативной памяти. Для последующих представлений файла, если указанный адрес не соответствует адресу, в который система отобразила представление файла, работа MapViewOfFileEx завершается ошибкой.

Приложение может создать несколько представлений файла из одного и того же объекта "проецируемый файл". Представление файла может быть другим по размеру, чем объект "проецируемый файл", из которого оно получено, но оно должно быть меньше, чем объект "проецируемый файл". Смещение, задаваемое параметрами dwOffsetHigh и dwOffsetLow функции MapViewOfFile должно быть кратно степени дробления распределенного пространства системы.

23. Рекурсивные алгоритмы. Понятие рекурсии, возможности и эффективность, решаемые классы задач Реку́рсия — процесс повторения элементов самоподобным образом. Например, если два зеркала установить друг напротив друга, то возникающие в них вложенные отражения суть одна из форм бесконечной рекурсии.Рекурсия и эффективность алгоритмов. Рекурсивное программирование дает нам общий подход к решению задач – разбиению их на аналогичные подзадачи меньшей размерности, либо на задачи, представляющие собой шаги в возможных направлениях ее решения. Так или иначе, рекурсивные вызовы образуют древовидную структуру, количество вершин в которой определяет эффективность алгоритма (выражаемую обычно через трудоемкость). Разница между различными типами алгоритмов состоит в способе получения подзадач, их размерности, способе соединения полученных результатов.• рекурсивное или обычное разделение. Идея разделения восходит к технологическому приему - модульному программированию (3.6). В своем первоначальном варианте она предполагает разбиение на задачи различной природы. Нерекурсивное разделение позволяет достичь определенного эффекта за счет разбиения задачи на множество идентичных задач меньшей размерности с последующим объединением результата. Типичным примером здесь является сортировка однократным слиянием (4.6). Применение того же самого алгоритма рекурсивно к полученным подзадачам дает следующий класс алгоритмов – рекурсивное разделение. Как правило, независимость полученных подзадач подразумевает соответствующее разделение исходных данных задачи на непересекающиеся подмножества – этому и соответствует сам тер-мин разделение. Эффективность (и трудоемкость) таких алгоритмов, зависит от затрат на само разделение и от пропорций разделяемых частей: лучшему случаю соответствует деление на равные части (логарифмические зависимость), худшему – выделение единственного элемента (линейные зависимости).• жадные алгоритмы. Идеальным случаем можно считать алгоритм, способный «выбрать из несколь-ких зол» единственно правильное. В основе его так же лежит принцип разделения, но в каждой точке он имеет основание выбрать одну из подзадач.Обычно это делается на основании особенностей организации обрабатываемых данных или их избыточности. Типичный пример: двоичный поиск в упорядоченных данных (4.6). Основой жадных алгоритмов является всегда довольно спорное утверждение: движение «по линии наименьшего сопротивления» в каждой точке приведет к желаемому результату.• полный перебор (исчерпывающий, комбинаторный перебор). Перечисленные выше подходы основаны на всевозможных «ухищрениях», основанных на особенностях предметной области алгоритма. Если же ничего не помогает, то остается полный перебор всех возможных вариантов решения задачи (8.4).• динамическое программирование. В процессе порождения дерева рекурсивных вызовов возможно повторение подзадач с одними и теми же данными. Если запоминать результат их выполнения, то эффектив-ность алгоритма может быть значительно увеличена.Основные принципы рекурсивного решения:• рекурсивная функция решает задачу для двух оставшихся частей строк с длинами k1 и k2, возвращая в виде результата максимальную длину найденной подпоследовательности;• шаг рекурсии заключается в проверке пары очередных символов и получении аналогичных подзадач меньшей размерности за счет отбрасывания этих символов;• если пара очередных символов совпадает, то они оба отбрасываются, а длина подпоследовательности увеличивается на 1. При этом производится рекурсивный вызов с сокращением длин обеих строк v=F(k1-1,k2-1)+1;• если пара очередных символов не совпадает, то возникают две подзадачи, в которых одна строка укорачи-вается, а другая остается неизменной. Из результатов двух рекурсивных вызовов выбирается максимальный и возвращается в неизменном виде, т.к. текущий шаг не удлиняет цепочку совпадений;• рекурсивный алгоритм завершается, когда заканчивается хотя бы одна строка, в этом случае функция возвращает 0 совпадений. 24. Динамические типы данных: графы. Виды, структура, основные свойства.

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

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

Многосвязная структура обладает следующими свойствами:

· 1) на каждый элемент (узел, вершину) может быть произвольное количество ссылок;

· 2) каждый элемент может иметь связь с любым количеством других элементов;

· 3) каждая связка (ребро, дуга) может иметь направление и вес.

В узлах графа содержится информация об элементах объекта. Связи между узлами задаются ребрами графа. Ребра графа могут иметь направленность, показываемую стрелками, тогда они называются ориентированными, ребра без стрелок - неориентированные.

Двунаправленные графы (bi-directional graphs) - самый простой тип графов. Именно этот тип представлен на рисунке. В данном типе графов, если два узла соединены друг с другом, то между этими узлами можно свободно "перемещаться".

В однонаправленных графах, если между двумя узлами есть дуга, то она "указывает" только в одну сторону.

Дата добавления: 2015-07-15