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

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

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

СтекСтек (stack) – это динамическая последовательностьэлементов, количество которых изменяется, причем какдобавление, так и удаление элементов возможно толькос одной стороны последовательности (вершина стека).Работа со стеком осуществляется с помощью функций:push(x) – затолкать элемент x в стек;x = pop() – вытолкнуть элемент из стека.Стек можно организовать на базе:фиксированного массива stack[MAX],где константа MAX задает максимальную глубину стека.динамического массива, текущий размер которогохранится отдельно.в обоих случаях необходимо хранить позицию текущейвершины стека.можно использовать и другие структуры данных(например, список).2Организация стека на динамическом массивеstruct stack {int sp;/* Текущая вершина стека */int sz;/* Размер массива */char *stack;} stack = { .sp = -1, .sz = 0, .stack = NULL };static void push (char c) {if (stack.sz == stack.sp + 1) {stack.sz = 2*stack.sz + 1;stack.stack = (char *) realloc (stack.stack,stack.sz*sizeof (char));}stack.stack[++stack.sp] = c;}3Организация стека на динамическом массивеstruct stack {int sp;/* Текущая вершина стека */int sz;/* Размер массива */char *stack;} stack = { .sp = -1, .sz = 0, .stack = NULL };static char pop (void) {if (stack.sp < 0) {fprintf (stderr, "Cannot pop: stack is empty\n");return 0;}return stack.stack[stack.sp--];}static int isempty (void) {return stack.sp == -1;}4Пример работы со стекомПеревод арифметического выражения в обратную польскуюзапись (постфиксную).a + b × c - d→c × (a + b) - (d + e)/f →abc × + d cab + × de + f/abс×c-dab-d⇒Оп ПриорОп Приор+0abс×+d×1+0abс×+d-Оп Приор-05Пример работы со стекомПеревод арифметического выражения в обратную польскуюзапись.#include <stdio.h>#include <stdlib.h>#include <ctype.h>#include "stack.c"/* Считывание символа-операции или переменной */static char getop (void) {int c;while ((c = getchar ()) != EOF && isblank (c));return c == EOF || c == '\n' ? 0 : c;}6Пример работы со стекомПеревод арифметического выражения в обратную польскуюзапись./* Является ли символ операцией */static int isop (char c) {return (c == '+') || (c == '-') || (c == '*')|| (c == '/');}/* Каков приоритет символа-операции */static int prio (char c) {if (c == '(')return 0;if (c == '+' || c == '-')return 1;if (c == '*' || c == '/')return 2;return -1;}7Пример работы со стекомПеревод арифметического выражения в обратную польскуюзапись.int main (void) {char c, op;while (c = getop ()) {/* Переменная-буква выводится сразу */if (isalpha (c))putchar (c);/* Скобка заносится в стек операций */else if (c == '(')push (c);else <...>8Пример работы со стекомПеревод арифметического выражения в обратную польскуюзапись./* Операция заносится в стек в зависимости от приоритета */else if (isop (c)) {while (! isempty ()) {op = pop ();/* Заносим, если больший приоритет */if (prio (c) > prio (op)) {push (op); break;} else/* Иначе выталкиваем операцию из стека */putchar (op);}push (c);} else <...>9Пример работы со стекомПеревод арифметического выражения в обратную польскуюзапись./* Скобка выталкивает операции до парной скобки */} else if (c == ')')while ((op = pop ()) != '(')putchar (op);}/* Вывод остатка операций из стека */while (! isempty ())putchar (pop ());putchar ('\n');return 0;}10Организация стека как библиотеки stack.h:extern void push (char);extern char pop (void);extern int isempty (void); stack.c:#include "stack.h"struct stack {<...>};static struct stack stack= { <...> };void push (char c ) { <...> }char pop (void) { <...> }int isempty (void) { <...> } main.c:#include "stack.h"int main (void) {<...push (c), pop (), ...>}$gcc main.c stack.c –o main11Организация стека как библиотеки - II stack.h:struct stack;// forward declarationextern void push (struct stack *, char);extern char pop (struct stack *);extern int isempty (struct stack *);extern struct stack* new_stack (void);extern void free_stack (struct stack *); stack.c:#include "stack.h"struct stack {<...>};void push (struct stack *stack, char c ) {if (stack->sz == stack->sp + 1) <...>}<...>12Организация стека как библиотеки - III stack.c:struct stack* new_stack (void) {struct stack *s = malloc (sizeof (struct stack));*s = (struct stack){ .sp = -1, .sz = 0, .stack = NULL };return s;}void free_stack (struct stack *s) {free (s->stack);free (s);} main.c:#include "stack.h"int main (void) {struct stack *s = new_stack ();<...push (s, c), pop (s), ...>free_stack (s);<...>}13ОчередьОчередь (queue) – это линейный список информации, работа скоторой происходит по принципу FIFO.Для списка можно использовать статический массив:количество элементов массива (MAX) = наибольшейдопустимой длине очереди.Работа с очередью осуществляется с помощьюдвух функций:qstore() – поместить элемент в конец очереди;qretrieve() – удалить элемент из начала очереди;и двух глобальных переменных:spos (индекс первого свободного элемента очереди:его значение < MAX)rpos (индекс очередного элемента, подлежащегоудалению: «кто первый?»)14ОчередьsposНачальноесостояниеrpossposqstore('A')Arpossposqstore('B')ABrpossposqretrieve()Brpos15ОчередьТексты функций qstore() и qretrieve()#define MAX67int queue[MAX];int spos = 0, rpos = 0;int qstore (int q) {if (spos == MAX) {/* Можно расширить очередь, см.

реализацию стека */printf ("Очередь переполнена\n");return 0;}queue[spos++] = q;return 1;}int qretrieve (void) {if (rpos == spos) {printf ("Очередь пуста \n");return -1;}return queue[rpos++];}16Улучшение – «зацикленная» очередь#define MAX67int queue[MAX];int spos = 0, rpos = 0;int qstore (int q) {if (spos + 1 == rpos|| (spos + 1 == MAX && !rpos) {printf ("Очередь переполнена \n");return 0;}queue[spos++] = q;if (spos == MAX)spos = 0;return 1;}17Улучшение – «зацикленная» очередьint qretrieve (void) {if (rpos == spos) {printf ("Очередь пуста \n");return -1;}if (rpos == MAX - 1) {rpos = 0;return queue[MAX – 1];}return queue[rpos++];}Зацикленная очередь переполняется, когда spos находитсянепосредственно перед rpos, так как в этом случае записьприведет к rpos == spos, т.е.

к пустой очереди.18СпискиОдносвязный список – это динамическая структура данных,каждый элемент которой содержит ссылку на следующийэлемент (либо NULL, если следующего элемента нет).Доступ к списку осуществляется с помощью указателя на егопервый элемент.struct list {struct data info;struct list *next;};/* Данные *//* Ссылка на след. элемент */Выделение элементаstruct list *phead = NULL;phead = (struct list *) malloc (sizeof (struct list));19СпискиДобавление элемента в началоstruct list *phead = NULL;struct list *add_element (struct list *phead, structdata *elem) {struct list *new = malloc (sizeof (struct list));new->info = *elem;new->next = phead;return new;}20СпискиДобавление элемента в конецstruct list *phead = NULL;struct list *add_element (struct list *phead, structdata *elem) {if (! phead) {phead = malloc (sizeof (struct list));phead->info = *elem;phead->next = NULL;return phead;}while (phead->next != NULL)phead = phead->next;phead->next = malloc (sizeof (struct list));phead->next->info = *elem;phead->next->next = NULL;return phead;}21СпискиПоиск элемента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;}22СпискиУдаление элемента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;}23СпискиУдаление элемента (двойной указатель)void remove (struct list **pphead,struct data *elem) {struct list *prev = NULL, *phead = *pphead;while (phead && ! equals (&phead->info, elem)) {prev = phead;phead = phead->next;}if (! phead)return;if (prev)prev->next = phead->next;else*pphead = phead->next;free (phead);}24Курс «Алгоритмы и алгоритмические языки»1 семестр 2014/2015Лекция 151Топологическая сортировка узлов ациклическогоориентированного графаАциклический граф можно использовать для графическогоизображения частично упорядоченного множества.Цель топологической сортировки:преобразовать частичный порядок в линейный.Графически это означает, чтовсе узлы графа нужно расположить на одной прямой такимобразом, чтобы все дуги графа были направлены в однусторону.2Топологическая сортировка узлов ациклическогоориентированного графаПример.

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

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

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

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