Федеральное государственное бюджетное образовательное учреждение
высшего профессионального образования
«Тульский государственный университет»
Кафедра электронных вычислительных машин
Сборник методических указаний к лабораторным работам
по дисциплине
ТЕХНОЛОГИИ И МЕТОДЫ ПРОГРАММИРОВАНИЯ
Специальность: 090303 «Информационная
безопасность автоматизированных систем»
Формы обучения очная
Тула 2012
Методические указания к лабораторным работам составлены доцентом каф. ЭВМ А.А Сычуговым. и обсуждены на заседании кафедры ЭВМ факультета кибернетики
протокол №___ от "___"____________ 20___ г.
Зав. кафедрой________________В.С Карпов
Методические указания к лабораторным работам пересмотрены и утверждены на заседании кафедры ЭВМ факультета кибернетики
протокол №___ от "___"____________ 20___ г.
Зав. кафедрой________________В.С Карпов
Содержание
|
3 |
2. Лабораторная работа №2. Использование очереди при решении задач обслуживания ВС поступающих заявок……………………..
|
6 |
3. Лабораторная работа №3. Аналитические преобразования полиномов от нескольких переменных………………………………..
|
10 |
4. Лабораторная работы №4. Организация доступа в таблицах по имени………………………………………………………………………………….
|
14 |
5. Лабораторная работы №5. МЕТОДЫ ВНУТРЕННЕЙ СОРТИРОВКИ………...
|
17 |
6. Лабораторная работы №6. СПОСОБЫ задания графов…………………………. |
19 |
Лабораторная работа №1 Использование стека при решении различных задач
1. Цель работы
Начальное знакомство с элементами динамических структур данных (на примере стека) и получение практических навыков разработки структур хранения для динамических структур данных на основе вектора памяти (массива).
2. Теоретические сведения
Разработку программы рекомендуется выполнить в виде программного комплекса, состоящего из двух частей. В первой - основной - части программы следует выполнить решение поставленной задачи. Действия, связанные с реализацией динамической структуры стек, следует вынести во вторую часть программы, оформленную в виде макромодуля Unit.
Организация программного интерфейса
Требуемая дисциплина обработки номеров скобок при решении задачи анализа правильности расстановки скобок может быть обеспечена при помощи динамической структуры данных типа стек. Процедуры и функции, необходимые для реализации стека, следует оформить в виде макромодуля Unit. Рекомендуемый состав интерфейсной секции модуля Unit состоит в следующем.
Процедура InitStack выполняет инициализацию структуры; процедура должна быть выполнена перед началом работы со стеком.
Процедура PushStack используется для записи в стек нового значения.
Функция PopStack обеспечивает получение значения, записанного в стек последним; операция выполняется с удалением возвращаемого значения из стека.
Функция TopStack также используется для получения значения, записанного в стек последним; в отличие от предыдущей функции, возвращаемое значение из стека не удаляется.
Функция IsEmptyStack проверяет наличие значений в стеке и возвращает значение True в случае, когда в стеке элементов нет.
Функция IsFullStack оценивает возможность добавления в стек новых значений и возвращает значение True в случае, когда выделенная память для хранения стека заполнена полностью.
Функция StackError обеспечивает получение кодов завершения выполняемых процедур и функций стека. Рекомендуемая методика обработки ошибочных ситуаций при использовании стека состоит в следующем:
- все процедуры и функции стека при окончании своей работы записывают соответствующий код завершения в переменную StErr (эту переменную рекомендуется скрыть от пользователя и описать в секции реализации модуля);
- возможные ошибки могут состоять в попытке записи нового элемента в заполненный стек, в попытке извлечения значения из пустого стека и др.; коды возможных ошибочных ситуаций перечислены в секции констант модуля;
- функция StackError возвращает значение кода, записанное в переменной StErr, обеспечивая тем самым проверку кода завершения последней выполненной процедуры или функции стека; передачу кода в функции StackError следует выполнить с очисткой значения переменной StErr.
Приведенную форму интерфейсной секции следует сохранить и для последующих реализаций стека при использовании иных различных структур хранения.
Структура хранения стека
Выбор структуры хранения стека
В качестве структуры хранения стека целесообразно использовать одномерный (одноиндексный) массив Stack, количество элементов которого (максимальный размер стека) следует задать при помощи константы StackSize, а для фиксации количества сохраненных в стеке значений использовать переменную StackNum.
Описание массива и переменных следует провести в секции реализации модуля Unit
Процедура SetStErr секции реализации может быть использована при разработке для записи кода завершения в переменную StErr.
Рекомендуемая последовательность реализации процедур и функций стека может быть следующей
InitStack
SetStErr
IsEmptyStack
IsFullStack
PushStack
PopStack
StackError
TopStack
При реализации процедур и функций стека может оказаться полезной разработка процедур для автоматической проверки правильности функционирования стека. Возможная процедура проверки может состоять, например, в выполнении последовательности следующих действий:
- запись значения в стек;
- чтение значения из стека;
- проверка полученного значения.
При реализации лабораторной работы может оказаться полезной и процедура демонстрации содержимого стека на экране компьютера.