Файл: Зубов В.С. Математическое обеспечение цифровых вычислительных машин и систем учеб. пособие.pdf

- / t s -

J -M мес-те; B f jh * ja t s e

; щ ф

. l

x * S £ * & J J f u

°еп с / увеличения номера

позиции для

очередной записи с та­

ким же

значением ключа

e n d c o u n i e i s o i 'k

5.

Процедура дихотомического поиска в списке типа А

по совпадению,интервалу и близости

В числе параметров процедуры -

поисковые о б р а з ы /^ и

po2t

которые для поиска по

интервалу

соответствуют наибо­

ческого

параметра, ооответствуицего формальному параметру :

1

-

поиск по совпадению (вариант I :

отыокиваютоя вое

записи,

удовлетворяющие условию поиска)

или интервалу;

2

-

поиок по оовпаденшо (вариант 2 , достаточно найти .

одну

такую запись);

3

-

поиок по близости "сверху^

4

-

поиок по близости "снизу";

5 -

поиск по близости модулей поискового образа и клю­

приобретает значение f a & e

параметр В .

В теле процеду­

ры все разновидности имеют

общее начало -

отыокание верхней

границы к ( запись о номером

к

минимальна из записей, нахо­

Для разновидности I определяется нижняя граница

результатом поиска

являются все записи о

номером С ,

для ко­

торого справедливо

k>L>J- , если к

=

1 , искомых запи­

сей нет. Для разновидности 2 проверяется,

не соответствует

ли верхней границе- I -я запись списка

и соответствует

ли по­

p ro c e d u re

sea'zch

(/V )

наибольший ключ записи: (poj.)

наименьший ключ:{poi) массив записей:( Z )

их число:(/Z )

искомая верхняя граница:(А ')

ншшяя гр а н и ц а :^ )

результативность поиска: ( б ) ; u ite p e г

N .p o i poZ .n. k . j ;

a x i a y

z :

B ooiecm

В :

>

Begin

cnBepez

sm'fc/r /?.= mi,M2,M3,M4,M5;

/?

:= tzz/e

;

i ;

ki=rt+ I;

fo x

i-.= (J+ k)*2

whiBel<k'c/o

( / Z[i]^poiihenj •,=[+!

eBse k\=L •

* go to

ftf/vh

white

m<J afo

MI:

m:=

0;

joi L\- {flhj)+2 +1

i f po2*s Z [i] then'

J

: =

i - i

eBse m\= i ;

/£.к-J

= I ihen_B>'.= daBse

;

M7;

М2: i £ _ /=

I

then B:= daBse eBse ifz[k-1] jpoliheg

В := faBse -. goto

M6;

М3: _г^£

В :=

BoBse

;

M7;

M4: ££. / - = /

-then &:=

,-MBse

g o t o

M6;

M5: 7 /

aBs (

p o i-zrk l) >aBs iDQl-7/к-П )

-then

М б :

k\= к- I ;

M7:

g/yy/ search

- I I S -

Л И Т Е Р А Т У Р А

1.

Шрейдер Ю.А., Равенство, сходство, порядок,

М ., "Нау­

ка", 1971,

2.

Хопгуд Ф ., Метода компиляции, лер. с англ.,

"Мир",

1972.

3.

Лалернов А .А ., Поднмов В .Я ., Упорядочение информация

ских работ, МЭИ, М.,

1970.

5. Гаврилова Т.Л. О структурном

анализе вьетнамского тек­

ста и одном способе записей

его результатов , "Пробле­

мы кибернетики", вып.13,

М,,

1965. .

дительности алгоритмов внешней сортировки, использующих

методы-разделения, "Кибернетика", ft I , 1969.

7.

Селетков С .Н ., Волков Б .Г ., Хранение и поиск данных в

*

ЭВМ, М., "Советское радио", 1971.

8 .

Лавров С .С ,, Автоматическая обработка данных,хранение

информации в памяти ЭВМ, М ., "Наука", 1971.

-

1 1 6 -

Стр

ГЛАВА I I I .

ИНФОРМАЦИОННЫЙ ПОИСК.

§1. Понятие информационного поиска и его связь с понятия­

ми упорядочения и о®ртировки

...................................

........

.

.52

§2. Классификация условийинформационного

поиска . .

ф

§3. Классификация фундаментальных средств информационного

поиска .

.

.

.

.

.

.

.

.

.

.

.

.

90

§4. Поиск в структурах,представленныхспискомтипа А .

96

§5. Использование при поиске средств адресного программи­

рования ..........................................................................................................

ЮЗ

ПРИЛОЖЕНИЕ .

108.

ЛИТЕРАТУРА...................................................................................................

115,