Эвристический поиск элементов в массиве
Предположим" имеется приложение, которое использует такой массив,
который нельзя отсортировать (например, приложение добавляет слишком часто
в массив новые данные), но можно переставить несколько элементов массива. Как
улучшить поиск в таких несортируемых массивах? Необходимо использовать метод
эвристического поиска. Этот метод перемещает значение найденного элемента массива
по одной из следующих схем.
* Переместите найденное значение в первый элемент массива. В этой схеме
предполагается, что значение перемещенного элемента будет отыскиваться во
время следующего поиска.
* Поменяйте найденное значение с его соседом с более низким индексом. В этой
схеме предполагается, что значение перемещенного элемента будет
отыскиваться во время следующего поиска. Значение, которое отыскивается
неоднократно, передвигается вперед в массиве. (Другими словами, то
значение, которое ищут чаще всего, как бы всплывает" к началу массива.)
* Переместите найденное значение в последний элемент массива. В этой схеме
принимается, что, вероятнее всего, в следующих поисках не будет
отыскиваться значение перемещенного элемента.
Рассмотрим пример программирования. В примере содержится исходный текст
программы, которая иллюстрирует эвристический метод поиска. Программа выводит
неотсортированные элементы объекта Array, а затем четырежды - результаты поиска
значения 38 в объекте Array. После каждого поиска, программа выводит новый
порядок элементов в объекте Array.
В примере объявлен класс myArray. В новой версии класса myArray объявлена
функция-член heuristicSearch, которая осуществляет эвристический поиск.
В определении функции-члена heuristicSearch используется цикл for для
исследования элементов массива в диапазоне индексов от nFirst до nLast. В цикле
используется оператор if для сравнения аргумента поиска с элементом m_nArray[i].
Если два этих значения совпали, оператор if выполняет оператор break, чтобы
прекратить поиск. Функция-член меняет местами найденный элемент массива с
соседним элементом с более низким индексом (если найденный элемент не первый
элемент в массиве). Функция возвращает индекс найденного элемента или выдает
значение глобальной константы NOT_FOUND, если соответствующее значение не
найдено.
Функция main объявляет и инициализирует массив C++ nArr. В ней также
объявлен объект Array как экземпляр класса myArray. Затем функция main решает
следующие задачи.
* Копирует значения в массиве nArr в объект Array. В этой задаче исполь-
зуется цикл for для перебора элементов массива nArr.
* Выводит первоначальные неотсортированные элементы в объекте Array,
посылая ему сообщение С++ show. Аргумент этого сообщения - строка-литерал
"Initial heuristic array is:".
* Осуществляет поиск значений в nArr[nLast] четыре раза, используя цикл for.
В каждой итерации цикла выводится аргумент поиска, а затем посылается
сообщение С++ heuristicSearch объекту Array. Аргумент этого сообщения -
аргумент поиска nArr[i]. Цикл присваивает результат сообщения переменной j.
Чтобы определить, был ли поиск успешным, в цикле используется оператор if.
Если да, - программа выводит индекс найденного элемента массива. Последний
оператор цикла выводит новый порядок элементов в объекте Array, посылая ему
сообщение С++ show. Аргумент этого сообщения -
строка-литерал "Heuristic array is: ".
Содержание