Поиск в таблице
Поиск в массиве иногда называют поиском в таблице, особенно если ключ сам является составным объектом, таким, как массив чисел или символов. Часто встречается именно последний случай, когда массивы символов называют строками или словами. Строковый тип определяется так:
String = array[0..Мv1] of char
соответственно определяется и отношение порядка для строк x и y:
x = y, если xj = yj для 0 face="Symbol" =< j < M
x < y, если xi < yi для 0 face="Symbol" =< i < M и xj = yj для 0 face="Symbol" =< j < i
Для того чтобы установить факт совпадения, необходимо установить, что все символы сравниваемых строк соответственно равны один другому. Поэтому сравнение составных операндов сводится к поиску их несовпадающих частей, т. е. к поиску на неравенство¦. Если неравных частей не существует, то можно говорить о равенстве. Предположим, что размер слов достаточно мал, скажем, меньше 30. В этом случае можно использовать линейный поиск и поступать таким образом.
Для большинства практических приложений желательно исходить из того, что строки имеют переменный размер. Это предполагает, что размер указывается в каждой отдельной строке. Если исходить из ранее описанного типа, то размер не должен превосходить максимального размера M. Такая схема достаточно гибка и подходит для многих случаев, в то же время она позволяет избежать сложностей динамического распределения памяти. Чаще всего используются два таких представления размера строк:
Размер неявно указывается путем добавления концевого символа, больше этот символ нигде не употребляется. Обычно для этой цели используется непечатаемый¦ символ со значением 00h. (Для дальнейшего важно, что это минимальный символ из всего множества символов.)
Размер явно хранится в качестве первого элемента массива, т. е. строка s имеет следующий вид: s = s0, s1, s2, ..., sM-1. Здесь s1, ..., sM-1 v фактические символы строки, а s0 = Chr(M). Такой прием имеет то преимущество, что размер явно доступен, недостаток же в том, что этот размер ограничен размером множества символов (256).
В последующем алгоритме поиска отдается предпочтение первой схеме. В этом случае сравнение строк выполняется так:
i:=0;
while (x[i]=y[i]) and (x[i]<>00h) do i:=i+1
Концевой символ работает здесь как барьер.
Теперь вернемся к задаче поиска в таблице. Он требует вложенных¦ поисков, а именно: поиска по строчкам таблицы, а для каждой строчки последовательных сравнений v между компонентами. Например, пусть таблица T и аргумент поиска x определяются таким образом:
T: array[0..N-1] of String;
x: String
Допустим, N достаточно велико, а таблица упорядочена в алфавитном порядке. При использовании алгоритма поиска делением пополам и алгоритма сравнения строк, речь о которых шла выше, получаем такой фрагмент программы:
L:=0; R:=N;
while L<R do begin
m:=(L+R) div 2; i:=0;
while (T[m,i]=x[i]) and (x[i]<>00h) do i:=i+1;
if T[m,i]<x[i] then L:=m+1 else R:=m
end;
if R<N then begin
i:=0;
while (T[R,i]=х[i]) and (х[i]<>00h) do i:=i+1
end
{(R<N) and (T[R,i]=x[i]) фиксирует совпадение}
