Слайды лекций - 2014 (лектор - Белеванцев А. А.) (1107979), страница 10

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 10)

Каждый узел графа (не только ведущий)может иметь один или несколько ведомых узлов.6Топологическая сортировка узлов ациклическогоориентированного графаСтруктуры данных для представления узлов:Дескриптор каждого узла содержит ссылки на ведомыеузлы. Так как заранее неясно, сколько у узла будетведомых узлов, эти ссылки помещаются в список.На рисунке представлен элемент списка ссылок.7Топологическая сортировка узлов ациклическогоориентированного графа1 фаза алгоритма: ввод исходного графаНа этой фазе вводятся пары ключей и из них формируетсяпредставление ациклического графа через дескрипторы узлови списки ведомых узлов.Исходные данные представлены в виде множествапар ключей (*), которые вводятся в произвольномпорядке.После ввода очередной пары x < y ключи x и y ищутсяв списке «ведущих» и в случае отсутствия добавляютсяк нему.В список ведомых узлов узла x добавляется ссылка наy, а счетчик предшественников y увеличивается на 1(начальные значения всех счетчиков равны 0).По окончании фазы ввода будет сформирована структура, показаннаяна следующем слайде (для множества пар ключей (*) ).8Топологическая сортировка узлов ациклическогоориентированного графа9Топологическая сортировка узлов ациклическогоориентированного графа10Топологическая сортировка узлов ациклическогоориентированного графа11Топологическая сортировка узлов ациклическогоориентированного графа2 фаза алгоритма: сортировка(1)В списке «ведущих» находим дескриптор узла z,у которого значение поля count равно 0.(2)Включаем узел z в результирующую цепочку.(3)Если у узла z есть «ведомые» узлы(значение поля trail не NULL)(a)просматриваем очередной элемент списка«ведомых» узловкорректируем поле count дескрипторасоответствующего «ведомого» узла.Переходим к шагу (1)(b)(4)Так как с каждой коррекцией поля count его значениеуменьшается на 1, постепенно все узлы включаютсяв результирующую цепочку.12Курс «Алгоритмы и алгоритмические языки»1 семестр 2014/2015Лекция 161Описание алгоритма топологической сортировки на языке Си#include <stdio.h>#include <stdlib.h>typedef struct ldr {char key;int count;struct ldr *next;struct trl *trail;} leader;typedef struct trl {struct ldr *id;struct trl *next;} trailer;leader *head, *tail;int lnum;/*дескриптор ведущего узла*//*дескриптор ведомого узла*//*два вспомогательных узла*//*счетчик ведущих узлов*/2Описание алгоритма топологической сортировки на языке Си/* поиск по ключу w */leader *find (char w) {leader *h = head;/* "барьер" на случай отсутствия w */tail->key = w;while (h->key != w)h = h->next;if (h == tail) {/* генерация нового ведущего узла */tail = (leader *) malloc (sizeof (leader));/* старый tail становится новым элементом списка */lnum++;h->count = 0;h->trail = NULL;h->next = tail;}return h;3}Описание алгоритма топологической сортировки на языке Сиvoid init_list() {/* инициализация списка «ведущих» */leader *p, *q;trailer *t;char x, y;head = (leader *) malloc (sizeof (leader));tail = head;lnum = 0;/* начальная установка */while (1) {if (scanf ("%c %c", &x, &y) != 2)break;/* включение пары в список */p = find (x);q = find (y);/* коррекция списка */t = (trailer *) malloc (sizeof (trailer));t->id = q;t->next = p->trail;p->trail = t;q->count += 1;}}4Описание алгоритма топологической сортировки на языке Си/* Исходный список построен.

Организация нового списка */void sort_list() {leader *p, *q;trailer *t;/* В выходной список включаются все узлы старогос count == 0 */p = head;head = NULL; /* голова выходного списка */while (p != tail) {q = p;p = q->next;if (q->count == 0) {/* включение q в выходной список */q->next = head;head = q;}}<...>5Описание алгоритма топологической сортировки на языке Си/* Фаза сортировки и вывода результатов из нового списка */<...>q = head; /* есть ведущий узел -> head != NULL */while (q != NULL) {printf ("%c\n", q->key);lnum--;t = q->trail;q = q->next;while (t != NULL) {p = t->id;p->count -= 1;if (p->count == 0) {p->next = q;q = p;}t = t->next;/* здесь можно удалить ведомый элемент */}}/* lnum == 0 */}6Описание алгоритма топологической сортировки на языке Сиint main() {init_list ();sort_list ();return 0;}7СортировкаПостановка задачиСортировка – это упорядочение наборов однотипных данных,для которых определено отношение линейного порядка(например, <) по возрастанию или по убыванию.Здесь будут рассматриваться целочисленные данные иотношение порядка "<".В стандартную библиотеку stdlib входит функция qsort:void qsort (void *buf, size_t num, size_t size,int(*compare)(const void *, const void *));Функция qsort сортирует (по возрастанию) массив с указателемbuf, используя алгоритм быстрой сортировки Ч.Э.Р.

Хоара,который считается одним из лучших алгоритмов сортировкиобщего назначения.Параметр num задает количество элементов массива buf,параметр size – размер (в байтах) элемента массива buf.Параметр int(*compare)(const void *, constvoid *)задает правило сравнения элементов массива num.8СортировкаФункция, указатель на которую передается в qsort в качествеаргумента, соответствующего параметруint(*compare)(const void *, const void *), должнаиметь описание:int имя функции (const void *arg1, const void*arg2)и возвращать:целое < 0, если arg1 < arg2,целое = 0, если arg1 = arg2целое > 0, если arg1 > arg29Сложность алгоритмовРазмер входа: числовая величина, характеризующаяколичество входных данных (например – длина битовой записичисел- параметров алгоритма)Сложность в наихудшем случае: функция размера входа,отражающая максимум затрат на выполнение алгоритма дляданного размеравременнАя сложностьпространственная сложность (затраты памяти)часто оценивают не все затраты, а только самые“дорогие” операцииСложность в среднем: функция размера входа,отражающая средние затраты на выполнение алгоритма длявхода данного размера (учет вероятностей входа)Асимптотические оценки сложности: О-нотация (оценкасверху), точная O-оценка, Θ-оценка.Подробности: С.А.

Абрамов. Лекции о сложности алгоритмов.М.: МЦНМО, 200910СортировкаПростейший алгоритм сортировки: сведение сортировки кзадаче нахождения максимального (минимального) из n чисел.Нахождение максимума n чисел (n сравнений):Числа содержатся в массиве int a[n];max = a[0];for (i = 1; i < n; i++)if (a[i] > max)max = a[i];Алгоритм сортировки: находим максимальное из n чисел,получаем последний элемент отсортированного массива (nсравнений);находим максимальное из n – 1 оставшихся чисел, получаемпредпоследний элемент отсортированного массива (еще n – 1сравнений); и так далее.Общее количество сравнений: 1 + 2 + … + n-1 + n = n(n - 1)/2.Сложность алгоритма O(n2).11Курс «Алгоритмы и алгоритмические языки»1 семестр 2014/2015Лекция 171СортировкаПростейший алгоритм сортировки: сведение сортировки кзадаче нахождения максимального (минимального) из n чисел.Нахождение максимума n чисел (n сравнений):Числа содержатся в массиве int a[n];max = a[0];for (i = 1; i < n; i++)if (a[i] > max)max = a[i];Алгоритм сортировки: находим максимальное из n чисел,получаем последний элемент отсортированного массива (nсравнений);находим максимальное из n – 1 оставшихся чисел, получаемпредпоследний элемент отсортированного массива (еще n – 1сравнений); и так далее.Общее количество сравнений: 1 + 2 + … + n-1 + n = n(n - 1)/2.Сложность алгоритма O(n2).2СортировкаКлассификация алгоритмов сортировкиРазличают внешнюю и внутреннюю сортировку.Рассматривается только внутренняя сортировка:сортируемый массив находится в основной памяти компьютера.Внешняя сортировка применяется к записям на внешнихфайлах.3 общих метода внутренней сортировки:(1)сортировка обменами: рассматриваются соседниеэлементы сортируемого массива и при необходимостименяются местами;(2)сортировка выборкой: идея описанана предыдущем слайде(3)сортировка вставками: сначала сортируются дваэлемента массива, потом выбирается третий элемент ивставляется в нужную позицию относительно первых3двух и т.д.СортировкаСортировка обменами (пузырьком)Общее количество сравнений (действий): n(n - 1)/2, так каквнешний цикл выполняется (n - 1) раз, а внутренний – в среднемn/2 раза.void bubble_sort (int *a, int n) {int i, j, tmp;for (j = 1; j < n; ++j)for (i = n - 1; i >= j; --i) {if (a[i - 1] > a[i]) {tmp = a[i - 1];a[i - 1] = a[i];a[i] = tmp;}}}4СортировкаСортировка вставкамиКоличество сравнений зависит от степени перемешанностимассива a.

Если массив a уже отсортирован, количествосравнений равно n - 1. Если массив a отсортирован в обратномпорядке (наихудший случай), количество сравнений имеетпорядок n2.void insert_sort (int *a, int n) {int i, j, tmp;for (j = 1; j < n; ++j) {tmp = a[j];for (i = j - 1; i >= 0 && tmp < a[i]; i--)a[i + 1] = a[i];a[i + 1] = tmp;}}5СортировкаОценка сложности алгоритмов сортировкиСкорость сортировки определяется количеством сравнений иколичеством обменов (обмены занимают больше времени).Эти показатели интересны для худшего и лучшего случаев,а также интересно их среднее значение.Кроме скорости оценивается «естественность» алгоритмасортировки:естественным считается алгоритм, который на ужеотсортированном массиве работает минимальное время, а на неотсортированном работает тем дольше, чем больше степень егонеупорядоченности.Важным показателем является и объем дополнительной памятидля хранения промежуточных данных алгоритма.Для рекурсивных алгоритмов расход памяти связан снеобходимостью дублировать стек, в котором расположенынекоторые промежуточные данные.6СортировкаОценка сложности алгоритмов сортировки.Теорема.

Характеристики

Список файлов лекций