Задачи поиска в структурах данных
Структуры и алгоритмы обработки данных
2. Задачи поиска в структурах данных
Одно из наиболее часто встречающихся в программировании действий v поиск. Существует несколько основных вариантов поиска, и для них создано много различных алгоритмов. При дальнейшем рассмотрении делается принципиальное допущение: группа данных, в которой необходимо найти заданный элемент, фиксирована. Будет считаться, что множество из N элементов задано в виде такого массива
a: array[0..Nv1] of Item
Обычно тип Item описывает запись с некоторым полем, играющим роль ключа. Задача заключается в поиске элемента, ключ которого равен заданному аргументу поиска¦ x. Полученный в результате индекс i, удовлетворяющий условию а[i].key = x, обеспечивает доступ к другим полям обнаруженного элемента. Так как здесь рассматривается, прежде всего, сам процесс поиска, то мы будем считать, что тип Item включает только ключ.
