15 (Лекции 2013-го года)

Курс «Алгоритмы и алгоритмические языки»1 семестр 2013/2014Лекция 151СпискиОдносвязный список – это динамическая структура данных,каждый элемент которой содержит ссылку на следующийэлемент (либо NULL, если следующего элемента нет).Доступ к списку осуществляется с помощью указателя на егопервый элемент.struct list {struct data info;struct list *next;};/* Данные *//* Ссылка на след. элемент */Выделение элементаstruct list *phead = NULL;phead = (struct list *) malloc (sizeof (struct list));2СпискиПоиск элементаstruct list * phead;int equals (struct data *, struct data *);struct list * search (struct list *phead, struct data*elem) {while (phead && ! equals (&phead->info, elem))phead = phead->next;return phead;}3СпискиУдаление элементаstruct list *remove (struct list *phead,struct data *elem) {struct list *prev = NULL, *ph = phead;while (phead && ! equals (&phead->info, elem)) {prev = phead;phead = phead->next;}if (! phead)return ph;if (prev)prev->next = phead->next;elseph = phead->next;free (phead);return ph;}4Топологическая сортировка узлов ациклическогоориентированного графаАциклический граф можно использовать для графическогоизображения частично упорядоченного множества.Цель топологической сортировки:преобразовать частичный порядок в линейный.Графически это означает, чтовсе узлы графа нужно расположить на одной прямой такимобразом, чтобы все дуги графа были направлены в однусторону.5Топологическая сортировка узлов ациклическогоориентированного графаПример.

Частичный порядок (<) задается следующим наборомотношений :a < b, b < d, d < f, b < l, d < h, f < c, a < c,c < e, e < h, g < e, g < k, k < d, k < l(*)Набор отношений (*) можно представить в виде следующегоациклического графа (см. рисунок):6Топологическая сортировка узлов ациклическогоориентированного графаТребуется привести рассматриваемый граф к линейному графу:На этом графе ключи расположены в следующем порядке:g k a b d f c e h l(поскольку топологическая сортировка неоднозначна, это одиниз возможных топологических порядков).Последовательная обработка полученного линейного спискаузлов графа эквивалентна их обработке в порядке обходаграфа.7Топологическая сортировка узлов ациклическогоориентированного графаПоскольку рассматриваемый граф – ациклический, существуетхотя бы один узел графа, у которого нет предшествующихузлов. Каждый такой узел будем называть ведущим узлом.Шаг алгоритма: Выберем один из ведущих узлов и поместимего в начало линейного списка отсортированных узлов, удаливего из исходного графа.Поскольку граф, у которого удалили один из ведущих узлов,останется ациклическим, в нем будет хотя бы один ведущийузел.

Следовательно, можно повторить шаг алгоритма.Легко видеть, что каждый узел графа рано или поздно станетведущим и попадет в формируемый линейный список,и алгоритм завершится через несколько шагов.8Топологическая сортировка узлов ациклическогоориентированного графаСтруктуры данных для представления узлов:Каждый узел исходного графа представляется спомощью дескриптора узла, который имеет вид:Ведомыми для узла n будут узлы, для которых n являетсяпредшественником. Каждый узел графа (не только ведущий)может иметь один или несколько ведомых узлов.9Топологическая сортировка узлов ациклическогоориентированного графаСтруктуры данных для представления узлов:Дескриптор каждого узла содержит ссылки на ведомыеузлы.

Так как заранее неясно, сколько у узла будетведомых узлов, эти ссылки помещаются в список.На рисунке представлен элемент списка ссылок.10Топологическая сортировка узлов ациклическогоориентированного графа1 фаза алгоритма: ввод исходного графаНа этой фазе вводятся пары ключей и из них формируетсяпредставление ациклического графа через дескрипторы узлови списки ведомых узлов.Исходные данные представлены в виде множествапар ключей (*), которые вводятся в произвольномпорядке.После ввода очередной пары x < y ключи x и y ищутсяв списке «ведущих» и в случае отсутствия добавляютсяк нему.В список ведомых узлов узла x добавляется ссылка наy, а счетчик предшественников y увеличивается на 1(начальные значения всех счетчиков равны 0).По окончании фазы ввода будет сформирована структура, показаннаяна следующем слайде (для множества пар ключей (*) ).11Топологическая сортировка узлов ациклическогоориентированного графа12Топологическая сортировка узлов ациклическогоориентированного графа13Топологическая сортировка узлов ациклическогоориентированного графа14Топологическая сортировка узлов ациклическогоориентированного графа2 фаза алгоритма: сортировка(1)В списке «ведущих» находим дескриптор узла z,у которого значение поля count равно 0.(2)Включаем узел z в результирующую цепочку.(3)Если у узла z есть «ведомые» узлы(значение поля trail не NULL)(a)просматриваем очередной элемент списка«ведомых» узловкорректируем поле count дескрипторасоответствующего «ведомого» узла.Переходим к шагу (1)(b)(4)Так как с каждой коррекцией поля count его значениеуменьшается на 1, постепенно все узлы включаютсяв результирующую цепочку.15Описание алгоритма топологической сортировки на языке Си#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;/*дескриптор ведущего узла*//*дескриптор ведомого узла*//*два вспомогательных узла*//*счетчик ведущих узлов*/16Описание алгоритма топологической сортировки на языке Си/* поиск по ключу 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;17}Описание алгоритма топологической сортировки на языке Си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;}}18Описание алгоритма топологической сортировки на языке Си/* Исходный список построен.

Организация нового списка */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;}}<...>19Описание алгоритма топологической сортировки на языке Си/* Фаза сортировки и вывода результатов из нового списка */<...>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 */}20Описание алгоритма топологической сортировки на языке Сиint main() {init_list ();sort_list ();return 0;}21.