Rеje: Ápiwayı kórip shıģıw hám binаr izlew аlgоritmleri 2

Bor strukturası

3-tablica

Belgiler	Túyinler
(_) probel	1	2	3	…	N
					26

5-mısal.
[A, AA,AB,ABC.ABCD, ABC A, ABCC.BOR, С, CC, CCC,

CCCD.CCCB.CCCA)

toplam berilgen.

Dáslebki berilgen toplamnan bor payda qılatugınına ótemiz.

Dáslebki alipbe = {A,B.C.В}

Bor - В haripten baslanıwshı tabiyiy sóz hám ol háripler boyınsha ajralmaydi.

Bor túyinleri hár bir komponenti gilt yaki silkadan (bos bolıwı múmkin) ibarat bolgan vektorları payda qılınadı. (4-tablica).

Bor usılında izlewge mısal

4-tablica

Belgiler	Túyinler
	1	2	3	4	5	6	7
_		A_	AB_	ABC	C_	CC_	CCC_
A	2	AA		ABCA			CCCA
B	BOR	3					CCCB
C	5		4	ABCC	6	7
D				ABCD			CCCD

1 túyin tamır, sol ushın da birinshi haripti usı jerden izlew kerek. Máselen, eger 1 shi В haribi boiıp shıqsa, ol halda jadvaldan ko'rinib turibdiki unga BOR so‘zi mos keladi. Agar 1 chi harf A b o is a , u holda 1 tugun 2 chi harf qidiriladigan 2 tugunga boshqaruvni topshiradi. 2 chi tugun ikkinchi harf_y4, В va hokozolar bo'lishi mumkinligini ko‘rsatadi.

h-Xeshlaw usılnda izlew
Izlew tiykarında dáslebki toplamnan Л-funkciya (h(k) toplamına ótiwdi kirgizedi.

h-funkciya tómendegi kóriniske iye:

(h(k)) = kmod(m),
bul jerde k-kalit; ш-butin san; mod- bóliwdiń butin sanlı qaldıgı.

H-funksiya tómendegi bóliniwge iye bolganlıgı ushın bóliw ámeli járdeminde к giltti birorta m yacheykaga к ni m ga qaldıqlı boliw arqalı tasvirlaydi:

(h (k )) = kmod(m),
Máselen, eger h-tablica m=12 ólshemge, к gilt mánisi k=100 ge iye bolsa , ol halda h(k)=4 boladi. H-funksiyani esaplawda bir bóliniw ámeli jeterli bolganlıgı sebepli, bóliniw usılı arqalı xeshlaw biraz tez ámelge asadı.

Masalan, {9,1,4,10,8,5} tор1ат berilgen bólinsin .

Onıń ushın (h(k)) - kmod(m) h-funksiyani anıqlaymız:

I) m = 1 bolganda

(h(k)) = {0,0,0 0,0,0};
2) m = 20 bolganda

(h(k) ) = { 9, 1, 4, 10, 8, 5};
3) т - eń úlken gilttiń jarımına bólgende m= [10/2]=5

(h(k)) - {4,1,4,0,3,0} boladı.
h-funksiya izlew kerek bolģan manzildi kórsetedi. Túrli giltler ushın

Л-funksiya birdey mánisti qabıl qılıwı múmkin, bunday jaģdayda toqnasıw halatı dep ataladı. Usı túrde A-lı izlew shınjır usulında toqnasıw halatı biytárep etiw menen tawsıladı.(5-suwret).

/

k₁

k₄




/

k₆

/
5-chizma. Shınjır usılında qaqtıģısıw jaģdayın biytárep etiw
6-mısal.

{7,13,6,3,9,4,8,5}

toplam berilgen bolsın. К = 27 gilt tabılsın.

h-funksiya (ft(fc)) = Kmod(m) ga teń;

m = [13/2] = 6 (13)-eń úlken gilt bolģanlıģı ushın)

(h(к)) = {1,1,0,3,3,4.2,5} boladı.

Toqnasıw halatın biytárep etiw 5-tablicanı dúzemiz.

h-funksiyani dáslebki gilt toplamların juplıqları menen salıstırıp, tablicanı toltıiramız. h-funksiya gilt izleniwi kerek bolģan manzilin kórsetiwin esletip ótemiz.

Qaqtıģısıw halatınıń biytárep etiliwi

5-tablica

h(k)	Gilt shinjırları
0	6
1	7,13
2	8
3	3,9
4	4
5	5

Máselen, eger izlenip atırgan gilt К = 11 bolsa, ol halda h{k) = 27mod6 = 3 boladı, bul ese К = 27 gilt tek 3 shi qatarda bolıwın bildiredi. Ol jerda gilt bar bolmasa, dáslebki toplamda da bar emesligin bildiredi.

Interval boyınsha izlew. Bunda shep yaki ońga eń maksimal jaqınlasģan shegara tapıladı. Soń stekti keri tártipte kórip shıģıw jolı menen oń shegaranı izlewmiz, jaqın shep shegaradan úlken yaki teń hám oń shegaradan kishi túyinlerdi izleymiz.

Procedure Obrab(ss.pt);

Begin Write (s.sA. kl:5) End; {imitiruyushaya obrabotku uzlov}

Prosedure Poisk(sor:pt; arl ,ar2:tipkl; l. integer; var pp.pt);

Label 1,2; {si - BDU tuguniga ko'rsatkich sohasi, ssl — stekdagi bog ‘lanish}

Type pn1=Az;

z=Re cord

sl:pt; ssl.pnt End;

Var rr,ss,tt: pt; q,t: pnt;

Procedure Stekln; { BDU tuguniga t ко ‘rsatkichni stekka qo ‘shish}

Begin New(q); q^.sl:= ss; qA.ssI:=t; t:=q End;

Begin pp:= Nil; rr:= Nil; t:— Nil; tl: = sor;

I f I — 3 Then ar2 : =arl;

While tt о Nil do {Iziash jarayoni sikli}

Begin ss: — tt;

IfssA.kl = a rl Thi n {kalitning mos tushish holati}

Begin pp:= ss; Stekln; Goto 1 End;

If s s \k l > arl Then Begin tt:= tt'\ Ison; Stekln End

Else Begin tt:= ttA.rson; rr:= ss End;

End:

I f (I <> 2) And (t <> Nil) Then pp: = tA.sl;

I fl--1 Then pp:= rr;

l:Ifp p <> Nil Then I f I < 3 Then Obrab(pp)

Else I ftA.slA. kl > ar2 Then pp: - Nil

Else {1=3,4: uchun ishning 2-ETAP1}

While t< > Nil do {BDUni chapdan qismiy ко ‘rib chiqish sikli}

Begin q:= t; ss:qtA.sl; t:= t^.ssl; Dispose(q);

Ifss^.kl > ar2 Then Goto 2;{ Ко ‘rib chiqishni tugallash ehtimoli}

Obrab(ss); ss: = ss^.rson;

While ss < > Nil do

Begin While ssA.lson < > Nil do { “'() ‘yinchi ”gacha chapga о ‘tish}

Begin Stekln; ss: = ssA. Ison End;

Ifss^.kl > ar2 Then Goto 2; {Ко ‘rib chiqishni tugallash ehtimoli}

Obrab(ss); ss: = ssA.rson

End

End; {BDU ni chapdan qismiy ко ‘rib chiqish blokining oxiri}

2. While t <> Nil do Begin q:=t; t: =tA.ssl; Dispose(q) End;

End{Binar daraxtda iziash bloki oxiri( BDU)};
Binar terek B-terektiń xususiy halı bolıp esablanadı. M – dárejeli V - terek tómendegi shártlerdi qanaatlandırıwshı ulıwmalıq terek sıpatında anıqlanadı:

1. Hár bir túyin maksimal m-1 ta gilt saqlaydı;

2. Bas(tamır) túyinnen basqa hár bir túyin eń keminde int((m-l)/2) ta gilt saqlaydı;

3. Tamır túyin áwlad bolmasa, eń keminde 2 áwlad túyinge iye;

4. Bárshe áwladlar bir dárejede jaylasģan.

5. Áwlad bolmaģan n giltli túyin p+1 áwladģa iye. Tómendegi suwrette 5-dárejeli V-terek kórsetilgen. Bul jerde hár bir túyin qandayda bir tártiplenen (pi, ki, рг, кг, ..., kn-1, m)topar arqalı kórsetiliwi múmkin.Bul jerde pi kórsetkish (bos kórsetkish berilgen túyin áwlad bolsa) ese qandayda bir gilt. Pi kórsetip atırģan túyindegi giltler ki-1 hám ki arasında jaylasadı. Hár bir túyin ishinde ese

k_i< b< .. ,n-1 teńsizlik orınlanadı.

6 – suwret
Cifrlı izlew terekleri. Izlew procesin tezlestiriw ushın tereklerden paydalanıwdıń basqa usılı giltlerden quralģan simvollarģa tiykarlanatuģın qandayda bir ulıwmalıq terek shakllantirishdan ibarat. Máselen, eger giltler sanlı bolsa, hár bir cifr poziciyası berilgen túyinniń 10 múmkin bolģan áwladlarınan birin anıqlaydı.


7-suwret
Terektiń hár bir túyini arnayı tok simvolına iye. Bul simvol qaysidúr gilt axırın bildiredi. Bunday túyin saqlap qalınıwshi jazıwdı kórsetiwshi kórsetkishdi da ózinde saqlaydı. Shtrixlanģan sızıq terek túyininen giltke kórsetkishdi kórsetedi.

.

8-suwret

Paydalanılģan ádebiyatlar:

1. https://structur.h1.ru/hash.htm

2. А.Р.Есаyaн и др. Информатика. М.:Просвещение,1991.212-224 с.