АвтоАвтоматизацияАрхитектураАстрономияАудитБиологияБухгалтерияВоенное делоГенетикаГеографияГеологияГосударствоДомДругоеЖурналистика и СМИИзобретательствоИностранные языкиИнформатикаИскусствоИсторияКомпьютерыКулинарияКультураЛексикологияЛитератураЛогикаМаркетингМатематикаМашиностроениеМедицинаМенеджментМеталлы и СваркаМеханикаМузыкаНаселениеОбразованиеОхрана безопасности жизниОхрана ТрудаПедагогикаПолитикаПравоПриборостроениеПрограммированиеПроизводствоПромышленностьПсихологияРадиоРегилияСвязьСоциологияСпортСтандартизацияСтроительствоТехнологииТорговляТуризмФизикаФизиологияФилософияФинансыХимияХозяйствоЦеннообразованиеЧерчениеЭкологияЭконометрикаЭкономикаЭлектроникаЮриспунденкция

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

Читайте также:
  1. IV. Далее в этой лабораторной работе необходимо создать и сохранить запрос для отображения средних цен на все товары по таблице «Товары».
  2. Алг «поиск минимума»
  3. Алгоритмы поиска дефектов
  4. Бодрствование в поисках знания
  5. В ПОИСКАХ АЛЬТЕРНАТИВ
  6. В поисках гуманной смерти
  7. В поисках духовного просветления
  8. В поисках единицы перевода. «За» и «против»
  9. В ПОИСКАХ ЛУЧШЕГО ПУТИ
  10. В поисках новых объяснительных понятий
  11. В ПОИСКАХ СНОВИДЦА
  12. В поисках сновидца.

Поиск в массиве иногда называют поиском в таблице, особенно если ключ сам является составным объектом, таким, как массив чисел или символов. Часто встречается именно последний случай, когда массивы символов называют строками или словами. Строковый тип определяется так:

String = array[0..М√1] 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 √ фактические символы строки, а s0 = Chr(M). Такой прием имеет то преимущество, что размер явно доступен, недостаток же в том, что этот размер ограничен размером множества символов (256).

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

i:=0;

while (x[i]=y[i]) and (x[i]<>00h) do i:=i+1

Концевой символ работает здесь как барьер.

Теперь вернемся к задаче поиска в таблице. Он требует ⌠вложенных■ поисков, а именно: поиска по строчкам таблицы, а для каждой строчки последовательных сравнений √ между компонентами. Например, пусть таблица 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]) фиксирует совпадение}


1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 | 20 | 21 | 22 | 23 | 24 | 25 | 26 | 27 | 28 | 29 | 30 | 31 | 32 | 33 | 34 | 35 | 36 | 37 | 38 | 39 |

Поиск по сайту:



Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. Студалл.Орг (0.004 сек.)