Курсовая работа (т): Реализация инструментария по работе с бинарными деревьями

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

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

Финальным этапом стало тестирование программного продукта на наличие ошибок и их отладка.

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

СПИСОК ИСПОЛЬЗОВАННЫХ ИСТОЧНИКОВ

1.   ГОСТ 2.105-95. ЕСКД. Общие требования к текстовым документам. - М.: Изд-во стандартов, 2007. - 31 с.

2.      Павловская Т. А. C#. Программирование на языке высокого уровня. - Изд.: Питер, 2009. - 432 с.

.        Пайлон Д., Питмен Н. UML 2 для программистов. - Изд.: Питер, 2012. - 240 с.

.        Троелсен Э. Язык программирования C# 2010 и платформа .NET 4. - Изд.: Вильямс, 2011. - 1392 с.

.        Буч Г., Рамбо Д., Якобсон И. Введение в UML от создателей языка. - Изд.: ДМК Пресс, 2011. - 496 с

ПРИЛОЖЕНИЯ

Приложение 1

Листинг программы

System;System.Collections.Generic;System.ComponentModel;System.Data;System.Drawing;System.Linq;System.Text;System.Windows.Forms;System.IO;

BinTree

{partial class Form1 : Form

{

BinaryTree<int> Derevo = new BinaryTree<int>();

pictGraphics; // для доступа к поверхности pictureBox

// шрифт для показа содержимого узловNodesFont = new Font(FontFamily.GenericMonospace, (float)12.0, FontStyle.Bold);

NodesColor = Color.FromArgb(255, 255, 0); // цвет внутренных узловLeavesColor = Color.FromArgb(255, 127, 0); // цвет листьев

Form1()

{();

}

// при загрузке формыvoid Form1_Load(object sender, EventArgs e)

{

// кнопки "развернуть" и "свернуть" будут недоступны

this.MinimizeBox = false;.MaximizeBox = false;

pw = pictDerevo.Width, ph = pictDerevo.Height; // размеры pictureBox

// следующий код даёт доступ к рисованию на картинке

pictDerevo.Image = (Image)new Bitmap(pw, ph);= Graphics.FromImage(pictDerevo.Image);

RefreshTree(); // обновляем картинку

}

// содержится ли элемент item среди первых n элементов массива A?

bool ContainsInArray(int[] A, int n, int item)

{(int i = 0; i < n; i++)(A[i] == item) return true;

return false;

}

// получение случайных чисел в диапазоне [xmin; xmax]

// размер массива случайный от nmin до nmax

int[] GetRandItems(int nmin, int nmax, int xmin, int xmax)

{

// DateTime.Now.Millisecond - для инициализации случайного датчика

Random R = new Random(DateTime.Now.Millisecond);

int n = R.Next(nmin, nmax + 1); // получаем случайный размер

int[] A = new int[n];

(int i = 0; i < n; i++)

{cur = R.Next(xmin, xmax + 1); // генерируем новое случайное число

// если оно уже есть среди ранее сгенерированных случайных чисел

if (ContainsInArray(A, i, cur) == true) i--;A[i] = cur; // если оно НОВОЕ

}

A;

}

CopyRight() // рисование копирайта

{s = "Автор Бартенева Н.И.";B = new SolidBrush(Color.Red); // цвет надписи копирайта

// центр круга, по которому выведем буквы

double xc = pictDerevo.Width - 80;yc = 80;

// h_fi - шаг угла, cur_fi - текущий уголh_fi = 2.0 * Math.PI / s.Length, cur_fi = Math.PI / 2.0;

(int i = 0; i < s.Length; i++, cur_fi += h_fi)

{

// позиция для вывода i-ой буквы

double x = xc - 60 * Math.Cos(cur_fi);y = yc - 60 * Math.Sin(cur_fi);

// вывод i-ой буквы.DrawString(s.Substring(i, 1), NodesFont, B, (float)x, (float)y);

}

}

RefreshTree() // обновление картинки

{.Clear(pictDerevo.BackColor); // очищаем картинку.VisualiseTree(pictGraphics, 14, pictDerevo.Width, pictDerevo.Height,, LeavesColor, NodesFont); // показываем дерево(); // рисуем копирайт

pictDerevo.Invalidate(); // инициируем отрисовку на картинке

}

void построитьПоСлучайнойКоллекцииToolStripMenuItem_Click(object sender, EventArgs e)

{

// получаем случайные числа (в данном случае от 1 до 99)

int[] A = GetRandItems(3, 15, 1, 99);= new BinaryTree<int>(A, A.Length); // строим дерево

();

}

void добавитьЭлементToolStripMenuItem_Click(object sender, EventArgs e)

{.SelectedNum = 0; // останется нулём, если пользователь закроет диалогMyDlgWindow("Добавление элемента").ShowDialog();

(MyDlgWindow.SelectedNum == 0) return; // если пользователь закрыл диалог

// если пользователь нажал на ОК в открывшемся диалоге

// Insert возвращает false, если была попытка вставки существующего элемента

if (Derevo.Insert(MyDlgWindow.SelectedNum) == false)

{.Show("Элемент " + MyDlgWindow.SelectedNum.ToString() + " уже имеется");;

}

();

}void удалитьЭлементToolStripMenuItem_Click(object sender, EventArgs e)

{.SelectedNum = 0;MyDlgWindow("Удаление элемента").ShowDialog();

if (MyDlgWindow.SelectedNum == 0) return;

// Remove возвращает false, если была попытка удаления отсутствующего элемента

if (Derevo.Remove(MyDlgWindow.SelectedNum) == false)

{.Show("Элемент " + MyDlgWindow.SelectedNum.ToString() + " отсутствует");

return;

}

();

}

// выбор файла с помощью стандартного диалога

string GetFName()

{dlg = new OpenFileDialog();.Filter = "Special Tree Files (*.derevo)|*.derevo";.Multiselect = false;.InitialDirectory = Path.GetDirectoryName(Application.ExecutablePath);(dlg.ShowDialog() == DialogResult.OK)dlg.FileName;null;

}void загрузитьКоллекциюИзФайлаToolStripMenuItem_Click(object sender, EventArgs e)

{FileName = GetFName(); // пользователь выбирает файл в стандартном диалоге(FileName == null) return; // если пользователь ничего не выбрал

// грузим элементы из файла в список (не в массив, т.к. число элементов

// неясно до полного просмотра файла)

List<int> Items = new List<int>();sr = new StreamReader(FileName, Encoding.GetEncoding(1251));buffer;((buffer = sr.ReadLine()) != null)

{.Add(Convert.ToInt32(buffer));

}.Close();

[] A = Items.ToArray(); // получаем массив по списку элементов

Derevo = new BinaryTree<int>(A, A.Length); // строим дерево

RefreshTree();

}

}

Приложение 2

Листинг классов BinaryTree и BinaryTreeNode

System;System.Collections.Generic;System.Linq;System.Text;System.Drawing;

BinTree

{BinaryTreeNode<Data> // шаблон класса УЗЕЛ ДЕРЕВА

{Data Item; // полезные данныеBinaryTreeNode<Data> Left, Right; // ссылки на дочерние узлыBinaryTreeNode(Data Item) // конструктор

{.Item = Item;.Left = null;

this.Right = null;

}

// является ли узел листовым?

public bool IsLeaf() { return (Left == null && Right == null) ? true : false; }

}

BinaryTree<Data> where Data:IComparable<Data> // класс БИНАРНОЕ ДЕРЕВО ПОИСКА

{BinaryTreeNode<Data> root; // ссылка на корень

public BinaryTree() // конструктор пустого дерева

{

this.root = null;

}

void QuickSort(Data[] A, int low, int high) // "быстрая сортировка"

{i = low, j = high;x = A[(low + high) / 2];

{(A[i].CompareTo(x) < 0) i++;(A[j].CompareTo(x) > 0) j--;(i <= j)

{temp = A[i];[i] = A[j];[j] = temp;++;-;

}

}(i < j);

(low < j) QuickSort(A, low, j);(i < high) QuickSort(A, i, high);

}

// следующая функция вставки формирует идеально сбалансированное дерево

void IBTInsert(Data[] A, int low, int high)

{(low > high) return; // граничное условие - для пустого подмассиваmid = (low + high) / 2; // середина подмассива.Insert(A[mid]); // вставляем элемент из середины подмассива(A, low, mid - 1); // рекурсия для левой половины(A, mid + 1, high); // рекурсия для правой половины

}

// конструктор на основе массиваBinaryTree(Data [] Records, int NRecords)

{(NRecords == 0) // если массив пустой

{.root = null;;

}

// если более одной записи - требуется сортировка

if (NRecords > 1) QuickSort(Records, 0, NRecords - 1);

// строим по отсортированному массиву сбалансированное дерево

IBTInsert(Records, 0, NRecords - 1);

}

bool Insert(Data NewItem) // вставка

{(root == null) // если дерево пустое

{= new BinaryTreeNode<Data>(NewItem);true;

}

// для непустого дерева

<Data> cur = root;

while (true)

{

// если такой элемент уже есть в дереве, вставка неуспешна

if (cur.Item.CompareTo(NewItem) == 0) return false;

// если элемент в узле cur больше элемента NewItem

if (cur.Item.CompareTo(NewItem) > 0)

{(cur.Left == null) // если у cur нет левого потомка

{

// вставляем влево и завершаем вставку.Left = new BinaryTreeNode<Data>(NewItem);;

}

= cur.Left; // если у cur есть левый потомок, идём к нему

}

// если элемент в узле cur меньше элемента NewItem

{

// действуем аналогично предыдущей ситуации, но в правом поддереве

if (cur.Right == null)

{.Right = new BinaryTreeNode<Data>(NewItem);;

}

= cur.Right;

}

}

true;

}

// визуализация поддерева с корнем rootvoid VisualiseTree(Graphics G, BinaryTreeNode<Data> root,LevelH, int radius, int left, int right, int top, Color NodesColor,LeavesColor, Font NodesLabel)

{

// levelH - высота области под один уровень, radius - радиус круга, который показывает узел,

// NodesColor - цвет внутренныз узлов, LeavesColor - цвет листьев,

// NodesLabel - шрифт для показа элементов, G - объект, куда выводим

// координаты центра круга, обозначающего узел дерева

int xc = (left + right) / 2, yc = top + LevelH / 2;

// кисть для закраски круга, цвет зависит от того, root - лист или нет

Brush ForEllipse = new SolidBrush((root.IsLeaf() == true) ? LeavesColor : NodesColor);

// рисуем узел-кружок.FillEllipse(ForEllipse,Rectangle(xc - radius, yc - radius, 2 * radius, 2 * radius));

// показываем элемент узла.DrawString(root.Item.ToString(), NodesLabel, Brushes.Black,Rectangle(xc - radius, yc - radius / 2, 2 * radius, radius));

d = (int)(Math.Sqrt(0.5) * ((double)radius));rchild_left, rchild_top = top + LevelH, rchild_right;xc_child, yc_child = rchild_top + LevelH / 2;

if (root.Left != null) // если есть левое поддерево

{

// координаты области построения_left = left;

rchild_right = (left + right) / 2;_child = (rchild_left + rchild_right) / 2;

// рисуем соединительную линию между узлом и левым сыном

G.DrawLine(new Pen(Color.Black), xc_child, yc_child - d, xc - d, yc + d);

// рекурсивный вызов для левого сына(G, root.Left, LevelH, radius, rchild_left, rchild_right,_top, NodesColor, LeavesColor, NodesLabel);

}

(root.Right != null) // если есть правое поддерево (аналогично левому)

{_left = (left + right) / 2;_right = right;_child = (rchild_left + rchild_right) / 2;.DrawLine(new Pen(Color.Black), xc + d, yc + d, xc_child, yc_child - d);(G, root.Right, LevelH, radius, rchild_left, rchild_right,_top, NodesColor, LeavesColor, NodesLabel);

}

}

// количество уровней в поддереве с корнем root

private int LevelsAmount(BinaryTreeNode<Data> root)

{lev_left_sub = 0, lev_right_sub = 0;

// если левое поддерево непустое, считаем его число уровней

if (root.Left != null) lev_left_sub = LevelsAmount(root.Left);

// если правое поддерево непустое, считаем его число уровней

if (root.Right != null) lev_right_sub = LevelsAmount(root.Right);

// число уровней дерева = 1 + число уровней самого высокого поддерева

// если левое поддерево выше правого(lev_left_sub >= lev_right_sub)lev_left_sub + 1;lev_right_sub + 1; // если правое поддерево выше левого

}

// визуализация дерева - главная функцияvoid VisualiseTree(Graphics G, int radius, int width, int height,NodesColor, Color LeavesColor, Font NodesLabel)

{(this.root == null) // для пустого дерева

{.DrawString("Дерево пустое (root = null)", NodesLabel, Brushes.Black,

(float)0.0, (float)0.0);;

}

// для непустого дерева

nLevs = LevelsAmount(this.root); // вычисляем количество уровней

VisualiseTree(G, this.root, height / nLevs, radius, 0, width, 0,, LeavesColor, NodesLabel); // визуализируем дерево

}

// поиск родителя для узла ItemBinaryTreeNode<Data> FindParent(Data Item)

{(this.root.Item.CompareTo(Item) == 0) return null;<Data> cur = root;(true)

{(cur.Item.CompareTo(Item) > 0)

{(cur.Left == null) break;(cur.Left.Item.CompareTo(Item) == 0) break;= cur.Left;

}

{(cur.Right == null) break;(cur.Right.Item.CompareTo(Item) == 0) break;= cur.Right;

}

}

cur;

}

bool Remove(Data ToRemove) // удаление элемента ToRemove

{<Data> nodeToRemove = root;<Data> parent = null;

// спуск с поиском удаляемого узла((nodeToRemove != null) && (ToRemove.CompareTo(nodeToRemove.Item) != 0))

{= nodeToRemove;(ToRemove.CompareTo(nodeToRemove.Item) < 0)= nodeToRemove.Left;nodeToRemove = nodeToRemove.Right;

}

// если запрашиваемый элемент отсутствует(nodeToRemove == null) return false;

// если удаляемый узел - корень, и он единственный

if (nodeToRemove == root && root.IsLeaf() == true)

{= null;true;

}

// если удаляемый узел является листовым

if (nodeToRemove.Left == null && nodeToRemove.Right == null)

{

// если он - левый ребёнок своего родителя

if (nodeToRemove.Item.CompareTo(parent.Item) < 0).Left = null;

parent.Right = null; // если он - правый ребёнок своего родителя

return true;

}

// если у удаляемого узла есть только правое поддерево

if (nodeToRemove.Left == null && nodeToRemove.Right != null)

{

// если удаляемый узел - корень(nodeToRemove == root) root = root.Right;

else // если удаляемый узел - не корень

{

// если удаляемый узел - левый ребёнок своего родителя

if (nodeToRemove.Item.CompareTo(parent.Item) < 0)

parent.Left = nodeToRemove.Right;

// если он правый ребёнок своего родителя

else parent.Right = nodeToRemove.Right;

}true;

}

// если у удаляемого узла есть только левое поддерево

if (nodeToRemove.Left != null && nodeToRemove.Right == null)

{

// если удаляемый узел - корень(nodeToRemove == root) root = root.Left;

else // если удаляемый узел - не корень

{

// если удаляемый узел - левый ребёнок своего родителя

if (nodeToRemove.Item.CompareTo(parent.Item) < 0)

parent.Left = nodeToRemove.Left;

// если удаляемый узел - правый ребёнок своего родителя

else parent.Right = nodeToRemove.Left;

}true;

}

// если у удаляемого узла есть оба поддерева

// ищем наибольший элемент в левом поддереве удаляемого узла

BinaryTreeNode<Data> largestItem = nodeToRemove.Left;(largestItem.Right != null)= largestItem.Right;

// ищем родителя наибольшего элемента в левом поддереве

BinaryTreeNode<Data> ParentOfLI = FindParent(largestItem.Item);

if (nodeToRemove.Left != largestItem) // если этот родитель - не сам удаляемый узел

{

// если у наибольшего элемента есть левое поддерево

if (largestItem.Left != null) ParentOfLI.Right = largestItem.Left;

else ParentOfLI.Right = null; // если у него нет левого поддерева

}

// если этот родитель - сам удаляемый узел

else nodeToRemove.Left = largestItem.Left;

// заменяем элемент удаляемого узла на наибольший элемент в левом поддереве

nodeToRemove.Item = largestItem.Item;true;

}

}

}

Приложение 3

Графический интерфейс программы