14 (1106251)

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

Текст из файла

Курс «Алгоритмы и алгоритмические языки»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}.

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

Тип файла PDF

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

Например, если Вам нужно распечатать чертёж из автокада, Вы сохраните чертёж на флешку, но будет ли автокад в пункте печати? А если будет, то нужная версия с нужными библиотеками? Именно для этого и нужен формат PDF - в нём точно будет показано верно вне зависимости от того, в какой программе создали PDF-файл и есть ли нужная программа для его просмотра.

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