Programmirovanie_i_osnovyi_algo

return/

//Бинарный (логарифмический) поиск в таблице, подготовленной

//в форме алфавитно-упорядоченного двоичного дерева

//Подготовка к поиску found = 0; EndTab = 0;

//Поиск

i = 1;

while ( ! found && .'EndTab )

{

±f( !strcmp( Keyword, pTable[ i-1 ] . key ) )

{//Нашли

found = 1; line = i-1;

}

else

{//Шаг вперед по таблице

±f( strcmp( Keyword, pTable [ i-1 ] , key ) < 0 )

{

i = 2*i/

}

300

301

}

//Ключ

char

302

}

}

//Открытие файла для чтения

//Закрытие файла ввода

геЬмтсп;

303

}

//Подготовка к поиску

found = О; EndTab = О; i = Hash( KeyWord ) ;

//Поиск в таблице

while ( ( .'found ) && ( .'EndTab ) )

{

}

else

{// Шаг no таблице

}

}

}

retujni/

304

17.3. Логарифмический (бинарный) поиск

Кардинальное повышение эффективности поиска в таблице достигается полным пересмотром алгоритма поиска аналогично то­ му, как это было ранее в сложных алгоритмах сортировки массивов.

Пример. В реальных словарях, например в англо-русском сло­ варе, человек быстро находит нужные сведения, используя их упо­ рядоченность по алфавиту. Указанный подход и использован при

305

логарифмическом (с помощью двоичного дерева) поиске в таблице. Если исходную таблицу (словарь) предварительно подготовить

в форме двоичного дерева так, чтобы ключи левого поддерева были раньше по алфавиту, чем ключ корня, а ключи правого поддерева - позже, то число обращений к таблице для сравнения с заданным ключевым словом не может превышать log^isize). При этом, после каждого обращения к таблице, область поиска сокращается в общем случае примерно в два раза.

Начальная подготовка таблицы в форме двоичного дерева.

Исходные данные при заполнении таблицы перед чтением должны быть упорядочены по алфавиту для ключевых слов. Это легко обес­ печить, используя рассмотренные выше способы сортировки масси­ вов.

Пусть, например, читаемые данные содержат в каждой отдель­ ной строке информацию для заполнения одной строки таблицы, причем они отсортированы по ключам по не убыванию (size=\0):

Двоичное дерево строится, как это было ранее рассмотрено, с использованием рекуррентного подхода (см. рис. 57). Для нашего примера после начальной подготовки двоичное дерево должно иметь вид, показанный на рис. 98.

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

1. Исходный ключ сравнивается с ключом, соответствующим корню дерева (номер соответствующей вершины дерева / = 1, а ин­ декс элемента массива - (/ - 1) ). Если при этом ключи совпадают, то нужная строка найдена {found = 1), ее индекс line = i - 1 и поиск за-

306

вершен.

Среднее слово по алфавиту (G) присваивается корню.

Аналогично заполняются левые и правые поддеревья для частичных корней

Рис. 98. Двоичное дерево после начального заполнения

2. Если поиск не завершен, то определяется поддерево для продолжения поиска путем сравнения KeyWord < рТаЫо[ /-1 ].кеу. При положительном итоге необходимо вести поиск в левом подде­ реве и номер следующей вершины / = /*2. При выполнении же про­ тивоположного условия KeyWord > рТаЫе[ /-1 ].кеу, поиск следует вести в правом поддереве и номер следующей вершины дерева / = /*2+1.

3. При выполнении условия i > size (вершину / дерево не со­ держит) поиск следует прекратить, так как строка с ключевым сло­

раза и среднее число обращений к таблице (средняя длина поиска) составляет 1^^.,, =\og^{size), что существенно эффективнее, чем при по­ следовательном поиске.

307

в соответствии со сказанным, прототип, определение функции LogariphmSearch и пример ее вызова имеют вид, показанный в про­ грамме из подразд. 17.2.

17.4. Поиск с использованием перемешанной таблицы (хэш-таблицы)

при поиске с использованием хэш-таблицы используется ор­ ганизация данных в виде массива. Основная идея поиска состоит в преобразовании заданного ключа Key Word в индекс Hash( Key Word ) соответствующей строки в таблице. Поэтому такой способ поиска иногда называют поиском с преобразованием ключей (рис. 99).

рТаЫе

Рис. 99. Хэш-поиск в таблице

Основная трудность преобразования ключей состоит в том, что множество возможных значений ключей намного обширнее, чем множество индексов строк в таблице. Так, например, если ключ со­ держит восемь символов, в качестве которых используются строч­ ные латинские буквы, цифры и пробел (всего 37 возможных значе­ ний каждого символа в ключе), то всего имеется 37^ возможных значений ключей, что, естественно, во много раз превышает реаль­ ный размер таблицы size. Из сказанного следует, что функция Hash является отображением "много в один".

Идея поиска с использованием хэил-таблицы состоит в сле­ дующем. Первый этап в операции поиска - вычисление соответст­ вующего индекса Hash{ KeyWord ) в таблице, а второй - очевидно необходимый этап - проверка, действительно ли элемент с ключом KeyWord находится в таблице в строке с индексом Hash( KeyWord ).

При этом сразу же возникают два вопроса.

308

1. Какую функцию Hash( KeyWord ) следует использовать?

2. Как поступать в ситуации, когда функция Hash{ KeyWord ) не дает местонахождения нужного элемента (! много ключей дают одинаковый индекс)?

Ответ на второй вопрос заключается в том, что нужно исполь­ зовать какой-то метод для получения нового индекса в таблице, а если и там нет нужного элемента, то следующего индекса и т.д. По­

чтобы она распределяла ключи как можно более равномерно по шкале значений индексов. Разумеется, она должна также эффектив­ но вычисляться, т.е. состоять из очень небольшого числа основных арифметических действий.

Пусть ih определяет порядковый номер ключевого слова KeyWord во множестве всех возможных значений ключей и вычисляется следующим образом:

{

ih = ih * 37 + Kod( KeyWord[ IKey ] ) ;

}

ih = ih % size;

Врезультате вычислений ih получает значение из диапазона 0-

36.К сожалению, величина ih существенно превышает максимально допустимое целое значение (2'^-1 или 2^'~1). По этой причине функцию Hash{ KeyWord ) следует построить несколько иначе — вы­ числение

ih = ih % size;

перенести в блок цикла. Прототип полученной таким образом хэшфункции и ее определение приведены в примере программы в подразд. 17.2. Функция Hash{ KeyWord ) также является вспомогатель­ ной и используется при хэш-поиске. Эта функция обладает тем свойством, что значения ключей равномерно распределяются во всем интервале индексов строк таблицы. Исследованиями показано, что для большей равномерности распределения желательно, чтобы

309