Программная реализация B+-дерева

Министерство  образования и науки РФ

Государственное образовательное  учреждение высшего профессионального  образования

«Юго-западный государственный  университет»

 

Кафедра ПО ВТ

 

 

 

КУРСОВАЯ  РАБОТА

 

по дисциплине «Структуры и алгоритмы обработки данных»

 

на тему «Программная реализация B+-дерева»

 

Специальность (направление  подготовки)  ПО ВТ                                   

_______________________________________________________________________

Автор работы (проекта)                     Клыков А.В.   ___________________

 

Группа  ПО-92

Руководитель работы (проекта)                Белова Т.М.    __________________

 

Работа (проект) защищена     ____________________

 

Оценка  ____________________

 

 

Председатель  комиссии      ____________________        ___________________

 

Члены комиссии:                 ____________________        ___________________

 

     ____________________         ___________________

 

 

 

 

 

 

 

 

 

 

 

Курск, 2011 г.

 

 

Министерство  образования и науки РФ

Государственное образовательное учреждение высшего профессионального образования

«Юго-западный государственный университет»

 

Кафедра ПО ВТ

 

 

 

ЗАДАНИЕ НА КУРСОВУЮ РАБОТУ

 

Студент     Клыков А.В.     шифр 349014 группа    ПО-92

 

1.Тема Программная реализация B+-дерева

 

2. Срок предоставления  работы (проекта) к защите  «    »               2011 г.

 

3. Исходные данные (для  проектирования, для научного исследования):

Данные, введенные пользователем; файл данных.

 

4. Содержание пояснительной  записки курсовой работы (проекта):

4.1. Содержание

4.3. Техническое задание

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

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

4.6. Список использованных источников

4.7. Приложение

 

5. Перечень графического  материала: 

_____________________________________________________________

_____________________________________________________________

 

Руководитель  работы (проекта)                                                 Белова Т.М.  

 

Задание принял к исполнению                                                                 Клыков А.В.  

 

Содержание

1. ТЕХНИЧЕСКОЕ ЗАДАНИЕ

1. Введение

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

Для программного продукта данной курсовой работы операционной средой является система Microsoft Windows XP. Для создания использовалась среда программирования Microsoft Visual Studio 9 и язык программирования C++.

Язык  C++ является одним из наиболее мощных современных языков программирования. Он поддерживает большинство перспективных технологий разработки программ, включая структурное программирование, модульное построение программ, объектную декомпозицию. С его использованием разработаны такие программные комплексы, как, например, операционные системы семейства Windows.

Целью создания программного продукта данной курсовой работы является изучение структуры данных B+ - дерево.

В данной курсовой работе реализуется  программный комплекс "Информационно-поисковая система банка на основе B+-дерева".

2. Основания для разработки

Данный программный продукт  разрабатывается как задание  на курсовую работу по дисциплине "Структуры и алгоритмы обработки данных".

3. Назначение разработки

1. Функциональное и эксплуатационное назначение изделия

В соответствии с заданием данное программное изделие должно представлять собой приложение, позволяющее просматривать, искать, удалять и добавлять информацию о банковских клиентах и их вкладах, использующее структуру данных «B+ - дерево».

2. Перечень требований пользователя к программному продукту

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

3. Рассмотренные альтернативы

При постановке задачи на разработку данного программного изделия в  качестве альтернативы рассматривались структуры данных «B – дерево» и «B* - дерево». Была выбрана структура «B+ - дерево» как наиболее экономичная по времени исполнения.

4. Требования к программе или программному изделию

1. Стандарты

Разработка программной документации и программного изделия должна производиться  согласно ГОСТ 19.701-90, ГОСТ 2.304-88. Единая система программной документации.

2. Требования к составу и параметрам технических средств

Программное изделие должно работать на компьютере под управлением операционной системы Windows XP с частотой процессора не ниже 2 ГГц, ОЗУ не менее 1024Мбайт. Для переноса программы не должны требоваться специальные программные и аппаратные средства.

3. Требования к информационной и программной совместимости

Программное изделие должно быть написано на языке C++ и работать под управлением операционной системы Windows XP.

4. Требования к функциональным характеристикам

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

5. Результирующие компоненты изделия

В комплект поставки программного изделия  входит исполняемый файл «B+ Tree.exe», а также файл данных «schedule.txt», содержащий информацию о клиентах банка.

6. Носители информации

Программное изделие будет размещено в виде файлов на компакт-диске.

7. Безопасность и секретность

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

8. Удобства эксплуатации

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

9. Мобильность

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

5. Требования к программной документации

Программная документация должна включать следующие документы:

1. техническое задание;
2. технический проект;
3. рабочий проект,
4. тесты.

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

6. Стадии и этапы разработки

Выполнение разработки должно включать три стадии:

1. техническое задание;
2. технический проект;
3. рабочий проект.

На стадии "Техническое задание" проводится постановка задачи, разработка требований к программному изделию, изучение литературы по задаче и оформление документа "Техническое задание".

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

На стадии "Рабочий проект" проводится разработка схем алгоритмов для каждого из функциональных модулей, физическое проектирование программного изделия, разработка тестов, тестирование и отладка программных модулей. В заключение данного этапа оформляется документ "Рабочий проект".

7. Порядок контроля и приемки

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

 

2. ТЕХНИЧЕСКИЙ ПРОЕКТ

1. Анализ области

Стандартное использование программного продукта состоит в следующей  последовательности действий пользователя:

1. запуск файла «B+ Tree.exe»
2. добавление данных к существующему дереву, удаление и поиск посредством использования соответствующих компонент в окне;
3. закрытие окна программы;

2. Структура программы

Программа состоит из двух модулей: файлы Form.cpp + Form.h, в которых описан класс TFormMain и BTree.h, где содержатся методы, описывающие алгоритмы работы с B+-деревом, а также методы для внешнего взаимодействия с этой структурой данных.

1. Класс TFormMain

В этом классе описаны следующие  функции:

1. Отрисовка дерева;
2. Чтение данных из файла;
3. Поиск узла дерева, на который нажал пользователь;
4. Обработка вводимых пользователем данных для поиска/удаления/добавления записи в дерево.

1. Входные данные

При нажатии одной из трех кнопок («добавить», «удалить» или «найти») входными данными являются значения четырех полей: «Номер счета», «ФИО», «Сумма вклада», «Длительность (мес - %) ». При нажатии левой кнопки мыши на области вывода дерева в графическом представлении входными данными являются координаты курсора мыши.

2. Выходные данные

При нажатии кнопки «найти» или  щелчке мыши на области вывода дерева выходными данными могут являться строки «Номер счета», «ФИО», «Сумма вклада», «Длительность (мес - %) », а также сообщение об ошибке ввода или поиска. При нажатии на другие кнопки происходит перерисовка дерева или вывод сообщения об ошибке в случае неудачи при выполнении операции.

3. Процессы обработки модуля

1. создание графического интерфейса, запуск приложения;
2. отрисовка окна приложения;
3. обработка действий пользователя.

2. Класс CB_PLUS_Tree

В этом классе описаны следующие  функции:

1. добавление записи в дерево;
2. поиск записи в дереве по первичному ключу;
3. удаление записи по первичному ключу.

1. Входные данные

Запись, включающая в себя номер  счета (первичный ключ), ФИО, сумма вклада и длительность (мес - %).

2. Выходные данные

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

3. Методические ограничения

В модулях не используется методологически  сложных операций

4. Аппаратные ограничения

Для корректной работы программ необходимо дисковое пространство в размере не менее 1 КБ, свободная оперативная память в размере не менее 15МБ.

 

3. РАБОЧИЙ ПРОЕКТ

1. Введение

В данном программном изделии используются алгоритмы обработки структуры данных «B+-дерево».

2. Назначение разработки

Данный программный продукт наглядно демонстрирует структуру B+ - дерева.

3. Требования к программе или программному изделию