Результат работы программы
Алгоритмы поиска
Выполнена Затеваловой М.А.
Проверил Силаев А.В.
Задание
Вариант
Блок-схемы
Код программы
#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 - последний. Он быстр, потому что перебирает не все элементы, а бесконечно сужает область поиска, пока она не уменьшится до одного элемента — искомого.