А.А. Белеванцев, С.С. Гайсарян, Л.С. Корухова, Е.А. Кузьменкова, В.С. Махнычев. Семинары по курсу Алгоритмы и алгоритмические языки (1108027), страница 14
Текст из файла (страница 14)
Задачи для самостоятельного решенияСтек. Очередь.10.2.1. Описать реализацию стека на основе однонаправленного списка.10.2.2. Описать реализацию очереди на основе однонаправленного списка.В задачах 10.2.3. — 10.2.6. считать уже описанными типы и функции для работы состеком и очередью.10.2.3. Написать программу, которая переводит заданное алгебраическоевыражение, содержащее операнды (целые числа), круглые скобки, бинарные операции + и−, в постфиксную запись.
Считать точку признаком конца выражения. Для решениязадачи использовать стек.10.2.4. Решить предыдущую задачу, если в качестве операций могут встречатьсятакже умножение и деление (* и /); приоритеты операций должны быть соблюдены.10.2.5. Реализовать вычисление выражения, содержащего бинарные операции +, −,*, / и записанного в постфиксной форме. В реализации использовать стек.10.2.6. Дан файл, содержащий целые числа (их количество заранее не известно).Определить подходящую структуру данных и написать программу, которая за одинпросмотр файла решает следующую задачу:а) напечатать сумму первого и последнего чисел, сумму второго ипредпоследнего чисел и т. д.;б) вывести сначала все четные числа файла, а затем — все нечетные в том жепорядке, в котором они идут в файле;в) вывести все четные числа из файла в исходном порядке, а затем — всенечетные числа файла в порядке, обратном порядку их следования в файле.6410.3.
Двоичные деревьяДеревья используются преимущественно для хранения упорядоченных данных свозможностью быстрого поиска по ключу.Двоичное дерево — древовидная структура данных, в которой каждая вершинаимеет не более двух потомков. Можно привести рекурсивное определение двоичногодерева:a) пустая структура (пустое множество вершин) является двоичным деревом;b) структура, состоящая из вершины, потомками которой являются двадвоичных дерева (возможно, одно из них или оба — пустые), такжеобразует двоичное дерево.Любое поддерево двоичного дерева также является деревом.Корнем дерева называется вершина, не являющаяся потомком никакой другойвершины.
В непустом дереве всегда ровно один корень.Листьями дерева называются вершины, не имеющие потомков.Высотой дерева называется наибольшая длина пути от корня дерева до любого изего листьев. Длина пути измеряется в пройденных вершинах: так, у дерева, состоящего изединственной вершины, корень является и его единственным листом, а высота такогодерева равна 1.2h−1Легко видеть, что количество листьев в двоичном дереве высоты h не превышает, а общее количество вершин ограничено величиной 2h−1.Для работы с двоичными деревьями на языке Си можно использовать следующееописание:struct treenode {int elem;struct treenode *left, *right;};При передаче двоичного дерева в функцию передают указатель на корень этого дерева.Пустому дереву соответствует указатель NULL.Для обхода всех вершин дерева используют как рекурсивные, так и нерекурсивныеалгоритмы.Рекурсивный обход дерева вытекает непосредственно из рекурсивного определениядерева.
Пример: функция, печатающая значения всех элементов дерева.void print_tree (struct treenode *T) {if (T != NULL) {printf ("%d\n", T->elem);print_tree (T->left);print_tree (T->right);}}Рекурсивный алгоритм осуществляет обход дерева «в глубину»: элементы дерева,расположенные дальше от корня, обрабатываются раньше большинства (или всех)элементов, находящихся ближе к корню.При нерекурсивном обходе дерева для хранения вершин, подлежащих обработке,используют стек или очередь.
Использование стека дает тот же порядок обработкивершин, что и приведенный выше рекурсивный алгоритм, а использование очереди65позволяет обрабатывать элементы дерева в порядке увеличения расстояния от корня:сначала корневую вершину, затем – все вершины, отстоящие от корня на 1, затем – всевершины, отстоящие от корня на 2, и так далее. Такой обход называется обходом «вширину».Пример: нерекурсивные функции, печатающие значения всех элементов дерева припомощи стека и очереди (стек и очередь при этом должны хранить значения типа structtreenode *).// typedef struct treenode *datatype;// тип данных для стека/очередиvoid print_tree_stack (struct treenode *T) {stack st;init_stack (&st);push (&st, T);while (!empty_stack (&st)) {pop (&st, &T);if (T != NULL) {printf ("%d\n", T->elem);push (&st, T->right);push (&st, T->left);}}delete_stack (&st);}void print_tree_queue( struct treenode *T) {queue q;init_queue (&q);enqueue (&q, T);while (!empty_queue (&q)) {dequeue (&q, &T);if (T == NULL)continue;printf ("%d\n", T->elem);enqueue (&q, T->left);enqueue (&q, T->right);}delete_queue (&q);}10.3.1.
Задачи для самостоятельного решения10.3.1. Описать функцию, которая:а) вычисляет сумму всех элементов двоичного дерева;б) подсчитывает количество вхождений заданного элемента в двоичноедерево;в) вычисляет высоту двоичного дерева;г) печатает значения данных из всех вершин дерева, не являющихсялистьями;д) проверяет, идентичны ли два двоичных дерева;е) удаляет все элементы заданного двоичного дерева.6610.3.2. Используя определенные ранее типы данных «очередь» и «стек», описатьнерекурсивную функцию, которая:а) определяет число вхождений заданного элемента в двоичное дерево;б) вычисляет сумму элементов двоичного дерева;в) находит длину (количество узлов) на пути от корня до ближайшей вершины,содержащей заданный элемент (если такой вершины в дереве нет, то считатьрезультат равным -1);г) подсчитывает количество узлов на заданном уровне непустого двоичногодерева (корень считать вершиной нулевого уровня).10.4.
Деревья поиска. АВЛ-деревьяДвоичным деревом поиска называется двоичное дерево, в котором левое поддеревокаждой вершины может содержать только значения (ключи), строго меньшие ключа ввершине, а правое поддерево – только ключи, строго большие ключа в вершине.Одинаковых ключей в дереве поиска быть не может.Дерево поиска позволяет находить нужные элементы в нем за время,пропорциональное высоте дерева. Пример: функция, возвращающая указатель на вершинудерева поиска с заданным ключом.struct treenode *search (struct treenode *T, int key) {if (T == NULL)return NULL;if (T->elem == key)return T;if (key < T->elem)return search (T->left, key);elsereturn search (T->right, key);}Эффективность поиска ключа в дереве поиска существенно зависит от его структуры.Так, для дерева поиска из N вершин в лучшем случае его высота составляетприблизительно log2N (и при поиске в дереве из миллиона вершин придется выполнитьвсего 20 сравнений), а в худшем – высота равна N: дерево «вытянуто» в цепочку (и припоиске в таком дереве придется просмотреть все его вершины).АВЛ-дерево – двоичное дерево поиска, в каждой вершине которого высота левогоподдерева этой вершины отличается от высоты правого поддерева этой вершины не болеечем на единицу.
Такое свойство существенно ограничивает увеличение высоты дерева сростом количества вершин, то есть поиск нужного элемента происходит быстро. Крометого, существует эффективный алгоритм добавления (вставки) нового элемента в АВЛдерево: новый элемент добавляется в качестве листа к одному из поддеревьев (как и вдереве поиска), а затем для тех вершин, где условие балансировки АВЛ-дерева оказалосьнарушенным, выполняется соответствующий поворот, который сводится к перестановкенескольких вершин и поддеревьев. Пример: реализация короткого правого поворота RR.67Рис.
6. Балансировка АВЛ-дереваstruct treenode *rotate_RR (struct treenode *root) {struct treenode *b = root->left;struct treenode *c = b->right;root->left = c->right; // перенос поддерева Nc->right = root; // а становится потомком сb->right = c->left; // перенос поддерева Mс->left = b; // b становится потомком creturn c; // указатель на новый корень дерева}10.4.1. Задачи для самостоятельного решения10.4.1.
Описать функцию, которая определяет, является ли данное двоичное дереводеревом поиска:а) рекурсивно;б) нерекурсивно, используя определенные ранее типы данных «стек» и«очередь».10.4.2. Описать функцию, которая для заданного двоичного дерева поиска:а) находит наименьшее значение в нем (считать, что дерево непустое);б) добавляет заданный элемент в дерево поиска (если элемент уже был вдереве, то не добавлять);в) удаляет из непустого дерева поиска его максимальный элемент;г) находит в дереве поиска максимальное и второе по величине значения(считать, что дерево содержит не менее двух элементов);д) удаляет из дерева поиска элемент с заданным значением (если он есть);е) определяет, является ли заданное дерево поиска АВЛ-деревом.11. Схема компиляции Си-программы.
Препроцессор.Компоновщик. ОтладчикРеальные программы на Си, как правило, состоят из нескольких файлов. Средиэтих файлов могут быть заголовочные файлы, содержащие интерфейс программы или еечастей (т.е. набор функций и переменных, с помощью которых можно использоватьфункциональность, реализованную программой), и файлы с реализацией частей68программы (с расширением .c). В Си используется раздельная компиляция, то есть всефайлы с кодом программы можно компилировать отдельно.Схема компиляции Си-программы представлена на рисунке 7. В ходе компиляцииодного файла сначала этот файл обрабатывается препроцессором – компонентом,производящим набор текстовых подстановок над файлом для получения егоокончательного вида и передачи компилятору. Потом компилятор получает ассемблерныйкод, то есть представляет программу в виде последовательности команд центральногопроцессора и описания необходимых ячеек в глобальной и статической памяти.
Далееассемблер получает по файлу на языке ассемблера т.н. объектный файл (как правило,имеющий расширение .o на Unix-подобных системах), в котором команды ассемблеразакодированы в двоичном виде, а также описан вид статической и глобальной памяти.Наконец, компоновщик обеспечивает слияние нескольких объектных файлов в одинисполняемый файл программы.Рис. 7. Схема компиляции многомодульной программы.11.1. ПрепроцессорПрепроцессор Си обеспечивает текстовую обработку файла программы допередачи ее компилятору.
Среди задач препроцессора можно назвать обеспечениемодульности программы (т.е. описание интерфейсных функций программы взаголовочных файлах и их подключение), обеспечение переносимости программы (за счетусловной компиляции), автоматическая генерация однотипных участков кода (за счетмакросов). Управление препроцессором обеспечивается включением в текст программыдиректив препроцессора. При обработке каждой директивы препроцессор меняет текст69программы определенным образом, после чего удаляет из текста обработанную директиву.После окончания работы препроцессора компилятору Си на вход подается файл стекстом программы, содержащим лишь определения и объявления функций и объявленияпеременных, как описано в разделе 1.
Строго говоря, до этапа препроцессированиякомпилятор также производит предварительную подготовку текста программы –обрабатывает многобайтовые символы, заменяет комментарии пробелом и т.п., – норассмотрение этого процесса не входит в задачи настоящего пособия.Подключение заголовочных файлов программы осуществляется с помощьюдирективы #include <file.h> или #include "file.h". Как правило, списокдиректив #include для подключения необходимых файлов указывается в первыхстроках .c-файла.
Первый вариант директивы с заключением имени файла в угловыескобки используется для общесистемных библиотек, включая стандартную библиотекуСи, а второй вариант (с двойными кавычками) – для пользовательских файлов. В скобкахили кавычках находится имя получаемого файла или относительный путь к нему. Разницав двух вариантах директивы заключается в разных наборах каталогов, относительнокоторых ищутся заданные в директиве пути к подключаемым заголовочным файлам.Директива #define служит для определения некоторого имени, называемогомакросом, и соответствующего ему текста подстановки, или тела макроса. Например,директива#defineDEBUGPRINTfprintf(stderr,"debugoutput:")определяет макрос DEBUGPRINT, при этом после обработки директивы далее в текстепрограммы препроцессор заменяет все вхождения имени макроса в текст на его тело(выполняется т.н.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
