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

procedu re

I Z M 3 ( гг)

записей:( Z )

цепной описок:(А1) его

фиксатор: ( / я / ) ;

in te g e r

n .'- fn h

a r z a g

Z

;

'

Integer

a r ia у

Ah

A2 ;

integer J n2. i,/\ & •

Begin

integer

azzag

J ,

: = / / ? / ;

J o z

/ Ы I s te p

1 u n t ie

(/?-1 )

Vo_ S ep in

A 2 [A i[jll i - J ;

1'.= А 1ф e n d

построения^ встречного

цепного

списка А2

с фиксатором fh Z 3 J-n2x=g

;

J

' - f a t »

/от / r : = i

step

1 unii t

п do

Begin

геаВ г ;

г -.-ZiK7; Z[kb=Z[j]; Z [J]i-

г ; comment предыдущие 3

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

- й записи i-a/f-ю

позицию формируемого списка

типа_А;

М:

i

:=

A i[ g l\

A

i [ j ] := A t [ к ]

;A 1[A 2 [ к ] ]

;

c o m m e n t

предыдущие

2

оператора отражают переключения в

исходном,

а следующие

2

оператора - во

встречном

списке,

отражающие изменение

позиции записи,

перешедшей с к -й на ^ /-ю

позицию;

А 2$]:=А 2[1<}, A 2[A 1[K U -=J

; J

: = i

;

c o m m e n t

продви­

жение по цепочке, см.также

оператор с меткой М;

e n d од­

ного

замещения

записей

e n d

i z М 3 -

г ) Оператор "Дихотомический описок -

односвязный цеп­

ной

список"

integer

п ; integer a rra y

AL,

АР;

Begirt

Boolean

arza g

В [l\rij\

comment элемен­

ты массива АО представляют адреса

"обратной связи" в ди­

хотомическом списке;

integer

i

, J >к ; com m ent i -

носвязный список к некоторому моменту; integer

arrop

АО[lift]; comment

массив В необходим для различения

элементов уже включённых в односвязный список от ещё не

включённых, следующий оператор приводит его к исходному

состоянию;

к°г i :=I

step I a n tiВ п do B[i}.= -faUse ;

J:=Q; comment это

означает, что отправной точкой служит

корень; MI; I %=/ ;

comment далее осуществляется переход

по

правому адресу

(вначале - от фжеатора к корню)

и если

он

не пуст,

то затем ври переходе по цепочке 'по индексу^)

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-й

и у -й

записей,

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

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

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