Структуры и алгоритмы обработки данных

       

Задачи поиска в структурах данных


Структуры и алгоритмы обработки данных

2. Задачи поиска в структурах данных

Одно из наиболее часто встречающихся в программировании действий v поиск. Существует несколько основных вариантов поиска, и для них создано много различных алгоритмов. При дальнейшем рассмотрении делается принципиальное допущение: группа данных, в которой необходимо найти заданный элемент, фиксирована. Будет считаться, что множество из N элементов задано в виде такого массива

a: array[0..Nv1] of Item

Обычно тип Item описывает запись с некоторым полем, играющим роль ключа. Задача заключается в поиске элемента, ключ которого равен заданному аргументу поиска¦ x. Полученный в результате индекс i, удовлетворяющий условию а[i].key = x, обеспечивает доступ к другим полям обнаруженного элемента. Так как здесь рассматривается, прежде всего, сам процесс поиска, то мы будем считать, что тип Item включает только ключ.



Содержание раздела