..
..
-
#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 - . , , , .
