1 TEMA

 

 

         Visų algoritmų ar programų esmė yra ta, kad jos aprašo tam tikrų pradinių duomenų pertvarkymą į galutinius duomenis. Duomenų organizavimą būtina išspręsti iki programos algoritmo sudarymo, nes prieš atliekant kokias nors operacijas, reikia turėti objektus, kuriems tos operacijos bus taikomos, bei aiškiai įsivaizduoti tų objektų, kurie bus gauti, struktūrą. Sprendžiant konkretų uždavinį pirmiausiai būtina pasirinkti duomenų, išreiškiančių realią situaciją,  aibę. Tada reikia apibrėžti tos informacijos pateikimo būdą, įvertinant konkrečias kompiuterinės sistemos galimybes. Čia svarbų vaidmenį vaidina pačių duomenų savybės bei su jais atliekamos operacijos.

         Vystantis kompiuterinei technikai ir programavimui tobulėjo ir duomenų pateikimo priemonės ir galimybės. Dabar galime naudoti kaip paprastus nestruktūrinius, taip ir sudėtingesnių tipų duomenis, gaunamus iš įvairių paprastų duomenų kombinacijų. Tokie duomenys vadinami struktūriniais, nes jie yra išdėstyti tam tikra tvarka, t.y. tam tikru būdu organizuoti.

 

 

Paprastieji (baziniai )duomenų tipai

 

        Paprastųjų duomenų pagrindinis požymis-vienas vardas -viena reikšmė. Informatikoje bet kokia konstanta, kintamasis, reiškinys arba funkcija priskiriami kuriam nors tipui. Faktiškai tipas charakterizuoja aibę reikšmių, kurias gali gauti konstanta, kintamasis, reiškinys arba funkcija. Kiekvieno tipo duomenims yra nustatytas tam tikras operacijų rinkinys, jų elgseną apsprendžia tam tikros aksiomos. Baziniai šių duomenų tipai yra:

ü             Sveikieji skaičiai;

ü             Realieji skaičiai;

ü             Tekstiniai duomenys (rašmenys);

ü             Loginiai duomenys.

 

        Sveikieji skaičiai. Su sveikaisiais skaičiais galima atlikti sudėties (+), atimties (-) ir daugybos (*) operacijas. Yra dvi operacijos, surištos su dalyba ir neišeinančios iš sveikųjų skaičių aibės: 1) sveikosios dalies nustatymas, dalijant vieną iš kito; 2) liekanos nustatymas dalijant vieną skaičių iš kito. Sveikieji skaičiai, naudojami kompiuteriuose, turi tas pačias savybes (aksiomas) kaip ir sveikieji skaičiai aritmetikoje. Visi skaičiavimai atliekami absoliučiai tiksliai. Tačiau yra ir vienas skirtumas. Tai – skaičiaus dydžio intervalas. Kiekvienoje konkrečioje kompiuterinėje sistemoje yra pats didžiausias sveikasis skaičius M+∞ ir pats mažiausias neigiamas skaičius M-∞. Jiems galioja lygybės:

M+∞ +1=M-∞       ir        M-∞  -1=M+∞ ,

t.y. pridėjus prie didžiausio teigiamo skaičiaus vienetą, gauname mažiausią neigiamą skaičių ir atvirkščiai. Tai susiję su sveikųjų skaičių kodavimo ir saugojimo atminties ląstelėje ypatybėmis.

 

          Realieji skaičiai. Su realiaisiais skaičiais galima atlikti sudėties (+), (-), daugybos (*) ir dalybos (/) operacijas kaip ir su matematiniais realiaisiais skaičiais. Tačiau su realiaisiais skaičiais visos operacijos atliekamos su tam tikru tikslumu, nes skaičiaus pateikimas kompiuterio atmintyje riboja jo trupmeninės dalies ilgį.

          Pavyzdžiui kompiuteryje 1/3 standartiniu (4 baitų) realiuoju skaičiumi bus 0,3333333, o matematikoje tiksli 1/3 išraiška - begalinė dešimtainė trupmena.

          Realiesiems skaičiams pagal tikslumo poreikį paprastai skiriama 4, 8 ar 16 baitų atminties. Jei reikalingas fiksuotas tikslumas, pvz. finansiniuose skaičiavimuose Excel’iu, reikia naudoti apvalinimo funkciją ROUND (išraiška; skaičių po kablelio) arba meniu Tools/Options kortelėje Calculation pažymėti nuorodą Precision as displayed.

        Tekstiniai ir loginiai duomenys. Pagrindinė tekstinių duomenų (rašmenų) savybė -jų sutvarkymas, t.y. savybė būti palyginamiems. Paprastai tai “a” < ”b”, “b” < “c” ir t.t. Kiekvienas simbolis turi skaitmeninį kodą, pagal kuriuos ir atliekamas lyginimas. Naudojamas ir atskiras tekstinių duomenų tipas -eilutė (string), kurią sudaro rašmenų rinkinys. Eilutės tipo duomenys turi vieną operaciją -susijungimą (konkatenciją). Pvz.: ‘abcd’ // ‘efg’=’abcdefg’. 

          Loginiams duomenims, įgaunantiems tik reikšmę “teisinga” arba “klaidinga” taikomi visi logikos algebros veiksmai. Loginės konstantos paprastai žymimos žodžiais TRUE (teisinga) ir FALSE (klaidinga), loginė operacijos: disjunkcija – OR, konjunkcija – AND.

 

Struktūriniai duomenų tipai

 

          Didelių duomenų rinkinių apdorojimą lengviau automatizuoti, kai visi duomenys yra tam tikru būdu sutvarkyti, t.y. sudaro tam tikrą struktūrą. Tai aptarsime paprastu knygos pavyzdžiu. Jei knygą sukarpysime į atskirus lapus, o dar blogiau, į atskiras raides, tai vargu ar rasime adekvatų būdą knygai perskaityti. Tačiau, jei lapus sudėsime teisinga tvarka, gausime paprasčiausią – tiesinę duomenų struktūrą. Ją jau galime skaityti, nors reikalingų duomenų radimui gali tekti perskaityti visą.

        Efektyvesnei duomenų paieškai egzistuoja hierarchinės struktūros. Knygos atveju tai – dalys, skyriai, skirsniai, skyreliai, pastraipos ir t.t. Žemiausio lygio elementai įeina į aukštesnių lygių elementų sudėtį. Skirsniai susideda iš pastraipų, skyriai iš skirsnių, dalys iš skyrių ir t. t. Tokioje hierar-chinėje struktūroje paieška jau daug paprastesnė, tačiau ir joje reikalinga navigacija – t.y. žinojimas kaip eiti iš vieno hierarchijos elemento prie kito. Tam reikalinga  papildoma informacija – lentelė, susiejanti hierarchinės struktūros elementus su tiesinės struktūros elementais, t.y. dalis, skyrius, skirsnius, pastraipas – su jų puslapių numeriais. Tokią lentelę knygoje mes vadiname turiniu.

          Įprasta struktūrinius duomenis skirstyti į grupes. Tai:

ü             Tiesinės struktūros;

-       Masyvai;

-       Sąrašai (įrašai);

-       Rodyklės;

·         Nepertraukiamieji sąrašai;

·         Susietieji sąrašai;

·         Įrašai;

-       Stekai;

-       Eilės;

ü             Hierarchinės struktūros;

-       Medžio tipo struktūros;

·         Binariniai medžiai.

 

        Masyvai. Kai apdorojami duomenys yra vienalyčiai, t.y. vieno tipo, plačiausiai naudojama ir tradiciškiausia iš tiesinių struktūrų yra masyvas. Masyvas - tai vieno tipo duomenų rinkinys. Šie duomenys, vadinami masyvo elementais arba komponentais, yra sujungti bendru vardu (identifikatoriumi) ir adresuojami išskaičiuojamu indeksu, t.y. visi masyvo elementai turi tą patį vardą ir skiriasi tik savo indeksu. Pagal indeksą galime kreiptis į bet kurį masyvo elementą tiesiogiai ir naudoti jį kaip pavienį duomenį.

 

0.5

4.7

7.2

0.8

 

 

 

A1

A2

A3

A4

 

 

 

A(1)

A(2)

A(3)

A(4)

 

 

 

 

          Masyvo elementai gali būti ne tik paprastųjų tipų, bet ir struktūriniai arba kiti masyvai. Tada turime daugiamatį masyvą.

          Sąrašai (įrašai).  Masyvų dydis ir forma paprastai būna pastovūs. Tačiau aprašant ūkinės veiklos procesus dažnai tenka naudoti skirtingų tipų duomenis, kurių apimtis ir forma gali kisti, t.y. čia turime reikalą su dinaminėmis (kintančiomis) struktūromis. Tokios struktūros pavyzdžiu gali būti organizacijos narių sąrašas, kuris auga priimant naujus narius ir mažėja jiems paliekant organizaciją. Kuriant bet kokią duomenų struktūrą reikia spręsti tokius uždavinius: kaip atskirti duomenų elementus (DE) tarp savęs, kaip ieškoti reikalingų elementų, kaip pridėti ar pašalinti atskirus sąrašo elementus, išlaikant jų surikiavimo tvarką. Sąrašo duomenų elementai atskiriami vienas nuo kito nustatant jiems pastovų ilgį, t.y. tas pats DE užima atmintyje vienodą baitų kiekį. Sudarant sąrašo struktūrą nurodomi jį sudarančių DE baziniai tipai ir ilgiai. Pavyzdžiui, sąrašo apie detales struktūra gali būti aprašyta taip:

Lentelė 1

Detalė

Nr.

Ilgis

CHAR*20

INT*2

REAL*4

Varžtas

16

35,6

 

Tokio sąrašo 1 eilutė užims 26 baitus atminties ir, pvz., 15-os detalės ilgį rasime prie sąrašo 15-to elemento adreso pridėję 22.

          Kiek sudėtingiau su sąrašo elementų papildymu ir pašalinimu norint išlaikyti nustatytą jų surikiavimo tvarką. Dažnai rikiuojame abėcėlės ar didėjimo bei mažėjimo tvarka. Jei, pavyzdžiui, taip surikiuotas minėtas sąrašas apie detales ir reikia įrašyti naują detalę iš A raidės, tai teks perrašyti beveik visą sąrašąi naujas atminties ląsteles.  Sprendžiant šias problemas naudojamos tokios sąvokos:

ü             Rodyklės;

ü             Vientisieji (nepertraukiamieji) sąrašai;

ü             Nuorodiniai (susietieji ) sąrašai.

          Duomenų išsidėstymas kompiuterio pagrindinėje atmintyje apibrėžiamas skaitmeniniais adresais. Jei žinomas kokio tai duomenų elemento (DE) adresas, tai rasti šį elementą yra paprasta. Tai realizuojama naudojant du sąrašo išdėstymo atmintyje būdus, bet pirmiausiai aptarsime rodyklės (angl. pointer)  sąvoką.

        Sąrašo rodyklės. Būdami paprasčiausiais skaitiniais dydžiais,  duomenų elementų adresai ir patys gali būti saugomi kompiuterio atminties ląstelėse. Tokiu būdu, įrašydami DE į vieną atminties ląstelę, mes galime įrašyti to DE adresąi kitą atminties ląstelę ir vėliau ją naudoti kaip kreities į tą DE priemonę. Kitais žodžiais, tos ląstelės turinys mums nusako kur ieškoti DE. Šia prasme atminties ląstelę, saugančią kitos ląstelės adresą, mes galime traktuoti kaip būdą nurodyti kitos ląstelės buvimo vietą. Todėl tokios ląstelės vadinamos rodyklėmis. Šį būdą palaiko visos šiuolaikinės aukšto lygio programavimo kalbos. Rodyklių pagalba kompiuterio atmintyje galima kurti sudėtingas duomenų struktūras ir lengvai manipuliuoti jų turiniu. Pavyzdžiui, bibliotekoje yra knygų katalogas pagal jų pavadinimus. Jame lengvai rasime ieškomo pavadinimo knygą, tačiau sunku bus rasti visas vieno autoriaus knygas. Tai lengvai galėsime padaryti, jei kataloge kiekvienos knygos aprašyme įdėsime dar vieną elementą – rodyklę į sekančią to paties autoriaus knygą kataloge(žr. lentelę 2).

Bibliotekos katalogas, surikiuotas pagal pavadinimus ir autorius, panaudojant rodykles:

Lentelė 2

 

Vientisieji (nepertraukiamieji) sąrašai. Taigi, kaip galima saugoti sąrašus kompiuterio atmintyje?

Vienas iš būdų –saugoti visą sąrašo turinį vieningame atminties  ląstelių bloke su nuosekliais adresais. Jeigu vienam sąrašo elementui (eilutei) įrašyti skirsime M atminties ląstelių (baitų), o tokių eilučių maksimaliai gali būti N, tai kompiuterio atmintyje reikės rasti vientisą bloką iš M*N ląstelių. Tokia struktūra vadinama vientisuoju sąrašu. Tai tipiška masyvo struktūra.

        Vientisuosius sąrašus paprasta naudoti ir aprašyti, tačiau jie turi gana esminių trūkumų. Tarkime, reikia pašalinti vieną sąrašo elementą (eilutę), tada likusius už jo elementus reikės perkelti per M ląstelių, kad užpildyto pašalintojo vietą. Dar sudėtingiau, jei reikia įterpti naujus įrašus sąraše. Tada reikės didinti bloko dydį ir gali nebūti laisvų atminties ląstelių su nuosekliais adresais. Tada tektų perkelti visą sąrašą į naują laisvos atminties sritį.Tokie veiksmai žymiai padidins duomenų apdorojimo laiką.

 

          Nuorodiniai (susietieji ) sąrašai. Išvengti minėtų problemų galėsime tik tada, jei sąrašo elementus galėsime saugoti bet kurioje sąrašo vietoje nepriklausomai vienas nuo kito. Šiuo atveju kiekvienam sąrašo elementui saugoti reikės M+1 ląstelių, ir paskutinėje M+1 ląstelėje reikės saugoti rodyklę į sekantį pagal rikiavimo tvarką sąrašo elementą, t.y. to elemento pirmos ląstelės adresą. Tokiu būdu

rodyklėmis bus susietas visas, įvairiose atminties vietose išmėtytas sąrašas. Todėl tokios struktūros vadinamos nuorodiniais arba susietaisiais sąrašais. Nuorodinis sąrašas visada prasideda sąrašo pradžios rodykle ir baigiamas elementu su nulinės reikšmės rodykle (NIL):

 

 

Pav. 1 Nuorodinio sąrašo pavyzdys

 

          Įrašo šalinimas nuorodiniame sąraše. Įterpti naują įrašą ar pašalinti esamą, išsaugant surikiavimo tvarką, nuorodiniame sąraše nesukelia jokių problemų. Tokiai operacijai nereikia perstumdyti atmintyje mažesnės ar didesnės sąrašo dalies, o tik reikia pakeisti vieno atitinkamo įrašo rodyklės turinį:

Pav. 2  Įrašo šalinimo nuorodiniame sąraše pavyzdys

 

          Įrašo įterpimas nuorodiniame sąraše. Naujo įrašo įterpimas taip pat atliekamas gana paprastai. Naujas įrašas išsaugomas bet kurioje laisvos atminties srityje ir modifikuojama tik atitinkamo įrašo pagal rikiavimo tvarką rodyklė, suteikiant jos reikšmę naujo įrašo rodyklei:

 

Pav. 3 Įrašo įterpimo nuorodiniame sąraše pavyzdys

 

          Įrašai. Aprašant ūkinės veiklos procesus dažnai tenka naudoti skirtingų tipų duomenis, tada jų rinkinys sudaro įrašą ( record). Įrašas - tai įvardintų komponentų - laukų rinkinys, turintis bendrą vardą. Į kiekvieną įrašo lauką galime kreiptis įrašo bei lauko vardu; pvz.: turime įrašą:

 

Lentelė 3

Įrašas B

Detalė

Nr.

Ilgis

 

Varžtas

16

35,6

 

 

 

 

 

B.Detalė

B.Nr.

B.Ilgis

 

CHAR

INT

REAL

 

 

Ir masyve, ir įraše galima tiesiogiai kreiptis į konkretų elementą.

          Įrašuose gali būti skirtingi duomenų tipai, o masyvų elementų indeksacija yra lankstesnė, nes leidžia apskaičiuoti reikalingą indeksą.

 

          Stekas. Viena iš sąrašo savybių, dėl kurios susietieji sąrašai yra patrauklesni, yra poreikis pridėti ar šalinti jo elementus. Prisimename, kad vientisųjų sąrašų atveju šios operacijos gali iššaukti kompiuterio atmintyje didelius duomenų perstumdymus. Jeigu elementų įterpimo ir šalinimo operacijų naudojimo sritį apribosime tik sąrašo galais, tai vientisojo sąrašo panaudojimas taps patrauklesnis. Tokios duomenų struktūros pavyzdžiu gali būti stekas - sąrašas, kuriame visi įterpimo ir šalinimo veiksmai atliekami viename gale, t.y. paskutinis į jį patalpintas elementas paimamas pirmas ir atvirkščiai, tai vadinama LIFO – Last In First Out.

 

 

Tokių struktūrų pavyzdžiai - šaunamo ginklo dėklas, padėklai valgykloje, paprogramės parametrai, grįžimo adresai programose, atlikus vidines procedūras ir t.t. Steko galas, kur vyksta įrašų pridėjimas ir šalinimas, vadinamas viršūne, o kitas – pagrindu.

 

 

 

Eilė. Priešingai stekui, kur elementų pridėjimas ir paėmimas vyksta viename gale, eilė – tai toks sąrašas, kuriame elementų pridėjimas vyksta viename gale, o paėmimas kitame. Eilės ilgis iš anksto neapibrėžiamas ir teoriškai gali būti begalinis. Tokia seka vadinama “pirmas įėjo - pirmas išėjo”(FIFO – first in first out). Eilės kraštas, kuriame elementai paimami, vadinamas pradžia, o kur pridedami – eilės pabaiga. Saugant eilę kompiuterio atmintyje kaip susietą sąrašą, reikia naudoti dvi rodykles, nurodančias eilės pradžią ir pabaigą.

 

          Hierarchinės struktūros. Nereguliarūs duomenys dažnai pateikiami kaip hierarchinės struktūros. Hierarchinę struktūrą turi įvairios adresų sistemos (pašto, interneto). Ji naudojama sistematizacijoje bei klasifikacijoje, pavyzdžiui, duomenys apie turimą programinę įrangą gali turėti tokią hierarchinę

struktūrą:

         

Hierarchinėje struktūroje kiekvieno elemento adresas apibrėžiamas kreipties keliu (maršrutu), vedančiu nuo struktūros viršūnės iki ieškomo elemento. Pvz.: programos Corel DRAW kreipties kelias ankstesnėje struktūroje bus:

Programinė įranga Taikomoji Vektoriniai redaktoriai Corel DRAW

          Šio kelio atvaizdavimo (kodavimo) būdai yra įvairūs. Informatikoje dažnai naudojamas būdas, paremtas taip vadinamu dichotomijos metodu. Jis leidžia kreipties kelią sutvarkytoje struktūroje užrašyti labai kompaktiškai, naudojant dvejetainius simbolius. Dichotomijos metodu sudarytoje hierarchinėje struktūroje kreipties kelią į bet kurį elementą galime pateikti kaip kelią per racionalų labirintą su posūkiais į kairę (1) ir dešinę (0) ir išreikšti kreipties kelią kompaktišku dvejetainiu įrašu.

 

Pav. 4 Pvz. struktūroje

Kreipties kelias į tekstų procesorių Word 2000 bus išreikštas dvejetainiu skaičiumi 1 0 1 0.

 

          Medžio tipo struktūros (grafai). Medžio tipo struktūras nagrinėja speciali matematikos sritis, vadinama grafų teorija. Grafą (G) sudaro dvi aibės: viršūnių aibė (V) ir briaunų aibė (E), G = (V,E). Viršūnės gali būti nurodomos jų numeriais, o briaunos jungiamų viršūnių pora.

Tam tikros grafų rūšys turi savo pavadinimus. Medžiu vadinamas susietas grafas, kuriame nėra ciklų. Medžiai turi vieną viršūnę, į kurią neįeina jokia kita. Ši viršūnė vadinama šaknimi. Iš šaknies į kiekvieną viršūnę veda vienintelis kelias

 

        Dvejetainiai medžiai. Dvejetainiu arba binariniu vadinamas orientuotas medis, kuriame į kiekvieną viršūnę, išskyrus šakninę, įeina viena briauna, o išeina dvi. Medžio dalis, išeinanti iš bet kokios viršūnės, vadinama šaka. Grafų tipo struktūros naudojamos modeliuojant objektų sistemas, tarp kurių egzistuoja tam tikri ryšiai, santykiai, priklausomybė, kai reikia ištirti tokių sistemų struktūrą, jų funkcionavimą.

        Pvz.: pavaizduoti binariniu medžiu reiškinį S=(a+b/c)*(d-e*f):

 

 

 

Parengta pagal:

 

V. Dagys ir kt. Duomenų bazės. ECDL atstovybės Lietuvoje sertifikuota mokomoji medžiaga, L-kla “ Žara”, Kaunas, 2000.

 

J.Adomaitis ir kt. Informatika I dalis Vadovėlis, L-kla “Technolgija”, Kaunas, 1999.

 

V. Sekliuckis, S.Gudas, G.Garšva INFORMACIJOS SISTEMOS IR DUOMENŲ BAZĖS, Vadovėlis. Kaunas: Technologija, 2003.

 

A.Vidžiūnas, R.Marčiulynienė ACCESS XP. Taikomųjų duomenų bazių projektavimo pagrindai,

“Smaltijos” leidykla, Kaunas, 2003.