Разделение массива

На входе массив a[0]...a[N] и опорный элемент p, по которому будет производиться разделение.

1. Введем два указателя: i и j. В начале алгоритма они указывают, соответственно, на левый и правый конец последовательности;

2. Будем двигать указатель i с шагом в 1 элемент по направлению к концу массива, пока не будет найден элемент a[i] >= p. Затем аналогичным образом начнем двигать указатель j от конца массива к началу, пока не будет найден a[j] <= p;

3. Далее, если i <= j, меняем a[i] и a[j] местами и продолжаем двигать i,j по тем же правилам...

4. Повторяем шаг 3, пока i <= j.

Рассмотрим работу процедуры для массива a[0]...a[6] и опорного элемента p = a[3].

Теперь массив разделен на две части: все элементы левой меньше либо равны p, все элементы правой - больше, либо равны p. Разделение завершено.

19. Динамические типы данных – линейные списки. Виды, основные свойства, применение.

линейные списки – это структура данных, состоящая из элементов одного типа, связанных между собой.

Различают:

1. односвязные – каждый элемент списка имеет указатель на следующий;

2. двусвязные – каждый элемент списка имеет указатель на следующий и на предыдущий элементы;

3. циклические – первый и последний элементы списка ссылаются друг на друга и цепочка представляет собой кольцо.

1-3 Связные списки – структура данных, состоящая из узлов, каждый из которых содержит как собственно данные, так и одну или две ссылки («связки») на следующий и/или предыдущий узел списка. Принципиальным преимуществом перед массивом является структурная гибкость: порядок элементов связного списка может не совпадать с порядком расположения элементов данных в памяти компьютера, а порядок обхода списка всегда явно задаётся его внутренними связями.

4. Стек (англ. stack — стопка) — структура данных, в которой доступ к элементам организован по принципу LIFO (англ. last in — first out, «последним пришёл — первым вышел»). Чаще всего принцип работы стека сравнивают со стопкой тарелок: чтобы взять вторую сверху, нужно снять верхнюю;

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

5. Очередь – структура данных с дисциплиной доступа к элементам «первый пришёл — первый вышел».

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

Клавиатурный буфер BIOS организован в виде кольцевого массива, обычно длиной в 16 машинных слов, и двух указателей: на следующий элемент в нём и на первый незанятый элемент.

Дек – двухсвязная очередь.

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

20. Динамические типы данных – деревья. Виды, основные свойства, применение. (как-то много деревьев то)

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

Корневой узел — самый верхний узел дерева.

Корень — одна из вершин, по желанию наблюдателя.

лист, листовой или терминальный узел — узел, не имеющий дочерних элементов.

Внутренний узел — любой узел дерева, имеющий потомков, и таким образом не являющийся листовым узлом.

Дерево считается ориентированным, если в корень не заходит ни одно ребро.

Классификация. Существует очень большое количество видов древовидных структур данных, которые можно классифицировать по нескольким различным признакам.

Деревья и пирамиды.

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

— двоичными (или бинарными) – имеющими не более двух ветвей (примеров таких деревьев очень много, они будут приведены позже);

– с числом ветвей больше 2 – часто такие деревья называют мультивариантными (многопутевыми) или K-деревьями (т.е. K-мерными). Примерами могут быть 2-3-деревья (и им подобные), Б-деревья (различные деревья Байера с подвариантами, например, дерево Байера-МакКрейта, Байера-Баума) и т.п. Видов K-деревьев очень много (свыше 40 различных древовидных структур для представления многомерной информации: R-Tree, R+-Tree, Hilbert R-Tree, hB-Tree, hBII-Tree, BV-Tree, BD-Tree, GBD-Tree, G-Tree, SKD-Tree, kd-Tree, kd2B-Tree, BSP-Tree, LSD-Tree, P-Tree, TR-Tree, Cell-Tree, Quadtree, Grid File, Z-Hashing, SS-Tree).

Важным признаком является состояние сбалансированности дерева и способы его достижения. Деревья могут быть:

– сбалансированными;

– идеально сбалансированными (отличие этих двух первых состояний будет рассмотрено позже);

– вырожденными;

– отличающимися более или менее сильно от сбалансированных и от вырожденных.

Автоматическая балансировка дерева выполняется, например, для АВЛ-деревьев, красно-чёрных деревьев (все эти деревья являются двоичными), Б-деревьев и некоторых других видов деревьев.

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

Отдельные типы деревьев применяются для решения специальных задач, например остовные деревья на графах (каркасы графов, Spanning Tree) или PATRICIA-деревья (Practical Algorithm To Retrieve Information Coded In Alphanumeric), используемые для поиска данных на основе их поразрядного двоичного представления.

Несколько несвязанных между собой деревьев образуют структуру данных, которая называется "лес" (иногда её называют "бор").

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