Размещено на http://www.allbest.ru/

Реферат

Отчет содержит 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;

// Разрешаю ввод <BackSpace>:

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;

// Разрешаю ввод <BackSpace>:

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;

// Разрешаю ввод <BackSpace>:

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ВП2\nОсипов Владимир");

}

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Размещено на Allbest.ru