|
ELEKTRONINĖS KNYGOS |
|
|
Gintautas GRIGAS
PROGRAMAVIMAS PASKALIU
|
7. DUOMENŲ STRUKTŪROS
|
Kai programoje atsiranda daug paprastųjų
sakinių arba kelis sakinius reikia laikyti vienu, tuos sakinius
jungiame į stambesnius, struktūrinius sakinius, dar vadinamus
valdymo struktūromis. Daugelis sakinių pavirsta vienu sakiniu.
Kai programoje atsiranda daug paprastųjų
duomenų (reikšmių) arba kelis duomenis reikia laikyti vienu, tuos
duomenis jungiame į stambesnius, struktūrinius duomenis, dar
vadinamus duomenų struktūromis. Daugelis duomenų (reikšmių)
tampa vienu duomeniu (reikšme).
|
7.1. Įrašas
|
Dažnai programose pasitaiko tarpusavyje
susijusių kintamųjų ir jų reikšmių. Pavyzdžiui, data apibūinama
trimis reikšmėmis metais, mėnesiu, diena. Visus tris datos
komponentus programose pavadindavome skirtingais vardais ir
operuodavome kaip su atskirais komponentais. Kai operuojame su viena
data, tai nepatogumų nejaučiame. Tačiau, kai toje pačioje
programoje prireikia kelių datų, atsiranda kelis kartus daugiau
vardų ir sunkiau susigaudyti. Iš dalies tų sunkumų išvengdavome,
parinkdami vardus pagal sistemą:
mt1, mn1, dn1,
mt2, mn2, dn2 ir t. t.
Tačiau Paskalio kalboje yra numatytas kur kas
geresnis būdas duomenims grupuoti. Programoje aprašomi nauji
duomenų tipai, kurių reikšmės sudaromos iš kitų, jau žinomų
duomenų tipų reikšmių. Tokie duomenų tipai vadinami struktūriniais.
Aprašysime duomenų tipą ir pavadinkime jį
vardu data,
type data = record
metai: 1..maxint;
mėnuo: 1..12;
diena: 1..31
end
Tai įrašo tipas. Jo aprašas pradedamas žodžiu
record ir baigiamas žodžiu end. Tarp jų išvardijamos
sudedamosios įrašo dalys, vadinamos laukais. Nurodomas kiekvieno
lauko vardas ir tipas. Įrašo lauko tipas gali būti įvairus. Čia
aprašytą įrašą sudaro trys laukai: metai, mėnuo
ir diena. Jų tipai yra įvairios sveikųjų skaičių
atkarpos. Konstanta maxint žymi didžiausią sveikąjį skaičių
kompiuteryje.
Aprašysime daugiau įrašo tipų:
type laikas = record
val: 0..23;
min: 0..59;
sek: 0..59
end;
trupmena = record
{ paprastoji trupmena }
s,
{ skaitiklis }
v: integer {
vardiklis }
end;
Kiekvienas čia aprašytas tipas yra naujas
duomenų tipas. Vadinasi, įrašo negalima laikyti vienu duomenų
tipu. Tai tipų šeima.
Aprašius duomenų tipą, toliau programoje
galima naudoti tipo vardą kintamiesiems aprašyti, pavyzdžiui:
var šiandien, gimimodata: data
Taip aprašyti kintamieji šiandien ir gimimodata
priklauso tipui data. Jų reikšmės yra sudėtinės (įrašai)
jas sudaro trys dalys (laukai).
Ten, kur reikia viso kintamojo reikšmės (įrašo),
rašomas kintamojo vardas. Pavyzdžiui, viso įrašo reikšmės
priskyrimą galima nurodyti vienu prieskyros sakiniu:
gimimodata := šiandien
Galima operuoti ir su atskirais įrašo
laukais. Tada po kintamojo vardo rašomas taškas, o po jo
reikiamo lauko vardas, atskirtas tašku. Pavyzdžiui,
m := šiandien.metai;
d := šiandien.diena;
gimimodata := šiandien.diena
Laukus galima rašyti ir kairėje prieskyros
sakinio pusėje, pavyzdžiui:
gimimodata.metai := 1968;
gimimodata.mėnuo := 3
Atlikus šiuos prieskyros sakinius, bus
pakeistos dviejų kintamojo gimimodata laukų reikšmės, o trečiojo
lauko reikšmė išliks ta pati.
Atkreipiame dėmesį į tai, kad vienas
prieskyros sakinys
gimimodata: = šiandien
prilygsta trims paprastųjų reikšmių
prieskyros sakiniams:
gimimometai.metai := šiandien.metai;
gimimodata.mėnuo := šiandien.mėnuo;
gimimodata.diena := šiandien.diena
Taigi, operuodami su sudėtingesnėmis reikšmėmis
(įrašais), galime sutrumpinti programos tekstą.
1 pavyzdys.
program datos;
type data = record
met: 1..maxint;
mėn: 1..12;
dien: 1..31
end;
var a, b, c, ankstyva: data;
function ankstesnė(a, b: data): boolean;
{ ankstesnė = true, jeigu a ankstesnė negu b
}
begin
if a.met < b.met then
ankstesnė := true
else if
a.met > b.met then ankstesnė := false
else if a.mėn < b.mėn then ankstesnė := true
else if a.mėn > b.mėn then ankstesnė := false
else if a.dien < b.dien then ankstesnė := true
else ankstesnė := false
end;
begin
read(a.met, a.mėn, a.dien);
read(b.met, b.mėn, b.dien);
read(c.met, c.mėn, c.dien);
ankstyva := a;
if ankstesnė (b, ankstyva)
then ankstyva := b;
if ankstesnė(c, ankstyva)
then ankstyva := c;
write(ankstyva.met, ankstyva.mėn: 3, ankstyva.dien:
3)
end.
Šios programos pradiniai duomenys yra trys
datos, o rezultatas viena, pati ankstyviausia iš jų data.
Funkcija ankstesnė nustato, ar pirmoji data (a)
yra ankstesnė už antrąją datą (b). Jos parametrai įrašo
tipo kintamieji. Jei nebūtų įrašo, reikėtų šešių parametrų.
Pastaba. Kai tipai vadinami vardais, dažnai
pasitaikanti klaida yra duomenų tipo vardo vartojimas vietoj
kintamojo vardo. Pavyzdžiui, galima rašyti
šiandien.met,
bet negalima rašyti
data.met,
nes šiandien yra kintamojo vardas, o data
duomenų tipo vardas.
2 pavyzdys. Iki 1971 metų D. Britanijos
pinigų sistema buvo tokia: svarai sterlingų, šilingai ir pensai;
svarą sterlingų sudarė 20 šilingų, šilingą 12 pensų.
Aprašysime įrašą pinigams užrašyti šia sistema ir sudarykime
procedūrą dviem duotoms pinigų sumoms sudėti.
type pinigai = record
svarai: 0..maxint;
šilingai: 0..20;
pensai: 0..12
end;
procedure sudėtis(a, b: pinigai; var c: pinigai);
var p: integer;
begin
p := a.pensai +
b.pensai +
12*(a.šilingai
+ b.šilingai +
20*(a.svarai + b.svarai));
c.pensai := p mod 12;
p := p div 12;
c.šilingai := p mod 20;
c.svarai := p div 20
end;
3 pavyzdys. Žmogus turi iš viso 20 pirštų.
Jeigu operuotume duomeniu, kurio reikšmės būtų kuris nors
(rankos arba kojos) pirštas, tai reikėtų sugalvoti 20 pirštų
vardų. Vartojant įrašą, galima apsieiti su mažiau vardų.
type galūnė = (ranka, koja);
pusė = (kairė, dešinė);
pirštas = (nykštys,
smilius, didysis, bevardis, mažylis);
p = record
g: galūnė;
p: pusė;
pir: pirštas
end;
Užrašysime funkciją, kuri patikrintų, ar
dviejų duotų kintamųjų reikšmės apibūdina tą patį pirštą:
function taspats(a, b: p): boolean;
begin
taspats := (a.g = b.g) and
(a.p = b.p) and
(a.pir = b.pir)
end;
Šioje programoje kojų pirštus pavadinome
tokiais pat vardais, kaip ir rankų pirštus, nors kojų pirštai (išskyrus
nykštį) vardų neturi.
Uždaviniai
7.1.1. Aprašykite įrašo tipus, apibūdinančius:
a) tašką koordinačių plokštumoje;
b) tiesinės lygties su dviem kintamaisiais koeficientus.
7.1.2. Laiko tarpą vaizduoja tokio tipo
įrašas:
type laikas = record
p: 0..maxint; { paros }
h: 0..23, { valandos }
min, s: 0..59
end
Sudarykite:
a) funkciją, kuri nustatytų, ar du duoti
laiko tarpai yra lygūs;
b) funkciją, kuri nustatytų, ar pirmasis duotas laiko tarpas yra
trumpesnis už antrąjį;
c) procedūrą, kuri sudėtų du duotus laiko tarpus;
d) funkciją, kurios reikšmė būtų realiojo tipo skaičius,
lygus duotam laiko tarpui, išreikštam paromis.
7.1.3. Aprašykite įrašą kampui, išreikštam
laipsniais, minutėmis ir sekundėmis, pavaizduoti.
Sudarykite funkciją
šitaip pavaizduotam kampui pakeisti radianais (3600 = 2p
radianų).
7.1.4. Iki 1920 metų Lietuvoje buvo
vartojama colinė matavimo sistema (1 colis = 12,4 mm).
12 colių sudaro pėdą,
o 3 pėdos jardą.
Aprašykite įrašo tipą, tinkantį ilgiui užrašyti
coline sistema.
Sudarykite procedūrą dviem ilgiams, užrašytiems coline
sistema, sudėti.
Sudarykite funkciją ilgiui, užrašytam coline sistema, pakeisti
metrais.
|
7.2. Įrašas, sudarytas iš įrašų
|
Įrašo laukas gali būti bet kurio tipo. Pats
įrašas taip pat yra duomenų tipas. Vadinasi, įrašo laukas gali
būti kitas įrašas. Pateikiame tokių pavyzdžių iš geometrijos.
Pirmiausia aprašysime tašką:
type taškas = record x, y:
real end
Čia x ir y yra taško koordinatės
plokštumoje. Pavyzdžiui, aprašę kintamąjį
var a: taškas
ir atlikę prieskyros sakinius
a.x := 3.0;
a.y := -2.0
gausime 31 paveiksle pavaizduotą tašką.
31 pav. Taškas
Vartodami įrašą taškas, aprašykime naujus
įrašus:
type atkarpa = record a, b: taškas
{ atkarpos galai } end;
apskritimas = record
centras: taškas;
spindulys: real
end;
trikampis = record
a, b, c: taškas end
Visuose trijuose tipuose (atkarpa, apskritimas
ir trikampis) vartojamas paprastesnis įrašas taškas.
Matome, kad įrašai gali būti vienas kitame.
Dėl to įrašai priskiriami prie struktūrinių duomenų tipų,
arba duomenų struktūrų.
Kiekvieną iš šių tipų galima buvo aprašyti
ir tiesiogiai, nevartojant tarpinio tipo taškas, pavyzdžiui:
type ap = record
c: record
x, y: real
end;
spindulys: real
end;
type apskr = record x, y,
spindulys: real
end;
Gali iškilti klausimas, kada naudoti tarpinį
tipą ir kada didelį įrašą aprašyti tiesiogiai, iš karto.
Patariame pasirinkti tą variantą, kuris yra vaizdesnis, aiškesnis.
Pavyzdžiui, jeigu programoje yra aprašoma daug geometrinių figūrų,
vaizduojamų taškais, tai, be abejo, tašką geriau aprašyti kaip
atskirą tipą ir toliau šį tipą naudoti. Kai aprašoma tik viena
figūra, tą ją sudarančias kitas figūras geriau neskirstyti į
atskirus tipus. Čia galima įžvelgti analogiją tarp įrašų ir
procedūrų bei funkcijų: pasikartojančius veiksmus patogu aprašyti
funkcijomis ir procedūromis, o pasikartojančias duomenų grupes
duomenų struktūromis (įrašais).
Grįžkime prie apskritimo aprašo.
Aprašykime tipų apskritimas ir apskr
kintamuosius:
var p, s: apskritimas;
r: apskr;
t: taškas
Atlikę sakinius
t.x := 0.0;
t.y := 2.0;
p.centras := t;
p.spindulys := 1.0;
r.x := 4.0;
r.y := 1.0;
r.spindulys := 2.0;
s := p;
s.centras.x := 6.0
gausime tris apskritimus.
Kintamojo t galima buvo ir nenaudoti.
Tada pirmuosius tris prieskyros sakinius reikėtų perrašyti taip:
p.centras.x := 0.0;
p.centras.y := 2.0
Kintamieji p ir s yra to paties tipo. Todėl
vieno jų reikšmę galima priskirti kitam ir atlikti sakinį s :=
p.
Kintamasis r yra jau kito tipo, nors
taip pat reiškia apskritimą. Ar galima kintamojo r reikšmę
priskirti kintamiesiems p ir s? Paskalio kalboje tai
neapibrėžta. Todėl šiuo klausimu programuotojų nuomonės
skiriasi. Tačiau logiškiau prieskyros sakinyje skirtingų tipų
reikšmių nepainioti jeigu programuotojas sugalvojo skirtingų
tipų vardus, tai matyt, jie kažkuo turi skirtis. Tipus apskritimas
ir apskr geriau laikyti skirtingais ir nepainioti jų kintamųjų
reikšmių. Vadinasi, abi prieskyros sakinio pusės turi būti to
paties tipo.
Dar pateikiame funkcijų ir procedūrų pavyzdžių,
kuriuose yra įrašų. Sakykime programoje aprašyti tokie įrašo
tipai:
type taškas = record x, y:
real end;
atkarpa = record
a, b: taškas end;
apskritimas = record
c: taškas; { centras }
r: real { spindulys }
end;
1 pavyzdys. Funkcija atstumui tarp dviejų
taškų rasti (32 pav.):
function atstumas (a, b: taškas):
real;
begin
atstumas := sqrt(sqrt(b.x - a.x) + sqrt(b.y -
a.y))
end;
32 pav.
2 pavyzdys. Funkcija atkarpos ilgiui
rasti:
function ilgis (atk: atkarpa): real;
begin
ilgis := atstumas(atk.a, atk.b)
end;
3 pavyzdys. Funkcija, patikrinanti, ar
duotas taškas yra duoto apskritimo viduje:
function viduje (t: taškas; ap:
apskritimas): boolean;
begin
viduje := atstumas(t, ap.c) < ap.r
end;
4 pavyzdys. Funkcija, patikrinanti, ar
kertasi du duoti apskritimai:
function kertasi (ap, aps:
apskritimas): boolean;
begin
kertasi := ap.r + aps.r > atstumas(ap.c,
aps.c)
end;
Uždaviniai
7.2.1. Aprašykite taisyklingąjį
daugiakampį apibūdinantį įrašą.
7.2.2. Sudarykite funkciją trikampio
plotui rasti. Pradinio duomens tipas trikampis. Vartokite
šiame skyrelyje
aprašytas funkcijas.
|
7.3. Masyvas
|
U ždaviniuose dažnai būna didelės
vienodo tipo duomenų grupės. Tokius duomenis patogu jungti į
masyvus. Masyvas tai duomenų struktūra, kurią sudaro daugelis
vienodo tipo reikšmių.
Išnagrinėkime pavyzdį. Sakykime, reikia turėti
duomenų struktūrą, nurodančią pamokų skaičių kiekvieną
savaitės dieną. Tam aprašome vardinį tipą savd, duomenų
tipą pamokų skaičiui kiekvieną savaitės dieną fiksuoti
masyvą, ir kintamąjį p:
type savd = (pirm, antr, treč, ketv,
penk, šešt, sekm);
pamokos = array [savd]
of 0..6;
var p: pamokos;
Skirtingai nuo įrašo, masyvo komponentai
nurodomi ne laukų vardais, o kito, diskrečiojo duomenų tipo reikšmėmis.
Šiuo atveju masyvo komponentai jie vadinami masyvo elementais
nurodomi tipo savd reikšmėmis, kurios vadinamos
indeksais.
Kaip matyti iš ankstesnio aprašo, tipas savd
turi iš viso 7 reikšmes. Vadinasi, masyvas pamokos turi 7
elementus. Visas masyvas nurodomas kintamojo vardu, šiuo atveju
vardu p. Atskiri masyvo elementai nurodomi masyvo vardu ir po jo
laužtiniuose skliaustuose parašytu indeksu. Kintamasis p[pirm]
reiškia pamokų skaičių pirmadienį, kintamasis p[antr]
pamokų skaičių antradienį ir t. t.
Kokio tipo reikšmes gali įgyti masyvo
elementai, rašoma po žodžio of tipo apraše. Šiuo atveju
pamokų skaičius išreiškiamas atkarpos tipu 0..6. Vadinasi, per
dieną gali būti ne daugiau kaip 6 pamokos.
Masyvo elementus galima naudoti, kaip ir
paprastus kintamuosius, t. y. kaip reiškinius, ir rašyti kairėje
prieskyros sakinio pusėje; jie gali būti faktiniai funkcijų ir
procedūrų parametrai.
Štai keli prieskyros sakiniai su kintamojo p
komponentais:
p[pirm] := 5;
p[antr] := p[pirm];
p[treč] := p[pirm]+1;
p[ketv] := 4;
p[penk] := p[ketv];
p[šešt] := 3;
p[sekm] := 0
Atlikę šiuos sakinius, gausime kintamojo p
reikšmę (33 pav.).
pirm |
5 |
antr |
5 |
treč |
6 |
ketv |
4 |
penk |
4 |
šešt |
3 |
sekm |
0 |
33 pav.
Masyvo indeksai turi būti diskrečiojo duomenų
tipo reikšmės. Su tokiomis reikšmėmis atliekamos tam tipui leidžiamos
operacijos. Ši masyvo indeksų savybė ypač dažnai pritaikoma
cikluose: dažniausiai masyvo indeksas įgyja visas leistinas reikšmes.
Pavyzdžiui, norint rasti pamokų skaičių s per savaitę, reikia
parašyti tokį ciklą:
s := 0;
for d := pirm to sekm do
s := s + p[d]
Čia ciklo kintamasis d turi būti savd tipo.
Atlikę šį ciklą su ankstesne kintamojo p reikšme, gausme
s = 27.
Masyvo elementai dar vadinami indeksuotais
kintamaisiais.
Aprašome daugiau masyvų tipų:
1. Vienos paros oro temperatūra, išmatuota
kas valandą:
type temp = array [0..23] of
-40..40;
2. Šimto skaičių seka:
type seka = array [1..100] of
integer;
3. Kita šimto skaičių seka:
type kitaseka = array [2..101] of
integer;
Masyvas kitaseka turi tiek pat elementų,
kiek ir masyvas seka, tik jo elementai indeksuojami kito
intervalo sveikaisiais skaičiais.
Masyvo tipo kintamuosius leidžiama rašyti
abiejose prieskyros sakinio pusėse, jie gali būti funkcijų arba
procedūrų parametrai.
Masyvo elemento tipas būna įvairus: loginis,
vardinis, sveikasis, realusis, įrašas, masyvas ir t. t. Aprašome
dar du masyvus.
1. Šešiakampis
type šešiakampis = array [1..6]
of taškas
Čia taškas įrašo tipas, kuris turėjo būti
aprašytas prieš tai, pavyzdžiui, taip:
type taškas = record x, y:
real end
Tipą šešiakampis galima aprašyti ir
iš karto (t. y. be tipo taškas):
type šešiakampis = array
[1..6] of
record x, y: real end
Aprašome tipo šešiakampis kintamąjį
var x: šešiakampis
Pateikiame tokiais aprašais apibūdintų
kintamųjų tipus:
x šešiakampis, t. y. šešių elementų
masyvas, kurio kiekvienas elementas yra įrašas, sudarytas iš
dviejų realaus tipo elementų;
x[2] taškas, nurodantis antrąjį šešiakampio
kampą, t. y. įrašas, sudarytas iš dviejų realaus tipo elementų;
x[2].x taško, nurodančio antrąjį šešiakampio
kampą, koordinatė x (realaus tipo).
2. Mėnesio kalendorius gali būti pavaizduotas
šitaip:
P
2 9 16
23 30
A 3
10 17 24 31
T 4
11 18 25
K 5
12 19 26
P 6
13 20 27
Š 7
14 21 28
S 1 8 15
22 29
Aprašome masyvo tipą kalend, kuriuo būtų
galima pavaizduoti minėtą kalendorių:
type savd = (pirm, antr, treč, ketv,
penk, šešt, sekm);
savnr =
1..6
{ savaitės numeris }
diena = 0..31
; { nuliu žymėsime
tuščius }
{ kalendoriaus langelius masyve }
kalend = array
[savnr] of
array [savd] of diena
Aprašome tipo kalend kintamąjį:
var k: kalend;
Jeigu kintamojo k reikšmė būtų anksčiau
pavaizduotas kalendorius, tai masyvas k[2] (jis įeina į
masyvą k) reikštų antrosios mėnesio savaitės dienas
2, 3, 4, 5, 6, 7, 8, masyvo elementas k[2][pirm] būtų lygus
2, o elementas k[1][pirm] nuliui, nes pirmoji pavaizduoto
mėnesio savaitė prasideda tik sekmadienį.
Masyvo elementus, nurodomus keliais indeksais,
galima rašyti paprasčiau vidurinių skliaustų ] [ poras pakeičiant
kableliais, pavyzdžiui, vietoj k[2][pirm] rašyti k[2,
pirm].
Pateikiame programų su masyvais pavyzdžių.
1 pavyzdys. Procedūra tipo kalend
masyvui užpildyti:
procedure kal (sd:
savd;
{ kurią savaitės dieną }
{ prasideda mėnuo }
dsk:
diensk;
{ mėnesio dienų skaičius }
var mėnuo: kalend);
var mėnd:
diena;
{ mėnesio diena }
snr: savnr;
sdx: savd;
begin
mėnd := 0;
for snr := 1 to 6 do
for sdx := pirm to sekm do
begin
if (snr = 1) and (sdx = sd)
then mėnd := 1 { kalendoriaus pradžia }
else if mėnd = dsk
then mėnd := 0 { kalendoriaus pabaiga }
else if mėnd <> 0 then mėnd := mėnd + 1;
mėnuo[snr, sdx] := mėnd
end
end
Kad masyvas k vaizduotų minėto mėnesio
kalendorių, programoje reikėtų parašyti kreipinį
kal(sekm, 31, k)
2 pavyzdys. Kompiuteris skaito 100 skaičių
seką. Kompiuteris rašo tuos pačius skaičius, sutvarkytus didėjimo
(tiksliau, nemažėjimo) tvarka:
program tvarkymas;
const n = 100;
var prad:
text;
{ byla, turinti bent 100 skaičių }
x:
integer;
{ skaičius }
m: array [1..n]
of integer; { sutvarkyti skaičiai }
i, ind:
1..n;
{ indeksai }
tinka:
boolean;
{ tinka į m[i] vietą }
begin
assign(prad, 'DUOMENYS.TXT'); reset(prad);
for ind := 1 to n do
begin
tinka
:= false;
i := ind;
read(prad,
x);
while
not tinka do
if i = 1 then tinka := true
else if m[i-1] <= x then tinka := true
else begin
m[i-1] := m[i];
i := i - 1
end;
m[i]
:= x
end;
for i := 1 to n do
writeln(m[i])
end.
Skaičiai masyve rašomi taip, kad visi jo
elementai būtų sutvarkyti nuo mažiausio iki didžiausio. Jeigu
naujai perskaitytas skaičius x ne mažesnis už paskutinį
masyvo elementą m[i-1], tai skaičius įrašomas į
paskutinį laisvą masyvo elementą m[i]. Priešingu atveju
masyvo elementai iš eilės stumiami per vieną vietą į dešinę
tol, kol randama tinkama vieta naujam skaičiui x įrašyti (tokia,
kad kairėje nuo jo neliktų skaičių, didesnių už jį, o dešinėje
visi skaičiai būtų didesni).
3 pavyzdys. Masyvo elementų rikiavimo
procedūra.
const n = ...;
type masyvas = array [1..n] of integer;
procedure tvarka(var m: masyvas);
var c:
integer;
{ masyvo elementas }
j, k:
1..n;
{ masyvo indeksai }
begin
for k := 1 to n-1 do
for j := 1 to n-k do
if m[j] >
m[j+1] then
begin
{ du elementai keičiami vietomis }
c := m[j+1];
m[j+1] := m[j];
m[j] := c
end
end;
Šis masyvo elementų rikiavimo metodas
vadinamas burbulo metodu. Kiekvienas masyvo elementas pamažu
juda link savo vietos panašiai kaip burbulas pamažu kyla į
vandens paviršių. Tai pats paprasčiausias ir pats lėčiausias
rikiavimo metodas. Efektyvesni rikiavimo metodai puikiai aprašyti
knygoje [9].
4 pavyzdys. Pradiniai duomenys
mokinių pažymių seka. Sekos pabaigą pažymėsime nuliu.
Sudarykime programą pažymiams sumuoti ir pažymių vidurkiui
rasti.
program pažymiai;
var k, p:
0..5;
{ pažymiai }
suma,
{ pažymių suma }
n:
integer;
{ pažymių skaičius }
vidurkis: real;
paž: array [1..5]
of integer;
begin
for k := 1 to 5 do
paž[k] := 0;
{ užpildomas pažymių masyvas }
read(p);
while p <> 0 do
begin
paž[p]
:= paž[p]+1;
read(p)
end;
{ randamas vidurkis }
n := 0; suma := 0;
for k := 1 to 5 do
begin
n :=
n+paž[k];
suma :=
suma + paž[k]*k
end;
vidurkis := suma/n;
for k := 1 to 5 do
writeln(k, ':', paž[k]:
2);
riteln('VIDURKIS ', vidurkis)
end.
Uždaviniai
7.3.1. Aprašykite duomenų tipą, kurio
reikšmė būtų kiekvieno metų mėnesio vidutinė,
žemiausia ir aukščiausia
temperatūra.
7.3.2. Sudarykite dvi procedūras vieno
mėnesio kalendoriui spausdinti iš tipo kalend masyvo šitokiu
pavidalu:
a)
2 9 16
23 30
3 10
17 24 31
4 11
18 25
5 12
19 26
6 13
20 27
7 14
21 28
1 8 15 22 29
b)
1
2 3
4 5
6 7 8
9 10 11
12 13 14 15
16 17 18 19
20 21 22
23 24 25 26
27 28 29
30 31
7.3.3. Ką reikėtų pakeisti 2 pavyzdžio
programoje tvarkymas, kad pradiniai duomenys būtų
rašomi nedidėjimo
tvarka?
|
7.4. Įrašo ir masyvo palyginimas
|
Įrašas ir masyvas dvi duomenų struktūros,
du duomenų tipai. Išsiaiškinkime, ką jie turi bendra ir kuo jie
skiriasi?
Abi struktūras sudaro komponentai kitos
smulkesnės struktūros arba paprastosios (skaliarinės) reikšmės.
Jų komponentų tipai gali būti įvairūs: įraše įrašas
arba masyvas, o masyve masyvas arba įrašas. Vieną struktūrą
įterpdami į kitą, galime aprašyti sudėtingiausias duomenų
struktūras, panašiai kaip įterpdami vieną į kitą funkcijas
arba procedūras, aprašome įvairaus sudėtingumo veiksmus.
Pagrindinis skirtumas tarp įrašo ir masyvo
yra tas, kad visi masyvo komponentai turi būti to paties tipo (įrašo
komponentai gali būti skirtingų tipų). Dėl to nevienodai
nurodomi komponentai. Įrašo komponentai vadinami laukais, kurių
vardai nurodomi įrašo apraše. Masyvo komponentus, kurie vadinami
elementais, nurodo indeksai. Elementų indeksai yra diskrečiojo
duomenų tipo reikšmės, o su jomis galima atlikti operacijas,
pavyzdžiui, vartojant funkcijas succ ir pred, pereiti
prie kitos indekso reikšmės. Tokia galimybe paranku pasinaudoti
cikluose, o automatiškai perrinkti įrašo laukų negalima. Ši įrašų
ir masyvo skirtybė atsiranda ne dėl kokių nors susitarimų arba
komponentų žymėjimo, bet dėl to, kad masyvo elementai yra to
paties tipo, o įrašo laukai gali būti skirtingų tipų. Jeigu
automatiškai perrinktume įrašo laukus, tai programoje nebūtų
galima užrašyti operacijų su įrašo laukais, nes nežinotume,
kokio tipo gali būti laukas.
Kadangi masyvo elementai indeksuojami diskrečiojo
duomenų tipo reikšmėmis, tai jų elementų gali būti labai daug.
Tuo tarpu visų įrašo laukų vardus reikia išvardyti įrašo apraše.
Dėl to įrašus su daugeliu komponentų nepatogu aprašyti. Kai
duomenų struktūroje yra nedaug to paties tipo komponentų, juos
galima aprašyti ir įrašu, ir masyvu. Pavyzdžiui, aprašykime įrašu
racionalųjį skaičių (arba paprastąją trupmeną):
type rac = record
skaitiklis, vardiklis: integer;
end
arba tokio tipo masyvais
type racm1 = array [1..2] of
integer
arba
type racm2 = array
[(skaitiklis, vardiklis)] of integer
Aprašę kintamuosius
var x: rac;
y: racm1;
z: racm2
trupmenos skaitiklį turėtume nurodyti taip:
x.skaitiklis
y[1]
z[skaitiklis]
Pirmas ir trečias variantas yra vaizdesni. Tačiau
trečiame variante vartojamas papildomas vardinis duomenų tipas,
turintis dvi reikšmes.
Kurį variantą pasirinkti? Turbūt lakoniškiausias
ir aiškiausias yra pirmasis.
Galima pastebėti analogiją tarp valdymo ir
duomenų struktūrų.
Iš paprastųjų sakinių (pavyzdžiui,
prieskyros) yra sudaromi sudėtingesni struktūriniai sakiniai
valdymo struktūros (pavyzdžiui, sudėtinis sakinys, ciklo
sakinys). Iš paprastųjų duomenų tipų (pavyzdžiui, sveikųjų
skaičių, loginių reikšmių) irgi sudaromi sudėtingesni duomenų
tipai, kurie vadinami struktūriniais duomenų tipais, arba duomenų
struktūromis.
Sudėtingą duomenų struktūrą galima išreikšti
vis paprastesnėmis, kol galiausiai prieinama prie paprastųjų
duomenų tipų. Pasikartojančius veiksmus galima užrašyti
funkcijomis ir procedūromis, o pasikartojančias keliose programos
vietose duomenų struktūras patogu aprašyti duomenų tipais.
Išnagrinėję duomenų ir valdymo struktūras,
galime sėkmingai programuoti sudėtingus realaus gyvenimo uždavinius,
nes jau mokame sudėtingus veiksmus skaidyti į paprastesnius
(naudoti funkcijas, procedūras ir valdymo struktūras), o sudėtingas
duomenų struktūras skaidyti į paprastesnes duomenų struktūras.
Uždavinys
7.4.1. Kurie iš šių teiginių yra
teisingi:
a) masyvo indeksą galima apskaičiuoti;
b) įrašo lauką galima apskaičiuoti;
c) vietoj įrašo, kurio visi laukai yra to paties tipo, galima
naudoti masyvą;
d) įrašo laukus galima įvardyti vardinio tipo konstantomis.
|
7.5. Duomenų struktūros sudarymo pavyzdys: šachmatų
lenta
|
Kai gerai parinkta duomenų struktūra,
lengviau užrašyti veiksmus su tais duomenimis. Todėl, dar prieš
rašant veiksmus, reikia gerai apgalvoti duomenų struktūras ir
parinkti pačias tinkamiausias, kuo natūraliau atspindinčias ir uždavinį,
ir veiksmus programoje.
Sudarykime duomenų tipą, kurio reikšmė būtų
šachmatų lenta (34 pav.). Ją patogu vaizduoti masyvu, sudarytu iš
langelių. Lentos stulpelius priimta žymėti raidėmis, o eilutes
skaičiais. Todėl pirmiausia aprašysime masyvo indeksų tipus:
34
pav.
type stulpelis =
(a, b, c, d, e, f, g, h);
eilutė = 1..8;
Dabar galime aprašyti ir masyvą. Galimi du
variantai:
1) type lenta = array [stulpelis]
of
array [eilutė] of ...
2) type lenta = array [eilutė] of
array [stulpelis] of ...
Jeigu priimtume pirmąjį variantą, tai masyvo
elementus (langelius) reikėtų indeksuoti, pavyzdžiui, taip: [a,
3], jei antrąjį, tai šitaip: [3, a]. Kadangi šachmatų
literatūroje priimta pirma rašyti raidę, po to skaičių (pavyzdžiui,
a3), tai natūralesnis pirmasis variantas.
Dabar reikia aprašyti masyvo elemento
lentos langelio tipą. Ant lentos statysime šachmatų figūras.
Vadinasi, langelio reikšmė bus figūra.
Šachmatų figūros tipą galima aprašyti šitaip:
type figūra = (karalius, valdovė,
bokštas,
rikis, žirgas, pėstininkas)
Betgi čia dar ne viskas. Šachmatų figūros
yra baltos ir juodos, o langeliai gali būti neužimti. Todėl dar
reikia aprašyti figūros spalvą:
type spalva = (nieko, balta, juoda)
Reikšmė nieko tai trečioji spalva,
reikšianti, kad langelis neužimtas.
Aprašysime masyvo elemento tipą:
type langelis = record
f: figūra;
s: spalva
end
Dabar visus aprašus surašysime pagal Paskalio
kalbos taisyklę, kuri teigia, kad naujo duomenų tipo apraše
galima naudoti tik jau aprašytus duomenų tipus.
type figūra = (karalius, valdovė,
bokštas,
rikis, žirgas, pėstininkas);
spalva = (nieko, balta,
juoda);
langelis = record
f: figūra;
s: spalva
end;
stulpelis = (a, b, c,
d, e, f, g, h);
eilutė = 1..8;
lenta = array
[stulpelis] of
array [eilutė] of langelis;
Aprašysime dvi šachmatų lentas:
var x, y: lenta
Atskirą lentos langelį galima nurodyti
kintamuoju su dviem indeksais, pavyzdžiui:
x[a][3] reikš langelį a3 lentoje x,
y[h][5] reikš langelį h5 lentoje y.
Baltųjų žirgo ėjimą į langelį b4 lentoje
x galima užrašyti taip:
x[b][4].f := žirgas;
x[b][4].s := balta
Figūros perkėlimą iš langelio b4 į langelį
c6 (žirgo ėjimu) toje pat lentoje užrašysime šitaip:
x[c][6] := x[b][4];
x[b][4].s := nieko
Po šių veiksmų langelyje b4 liks bespalvė,
nieko nereiškianti figūra. Tai, žinoma, nenatūralu. Norint šito
išvengti, galima būtų pritaikyti Paskalio kalbos įrašą su
variantine dalimi.
Visų figūrų perkėlimą iš lentos x į lentą
y galima užrašyti vienu prieskyros sakiniu:
y := x
Uždaviniai
7.5.1. Rubiko kubo sienos nudažytos 6
skirtingomis spalvomis: balta, žalia, raudona,
geltona, oranžine,
mėlyna. Kiekviena siena padalyta į 9 kvadratėlius.
Aprašykite duomenų tipą bet kuriam kubo
spalvų deriniui užrašyti.
7.5.2. Sudarykite funkciją, patikrinančią,
ar Rubiko kubas tikrai turi po 9 kiekvienos spalvos
kvadratėlius.
Panaudokite ankstesnio uždavinio duomenų tipus ir, jei reikia,
aprašykite
naujus.
|
7.6. Aibė
|
Vieno kurio nors diskrečiojo duomenų tipo
reikšmių rinkinys vadinamas aibe. Pavyzdžiui, turime
savaitės dienų tipą
type savd = (pirm, antr, treč, ketv,
penk, šešt, sekm)
Pateiksime keleto šio duomenų tipo aibių.
[pirm];
[pirm, penkt];
[šešt, sekm];
[]
[pirm..sekm]
Aibės reikšmės suskliaudžiamos į laužtinius
skliaustus. Šitaip aibės reikšmė atskiriama nuo paprastojo
duomenų tipo reikšmės. Pavyzdžiui, pirm yra tipo savd
reikšmė, o [pirm] yra aibės tipo reikšmė.
Aibė [] neturi nė vieno komponento. Ji yra tuščia.
Paskutinę pavyzdžių sąraše pateiktą aibę
sudaro visos savaitės dienų tipo reikšmės.
Ištisinį į aibę patenkančių reikšmių
intervalą galima užrašyti paprasčiau, nurodant tik intervalo rėžius.
Aibėje negali būti pasikartojančių
komponentų.
Aibės duomenų tipo aprašas pardedamas
baziniais žodžiais set of, po kurių nurodomas aibės
komponentų tipas. Pateiksime pavyzdžių.
type SavDienųAibė = set of
savd;
skaitmenys = set
of 0..9;
dviženkliai = set
of 10..99;
Dabar galima aprašyti šių aibių
kintamuosius ir jiems priskirti aibių reikšmes.
var sd: savd;
sk: skaitmenys;
dd: savd;
sk := [1, 3, 5, 7,
9]; { nelyginių
skaitmenų aibė }
dd :=
[pirm..penk];
{ darbo dienų aibė}
Aibės komponentų tipas vadinamas aibės
baziniu duomenų tipu. Bazinis tipas gali būti bet kuris
diskretusis duomenų tipas, turintis nedidelį reikšmių skaičių.
Daugumoje kompiliatorių šis skaičius yra 256.
Su aibėmis atliekamos matematikoje žinomos
aibių operacijos. Tiktai jos žymimos kitaip.
Operacijos pavadinimas |
Žymėjimas matematikoje |
Žymėjimas Paskalyje |
Pavyzdžiai |
Sąjunga |
|
+ |
[1..5, 7] + [6, 9] ® [1..7, 9] |
Sankirta |
|
* |
[1..5, 7] * [3..9] ® [3..5, 7] |
Skirtumas |
\ |
- |
[1..5, 7] \ [3..9] ® [1, 2] |
Santykio |
|
<= |
[1..5, 7] <= [3..9] ® false |
Santykio |
|
>= |
[1..5, 7] >= [3..9] ® false |
Priklausomybė |
|
in |
4 in [1..5, 7] ® true |
Yra matematinių uždavinių, kuriuose
operuojama su aibėmis. Tačiau programavime aibės dažniau
naudojamos netiesiogiai, kaip patogi išraiškos priemonė sąlygose.
Pavyzdžiui, užuot rašę
if a > 10 and a <= 20...
galime rašyti
if a in 11..20...
Tokie užrašai žymiai sutrumpėja, kai reikia
išrinkti daugelį nesistemingai išsibarsčiusių reikšmių.
Pavyzdys. Funkcija, skaičiuojanti balsių
kiekį simbolių masyve.
const n = 1000;
type tekstas = array [1..n] of char;
function balsės (t: tekstas): integer;
{ laikoma, kad tekste tik didžiosios raidės }
var
balsk, { balsių
skaičius }
i: integer;
begin
balsk := 0;
for i := 1 to n do
if t[i] in ['A', 'Ą' , 'E', 'Ę',
'Ė', 'I',
'Į', 'Y', 'O', 'U', 'Ų', 'Ū']
then balsk
:= balsk + 1;
balsės := balsk
end;
Aibės duomenų tipas dažniausiai laikomas
struktūriniu. Tačiau jos komponentų tipas gali būti tik
paprastasis. Taigi aibė neturi tokių struktūrizavimo galimybių,
kaip masyvas arba įrašas.
Uždaviniai
7.6.1. Kurie iš šių teiginių
teisingi:
a) aibės elementai gali būti realieji skaičiai;
b) aibės elementai gali būti masyvai;
c) masyvo elementai gali būti aibės;
d) visi aibės elementai turi būti vienodo tipo.
7.6.2. Kurių iš čia pateiktų aibių
reikšmės yra lygios?
a := [1, 2, 7] + [5..10];
b := [1..10] - [3..4] + [2];
c := ([1..10] - [3..4] + [2]) * [];
d := [].
7.6.3. Kurie aibių reiškiniai užrašyti
neteisingai ir kodėl?
a) [9, 2] + [3];
b) [2, 9] + 3;
c) [2] in [2, 9];
d) 2 in [2..9];
e) 4 in [9..2];
7.6.4. Tekstinė byla SK.TEK yra
sudaryta iš sveikųjų skaičių. Teigiama, kad visi joje
esantys skaičiai iš
intervalo [0; 99] yra skirtingi. Parašykite programą, kuri
patikrintų,
ar iš tikrųjų
taip yra ir, kaip rezultatą, parašytų vieną iš dviejų pranešimų:
Byloje SK.TEK visi skaičiai iš intervalo
[0; 99] yra skirtingi
Byloje SK.TEK nevisi skaičiai iš intervalo [0; 99] yra skirtingi
|
E Ankstesnis
puslapis |
3
Turinys |
Kitas
puslapis F |
|
|
|
|