Результат работы программы

Алгоритмы поиска

Выполнена Затеваловой М.А.

Проверил Силаев А.В.

Задание

Результат работы программы - student2.ru

Вариант

Результат работы программы - student2.ru

Блок-схемы

Результат работы программы - student2.ru Результат работы программы - student2.ru Результат работы программы - student2.ru

Результат работы программы - student2.ru

Код программы

#include<iostream>

#include<time.h>

#include<string>

//Структура записи в таблице

struct Record

{

int Key;

std::string Line;

};

//Заполняет таблицу случайными записями с неповторяющимся ключом

void rndDataNoRepeat(Record* array, int n)

{

srand(time(NULL));

int j = 0;

//заполняем последовательно (обеспечиваем неповторяемость ключа)

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

{

array[i] = *(new Record());

array[i].Key = j + (rand() % 5) + 1;

array[i].Line = "Some text " + std::to_string(i);

j = array[i].Key;

}

//ПЕРЕМЕШИВАЕМ!

int a, b;

Record tmp;

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

{

a = rand() % n;

b = rand() % n;

tmp = array[a];

array[a] = array[b];

array[b] = tmp;

}

//И выводим на экран

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

std::cout << "key: " << array[i].Key << " line: " << array[i].Line << "\n";

std::cout << "\n";

}

//Ищет запись с ключом key последовательным поиском (алгоритм S)

//В случае успеха возвращает индекс записи. В случае неуспеха возвращает -1

int searchS(Record* array, int n, int key)

{

int compareNum = 0;

int i = -1;

do

{

++i;

compareNum += 2;

} while (array[i].Key != key && i != n);

std::cout << "Algorithm S has finished his work. Number of compares: " << compareNum << "\n";

if (i >= n)

return -1;

return i;

}

/*Ищет запись с ключом key последовательным поиском (алгоритм Q)

В случае успеха возвращает индекс записи. В случае неуспеха возвращает -1

*/

int searchQ(Record* array, int n, int key)

{

int compareNum = 0;

Record* tmp = new Record[n + 1];

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

{

tmp[i] = array[i];

}

tmp[n].Key = key;

tmp[n].Line = "";

int i = 0;

do

{

++i;

++compareNum;

} while (tmp[i].Key != key);

std::cout << "Algorithm Q has finished his work. Number of compares: " << compareNum << "\n";

if (i >= n)

return -1;

return i;

}

void sort(Record* array, int n)

{

Record tmp;

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

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

{

if (array[i].Key > array[i + 1].Key)

{

tmp = array[i];

array[i] = array[i + 1];

array[i + 1] = tmp;

}

}

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

std::cout << "key: " << array[i].Key << " line: " << array[i].Line << "\n";

std::cout << "\n"*/

}

int searchT(Record* array, int n, int key)

{

int compareNum = 0;

int i = 0;

while (array[i].Key < key)

{

++compareNum;

++i;

}

std::cout << "Algorithm T has finished his work. Number of compares: " << compareNum << "\n";

if (key == array[i].Key)

return i;

else

return -1;

}

int searchB(Record* array, int n, int key)

{

int left = 0, right = n - 1, result = n / 2, compareNum = 0;

while (array[result].Key != key)

{

if (key > array[result].Key)

{

left = result;

++compareNum;

}

else

{

++compareNum;

right = result;

}

if (left == right)

{

++compareNum;

std::cout << "Algorithm B has finished his work. Number of compares: " << compareNum << "\n";

return -1;

}

result = (right - left) / 2 + left;

}

std::cout << "Algorithm B has finished his work. Number of compares: " << compareNum << "\n";

return result;

}

int main()

{

int n;

std::cout << "Specify array size: ";

std::cin >> n;

Record* array = new Record[n];

rndDataNoRepeat(array, n);

std::cout << "Specify key is need to find: ";

int key;

std::cin >> key;

int result;

result = searchS(array, n, key);

std::cout << "Result of S: ";

if (result == -1)

std::cout << "not found\n";

else

std::cout << result << "\n";

result = searchQ(array, n, key);

std::cout << "Result of Q: ";

if (result == -1)

std::cout << "not found\n";

else

std::cout << result << "\n";

sort(array, n);

std::cout << "Array has sorted\n";

result = searchT(array, n, key);

std::cout << "Result of T: ";

if (result == -1)

std::cout << "not found\n";

else

std::cout << result << "\n";

result = searchB(array, n, key);

std::cout << "Result of B: ";

if (result == -1)

std::cout << "not found\n";

else

std::cout << result << "\n";

std::cout << "\n";

system("pause");

}

Результат работы программы

Specify array size: 16

key: 29 line: Some text 10

key: 5 line: Some text 1

key: 28 line: Some text 9

key: 23 line: Some text 7

key: 21 line: Some text 6

key: 19 line: Some text 5

key: 13 line: Some text 3

key: 2 line: Some text 0

key: 26 line: Some text 8

key: 43 line: Some text 15

key: 18 line: Some text 4

key: 41 line: Some text 14

key: 36 line: Some text 12

key: 9 line: Some text 2

key: 37 line: Some text 13

key: 32 line: Some text 11

Specify key is need to find: 18

Algorithm S has finished his work. Number of compares: 20

Result of S: 10

Algorithm Q has finished his work. Number of compares: 10

Result of Q: 10

Array has sorted

Algorithm T has finished his work. Number of compares: 4

Result of T: 4

Algorithm B has finished his work. Number of compares: 1

Result of B: 4

Сравнительный анализ

Ключ Несортированный массив Отсортированный массив
S Q T B

Вывод

Алгоритмы поиска широко используются в программировании. Выбор конкретного алгоритма сильно зависит от того, какие данные предоставляются для поиска. В случае несортированного массива данных возможен только последовательный поиск (S и Q). Для самых быстрых алгоритмов поиска требуется отсортированный массив данных. Сортировка даёт возможность утверждать о том, какие элементы расположены слева и справа друг от друга и пользоваться этим знанием.

Самый быстрый из алгоритмов S, Q, T и B - последний. Он быстр, потому что перебирает не все элементы, а бесконечно сужает область поиска, пока она не уменьшится до одного элемента — искомого.

Наши рекомендации