Учебное пособие Чебоксары 2008 удк 004. 657 П 36
| Лабораторный практикум Подготовка к работе Выполнение работы Защита работы Лабораторная работа 1. Стеки и очереди Необходимые исходные сведения Пример выполнения |
Смотрите также:
- Учебное пособие Владимир 2011 удк 657. 1: 69 ббк 65. 052. 253. 1
- Учебное пособие Новомосковск 2008 удк 93/99
- Учебное пособие Краснодар 2012 удк 159. 9+37. 01]: 378. 147 Ббк 74. 00
- Учебное пособие москва 2012 удк 32. 001 Ббк 66. 0
- Учебное пособие Новосибирск 2012 удк 330. 4 (075. 8) К. э н., доцент М. В. Облаухова
- Учебное пособие Санкт-Петербург 2010 удк 616-058: 93/99+61(06) isbn 57645-0189
- Учебное пособие Томский политехнический университет 2009 удк 000000 ббк 00000
функция STACKTOP(Q), которая определяет значение элемента в вершине стека Q без его удаления (не определена для пустого стека);
процедура INSERT(S,X), которая помещает элемент X в конец очереди S;
функция REMOVE(S), которая удаляет элемент из начала очереди S, т.е. операция X:=REMOVE (S) удаляет элемент из начала очереди S и присваивает его значение переменной X (не определена для пустой очереди).
Практикум состоит из четырёх лабораторных работ по темам: «Стеки и очереди», «Бинарные деревья», «Поиск в таблице значений», «Сортировка значений в таблице». Выполнение лабораторных работ предполагает четыре этапа: подготовку, непосредственно выполнение, оформление отчета и защиту работы. ^ выполняется в часы самостоятельных занятий и заключается в следующем. 1. Изучение описания работы и других теоретических сведений, касающихся тематики выполняемой работы. 2. Анализ задач и, при необходимости, их формализация. Формализация требуется в том случае, если имеется неформальная постановка задачи, и заключается в переходе от неформальной словесной постановки к математической формулировке. В результате анализа задачи определяются методы решения. 3. Выбор и описание структур данных и разработка алгоритмов. Задачи выбора структур данных и разработки алгоритмов взаимосвязаны; вo многих случаях существует прямая зависимость алгоритма от выбранной структуры данных, и, наоборот, алгоритм определяет необходимые структуры данных. Выбранные структуры данных должны быть обоснованы и подробно описаны в отчете о работе. Алгоритмы могут быть представлены в произвольной форме: по шагам, в виде блок-схемы, с помощью псевдокода (используя основные конструкции языков программирования) и т. п. Для каждого алгоритма должны быть четко определены вход (исходные данные) и выход (результаты вычислений). Следует помнить, что алгоритм является формальным описанием вычислительной процедуры и в нем необходимо использовать обозначения, определенные в формальной постановке задачи. Поэтому алгоритм не должен представляться текстом программы; излишние подробности, связанные с требованиями синтаксиса языка программирования, обычно заслоняют существо дела. 4. Программная реализация. Заключается в представлении структур данных и алгоритмов соответствующими конструкциями выбранного языка программирования. При этом должны быть указаны идентификаторы переменных, подпрограмм и т. п., сопоставленные с соответствующими элементами формального алгоритма. Тексты программ должны содержать подробные комментарии, поясняющие назначение процедур, их параметров, использование переменных, смысл и особенности реализации отдельных программных блоков. 5. Подготовка к экспериментальным исследованиям. Этот пункт необходим для тех работ, в которых предусмотрены экспериментальные исследования алгоритмов. Заключается в разработке алгоритмов и программ проведения исследований в соответствии с технологией, приведенной в описании работы, и подготовке специальных таблиц для записи результатов исследований. При исследовании алгоритмов подсчитываются различные характеристики и фиксируется время вычислений. Для подсчета характеристик необходимо предусмотреть в программах соответствующие счетчики. Фиксируется же только чистое время работы алгоритмов – операции с дополнительными счетчиками не должны учитываться. Поэтому для каждого исследуемого алгоритма следует использовать две программные реализации – со счетчиками (для подсчета значений характеристик) и без них (для фиксации времени). Если подготовка не выполнена, студент не допускается к выполнению лабораторной работы. ^ заключается в вводе текстов программ, их трансляции и отладке на тестовых примерах, а также в проведении экспериментальных исследований. В ряде работ по полученным данным и времени вычислений требуется построить аппроксимирующие функции и вычислить аналитические зависимости времени вычислений от размера входа. Для этого можно использовать любой метод решения задачи аппроксимации. Порядок выполнения приводится в описании каждой работы. Выполнение работы подтверждается подписью преподавателя в отчете, что означает допуск к защите работы. Отчет о работе должен содержать: 1. Титульный лист. 2. Цель работы. 3. Информацию в соответствии с подготовкой к работе. 4. Результаты выполнения работы (результаты решения задач, таблицы, графики, аналитические и/или экспериментальные зависимости и т. д.). 5. Выводы по работе, отражающие анализ результатов и предпочтительные области применения разработанных структур данных и алгоритмов. 6. Тексты программ в виде текстовых файлов. ^ заключается в опросе студента преподавателем. Преподаватель вправе задавать вопросы по всем разделам отчета: теоретической части, аспектам выбора структур данных и разработки алгоритмов, программной реализации, результатам исследований. По итогам опроса решается вопрос о защите лабораторной работы. ^ Цель работы: 1) ознакомиться со способами реализации стеков и очередей и выполнения над ними операций; 2) получить практические навыки в программировании с использованием стеков и очередей. ^ Стеки и очереди – это динамические структуры данных с ограниченным видом операций, включением новых и выключением старых переменных. Стек представляет собой последовательность элементов с одной точкой доступа, называемой вершиной стека. Все элементы последовательности, кроме элемента, расположенного в вершине стека, недоступны. Новый элемент добавляется только в вершину стека, сдвигая остальные элементы последовательности. Исключить можно только элемент из вершины стека. Остальные элементы при этом сдвигаются в сторону вершины. Таким образом, стек работает по принципу «последним пришел – первым ушел» и часто называется структурой LIFO (Last In – First Out). В алгоритмах операцию добавления элемента в стек записывают в виде S←X (элемент X поместить в вершину стека S); операцию исключения в виде X←S (исключить элемент X из вершины стека S и присвоить его значение переменной X). В литературе эти операции традиционно называются PUSH (добавление) и POP (исключение). Очередь представляет собой последовательность элементов с двумя точками доступа: начало (голова) и конец (хвост). Новый элемент добавляется всегда в конец очереди, исключается всегда элемент, расположенный в начале очереди. Таким образом, очередь работает по принципу «первым зашел – первым ушел» и часто называется структурой FIFO (First In – First Out). В алгоритмах операцию включения элемента в очередь записывают в виде Q←X (элемент X помещается в конец очереди Q), а операцию исключения из очереди – в виде X←Q (исключить элемент X из начала очереди Q и присвоить его значение переменной X). Стеки и очереди удобно реализовывать с помощью указателей, т.к. указатели имеют весьма гибкую структуру. Описание типа стек: type ct=^celltype; celltype=record element:byte; next:ct; end; stack=record top:ct; fin:ct; end; где top – указатель на вершину стека. Описание типа очередь: type ct=^celltype; celltype=record element:byte; next:ct; end; queue=record front:ct; rear:ct; end; где front – указатель на начало очереди, rear – указатель на конец очереди.
^ Задание: написать программы, реализующие операции над стеками и очередями, с помощью указателей: Реализация функции STACKTOP(Q): function stacktop(var s:stack):byte; begin stacktop:=s.top^.next^.element; end; Реализация процедуры INSERT(S,X): procedure insert(var q:queue;x:byte); begin new(q.rear^.next); q.rear:=q.rear^.next; q.rear^.element:=x; q.rear^.next:=nil; end; Реализация функции REMOVE(S): function remove(var q:queue):byte; begin remove:=q.front^.next^.element; delstart(q); end;
|
