Главная Случайная страница


Категории:

ДомЗдоровьеЗоологияИнформатикаИскусствоИскусствоКомпьютерыКулинарияМаркетингМатематикаМедицинаМенеджментОбразованиеПедагогикаПитомцыПрограммированиеПроизводствоПромышленностьПсихологияРазноеРелигияСоциологияСпортСтатистикаТранспортФизикаФилософияФинансыХимияХоббиЭкологияЭкономикаЭлектроника






Классификация нелинейных структур

Нелинейные структуры данных— это СД, у которых связи между элементами зависят от выполнения определенного условия. Пример нелинейных структур — деревья, графы, многосвязные списки.

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

Вершина, располагающаяся в нулевом уровне, называется корнем дерева. В корень не входит ни одно ребро (вершина 1).

Рис. 1.9.Древовидная структура (дерево)

Вершины, из которых не выходит ни одного ребра, называются листьями (вершины 8, 9, 5, б, 7).

Дерево, из каждой вершины которого выходит только по два ребра, называется бинарным (рис. 1.10).

Рис. 1.10.Бинарное дерево

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

Рис. 1.11.Примеры графовых структур

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

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

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

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

Типичными графами являются схемы авиалиний и схемы метро, а на географических картах — изображение железных или автомобильных дорог. Выбранные точки графа называются его вершинами, а соединяющие их линии — ребрами.

Сплетения(многосвязные списки) — это нелинейная структура данных, объединяющая такие понятия, как деревья, графы и списковые структуры.

Сплетения (плексы) обобщают понятия графов и списковых структур.

Основное свойство сплетений, отличное от других типов структур, — наличие у каждого элемента сплетения нескольких полей с указателями на другие элементы того же сплетения (рис. 1.12).

Рис. 1.12.Многосвязный список (сплетение)

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

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

 

Методы сортировки

Упорядочение элементов множества в возрастающем или убывающем порядке называется сортировкой.

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

Алгоритмы сортировки можно разбить на следующие группы (рис. 2.1).

Обычно сортируемые элементы множества называют записями и обозначают через k1, k2, ..., kn.

Рис. 2.1.Алгоритмы сортировки

Сортировка выбором

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

Например, требуется найти минимальный элемент списка:

{5, 11, 6, 4, 9, 2, 15, 7}.

Процесс выбора показан на рис. 2.2, где в каждой строчке выписаны сравниваемые пары. Выбираемые элементы с меньшим весом обведены кружком. Нетрудно видеть, что число сравнений соответствует на рисунке числу строк, а число перемещений — количеству изменений выбранного элемента.

{5, 11, 6, 4, 9, 2,15, 7}

Рис. 2.2. Сортировка выбором

Выбранный в исходном списке минимальный элемент размещается на предназначенном ему месте несколькими способами:

• минимальный элемент после i-го просмотра перемещается на i-е место нового списка (i= 1, 2, ..., n), а в исходном списке на место выбранного элемента записывается какое-то очень большое число, превосходящее по величине любой элемент списка, при этом длина заданного списка остается постоянной. Измененный таким образом список можно принимать за исходный;

• минимальный элемент записывается на i-е место исходного списка (i= 1, 2, ...., п), а элемент с i-го места — на место выбранного. При этом очевидно, что уже упорядоченные элементы (а они будут расположены начиная с первого места) исключаются из дальнейшей сортировки, поэтому длина каждого последующего списка (списка, участвующего в каждом последующем просмотре) должна быть на один элемент меньше предыдущего;

• выбранный минимальный элемент, как и в предыдущем случае, перемещается на i-е место заданного списка, а чтобы это i-eместо освободилось для записи очередного минимального элемента, левая от выбранного элемента часть списка перемещается вправо на одну позицию так, чтобы заполнилось место, занимаемое до этого выбранным элементом (элементы списка циклически сдвигаются).

Сложность метода сортировки выбором порядка составляет О(n2).

Сортировка вставкой

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

Сортировку вставкой рассмотрим на примере заданной неупорядоченной последовательности элементов: {40, 11, 83, 57, 32, 21, 75, 64}.

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

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

На втором этапе из неупорядоченной последовательности выбирается элемент и сравнивается с двумя упорядоченными ранее элементами. Так как он больше предыдущих, то остается на месте. Затем анализируются четвертый, пятый и последующие элементы — до тех пор, пока весь список не будет упорядоченным, что имеет место на последнем (седьмом) этапе.

Рис. 2.3. Сортировка вставкой

Сортировка слиянием

Разновидностью сортировки вставкой является метод фон Неймана.

Алгоритм решения этой задачи, известный как «сортировка фон Неймана» или сортировка слиянием, состоит в следующем: сначала анализируются первые элементы обоих массивов. Меньший элемент переписывается в новый массив. Оставшийся элемент последовательно сравнивается с элементами из другого массива. В новый массив после каждого сравнения попадает меньший элемент. Процесс продолжается до исчерпания элементов одного из массивов. Затем остаток другого массива дописывается в новый массив. Полученный новый массив упорядочен таким же образом, как исходные.

Пусть имеются два отсортированных в порядке возрастания массива р[1], р[2], ..., р[n]и q[l], q[2], ..., q[n]иимеется пустой массив r[1], r[2], ..., r[2n], который необходимо заполнить значениями массивов р и q в порядке возрастания. Для слияния выполняются следующие действия: сравниваются р[1]и q[1], и меньшее из значений записывается в r[1]. Предположим, что это значение р[1]. Тогда р[2]сравнивается с q[1]и меньшее из значений заносится в r[2]. Предположим, что это значение q[1]. Тогда на следующем шаге сравниваются значения р[2]и q[2]и т. д., пока не достигнута граница одного из массивов. Тогда остаток другого массива просто дописывается в «хвост» массива r.

Пример слияния двух массивов показан на рис. 2.4.

Сложность метода сортировки вставкой порядка 0(п2).

Рис. 2.4.Сортировка слиянием

Сортировка обменом

Сортировка обменом — метод, в котором элементы списка последовательно сравниваются между собой и меняются местами в том случае, если предшествующий элемент больше последующего.

Требуется, например, провести сортировку списка методом стандартного обмена или методом «пузырька»:

{40, 11, 83, 57, 32, 21, 75, 64}.

Обозначим квадратными скобками со стрелками ↑____↑ обмениваемые элементы, а |____| — сравниваемые элементы. Первый этап сортировки показан на рис. 2.5, а второй этап — на рис. 2.6.

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

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

Второй просмотр выявляет максимальный элемент, равный 75 (см. рис. 2.6).

Рис. 2.5. Сортировка обменом (первый просмотр)

Рис. 2.6.Сортировка обменом (второй просмотр)

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

Условие Айверсона:если в ходе сортировки при сравнении элементов не было сделано ни одной перестановки, то множество считается упорядоченным (условие Айверсона выполняется только при шаге d= 1).

Шейкерная сортировка

Модификацией сортировки стандартным обменом является шейкернаяили челночная сортировка. Здесь, как и в методе пузырька, проводится попарное сравнение элементов. При этом первый проход осуществляется слева направо, второй — справа налево и т. д. Иными словами, меняется направление просмотра элементов списка.

Сложность метода стандартного обмена — 0(п2).

Сортировка Шелла

В методе Шелла сравниваются не соседние элементы, а элементы, расположенные на расстоянии d = [n/2] (где d — шаг между сравниваемыми элементами, [ ] — целая часть от числа). После каждого просмотра шаг d уменьшается вдвое. На последнем просмотре он сокращается до d= 1.

Например, пусть дан список, в котором число элементов четно:

{40, 11, 83, 57, 32, 21, 75, 64}.

Список длины п разбивается на n/2 частей, т. е. d = [n/2] = 4.

При первом просмотре сравниваются элементы, отстоящие друг от друга на d= 4 (рис. 2.7), т. е. k1 и k5, k2 и k6 и т. д. Если ki> ki+d, то происходит обмен между позициями i и (i + d). Перед вторым просмотром выбирается шаг d = [d/2] = 2 (рис. 2.8). Затем выбираем шаг d= [d/2] = 1 (рис. 2.9), т. е. имеем аналогию с методом стандартного обмена.

Сложность метода Шелла — O(0,3n(lоg2n)2).

Рис. 2.7. Метод Шелла (шаг d= 4)

Рис. 2.8.Метод Шелла (шаг d= 2)

Рис. 2.9.Метод Шелла (шаг d= 1)

2.1.5. Быстрая сортировка (сортировка Хоара)

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

Поясним метод на примере.

На рис. 2.10 представлен первый этап быстрой сортировки. В первой строке указана исходная последовательность.

Примем первый элемент последовательности за базовый ключ, выделим его квадратом и обозначим k0 = 40. Установим два указателя: i и j, из которых i начинает отсчет слева (i=1), а j — справа (j= п).

Сравниваем базовый ключ k0 и текущий ключ kj. Если k0<= kj, то устанавливаем j =j - 1 и проводим следующее сравне­ние k0 и kj. Продолжаем уменьшать j до тех пор, пока не достигнем условия k0 > kj. После этого меняем местами ключи k0 и kj (шаг 3 на рис. 2.10).

Рис. 2.10.Метод Хоара

Теперь начинаем изменять индекс i = i + 1 и сравнивать элементы ki и k0. Продолжаем увеличение i до тех пор, пока не получим условие ki > k0, после чего следует обмен ki и k0 (см. шаг 5). Снова возвращаемся к индексу j, уменьшаем его. Чередуя уменьшение j и увеличение i, продолжаем этот процесс с обоих концов к середине до тех пор, пока не получим i = j (см. шаг 7). В отличие от предыдущих рассмотренных сортировок уже на первом этапе имеют место два факта: во-первых, базовый ключ k0 = 40 занял свое постоянное место в сортируемой последовательности; во-вторых, все элементы слева от k0 будут меньше него, а справа — больше него. Таким образом, по окончании первого этапа имеем:

Указанная процедура сортировки применяется независимо к левой и правой частям.

Сложность метода Хоара — О(nlоg2n).

Турнирная сортировка

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

Пример.Дано исходное множество {7, 1, 9, 3, 6, 5, 8}. Осуществить турнирную сортировку. Производится попарное сравнение вершин дерева снизу вверх. Найденный максимальный элемент помещается в результирующее множество (рис. 2.11).

Рис. 2.11.Турнирная сортировка

В результате будет получено упорядоченное множество

{9, 8, 7, 6, 5, 3}.

Пирамидальная сортировка

Данный тип сортировки заключается в построении пирами­дального дерева.

Пирамидальное дерево — это бинарное дерево, обладающее тремя свойствами:

• в вершине каждой триады располагается элемент с боль­шим весом;

• листья бинарного дерева располагаются либо в одном уров­не, либо в двух соседних (рис. 2.12);

• листья нижнего уровня располагаются левее листьев более высокого уровня.

Рис. 2.12.Бинарное дерево:

а — листья на одном уровне; 6 — листья на соседних уровнях

В ходе преобразования элементы триад сравниваются дваж­ды (рис. 2.13), при этом элемент с большим весом перейдет вверх, а с меньшим — вниз.

 

Рис. 2.13.Сравнение элементов триад:

1 — первое сравнение; 2 — второе сравнение

Пример.Дано исходное множество {2, 4, 6, 3, 5, 7}. Метод пирамидальной сортировки показан на рис. 2.14.

Рис. 2.14.Пирамидальная сортировка

В результате будет получено упорядоченное множество {2, 3, 4, 5, 6, 7}.

Функция сложности алгоритма

Для оценки эффективности алгоритмов используется функ­ция сложности алгоритма, которая обозначается прописной бук­вой О, в круглых скобках записывается аргумент. Например, функция сложности О(п2) читается как функция сложности по­рядка n2. Функция сложности алгоритма — это функция, кото­рая определяет количество сравнений, перестановок, а также временные и ресурсные затраты на реализацию алгоритма. Функция сложности принимает следующий ряд значений (рис. 2.15).

n nlog2n n2 n3 en n!

 
 


Рис. 2.15.Ряд значений функции сложности алгоритма

Чем правее на оси расположена функция сложности, тем ме­нее эффективен алгоритм.

Методы простая вставка, простой и стандартный обмен име­ют функцию сложности O(п2).

Метод Хоара и пирамидальная сортировка имеют функцию сложности O(nlog2n).

Метод Шелла и турнирная сортировка "имеют функцию сложности O(0,3n(log2n)2).

Контрольные вопросы

Последнее изменение этой страницы: 2016-07-23

lectmania.ru. Все права принадлежат авторам данных материалов. В случае нарушения авторского права напишите нам сюда...