Курсовая работа: Структура данных программного комплекса "Q-дерево"
Курсовая работа: Структура данных программного комплекса "Q-дерево"
Представляемый документ содержит:
52 страницы текста и список из двух источников.
Объектом исследования является структура данных «Q-дерево».
Цель работы состоит в создании программного комплекса, обеспечивающего работу со структурой данных «Q-дерево», представленной в виде модели. Методы, используемые при разработке, – язык программирования высокого уровня Object Pascal. Созданный программный продукт обеспечивает выполнение всех требований технического задания.
Содержание
Введение
1. Техническое задание
1.1 Основание для разработки
1.2 Назначение разработки
1.3 Функциональные требования к программе
1.4 Требования к составу и параметрам технических средств
1.5 Требования к информационной и программной совместимости
1.6 Требования к программной документации
1.7 Порядок контроля и приемки
2. Рабочий проект
2.1 Модуль UnitModel
2.1.1 Назначение
2.1.2 Функциональные требования, реализуемые модулем
2.1.3 Глобальные переменные и константы модуля
2.1.4 Подпрограммы модуля
2.2 Модуль UnitMainForm
2.2.1 Назначение
2.2.2 Функциональные требования, реализуемые модулем
2.2.3 Используемые компоненты
2.2.4 Глобальные переменные и константы модуля
2.2.5 Подпрограммы модуля
Заключение
Список используемых источников
Приложение
Введение
Цель данной курсовой работы – разработка программного продукта, предназначенного для работы со структурой данных «Q-дерево». Существует множество различных структур данных, предназначенных для работы с множествами: деревья, массивы и так далее. Среди них есть Q-деревья, позволяющие хранить множества точек и обеспечивать к ним быстрый и удобный доступ. Практическое значение. Программный продукт позволяет пользоваться Q-деревьями. Актуальность разработки программного продукта состоит в увеличении скорости работы с множествами. Программный продукт должен быть разработан на языке программирования высокого уровня Object Pascal, использовать принципы объектно-ориентированного программирования и структурный подход к решению поставленных задач.
Результатом выполнения курсовой работы должен стать готовый программный продукт, отвечающий всем требованиям технического задания.
1. Техническое задание
1.1 Основание для разработки
Основанием для разработки программного продукта служит задание на курсовую работу “Q-дерево точек”.
1.2 Назначение разработки
Программный продукт разрабатывается для работы с Q-деревьями точек.
1.3 Функциональные требования к программе
1. Возможность добавления элементов в дерево
2. Удаление элементов из дерева
3. Очистка дерева
4. Подсчет количества элементов
5. Отображение элементов дерева в виде точек на карте
6. Поиск точек в заданной прямоугольной области карты
7. Возможность выбора области карты для просмотра содержащихся в ней точек
8. Отображение точек заданной области карты в отдельном окне просмотра
9. Отображение координат выбранных точек
1.4 Требования к составу и параметрам технических средств
Программный комплекс должен корректно работать на компьютере со следующими техническими характеристиками:
− процессор Intel® Celeron® CPU 2.40 ГГц;
− оперативная память объемом 512 Мб;
− жесткий диск Seagate ST380011A, объемом 80 Гб;
− видеоадаптер AGP 8X;
− клавиатура;
− манипулятор типа “мышь”.
1.5 Требования к информационной и программной совместимости
Для работы программы необходима операционная система Microsoft Windows XP Professional 2002 (SP1-2).
1.6 Требования к программной документации
Программная документация должна включать следующие документы:
· техническое задание;
· рабочий проект.
В приложении к документу "Рабочий проект" должен быть приведен листинг исходных текстов программного изделия.
1.7 Порядок контроля и приемки
1.7.1 Возможность добавления элементов в дерево, подсчет количества элементов
Добавление элементов в дерево производится щелчком левой кнопкой мыши по точке с нужными координатами в окне просмотра (рис. 1)
Рис. 1
Результат: добавление точки в дерево и его перерисовка; увеличение количества точек в дереве на единицу.
1.7.2 Удаление элементов из дерева, подсчет количества элементов
Удаление элемента производится путем выделения точки с помощью мыши в окне просмотра в режиме выделения точек и щелчка по кнопке «Удалить точку» (рис. 2)
Рис. 2
Результат: удаление точки из дерева и его перерисовка; уменьшение количества точек в дереве на единицу.
1.7.3 Очистка дерева
Очистка дерева (удаление всех элементов) производится щелчком по кнопке «Удалить все» (рис. 3)
Рис. 3
Результат: удаление всех элементов дерева и соответствующая перерисовка изображений
1.7.4 Возможность выбора прямоугольной области карты для просмотра содержащихся в ней точек, поиск точек в заданной прямоугольной области карты
Выбор области просмотра осуществляется перемещением окна выделения с помощью мыши или клавиш (рис. 4)
Рис. 4
Результат: перемещение окна выделения, поиск и отрисовка точек, находящихся в выделенной области карты.
1.7.5 Отображение элементов дерева в виде точек на карте, отображение координат выбираемых точек
Выбор точки производится с помощью щелчка левой кнопкой мыши по точке с нужными координатами в режиме выбора точек (рис. 5)
Рис. 5
Результат: отображение координат выбранной точки в строке состояния; перерисовка соответствующим цветом ее изображения в окне просмотра.
1.7.6 Отображение точек заданной области карты в отдельном окне просмотра, отображение координат выбираемых точек
Для получения координат точки без ее выделения достаточно навести указатель мыши на ее изображение в окне просмотра (рис. 6)
Рис. 6
Результат: отображение координат точки в строке состояния без ее выбора; перерисовка соответствующим цветом ее изображения в окне просмотра.
2. Рабочий проект
2.1 Модуль UnitModel
2.1.1 Назначение
Данный модуль представляет собой реализацию модели структуры данных «Q-дерево точек».
2.1.2 Функциональные требования, реализуемые модулем
· Возможность добавления элементов в дерево
· Удаление элементов из дерева
· Очистка дерева
· Поиск точек в заданной прямоугольной области карты.
2.1.3 Глобальные переменные и константы модуля
Константы
· М = 3 – максимальное число точек в листе;
- тип – целый;
- область видимости – внутри и вне модуля;
- используется в операциях вставки и удаления элементов дерева для проверки числа точек в листьях.
2.1.4 Подпрограммы модуля
2.1.4.1 Функция InsertPoint
· Функция предназначена для вставки нового элемента в Q-дерево
· Параметры
- выходной параметр – указатель на узел дерева, в которое вставляется элемент (тип PNode);
- входной параметр – границы этого узла (тип TRect);
- входной параметр – координаты вставляемой точки (тип TPoint);
· Функция возвращает логическое значение (тип boolean), указывающее на изменение количества элементов в дереве
· Локальные переменные
- CurNode – текущий квадрант (тип PNode);
- DopArray – дополнительный массив, необходимый при делении листа на новые узлы (тип TArrayOfPoints);
- midX, midY – координаты середины узла (тип real);
- NewBounds – границы нового узла, передаваемые в качестве параметра в рекурсивном вызове функции (тип TRect);
- i – счетчик цикла (тип integer).
· Словесный алгоритм
В начале своей работы функция проверяет, не является ли пустым параметр-указатель; если да, то для него выделяется память, устанавливаются начальные значения полей и вставляется новый элемент. Если он не является листом, осуществляется цикл переходов к листу с нужными границами. Далее проверяется число элементов в листе, и, если оно меньше допустимого, туда вставляется новая точка; иначе этот лист разделяется на 4 новых, его точки рекурсивно распределяются по новым листам и затем вставка новой точки.
2.1.4.2 Процедура DeletePoint
· Процедура предназначена для удаления элемента из Q-дерева
· Параметры
- выходной параметр – указатель на корневой узел дерева, из которого удаляется элемент (тип PNode);
- входной параметр – границы этого узла (тип TRect);
- входной параметр – координаты вставляемой точки (тип TPoint);
· Предусловия
Указатель на дерево не должен быть пустым
· Локальные переменные
- CurNode – текущий квадрант (тип PNode);
- ParentNode – родительский узел листа с удаляемой точкой;
- DopArray – дополнительный массив, необходимый при делении листа на новые узлы (тип TArrayOfPoints);
- midX, midY – координаты середины узла (тип real);
- PointsInNodes, numSZ, numSV, numYZ, numYV – переменные, использующиеся при подсчете числа точек в листах (тип real);
- there – индикатор наличия точки в дереве (тип boolean);
- N – число точек в листе (тип integer);
- i – счетчик цикла (тип integer).
· Словесный алгоритм
В начале своей работы функция проверяет, не является ли пустым параметр-указатель; если да – выход из подпрограммы. Если он не является листом, осуществляется цикл переходов к листу с нужными границами. Далее проверяется наличие точки в листе, и, если она там не обнаружена, процедура заканчивает свою работу; иначе происходит удаление точки из листа и последующая проверка общего числа точек в соседних листах. Если появилась возможность, соседние листы объединяются в один, старые удаляются.
2.1.4.3 Процедура ClearTree
· Процедура предназначена для удаления всех элементов Q-дерева
· Параметры
- выходной параметр указатель на узел дерева (тип PNode);
· Предусловия
Указатель на дерево не должен быть пустым
· Словесный алгоритм
В начале своей работы функция проверяет, не является ли пустым параметр-указатель; если да – выход из подпрограммы. Если он не является листом, осуществляются рекурсивные вызовы подпрограммы для каждого из его дочерних узлов; если параметр-указатель является листом, подпрограмма освобождает занятую им память и завершает свою работу.
2.1.4.4 Функция Find
· Функция предназначена для поиска элементов Q-дерева, расположенных в заданной области карты
· Параметры
- входной параметр указатель на узел дерева (тип PNode);
- параметр-константа границы этого узла (тип TRect);
- параметр-константа границы заданной области карты (тип TRect);
· Функция возвращает список (тип TList) элементов дерева, расположенных в заданной области
· Предусловия
Указатель на дерево не должен быть пустым
