Описание работы программного комплекса. Инструкция по работе с программным комплексом
программный алгоритм данные бинарный
После запуска программы на экране пользователя появляется окно (см. Рисунок 11), в котором будет выведены: номер варианта задания, формулировка задания и список команды выполняемых программой.
Рисунок 11 –Запуск программы
Каждую команду можно активировать, нажав соответствующую клавишу на клавиатуре («1» - Для заполнения дерева автоматически, «2» - Для ввода дерева вручную, «3» - Для выхода из программы).
Если пользователем будет выбрана команда «3», то программа завершит работу.
Команда «1» позволит пользователю самостоятельно заполнить дерево элементами в диалоговом режиме. Также произойдёт вывод введённого дерева и вывод обработанного дерева, а также их обход и глубина. (см. Рисунок 12).
Рисунок 12 - ввод дерева с клавиатуры
Выбрав команду «2», программа автоматически сгенерирует дерево заданной длины, наполнив его случайными элементами. Произойдёт вывод этого дерева, затем вывод дерева с удаленными повторяющимися элементами, а также их обходы и глубина (см. Рисунок 13).
Рисунок 13 - Автоматическое генерирование дерева
Заключение
В ходе выполнения курсовой работы были Проанализированы различные способы представления и использования двоичных деревьев поиска. Общие принципы построения деревьев и методы удаления элементов из них.
Задача, поставленная в данной курсовой работе, является достаточно сложной с точки зрения составления алгоритма. Помимо этого, она довольно сложна в плане реализации, так как требует детального изучения и понимания предметной области. Результатом выполнения курсовой работы является полноценное приложение с отдельными функциями, разработанное в соответствии с современными подходами к созданию программного обеспечения. Был разработан и реализован пользовательский интерфейс, а также защита от возникновения ошибки при неправильном вводе. Также написанное приложение решает поставленную ранее задачу и полностью соответствует всем установленным для нее требованиям.
Выполнение данной работы позволило закрепить изученный материал, а также получить новые, принципиально важные знания в области программирования, проектирования и разработки программных продуктов.
Литература
«С++. Освой на примерах» М. И. Динман – СПб: БХВ-Петербург, 2006. 384с.
«Структуры и алгоритмы обработки данных» И. В. Цапко – Томск: Изд-во Томского политехнического университета, 2007. 184с.
«/С++ и MS Visual C++ 2008 для начинающих» Б.И. Пахомов – СПб: БХВ-Петербург, 2009. 624с.
Приложения
Приложение А
Листинг программы
#include "stdafx.h"
#include <iostream>
#include <conio.h>
#include <iomanip>
#include <time.h>
#pragma hdrstop//директива связана с особенностью работы препроцессора, производительность которого
//существенно повышается, если учитывается, что некоторое количество заголовочных файлов
//общие для всех модулей
#pragma argsused//говорит компилятору, что следует подавить выдачу предупреждающего сообщения о том,
//что параметры функции main () никак в ней не используются.
//---------------------------------------------------------------------------
using namespace std;
struct TREE
{
char dann;
TREE *pleft;
TREE *pright;
};
TREE *root = NULL;
TREE *parent = NULL;
int i, k, b, n, c, p;
char tt = 0;
bool array[100];
char *str = new char [n];
char a = 0;
char cmax, cmin;
//---------------------------------------------------------------------------
void build(TREE *tt, char str) // функция построения дерева
{
TREE *left;
TREE *right;
if (tt->dann==NULL)
{
tt->dann=str;
tt->pleft=NULL;
tt->pright=NULL;
}
else
{
if (str<tt->dann)
if (tt->pleft == NULL)
{
left = new TREE;
tt->pleft = left;
left->dann = str;
left->pleft = NULL;
left->pright = NULL;
}
else build(tt->pleft, str);
else
if (tt->pright == NULL)
{
right = new TREE;
tt->pright = right;
right->dann = str;
right->pleft = NULL;
right->pright = NULL;
}
else build(tt->pright, str);
}
}
//---------------------------------------------------------------------------
void Delet1(TREE* node, TREE*& parent) // функция удаления узла дерева
{
if (!node) return;
if (!node->pleft && !node->pright)
{
delete node;
if (parent) parent = 0;
}
else if (!node->pleft && node->pright)
{
if (parent) parent = node->pright;
delete node;
}
else if (node->pleft && !node->pright)
{
if (parent) parent = node->pleft;
delete node;
}
else
{
TREE* temp = node->pright;
while (temp->pleft)
temp = temp->pleft;
temp->pleft = node->pleft;
temp = node;
node = node->pright;
parent = node;
delete temp;
}
}
//---------------------------------------------------------------------------
void Solution(TREE* node, TREE*& parent)//функция поиска повторяющихся элементов
{
while (array[node->dann])
{
Delet1(node, parent);
node = parent;
if (!node) return;
}
array[node->dann] = true;
if (node->pleft) Solution(node->pleft, node->pleft);
if (node->pright) Solution(node->pright, node->pright);
}
//---------------------------------------------------------------------------
void print (TREE *first, int step) // функция печати дерева
{
if (first)
{
print (first->pright, step+1);
for (int i = 1; i <= step; i++) cout << " ";
cout << first->dann << endl;
print (first->pleft, step+1);
}
}
//---------------------------------------------------------------------------
void obhod(TREE *ptr)//функция прямого метода обхода дерева
{
if (ptr)
{
putchar(ptr->dann);
cout << ' ';
if (ptr->pleft) obhod(ptr->pleft);
if (ptr->pright) obhod(ptr->pright);
}
}
//---------------------------------------------------------------------------
void deep(TREE *ptr) // функция определения глубины дерева
{
if (ptr)
{
if (a > b)
{
b = a;
}
if (ptr->pleft)
{
++a;
deep(ptr->pleft);
}
if (ptr->pright)
{
++a;
deep(ptr->pright);
}
}
}
//---------------------------------------------------------------------------
void RandomCreate(TREE*& node, int n) // функция генерации случайных велечин
{
srand(time(0));
node = new TREE;
node->dann = rand() % 9+48;
node->pleft = node->pright = 0;
for(int i = 1; i < n; i++)
build(root, rand() % 9+48);
}
//---------------------------------------------------------------------------
//---------------------------------------------------------------------------
int main() // главная функция
{
//смена кодировки в консоли для отображения русских символов
setlocale(LC_ALL,"rus_rus.1251");
//Вывод задания на экран:
cout << "Вариант 1" << endl << "Построить двоичное дерево поиска из целых чисел.";
cout << "Удалить из него элементы, встречающиеся несколько раз. ";
cout << "Результат вывести на экран. Определить глубину дерева до и после удаления."<<endl;
int n, count;
cout << "Выберите пункт:" << endl;
cout << "1 - Ввод с клавиатуры" << endl;
cout << "2 - Ввод в автоматическом режиме" << endl;
cout << "3 - Выход из программы" << endl;
cout << "-> ";
M: ;
cin >> count;
switch(count)
{
case 1:
cout << "Введите элементы дерева: ";
cin >> str;
n = strlen(str);
root = new TREE;
root->dann = str[0];
root->pleft = NULL;
root->pright = NULL;
for (i = 1; i <n; i++) build(root, *(str+i));
for(i = 0; i < n; i++)
array[i] = false;
break;
case 2:
cout << "Введите количество элементов дерева: " << endl;
cin >> n;
RandomCreate(root, n);
for(i = 0; i < n; i++)
array[i] = false;
break;
case 3:
goto exit;
break;
default:
cout << "Неверный ввод! Повторите ввод снова" << endl;
goto M;
break;
}
cout << endl << "Построенное дерево: " << endl << endl;
print(root, 0);
cout << "Обход дерева: ";
obhod(root);
cout << endl;
deep(root);
cout << endl << "Глубина дерева составляет: " << b << endl;
cout << endl << "Дерево после обработки: " << endl << endl;
Solution(root,root);
print(root, 0);
obhod(root);
a=b=0;
deep(root);
cout << endl << "Глубина дерева после обработки составляет: : " << b << endl;
getch();
exit: ;
return 0;
}
//---------------------------------------------------------------------------
Размещено на Allbest.ru