Лекции (1171139), страница 18
Текст из файла (страница 18)
Эта функция легкореализуется с помощью рекурсии: достаточно подсчитать число вершин для каждого издвух поддеревьев, соответствующих левому и правому сыновьям корневой вершины,сложить их и прибавить к сумме единицу. Если левый или правый сын отсутствует, тосоответствующее слагаемое равно нулю. Вот фрагмент программы, реализующийфункцию numNodes.// Описание структуры, представляющей вершину дереваstruct TreeNode {struct TreeNode *parent; // Указатель на отца,struct TreeNode *left;//на левого сына,struct TreeNode *right; //на правого сынаvoid *value;// Значение в вершине};// Рекурсивная реализация функции,// вычисляющей число вершин дерева.// Вход: указатель на корень поддерева// Возвращаемое значение: число вершин поддереваint numNodes(const struct TreeNode *root) {int num = 0;if (root == 0) { // Для нулевого указателя на кореньreturn 0;// возвращаем ноль}if (root->left != 0) {// Есть левый сын =>num += numNodes(root->left); // вызываем функцию}// для левого сынаif (root->right != 0) {// Есть правый сын =>num += numNodes(root->right); // вызываем ф-цию}// для правого сына}return num + 1; // Возвращаем суммарное число вершинЗдесь неоднократно применялась операция стрелочка −> для доступа к полю структурычерез указатель на нее.При создании переменной типа структуры память под все элементы структурывыделяется последовательно для каждого элемента.
Рассмотрим пример выделенияпамяти под структуру:struct structA {char cA;char sA[2];float fA;};При создании переменной структурного типа structA будет выделено 7 байтов. Элементыструктуры будут размещены в памяти в следующем порядке:char cAchar sA[2]float fA651234567Простейшие структуры данных.
Стек. Очередь.Наиболее важными из простейших структур данных являются стек и очередь. Этиструктуры встречаются в программировании буквально на каждом шагу, в самыхразнообразных ситуациях.ОчередьОчередь как структура данных понятна даже людям, не знакомым с программированием.
Очередьсодержит элементы, как бы выстроенные друг за другом в цепочку. У очереди есть начало и конец.Добавлять новые элементы можно только в конец очереди, забирать элементы можно только из начала. Вотличие от обычной очереди, которую всегда можно при желании покинуть, из середины программистскойочереди удалять элементы нельзя. Очередь можно представить в виде трубки. В один конец трубки можнодобавлять шарики — элементы очереди, из другого конца они извлекаются. Элементы в середине очереди,т.е. шарики внутри трубки, недоступны. Конец трубки, в который добавляются шарики, соответствует концуочереди, конец, из которого они извлекаются — началу очереди.
Таким образом, концы трубки несимметричны, шарики внутри трубки движутся только в одном направлении.Рис. 3.3 ОчередьВ принципе, можно было бы разрешить добавлять элементы в оба конца очереди изабирать их также из обоих концов. Такая структура данных в программировании тожесуществует, ее название — "дек", от англ. Double Ended Queue, т.е. очередь с двумяконцами.
Дек применяется значительно реже, чем очередь.Использование очереди в программировании почти соответствует ее роли вобычной жизни. Очередь практически всегда связана с обслуживанием запросов, в техслучаях, когда они не могут быть выполнены мгновенно.
Очередь поддерживает такжепорядок обслуживания запросов. Рассмотрим, к примеру, что происходит, когда человекнажимает клавишу на клавиатуре компьютера. Тем самым человек просит компьютервыполнить некоторое действие. Например, если он просто печатает текст, то действиедолжно состоять в добавлении к тесту одного символа и может сопровождатьсяперерисовкой области экрана, прокруткой окна, переформатированием абзаца и т.п.Любая, даже самая простая, операционная система всегда в той или иной степенимногозадачна.
Это значит, что в момент нажатия клавиши операционная система можетбыть занята какой-либо другой работой. Тем не менее, операционная система ни в какойситуации не имеет права проигнорировать нажатие на клавишу. Поэтому происходитпрерывание работы компьютера, он запоминает свое состояние и переключается наобработку нажатия на клавишу. Такая обработка должна быть очень короткой, чтобы ненарушить выполнение других задач.
Команда, отдаваемая нажатием на клавишу, простодобавляется в конец очереди запросов, ждущих своего выполнения. После этогопрерывание заканчивается, компьютер восстанавливает свое состояние и продолжаетработу, которая была прервана нажатием на клавишу. Запрос, поставленный в очередь,будет выполнен не сразу, а только когда наступит его черед.Реализация очереди на базе массива. Как уже было сказано, программистумассив дан свыше, все остальные структуры данных нужно реализовывать на егооснове.
Конечно, такая реализация может быть многоэтапной, и не всегда массиввыступает в качестве непосредственной базы реализации. В случае очереди наиболеепопулярны две реализации: непрерывная на базе массива и ссылочная реализация, илиреализация на базе списка. При непрерывной реализации очереди в качестве базывыступает массив фиксированной длины N, таким образом, очередь ограничена и неможет содержать более N элементов.
Индексы элементов массива изменяются в66пределах от 0 до N - 1. Кроме массива, реализация очереди хранит три простыепеременные: индекс начала очереди, индекс конца очереди, число элементов очереди.Элементы очереди содержатся в отрезке массива от индекса начала до индексаконца.Рис. 3.4 Очередь на базе массива.При добавлении нового элемента в конец очереди индекс конца сперва увеличивается наединицу, затем новый элемент записывается в ячейку массива с этим индексом.Аналогично, при извлечении элемента из начала очереди содержимое ячейки массива синдексом начала очереди запоминается в качестве результата операции, затем индексначала очереди увеличивается на единицу.
Как индекс начала очереди, так и индекс концапри работе двигаются слева направо.СтекСтек — самая популярная и, пожалуй, самая важная структура данных впрограммировании. Стек представляет собой запоминающее устройство, из которогоэлементы извлекаются в порядке, обратном их добавлению. Это как бы неправильнаяочередь, в которой первым обслуживают того, кто встал в нее последним. Впрограммистской литературе общепринятыми являются аббревиатуры, обозначающиедисциплину работы очереди и стека. Дисциплина работы очереди обозначается FIFO, чтоозначает первым пришел — первым уйдешь (First In First Out).
Дисциплина работы стекаобозначается LIFO, последним пришел — первым уйдешь (Last In First Out).Стек можно представить в виде трубки с подпружиненным дном, расположеннойвертикально. Верхний конец трубки открыт, в него можно добавлять, или, как говорят,заталкивать элементы. Общепринятые английские термины в этом плане очень красочны,операция добавления элемента в стек обозначается push, в переводе "затолкнуть,запихнуть". Новый добавляемый элемент проталкивает элементы, помещенные в стекранее, на одну позицию вниз. При извлечении элементов из стека они как бывыталкиваются вверх, по-английски pop ("выстреливают").Рис.
3.5 Стек.Примером стека может служить стог сена, стопка бумаг на столе, стопка тарелок ит.п. Отсюда произошло название стека, что по-английски означает стопка. Тарелкиснимаются со стопки в порядке, обратном их добавлению. Доступна только верхняятарелка, т.е. тарелка на вершине стека.Стек применяется довольно часто, причем в самых разных ситуациях. Объединяет их следующаяцель: нужно сохранить некоторую работу, которая еще не выполнена до конца, при необходимостипереключения на другую задачу.
Стек используется для временного сохранения состояния не выполненногодо конца задания. После сохранения состояния компьютер переключается на другую задачу. По окончании67ее выполнения состояние отложенного задания восстанавливается из стека, и компьютер продолжаетпрерванную работу.Реализация стека на базе массива. Реализация стека на базе массива является классикойпрограммирования. Иногда даже само понятие стека не вполне корректноотождествляется с этой реализацией.Базой реализации является массив размера N, таким образом, реализуется стекограниченного размера, максимальная глубина которого не может превышать N. Индексыячеек массива изменяются от 0 до N - 1.
Элементы стека хранятся в массиве следующимобразом: элемент на дне стека располагается в начале массива, т.е. в ячейке с индексом 0.Элемент, расположенный над самым нижним элементом стека, хранится в ячейке синдексом 1, и так далее. Вершина стека хранится где-то в середине массива. Индексэлемента на вершине стека хранится в специальной переменной, которую обычноназывают указателем стека (по-английски Stack Pointer или просто SP).Рис.
3.6 Стек на баземассива.Когда стек пуст, указатель стека содержит значение минус единица. При добавленииэлемента указатель стека сначала увеличивается на единицу, затем в ячейку массива синдексом, содержащимся в указателе стека, записывается добавляемый элемент. Приизвлечении элемента из стека сперва содержимое ячейки массива с индексом,содержащимся в указателе стека, запоминается во временной переменной в качестверезультата операции, затем указатель стека уменьшается на единицу.В приведенной реализации стек растет в сторону увеличения индексов ячеекмассива. Часто используется другой вариант реализации стека на базе вектора, когда дностека помещается в последнюю ячейку массива, т.е.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
