книги из ГПНТБ / Зубов В.С. Математическое обеспечение цифровых вычислительных машин и систем учеб. пособие

ki=APrf]i

М k &

then

Bep in

Л\2-.A0[k} .= J

\ J * = k \

t £ A L lJli

0

th en ’ B e g in

к := A L fjh

$Q to

№

e/7<^

пере­

хода по цепочке левых;

М3\A L [i] \ - j

;

com m en t предыдущий

оператор включает очередной элемент в

односвязный

список,

а последующий фиксирует этот факт;

tr u e ;

9 °

to Ml

e n d перехода к

зайоминанлю места вынужденного

перехода

в цепочке по правому адресу, следующие 2 оператора реали­

зуют возврат по цепочке к первому попавшемуся элементу,

ещё не учтённому в

односвязном

списке;

Ш \ Ji~ A 0 jj]\

/£ BQ] the/,'

poto М4;

i£ AO[J,J Ф o then ро % №

e n d IZM4 при возврате

к фиксатору

2 .

Процедура простейших алгоритмов упорядочения

(в дополнение к § 2 гл. П)

a) p ro c e d u re

вставка ( Л )

записей:(-Z ) -.onauZ. ; integerп:

Begin

in te g e r

L

r e n t z ;

com m ent внешний цикл -

по включаемым записям,

вложенный цикл -

поиск места

вклю­

чения записи;

/ о г

/:=

2

ste p

I

u n tii /у

do

B ep in

-fo r j

;= i - 1

ste p

- I

u n tie

l

d o

i f z d l^ z itlth en

gotolk,

M: Z := Z C iJi

s te p

- I

u n tiB j

+ I

do

Z [к + I j:= 2 fk j ;

com m ent предшествующий

оператор осущест­

последующий -

размещает новую запись на освобождённую тем

самым позицию,^ fj +l] := 7

e n d

включения очередной записи

e n d вставки

б) p ro c e d u re

пузырёк ( / ? )

записей: (Z ) ;

a r r a p Z ;

in te g e r п ;

co m m e n t

П -

асло записей;

B eg in in te g e r

L . J i

r e a d

z ; co m m e n t

во внешнем

версии, ибо за один её просмотр экстремальная

запись з о н ы

занимает заведомо окончательное положение;

f o e j := n ste p - I u n t ie 2 <fo B egin 7 \=ZCG\

com m ent

e£se

Begin

:= Z ;

M: Z : = Z [ i ]

e n d перехода к новой

"всплывающей"

записи; 2 [jj:~ Z ;

com m ent установка на

окончательное

место

экстремальной

записи;

e n d просмотра

зоны

e n d

пуэырька

3 .

Оператора оптимального

объединения внутренне

упо­

рядоченных сегментов (а )

и разделения на взаимно упорядо­

ченные

сегменты (б )(в дополнение к

§ 3 гл.П )

а)

ргосес/ап е

m ezp e (Z3)

число:in ?)

записей b : ( z 2 )

число:(/*?)

записей в : ( 2 У ) : in te p e z т ,

П ; a z z a j/Zf.Z2,Z3}

com m en t 2 3 - результирующий сегмент;

B egin

in te o e z

i tp

i ;

J o i^ k \= i

s t e p

i

u n t i t n V m d o в е р in

I / i> n / h en n o to d :

a / J > m

‘th en

p o to M : com m ent эти условные операторы

необходимы для обхода следующего оператора сопоставления

записей, если

один из

сегментов 21 t2 2 исчерпался;

i £ z i [ i ] < Z 2 [ p J th en

м '.Begin

Z 3 [k ]\= z -i[i] ; /: =

£+ le n d

выталкивания магазина Z i

e £ se

d :

Bep/n

Z 3 [t]\=

Z2fy'J\

I»

^ n d выталкивания магазина Z 2 e n d включения оче­

редной'записи

в магазин 2 3 e n d т е ? р е

б) p z o c e d u z e so z /d iB B a id (Z )

нижняя грань; (<7) верх­

няя грань:{ & ) ; L n /e o e z

а . в :

a z z a t/Z

; с о т т е л / Z

-

разделяемый сегмент записей;

Bepin _ infeyeг

rent г: zW j^/W ; i^ Z fih

магазинав

"нижний", если она инверсна с опорной 1 ;

М 2

: / : = / -

1 ; $ °

У

^he/г

M I

e£se М 5 ;

М3:

if_ Zfij>Z then

Be#in Z [j]\-Z C H :

g o to

М2 e n d :

- т -

4 .

Примеры алгоритмов отобразительного упорядочения

(в дополнение к § 4 гл П)

а) Упорядочение неповторяющихся кодов через отображе­

ние на двоичный вектор В.

(ft) записей: (Z. ) разрядность

procedure

S it so rt

их ключей: (A ’ ) ;

integer arrapZ',integernfo Sepln Boolean

cnraigBBPtkbintepeZi ,J - ; fo r / : = I step 1 u n til

2f кdo

-false j

comment

элементы вектора В со значением

tr u e

будут

соответствовать

значениям,

вотретивишмся в Z. ;

jo 7 I ;= I

stepi

until /7

do_

true ;

comment

выполнена регистрация всех

значений ключей в Z

; J

г= I ;

for L

. 1

step

I

u n til 2rk do j£_ BiOthen

Sepin'

2 ф х ~

L\ j

I

d ftd этим

оператором по вектору В в цик­

ле выполняется''воспроизведение кодов Z

, но уже в упорядочен­

ном описке

типа

A e n d S i t SO T'S

p ro c e d u re

c o u n te rso rt

(П ) записей: ( Z ) разрядность

их ключей:( к ) ;

in te g e r

n . h i

I n te g e r

a r r a y

Z

;

com m ent значение

ключа

будет использоваться как номер

счётчика в векторе S ;

B enin

I n t e g e r

i , J j

in t e g e r

a r r a y

[ u z f k } ,

•

B o o le a n

a r ? a g

C l-.dh

fo r i ?=/

ste p

I u n t i l 2 tk cb_

Sfi]i=

Qi

to r

i:= i

s te p i

u n t i l a

do

8

t r u e

:

com m ent эти

оператора

приводят к исходному Виду вектор S

и в е к то р ^ ,

в котором будет

регистрироваться факт

окончате­

льного установления записи на позицию списка типа А;

fo r / ; = I

s te p i

u n t i l п do s r e f i j j i = . $ [ z [ i jj + i ;

com m ent этот

оператор

подсчитал чиоло

повторений каждого

значения ключа; J '.=pl+l; fo r

/•= 2fk ste p - I

u n t i l

I d o

Begin

S fiJ\= J : _ 7

- S / / 7

e n d замены элемента счётчика

номе­

расстанавливает заш ои;

fo r С := I

s te p

I O n t il П

d o

i f BLil then fo ? J := S [ Z £ i j]

i&fo'lej t /

d p

B eg in

re ali ;

7 := ZC J]', Z lj}.= Z [i]\Z [H

:= 7 ;

com m ent

эти

3 оператора

осуществили обмен местами L-й

и у -й

записей,

следующий опе­

ратор регистрирует факт

окончательного положения записи на

- / 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,