Поиск по бинарному дереву

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

Министерство Образования и науки Украины

Национальная Металлургическая Академия Украины

Кафедра информационных технологий и систем

Индивидуальное Задание Вариант 1

по дисциплине ”Теория алгоритмов”

Проверил к.т.н. доц. Журба А.А.

Выполнил

Студент гр.КН01-17 Старина М.С.

Днепр 2018



поиск бинарный символ массив



#include "pch.h"

#include <iostream>

#include <conio.h>

#include <stdlib.h>

#include <stddef.h>

#include <time.h>

#include <vector>

using namespace std;

bool menu; // Триггер для программы

unsigned int endtime, starttime, Searchtime; // время

enum eMenu { NOONE = 0, INPUT, DELETE, SHOW, SEARCH, RAND, SORT }; // состояния меню

static eMenu MenuChoose; // триггер меню

void MenuDraw(); // рисуем меню

void MenuInput(); // переводим меню в состояния(вкладки)

void MenuLogic(int n, int* arr); // для каждого состояния прописываем логику

void Setup(); // сетупер

void Quicksort(int* arr, int b0, int e0); // сортировка

void FillArray(int* const arr, const int size); // рандом

void ShowArray(const int* const arr, const int size); // вывод

void push_back(int*& arr, int& size, const int value); // доб элемент

void BinarTree(int* arr, int b0, int e0, int target); // поиск

void push_back1(int*& arr, int& size); // удаляем

int main(){

cout << "Enter mas size: " << endl;

int n;

cin >> n;

int* arr = new int[n];

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

{

arr[i] = 0;

}

Setup();

while (!menu) // пока menu = false -выполняем цикл. Рисуем, проверяем на нажатие клавиш - даем им логику

{

MenuDraw();

MenuInput();

MenuLogic(n, arr);

switch (MenuChoose)

{

case INPUT:

cout << "Enter element " << endl;

int m;

cin >> m; // вводим что добавить

push_back(arr, n, m);

MenuChoose = NOONE;

break;

case DELETE:

cout << "Enter index of element: " << endl;

int index;

cin >> index; // выбираем индекс , какой удалить

swap(arr[index], arr[n - 1]);

push_back1(arr, n);

MenuChoose = NOONE;

break;

}

}

delete[] arr;

return 0;

}

void Setup()

{

menu = false;

}

void MenuDraw()

{

system("cls");

cout << "---------------" << endl;

cout << "1.Enter Element" << endl;

cout << "2.Delete Element" << endl;

cout << "3.ANIME" << endl;

cout << "4.QuickSort" << endl;

cout << "5.Show ATD" << endl;

cout << "6.Search Element" << endl;

cout << "0.Exit" << endl;

cout << "---------------" << endl;

}

void MenuInput()

{

if (_kbhit()) // позволяет оставлять в буфере состояния меню , как будто мы постоянно жали бы на эту кнопку

{

switch (_getch())

{

case '1':

MenuChoose = INPUT;

break;

case '2':

MenuChoose = DELETE;

break;

case '3':

MenuChoose = RAND;

break;

case '4':

MenuChoose = SORT;

break;

case '5':

MenuChoose = SHOW;

break;

case '6':

MenuChoose = SEARCH;

break;

case '0':

menu = true; // закрываем программу

break;

}

}

}

void MenuLogic(int n, int* arr)

{

switch (MenuChoose) // проверяем в каком состоянии тригер

{

case SHOW:

ShowArray(arr, n);

break;

case SEARCH:

cout << "Enter target: " << endl;

int target;

cin >> target;

starttime = clock();

BinarTree(arr, 0, n - 1, target);

endtime = clock();

Searchtime = (endtime - starttime)/100;

cout << "Binary tree time: " << Searchtime << endl;

system("pause");

MenuChoose = NOONE;

break;

case RAND:

FillArray(arr, n);

break;

case SORT:

Quicksort(arr, 0, n - 1);

break;

case NOONE:

break;

}

}

void Quicksort(int* arr, int b0, int e0) // просто идем с двух сторон и свапаем, после рекурсивно вызываем

{

int d = arr[e0];

int b = b0;

int e = e0;

do

{

while (arr[b] < d)

++b;

while (arr[e] > d)

--e;

if (b <= e)

{

swap(arr[b], arr[e]);

++b;

--e;

}

} while (b <= e);

if (e > b0)

Quicksort(arr, b0, e);

if (b < e0)

Quicksort(arr, b, e0);

}

void FillArray(int* const arr, const int size)

{

srand(time(NULL));

for (int i = 0; i < size; i++)

{

arr[i] = 1 + rand() % 99;

}

}

void ShowArray(const int* const arr, const int size)

{

for (int i = 0; i < size; i++)

{

cout << arr[i] << " ";

}

cout << endl << endl;

}

// Работает только в той функции, где создан массив. Имхо с копиями не работаем.

void push_back(int*& arr, int& size, const int value)

{

int* newArray = new int[size + 1]; // создаем массив с 1 доп слотом и заполняем его елементами нашего массива,

for (int i = 0; i < size; i++)

{

newArray[i] = arr[i];

}

newArray[size] = value; // в последний слот закидываем значение

size++; // увеличивем сайз, для того что б в след раз у нас доб в новый слот

delete[] arr; // чистим наш массив прошлый

arr = newArray; // задаем указателю новый массив

}

void push_back1(int*& arr, int& size) // тоже самое , но создаем массив на 1 слот меньше и удаляем последний лишний, а индекс выбираем и свапаем с последним

{

int* newArray = new int[size - 1];

for (int i = 0; i < size - 1; i++)

{

newArray[i] = arr[i];

}

size--;

delete[] arr;

arr = newArray;

}

void BinarTree(int *arr, int b0, int e0, int target) // поиск просто на ифах, циклично , пока начало меньше или равно концу

{

int k = 0;

while (b0 <= e0)

{

int mid = (b0 + e0) / 2;

if (target == arr[mid])

{

cout << "Target: " << target << " Index: " << mid << endl;

k = 1; // нужно для того , что бы вывести NO one если не нашло

break;

}

else if (target > arr[mid])

{

b0 = mid + 1; // меняем мидл ,прежде проверяем справа или слева наша цель

}

else

{

e0 = mid - 1; // меняем центр , проверяя справа или слева наша цель

}

}

if (k == 0)

cout << "No one" << endl;

k = 0;

system("pause");

}

Размещено на Allbest.ru