Эвристический поиск элементов в массиве

Предположим" имеется приложение, которое использует такой массив, который нельзя отсортировать (например, приложение добавляет слишком часто в массив новые данные), но можно переставить несколько элементов массива. Как улучшить поиск в таких несортируемых массивах? Необходимо использовать метод эвристического поиска. Этот метод перемещает значение найденного элемента массива по одной из следующих схем. * Переместите найденное значение в первый элемент массива. В этой схеме предполагается, что значение перемещенного элемента будет отыскиваться во время следующего поиска. * Поменяйте найденное значение с его соседом с более низким индексом. В этой схеме предполагается, что значение перемещенного элемента будет отыскиваться во время следующего поиска. Значение, которое отыскивается неоднократно, передвигается вперед в массиве. (Другими словами, то значение, которое ищут чаще всего, как бы всплывает" к началу массива.) * Переместите найденное значение в последний элемент массива. В этой схеме принимается, что, вероятнее всего, в следующих поисках не будет отыскиваться значение перемещенного элемента. Рассмотрим пример программирования. В примере содержится исходный текст программы, которая иллюстрирует эвристический метод поиска. Программа выводит неотсортированные элементы объекта 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: ".

Содержание