Описание работы программного комплекса. Инструкция по работе с программным комплексом

программный алгоритм данные бинарный

После запуска программы на экране пользователя появляется окно (см. Рисунок 11), в котором будет выведены: номер варианта задания, формулировка задания и список команды выполняемых программой.

Рисунок 11 –Запуск программы

Каждую команду можно активировать, нажав соответствующую клавишу на клавиатуре («1» - Для заполнения дерева автоматически, «2» - Для ввода дерева вручную, «3» - Для выхода из программы).

Если пользователем будет выбрана команда «3», то программа завершит работу.

Команда «1» позволит пользователю самостоятельно заполнить дерево элементами в диалоговом режиме. Также произойдёт вывод введённого дерева и вывод обработанного дерева, а также их обход и глубина. (см. Рисунок 12).

Рисунок 12 - ввод дерева с клавиатуры

Выбрав команду «2», программа автоматически сгенерирует дерево заданной длины, наполнив его случайными элементами. Произойдёт вывод этого дерева, затем вывод дерева с удаленными повторяющимися элементами, а также их обходы и глубина (см. Рисунок 13).

Рисунок 13 - Автоматическое генерирование дерева

Заключение

В ходе выполнения курсовой работы были Проанализированы различные способы представления и использования двоичных деревьев поиска. Общие принципы построения деревьев и методы удаления элементов из них.

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

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

Литература

1. «С++. Освой на примерах» М. И. Динман – СПб: БХВ-Петербург, 2006. 384с.

2. «Структуры и алгоритмы обработки данных» И. В. Цапко – Томск: Изд-во Томского политехнического университета, 2007. 184с.

3. «/С++ и 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