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

таблетка в томске ру

Поиск в таблице - часть 2


В последующем алгоритме поиска отдается предпочтение первой схеме. В этом случае сравнение строк выполняется так:

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]) фиксирует совпадение}




Начало  Назад  Вперед



Книжный магазин