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

Курс «Алгоритмы и алгоритмические языки»1 семестр 2013/2014Лекция 141Динамические структуры данныхСтек (stack) – это динамическая последовательностьэлементов, количество которых изменяется, причем какдобавление, так и удаление элементов возможно толькос одной стороны последовательности (вершина стека).Работа со стеком осуществляется с помощью функций:push(x) – затолкать элемент x в стек;x = pop() – вытолкнуть элемент из стека.Стек можно организовать на базе:фиксированного массива stack[MAX],где константа MAX задает максимальную глубину стека.динамического массива, текущий размер которогохранится отдельно.в обоих случаях необходимо хранить позицию текущейвершины стека.можно использовать и другие структуры данных(например, список).2Динамические структуры данныхПример.

Перевод арифметического выражения в обратнуюпольскую запись (постфиксную).a + b × c - d→c × (a + b) - (d + e)/f →abc × + d cab + × de + f/abс×c-dab-d⇒Оп ПриорОп Приор+0abс×+d×1+0abс×+d-Оп Приор-03Динамические структуры данныхПример. Перевод арифметического выражения в обратнуюпольскую запись.#include <stdio.h>#include <stdlib.h>#include <ctype.h>/* Считывание символа-операции или переменной */static char getop (void) {int c;while ((c = getchar ()) != EOF && isblank (c));return c == EOF || c == '\n' ? 0 : c;}4Динамические структуры данныхПример.

Перевод арифметического выражения в обратнуюпольскую запись./* Является ли символ операцией */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;}5Динамические структуры данныхПример.

Перевод арифметического выражения в обратнуюпольскую запись.int main (void) {char c, op;while (c = getop ()) {/* Переменная-буква выводится сразу */if (isalpha (c))putchar (c);/* Скобка заносится в стек операций */else if (c == '(')push (c);else <...>6Динамические структуры данныхПример. Перевод арифметического выражения в обратнуюпольскую запись./* Операция заносится в стек в зависимости от приоритета */else if (isop (c)) {while (! isempty ()) {op = pop ();/* Заносим, если больший приоритет */if (prio (c) > prio (op)) {push (op); break;} else/* Иначе выталкиваем операцию из стека */putchar (op);}push (c);} else <...>7Динамические структуры данныхПример.

Перевод арифметического выражения в обратнуюпольскую запись./* Скобка выталкивает операции до парной скобки */} else if (c == ')')while ((op = pop ()) != '(')putchar (op);}/* Вывод остатка операций из стека */while (! isempty ())putchar (pop ());putchar ('\n');return 0;}8ОчередьОчередь (queue) – это линейный список информации, работа скоторой происходит по принципу FIFO.Для списка можно использовать статический массив:количество элементов массива (MAX) = наибольшейдопустимой длине очереди.Работа с очередью осуществляется с помощьюдвух функций:qstore() – поместить элемент в конец очереди;qretrieve() – удалить элемент из начала очереди;и двух глобальных переменных:spos (индекс первого свободного элемента очереди:его значение < MAX)rpos (индекс очередного элемента, подлежащегоудалению: «кто первый?»)9ОчередьsposНачальноесостояниеrpossposqstore('A')Arpossposqstore('B')ABrpossposqretrieve()Brpos10ОчередьТексты функций 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++];}11Улучшение – «зацикленная» очередь#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;}12Улучшение – «зацикленная» очередь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, т.е.

к пустой очереди.13СпискиОдносвязный список – это динамическая структура данных,каждый элемент которой содержит ссылку на следующийэлемент (либо NULL, если следующего элемента нет).Доступ к списку осуществляется с помощью указателя на егопервый элемент.struct list {struct data info;struct list *next;};/* Данные *//* Ссылка на след. элемент */Выделение элементаstruct list *phead = NULL;phead = (struct list *) malloc (sizeof (struct list));14СпискиДобавление элемента в начало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;}15СпискиДобавление элемента в конецstruct list *phead = NULL;struct list *add_element (struct list *phead, structdata *elem) {if (! phead) {phead = (struct list *) malloc (sizeof (struct list));phead->info = *elem;phead->next = NULL;return phead;}while (phead->next != NULL)phead = phead->next;phead->next = (struct list *) malloc (sizeof (struct list));phead->next->info = *elem;phead->next->next = NULL;return phead;16}.