В ниже приведенном примере объявим массив на 50 элементов и заполним его используя генератор случайных чисел rand(). Предложим пользователю ввести искомое значение с клавиатуры и реализуем проверку на наличие этого значения в нашем массиве. Если значение будет найдено в каком-либо элементе массива – выведем на экран индекс этого элемента. Это классический пример. Тяжело и придумать что-то лучшее для демонстрации линейного поиска в C++.
листинг кода
#include "iostream"
#include "iomanip"
#include "ctime"
using namespace std;
//прототипы функций
int linSearch(int arr[], int requiredKey, int size); // линейный поиск
void showArr(int arr[], int size); // показ массива
int main()
{
setlocale(LC_ALL, "rus");
const int arrSize = 50;
int arr[arrSize];
int requiredKey = 0; // искомое значение (ключ)
int nElement = 0; // номер элемента массива
srand(time(NULL));
//запись случ. чисел в массив от 1 до 50
for (int i = 0; i < arrSize; i++)
{
arr[i] = 1 + rand() % 50;
}
showArr(arr, arrSize);
cout << "Какое число необходимо искать? ";
cin >> requiredKey; // ввод искомого числа
//поиск искомого числа и запись номера элемента
nElement = linSearch(arr, requiredKey, arrSize);
if (nElement != -1)
{
//если в массиве найдено искомое число - выводим индекс элемента на экран
cout << "Значение " << requiredKey << " находится в ячейке с индексом: " << nElement << endl;
}
else
{
//если в массиве не найдено искомое число
cout << "В массиве нет такого значения" << endl;
}
return 0;
}
//вывод массива на экран
void showArr(int arr[], int arrSize)
{
for (int i = 0; i < arrSize; i++)
{
cout << setw(4) << arr[i];
if ((i + 1) % 10 == 0)
{
cout << endl;
}
}
cout << endl << endl;
}
//линейный поиск
int linSearch(int arr[], int requiredKey, int arrSize)
{
for (int i = 0; i < arrSize; i++)
{
if (arr[i] == requiredKey)
return i;
}
return -1;
}
Функция выполняющая линейный поиск определена в строках 62-70. Она возвращает в программу -1 в том случае, если значение, которое ищет пользователь, не будет найдено в массиве. Если же значение будет найдено – функция вернет индекс элемента массива, в котором это значение хранится.
результат работы
В случае отсутствия значения в массиве
Посмотрев на первый снимок, вы сразу обратите внимание, что в ячейке с индексом 6 искомое значение найдено и программа завершает работу, хотя в ячейках 23 и 33 этого массива находятся такие же значения. Если вас это устраивает, то индекс первого найденного элемента и будет результатом работы программы. Иначе программу надо дорабатывать, чтобы найти и записать (например в отдельный массив) все индексы ячеек, хранящих искомое число (ключ).
Обычно линейный поиск применяется для одиночного поиска в небольшом массиве, который не отсортирован. В других случаях, лучше и эффективней сначала отсортировать массив и применять другие алгоритмы поиска. Например двоичный (бинарный) поиск либо другие.
2015-06-29 • Просмотров [ 3397 ]