Äîêóìåíò âçÿò èç êýøà ïîèñêîâîé ìàøèíû. Àäðåñ îðèãèíàëüíîãî äîêóìåíòà : http://www.astro.spbu.ru/staff/ilin2/EDU/NON-NUM/part1.ps Äàòà èçìåíåíèÿ: Fri Nov 19 16:15:05 2010 Äàòà èíäåêñèðîâàíèÿ: Tue Oct 2 02:28:31 2012 Êîäèðîâêà: ISO8859-5

VVEDENIE V NEQISLOVOE
PROGRAMMIROVANIE (qast~ 1)
V.B.IL?IN, A.D.POLOjENCEV
S.-Peterburg 1994

1 Vvedenie 3
1.1 Ponètie neqislovogo programmirovaniè : : : : : : : : : : : : : : : : : : : : : 3
1.2 Zadaqi neqislovogo programmirovaniè : : : : : : : : : : : : : : : : : : : : : : 3
2 Tipy dannyh 7
2.1 Dannye i tipy dannyh : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 7
2.2 Prostye tipy dannyh : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 8
2.2.1 Skalèrny$i tip dannyh : : : : : : : : : : : : : : : : : : : : : : : : : : : : 8
2.2.2 Ograniqenny$i tip dannyh : : : : : : : : : : : : : : : : : : : : : : : : : : 9
2.3 Standartnye tipy dannyh : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 10
2.3.1 Logiqeski$i tip dannyh : : : : : : : : : : : : : : : : : : : : : : : : : : : : 10
2.3.2 Cely$i tip dannyh : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 10
2.3.3 Simvol~ny$i tip dannyh : : : : : : : : : : : : : : : : : : : : : : : : : : : 11
2.3.4 Vewestvenny$i tip dannyh : : : : : : : : : : : : : : : : : : : : : : : : : : 11
2.4 Sostavnye tipy dannyh : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 13
2.4.1 Kombinirovanny$i tip dannyh : : : : : : : : : : : : : : : : : : : : : : : : 13
2.4.2 Regulèrny$i tip dannyh : : : : : : : : : : : : : : : : : : : : : : : : : : : : 14
2.4.3 Mnoïestvenny$i tip dannyh : : : : : : : : : : : : : : : : : : : : : : : : : 15
2.5 Ssyloqny$i tip dannyh : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 15
3 Struktury dannyh 19
3.1 Dinamiqeskie struktury dannyh : : : : : : : : : : : : : : : : : : : : : : : : : : 19
3.2 Line$inye spiski : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 20
3.2.1 Opredeleniè i osnovnye operacii : : : : : : : : : : : : : : : : : : : : : 20
3.2.2 Sposoby predstavleniè spiskov : : : : : : : : : : : : : : : : : : : : : : : 21
3.2.3 Qastnye sluqai line$inyh spiskov: stek, oqered~, dek : : : : : : : : : 28
3.3 Rekursivny$i sposob raboty so spiskami : : : : : : : : : : : : : : : : : : : : : 30
3.4 Neline$inye struktury dannyh: derev~è i grafy : : : : : : : : : : : : : : : : 35
4 Struktury i tipy dannyh v rabote 41
4.1 Igrovye zadaqi : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 41
4.2 Modelirovanie igry v ''orlènku'' : : : : : : : : : : : : : : : : : : : : : : : : : 41
4.2.1 Uslovie zadaqi : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 41
4.2.2 Postanovka zadaqi dlè programmista : : : : : : : : : : : : : : : : : : : 41
4.2.3 Realizaciè algoritma : : : : : : : : : : : : : : : : : : : : : : : : : : : : 42
5 ZaklÈqenie 45
6 Literatura 47
1

2 CONTENTS
Annotaciè
Dannoe posobie napisano na osnove kursa programmirovaniè, qitavxegosè
v teqenie neskol~kih let studentam vtorogo kursa matematiko-mehaniqeskogo
fakul~teta Leningradskogo gosudarstvennogo universiteta.
Kurs predstavlèl sobo$i dopolnenie k standartnomu kursu programmirova-
niè, gde rassmatrivaetsè kako$i-libo èzyk programmirovaniè i daÈtsè osnovy
metodov vyqisleni$i.
V posobii rassmatrivaÈtsè nekotorye zadaqi ''neqislovogo'' programmiro-
vaniè i ih rexenie na èzyke ''Paskal~''. Pervaè glava posvèwena tipam dannyh
èzyka ''Paskal~''. Vo vtoro$i glave obsuïdaÈtsè nekotorye struktury dannyh
i ih realizaciè pri pomowi sredstv èzykov ''Paskal~'' i ''Fortran'' (pred-
polagaetsè, qto s osnovami èzyka ''Fortran'' i ''Paskal~'' qitatel~ znakom).
V tret~e$i glave, na primere igry v ''orlènku'', rassmatrivaetsè programmi-
rovanie igrovyh zadaq (dialogovyh). Pri razbore danno$i zadaqi, osnovnoe
vnimanie udeleno vyboru udobnyh tipov i struktur dannyh.

Vvedenie
1.1 Ponètie neqislovogo programmirovaniè
Sredi vstreqaÈwihsè v programmirovanii zadaq provedem razdelèÈwuÈ qer-
tu (bezuslovno sil~no rasplyvqatuÈ), i otdelim algoritmy, gde osnovnye
trudnosti vyzvany znaqitel~nym qislom arifmetiqeskih (algebraiqeskih)
operaci$i ot zadaq, gde glavnym èvlèetsè ne ffto, a organizaciè dannyh i dru-
gie voprosy (naprimer logika v sil~no zaputannyh algoritmah, predstavle-
nie dannyh, suwestvenno otliqaÈwihsè ot qislovyh i t.d.). Rexeniè na \LambdaVM
zadaq pervogo roda budem nazyvat~ ''qislovym'' programmirovaniem, vtorogo
roda - sootvetstvenno ''neqislovym'' programmirovaniem.
V qem ïe razliqie fftih dvuh vidov programmirovaniè ? V qislovom prog-
rammirovanii glavnaè trudnost~ zaklÈqaetsè v adekvatnom primenenii soot-
vetstvuÈwe$i metodiki iz oblasti ''metodov vyqisleni$i'' i v bor~be s potere$i
toqnosti, voznikaÈwe$i pri bol~xom qisle posledovatel~nyh arifmetiqes-
kih operaci$i, vsledstvie pribliïennogo predstavleniè vewestvennyh qisel v
\LambdaVM.
V neqislovom programmirovanii akcent smewaetsè s fftih problem na orga-
nizaciÈ dannyh i drugie voprosy, poskol~ku koliqestvennoe uveliqenie ob?e-
ma dannyh (kak, naprimer, v sluqae zadaq sortirovki), kaqestvennoe izmenenie
dannyh (kak pri rabote s analitiqeskimi vyraïenièmi) ili inoe otnoxenie
k dannym (kak v sluqae servisnyh programm) trebuet primeneniè special~nyh
algoritmov (t.e. dannye i logika stanovètsè opredelèÈwimi dlè algoritma).
1.2 Zadaqi neqislovogo programmirovaniè
Pereqislim osnovnye zadaqi neqislovogo programmirovaniè, voznikaÈwie na
granice informatiki i astronomii.
Bol~xuÈ qast~ dannyh, kak izvestno, astronomiè poluqaet v ffksperimen-
tah. Sredi programm, obespeqivaÈwih avtomatizaciÈ ffksperimentov, podav-
lèÈwee qislo sostavlèÈt zadaqi neqislovogo programmirovaniè: programmy
upravleniè raboto$i priborov (teleskopy, priemniki i t.d.), perviqno$i ob-
rabotki informacii (vvedenie popravok za ffffekty, vnosimye priborami) i
organizacii informacii (t.e. kodirovka, upakovka, raspakovka informacii i
t.d.). Primerom upravlèwih programm èvlèÈtsè programmy avtomatiqeskogo
3

4 CHAPTER 1. VVEDENIE
gidirovaniè ob?ektov na teleskopah, upravlenie mnogokomponentnymi radio-
teleskopami (naprimer RATAN-600) i dr.; perviqno$i obrabotki --- vyqita-
nie instrumental~nogo profilè v spektroskopii, vyqitanie pomeh vnosimyh
kosmiqeskimi luqami v nablÈdenièh s PZS-matricami i t.d.; organizaciè
informacii --- upakovka dvuhmernyh izobraïeni$i astronomiqeskih ob?ektov
dlè ffkonomii pamèti \LambdaVM pri ih hranenii i t.p.
SleduÈwi$i fftap raboty s rezul~tatami nablÈdeni$i v astronomii --- obra-
botka dannyh. Zdes~ zadaqi neqislovogo programmirovaniè voznikaÈt reïe i
v osnovnom v teh sluqaèh, kogda ob?em dannyh velik (naprimer, pri obrabot-
ke izobraïeni$i) ili kogda povyxaÈtsè trebovaniè k servisu (dlè bol~xih
programm, prednaznaqennyh dlè dlitel~nogo i xirokogo ispol~zovaniè).
Nekotoraè (hotè i ne oqen~ bol~xaè) qast~ obrabotannyh dannyh, predla-
gaemaè dlè ispol~zovaniè xiroko$i astronomiqesko$i obwestvennost~È, pere-
daetsè dlè vklÈqeniè v banki dannyh v centry dannyh (naprimer CAD pri
astronomiqeskom sovete AN SSSR v Moskve i/ili meïdunarodny$i CAD v
Strassrburge). Pri rabote s bankami dannyh osnovnymi èvlèÈtsè program-
my neqislovogo programmirovaniè. V proste$ixem sluqae kataloga dannyh
vstreqaemost~ neqislovyh programm suwestvenno niïe i zavisit obyqno ot
ob?ema kataloga i naznaqeniè kompleksov programm.
PrisutstvuÈt zadaqi neqislovogo programmirovaniè i v teoretiqeskih
issledovanièh. V qastnosti special~nye translètory, interpretatory i t.p.
PozvolèÈt avtomatizirovat~ kodirovku (obyqno krupnyh, odnoobraznyh) prog-
ramm. Naprimer, v fiziko-himii atmosfer planet i meïzvezdno$i himii pri-
menèÈtsè interpretatory, vosprinimaÈwie blizkuÈ k obyqno$i zapis~ himi-
qeskih reakci$i i stroèwie sootvetstvuÈwie programmnye moduli. Otnosi-
tel~noe qislo takih programm oqen~ malo, no ih ob?em i rastuwaè neline$ino
s nim trudoemkost~ sozdaniè i otladki, privodèt k tomu, qto zatraty na ih
sozdanie (dlitel~nost~ sozdaniè i neizbeïnyh modifikaci$i gody !) mogut
sostavit~ znaqitel~nuÈ dolÈ vremeni raboty programmistov (astronomov).
Naivysxim dostiïeniem neqislovogo programmirovaniè, èvlèÈtsè, po-vi-
dimomu, sistemy dlè raboty s analitiqeskimi vyraïenièmi. Takie siste-
my v nastoèwi$i moment ''umeÈt'' proizvodit~ integrirovanie, ne govorè o
differencirovanii ili privedenii podobnyh qlenov, lÈbyh algebraiqeskih
vyraïeni$i, vklÈqaÈwih kak polinomy, tak i vse algebraiqeskie funkcii
vplot~ do special~nyh (sistema MACSIMA). Special~nye vidy takih sistem
(SCHOOLSHIP, REDUCE i t.d.) ispol~zuÈtsè v fizike fflementarnyh qastic,
relètivistko$i kvantovo$i mehanike i nebesno$i mehanike.
Na vseh fftapah deètel~nosti astronomov inogda voznikaet neobhodimost~
sozdaniè servisnyh programm, t.e. programm na kotorye nalagaÈtsè osobo ïes-
tkie trebovaniè (qto koneqno privodit k modifikacii ishodnogo algoritma).
Obyqno ffti trebovaniè takovy: usilennaè zawita ot oxibok, nadeïnost~, do-
kumentirovannost~, uluqxennaè forma vydaqi rezul~tatov i t.d. Otliqny$i
primer servisnyh programm - igrovye programmy !
Podvodè itog, pereqislim snova naibolee tipiqnye zadaqi neqislovogo
programmirovaniè: upravlèÈwie programmy; programmy, rabotaÈwie s oqen~
bol~ximi ob?emami dannyh (vklÈqaè programmy sortirovki); programmy,
rabotaÈwie s informacie$i, znaqitel~no otliqaÈwe$isè ot qislovo$i i, nako-

1.2. ZADAQI NEQISLOVOGO PROGRAMMIROVANI? 5
nec, servisnye programmy lÈbogo naznaqeniè.
V zaklÈqenii, stoit otmetit~ veroètno neoïidanny$i dlè mnogih fakt, qto
astronomiè i programmirovanie svèzany ne stol~ slabo, kak kaïetsè na per-
vy$i vzglèd. Primerami vlièniè astronomii na programmirovanie moïet slu-
ïit~ to, qto imenno astronomiqeskie potrebnosti priveli k sozdaniÈ pervyh
vyqislitel~nyh maxin ili ïe xirokaè rasprostranennost~ èzyka ''FORTH'',
sozdannogo dlè upravleniè radioteleskopom; obratnoe vliènie - nekotorye
izmeneniè obraza ïizni astronomov, v qastnosti v rède stran astronomy ne
ezdèt nablÈdat~ v observatorii, a podaÈt so svoego terminala zaèvku i qe-
rez nekotoroe vremè poluqaÈt na nego rezul~taty nablÈdeni$i (transkonti-
nental~naè svèz~ evrope$iskaè Èïnaè observatoriè (ESO) v Qili - Angliè).

6 CHAPTER 1. VVEDENIE

Tipy dannyh
V danno$i glave rassmatrivaÈtsè razliqnye gruppy (tipy) dannyh, kotorye
prisutstvuÈt v sovremennyh èzykah programmirovaniè (a ne tol~ko v Paskale
ili Fortrane!) 1 .
Snaqala obsuïdaÈtsè obyqnye, fflementarnye tipy dannyh (p. 2.2--2.3),
vstreqaÈwiesè vo vseh èzykah. Zatem opisyvaÈtsè sostavnye tipy dannyh
(p. 2.4), v kotoryh kaïdy$i fflement dannyh est~ nekotoraè sovokupnost~ ob?-
ektov. Ispol~zovanie dannyh fftih tipov okazyvaetsè udobnym pri ''neqis-
lovom'' programmirovanii. V zaklÈqenie (p. 2.5) obsuïdaetsè suwestvenny$i
dlè mnogih aspektov ''neqislovogo'' programmirovaniè tip dannyh --- ssyloq-
ny$i. \Lambdatot tip isklÈqitel~no vaïen pri postroenii v programmah neline$inyh
struktur dannyh (naprimer, vetvèwihsè ili s bol~xim qislom svèze$i).
Otmetim, qto punkty, v kotoryh obsuïdaÈtsè izvestnye qitatelÈ tipy,
mogut byt~ propuweny, isklÈqaè p. 2.4.1 i 2.5, gde izlagaÈtsè svedeniè, ne-
obhodimye dlè ponimaniè Glavy 3.
2.1 Dannye i tipy dannyh
LÈbo$i algoritm (programma) dlè vyqislitel~no$i maxiny sostoit iz dvuh
osnovnyh qaste$i: opisanie de$istvi$i, kotorye predstoit vypolnit~, i opisa-
niè ob?ektov, nad kotorymi budut vypolnèt~sè ffti de$istviè. Obyqno pri
obuqenii programmirovaniÈ osnovnoe vnimanie udelèetsè pervo$i qasti, my
rassmotrim ne menee vaïnuÈ, vtoruÈ qast~.
Ob?ekty, kotorymi operiruet programma, budem nazyvat~ dannymi. Vaï-
no$i osobennost~È dannyh èvlèetsè to, qto oni imeÈt dva atributa: imè i
znaqenie. Esli pere$iti na èzyk maxinnyh komand, to imeni budet sootvets-
tvovat~ nomer èqe$iki, a znaqeniÈ --- soderïimoe èqe$iki. V apparature \LambdaVM
vse dannye predstavlèÈt sobo$i posledovatel~nost~ dvoiqnyh cifr, t.e. rèdy,
sostoèwie iz nule$i i edinic. Takie dannye ispol~zovalis~ v proxlom pri
programmirovanii na èzyke maxinnyh komand (v maxinah pervogo pokoleniè:
Ural-1 i dr.). ?zyki programmirovaniè vysokogo urovnè (Algol, Fortran i
dr.) pozvolèÈt abstragirovat~sè ot neudobnyh detale$i predstavleniè dannyh
i proishodit ffto v osnovnom za sqet vvedeniè koncepcii tipov dannyh.
1 \Lambdata glava imeet harakter ''likbeza''. Osnovnoe soderïanie kursa nahoditsè v Glave 3 i illÈstri-
ruÈwe$i ee Glave 4 (Glava 4 privedena v sokrawennom variante).
7

8 CHAPTER 2. TIPY DANNYH
Opredelenie: tipom dannyh budem nazyvat~ klass (gruppu) ob?ektov, zna-
qeniè kotoryh prinadleïat opredelennomu mnoïestvu.
Naprimer, cely$i tip dannyh, vstreqaÈwi$isè poqti vo vseh èzykah prog-
rammirovaniè, ob?edinèet ob?ekty, znaqeniè kotoryh èvlèÈtsè celymi qis-
lami.
Obyqno vvedeniem tipov dannyh ob?ekty, ispol~zuemye v algoritmah (prog-
rammah) v vide peremennyh ili konstant, razbivaÈtsè na neskol~ko grupp po
obwim oblastèm znaqeni$i. Pri fftom kaïdaè peremennaè soprovoïdaetsè spe-
cifikacie$i ee vozmoïnyh znaqeni$i. \Lambdato delaetsè po sleduÈwim priqinam:
vo-pervyh, koliqestvo fflementov v pamèti \LambdaVM, neobhodimoe dlè hraneniè
znaqeni$i peremenno$i zavisit ot diapazona ee znaqeni$i. Tak dlè hraneniè pe-
remenno$i, prinimaÈwe$i N celyh znaqeni$i, neobhodimo primerno log N bitov.
V qastnosti dlè peremenno$i, znaqenièmi kotoro$i mogut byt~ 0, 1 i 2 neob-
hodimo dva bita (v dvoiqnom kode znaqeniè est~ 00, 01 i 10). Vo-vtoryh,
realizaciè de$istvi$i, opisannyh v algoritme, v komandah \LambdaVM qasto (poqti
vsegda) zavisit ot koliqestva fflementov pamèti, kotoroe zanimaet ob?ekt, tak
kak ispol~zuÈtsè razliqnye registry maxinnyh komand (po kra$ine$i mere, v
odnoadresnyh serii ES \LambdaVM i dr.)
I tak mnoïestvo znaqeni$i, kotoroe moïet prinimat~ peremennaè igraet
vaïne$ixuÈ rol~ dlè harakteristiki dannyh. Pofftomu, obyqno, vse peremen-
nye v programmah dolïny byt~ opisany (isklÈqaè pravilo umolqaniè nekoto-
ryh èzykov programmirovaniè) ili inymi slovami otneseny k kakomu-to tipu
dannyh 2 .
Tipy dannyh razdelèÈtsè na prostye i sostavnye.
Opredelenie: prostye tipy dannyh --- klassy ob?ektov, kaïdy$i iz kotoryh
predstavlèet sobo$i edinoe celoe, t.e. atom.
Opredelenie: sostavnye tipy dannyh --- klassy ob?ektov, kaïdy$i iz koto-
ryh vklÈqaet v sebè neskol~ko fflementov.
Primerom prostogo tipa èvlèetsè cely$i, vewestvenny$i tip i t.p., a sos-
tavnogo --- massivy.
2.2 Prostye tipy dannyh
Vo mnogih sovremennyh èzykah programmirovaniè razrexaetsè, krome stan-
dartnyh (prostyh) tipov: celogo, vewestvenogo, logiqeskogo i liternogo ---
vvodit~ i svoi tipy dannyh. Dlè fftogo v èzyke Paskal~ suwestvuet ponètie
skalèrtnogo tipa.
2.2.1 Skalèrny$i tip dannyh
Opredelenie : skalèrny$i tip dannyh --- klass ob?ektov, kotorye mogut pri-
nimat~ znaqeniè tol~ko iz nekotorogo zadannogo uporèdoqenogo mnoïestva.
Opredelenie skalèrnogo tipa v èzyke Paskal~ vyglèdit sleduÈwim obra-
zom:
TYPE Ts = (w1, w1, ..., wn)
2 Opisanie peremennyh v èzyke Paskal~ imeet vid: VAR v1, v2, ..., vn: T, gde VAR --- sluïebnoe slovo
èzyka Paskal~; v1, v2, ..., vn --- imena peremennyh (indentifikatory); T --- imè tipa dannyh.

2.2. PROSTYE TIPY DANNYH 9
gde TYPE --- sluïebnoe slovo èzyka Paskal~;
Ts --- imè skalèrnogo tipa dannyh;
w1, w2, ..., wn --- konstantye indetifikatory.
Konstantnye indentifikatory dolïny byt~ razliqny; ih uporèdoqivae-
most~ zadaetsè porèdkom sledovaniè tak, qto sqitaetsè w1 ! w2 ! ... ! wn.
Na peremennyh skalèrnogo tipa opredeleny operacii:
otnoxeniè: !; ?; = i !?;
i funkcii poluqeniè sleduÈwego i predyduwego fflementa SUCC i PRED (nap-
rimer, rezul~tat SUCC(w2) est~ w1 i t.d.).
Primer. Opredelim skalèrny$i tip, pereqisèÈwi$i planety Solneqno$i sis-
temy, i vypolnim rèd trivial~nyh operaci$i s peremenymi dannogo tipa.
TYPE Planets = (me, v, e, ma, j, s, u, n, p); ...
VAR planet1, planet2: Planets; l: BOOLEAN; ...
... planet1:= e; planet2:= V;
l:= planet1 ?= planet2; ...
V dannom sluqae peremennaè l primet znaqenie FALSE.
Otmetim, qto cel~È vvedeniè skalèrnyh tipov dannyh èvlèetsè abstra-
girovanie ot maxinno orientirovannogo predstavleniè dannyh (rèdy 0 i 1)
tak, qtoby rabotat~ s ob?ektami v udobno$i qeloveku forme, t.e. maksimal~no
pribliïenno$i k real~no$i. SleduÈwi$i xag v fftom napravlenii --- opredele-
nie special~nyh operaci$i na novyh tipah. V nekotoryh èzykah (Algol-68,
FORTH i dr.) ffto moïno delat~ èvno. V èzyke Paskal~ ffto delaetsè kosvenno,
qerez podprogrammy.
2.2.2 Ograniqenny$i tip dannyh
Na opredelenii skalèrnogo tipa baziruetsè opredelenie ego qasti, nazyvae-
mo$i ograniqennym tipom.
Opredelenie: ograniqenny$i tip dannyh --- klass ob?ektov, kotorye mogut
prinimat~ znaqeniè iz ukazannogo svèznogo podmnoïestva nekotorogo mnoïes-
tva (zadavaemogo opredeleniem bazovogo skalèrnogo tipa).
V èzyke Paskal~ opredelenie dannogo tipa imeet vid:
TYPE To = wi .. wl
gde .. (dve toqki!) --- special~ny$i znak èzyka;
wi i wl -- konstantnye indentifikatory, vhodèwie v bazovy$i skalèrny$i tip
(zadany$i vyxe).
Peremennye ograniqennogo tipa mogut prinimat~ znaqeniè konstantnyh iden-
tifikatorov skalèrnogo tipa Ts v intervale ot wi do wl vklÈqitel~no.
Na ograniqennom tipe razrexeny te ïe operacii, qto i na bazovom skalèr-
nom tipe.
Primer. V massive indeksy fflementov ograniqeny nekotorym celym qis-
lom. Ograniqenny$i tip, udobny$i dlè opisaniè indeksov massiva v 100 ffle-
mentov, moïet byt~ opredelen na standartnom skalèrnom tipe (celom tipe)
tak
TYPE Index = 1 .. 100

10 CHAPTER 2. TIPY DANNYH
2.3 Standartnye tipy dannyh
Nekotorye skalèrnye tipy ispol~zuÈtsè stol~ qasto (i davno!), qto sootvets-
tvuÈwee opredeleniè tipa i ego standartnoe imè zaloïeny v èzyke. V Paskale
standartnymi skalèrnymi tipami èvlèÈtsè: logiqeski$i, cely$i, literny$i i
vewestvenny$i 3 . \Lambdati tipy prisutstvuÈt i v bol~xinstve drugih èzykah prog-
rammirovaniè.
2.3.1 Logiqeski$i tip dannyh
Opredelenie: logiqeski$i (ili bulevski$i) tip dannyh --- klass ob?ektov, ko-
torye mogut prinimat~ lix~ dva znaqeniè: FALSE (loï~) i TRUE (istina).
V èzyke Paskal~ podrazumevaetsè sleduÈwee opisanie dannogo tipa, ime-
Èwego standartnoe fiksirovannoe imè BOOLEAN:
TYPE BOOLEAN = (FALSE, TRUE)
i dlè dannogo tipa opredeleny sleduÈwie operacii:
logiqeskie OR, AND, NOT;
otnoxeniè !; ?; =; !?;
tip rezul~tata fftih operaci$i vsegda BOOLEAN.
Primer. Sleduwie operatory programmy:
... VAR x, y, z, u: BOOLEAN;
y:= FALSE; z:= TRUE;
x:= Y ? Z; u:= y OR z; ...
privedut k tomu, qto peremennaè x budet imet~ znaqenie FALSE, a u --- TRUE.
Otmetim, qto tip BOOLEAN vyzvan (svèzan) suwestvovaniem v algoritmah
struktur (de$istvi$i) tipa razvilka: IF ... THEN ... ELSE ... .
2.3.2 Cely$i tip dannyh
Dlè kaïdo$i vyqislitel~no$i maxiny opredeleno nekotoroe podmnoïestvo ce-
lyh qisel, takih s kotorymi ee arifmetiqeskoe ustro$istvo moïet operiro-
vat~. V ES \LambdaVM na celoe qislo otvodit~sè 4 ba$ita = 32 bitam i sledova-
tel~no moïno predstavlèt~ qisla v intervale [\Gamma2 31 ; 2 31 ].
Opredelenie: cely$i tip dannyh --- klass ob?ektov, kotorye mogut prini-
mat~ znaqeniè iz mnoïestva celyh maxinnyh qisel.
Podrazumevaetsè sleduÈwee (oqen~ dlinnoe!) opisanie v Paskale dannogo
tipa (standartnoe imè INTEGER):
TYPE INTEGER = (minint, minint+1, minint+2, ..., maxint-1, maxint),
gde minint i maxint --- sootvetstvenno maksimal~noe i minimal~noe qislo iz
mnoïestva maxinnyh celyh qisel.
3 Vewestvenny$i tip, stoit osobnèkom sredi skalèrnyh tipov, t.k. na nem nel~zè opredelit~ ograni-
qenny$i tip. Nakladyvanie takogo ograniqeniè v èzyke, svèzano s tem, qto opredelenie ograniqennogo
tipa na vewestvennom na raznyh maxinah budet ne odnoznaqno (zavisit ot razrèdnosti maxiny).

2.3. STANDARTNYE TIPY DANNYH 11
Razrexeny sleduÈwie operacii dlè celyh qisel:
arifmetiqeskie +; \Gamma; \Lambda, DIV (delenie), MOD (vzètie ostatka) --- rezul~tat ope-
raci$i tipa INTEGER;
otnoxeniè !; ?; !=;=?;=;!? --- rezul~tat BOOLEAN.
Suwestvuet i rèd vstroennyh funkci$i.
Podqerknem, qto obyqnye aksiomy arifmetiki mogut byt~ ne verny dlè
maxinno$i arifmetiki. Naprimer dlè maxinnogo sloïeniè dvuh celyh qisel
x i y, rezul~tat budet ne opredelen, esli (x+y) ! minint ili (x+y) ? maxint 4 .
2.3.3 Simvol~ny$i tip dannyh
Opredelenie: simvol~ny$i tip dannyh --- klass ob?ektov, kotorye mogut pri-
nimat~ znaqeniè liter: 26 latinskih bukv, 10 arabskih cifr i neskol~ko spe-
cial~nyh simvolov, vklÈqaè probel (dlè ES \LambdaVM).
Podrazumevaetsè sleduÈwee opisanie v Paskale:
TYPE Char = ('a','b','c',...,'Z','0',...'9',' ','/','*',...)
t.e. litery uporèdoqeny nekotorym obrazom.
Razrexeny sleduÈwie operacii: otnoxeniè: !; ?; !=;=?;!? --- rezul~tat
BOOLEAN.
Otmetim, qto simvol~ny$i tip obyqno ispol~zuetsè pri operacièh vvo-
da/vyvoda v programmah.
2.3.4 Vewestvenny$i tip dannyh
V vyqislitel~no$i maxine moïno predstavit~ qisla dostatoqno razreïennogo
koneqnogo podmnoïestva vewestvennyh qisel. V sovremennyh cifrovyh ma-
xinah, ispol~zuetsè predstavlenie vewestvennogo qisla s ''plavaÈwe$i toq-
ko$i'', t.e. kaïdoe vewestvennoe qislo x predstavlèetsè paro$i qisel m i i:
x = m \Delta b i ; i = [\GammaK; K]; m = [\GammaN; N ], gde b --- osnovanie, i --- porèdok, a m --- man-
tissa qisla x. Esli 1 ? jmj ? 0:1, to forma predstavleniè qisla nazyvaetsè
normalizovanno$i. V maxinah serii ES \LambdaVM dlè b = 10, m --- priblizitel~no
sem~ desètiqnyh znakov, a i = [\Gamma79; 75].
Oqevidno, qto pri ispol~zovanii takogo predstavleniè plotnost~ ''maxin-
nyh'' vewestvennyh qisel umen~xaetsè s ih rostom: v intervale 0.1--1.0 so-
derïitsè stol~ko ïe vewestvennyh ''maxinnyh'' qisel, skol~ko i v otrezke
1000.0--10000.0! Trudno predskazat~ k qemu ffto moïet privesti v to$i ili
ino$i programme.
Opredelenie: vewestvennom tipom dannyh budem nazyvat~ klass ob?ektov,
kotorye mogut prinimat~ znaqeniè iz mnoïestva ''maxinnyh'' vewestvennyh
qisel.
Podrazumevaetsè oqen~-oqen~ dlinnoe opisanie (v èzyke Paskal~)
TYPE REAL = (minreal, ..., maxreal),
4 Otmetim, qto cely$i tip qasto svèzan s konstrukcièmi programm tipa cikla (sqetqik cikla) FOR ...
DO ...

12 CHAPTER 2. TIPY DANNYH
gde dolïny byt~ pereqisleny v porèdke vozrastaniè vse ''maxinnye'' ve-
westvennye qisla.
Razrexeny sleduÈwie operacii:
arifmetiqeskie: +; \Gamma; \Lambda; = --- rezul~tat tipa REAL;
otnoxeniè: !; ?; !=;=?;=;!? --- rezul~tat BOOLEAN.
Dostupen obyqno i rèd xiroko ispol~zuemyh vstroennyh funkci$i.
Otmetim, qto kak i v sluqae celogo tipa, aksiomy arifmetiki mogut byt~
ne vypolnimy dlè peremennyh vewestvennogo tipa. V qastnosti, net zako-
nov associativnosti i distributivnosti, qto svèzano s ograniqeniem dliny
mantisy u ''maxinnyh'' vewestvennyh qisel. Iz-za fftogo osobuÈ opasnost~
predstavlèet vyqitanie dvuh primerno ravnyh qisel. Pri fftom bol~xoe ko-
liqestvo znaqawih cifr uniqtoïaetsè i v poluqenno$i raznosti moïet oka-
zat~sè oqen~ malo vernyh cifr. Naprimer, vyqitanie iz qisla 0.2013 qisla
0.2008, na maxine s dlino$i mantissy 4 budet proishodit sleduÈwim obrazom:
0.2013 10**0
-0.2008 10**0
--------------------
.5xxx 10**(-3)
i v mantisu rezul~tata popadet 5 i ewe tri cifry (xxx), kotorye, napri-
mer, maxiny serii ES \LambdaVM ''vydumaÈt'' sami. T.o. v rezul~tate ostanetsè
lix~ odna vernaè cifra!
Otmetim, qto vewestvenny$i tip dannyh neobhodim v programme dlè vyqis-
leni$i.
Upraïneniè
1. Opredelen skalèrny$i tip imen spektral~nyh klassov zvezd:
TYPE Spectral = (O, B, A, F, G, K, M)
izvestno, qto v peremennyh fftogo tipa s1 i s2 nahodètsè imena spektral~nyh
klassov dvuh zvezd. Napisat~ operator, proverèÈwi$i: èvlèÈtsè li klassy
zvezd sosednimi.
2. Dobavit~ opisanie peremennyh k imeÈwe$isè programme:
b:= a=1 OR c=1.0
3. Dano opisanie peremennyh:
VAR kh, y, z: REAL; i, j, k: INTEGER
Proverit~ pravil~no li zapisany vyraïeniè:
a) x + y * i
b) x + k ! i + j
v) i DIV j + x
4. Opisat~ tipy dannyh, udobnye dlè raboty:
a) s hablovsko$i klassifikacie$i gallaktik;
b) s ocenkami uqawihsè v xkole.

2.4. SOSTAVNYE TIPY DANNYH 13
2.4 Sostavnye tipy dannyh
Vyxe my rassmotreli prostye tipy fflementarnyh dannyh, t.e. dannyh, zna-
qeniè kotoryh èvlèÈtsè nedelimymi. Odnako, qasto prihoditsè rabotat~ s
ob?ektami, predstavlèÈwimi sobo$i nekotoruÈ sovokupnost~ dannyh (''klas-
siqeski$i'' primer --- massiv). Pri fftom moïet potrebovat~sè sovokupnost~
dannyh raznogo tipa, s kotorymi neobhodimo rabotat~ kak s odnim celym.
Naprimer, s dato$i ili so svedenièmi o kakom-to ob?ekte: qeloveke, zvezde i
t.p. V fftih sluqaèh udobno ispol~zovat~ tak nazyvaemy$i kombinirovanny$i
tip dannyh.
2.4.1 Kombinirovanny$i tip dannyh
Opredelenie: kombinirovanny$i tip dannyh (ili zapisi) --- klass ob?ektov,
kotorye sostoèt iz fiksirovannogo qisla fflementov raznogo tipa.
Na zapisèh razrexeny tol~ko operacii prisvaivaniè, no nuïnye nam ope-
racii mogut byt~ opredeleny dopolnitel~no (po kra$ine$i mere, qerez podprog-
rammy, kak v èzyke Paskal~). Dlè komponentov zapisi opredeleny vse opera-
cii, razrexennye dlè ih tipov dannyh.
Opisanie v èzyke Paskal~ imeet vid:
TYPE Ts = RECORD p1: T1; p2: T2; ...; pn: TN END
gde Tc --- imè kombinirovannogo tipa;
RECORD i END --- zarezervirovannye slova Paskalè;
T1, T2, ..., TN --- imena tipov komponentov zapisi;
p1, p2, ..., pN --- imena pole$i, neobhodimye dlè raboty s komponentami.
Dlè peremenno$i s kombinirovanogo tipa Ts (opisanie: VAR s: Ts) s.p1 ---
est~ komponent tipa T1; s.p2 --- komponent tipa T2 i t.d.
Primer. Opredelim kombinirovanny$i tip s imenem Date dlè predstavleniè
daty i prisvoim nekotorye znaqeniè komponentam peremenno$i today dannogo
tipa.
TYPE Tdate = 1..31;
Tmonth = (JAN, FEB, MAR, APR, MAY, JUN, JUL, AUG,
SEP, OCT, NOV, DEC);
Tyear = 0..2005;
Date = RECORD day: Tdate;
mon: Tmonth;
year: Year
END;
VAR today: Date;
BEGIN
today.day:= 23; today.mon:= MAR; today.year:= 1995
END.

14 CHAPTER 2. TIPY DANNYH
2.4.2 Regulèrny$i tip dannyh
Qasto vstreqaetsè qastny$i sluqa$i kombinirovannogo tipa, kogda komponenty
peremenno$i imeÈt odinakovy$i tip. \Lambdatot sluqa$i vydelen osobo v tak nazyva-
emy$i regulèrny$i tip.
Opredelenie: regulèrny$i tip dannyh (ili massivy) --- klass ob?ektov, ko-
torye sostoèt iz fiksirovannogo qisla fflementov odnogo i togo ïe tipa (v
otliqie ot zapise$i, u kotoryh tip fflementov moïet byt~ raznym!)
Opisanie na èzyke Paskal~ dannogo tipa est~:
TYPE Tr = ARRAY [Ti] OF Tk
gde Tr --- imè regulèrnogo tipa;
ARRAY i OF --- zarezervirovannye slova v èzyke Paskal~;
Ti --- imè tipa dannyh indeksov massiva --- obèzatel~no kako$i-libo skalèrny$i
tip (krome vewestvennogo)!
Tk --- imè tipa komponentov.
Tak ïe, kak i dlè zapise$i, opredelena lix~ odna operaciè --- prisvaiva-
nie (odnako moïno kosvenno vvodit~ i svoi specifiqeskie), a dlè komponentov
massiva razrexenny vse operacii ih tipa.
Opisanie peremenno$i regulèrnogo tipa v èzyke Paskal~ i rabota s ee kom-
ponentami vyglèdit sleduÈwim obrazom:
... VAR b,a: Tr; i,j: Ti; c: Tk;...
... c:= a[i]; a[i]:= a[j]; a[j]:= c; b:= a...
Vozmoïna rabota i s mnogomernymi massivami (toïe qasto vstreqaetsè na
praktike). V èzyke Paskal~ dvumerny$i massiv opisyvaetsè tak:
TYPE Ta = ARRAY [Ti,Tj] OF Tk
gde Ti i Tj --- tipy indeksov (pervogo i vtorogo).
Primer. Dlè predstavleniè daty i raboty s ne$i moïno ispol~zovat~ ne
tol~ko zapisi (sm. kombinirovanny$i tip v p. 1.4.1), no i massivy:
TYPE Ti = 1..3; Tk = 0..2005;
Data = ARRAY [Ti] OF Tk;
VAR tomorow: Data;
BEGIN
tomorow[1]:= 24;
tomorow[2]:= 3;
tomorow[3]:= 1995
END.
Primeqanie. ?sno, qto rabota s zapisèmi v dannom sluqae naglèdnee i,
sledovatel~no, ih ispol~zovanie predpoqtitel~nee (esli postanovka zadaqi
ne trebuet ispol~zovaniè massivov).

2.5. SSYLOQNY $
I TIP DANNYH 15
2.4.3 Mnoïestvenny$i tip dannyh
Inogda (ne tak redko!) voznikaet neobhodimost~ rabotat~ s mnoïestvom (ob?-
ektov) i togda udobno vospol~zovat~sè tak nazyvaemym mnoïestvennym tipom.
Opredelenie: mnoïestvenny$i tip --- klass ob?ektov, znaqenièmi kotoryh
èvlèÈtsè podmnoïestva nekotorogo fiksirovannogo mnoïestva (poslednee za-
daetsè opisaniem skalèrnogo tipa). Opisanie tipa v èzyke Paskal~ vyglèdit
tak:
TYPE Bset = (b1, b2, ..., bn);
Tm = SET OF Bset
gde Bset --- imè bazovogo skalèrnogo(!) tipa;
b1, b2, ..., bn --- konstantnye identifikatory tipa Bset;
SET OF --- zarezervirovannye slova èzyka Paskal~.
Opredeleny sleduÈwie operacii:
a) otnoxeniè: !=;=? (vklÈqenie mnoïestv!) i =; !? (toïdestvo i razliqie)
--- tip rezul~tata BOOLEAN;
b) nad mnoïestvami: + (ob?edinenie); \Lambda (pereseqenie);
IN (prinadleïnost~ fflementa mnoïestvu) --- tip rezul~tata BOOLEAN.
Opisanie peremennyh mnoïestvennogo tipa i rabota s nimi vyglèdit sle-
duÈwim obrazom:
VAR t1, t2: Tm; L: BOOLEAN;
BEGIN
t1:= [b2, b5, b8];
l:= b5 IN t1
END.
gde t1 --- podmnoïestvo iz treh fflementov, a l v rezul~tate raboty danno$i
programmy budet imet~ znaqenie TRUE.
Primer. Dva ob?ekta nablÈdalis~ v razliqnyh fotometriqeskih polosah
(U,B,V,R). Programma, kotoraè opredelèet imeÈtsè li nablÈdeniè ob?ektov
hotè by v odno$i obwe$i polose moïet byt~ sleduÈwe$i:
TYPE Phband = (U, B, V, R); Obj = SET OF Phband;
VAR obj1, obj2: Obj; L: BOOLEAN;
BEGIN
L:= NOT( (obj1 * obj2) = [])
END.
gde [] --- pustoe mnoïestvo.
2.5 Ssyloqny$i tip dannyh
Kak otmeqalos~ vyxe, vsè informaciè v pamèti \LambdaVM predstavlèetsè v vide
mnoïestva nule$i i edinic, t.k. pamèt~ sostoit iz fflementov, hranèwih po 1
bitu informacii (fflement imeet tol~ko dva sostoèniè, odnomu pripisyvaetsè

16 CHAPTER 2. TIPY DANNYH
''0'', a vtoromu ''1''). Odnako obmen informacie$i meïdu pamèt~È i arifme-
tiqeskim ustro$istvom \LambdaVM proishodit ne po 1 bitu (ffto oqen~ medlenno), a
gruppami bit --- slovami (i daïe gruppami slov). V ES \LambdaVM, naprimer, 32
razrèdnoe slovo, t.e. soderïawee 32 bita (ili 4 ba$ita). Dlè vozmoïnosti ob-
raweniè k slovam (èqe$ikam pamèti, kak govorili ran~xe), kaïdoe slovo imeet
svo$i nomer --- adres. Takim obrazom s lÈbym ob?ektom, s kotorym operiruet
\LambdaVM i kotory$i raspolagaetsè v ee pamèti, svèzano dva qisla: adres èqe$iki,
v kotoro$i hranitsè informaciè (ob ob?ekte), i soderïimoe èqe$iki, t.e. ne-
posredstvenno sama informaciè. ?zyk Paskal~ (kak i mnogie drugie èzyki)
pozvolèÈt hranit~ v kaqestve informacii adresa èqeek. Ob?ekty znaqeniè
kotoryh est~ adresa èqeek nazyvaÈtsè ssylkami.
Opredelenie: ssyloqny$i tip dannyh --- klass ob?ektov, kotorye mogut
imet~ znaqeniè vseh vozmoïnyh adresov (v pamèti maxiny) ob?ektov neko-
torogo tipa.
Opisanie ssyloqnogo tipa v èzyke Paskal~:
TYPE Tl=@T
gde TL --- imè ssyloqnogo tipa;
T --- imè tipa, na dannye kotorogo opredelèÈtsè ssylki.
\Lambdatot tip moïet byt~ kak prostym, tak i sostavnym;
@ --- special~ny$i simvol èzyka Paskal~, dlè opredeleniè ssyloqnogo tipa
(simvol zavisit ot versii).
Opisanie peremennyh vyglèdit obyqno:
VAR s, p, q: Tl; a, b: T;
Razrexennymi operacièmi na ssyloqnom tipe èvlèÈtsè:
a) proverka toïdestva ili neravenstva: = i !?;
b) razimenovanie: @ ffto unarnaè operaciè (kak logiqeskoe otricanie .NOT.
dlè bulevskogo tipa), odnako ee znak stavitsè ne pered operandom, a posle
nego: S@. \Lambdato oznaqaet perehod ot adresa (ssylki) k soderïimomu èqe$iki.
T.e., esli s --- èvlèetsè peremenno$i ssyloqnogo tipa, to rezul~tat operacii
razimenovaniè s@ --- togo ïe tipa, na kotorom opredeleny ssylki (v primere
--- T).
Primery. Poèsnim qto oznaqaÈt sleduÈwie operatory:
a) s@:= b --- adres, soderïawi$isè v s ostaetsè preïnim, a vot soderïimoe
èqe$iki po fftomu adresu, byvxee ranee ravnym s@, teper~ budet ravno znaqeniÈ
peremenno$i b.
Do operacii
s: k
-
?
(k)
b: w
gde (k) --- adres èqe$iki
i posle operacii s@ := b

2.5. SSYLOQNY $
I TIP DANNYH 17
s: k
-
w
(k)
b: w
b) a:= s@ --- peremenno$i a prisvaivaetsè znaqenie, hranèweesè v èqe$ike s
adresom ravnym znaqeniÈ nahodèwemusè v peremenno$i s.
Do operacii
s: k
-
w
(k)
a: ?
i posle operacii a:= s@
s: k
-
w
(k)
a: w
v) s:= q --- v peremenno$i s hranilsè neki$i adres, teper~ on budet budet
zamenen na adres, hranèxi$isè v q.
Do operacii s := q i posle operacii
q: m
-
g
(m)
s: k
-
w
(k)
q: m
-
g
(m)
s: m
-
w
(m)
g) s@:= r@ --- v peremennyh s i r hranètsè raznye adresa, no znaqeniè v
èqe$ikah po fftim adresam teper~ budut odinakovymi.
Do operacii s@ := r@ i posle operacii
p: n
-
y
(n)
s: m
-
g
(m)
p: n
-
y
(n)
s: m
-
y
(k)
Suwestvuet standartnaè ssylka v ''nikuda'': NIL. Esli s:= NIL, to pere-
menno$i s budet prisvoena ssylka na opredelenny$i, ''izvestny$i'' maxine, no
fiktivny$i adres.
Vaïnaè standartnaè procedura: NEW(p), gde NEW --- imè procedury, p ---
parametr ssyloqnogo tipa. V rezul~tate raboty ffto$i procedury peremenno$i

18 CHAPTER 2. TIPY DANNYH
p budet prisvoen adres (pervogo slova) uqastka pamèti, otvedennogo \LambdaVM dlè
razmeweniè odnogo ob?ekta nekotorogo zadannogo tipa. Tip opredelèetsè v
sootvetstvii s ssylko$i p. Takim obrazom otvoditsè mesto dostatoqnoe dlè
razmeweniè ob?ekta, na kotory$i opredelena ssylka p. Obratnaè procedura
--- DISPOSE (p).
Primer. Otvedem v pamèti mesto dlè razmeweniè celogo qisla i zaxlem v
èqe$iku cifru ''5'':
TYPE ref = @INTEGER;
VAR p: ref;
BEGIN
NEW(p); p@:= 5
END.
Upraïneniè
1. Qto napeqataet programma:
TYPE ref= @REAL;
VAR s, q: ref
BEGIN
NEW(s); NEW(q)
q@:= 4.0; s:= q;
WRITE ( s@);
q@:= 5.0
WRITE ( s@)
END.
2. Sozdat~ strukturu v vide steka (po principu --- pervy$i prixel i posled-
ni$i uxel) dlè zapominaniè zaranee neizvestnogo koliqestva par celyh qisel,
ispol~zuè sleduÈwie tipy dannyh:
TYPE Stack = @Elem
Elem = RECORD n: T1;
m: T2;
ref: Stack
END;
T1 = 1..200;
T2 = -200..200;
Stek na risunke dlè danno$i zadaqi budet vyglèdit~ tak:
n m ref
-
n m ref
- -
n m ref
-
3. Analogiqno upr. 2 napisat~ programmu, kompaktno hranèwuÈ razreïen-
nuÈ matricu, t.e. matricu, soderïawuÈ oqen~ mnogo nulevyh fflementov.

Struktury dannyh
Opredelenie: Pod strukturo$i dannyh my budem ponimat~ ne tol~ko mnoïestvo
kakih-to ob?ektov, no i mnoïestvo svèze$i meïdu fftimi ob?ektami.
Primerami strukturirovannyh dannyh èvlèÈtsè: genealogiqeskoe derevo
qeloveka, soderïawee informaciÈ o ego rodstvennikah i svèzi meïdu nimi;
geografiqeskaè transportnaè karta, gde dany svedeniè o punktah i ukazany
suwestvuÈwie meïdu nimi (m.b. ne vse) dorogi; modeli sloïno$i molekuly
i t.d. Bolee prostymi strukturami èvlèÈtsè spiski ob?ektov (v qastnosti
lÈde$i) s ukazaniem ih harakteristik, katalogi i t.p.
Struktury dannyh i ih predstavlenie --- odin iz naibolee vaïnyh vop-
rosov neqislovogo programmirovaniè. Ponimanie nekotoryh aspektov fftogo
voprosa trebuet obyqno znaqitel~nyh usili$i i usloïnèetsè otsutstviem ih
èsnogo opisaniè v suwestvuÈwe$i literature.
My ostanovimsè na opredelenii osnovnyh ponèti$i, opisanii naibolee su-
westvennyh tehniqeskih detale$i predstavleniè razliqnyh struktur dannyh
(spiskov, derev~ev i t.d.) i illÈstracii raboty s nimi.
3.1 Dinamiqeskie struktury dannyh
Otmetim, qto kak qislo ob?ektov v strukturah dannyh, tak i svèzi meïdu
fftimi ob?ektami mogut izmenèt~sè so vremenem.
Naprimer, stroèt~sè novye naselennye punkty ili prokladyvaÈtsè novye
dorogi; v spiski dobavlèÈtsè ili iz spiskov isklÈqaÈtsè nekotorye qleny.
Inogda (i dostatoqno qasto) takie izmeneniè proishodèt vo vremè raboty
programmy. Takie ''nestacionarnye'' struktury dannyh vydeleny v otdel~-
ny$i klass.
Opredelenie: Dinamiqeskimi strukturami dannyh budem nazyvat~ struk-
tury, kotorye mogut sozdavat~sè, menèt~sè i uniqtoïat~sè v processe vypol-
neniè programmy.
Oqevidno, takie struktury naibolee qasto vstreqaÈtsè pri rabote prog-
ramm v real~nom vremeni.
Iz vsego mnogoobraziè vozmoïnyh struktur dannyh, voznikaÈwih v osnov-
nom iz-za razliqno$i sloïnosti svèze$i meïdu ob?ektami, my rassmotrim bolee
ili menee podrobno lix~ dva naibolee qasto vstreqaÈwihsè v programmiro-
vanii vida: line$inye spiski (i ih qastnye sluqai --- stek i oqered~) i derev~è
19

20 CHAPTER 3. STRUKTURY DANNYH
(kak harakterny$i primer, neline$inyh struktur).
3.2 Line$inye spiski
3.2.1 Opredeleniè i osnovnye operacii
Opredelenie: Line$iny$i spisok --- mnoïestvo, sostoèwee iz n fflementov (n ?
0), so sleduÈwimi svo$istvami:
1) suwestvuet pervy$i fflement (pri n ? 0);
2) dlè lÈbyh ne kra$inih fflementov suwestvuet predyduwi$i i posleduÈ-
wi$i;
3) suwestvuet posledni$i fflement (pri n ? 0).
Inymi slovami, ob?ekty line$inogo spiska svèzany lix~ s dvumè sosedni-
mi. Dannaè struktura pofftomu horoxo predstavlèetsè sprèmlenno$i posledo-
vatel~nost~È svèze$i (otsÈda i ee nazvanie):
Primery grupp ob?ektov, podpadaÈwih pod dannoe opredelenie, mnogoqis-
leny i mnogoobrazny, v qastnosti: stopka lÈbyh predmetov (naprimer, pod-
nosov), knigi, tetradi (kak spisok listov) i t.d.
Podrobnee rassmotrim oqered~ k vraqu. Oqevidno, qto zdes~ imeem mnoïes-
tvo pacientov, priqem mnoïestvo moïet byt~ i pustym. Takïe èsno, qto est~
pervy$i i posledni$i fflement, i dlè lÈbyh ne kra$inih suwestvuet predyduwi$i
i posleduÈwi$i.
Operacii, kotorye qawe vsego proizvodèt nad line$inymi spiskami, èvlè-
Ètsè:
1) prosmotr spiska i poisk fflementa;
2) vklÈqenie novogo fflementa;
3) isklÈqenie fflementa;
4) ob?edinenie dvuh spiskov v odin;
5) kopirovanie spiska i drugie operacii.
V naxem primere oqeredi k vraqu ffti operacii oznaqaÈt:
1) Kto-to hoqet uznat~, kak daleko on nahoditsè ot naqala i opraxivaet
lÈde$i (s naqala ili ot sebè k naqalu). Faktiqeski prosmatrivaè oqered~.
2) Prixel ewe odin bol~no$i (i vstal v konec oqeredi ili, esli ''po nomer-
kam'', to v seredinu!).
3) Kto-to otqaèlsè ïdat~ i uxel domo$i (ili poxel k vraqu).
4) Bylo dva vraqa i dve oqeredi, no odin vraq uxel ...
5) Ostavxi$isè posle okonqaniè priema vraqa narod skopiroval svo$i porè-
dok v spisok, qtoby v sleduÈwi$i raz vosstanovit~ porèdok ili medicinskaè
sestra vseh perepisala pered naqalom priema vraqa v porèdke oqeredi.
Vozratimsè k programmirovaniÈ. Otmetim, qto, po-vidimomu nevozmoïno
na$iti predstavlenie (strukturirovannyh) dannyh, pri kotoryh vse vozmoïnye
operacii vypolnèlis~ by odinakovo ffffektivno. Odnako, k sqast~È, v red-
kih sluqaèh trebuetsè vypolnenie vseh operaci$i, qawe neobhodimo obespeqit~
ffffektivnost~ raboty lix~ neskol~kih operaci$i. V zavisimosti ot fftogo vy-
biraÈt kak sposob predstavleniè struktury dannyh (v qastnosti, line$inogo

3.2. LINE $
INYE SPISKI 21
spiska), tak i konkretny$i podvid struktur (naprimer, dlè line$inyh spiskov
--- steki, oqeredi, deki i t.p.).
3.2.2 Sposoby predstavleniè spiskov
Suwestvuet dva osnovnyh sposoba predstavleniè spiskov: posledovatel~ny$i i
svèzny$i. Pri posledovatel~nom --- fflementy spiska raspolagaÈtsè v pamèti
\LambdaVM posledovatel~no drug za drugom; pri svèznom --- informaciè gruppi-
ruetsè v pary (naprimer, zapisi), gde odin komponent --- oqeredno$i fflement
spiska, a vtoro$i --- ssylka (adres) na paru so sleduÈwim (ili predyduwim)
fflementom. T.e. raspoloïenie v pamèti \LambdaVM fflementov line$inogo spiska
moïet byt~ predstavlenno sleduÈwim obrazom:
a) pri posledovatel~nom predstavlenii (tabliqno i risunkom):
address
m
m+c
m+2c ...
m+i*c ...
info.
a1
a2
a3 ...
ai ...
m - a1
a2
a3
...
ai
...
a1, a2, a3, ... --- fflementy spiska;
m --- adres pervogo ffelementa (a1);
c --- ob?em pamèti, otvodimy$i dlè razmeweniè odnogo fflementa.
b) pri svèznom predstavlenii (tabliqno i risunkom):
address
m1
m2
m3 ...
mi-1 ...
inform.
a1,m2
a2,m3
a3,m4 ...
ai,mi ...
m2 - a2,m3
...
m1 - a1,m2
...
m3 - a3,m4
...
gde m1, m2, m3, ... --- adresa pamèti v \LambdaVM sootvetstvuÈwih par, v koto-
ryh nahoditsè informaciè ob fflemente i adrese sleduÈwego fflementa. Pri
fftom adresa m1, m2, m3, ... mogut byt~ ne uporèdoqeny.
V podrobno rassmatrivaemom nami primere --- oqeredi k vraqu, posledo-
vatel~noe predstavlenie oznaqaet, qto lÈdi v oqeredi sidèt na line$ino ras-
poloïennyh stul~èh v pravil~nom porèdke (priqem podrèd!). Pri svèznom
predstavlenii fftogo net, t.e. narod sidit kak popalo, no u kaïdogo imeetsè
ssylka na predyduwuego (inaqe anarhiè, privodèwaè obyqno k skandalu); ffta
ssylka v dannom sluqae suwestvuet v pamèti qeloveka v vide obraza vperedi
stoèwego pacienta.
Otmetim, qto v poliklinikah, esli oqered~ dlinnaè, to stihi$ino (no daleko
ne sluqa$ino!) realizuetsè svèzno$i predstavlenie, a, naprimer, v magazine ---
obyqno posledovatel~noe. Svèzano ffto skoree vsego s tem, qto peremewat~sè

22 CHAPTER 3. STRUKTURY DANNYH
stoè legko, a sidè sloïno. Takïe i v programmirovanii pri nekotoryh uslo-
vièh okazyvaetsè predpoqtitel~nee odin vid predstavleniè, a pri drugih ---
drugo$i.
Upraïnenie. Privesti primery, kogda udobnee pol~zovat~sè svèznym pred-
stavleniem line$inogo spiska, a kogda posledovatel~nym.
Rassmotrim neskol~ko podrobnee posledovatel~ny$i sposob predstavleniè
(line$inyh) spiskov. Standartny$i sposob ego realizacii --- ispol~zovanie
massiva, dlina kotorogo bol~xe predpolagaemo$i dliny spiska (horoxo zadat~
fftu dlinu inogda byvaet trudno!).
Napixem programmu, kotoraè budet vvodit~ posledovatel~no ob?ekty (da-
ty 1 ) i stroit~ iz nih line$iny$i spisok, poka oni ne konqatsè v fa$ile datafile.
TYPE Typeofdata = ARRAY [1..3] OF 0..2005;
Seqreprs = ARRAY [1..m] OF Typeofdata;
VAR a: Typeofdata; list: Seqrepres; n: 1..m;
BEGIN
n:= 0;
WHILE NOT eof(datafile) DO
BEGIN
n:= n + 1; READ (datafile, a);
list[n]:= a
END;
END.
Posle fftih operaci$i line$iny$i spisok budet raspoloïen v pervyh n--fflementah
massiva list.
Rassmotrim kak programmno moïno realizovat~ pereqislennye vyxe ope-
racii.
1. Prosmotr --- poisk fflementa. Pust~ nuïno uznat~, est~ li (i kako$i ot
naqala) fflement, znaqenie kotorogo ravno znaqeniÈ peremenno$i indata (tipa
Typeofdata, t.e. na$iti zadannuÈ datu). Plan raboty sleduÈwi$i: esli fflemen-
tov v spiske net, to i delat~ niqego ne nado, inaqe neobhodimo prosmotret~
line$iny$i spisok s naqala, poka ne na$idem nuïny$i fflement, ili poka ne do$idem
do poslednego fflementa. Oformim poisk fflementa v vide procedury tak:
PROCEDURE Find (n: INTEGER; list: Seqrepres; indata: Typeofdata);
VAR yes: BOOLEAN; k: INTEGER
BEGIN
yes:= FALSE;
IF n=0
THEN WRITE ('list is empty')
ELSE
BEGIN
k:= 0;
WHILE (NOT yes) AND k!=N DO
BEGIN
k:= k + 1;
1 Opredelenie dannyh tipa 'data' razobrano v predyduwe$i glave v razdele ''Sostavnye tipy dannyh''.

3.2. LINE $
INYE SPISKI 23
yes:= (list [k] = indata)
END; (* while *)
END (* else *)
IF NOT yes THEN k:=0;
WRITE ( yes, 'k=', k);
END; (* Find *)
(list is empty = spisok pust)
V rezul~tate, esli v spiske fflementov net, to podprogramma napeqataet
''spisok pust'', v protivnom sluqae, esli fflement budet na$iden, to napeqataet
''TRUE k = ''porèdkovy$i nomer fflementa'''', esli fflement ne budet na$iden, to
--- ''FALSE k = 0''.
2. VklÈqenie novogo fflementa. Pust~ nuïno vstavit~ meïdu k-ym i (k +1)-
ym fflementami ewe odin (k ! n), pri fftom sleduet proverit~ ne budet li
spisok perepolnen, t.e. vyhodit~ za granicy massiva. V illÈstrativnom
primere oqeredi algoritm budet vyglèdet~ sleduÈwim obrazom: proverit~,
esli novoe qislo qelovek (n + 1) stanet bol~xe qisla stul~ev, to luqxe ni-
qego ne delat~, inaqe poprosim lÈde$i s konca oqeredi do (k + 1)-ogo qeloveka
peresaïivat~sè na sosedni$i osvoboïdaÈwi$isè stul (v obratnom napravlenii
ne vy$idet). Zatem na osvobodivxi$isè v seredine stul posadim noven~kogo.
OH Hj
1
O O O O O O O O
2 ... k
\Phi \Phi \Phi \Phi \Phi \Phi
H Hj H Hj H Hj
k+1 k+2 ... n n+1 ...
\Phi \Phi \Phi \Phi
H Hj H Hj
m
Oformim algoritm v vide procedury Putin:
PROCEDURE Putin (VAR k,n, m: INTEGER; list: Seqrepres;
indata: Typeofdata);
VAR I: INTEGER;
BEGIN
IF (n + 1) ? m
THEN WRITE ('list is full')
ELSE
BEGIN
FOR I:= n DOWNTO k+1 DO
list [I+1]:= list [I];
list [k+1]:= indata;
n:= n + 1
END (* else *)
END;
(list is full = spisok zapolnen)
3. IsklÈqenie fflementa. Pust~ neobhodimo isklÈqit~ k-y$i s naqala oqe-
redi fflement (k ? n).
V naxe$i illÈstracii ffto budet oznaqat~, qto kto-to uxel i osvobodilsè
stul. Qtoby ego ne zanèli, ''narod'' sdvigaetsè k naqalu na odno mesto.
Oformim v vide procedury Exlcude:

24 CHAPTER 3. STRUKTURY DANNYH
PROCEDURE Exlcude (VAR k, n: INTEGER; list: Seqrepres;
out: Typeofdata);
VAR i: INTEGER;
BEGIN
out:= list [k];
FOR i:= k+1 TO n DO
list [i-1]:= list [i];
n:= n - 1
END;
4. Ob?edinenie dvuh spiskov. Pust~ neobhodimo ob?edinit~ dva spiska
list1 i list2 (dva massiva razmernosti m1 i m2). Qislo fflementov v pervom
spiske --- n1, a vo vtorom --- n2. Ob?edinenie proizvedem v odin massiv list1.
Primerom slièniè oqerede$i k vraqu moïet byt~ prisoedinenie odno$i k
drugo$i, esli hvatit stul~ev, t.e. n1 + n2 men~xe ili ravno m1. Esli stul~ev
ne hvatit, to togda ...! V programme ïe, esli fftot sluqa$i ne predusmotret~,
to proizo$idet vyhod za ramki massiva, qto privedet k ee avari$inomu zaver-
xeniÈ 2 .
Oformim dannuÈ operaciÈ v vide procedury Unit:
PROCEDURE Unit (VAR n1, n2, m1: INTEGER;
list1, list2: Seqrepres);
VAR i: INTEGER
BEGIN
IF n1+n2 ? m1
THEN WRITE ('merging is impossible')
ELSE
BEGIN
FOR i:= n1+1 TO n1+n2 DO
list1 [i]:= list2 [i-n1];
n1:= n1 + n2
END (* else *)
END;
(merging is impossible = ob?edinenie ne vozmoïno)
5. Kopirovanie spiskov --- peqat~. V primere, esli oqeredi net, to vraq
svoboden, v protivnom sluqae medicinskaè sestra perepixet lÈde$i v porèdke
oqeredi.
Oformim ffto v vide podprogrammy Copylist:
PROCEDURE Copylist (n: INTEGER; list: Seqrepres);
VAR i: INTEGER
BEGIN
IF n = 0
THEN WRITE ('list is empty')
ELSE
2 Esli programma budet napisana na Fortrane, to vyhod za granicy massiva moïet privesti k potere
informacii sosednih s massivom pole$i i prodolïeniem raboty vaxe$i programmy. Avari$iny$i ostanov
programmy vozmoïen sovsem v drugo$i qasti programmy i poisk ffto$i oxibki dovol~no sloïen.

3.2. LINE $
INYE SPISKI 25
FOR i:= 1 TO n DO
WRITE (list [i])
END;
(list is empty = spisok pust)
Zametim, qto kopirovanie (peqat~) massiva (dlè posledovatel~nogo pred-
stavleniè line$inogo spiska) vozmoïno lix~ ukazannym obrazom, t.e. po ffle-
mentam.
Podvedem itogi rassmotreniè posledovatel~nogo predstavleniè spiskov.
Osnovnye trudnosti voznikaÈt pri neopredelenno$i dline spiska, t.k. v fftom
sluqae ne èsno kako$i razmernosti brat~ massiv. Takïe sleduet otmetit~, qto
osnovnaè operaciè --- peresylka. Pri dlinnyh spiskah ffta operaciè moïet
potrebovat~ mnogo processornogo vremeni \LambdaVM.
Teper~ rassmotrim svèzny$i sposob predstavleniè spiskov. Kak otmeqalos~
v naqale p. 3.2.2, nuïno sozdat~ pary: fflement + ssylka na sleduÈwi$i (ili
predyduwi$i). Dlè fftogo obyqno ispol~zuÈt zapisi i ssylki na nih sleduÈ-
wim obrazom:
TYPE Typeofdata = ARRAY [1..3] OF 0..2005;
Relrepes = @Element;
Element = RECORD data: Typeofdata;
link: Relrepes
END;
VAR list, ref: Relrepes; a: Typeofdata;
V peremenno$i list budem hranit~ ssylku na posledni$i fflement line$inogo
spiska (analog peremenno$i n pri posledovatel~nom predstavlenii).
Sozdanie spiska, analogiqnoe vypolnennomu vyxe dlè posledovatel~nogo
predstavleniè, budet imet~ vid:
BEGIN
list:= NIL;
WHILE eof (file) DO
BEGIN
NEW (ref); READ (a);
ref@.data:= a; ref@.link:= list;
list:= ref
END (* while *)
END.
Teper~ u nas est~ line$iny$i svèzny$i spisok, kotory$i, qtoby ego ne poterèt~,
''zaceplen za konec'' peremenno$i link.
link - - - - - - nil
Rassmotrim programmnuÈ realizaciÈ pereqislennyh ranee operaci$i. Kak
i pri posledovatel~nom predstavlenii oformim ih v vide procedur.
1. Poisk fflementa --- prosmotr. Delaetsè takïe, kak i pri posledovatel~-
nom predstavlenii.

26 CHAPTER 3. STRUKTURY DANNYH
PROCEDURE Findconn (list: Relrepes; indata: Typeofdata);
VAR ref: Relrepes;
BEGIN
ref= list;
IF ref=NIL
THEN WRITE ('list is empty')
ELSE
WHILE (ref@.data !? indata) OR (ref !? NIL) DO
ref:= ref@.link;
(* ref:= ref@.link --- oqen~ vaïnaè operaciè -- analog i:= i+1,
oznaqaÈwaè perehod k sleduÈwemu fflementu *)
IF ref@.data !? NIL
THEN WRITE ('element is found')
ELSE WRITE ('no such element in the list')
END;
(list is empty = spisok pust;
element is found = fflement na$iden;
no such element in the list = fflementa v spiske net)
Vstavit~ novy$i fflement za fflementom, na kotory$i ukazyvaet ssylka here.
Sdelaem ffto tak, esli ispol~zovat~ nax primer oqeredi k vraqu: sprosim u
otmeqennogo, kto nahoditsè pered nim i noven~komu skaïem, qto on za fftim
qelovekom, a otmeqennomu, qto on za noven~kim.
here -
-
new -
- - -
PROCEDURE Putinconn (VAR here: Relrepes; indata: Typeofdata);
VAR new, next: Relrepes;
BEGIN
NEW (elnew); elnew@.data:= indata;
next:= here@.link;
elnew@.link:= next;
here@.link:= elnew
END;
3. IsklÈqenie fflementa. IsklÈqim fflement, sleduÈwi$i za fflementom
ukazannom v ssylke here. Kak ffto sdelat~, oqevidno iz sleduÈwego risunka:
here - - - - -

3.2. LINE $
INYE SPISKI 27
PROCEDURE Exclconn (VAR here: Relrepes);
VAR next: Relrepes;
BEGIN
next:= here@.link;
here@.link:= next@.link;
DISPOSE (next)
END;
4. Ob?edinenie dvuh spiskov. Pust~ v peremennyh l1begin, l1end i l2begin,
l2end --- ssylki na naqalo i konec dvuh spiskov. Sleduet vypolnit~ sleduÈwee
soedinenie:
-
l2begin -
-
?
nil l1end -
- -
PROCEDURE Unitconn (VAR l2begin, l1end: Relrepes);
BEGIN
l2begin@.link:= l1end
END;
Posle vypolneniè ffto$i procedury spiski budut svèzany v odin, priqem v
l1begin budet ssylka na naqalo, a v l2end --- na konec ob?edinennogo spiska.
5. Kopirovanie spiska.
PROCEDURE Copyconn (list: Relrepes);
VAR next: Relrepes;
BEGIN
next:= list;
IF next = NIL
THEN WRITE ('list is empty')
ELSE
REPEAT
WRITE (next@.data); next:= next@.link
UNTIL next = NIL
END;
(list is empty = spisok pust')
RezÈmiruem sravnitel~noe rassmotrenie realizaci$i operaci$i pri razliq-
nyh predstavlenièh spiskov:
--- prosmotr i kopirovanie spiskov realizuetsè primerno odinakovo;
--- ob?edinenie spiskov suwestvenno ffffektivnee moïno sdelat~ pri svèz-
nom ih predstavlenii (vsego odna operaciè!) 3 ;
--- vklÈqenie i isklÈqenie fflementov v nekotorom smysle ffffektivnee pri
svèznom predstavlenii (t.k. net mnogoqislennyh peresylok daqnnyh, no vygo-
da zdes~, veroètno, neznaqitel~no prevoshodit otricatel~nuÈ storonu: nep-
rivyqnost~ i neoqevidnost~ svèznogo predstavleniè);
3 V sluqae, esli ob?edinenie proishodit po kakomu-to pravilu (naprimer v porèdke vozrastaniè ffle-
mentov), to ffffektivnost~ primerno odinakovaè.

28 CHAPTER 3. STRUKTURY DANNYH
Moïno sdelat~ sleduÈwie vyvody:
1) Esli v osnovnom predstoit vypolnèt~ operacii tipa prosmotra, ili
vklÈqeniè i isklÈqeniè, to vozmoïno ispol~zovanie lÈbogo predstavleniè.
2) Esli operacii ob?edineniè spiskov ili nekotorye modifikacii vklÈ-
qeniè ili isklÈqeniè igraÈt glavnuÈ rol~, to ispol~zovanie svèznogo pred-
stavleniè moïet sposobstvovat~ sozdaniÈ suwestvenno bolee ffffektivnyh prog-
ramm.
Otmetim, qto v nekotoryh èzykah programmirovaniè (Fortran, Algol-60 i
dr.) net prèmo$i vozmoïnosti raboty so ssylkami, no svèznoe predstavlenie,
esli nemnogo potrudit~sè, smodelirovat~ moïno.
3.2.3 Qastnye sluqai line$inyh spiskov: stek, oqered~, dek
V programmirovanii naibolee qasto ispol~zuÈtsè neskol~ko qastnyh sluqaev
line$inyh spiskov, kogda dopolnitel~no k svo$istvam opredeleniè na struktury
dannyh nakladyvaÈtsè novye ograniqeniè.
Opredelenie: Stekom budem nazyvat~ line$iny$i spisok, v kotorom vse vklÈ-
qeniè i isklÈqeniè fflementov razrexeno proizvodit~ tol~ko na odnom konce
(sqitaetsè, qto vklÈqenie i isklÈqeniè samye qastye (osnovnye) operacii!).
Primery --- magazin avtomata s patronami, ïeleznodoroïny$i sostav vago-
nov v tupike i t.d.
oe -
Opredelenie: Oqered~ --- line$iny$i spisok, v kotorom vse vklÈqeniè pro-
izvodètsè na odnom konce, a isklÈqeniè --- na drugom.
Primerom èvlèetsè lÈbaè oqered~, esli ne razrexeno novye fflementy vstav-
lèt~ i isklÈqat~ iz serediny.
- -
Opredelenie: Dek --- line$iny$i spisok, gde isklÈqeniè i vklÈqeniè proiz-
vodètsè s oboih koncov.
Primer prosto$i i ne iskusstvenny$i privesti trudno, nekotoruÈ analogiÈ
imeet vhod i vyhod iz vagona fflektriqki.
-
oe -
oe
Otmetim, qto nad stekom, oqered~È i dekom mogut proizvodit~sè raznoob-
raznye operacii, vklÈqaè pereqislennye vyxe dlè line$inyh spiskov. Odna-
ko, iz dannyh opredeleni$i èsno, qto dannye qastnye sluqai line$inyh spiskov
orientirovanny na situacii, kogda v osnovnom proizvodètsè operacii vklÈ-
qeniè i isklÈqeniè fflementov. Specifiqnost~ fftih operaci$i (mesto vypol-
neniè) delaet bolee udobnym svèznoe predstavlenie (sm. vyvody v p. 3.2.2),
hotè posledovatel~noe predstavlenie ne isklÈqeno.
My rekomenduem ispol~zovat~ sleduÈwi$i porèdok svèzi fflementov.
Dlè steka:

3.2. LINE $
INYE SPISKI 29
-
oe
p - - -
x(n) x(n-1)
- - -
x(3) x(2) x(1)
nil
gde p --- peremennaè ssyloqnogo tipa, v kotoro$i hranitsè adres verhnego
fflementa steka, x --- dannye v spiske. VklÈqenie i isklÈqenie fflementov pro-
izvoditsè so storony verhnego fflementa, pri pomowi operatorov:
(vklÈqenie) NEW(s); s@.link:= p; p:= s
(isklÈqenie) s:= p; p:= p@.link; DISPOSE (s)
Dlè oqeredi 4 :
-
pn -oe oe oe
oe
nil
oe oe oe p1
-
gde v peremennyh ssyloqnogo tipa p1 i pn budem hranit~ adresa sootvets-
tvenno pervogo i poslednego fflementa oqeredi.
VklÈqenie (so storony poslednego fflementa) i isklÈqenie (so storony
pervogo) proizvoditsè sleduÈwim obrazom:
(vklÈqenie) NEW (s); s@.link:= pn; pn:= s
(isklÈqenie) s:= p1; p1:= p1@.link; DISPOSE (s)
Dlè deka:
-
oe
pl -oe - oe
oe
nil
- oe - oe
pr
- nil
-
oe
gde pl i pr --- ssylki na levy$i i pravy$i konec deka, i t.k. isklÈqenie i vklÈ-
qenie fflementov vozmoïno s oboih koncov, to prihoditsè nekotorym obrazom
sovmestit~ stek i oqered~, sozdavaè tak nazyvaemy$i 'dvuhsvèzny$i' line$iny$i
spisok.
Teper~ o tom, gde i kak ispol~zuÈtsè rassmotrennye vyxe qastnye slu-
qai line$inyh spiskov. Steki i oqeredi primenèÈtsè v teh sluqaèh, kogda
proishodit vyborka ob?ektov iz nekotorogo ih mnoïestva dlè dal~ne$ixe$i ih
obrabotki. Naprimer, iz ogromnyh zvezdnyh katalogov obyqno vybiraetsè
nekotoraè gruppa zvezd po kakim-to priznakam (naprimer, odin spektral~ny$i
klass, raspoloïenie v zadanno$i plowadke neba i t.p.) dlè dal~ne$ixe$i ih sta-
tistiqesko$i ili drugo$i obrabotki. Pri fftom qasto nevaïno, qto ispol~zovat~
stek ili oqered~ (hotè i prinèto stroit~ stek).
Inaè situaciè, kogda programma rabotaet v reïime real~nogo vremeni.
Qasto zdes~ voznikaet neobhodimost~ obrazovyvat~ iz ob?ektov line$iny$i spi-
sok, priqem tak, qto pribyvxi$i pervym fflement uhodil by (obrabatyvalsè)
toïe pervym. \Lambdatot princip realizuetsè v oqeredi (v steke pravilo --- pervym
prixel i poslednim uxel).
T.o. pri rabote s dannymi bol~xogo ob?ema, a takïe v translètorah, tek-
stovyh redaktorah i vo mnogih drugih programmnyh sredstvah ispol~zuÈtsè
steki.
4 Otmetim obratnoe napravlenie svèzi fflementov v oqeredi po sravneniÈ so stekom, qto opredelèetsè
izmeneniem napravleniè ''stoka'' fflementov.

30 CHAPTER 3. STRUKTURY DANNYH
Dlè funkcioniruÈwe$i v real~nom vremeni sistemno$i programmy, upravlè-
Èwe$i processom obrabotki programm pol~zovatele$i \LambdaVM (i nazyvaemo$i ope-
racionno$i sistemo$i), sozdaÈtsè oqeredi: oqered~ zadani$i dlè vypolneniè ih
central~nym processorom \LambdaVM, vyhodnye oqeredi dannyh i t.p.
Dek ispol~zuetsè znaqitel~no reïe, qem oqered~ i steki.
3.3 Rekursivny$i sposob raboty so spiskami
Pri rabote so spiskami (s line$inymi v men~xe$i stepeni, s neline$inymi ---
v bol~xe$i) okazyvaetsè ffffektivnym ispol~zovanie rekursii. Poèsnim, qto
ffto oznaqaet. Otmetim snaqala, qto v matematike dovol~no qasto vstreqa-
Ètsè rekurrentnye sootnoxeniè posledovatel~noste$i i funkci$i. Naprimer,
funkciè faktorial qisla moïet byt~ opredelena tak:
n! =
(
1 pri n = 0
n(n \Gamma 1)! pri n ? 0 (3:1)
V nekotoryh èzykah programmirovaniè (v Paskale --- da, v Fortrane ---
net!) dopuskaetsè analogiqnoe de$istvie, nazyvaemoe rekursie$i i zaklÈqaÈ-
weesè v obrawenii podprogrammy samo$i k sebe. Takim obrazom, podprogramma
--- funkciè vyqisleniè n-ogo qisla Fibonaqqi na èzyke Paskal~ moïet imet~
sleduÈwi$i vid:
FUNCTION Fib (n: INTEGER) : INTEGER;
BEGIN
IF n=0
THEN Fib:= 0
ELSE IF n=1
THEN Fib:= 1
ELSE Fib:= Fib(n-1) + Fib(n-2)
END;
Otmetim posledni$i operator prisvaivaniè, gde sleva stoit imè funkcii,
vyqislèemo$i s ispol~zovaniem ffto$i ïe procedury-funkcii(!).
Rassmotrim, kak budet rabotat~ dannaè podprogramma pri takom obrawe-
nii k ne$i: m:= Fib (4). Naqinaè, vhodim v podrogrammu Fib so znaqeniem for-
mal~nogo parametra n ravnym 4. Vstrqaem obrawenie Fib (n-1), kotoroe snova
vyzyvaet naxu podprogrammu. Pri fftom \LambdaVM zapomnit adres toqki vozrata
v podrogrammu Fib, znaqeniè lokal~nyh dlè Fib peremennyh i ewe koe-qto i
perehodit snova na naqalo podprogrammy Fib, no uïe dlè novogo znaqeniè n
= 4 \Gamma 1 = 3 i

3.3. REKURSIVNY $
I SPOSOB RABOTY SO SPISKAMI 31
Fib
n=4
\Gamma
\Gamma
\Gamma
\Gamma
\Gamma \Gamma`
XXXXX Xz
Fib
n=3
\Gamma
\Gamma
\Gamma
\Gamma
\Gamma \Gamma`
ÈÈÈÈÈ È:
È
È
È
È
È
È9
Fib
n=2
\Phi \Phi \Phi \Phi \Phi \Phi*
XXXXX Xz
@
@
@
@
@
@I
Fib
n=2
\Phi \Phi \Phi \Phi \Phi \Phi*
XXXXX Xz
È
È
È
È
È
È9
Fib
n=1
H
H
H
H
H
HY
Fib
n=1
X
X
X
X
X
Xy
Fib
n=0
@
@
@
@
@
@I
Fib
n=1
X
X
X
X
X
Xy
Fib
n=0
@
@
@
@
@
@I
i t.d. do n=1. K fftomu momentu v pamèti maxine budet zapisano tri toqki
vozvrata, tri varianta znaqeni$i lokal~nyh peremennyh, pri kotoryh proi-
zoxlo sleduÈwee obrawenie k Fib, i ewe koe-qto toïe tri raza (otmetim,
kstati, qto operacionnaè sistema pri orbabotke rekursivno$i programmy bu-
det ispol~zovat~ steki!).
Pri n=1 podprogramma-funkciè vyqislit svoe znaqenie Fib bez novogo ob-
raweniè k samo$i sebe (t.k. Fib(1) = 1) vozrawaetsè v tret~È toqku vozrata
(n=2), posle qego, prodolïiv operator sloïeniè (Fib(n-1) + Fib(n-2)), proizo$i-
det snova obrawenie k Fib (na tret~em urovne vloïeniè) s n=0. Vy$idè iz fftogo
obraweniè (t.k. Fib(0) = 1), my proizvedem sloïenie Fib(1) + Fib(0) i poluqim
znaqenie funkcii Fib pri n=2 i vy$idem iz Fib dlè n=2 i t.d., kak ffto pokazano
na risunke.
Iz rassmotrennogo primera stanovètsè èsnymi preimuwestva i nedostatki
rekursivnogo sposoba programmirovaniè. Poloïitel~ny$i moment sostoit v
tom, qto programma adekvatno otraïaet algoritm rexeniè zadaqi pri suwes-
tvovanii rekurrentnyh formul. I pofftomu ona prosta i, kak sledstvie, menee
podverïena vozmoïnomu privneseniÈ programmistom oxibok. Otricatel~ny$i
moment v tom, qto pri bol~xom qisle obraweni$i podprogrammy samo$i k sebe
(bol~xo$i tak nazyvaemaè 'glubine rekursii') moïet proishodit~ neopravdan-
noe i oqen~ ser~eznoe (ffksponencial~noe!) uveliqenie zatrat pamèti \LambdaVM i
vremeni sqeta.
Al~ternativo$i rekursii èvlèetsè iteraciè. Ponètie iteracii vstreqaetsè
dostatoqno qasto i opredelèt~ ego, po-vidimomu, net neobhodimosti. Poèsnim
lix~ na primere vyqisleniè qisel Fibonaqqi:
FUNCTION Fib2 (m: INTEGER) : INTEGER;
VAR i, i1, i2, io: INTEGER;
BEGIN
IF m=0
THEN Fib:= 0
ELSE

32 CHAPTER 3. STRUKTURY DANNYH
IF m=1
THEN Fib2:= 1
ELSE
BEGIN
i:= 1; i1:= 1; i2:= 0;
WHILE i!m DO
BEGIN
io:= i1 + i2;
Fib2:= io;
i2:= i1; i1:= io;
i:= i + 1
END (* while *)
END (* else *)
END;
Zdes~ pri m ? 2 v cikle WHILE rovno m \Gamma 2 raza budet primenètsè re-
kurrentnaè formula. V otliqie ot rekursivno$i podprogrammy, vyqisleniè v
Fib2 budut naqinat~sè s vyqisleniè pervyh qlenov posledovatel~nosti qisel
Fibonaqqi, t.e. dlè i = 1, 2, 3 i t.d. do m. Pri fftom v peremennyh io, i1 i i2
budut zapominat~sè znaqeniè qisel Fib(i), Fib(i-1) i Fib(i-2).
Otmetim, qto iteracionnaè versiè (Fib2) neskol~ko sloïnee i suwestvenno
menee naglèdna, qem rekursivnaè Fib.
Odnako otvet na obwi$i vopros --- kako$i iz metodov vyqisleni$i: rekursiÈ
ili iteraciÈ ispol~zovat~ v tom ili inom sluqae? --- okazyvaetsè neskol~ko
neoïidannym: rekursii sleduet izbegat~ v teh sluqaèh, kogda est~ oqevidnoe
iterativnoe rexenie zadaqi.
\Lambdatot neblagopriètny$i dlè rekursii vyvod, odnako smègqim zameqaniem o
tom, qto dostatoqno qasto dat~ iterativnoe rexenie oqen~ ne prosto. Prime-
rami takih sluqaev èvlèetsè rabota s neline$inymi (v qastnosti vetvèwimi-
sè) strukturami (sm. p. 3.4) ili zadaqi tipa rassmotrenno$i niïe ''zadaqi o
hano$isko$i baxne''.
Dlè line$inyh spiskov ispol~zovanie rekursii ne tak ffffektivno. Rassmot-
rim, naprimer, operaciÈ poiska fflementa v line$inom spiske. Iterativnoe
rexenie dano vyxe. Rekursivnoe dlè posledovatel~nogo i svèznogo predstav-
leniè vyglèdit sleduÈwim obrazom 5 :
posledovatel~noe svèznoe
?????????????????????????????I????????????????????????????????
I
PROCEDURE I PROCEDURE
Search (n: INTEGER; I Search1 (x: Typeofdata;
list: Seqrepres I ref: Relrepres;
x: Typeofdata); I VAR here: Relrepres);
VAR k: INTEGER; I
BEGIN I BEGIN
IF list [k] = x I IF ref@.Data = x
THEN WRITE (k) I THEN s:= ref
5 Imena peremennyh ispol~zovany te ïe qto i ranee.

3.3. REKURSIVNY $
I SPOSOB RABOTY SO SPISKAMI 33
ELSE I ELSE
IF k != N I IF ref@.link !? NIL
THEN Search (N, I THEN Search1 (x,
list, x, k-1) I ref@.link, here)
ELSE WRITE ('no') I ELSE WRITE ('no')
END; I END;
I
Obrawenie :
k:=1; Search (n, list, x, k);I Search1 (ref, x, here);
?????????????????????????????I?????????????????????????????????
Poskol~ku iterativnoe rexenie zadaqi dostatoqno prosto (priqem daïe
prowe rekursivnogo!), to soglasno naxe$i rekomendacii predpoqtitel~nee dlè
analogiqnyh zadaq ispol~zovat~ iterativnye algoritmy. Otmetim, odnako,
qto i dlè line$inyh spiskov v nekotoryh sluqaèh moïet byt~ bolee udobnym
primenenie rekursii.
Teper~ rassmotrim sluqa$i, gde bez rekursii obo$itis~ qrezvyqa$ino zatrud-
nitel~no --- zadaqu o ''hano$isko$i baxne''. Ona formuliruetsè tak:
Soglasno drevne$i legende, v nekotorom hrame nahoditsè bronzovaè plita s
tremè sterïnèmi. Na odin iz sterïne$i Bog pri sotvorenii mira nanizal 64
diska raznogo diametra iz qistogo zolota tak, qto naibol~xi$i disk nahoditsè
na bronzovo$i plite, a ostal~nye obrazuÈt piramidu, suïaÈwuÈsè k verhu.
Rabotaè den~ i noq~ ïrecy perenosèt diski s odnogo sterïnè na drugo$i po
sleduÈwim pravilam: diski moïno peremewat~ so sterïnè na sterïen~ tol~-
ko po odnomu i nel~zè klast~ bol~xi$i disk na men~xi$i. Izvestno, qto kogda
ïrecy perenesut vse 64 diska s odnogo sterïnè na drugo$i, ispol~zuè treti$i
sterïen~, nastupit konec sveta.
Vopros: kak (v kako$i posledovatel~nosti) ïrecy dolïny perenosit~ diski
(lÈbopytno, takïe, ocenit~, kogda moïno ïdat~ okonqaniè ih raboty!).
Rexenie zadaqi iteracièmi otyskat~ sovsem neprosto, v to vremè kak re-
kursiè daet qrezvyqa$ino korotkoe (i fflegantnoe!) rexenie. Ono faktiqeski
sostoit v neobhodimosti perenosa piramidy iz m \Gamma 1 diska (kstati, dlè m = 2
perenos piramidy iz m \Gamma 1 diska est~ prosto perenos diska!).
Rexenie ffto$i podzadaqi takovo:
1) perenesti piramidu iz m \Gamma 1 diska s igly A na iglu C, ispol~zuè iglu
B.
2) perenesti ostavxi$isè na igle A niïni$i disk na iglu B.
3) perenesti piramidu iz m \Gamma 1 diska s igly C na iglu B.
A B C
-
A B C
-

34 CHAPTER 3. STRUKTURY DANNYH
A B C
-
A B C
Netrudno napisat~ rekursivnuÈ podprogrammu, realizuÈwuÈ fftot algo-
ritm 6 :
PROGRAM Han;
VAR f: TEXT; i: INTEGER;
(* procedura perenosa baxni s n-kol~cami s c1 na c2, pol~zuès~ c3 *)
PROCEDURE Hanoi (n: INTEGER; c1, c2, c3: CHAR);
BEGIN
IF n !? 0 THEN
BEGIN
(* perenosim baxnÈ iz n \Gamma 1 kol~ca s c1 na c3, pol~zuès~ c2 *)
Hanoi (n-1, c1, c3, c2);
(* perenosim n-oe kol~co na c2, t.e. na zadannoe mesto *)
WRITE (f, 'ring n=', n:2, ' from ', c1, ' to ', c2);
(* perenosim baxnÈ iz n \Gamma 1 kol~ca s c3 na c2, pol~zuès~ c1 *)
Hanoi (n-1, c3, c2, c1)
END (* if *)
END; (* Hanoi *)
BEGIN
REWRITE (f, 'Lr:');
i:= 2;
Hanoi (i, 'A', 'B', 'C')
END.
Rabota danno$i programmy privedet k tomu, qto budet napeqatano oqevidnoe
rexenie: kol~co n= 1 perenesti s igly A na iglu C kol~co n= 2 perenesti s
igly A na iglu B kol~co n= 1 perenesti s igly C na iglu B
Napomnim, qto kol~ca my pronumerovali sverhu vniz, t.e. nomer 1 imeet
naimen~xee kol~co.
Stoit otmetit~, qto pri n = 2 potrebovalos~ 3 peremeweniè, pri n = 3 pot-
rebuetsè uïe 7 i t.d. T.o., qislo peremeweni$i ravno 2 n \Gamma 1. Sledovatel~no, pri
n = 64 qislo peremeweni$i budet ravno porèdka 2 64 ili 10 19 i esli odno kol~co
perenosit~ za 1 sekundu, to rabota potrebuet okolo 3 10 11 let, t.e. vremè,
bol~xee vozrasta Galaktiki i sravnimoe s kosmologiqeskim. Pofftomu poka
moïno ïit~ spoko$ino, u ïrecov vperedi ewe mnogo raboty.
6 Dannaè programma proverena na SM-4.

3.4. NELINE $
INYE STRUKTURY DANNYH: DEREV~? I GRAFY 35
3.4 Neline$inye struktury dannyh: derev~è i grafy
Ne vyzyvaet somneniè tot fakt, qto vozmoïnye struktury dannyh ne ograni-
qivaÈtsè line$inymi, rassmotrennymi vyxe. Real~nye ob?ekty mogut potre-
bovat~ sozdanie dostatoqno sloïnyh struktur dannyh, naprimer, pri pred-
stavlenii transportnyh shem ili sloïnyh molekul. V fftih sluqaèh mogut
imet~ mesto i takie netrivial~nye struktury:
\Gamma
\Gamma
\Gamma
\Gamma \Gamma
H H H H H
@
@
@
\Delta
\Delta \Delta
A
A A \Delta
\Delta \Delta
A
A A
Opredelenie: Struktury dannyh, fflementy kotoryh svèzany proizvol~nym
obrazom, budem nazyvat~ grafami.
Line$inye spiski --- qastny$i sluqa$i grafa. Niïe my rassmotrim i drugo$i
qastny$i sluqa$i grafov --- derev~è, èvlèÈwiesè neline$inymi strukturami.
Nesmotrè na to, qto princip svèzi meïdu fflementami struktury dannyh tipa
dereva legko ponèt~ iz sleduÈwego risunka,
@ @
\Gamma \Gamma
\Gamma \Gamma
@ @
\Gamma \Gamma@ @
\Gamma \Gamma
@ @
\Gamma \Gamma
my dadim strogoe, formal~noe opredelenie.
Opredelenie: Derevom budem nazyvat~ strukturu dannyh, ob?edinèÈwuÈ
koneqnoe mnoïestvo fflementov T, gde T ne pusto, tak qto:
1) imeetsè vydelenny$i fflement, nazyvaemy$i kornem;
2) ostal~nye fflementy soderïatsè v m ? 0 poparno ne peresekaÈwihsè
mnoïestvah T1, T2, T3, ..., Tm, kaïdoe iz kotoryh èvlèetsè derevom (toqnee
podderevom).
Koneqnye fflementy vetve$i derev~ev budem nazyvat~ list~èmi, a ostal~nye
--- uzlami.
Otmetim vaïnuÈ detal~ opredeleniè --- ispol~zovanie rekursii (derevo
opredelèetsè qerez ponètie dereva, priqem dostatoqno fflegantno!). Pofftomu
neudivitel~no, qto mnogie operacii nad derev~èmi ffffektivnee realizuÈtsè
pri ispol~zovanii rekursivnyh algoritmov.
Primery derev~ev:
--- genealogiqeskie derev~è, stroèwiesè ot sub?ekta (koren~) s ukazaniem
dvoih roditele$i, roditele$i roditele$i i t.d.;

36 CHAPTER 3. STRUKTURY DANNYH
@ @
\Gamma \Gamma
@ @
\Gamma \Gamma
@ @
\Gamma \Gamma
--- varianty vozmoïnyh hodov v xahmatah i drugih igrah;
--- shema vyqisleniè qisel Fibonaqqi s ispol~zovaniem rekursivnyh pod-
programm.
V pervom i tret~em primere ispol~zuetsè derevo, imeÈwee special~noe
nazvanie, a imenno --- binarnoe, t.e. takoe derevo, u kotorogo iz kaïdogo uz-
la vyhodit ne bolee dvuh vetve$i. Niïe my v osnovnom budem rassmatrivat~
imenno fftot vid derev~ev.
Kak i line$inye spiski derev~è mogut byt~ realizovany v programmirova-
nii putem ispol~zovaniè kak posledovatel~nogo, tak i svèznogo predstavleniè.
Otmetim, qto posledovatel~noe predstavlenie budet ispol~zovat~ bolee od-
nogo massiva. Tak naprimer binarnoe derevo moïno realizovat~ pri pomowi
treh massivov:
1) massiv, kaïdy$i fflement kotorogo soderïit informaciÈ ob odnom uzle
dereve;
2) massiv, k-y$i fflement kotorogo soderïit informciÈ (indeksy pervogo
massiva) o nahoïdenie levogo uzla k-ogo fflementa pervogo massiva;
3) massiv, k-y$i fflement kotorogo soderïit analogiqnuÈ informaciÈ, qto
i vtoro$i, no o pravom uzle k-ogo fflementa.
knot
a1
a2
a3
a4
a5
a6
left
2
4
5
0
0
0
right
3
0
6
0
0
0
a1
H H Hj
\Phi
\Phi
\Phiï
a2
\Phi
\Phi
\Phiï
a3
H H Hj
\Phi
\Phi
\Phiï
a4 a5 a6
Svèznoe predstavlenie pozvolèet suwestvenno bolee adekvatno predstavit~
derevo i v dal~ne$ixem my budem ispol~zovat~ lix~ fftot vid predstavleniè.
Binarnoe derevo moïno predstavit~ naprimer tak:
a2
-
L
a1
- -
a3
gde kaïdy$i uzel soderïit sleduÈwuÈ informaciÈ: ob fflementah dereva
(a1, a2, ...) i ssylki na sootvetstvuÈwie uzly levogo poddereva i pravogo
poddereva. L --- ssylka na koren~ dvoiqnogo dereva.
Dlè opisaniè informacii, po-vidimomu, udobno vospol~zovat~sè kombini-
rovannym tipom (zapisèmi), gde dva polè ssyloqnogo tipa (na ffti zapisi),

3.4. NELINE $
INYE STRUKTURY DANNYH: DEREV~? I GRAFY 37
a odno ili neskol~ko pole$i otvodètsè dlè informacii ob fflementah dereva.
Tip fftih pole$i zavisit ot dannyh.
Operacii nad derev~èmi vypolnèÈtsè te ïe, qto i nad line$inymi spiskami,
no naibolee vaïno$i iz nih na fftot raz stanovit~sè qastny$i sluqa$i prosmotra
--- obhod dereva 7 .
Opredelenie: Obhod dereva --- tako$i ego prosmotr, kogda kaïdy$i uzel de-
reva analiziruetsè odin (i tol~ko odin) raz.
OsnovnuÈ qast~ algoritma obhoda dereva udobno sformulirovat~ v rekur-
sivnom vide:
obo$iti derevo =
obo$iti levoe podderevo
proanalizirovat~ koren~
obo$iti pravoe podderevo
\Lambdato tak nazyvaemy$i ''obratny$i'' porèdok obhoda, no mogut byt~ i drugie.
Pokaïem rabotu algoritma na primere sleduÈwego dereva, predstavlèÈ-
wego nekotoroe algebraiqeskoe vyraïenie:
\Lambda
H H Hj
\Phi
\Phi
\Phiï
=
H H Hj
\Phi
\Phi
\Phiï
w
x +
H H Hj
\Phi
\Phi
\Phiï
y z
Esli pod analizom uzla ponimat~ peqat~ uzla, to primenenie algoritma
obhoda dast vyraïenie: (X=(Y +Z)) \Lambda W , gde skobki oznaqaÈt uroven~ glubiny
rekursii.
SootvetstvuÈwaè programma na èzyke paskal~ budet imet~ vid:
(* procedura peqati dvoiqnogo dereva *)
PROCEDURE Pr (p: ref);
BEGIN
IF p !? NIL THEN
BEGIN
Pr (p@.left);
WRITE (f, p@.key: 4);
Pr (p@.right)
END (* if *)
END;
Porèdok raboty ffto$i procedury analogiqen podrobno rassmotrennomu na-
mi dlè rekursivno$i procedury Fib, vyqislèÈwe$i znaqeniè qisel Fibonaqqi,
i Hanoi, rexaÈwe$i zadaqu o hano$isko$i baxne.
O drugih operacièh zametim sleduÈwee:
1) prosmotr --- poisk fflementa analogiqen obhodu;
7 V dal~ne$ixem, vse operacii budut proizvolitsè s binarnymi derev~èmi i v celèh kratkosti termin
binarnye budet opuwen.

38 CHAPTER 3. STRUKTURY DANNYH
2) vklÈqenie novogo fflementa --- zamenu lista poddereva sdelat~ prosto, a
dobavlenie novogo uzla --- neskol~ko sloïnee;
3) isklÈqenie fflementa--lista --- prosto, a uzla iz serediny --- sloïno
(priqem nuïno ukazat~ special~nye pravila kak ffto delat~!);
4) ob?edinenie derev~ev v odno, esli vklÈqenie kornè odnogo iz derev~ev
v kaqestve lista drugogo vozmoïno, sdelat~ legko;
5) kopirovanie dereva --- ffkvivalentno obhodu.
Process vklÈqenie novyh list~ev proillÈstriruem na primere sleduÈ-
we$i programmy postroeniè dereva. Pust~ imeetsè nekotory$i stek s celymi
qislami (grubo govorè fa$il). Napixem programmu, stroèwuÈ takoe derevo,
qto v levyh podderev~èh budut qisla men~xie, qem v korne, a v pravom ---
bol~xie 8 . Naprimer dlè posledovatel~nosti 5, 3, 9, 6, 4, 10 dolïno byt~
postroeno sleduÈwee derevo:
5
\Phi
\Phi
\Phi
\Phiï
H H H Hj
3
@
@R
4
9
@
@R
\Gamma
\Gamma\Psi
6 10
SootvetstvuÈwaè programma moïet byt~ sleduÈwe$i:
(* programma sozdaniè dvoiqnogo dereva tipa poisk *)
PROGRAM Buildtree;
TYPE Rootref = @Ntree;
Typeofdata = ARRAY [1..3] OF 0..4005;
Ntree = RECORD key: INTEGER;
data: Typeofdata;
right, left: Rootref
END;
VAR newkey: INTEGER; newdata: Typeofdata;
newroot: Rootref; f: Text;
(* procedura postroeniè dereva *)
PROCEDURE Build (inkey: INTEGER; indata: Typeofdata;
VAR root: Rootref);
BEGIN
IF root = NIL
THEN
BEGIN
NEW (root);
root@.left:= NIL; root@.right:= NIL;
root@.key:= inkey; root@.data:= indata
END
8 Podobnoe derevo imeet special~noe nazvanie --- derevo poiska.

3.4. NELINE $
INYE STRUKTURY DANNYH: DEREV~? I GRAFY 39
ELSE
IF inkey ! root.key
THEN Build (inkey, indata, root@.left)
ELSE Build (inkey, indata, root@.right)
END; (* Build *)
BEGIN
newroot:=NIL; WRITELN ('Input data')
WHILE eof (f) DO
BEGIN
READ (newkey, newdata);
Build (newkey, newdata, newroot)
END; (* while *)
(* Printtree (newroot) *)
END.
(input data = vvodite dannye)
Napomnim, qto v rezul~tate raboty programmy Buildtree my poluqim dere-
vo, v kotorom v levyh podderev~èh budut uzly (zapisi) so znaqenièmi v pole
key men~ximi, qem v pole key podkornè, a v pravyh --- bol~xe. Otmetim, qto
esli teper~ vklÈqit~ v fftu programmu podprogrammu Printtree i obratit~sè
k ne$i, kak pokazano v kommentarii, to budut napeqatany vvedennye qisla, no
uïe uporèdoqennye v porèdke vozrastaniè (t.e. 3, 4, 5, 6, 9, 10). Metody
sortirovki, osnovannye na podobnom algoritme, okazyvaÈtsè dostatoqno fff-
fektivnymi, hotè suwestvuet i bolee bystry$i sposob sortirovki.
Derevo poiska èvlèetsè nezamenimym sredstvom v zadaqah, gde krome sorti-
rovki, trebuetsè ewe i poisk sootvetstvuÈwego fflementa. Prodolïitel~nost~
poiska budet optimal~no$i (minimal~no$i), esli pravil~no vybrat~ koren~ de-
reva (oqevidno, qto derevo poiska dolïno imet~ vetvi po vozmoïnosti primer-
no odinakovo$i dliny). Zadaqi takogo sorta qasto vstreqaÈtsè pri sozdanii
translètorov i bankov dannyh.

40 CHAPTER 3. STRUKTURY DANNYH

Struktury i tipy dannyh v rabote
4.1 Igrovye zadaqi
Igrovye zadaqi èvlèÈtsè tipiqnymi predstavitelèmi zadaq neqislovogo prog-
rammirovaniè. Otmetim, qto obyqno programmy, modeliruÈwie igry, èvlè-
Ètsè dialogovymi sistemami. Priqem v otliqie ot drugih dialogovyh prog-
ramm, igrovye imeÈt qasto prostuÈ formulirovku uslovi$i pri xirokom di-
apazone sloïnosti.
Naprimer, pri sozdanii programmy igry v xahmaty voznikaet vopros o
sozdanii iskusstvennogo intelekta, a igra v ''tennis'' trebuet usili$i lix~
pri programmirovanii grafiki.
\Lambdato, a takïe zanimatel~nost~ igrovyh programm delaet ih udobno$i illÈs-
tracie$i pri izuqenii zadaq neqislovogo programmirovaniè.
V kaqestve primera igrovo$i zadaqi my rassmotrim prostuÈ programmu,
modeliruÈwuÈ igru v ''orlènku''.
4.2 Modelirovanie igry v ''orlènku''
4.2.1 Uslovie zadaqi
V igre uqastvuet bankir i neopredelennoe qislo igrokov, kotorye delaÈt
stavki na ''orel'' (''o'') ili ''rexku'' (''r''). Bankir brosaet monetu. V sluqae,
esli igrok ugadal, na kakuÈ storonu upadet moneta, emu vyplaqivaetsè summa
ravnaè ego udvoenno$i stavke. V protivnom sluqae igrok terèet stavku.
4.2.2 Postanovka zadaqi dlè programmista
Programmist pereformuliruet zadaqu primerno sleduÈwim obrazom:
1) zadat~ nekotoroe qislo (summu deneg v banke);
2) vvesti: imè igroka, razmer stavki i priznak, na qto sdelana stavka;
3) povtorit~ vvod, esli igraÈt neskol~ko igrokov;
4) poluqit~ odno sluqa$inoe qislo (t.e. smodelirovat~ brosok monety);
5) opredelit~ qislo vyigravxih igrokov i proizvesti sootvetstvuÈwi$i
rasqet;
6) esli nuïno, to vernut~sè ko vtoromu punktu (proizvesti novy$i vvod), v
protivnom sluqae - konec raboty.
41

42 CHAPTER 4. STRUKTURY I TIPY DANNYH V RABOTE
4.2.3 Realizaciè algoritma
Rassmotrim odin iz vozmoïnyh sposobov realizacii dannogo algoritma.
1) Zadat~ summu deneg v banke moïno pri pomowi konstanty:
CONST bank = 1000
2) Dlè hraneniè vvodimo$i informacii moïno ispol~zovat~ lineny$i spi-
sok, predstavlenny$i svèzannym obrazom. Kaïdy$i fflement kotorogo --- zapis~
s qetyr~mè polèmi: imè igroka, stavka, ukazanie na qto ona sdelana i ssylka
na sleduÈwi$i fflement line$inogo spiska.
Dlè organizacii takogo line$inogo spiska na Paskale moïno opredelit~
sleduÈwie tipy dannyh (predpolagaem, qto imè igroka ne moïet byt~ bolee
20 simvolov):
TYPE References = @Records;
Records = Record name: Arr;
stake: REAL;
what: CHAR
next: References
END;
Arr = ARRAY [1..20] OF CHAR
3) vvod informacii budem proizvodit~ sleduÈwim obrazom:
VAR ref, last: References;
yes, answer: CHAR;
BEGIN
last:=NIL;
REPEAT
NEW (ref);
WRITELN ('Give your name, count, and point');
READLN (ref@.name, ref@.stake, ref@.what);
ref@.next:= last; last:= ref;
WRITELN ('more players? (Y/N)');
READLN (answer);
UNTIL answer = 'Y'
(Give your name, count, and point = soobwite imè, stavku i na qto stavite;
more players? = ewe igroki?).
4) Modelirovanie broska monety moïet byt~ proizvedeno vyzovom funkcii
poluqeniè sluqa$inogo qisla v diapozone [0--1]. V sluqae, esli sluqa$inoe qis-
lo !0.5, to sqitaem, qto vypal ''orel''. V protivnom sluqae --- ''rexka''.
5) Podsqet qisla vyigravxih i rasqet so vsemi igrokami proizvodit~sè
pri pomowi prosmotra sozdanogo v p. 3 svèznogo line$inogo spiska (operaciè
prosmotra line$inogo spiska podrobno byla rassmotrena v predyduwe$i glave).
6) Dlè prodolïeniè igry neobhodimo organizovat~ vnexni$i cikl pri po-
mowi operatorov REPEAT .... UNTIL !uslovie?, ili WHILE !uslovie? DO
... Uslovie okonqaniè cikla dolïno byt~ organizovano, analogiqno usloviÈ
okonqaniè v p. 3.

4.2. MODELIROVANIE IGRY V ''ORL?NKU'' 43
Podqerknem, qto ispol~zovanie svèznogo line$inogo spiska dlè hraneniè
stavok v danno$i zadaqe neskol~ko udobnee ispol~zovaniè massiva, t.k. nape-
red neizvestno qislo igraÈwih.
V sluqae ïe, naprimer, igry v ruletku, gde qislo vozmoïnyh stavok od-
nim igrokom veliko i qislo igraÈwih obyqno toïe ne malo, preimuwestva
ispol~zovaniè svèznogo predstavleniè stanovètsè owutimymi.
Otmetim, qto dannye sluqai podpadaÈt pod otmeqennye v rezÈme k p. 3.2.3
i my oqen~ rekomenduem snova proqitat~ dannoe rezÈme.

44 CHAPTER 4. STRUKTURY I TIPY DANNYH V RABOTE

ZaklÈqenie
Pozdravlèem qitatele$i, doqitavxih do fftogo punkta. Vy teper~ moïete otno-
sitel~no kvalificirovanno podo$iti k rexeniÈ daïe takih zadaq kak modeli-
rovanie iskusstvennogo intelekta, i my ïelaem vam vsèqeskih udaq.
Qto kasaetsè ne doqitavxih do konca, to moïno naqat~ qitat~ snova, a
moïno i brosit~. No v lÈbom sluqae my dumaem, qto u vas ostalos~ kakoe-to
predstavlenie o tom, iz qego sostoèt i qto leïit v osnove zadaq ''neqislovogo
programmirovaniè'', pereqislennyh vo Vvedenii.
45

46 CHAPTER 5. ZAKLiQENIE

Literatura
1. K. $
Iensen, N.Virt ''Paskal~.'' M.: Finansy i statistika. 1982
(vtoroe russkoe izdanie po tret~emu angli$iskomu K. $
Iensen, N.Virt ''Paskal~.
Rukovodstvo dlè pol~zovatelè.'' M.: Finansy i statistika, 1989 --- na nax
vzglèd neskol~ko huïe pervogo).
Standartnoe i naibolee udaqnoe opisanie èzyka paskal~, kotoroe my brali
za osnovu pri napisanii Glavy 2 moïet byt~ zameneno lÈbym iz imeÈwihsè
v nastoèwi$i moment bol~xogo qisla uqebnikov po paskalÈ. Sredi nih moïet
byt~ rekomendovana (nebol~xaè po ob~emu, no izdannaè otnositel~no bol~xim
tiraïem (300 000 ffkz.)) broxÈra: Abramov S.A., Zima E.V. Naqala program-
mirovaniè na èzyke paskal~'' - M.:, Nauka, 1987.
2. N.Virt ''Algoritmy + struktura dannyh = programmy.'' M.: Mir., 1985
(vtoroe russkoe izdanie: N.Virt ''Algoritmy i struktury dannyh.'' M.: Mir,
1989 napisano dlè ''paskaleobraznogo'' èzyka Modula-2).
Soderïit neskol~ko podrobnyh illÈstraci$i primeneniè razliqnyh struk-
tur dannyh pri programmirovanii, vklÈqaÈwih zadaqi sortirovki i okan-
qivaÈwihsè podrobnym obsuïdeniem sozdaniè translètora dlè èzyka PL/0.
Rekomenduetsè dlè dal~ne$ixego qteniè.
3. V.B.Titov neqislovoe programmirovanie v zadaqah nebesno$i mehaniki.
Trudy AO LGU, L., 1987.
Dano kratkoe opisanie bol~xogo qisla struktur dannyh i konkretnye pri-
mery ih ispol~zovaniè v nebesno$i mehanike. Ideologiè imenno ffto$i stat~i
leïit v osnove Glavy 3.
4. R.Forsa$it ''Paskal~ dlè vseh''. M.: Maxinostroenie, 1986.
Soderïit opisanie èzyka Paskal~ i podrobno razobrano neskol~ko zadaq
neqislovgo programmirovaniè (sredi nih imeÈtsè igrovye zadaqi). Rekomen-
duetsè dlè dal~ne$ixego qteniè.
47