Создание класса и разработка приложения «Бинарное дерево поиска»
В пояснительной записке разобраны основные понятия, связанные с бинарными деревьями. Также рассмотрены требования к интерфейсу пользователя. В разделах проектирования и реализации приведены структура и компоненты программных средств и результаты тестирования, а также диаграммы вариантов использования и иерархии классов. В ООП данные и подпрограммы непосредственно связаны, что позволяет… Читать ещё >
Создание класса и разработка приложения «Бинарное дерево поиска» (реферат, курсовая, диплом, контрольная)
Реферат Отчет содержит 30 листов, 21 рисунков, 2 приложения и 3 источника.
БИНАРНОЕ ДЕРЕВО ПОИСКА, ДИНАМИЧЕСКИЕ СТРУКТУРЫ ДАННЫХ, ОБЪЕКТНО-ОРИЕНТИРОВАННОЕ ПРОГРАММИРОВАНИЕ, C#
Предмет разработки — программа для работы с бинарным деревом поиска. Пользователь может добавлять, удалять, искать элементы.
Цель работы — создание класса и разработка приложения «Бинарное дерево поиска» .
Результат разработки — приложение Windows «Бинарное дерево поиска» .
- Введение
- 1. Создание класса и разработка приложения «Бинарное дерево поиска»
- 1.1Анализ предметной области
- 1.2Анализ требований
- 1.2.1 Требования к интерфейсу пользователя
- 1.2.2 Требования к структуре данных
- 1.2.3 Требования к программным средствам
- 1.3 Технология разработки
- 2. Проектирование
- 2.1 Проектирование интерфейса пользователя
- 2.2 Проектирование структуры данных
- 2.3 Структура программных средств
- 2.4 Пример блок-схемы
- 3. Реализация
- 3.1 Кодирование
- 3.2 Тестирование
- Заключение
- Список литературы
- Приложение
Объектом разработки в курсовой работе является структура данных — бинарное дерево поиска.
Целью работы является изучение данной структуры, а затем разработка приложения на языке программирования C# с её реализацией в виде класса.
В ходе курсовой работы был создан на языке C# среды Visual Studio 2010 класс, описывающий структуру бинарного дерева поиска и позволяющий выполнять с ним основные операции (например, добавления, удаления и поиска).
В пояснительной записке разобраны основные понятия, связанные с бинарными деревьями. Также рассмотрены требования к интерфейсу пользователя. В разделах проектирования и реализации приведены структура и компоненты программных средств и результаты тестирования, а также диаграммы вариантов использования и иерархии классов.
1. Создание класса и разработка приложения «Бинарное дерево поиска»
1.1 Анализ предметной области
Организация данных с помощью бинарных деревьев часто позволяет значительно сократить время поиска нужного элемента. Поиск элемента в линейных структурах данных обычно осуществляется путем последовательного перебора всех элементов, присутствующих в данной структуре. Поиск по дереву не требует перебора всех элементов, поэтому занимает значительно меньше времени. Максимальное число шагов при поиске по дереву равно высоте данного дерева, т. е. количеству уровней в иерархической структуре дерева.
Бинарное дерево — это упорядоченное дерево, каждая вершина которого имеет не более двух поддеревьев, причем для каждого узла выполняется правило: в левом поддереве содержатся только ключи, имеющие значения, меньшие, чем значение данного узла, а в правом поддереве содержатся только ключи, имеющие значения, большие, чем значение данного узла.
Узлы дерева, не имеющие потомков, называются листьями.
Схематичное изображение бинарного дерева представлено на рисунке 1:
Рисунок 1.
1.2 Анализ требований
1.2.1 Требования к интерфейсу пользователя
Все возможности, предоставляемые Пользователю при работе с приложением, основываются на основных операциях, осуществляемых над бинарными деревьями поиска:
2 создание дерева;
3 добавление нового узла в дерево;
4 поиск элемента в дереве;
5 удаление узла из дерева;
6 удаление дерева;
7 обход (просмотр) дерева.
1.2.2 Требования к структуре данных
Каждая вершина бинарного дерева имеет следующую структуру (рисунок 2) [1. стр. 63]:
PLP | INF | PRP | |
Рисунок 2 — Структура вершины бинарного дерева
· INF — значение элемента;
· PLPуказатель на левого потомка;
· PRP — указатель на правого потомка;
1.2.3 Требования к программным средствам
Основные функции, выполняемые разрабатываемые программными средствами приведены в диаграмме вариантов использования (рисунок 3).
Рисунок 3. Диаграмма вариантов использования.
1.3 Технология разработки
В курсовой работе используется технология объектно-ориентированного программирования C# среды Visual Studio 2010.
В ООП данные и подпрограммы непосредственно связаны, что позволяет разрабатывать программу постепенно (создавая модули и компоненты), поэтому такой подход способствует реализации приложения в короткие сроки и быстрому произведению их отладки.
Также стоит отметить, что данная технология не уменьшает размер кода и не упрощает его.
2. Проектирование
2.1 Проектирование интерфейса пользователя
На рисунке 4 изображен интерфейс программы.
Рисунок 4, 5. Визуальные компоненты интерфейса пользователя
бинарный дерево интерфейс программный
1. button_add_Click — Кнопка «Добавить элемент»
2. button_search_Click — Кнопка «найти элемент «
3. button_clear_Click — Кнопка «удалить элемент»
4. button1_Click — Кнопка «об авторе»
5. button_clear_history_Click — Кнопка «очистить историю»
6. button_clear_all_Click — Кнопка «удалить дерево»
7. textBoxVN_TextChanged — поле для просмотра «обход сверху вниз»
8. textBoxLP_TextChanged — поле для просмотра «обход слева направо»
9. textBoxNV_TextChanged — поле для просмотра «обход справа налево»
10. textBox_add_TextChanged — поле для ввода значения для добавления
11. textBox_search_TextChanged — поле для ввода значения для поиска
12. textBox_clear_TextChanged — поле для ввода значения для удаления
13. listBox1_SelectedIndexChanged — поле для вывода истории
14. — Форма «о проекте»
2.2 Проектирование структуры данных
Ниже приведена структура и описание разработанной структуры данных.
public class Tree
{
public string Z; // значение узла
public 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 — Иерархия классов
2.4 Пример блок-схемы
Блок-схема операции «Поиск элемента» приведена на рисунке 7.
Рисунок 7 — Блок-схема «Поиск элемента»
3. Реализация
3.1 Кодирование
Текст программы приведен в Приложении А
3.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 г.
2. http://ru.wikipedia.org/wiki/%D0%94%D0%B2%D0%BE%D0%B8%D1%87%D0%BD%D0%BE%D0%B5_%D0%B4%D0%B5%D1%80%D0%B5%D0%B2%D0%BE_%D0%BF%D0%BE%D0%B8%D1%81%D0%BA%D0%B0#.D0.A3.D0.B4.D0.B0.D0.BB.D0.B5.D0.BD.D0.B8.D0.B5_.D1.83.D0.B7.D0.BB.D0.B0_.28REMOVE.29
3. http://rflinux.blogspot.ru/2011/10/blog-post.html
Приложение А
Исходный код программы
using System;
using System.Collections.Generic;
using System. ComponentModel;
using System. Data;
using System. Drawing;
using System. Linq;
using System. Text;
using System.Windows.Forms;
namespace Tree
{
public partial class FormTree: Form
{
Tree t = new Tree ();
public FormTree ()
{
InitializeComponent ();
}
#region button
// Обработка кнопки «Добавить элемент»
private void button_add_Click (object sender, EventArgs e)
{
if (textBox_add.Text ≠ «»)
{
if (t.Insert (textBox_add.Text))
{
listBox1.Items.Add («Элемент «+ textBox_add.Text + «добавлен»);
Display ();
}
else
listBox1.Items.Add («Элемент «+ textBox_add.Text + «уже существует»);
textBox_add.Text = «» ;
}
else MessageBox. Show («Введите элемент»);
}
// Обработка кнопки «Удалить элемент»
private void button_clear_Click (object sender, EventArgs e)
{
if (textBox_clear.Text ≠ «»)
{
if (t.Delete (textBox_clear.Text))
{
listBox1.Items.Add («Элемент «+ textBox_clear.Text + «удален»);
Display ();
}
else
listBox1.Items.Add («Элемента «+ textBox_clear.Text + «нет в дереве»);
textBox_clear.Text = «» ;
}
else MessageBox. Show («Введите элемент»);
}
// Обработка кнопки «Найти элемент»
private void button_search_Click (object sender, EventArgs e)
{
if (textBox_search.Text ≠ «»)
{
if (t.Search (textBox_search.Text) ≠ null)
listBox1.Items.Add («Элемент «+ t. Search (textBox_search.Text).Z + «найден»);
else
listBox1.Items.Add («Элемент «+ textBox_search.Text + «не найден»);
textBox_clear.Text = «» ;
textBox_search.Text = «» ;
}
else MessageBox. Show («Введите элемент»);
}
// Обработка кнопки «Очистить историю»
private void button_clear_history_Click (object sender, EventArgs e)
{
listBox1.Items.Clear (); // очищаем значения в текстовом поле
MessageBox.Show («История очищена»);
}
// Функция, отвечающая за вывод в строку разных
// дерева при различных обходах
public void Display ()
{
textBoxVN.Text = t. DisplayVN (t);
textBoxLP.Text = t. DisplayLP (t);
textBoxNV.Text = t. DisplayNV (t);
}
// Очистка дерева
private void button_clear_all_Click (object sender, EventArgs e)
{
if (!t.IsEmpty ()) // если дерево пустое, не выполнять действий
{
t.Dispose ();
listBox1.Items.Add («Дерево очищено»);
Display ();
}
else
listBox1.Items.Add («Дерево пустое, очистка не нужна»);
}
#endregion button
#region KeyPress
private void textBoxVN_KeyPress (object sender, KeyPressEventArgs e)
{
e.Handled = true;
}
private void textBoxLP_KeyPress (object sender, KeyPressEventArgs e)
{
e.Handled = true;
}
private void textBoxNV_KeyPress (object sender, KeyPressEventArgs e)
{
e.Handled = true;
}
private void textBox_add_KeyPress (object sender, KeyPressEventArgs e)
{
// Разрешаю ввод десятичных цифр:
if (char.IsDigit (e.KeyChar) == true) return;
// Разрешаю ввод :
if (e.KeyChar == (char)Keys.Back) return;
e.Handled = true;
}
private void textBox_clear_KeyPress (object sender, KeyPressEventArgs e)
{
// Разрешаю ввод десятичных цифр:
if (char.IsDigit (e.KeyChar) == true) return;
// Разрешаю ввод :
if (e.KeyChar == (char)Keys.Back) return;
e.Handled = true;
}
private void textBox_search_KeyPress (object sender, KeyPressEventArgs e)
{
// Разрешаю ввод десятичных цифр:
if (char.IsDigit (e.KeyChar) == true) return;
// Разрешаю ввод :
if (e.KeyChar == (char)Keys.Back) return;
e.Handled = true;
}
#endregion KeyPress
private void textBox_search_TextChanged (object sender, EventArgs e)
{
}
private void button1_Click (object sender, EventArgs e)
{
MessageBox.Show («Курсовой проект: БИНАРНОЕ ДЕРЕВО ПОИСКАnВыполнил студент группы 10ВП2nОсипов Владимир»);
}
private void textBoxVN_TextChanged (object sender, EventArgs e)
{
}
private void textBoxLP_TextChanged (object sender, EventArgs e)
{
}
private void textBoxNV_TextChanged (object sender, EventArgs e)
{
}
private void textBox_add_TextChanged (object sender, EventArgs e)
{
}
private void textBox_clear_TextChanged (object sender, EventArgs e)
{
}
private void listBox1_SelectedIndexChanged (object sender, EventArgs e)
{
}
}
#region Tree
public class Tree
{
public string Z; // значение узла
public Tree left, right; // указатели на потомков
// добавление строки
public bool Insert (string value)
{
if (this.Z == null)
{
this.Z = value;
return true;
}
else
if (int.Parse (this.Z).CompareTo (int.Parse (value)) == 1)
{
if (left == null)
this.left = new Tree ();
return left. Insert (value);
}
else
if (int.Parse (this.Z).CompareTo (int.Parse (value)) == -1)
{
if (right == null)
this.right = new Tree ();
return right. Insert (value);
}
else
return false;
}
// поиск
public Tree Search (string value)
{
if (!IsEmpty ())
if (int.Parse (this.Z).CompareTo (int.Parse (value)) == 1)
if (left ≠ null)
return this.left.Search (value);
else
return (null);
else
if (int.Parse (this.Z).CompareTo (int.Parse (value)) == -1)
if (right ≠ null)
return this.right.Search (value);
else
return (null);
else return this;
else
return (null);
}
#region Отображение в строку
public string DisplayVN (Tree t) // Сверху вниз
{
string result = «» ;
result += t. Z + ««;
if (t.left ≠ null)
result += DisplayVN (t.left);
if (t.right ≠ null)
result += DisplayVN (t.right);
return result;
}
public string DisplayLP (Tree t) // Слева направо
{
string result = «» ;
if (t.left ≠ null)
result += DisplayLP (t.left);
result += t. Z + ««;
if (t.right ≠ null)
result += DisplayLP (t.right);
return result;
}
public string DisplayNV (Tree t) // Справа налево
{
string result = «» ;
if (t.right ≠ null)
result += DisplayNV (t.right);
result += t. Z + ««;
if (t.left ≠ null)
result += DisplayNV (t.left);
return result;
}
#endregion Отображение в строку
// проверка пустоты
public bool IsEmpty ()
{
if (this.Z == null)
return true;
else
return false;
}
// удаление элемента
public bool Delete (string value)
{
Tree q = new Tree ();
if (Search (value) ≠ null)
if (this.Z ≠ null)
if (int.Parse (this.Z).CompareTo (int.Parse (value)) == 1 && left ≠ null) // <
return left. Delete (value);
else
if (int.Parse (this.Z).CompareTo (int.Parse (value)) == -1 && right ≠ null) // >
return right. Delete (value);
else // =
{
if (left == null && right == null)
this.Z = null;
else
if (left ≠ null)
if (right == null)
{
q = this. left;
this.Z = q. Z;
left = q. left;
right = q. right;
}
else
{
q = right;
if (q.left ≠ null)
{
while (q.left.left ≠ null)
q = q. left;
this.Z = q.left.Z;
if (q.left.right == null)
q.left = null;
else
q.left = q.left.right;
}
else
{
this.Z = q. Z;
this.right = q. right;
}
}
else
{
q = right;
this.Z = q. Z;
left = q. left;
right = q. right;
}
return true;
}
else return false;
else return false;
}
// Очистка памяти, занимаемой деревом
public void Dispose ()
{
if (this.Z ≠ null)
{
if (left ≠ null)
left.Dispose ();
if (right ≠ null)
right.Dispose ();
this.left = null;
this.right = null;
this.Z = null;
}
}
}
#endregion Tree
}
Приложение Б
Результаты тестирования
Рисунок 1
Рисунок 2
Рисунок 3
Рисунок 4
Рисунок 5
Рисунок 6
Рисунок 7
Рисунок 8
Рисунок 9
Рисунок 10
Рисунок 11
Рисунок 12
Рисунок 13
Рисунок 14
Рисунок 15