Учебное пособие Чебоксары 2008 удк 004. 657 П 36 icon

Учебное пособие Чебоксары 2008 удк 004. 657 П 36



Смотрите также:
1   2   3   4   5   6   7
^

Лабораторный практикум


Практикум состоит из четырёх лабораторных работ по темам: «Стеки и очереди», «Бинарные деревья», «Поиск в таблице значений», «Сортировка значений в таблице».

Выполнение лабораторных работ предполагает четыре этапа: подготовку, непосредственно выполнение, оформление отче­та и защиту работы.

^ Подготовка к работе выполняется в часы самостоятель­ных занятий и заключается в следующем.

1. Изучение описания работы и других теоретических сведе­ний, касающихся тематики выполняемой работы.

2. Анализ задач и, при необходимости, их формализация. Формализация требуется в том случае, если имеется неформаль­ная постановка задачи, и заключается в переходе от неформаль­ной словесной постановки к математической формулировке. В результате анализа задачи определя­ются методы решения.

3. Выбор и описание структур данных и разработка алго­ритмов. Задачи выбора структур данных и разработки алгорит­мов взаимосвязаны; вo многих случаях существует прямая зависимость алгоритма от выбранной структуры данных, и, наоборот, алгоритм определяет необходимые структуры данных. Выбранные структуры данных должны быть обоснованы и подробно описаны в отчете о работе. Алгоритмы могут быть представлены в произвольной форме: по шагам, в виде блок-схемы, с помощью псевдокода (используя основные конструкции языков програм­мирования) и т. п. Для каждого алгоритма должны быть четко определены вход (исходные данные) и выход (результаты вы­числений). Следует помнить, что алгоритм является формаль­ным описанием вычислительной процедуры и в нем необходимо использовать обозначения, определенные в формальной поста­новке задачи. Поэтому алгоритм не должен представляться тек­стом программы; излишние подробности, связанные с требова­ниями синтаксиса языка программирования, обычно заслоняют существо дела.

4. Программная реализация. Заключается в представлении структур данных и алгоритмов соответствующими конструк­циями выбранного языка программирования. При этом должны быть указаны идентификаторы переменных, подпрограмм и т. п., сопоставленные с соответствующими элементами формального алгоритма. Тексты программ должны содержать подробные ком­ментарии, поясняющие назначение процедур, их параметров, ис­пользование переменных, смысл и особенности реализации от­дельных программных блоков.

5. Подготовка к экспериментальным исследованиям. Этот пункт необходим для тех работ, в которых предусмотрены экс­периментальные исследования алгоритмов. Заключается в раз­работке алгоритмов и программ проведения исследований в со­ответствии с технологией, приведенной в описании работы, и подготовке специальных таблиц для записи результатов иссле­дований. При исследовании алгоритмов подсчитываются раз­личные характеристики и фиксируется время вычислений. Для подсчета характеристик необходимо предусмотреть в програм­мах соответствующие счетчики. Фиксируется же только чистое время работы алгоритмов – операции с дополнительными счетчиками не должны учитываться. Поэтому для каждого иссле­дуемого алгоритма следует использовать две программные реа­лизации – со счетчиками (для подсчета значений характеристик) и без них (для фиксации времени). Если под­готовка не выполнена, студент не допускается к выполнению ла­бораторной работы.

^ Выполнение работы заключается в вводе текстов про­грамм, их трансляции и отладке на тестовых примерах, а также в проведении экспериментальных исследований. В ряде работ по полученным данным и времени вычислений требуется построить аппроксимирующие функции и вычислить аналитические зави­симости времени вычислений от размера входа. Для этого можно использовать любой метод решения задачи аппроксимации. По­рядок выполнения приводится в описании каждой работы. Вы­полнение работы подтверждается подписью преподавателя в от­чете, что означает допуск к защите работы.

Отчет о работе должен содержать:

1. Титульный лист.

2. Цель работы.

3. Информацию в соответствии с подготовкой к работе.

4. Результаты выполнения работы (результаты решения за­дач, таблицы, графики, аналитические и/или экспериментальные зависимости и т. д.).

5. Выводы по работе, отражающие анализ результатов и предпочтительные области применения разработанных структур данных и алгоритмов.

6. Тексты программ в виде текстовых файлов.

^ Защита работы заключается в опросе студента препода­вателем. Преподаватель вправе задавать вопросы по всем разде­лам отчета: теоретической части, аспектам выбора структур данных и разработки алгоритмов, программной реализации, резуль­татам исследований. По итогам опроса решается вопрос о защи­те лабораторной работы.

^

Лабораторная работа 1.

Стеки и очереди


Цель работы: 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 – указатель на конец очереди.

Вариант
Задание

1

Разработать реализации для очередей, состоящих из действительных чисел, с использованием массивов и указателей

2

Реализовать двухстороннюю очередь, если элементами являются действительные числа

3

Написать программу поиска элементов в позициях p для стека

4

Разработать реализации для стека, состоящего из действительных чисел, с использованием массивов и указателей

5

Написать программу поиска элементов в позициях p для очереди

6

Написать программу сортировки элементов для очереди

7

Написать программу обмена элементами в позициях p и NEXT(p) для стека

8

Написать программу обмена элементами в позициях p и NEXT(p) для очереди

9

Написать программу сложения и умножения двух стеков

10

Написать программу сложения и умножения двух очередей

^ Пример выполнения

Задание: написать программы, реализующие операции над стеками и очередями, с помощью указателей:

  1. функция STACKTOP(Q), которая определяет значение элемента в вершине стека Q без его удаления (не определена для пустого стека);

  2. процедура INSERT(S,X), которая помещает элемент X в конец очереди S;

  3. функция REMOVE(S), которая удаляет элемент из начала очереди S, т.е. операция X:=REMOVE (S) удаляет элемент из начала очереди S и присваивает его значение переменной X (не определена для пустой очереди).

Реализация функции 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;




страница4/7
Дата конвертации17.11.2013
Размер1,66 Mb.
ТипУчебное пособие
1   2   3   4   5   6   7
Разместите кнопку на своём сайте или блоге:
rud.exdat.com


База данных защищена авторским правом ©exdat 2000-2012
При копировании материала укажите ссылку
обратиться к администрации
Документы