Поиск кратчайшего пути в лабиринте (стр. 2 из 4)

3 Технический проект

3.1 Диаграмма потоков данных

Программа имеет 4 основных процесса, отражающие основные функции программы:

Рисунок 3.1 – Диаграмма 1-го уровня

Рисунок 3.2 – Детализация процесса “Ввод лабиринта и его редактирование”

3.2 Словарь данных

Лабиринт – множество комнат, соединённых между собой дверьми.

Комната – символически изображенный квадрат, заданный в лабиринте.

Дверь –устройство, соединяющее комнаты.

Команда – в процессе диалоговой работы пользователя с программой, нажатие пользователем функциональной клавиши, за которой закреплено определенное действие. Существует 5 видов: ввод комнаты, ввод двери, удаление (комнаты или двери), сохранение и выход.

Команда ввод комнаты – нажатие пользователем клавиши <к>.

Команда ввод двери - нажатие пользователем клавиши <д>.

Команда удаление - нажатие пользователем клавиши <я>.

Команда сохранение - нажатие пользователем клавиши <с>.

Команда выход - нажатие пользователем клавиши <esc>.

Координаты – численное значение, определяющее положение объекта в лабиринте.

Карта поля – двумерный массив, который содержит координаты всех комнат и дверей.

Карта прохождения - двумерный массив, который содержит координаты комнат и дверей, через которые проходит кратчайший путь.

3.3 Спецификация процессов

Процесс 1 Ввод лабиринта и его редактирование.

Данный процесс служит для формирования лабиринта и его редактирования

Вход: координаты комнат и дверей

Выход: лабиринт

Действия: Формирование лабиринта путем заполнения его структуры координатами комнат и дверей.

Процесс 1.1 Ввод комнаты

Прежде чем передать процессу 1 координаты комнат или дверей, необходимо преобразовать команды пользователя по расстановке комнат и дверей, в соответствующие координаты для каждой комнаты и двери. Процессы 1.1-1.3 считывают код клавиши, нажатой пользователем, и в соответствии с кодом клавиши и местоположением курсора формируют код и координаты.

Вход: ввод комнаты

Выход: код и координаты комнаты

Процесс 1.2 Ввод двери

Вход: ввод двери

выход:код и координаты двери

Процесс 1.3 Удаление комнаты или двери

Процесс удаления записывает в структуру лабиринта код 0, по заданным координатам, что обозначает пустое место, т.е. комната или дверь была удалена из лабиринта.

Вход:удаление

Выход:код и координаты

Процесс 2 Поиск пути

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

Вход: структура лабиринта

Выход: кратчайший путь в лабиринте.

Процесс 4 Отображение лабиринта

При вводе комнат или дверей необходимо чтобы пользователь видел отображение введенной информации на экране монитора. Данный процесс должен визуализировать лабиринт и найденный путь на экране.

Вход: координаты комнат и дверей

Выход: изображение лабиринта

Процесс 3 Сохранение введенных данных в файле

Для того чтобы координаты комнат или дверей не вводить заново при каждом запуске программы, необходимо сохранять их в файл.

Вход: структура лабиринта

Выход: файл с сохраненной структурой лабиринта

Процесс 3 Считывание данных из файла

Вход: файл с сохраненной структурой лабиринта

Выход: структура лабиринта

3.4 Определение формы представления входных и выходных данных

Входные данные:

Это последовательность символов, вводимая пользователем с клавиатуры.

Выходные данные:

Отображение лабиринта и пути его прохождения на экране монитора, а также файл с сохраненным лабиринтом.

Команды:

загрузка лабиринта

сохранение лабиринта

создание комнаты

создание двери

удаление комнаты или двери

выход

3.5 Разработка структуры программы

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

3.6 Спецификация модулей

Модуль создания и прорисовки сетки лабиринта

Входные данные: отсутствуют

Выходные данные: карта поля

Функции: создание карты поля

Модуль ввода и корректировки данных

Входные данные: команды

Выходные данные: карта поля

Функции - ввод данных и предоставление пользователю возможности их редактирования.

Модуль считывания и сохранения структуры лабиринта

Входные данные: команды, карта поля

Выходные данные: карта поля , файл

Внешние эффекты: загрузка сохраненного лабиринта, также модуль сохраняет файл на диске.

Функции - считывание и сохранения структуры лабиринта.

Модуль визуализации

Входные данные: координаты комнат и дверей

Выходные данные: отсутствуют

Внешние эффекты: на экране монитора появляется лабиринт и путь прохождения.

Функции – вывод на экран монитора информации.

Модуль расчета кратчайшего пути лабиринта

Входные данные: карта поля

Выходные данные: карта прохождения

Функции – нахождение путей прохождения и поиск кратчайшего.

3.7 Переход к тексту программы

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

Написание программного кода будет проводиться с использованием среды программирования Borland C++.

Реализация функций программы зависит полностью от программиста.

4 Рабочий проект

4.1 Программирование и отладка программы

Исходя из требований к программному обеспечению, программа кодировалась в среде программирования Borland C++ для функционирования в операционной системе Windows 9x. (Смотрите приложение В)

4.2 Тестирование программы

Тестирование программы заключается в проверке работы основных функций. Была разработана и проведена серия тестовых примеров для программы. Программа и методика испытаний приведены в приложении В. Результаты тестирования показали работоспособность программы и его соответствие предъявляемым требованиям.

Предложенное ПО тестировалось как во время разработки, так и после её завершения.

Для тестирования делались попытки ввода недействительных данных и попытки выполнить недопустимые действия как при программировании, так и в режиме взаимодействия с пользователями. Предложенное ПО адекватно реагировало на такие действия.

Заключение

В данной документации была разработана программа “Поиск кратчайшего пути”, которая создает лабиринт и находит кратчайший путь прохождения.

Описана область применения программного продукта. Приводятся диаграммы потоков данных, диаграммы состояния, диаграммы взаимодействия модулей. Доступным языком описывается методология создания программы.

Разработана спецификация функций программы, описано поведение программы в критических ситуациях, приводится спецификация модулей. В документации также приведены результаты тестирования программы
ПРИЛОЖЕНИЕ А

(обязательное)

Описание программы

Общие сведения

Наименование программы: “Поиск кратчайшего пути”

Для функционирования программы необходима Операционная Система Windows 9x.

Кодировка производилась в среде программирования Borland C++.

Функциональное назначение

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

Описание логической структуры

Программа имеет главную функцию main, которая описана в файле sapr_kyrsovik.cpp, с которой начинается выполнение программы. Также программа имеет библиотечные функции, которые описаны в заголовочном файле head.h. Заголовочный файл содержит все остальные функции, используемые в пограмме. Программа имеет структуру с именем Lab, которая содержит двухмерный массив карты лабиринта (Мар[MY][MX]) и двухмерный массив карты прохождения (Put[MY][MX]). В эту структуру производится запись координат комнат и дверей лабиринта.

Программа состоит из следующих функций:

int Grin(struct Lab *P)

Она выполняет:

инициализацию графики: очищается экран, включается графический режим

рисует сетку лабиринта

инициализацию масивов структуры P

void Rasstan(struct Lab *P) – функция расставляет комнаты и двери на карте поля, а также удаляет их, это реализуется с помощью клавиш управления курсором (<

> - вверх, <

> - вниз, <

> - вправо, <

> - влево) и клавиш специального назначения (например, при помощи клавиши <к> происходит ввод комнаты, при помощи клавиши <д> происходит ввод двери, при помощи клавиши <я> можно удалять комнаты или двери). Эта функция вызывает дополнительные две функции: