Система полуумного дома
Получение температуры...
Получение влажности...
Free BST Tree
Уххххх, ребята и девчата. На четвертом курсе универа мне пришлось столкнуться с траблой по предмету структуры и алгоритмы данных. Получили мы значит задание создать бинарное дерево на джаве или плюсах, да так чтобы был опрос размера дерева, очистка дерева, проверка дерева на пустоту, поиск элемента с заданным ключом, включение нового элемента, удаление элемента, обход дерева по схеме (в моем варианте t-Lt-Rt) и разными итераторами и т.д. и т.п.
Что такое это BST-дерево, оно же двоичное дерево поиска. Это такая структура, при которой при создании и добавлении новых элементов они записываются в уже отсортированном виде. Если запустить код ниже, то будет всё более понятно, когда выведется его структура. Корень дерева находится слева, элементы, которые больше выше, которые меньше соответственно ниже. Многие куски кода я подсмотрел на разных ресурсах, так что да что-то сплагиатил, что-то перестроил под свою работу, ну а что-то додумал сам.
Сама программа на плюсах запускается в двух режимах стандартном и с ключом, в который передаем количество элементов в дереве.
Сам код:
#include <iostream>
#include <algorithm>
using namespace std;
//Отображение меню
void showmenu() {
//Отображение меню
cout << " ***Нажмите необходимую клавижу для выбора режима в меню:***\n";
cout << "******************************************************************************************\n";
cout << "*1.опрос размера дерева *\n";
cout << "*2.очистка дерева *\n";
cout << "*3.проверка дерева на пустоту *\n";
cout << "*4.поиск элемента с заданным ключом *\n";
cout << "*5.включениенового элемента с заданным ключом *\n";
cout << "*6.удаление элемента с заданным ключом *\n";
cout << "* *\n";
cout << "*итератор для доступа к элементам дерева с операциями: *\n";
cout << "*a.установка на корень дерева *\n";
cout << "*b.проверка конца дерева *\n";
cout << "*c.доступ к данным текущего элемента дерева *\n";
cout << "*d.переход к следующему по значению ключа элементу дерева *\n";
cout << "*e.переход к предыдущему по значению ключа элементу дерева *\n";
cout << "* *\n";
cout << "*7.обход дерева по схеме t->Lt->Rt *\n";
cout << "*8.поиск для заданного ключа предыдущего по значению ключа в дереве (нерекурсивная форма)*\n";
cout << "*9.вывод структуры дерева на экран, *\n";
cout << "*0.опрос числа просмотренных операцией узлов дерева. *\n";
cout << "* *\n";
cout << "*Для выхода нажмите q. *\n";
cout << "******************************************************************************************\n";
}
//Проверка валидности ввода символа меню
bool ValidInput(char InSym) {
bool valid = false;
int i = 0;
char validSym[17] = { '1','2','3','4','5','6','7','8','9','0','a','b','c','d','e','t','\0' };
do {
if (validSym[i] == InSym) valid = true;
i++;
} while (validSym[i] != '\0');
if (!valid) cout << "Я вас не понял, попробуйте еще раз\n";
return valid;
}
//Пара затычек на этап разработки
void stub()
{
return;
}
void prints(char a) {
cout << "Я понял, вы нажали " << a;
}
// Функция преобразования строки в число
int StrToInt(char* s)
{
int temp = 0; // число
int i = 0;
int sign = 0; // знак числа 0- положительное, 1 — отрицательное
if (s[i] == '-')
{
sign = 1;
i++;
}
while (s[i] >= 0x30 && s[i] <= 0x39)
{
temp = temp + (s[i] & 0x0F);
temp = temp * 10;
i++;
}
temp = temp / 10;
if (sign == 1)
temp = -temp;
return(temp);
}
int tabs = 0; //Для создания отступов
int kol_vo = 0;
int address;
int diffsearch = 0;
int diffadd = 0;
int difremove = 0;
int dep_count = 0;
//Кол-во отступов высчитывается по кол-ву рекурсивного вхождения при выводе в фукцию print
//Структура ветки
struct Branch
{
int Data; //Поле данных
Branch* LeftBranch; //УКАЗАТЕЛИ на соседние веточки
Branch* RightBranch;
};
Branch* currentelem; //текущий элемент в итераторе
//Функция внесения данных
void Add(int aData, Branch*& aBranch)
{
//Если ветки не существует
if (!aBranch)
{ //создадим ее и зададим в нее данные
aBranch = new Branch;
aBranch->Data = aData;
aBranch->LeftBranch = 0;
aBranch->RightBranch = 0;
return;
}
else //Иначе сверим вносимое
if (aBranch->Data > aData)
{ //Если оно меньше того, что в этой ветке - добавим влево
Add(aData, aBranch->LeftBranch);
}
else
{ //Иначе в ветку справа
Add(aData, aBranch->RightBranch);
};
}
//Функция добавления элемента
void add_elem(int aData, Branch*& aBranch)
{
if (!aBranch)
{
aBranch = new Branch;
aBranch->Data = aData;
aBranch->LeftBranch = 0;
aBranch->RightBranch = 0;
diffadd++;
//cout << diffadd;
return;
}
else
{
if (aData < aBranch->Data) {
add_elem(aData, aBranch->LeftBranch);
diffadd++;
//cout << diffadd;
}
else if (aData > aBranch->Data) {
add_elem(aData, aBranch->RightBranch);
diffadd++;
//cout << diffadd;
}
}
return;
}
//Функция вывода дерева
void print(Branch* aBranch)
{
if (!aBranch) return; //Если ветки не существует - выходим. Выводить нечего
tabs += 5; //Иначе увеличим счетчик рекурсивно вызванных процедур
//Который будет считать нам отступы для красивого вывода
print(aBranch->LeftBranch); //Выведем ветку и ее подветки слева
for (int i = 0; i < tabs; i++) cout << " "; //Потом отступы
cout << aBranch->Data << endl; //Данные этой ветки
print(aBranch->RightBranch);//И ветки, что справа
tabs -= 5; //После уменьшим кол-во отступов
return;
}
//Функция обхода дерева в соответствии с вариантом
void treeprint(Branch* aBranch) {
if (aBranch != NULL) {
cout << aBranch->Data << " ";
treeprint(aBranch->LeftBranch);
treeprint(aBranch->RightBranch);
}
}
//Функция подсчета элементов
int SumOfBranch(Branch* aBranch) {
static int SumBranch = 0;
if (aBranch != NULL) {
//sumOfCount += aBranch->Data;
SumBranch++;
SumOfBranch(aBranch->LeftBranch);
SumOfBranch(aBranch->RightBranch);
}
return SumBranch;
}
//Функция подсчета глубины дерева
int Depth(Branch* aBranch, int dep_count) {
if (aBranch == NULL) return dep_count;
return max(Depth(aBranch->LeftBranch, dep_count + 1), Depth(aBranch->RightBranch, dep_count + 1));
}
//Функция подсчета суммы всех элементов
int SumOfCount(Branch* aBranch) {
static int SumCount = 0;
if (aBranch != NULL) {
//sumOfCount += aBranch->Data;
SumCount += aBranch->Data;
SumOfCount(aBranch->LeftBranch);
SumOfCount(aBranch->RightBranch);
}
return SumCount;
}
//Проверка на пустоту дерева
void is_Empty(Branch*& aBranch)
{
if (!aBranch)
{
cout << "Дерево пустое...";
}
else
{
cout << "Дерево не пустое...";
}
}
//установка на корень дерева
void is_coren(Branch*& aBranch) {
cout << "Корень дерева: " << aBranch->Data << '\n';
currentelem = aBranch;
cout << "Итератор установлен на корень дерева\n";
}
//Проверка на корень дерева
bool is_root(Branch*& aBranch) {
if (aBranch == currentelem) {
return true;
}
else return false;
}
//функция проверки конца дерева.
bool is_end(Branch*& aBranch) {
if (!aBranch->LeftBranch && !aBranch->RightBranch) {
return true;
}
else return false;
}
//Поиск максимального элемента
Branch* maximum(Branch*& aBranch) {
if (aBranch->RightBranch == NULL) return aBranch;
return maximum(aBranch->RightBranch);
}
//Поиск минимального элемента
Branch* minimum(Branch*& aBranch) {
if (aBranch->LeftBranch == NULL) return aBranch;
return minimum(aBranch->LeftBranch);
}
//Поиск следующего элемента по ключу
Branch* next(Branch*& aBranch, int aData) {
Branch* sucessor = NULL;
Branch* current = aBranch;
while (current != NULL) {
if (current->Data > aData) {
sucessor = current;
current = current->LeftBranch;
}
else {
current = current->RightBranch;
}
}
return sucessor;
}
//Поиск предидущего элемента по ключу
Branch* prev(Branch*& aBranch, int aData) {
Branch* sucessor = NULL;
Branch* current = aBranch;
while (current != NULL) {
if (current->Data < aData) {
sucessor = current;
current = current->RightBranch;
}
else {
current = current->LeftBranch;
}
}
return sucessor;
}
//Поиск элемента по ключу
Branch* elementSearch(Branch*& aBranch, int aData) {
if (aBranch == NULL or aData == aBranch->Data) {
//cout << "Мы в корне\n";
//cout << "сложность " << dificult << " ";
//cout << diffsearch <<" ";
return aBranch;
}
else if (aBranch->Data > aData) {
if (aBranch->Data != aData) {
diffsearch++;
//cout << diffsearch << " ";
}
return elementSearch(aBranch->LeftBranch, aData);
//cout << "Идем влево\n";
}
else {
if (aBranch->Data < aData) {
diffsearch++;
//cout << diffsearch << " ";;
}
return elementSearch(aBranch->RightBranch, aData);
//cout << "Идем в право\n";
}
}
//Удаление элемента
Branch* del_elem(Branch*& aBranch, int aData) {
if (aBranch == NULL) {
return aBranch;
difremove++;
}
if (aData == aBranch->Data) {
Branch* tmp;
if (aBranch->RightBranch == NULL) {
tmp = aBranch->LeftBranch;
difremove++;
}
else {
Branch* ptr = aBranch->RightBranch;
if (ptr->LeftBranch == NULL) {
ptr->LeftBranch = aBranch->LeftBranch;
tmp = ptr;
difremove++;
}
else {
Branch* pmin = ptr->LeftBranch;
while (pmin->LeftBranch != NULL) {
difremove++;
ptr = pmin;
pmin = ptr->LeftBranch;
}
ptr->LeftBranch = pmin->RightBranch;
pmin->LeftBranch = aBranch->LeftBranch;
pmin->RightBranch = aBranch->RightBranch;
tmp = pmin;
difremove++;
}
}
//cout << "сложность " << dificult;
delete aBranch;
return tmp;
}
else if (aData < aBranch->Data) {
aBranch->LeftBranch = del_elem(aBranch->LeftBranch, aData);
difremove++;
}
else {
aBranch->RightBranch = del_elem(aBranch->RightBranch, aData);
difremove++;
}
return aBranch;
//cout << "сложность " << dificult;
}
//Очитстка дерева
void FreeTree(Branch*& aBranch)
{
if (aBranch->LeftBranch) FreeTree(aBranch->LeftBranch);
if (aBranch->RightBranch) FreeTree(aBranch->RightBranch);
aBranch = NULL;
}
int main(int argc, char *argv[]) {
if (argc == 1) {
setlocale(LC_ALL, "Russian");
Branch* Root = 0;
cout << "Введите размер будущего дерева: ";
int vel;
cin >> vel;
/* while (vel > 99) {
cout << "Введите целое значение до 100\n";
cin >> vel;
}*/
int element;
int operations = 0; //Количество операций над узлами дерева
//Создаем дерево
for (int i = 0; i < vel; i++) {
int count = rand() % 100;
while (elementSearch(Root, count)) {
count = rand() % 100;
}
Add(count, Root);
}
print(Root);
cout << "\n";
is_coren(Root);
while (true)
{
char inSym;
showmenu();
cin >> inSym;
if (inSym == 'q') break;
else {
if (ValidInput(inSym)) {
switch (inSym)
{
case '1':
cout << "Элементов в дереве " << SumOfBranch(Root) << ", и их сумма составляет " << SumOfCount(Root) << ",а максимальная глубина составляет " << Depth(Root, dep_count) << '\n';
operations++;
break;
case '2':
FreeTree(Root);
operations++;
cout << "Дерево очищено\n";
break;
case '3':
is_Empty(Root);
operations++;
break;
case '4':
cout << "Какой элекмент пытаемся найти?: ";
diffsearch = 0;
cin >> element;
if (!elementSearch(Root, element)) {
cout << "Элемент " << element << " не найден, сложность: " << diffsearch << "\n";
}
else {
cout << "Элемент " << element << " найден, сложность: " << diffsearch << "\n";
}
operations++;
break;
case '5':
cout << "Введите новый элемент, который вы хотите добавить в дерево: ";
cin >> element;
if (elementSearch(Root, element)) {
cout << "Такой элемент уже существует\n";
}
else {
add_elem(element, Root);
cout << "Сложность: " << diffadd << '\n';
diffadd = 0;
cout << "Элемент " << element << " добавлен\n";
}
operations++;
break;
case '6':
cout << "Введите новый элемент, который вы хотите удалить из дерева: ";
cin >> element;
if (!elementSearch(Root, element)) {
cout << "Невозможно удалить, данного элемент не существует\n";
}
else
{
difremove = 0;
del_elem(Root, element);
cout << "Элемент " << element << " удален, сложность:" << difremove << " \n";
}
operations++;
break;
case '7':
treeprint(Root);
cout << '\n';
operations++;
break;
case '8':
cout << "Для какого элмента вы бы хотели найти предидущий элемент?: ";
cin >> element;
cout << "Для " << element << " предидущий по значению будет " << prev(Root, element)->Data << '\n';
operations++;
break;
case '9':
print(Root);
operations++;
break;
case '0':
cout << "С момента запуска программы вы провели над деревом и его узлами " << operations << " операций\n";
break;
case 'a':
is_coren(Root);
operations++;
break;
case 'b':
if (is_end(currentelem)) {
cout << currentelem->Data << " является концом дерева \n";
}
else {
cout << currentelem->Data << " не является концом дерева \n";
}
operations++;
break;
case 'c':
cout << "Данными узла " << currentelem->Data << " являются:\n";
cout << "-адресное пространство: " << currentelem << "\n" << "-подветвями с самим элементом являются: ";
treeprint(elementSearch(Root, currentelem->Data));
cout << '\n';
operations++;
break;
case 'd':
if (maximum(Root)->Data != currentelem->Data) {
cout << "Следующим элементом для " << currentelem->Data << " является " << next(Root, currentelem->Data)->Data << "\n";
currentelem = next(Root, currentelem->Data);
cout << "Итератор переставлен.\n";
}
else {
cout << "Вы достигли максимума дерева!\n";
}
break;
case 'e':
if (minimum(Root)->Data != currentelem->Data) {
cout << "Предидущим элементом для " << currentelem->Data << " является " << prev(Root, currentelem->Data)->Data << "\n";
currentelem = prev(Root, currentelem->Data);
cout << "Итератор переставлен.\n";
}
else
{
cout << "Вы достигли минимума дерева!\n";
}
operations++;
break;
case 't': //Для теста текущего элемента
cout << currentelem << '\n' << currentelem->Data << '\n';
break;
default:
stub();
break;
}
}
else {
continue;
}
}
}
return 0;
}
else {
int elements = StrToInt(argv[1]);
int predel = elements * 10;
//Заполняем первую половину дерева
int polovina = elements / 2;
Branch* Root = 0;
for (int i = 0; i < polovina; i++) {
int count = rand() % predel;
while (elementSearch(Root, count)) {
count = rand() % predel;
}
Add(count, Root);
}
//Находим 20% дерева для провдения операций
int countofoper = elements / 5;
int* ary = new int[countofoper];
for (int i = 0; i < countofoper; i++) {
int count = rand() % predel;
while (elementSearch(Root, count)) {
count = rand() % predel;
}
Add(count, Root);
ary[i] = count;
}
float meddifadd = 0.0; //Средняя сложность добавления
float meddifsearch = 0.0; //Средняя сложность поиска
float meddifremov = 0.0; //Средняя сложность удаления
int worstadd, worstsearch, worstremov; //худшие случаи
worstadd = worstsearch = worstremov = 0;
//заполняем попутно находя среднюю сложность
for (int i = 0; i < countofoper; i++) {
add_elem(ary[i], Root);
meddifadd += diffadd;
if (diffadd > worstadd) worstadd = diffadd;
diffadd = 0;
}
meddifadd = meddifadd / countofoper;
//добавляем остаток элементов
int remainder = elements - polovina - countofoper;
for (int i = 0; i < remainder; i++) {
int count = rand() % predel;
while (elementSearch(Root, count)) {
count = rand() % predel;
}
Add(count, Root);
}
//ищем элементы из массива и находим среднюю сложность
for (int i = 0; i < countofoper; i++) {
diffsearch = 0;
elementSearch(Root, ary[i]);
meddifsearch += diffsearch;
if (diffsearch > worstsearch) worstsearch = diffsearch;
diffsearch = 0;
}
meddifsearch = meddifsearch / countofoper;
//удаляем элементы
for (int i = 0; i < countofoper; i++) {
difremove = 0;
del_elem(Root, ary[i]);
meddifremov += difremove;
if (difremove > worstremov) worstremov = difremove;
difremove = 0;
}
meddifremov = meddifremov / countofoper;
//глубина дерева
int glubina = Depth(Root, dep_count);
cout <<elements<< "\t" << glubina <<"\t" << meddifsearch << "\t" << worstsearch << '\t' << meddifadd << "\t" << worstadd << '\t' << meddifremov << "\t" << worstremov << "\t";
return 1;
}
}
Тут сразу же оговорю минусы - я не сделал выбор типа данных, содержащихся в элементе (и у меня прокатило), а также программа в режиме с ключом не создает более 32768 элементов.
Следующий небольшой скрипт на питоне запускает эту программу (у меня скомпилированная называется 'BST_Three.exe', если у вас по-другому, то надо отредактировать место в коде на питоне, где попадается это название и обе должны лежать в одной папке. Скрипт на питоне выведет подобие таблицы. Ниже приведу расшифровку названий в шапке.
- Elem – количество элементов в дереве
- Depth – глубина дерева
- Madd – средняя сложность добавления
- Wadd – худшая сложность добавления
- Msearch – средняя сложность поиска
- Wsearch – худшая сложность поиска
- Mrem – средняя сложность удаления
- Wrem – худшая сложность удаления
- Time – время работы программы
Ну и сам код программы для теста на питоне:
import os
import time
print('elem'+'\t' + 'depth' +'\t'+'madd' + '\t' + 'wadd' + '\t'+'msearch'+'\t' + 'wsearch' + '\t' + 'mrem' + '\t' + 'wrem' + '\t' +'time' + '\n')
i = 10
while i < 100:
start_time = time.time()
os.system('BST_Three.exe ' + str(i))
print(round((time.time() - start_time),3))
i = i + 10
while i < 1000:
start_time = time.time()
os.system('BST_Three.exe ' + str(i))
print(round((time.time() - start_time),3))
i = i + 100
while i < 100000:
start_time = time.time()
os.system('BST_Three.exe ' + str(i))
print(round((time.time() - start_time),3))
i = i+1000;
input()
В заключении хочу сказать, мне не жалко вот так нахаляву выставить код из своей работы, глядя на него может кто-то поймёт сам принцип как делать данную работу. К тому же я не выложил своих пояснительных записок и выводов с таблицами и графиками. Тут уж сами, но я затупил, как и некоторые одногруппники на этом поэтому вот. А всякие исполнители работ, желающих за подобное задание сумму овер 10К - да идите вы козе в трещину! =)))))
Вы не можете комментировать записи, для этого вам необходимо войти или зарегистрироваться
Последний комментарий
mcfirsachy написал к публикации QUAD405 из поднебесной cледующее:
Кто дочитал до конца - извините за огромное количество ошибок =)))) Хотелось бы добавить что на выпрямителе стоит защита акустики - подключение колонок с задержкой.Погода за бортом
Сейчас в Сосновом Бору пасмурно
Скорость ветра 6.58 м/с
Влажность 89 %
Температура -9.39 °C