Создание класса и разработка приложения 'Бинарное дерево поиска'
Реферат
Отчет содержит 30 листов, 21 рисунков, 2 приложения и 3 источника.
БИНАРНОЕ ДЕРЕВО ПОИСКА, ДИНАМИЧЕСКИЕ СТРУКТУРЫ ДАННЫХ,
ОБЪЕКТНО-ОРИЕНТИРОВАННОЕ ПРОГРАММИРОВАНИЕ, C#
Предмет разработки - программа для работы с бинарным деревом поиска.
Пользователь может добавлять, удалять, искать элементы.
Цель работы - создание класса и разработка приложения "Бинарное
дерево поиска".
Результат разработки - приложение Windows "Бинарное дерево поиска".
Содержание
Введение
. Создание класса и разработка приложения "Бинарное
дерево поиска"
1.1Анализ предметной области
.2Анализ требований
1.2.1 Требования к интерфейсу пользователя
.2.2 Требования к структуре данных
.2.3 Требования к программным средствам
1.3 Технология разработки
2. Проектирование
2.1 Проектирование интерфейса пользователя
.2 Проектирование структуры данных
.3 Структура программных средств
.4 Пример блок-схемы
3. Реализация
3.1 Кодирование
3.2 Тестирование
Заключение
Список литературы
Приложение
Введение
Объектом разработки в курсовой работе является структура данных -
бинарное дерево поиска.
Целью работы является изучение данной структуры, а затем разработка
приложения на языке программирования C# с её реализацией в виде класса.
В ходе курсовой работы был создан на языке C# среды Visual Studio 2010 класс, описывающий структуру
бинарного дерева поиска и позволяющий выполнять с ним основные операции
(например, добавления, удаления и поиска).
В пояснительной записке разобраны основные понятия, связанные с бинарными
деревьями. Также рассмотрены требования к интерфейсу пользователя. В разделах
проектирования и реализации приведены структура и компоненты программных
средств и результаты тестирования, а также диаграммы вариантов использования и
иерархии классов.
1. Создание
класса и разработка приложения "Бинарное дерево поиска"
1.1 Анализ
предметной области
Организация данных с помощью бинарных деревьев часто позволяет
значительно сократить время поиска нужного элемента. Поиск элемента в линейных
структурах данных обычно осуществляется путем последовательного перебора всех
элементов, присутствующих в данной структуре. Поиск по дереву не требует
перебора всех элементов, поэтому занимает значительно меньше времени.
Максимальное число шагов при поиске по дереву равно высоте данного дерева, т.е.
количеству уровней в иерархической структуре дерева.
Бинарное дерево - это упорядоченное дерево, каждая вершина которого имеет
не более двух поддеревьев, причем для каждого узла выполняется правило: в левом
поддереве содержатся только ключи, имеющие значения, меньшие, чем значение
данного узла, а в правом поддереве содержатся только ключи, имеющие значения,
большие, чем значение данного узла.
Узлы дерева, не имеющие потомков, называются листьями.
Схематичное изображение бинарного дерева представлено на рисунке 1:
Рисунок 1.
1.2 Анализ
требований
1.2.1 Требования
к интерфейсу пользователя
Все возможности, предоставляемые Пользователю при работе с приложением,
основываются на основных операциях, осуществляемых над бинарными деревьями
поиска:
2 создание дерева;
3 добавление нового узла в дерево;
4 поиск элемента в дереве;
удаление узла из дерева;
удаление дерева;
обход (просмотр) дерева.
.2.2
Требования к структуре
данных
Каждая вершина бинарного дерева имеет следующую структуру (рисунок 2) [1.
стр. 63]:
Рисунок 2 - Структура вершины бинарного дерева
· INF - значение элемента;
· PLP- указатель на левого потомка;
· PRP - указатель на правого потомка;
.2.3
Требования к программным средствам
Основные функции, выполняемые разрабатываемые программными средствами
приведены в диаграмме вариантов использования (рисунок 3).
Рисунок 3. Диаграмма вариантов использования.
.3 Технология
разработки
В курсовой работе используется технология объектно-ориентированного
программирования C# среды Visual Studio 2010.
В ООП данные и подпрограммы непосредственно связаны, что позволяет
разрабатывать программу постепенно (создавая модули и компоненты), поэтому
такой подход способствует реализации приложения в короткие сроки и быстрому
произведению их отладки.
Также стоит отметить, что данная технология не уменьшает размер кода и не
упрощает его.
2.
Проектирование
.1
Проектирование интерфейса пользователя
На рисунке 4 изображен интерфейс программы.
Рисунок 4, 5. Визуальные компоненты интерфейса пользователя
бинарный дерево интерфейс программный
1. button_add_Click - Кнопка "Добавить элемент"
2. button_search_Click - Кнопка "найти элемент "
3. button_clear_Click - Кнопка "удалить элемент"
. button1_Click - Кнопка "об авторе"
5. button_clear_history_Click - Кнопка "очистить историю"
. button_clear_all_Click - Кнопка "удалить дерево"
. textBoxVN_TextChanged - поле
для просмотра "обход сверху вниз"
. textBoxLP_TextChanged - поле для просмотра "обход слева
направо"
. textBoxNV_TextChanged - поле для просмотра "обход справа
налево"
11. textBox_search_TextChanged - поле для ввода значения для поиска
12. textBox_clear_TextChanged - поле для ввода значения для
удаления
13. listBox1_SelectedIndexChanged - поле для вывода истории
14. - Форма "о проекте"
2.2
Проектирование структуры
данных
Ниже приведена структура и описание разработанной структуры данных.
public class Tree
{string Z; // значение узла Tree left, right;
// указатели на потомков
2.3 Структура
программных средств
Для проектирования данного приложения была разработана структура
собственных классов: Tree
(таблица 1), FormTree (таблица 2).
|
Член класса
|
Описание
|
|
public string Z
|
Значение узла
|
|
public Tree left
|
Указатель на левого потомка
|
|
public Tree right
|
Указатель на правого потомка
|
|
public bool Insert(string value)
|
Функция добавления элемента
|
|
public Tree Search(string value)
|
Функция поиска элемента
|
|
public string DisplayVN(Tree t)
|
Функция обхода дерева сверху вниз
|
|
public string DisplayLP(Tree t)
|
Функция обхода дерева слева направо
|
|
public string DisplayNV(Tree t)
|
Функция обхода дерева справа налево
|
|
public bool IsEmpty()
|
Функция проверки на пустоту
|
|
public bool Delete(string value)
|
Функция удаления элемента
|
|
public void Dispose()
|
Функция удаления дерева
|
|
Член класса
|
Описание
|
|
Tree t
|
Элемент, предназначенный для работы с деревом
|
|
public FormTree()
|
Конструктор
|
|
private void
button_add_Click(object sender, EventArgs e)
|
Обработчик нажатия на кнопку button_add
|
|
private void
button_clear_Click(object sender, EventArgs e)
|
Обработчик нажатия на кнопку button_clear
|
|
private void
button_search_Click(object sender, EventArgs e)
|
Обработчик нажатия на кнопку button_search
|
|
private void
button_clear_history_Click(object sender, EventArgs e)
|
Обработчик нажатия на кнопку button_clear_history
|
|
public void Display()
|
Функция обработки дерева
|
|
private void
button_clear_all_Click(object sender, EventArgs e)
|
Обработчик нажатия на кнопку
button_clear_all_Click
|
|
private void
button_info_Click(object sender, EventArgs e)
|
Обработчик нажатия на кнопку button_info_Click
|
|
private void
textBoxVN_KeyPress(object sender, KeyPressEventArgs e)
|
Обработчик события KeyPress текстового поля textBoxVN
|
|
private void
textBoxLP_KeyPress(object sender, KeyPressEventArgs e)
|
Обработчик события KeyPress текстового поля textBoxLP
|
|
private void
textBoxNV_KeyPress(object sender, KeyPressEventArgs e)
|
Обработчик события KeyPress текстового поля textBoxNV
|
|
private void
textBox_add_KeyPress(object sender, KeyPressEventArgs e)
|
Обработчик события KeyPress текстового поля textBox_add
|
|
private void textBox_clear_KeyPress(object
sender, KeyPressEventArgs e)
|
Обработчик события KeyPress текстового поля textBox_clear
|
|
private void
textBox_search_KeyPress(object sender, KeyPressEventArgs e)
|
Обработчик события KeyPress текстового поля textBox_search
|
|
private void button1_Click(object
sender, EventArgs e)
|
Обработчик события KeyPress MessageBox
|
Иерархия классов приведена на рисунке 6
Рисунок 6 - Иерархия классов
.4 Пример
блок-схемы
Блок-схема операции "Поиск элемента" приведена на рисунке 7.
Рисунок 7 - Блок-схема "Поиск элемента"
3. Реализация
.1
Кодирование
Текст программы приведен в Приложении А
.2
Тестирование
План функционального тестирования приведен в таблице 3.
|
Варианты использования
|
Тесты
|
Результат
|
|
Запуск программы
|
Открываем приложение Tree.exe
|
Приложение открылось, все текстовые поля пусты.
|
|
Добавление элемента
|
Добавляем элемент в пустое дерево.
|
Элемент добавился в корень дерева, в текстовом поле истории
появилось сообщение об этом, обновились поля с выводом дерева (Приложение Б,
рис.1).
|
|
Добавляем элемент, несуществующий в дереве.
|
Элемент встал на свое место в дереве, в текстовом поле
истории появилось сообщение об этом, обновились поля с выводом дерева
(Приложение Б, рис.2).
|
|
Добавляем элемент, уже существующий в дереве
|
Элемент не добавляется в дерево, в текстовом поле истории
появляется сообщение о недопустимости добавления, поля с выводом дерева не
изменяются (Приложение Б, рис.3).
|
|
Удаление элемента
|
Удаляем элемент, существующий в дереве, у которого нет
потомков.
|
Элемент удалился, в текстовом поле истории появилось
сообщение о выполненной операции, поля с выводом дерева обновились
(Приложение Б, рис.4).
|
|
Удаляем элемент, существующий в дереве, у которого есть
один левый потомок.
|
Элемент удалился, на его место встал левый потомок, в
текстовом поле истории появилось сообщение о выполненной операции, поля с
выводом дерева обновились (Приложение Б, рис.5).
|
|
Удаляем элемент, существующий в дереве, у которого есть
один правый потомок.
|
Элемент удалился, на его место встал правый потомок, в
текстовом поле истории появилось сообщение о выполненной операции, поля с
выводом дерева обновились (Приложение Б, рис.6).
|
|
Удаляем элемент, существующий в дереве, у которого есть два
потомка.
|
Элемент удалился, на его место встал либо правый потомок
(если у правого потомка не было левого узла), либо самый левый узел правого
потомка (если он существовал). В текстовом поле истории появилось сообщение о
выполненной операции, поля с выводом дерева обновились (Приложение Б, рис.7 -
до выполнения операции, Приложение Б, рис.8 - после выполнения операции).
|
|
Удаляем элемент, несуществующий в дереве
|
Элемент не удаляется, в текстовом поле истории появляется
сообщение об ошибке, поля с выводом дерева не обновляются (Приложение Б,
рис.9).
|
|
Удаление дерева
|
Нажимаем на кнопку "Удалить дерево", если дерево
не пустое.
|
Дерево удалено, в текстовом поле истории появляется
сообщение о выполненной операции, поля с выводом дерева становятся пустыми
(Приложение Б, рис.10).
|
|
Нажимаем на кнопку "Удалить дерево", если дерево
пустое.
|
Дерево не удаляется, в текстовом поле истории появляется
сообщение о невыполненной операции (Приложение Б, рис.11).
|
|
Поиск элемента
|
Поиск элемента при условии, что элемент существует в дереве
|
Элемент находится, в текстовом поле истории появляется
сообщение, что элемент найден (Приложение Б, рис.12).
|
|
Поиск элемента при условии, что элемент не существует в
дереве
|
Элемент не находится, в текстовом поле истории появляется
сообщение, что элемент не существует в дереве (Приложение Б, рис.13).
|
|
Очистка поля с историей
|
Нажимаем на кнопку "Очистить историю"
|
Поле истории становится пустым, появляется сообщение, что
история очищена (Приложение Б, рис.14).
|
|
Просмотр информации о программе
|
Нажатие на кнопку "?"
|
Появляется новая форма с информацией о программе
(Приложение Б, рис.15).
|
|
Закрытие программы
|
Нажатие на кнопку 
|
Закрытие программы происходит без ошибок.
|
Все рисунки, сделанные при тестировании, находятся в Приложение Б.
Заключение
В данном отчете выполнены анализ требований, проектирование и реализация
программных средств, которые являются необходимыми этапами разработки
программного обеспечения.
Для реализации бинарного дерева поиска были созданы собственные классы Tree, FormTree. В итоге разработано приложение Tree.exe, предназначенное для работы с бинарным деревом
поиска.
Результаты тестирования показали, что приложение работает корректно,
соблюдены все правила работы с бинарным деревом поиска.
Список
литературы
1. И.А. Казакова, С.В. Самуйлов "Структуры
данных" Учебное пособие. Пенза 2011г.
. #"601496.files/image007.gif">
Рисунок 1
Рисунок 2
Рисунок 3
Рисунок 4
Рисунок 5
Рисунок 6
Рисунок 7
Рисунок 8
Рисунок 9
Рисунок 11
Рисунок 12
Рисунок 13
Рисунок 14
Рисунок 15