Краткая теория

ПОИСК (SEARCH) является одной из основ обработки данных в ЭВМ. Его назначение состоит в том, чтобы по заданному аргументу найти среди массива данных те данные, которые соответствуют этому аргументу или определить, что этих данных нет. Если этих данных нет, добавить их в массив данных.

Набор любых данных будем называть ТАБЛИЦЕЙ или ФАЙЛОМ. Данное или элемент структуры отличается каким-то признаком от других данных. Этот признак называется КЛЮЧОМ. Ключ может быть УНИКАЛЬНЫМ, т.е. в таблице только одно данное с таким ключом, иначе уникальные ключи называются ПЕРВИЧНЫМИ КЛЮЧАМИ.

ВТОРИЧНЫЙ КЛЮЧ в одной таблице может повторяться, но по нему тоже можно организовать поиск. Ключи данных собраны в одном месте (таблице).

Ключи, которые выделены из таблицы данных и организованы в свой файл, называются ВНЕШНИМИ КЛЮЧАМИ. Если ключ в записи, то он называется ВНУТРЕННИМ КЛЮЧОМ.

ПОИСКОМ ПО ЗАДАННОМУ АРГУМЕНТУ называется алгоритм, определяющий соответствие ключа данного с заданным аргументом. Результатом работы алгоритма поиска может быть нахождение этого данного или отсутствие данного в таблице. В случае отсутствия данного возможны две операции:

       1. Индикация того, что данного нет.

       2. Вставка данного в таблицу.

Пусть К - массив ключей, тогда для всех К(i) существует R(i) - данное. KEY - аргумент поиска. Ему соответствует информационная запись REC. В зависимости от того, какова структура данных в таблице, различают несколько видов поиска.

ПЕРЕУПОРЯДОЧЕНИЕ   ТАБЛИЦЫ  ПОИСКА

Всегда можно говорить о некотором значении вероятности  нахождения того или иного элемента.

P(i) - вероятность нахождения элемента.

В этом случае таблица поиска представляется как система с дискретными состояниями, а искомый элемент характеризуется i-ым состоянием системы, вероятность которого P(i).

P(1) + P(2) + ... + P(n) = 1

Количество сравнений Z при поиске в таблице, т.е. количество сравнений, необходимых для поиска по заданному аргументу, представляет собой значение дискретной случайной величины, определяемой номерами состояний и вероятностями состояний системы.

Z=1*P(1) + 2*P(2) + 3*P(3) + ... + n*P(n)

ТАБЛИЦА ДАННЫХ ДОЛЖНА БЫТЬ УПОРЯДОЧЕНА ТАКИМ ОБРАЗОМ , чтобы в начале таблицы были элементы с большими вероятностями поиска или элементы , к которым чаще всего обращаются в таблице.

P(1) >= P(2) >= P(3) >= ... >= P(n)

ИМЕЕТСЯ ДВА ОСНОВНЫХ МЕТОДА ПЕРЕУПОРЯДОЧЕНИЯ ТАБЛИЦ  ПОИСКА:

1.   Переупорядочение путем перестановки  найденного элемента в начало списка.

2.   Метод транспозиции.