Главная » 1С Предприятие » ПОИСК ДАННЫХ

0

Поиск  данных в  векторе  и  файле  выполняется по  ключу.   Как  и  при  сортировке, выделяют  два метода  поиска:  внутренний  и  внешний.  В первом  случае  весь файл  находится в  отведенной   под  программу памяти  ЭВМ.   В  случае  внешнего  поиска  большая часть данных находится во внешней  памяти, например на жестком диске.

Рассмотрим  внутренний поиск применительно  к одномерному массиву.

Предположим,  что  х   это   вектор,  содержащий   п  ключей.  Пусть   key  является аргументом  поиска, то  есть  искомым  значением  ключа.  Сформулируем  задачу  поиска: установить в  переменную search  наименьшее  целое  число i такое,  что  x[i] = key,  если такое  i существует, и нуль в противном случае.  (При такой постановке  задачи нижняя граница массива х должна  быть  больше  нуля.)

9.2.1.  ПОСЛЕДОВАТЕЛЬНЫЙ ПОИСК

Последовательный поиск является  простейшей формой поиска.  В  представленной формулировке запись фрагмента поиска тривиальна:

перем х[20], нашел, ключ, ин, п;

<здание значений вектора х и переменной ключ>

n = 20; нашел = 0; ин= 1;

пока (ин <= п) и (нашел = 0) цикл если х[ин] = ключ тогда

нашел = ин;

конецЕсли;  ин = ин+1 ; конецЦикла // пока;  если нашел = 0 тогда

Сообщить("Ключ не найден."); иначе

Сообщить("Искомый элемент имеет в векторе x номер " + Строка(нашел)); конецЕсли;

Эффективность   последовательного  поиска  оценим  из  предположения,  что  аргумент  поиска может  равновероятно  располагаться в любой  позиции  массива.  Подсчитаем среднее  число сравнений  вида х[ин]  = ключ,  необходимых  для  завершения  поиска. Если  аргумент  является  первым  элементом  массива,  то  необходимо   одно  сравнение; если последним, то необходимо  и  сравнений. То есть среднее  число сравнений для успешного поиска составит (n + 1)/2.   А в  случае  неуспешного п.  В любом  случае  вычислительная  сложность алгоритма  последовательного поиска равна 0(п).

Область  применения последовательного поиска поиск в  неупорядоченных массивах (файлах).  Если  же  данные упорядочены, то  следует  применять  бинарный   поиск, имеющий и иное название дихотомия.

Источник: Бартеньев О. В. 1С:Предприятие:  программирование для  всех.  Базовые объекты и расчеты на одной дискете. М.: Диалог-МИФИ, 2005. 464 с.

По теме:

  • Комментарии