ĮVADAS
Programa ne tik turi išspręsti tam tikrą vartotojo pasirinktą uždavinį, bet ir kuo racionaliau išnaudoti kompiuterinius resursus. Programuotojai naudodami tik statines duomenų struktūras susiduria su problema, jog joms yra skiriama tik griežta ir ribota kompiuterio operatyviosios atminties dalis. Dėl šios priežasties yra neracionaliai išnaudojama atmintis. Tačiau šią problemą galima išspręsti pasinaudojus dinaminių duomenų struktūrų teikiamais atminties valdymo privalumais. Dinaminėmis yra vadinamos tokios duomenų saugojimo struktūros, kurių atminties skyrimo ir išlaisvinimo veiksmai yra tiesiogiai aprašomi programoje ir vykdomi jos darbo metu. Efektyviausia dinaminių duomenų struktūrų priemonė yra sąrašai, kurie ypač patogūs ne tik duomenų saugojimo, bet ir jų tvarkymo organizavimo priemonė.
Šio kursinio darbo tikslas yra aptarti svarbiausias ir klasikinėmis vadinamas dinamines duomenų struktūras, parodyti jų svarbą bei panaudojimo galimybes. Išsikeliamas pagrindinis uždavinys yra kuo tikslesnė, tačiau glausta dinaminių duomenų struktūrų analizė, jų grafinis atvaizdavimas ir interpretavimas. Kursiniame darbe aprašomos tokios dinaminės duomenų struktūros: tiesiniai dinaminiai sąrašai, kurie skaidomi į vienkrypčius, dvikrypčius bei ciklinius, elementariosios abstrakčiosios dinaminės duomenų struktūros, kurios skirstomos į steką, deką, eilę ir žiedinius sąrašus Taip pat aprašomos pagrindinės tiesinio dinaminio sąrašo tvarkymo operacijos: formavimas, naujų elementų įterpimas, sąrašo peržiūra, elementų paieška, jų įterpimas ir šalinimas. Paskutinėje darbo dalyje nagrinėjamas dinaminis kompiuterio atminties valdymas.
1. DUOMENŲ STRUKTŪROS
1.1. Duomenys, kintamieji, reikšmės
Duomenys – tai faktai, kiekybės ir kokybės objektų charakteristikos, pateiktos formatizuotu pavidalu tam tikrose laikmenose. Pirminiai duomenys yra pateikiami kompiuteriui, apdorojami pagal tam tikrą prieš tai programuotojo sukurtą algoritmą ir gaunami rezultatiniai duomenys. Taigi galime teigti, jog kompiuteris iš vienų duomenų gamina kitus. Puikus šio proceso pavyzdys yra paprasčiausi skaičiavimai, kurie taip pat yra vienas iš duomenų apdorojimo būdų.
Visi duomenys yra saugomi kompiuterio atmintyje. Reikėtų paminėti, kad kiekvieną duomenį charakterizuoja vardas ir reikšmė. Programose yra aprašomi ne patys duomenys, o tik jų vardai, kurių konkrečios reikšmės yra saugomos kompiuterio atmintyje. Tačiau yra duomenų, kurių reikšmės vykdant programą nekinta (pavyzdžiui, konstantos).
Svarbi kiekvienos programos, o, be abejo, ir algoritmo savybė yra masiškumas – tai yra galimybė operuoti iš anksto nežinomais duomenimis. Tokie duomenys programose yra kintamieji, kurie žymimi vardais. Kintamieji tam tikru programos vykdymo momentu atspindi konkretų duomenį, kuris yra vadinamas kintamojo reikšme. Vykdant programą, kintamųjų reikšmės gali keistis.
Duomenys pagal savo savybes skirstomi į klases, kurios vadinamos duomenų tipais. Pavyzdžiui, visi sveikieji skaičiai priklauso sveikųjų skaičių duomenų tipui integer, o visi realieji – duomenų tipui real. Taip yra apibrėžiami visi duomenų tipai, tačiau visuotinai priimtos ir griežtai apibrėžtos duomenų tipo apibrėžties nėra. Duomenų tipai taip pat gali būti susiaurinami ir susiejami, taip sukuriant duomenų tipų potipius bei duomenų tipų šeimas. Potipiu vadinamas duomenų tipas, kurio reikšmių aibė yra kito tipo reikšmių poaibis. Duomenų tipų šeima vadinami duomenų tipai, turintys bendrų savybių, dėl ko gali būti apjungti į šeimą. Šiuo atveju galime nagrinėti masyvus, kadangi jie, nors ir būdami skirtingų rėžių, turi bendrų savybių, pavyzdžiui, kad visų masyvų elementai identifikuojami indeksais. Todėl nesunkiai galima daryti išvadą, jog visi masyvų tipai priklauso masyvų šeimai.
1.2. Duomenų tipas ir jo samprata
Pirmieji kompiuteriai turėjo mažai atminties, todėl vienas iš svarbiausių programų kūrėjų tikslų buvo racionalus kompiuterio atminties išnaudojimas. Tai buvo veiksnys nulėmęs duomenų tipų atsiradimą, kadangi buvo aktualu informuoti transliatorių, kiek reikia skirti atminties tam tikro tipo kintamojo reikšmei saugoti. Tai ir buvo pagrindinė duomenų tipo paskirtis pirmosiose programavimo kalbose.
Ilgainiui, atsirandant naujiems kompiuteriams, didėjo ir jų pajėgumas: išaugo atminties kiekis bei greitis. Atsirado galimybė rašyti ilgesnes ir sudėtingesnes programas, kurios užėmė daugiau kompiuterio atminties. Tačiau naujiems kompiuteriams jos turint gerokai daugiau atminties ekonomijos klausimas pasidarė nebeaktualus ir duomenų tipas išryškėjo kaip programų kontrolės objektas. Svarbiausia šio naujo etapo savybe tapo programų patikimumas ir tikslumas, todėl, savaime suprantama, stengiamasi išvengti klaidų. Norint to pasiekti, būtina patikrinti duomenis prieš vykdant programą, o šią procedūrą atlieka kompiuteris arba programuotojas patikrinimą aprašo pačioje programoje. Programavimo kalbos, kuriose duomenų tipai nekontroliuojami yra vadinamos betipėmis. Tai mašininės ir kai kurios aukštesnio lygio programavimo kalbos. Tam kad būtų galima išvengti klaidų, susijusių su neleistinu duomenų tipų naudojimu, reikia patikrinti operandų tipus dar prieš atliekant operaciją su jais. Žinomi šie svarbiausi duomenų tipų kontrolės būdai: statinė ir dinaminė kontrolė. Abiem atvejais atmintyje yra saugomos ne tik duomenų reikšmės, bet ir jų tipai. Vienu ir kitu atveju skiriasi tik duomenų tipų saugojimo trukmė. Pirmuoju atveju, esant dinaminei kontrolei, tipas saugomas pastoviai, o statinės kontrolės metu informacija apie duomenų tipus saugoma tik tol, kol transliuojama programa, o tai reiškia, kad programos transliavimo metu kiekvienas kintamasis tvirtai susiejamas su duomenų tipu ir išlieka pastovus visą kintamojo gyvavimo laiką. Todėl ar operandų tipai yra tinkami operacijai atlikti, galima patikrinti dar tik transliuojant programą
Bendras duomenų tipų savybes, būdingas daugeliui aukšto lygio pirmosios bei antrosios programavimo kalbos kartoms, suformulavo Tonis Horas (C. A. R. Hoare). Mano nuomone, tai svarbus postūmis duomenų tipų evoliucijoje, kadangi apibrėžus juos tam tikromis savybėmis pasidaro lengviau jais operuoti bei juos suprasti. Duomenų tipams būdingos šios savybės [2]:
1. Duomenų tipas apibrėžia klasę reikšmių, kurias gali įgyti kintamasis ar reiškinys.
2. Kiekviena reikšmė priklauso vienam ir tik vienam duomenų tipui.
3. Konstantos, kintamojo arba reiškinio tipą galima nustatyti arba iš konteksto, arba iš paties operando pavidalo nepriklausomai nuo reikšmių, gautų atliekant programą.
4. Kiekvienos operacijos operandų ir rezultato tipai yra fiksuoti. Kai skirtingų tipų operacijos žymimos tais pačiais simboliais, laikoma, kad toks simbolis yra daugiareikšmis ir žymi skirtingas operacijas. Kokią konkrečiai operaciją jis žymi, visada galima nustatyti iš programos teksto, t. y. Jos transliavimo metu.
5. Kiekvieno tipo reikšmių savybės ir su tomis reikšmėmis atliekamų elementariųjų operacijų savybės apibrėžiamos aksiomomis.
6. Informacija apie tipus aukšto lygio kalboje leidžia išvengti beprasmių konstrukcijų programoje ar rasti jas, taip pat nustatyti, kaip duomenys vaizduojami kompiuteryje ir kokie su jais atliekami veiksmai.
Vėlesniuose programų kūrimo etapuose duomenų tipus imta sieti su operacijomis, kurias galima atlikti su to tipo duomenimis, nes norint atlikti veiksmus, reikia žinoti operandų savybes. Taip pat galimas ir atvirkščias veiksmas, kai pagal operacijas nustatomos reikšmių savybės.
Duomenų tipai, kurių reikšmes ir operacijas apibrėžia programuotojas yra vadinami abstrakčiaisiais duomenų tipais. Abstraktūs duomenų tipai yra objektinio programavimo kalbų pagrindas. Abstrakčiųjų duomenų tipams keliamus reikalavimus apibrėžė Barbara Liskov [2]:
1. Duomenų tipo apraše turi būti apibrėžtos visos operacijos, taikytinos tipo reikšmėm.
2. Abstrakčiojo duomenų tipo vartotojas neturi žinoti, kaip to tipo reikšmės vaizduojamos kompiuterio atmintyje.
3. Abstrakčiojo duomenų tipo vartotojas gali operuoti su to tipo reikšmėmis vien tik to tipo operacijoms, bet negali manipuliuoti tiesiogiai tų reikšmių atvaizdas atmintyje.
Kiekvienas uždavinys nuo jo formulavimo iki galutinių programų vykdymo kompiuteriu pereina keletą skirtingų etapų, kuriuose dalyvauja skirtingi vartotojai. Tai gali būti eiliniai vartotojai (užsakovai), sistemų analitikai, projektuotojai ir programuotojai. Visi šie žmonės tam tikru būdu susiduria su duomenimis, tačiau jų požiūris į duomenis gali labai skirtis. Eiliniam vartotojui nedalomas duomenų vienetas yra rekvizitas. Dar galima paminėti rodiklius, pranešimus, žiniaraščius, paveikslėlius ar ataskaitas. Šios duomenų pateikimo formos figūruoja bendrame uždavinio aprašyme.
Jau suformuluotam uždaviniui rengiant programą operuojama jau kitokiais duomenimis. Tai būtų skaičiai, simboliai, simbolių eilutės, masyvai, aibės, įrašai, failai, duomenų bazės ir kita.
Vykdydamas programą kompiuteris duomenis supranta kaip bitus, baitus, žodžius ar jų kombinacijas. Bitas – tai kompiuterio duomenų vienas dvejetainis atvaizdas. Vienu bitu galima vaizduoti duomenį, turintį dvi reikšmes: 0 ar 1. Be abejo, bitai jungiami į didesnes grupes: baitus, kilobaitus (2¹º = 1024b), megabaitus (2²º = 1048576b), gigabaitus (2³º = 1073741824b).
Į įvairias programavimo kalbas duomenų tipai bei duomenų struktūros atėjo ne vienu metu. Pirmosios duomenų tipų ir struktūrų idėjos buvo įgyvendintos Fortran kalboje (1953m). Programuotojas rašydamas programą šia kalba turi griežtai ir aiškiai apibrėžti kiekvieno kintamojo tipą, o apibrėžtas tipas turi išlikti pastovus visą to kintamojo gyvavimo laiką. Fortran programavimo kalboje pirmą kartą buvo panaudotas struktūrinis duomenų tipas – masyvas.
Algol kalboje (1960) naudojami tie patys duomenų tipai kaip ir Fortran, tik su nežymiais patobulinimais. Tačiau šioje kalboje nebeliko apribojimų masyvams, buvusių Fortran kalboje.
Algoritminėje kalboje Cobol, kuri pasirodė 1961 m. buvo įvestas simbolinis duomenų tipas ir iki tol nenaudotos duomenų struktūros – įrašas ir failas.
Visiška laisvė struktūrinių duomenų srityje pasiekta PL/1 kalboje. Pradėtos naudoti naujos duomenų struktūros – rinkinys. Rinkinių elementais galėjo būti ne tik skaliariniai, bet ir kiti struktūriniai duomenys. Taip pat PL/1 kalboje pradėtos naudoti dinaminės duomenų struktūros, apie kurias plačiau bus kalbama antrojoje darbo dalyje.
Minėtose programavimo kalbose duomenims aprašyti naudojami baziniai duomenų tipai. Pascal kalba, pasirodžiusi 1971 m., duomenų tipizavimo srityje žengė dar vieną žingsnį. Šioj kalboje galima aprašyti naujus duomenų tipus atskirai nuo kintamųjų ir pavadinti juos vardais, o naujai aprašyti tipai gali būti naudojami lygiai taip pat kaip ir standartiniai. Taigi čia standartiniai duomenų tipai prarado ypatingą statusą ir tapo lyg ir standartinių funkcijų analogais. Šioje kalboje naudojamas dar vienas – vardinis duomenų tipas. Lyginant Pascal kalbą su ankstesnėmis pastebima, kad daugiausia naujovių turi konstrukcijos, susijusios su duomenų tipais ir jų struktūromis. Kalbai būdinga darni duomenų tipų sistema, pagrįsta C. A. R. Hoare duomenų tipų teorija. Svarbu paminėti, jog ši kalba turi pakankamas galimybes apibrėžti naujus tipus, tačiau kalbos priemonėmis yra apibrėžiama tik tai reikšmių aibė, ko gali ir nepakakti. Norint operuoti reikšmėmis reikia žinoti jų savybes, o jas galima nustatyti apibrėžiant operacijas su reikšmėmis. Kaip jau buvo aprašyta anksčiau, duomenų tipai, kurių reikšmes ir operacijas su jomis apibrėžia programuotojas yra vadinami abstrakčiaisiais duomenų tipais, o šių duomenų tipų pirmtakas – klasė – atsirado Simula-67 kalboje, nors šiuos duomenų tipus naudoti pradėta tik atsiradus objektiniam programavimui [4].
1.3. Duomenų tipų klasifikacija
Duomenys klasifikuojami pagal tipus, tačiau ir tipai turi savo klasifikaciją. Duomenų tipai klasifikuojami pagal reikšmių struktūrinimo laipsnį į dvi klases [2]:
• paprastuosius;
• struktūrinius.
Paprastųjų tipų reikšmės nedalomos, o struktūrinių tipų reikšmės yra sudarytos iš kitų − paprastųjų ar struktūrinių − reikšmių. Kalbėdami apie nedalomumą, turėtume suprasti, kad tai yra loginis nedalomumas. Pavyzdžiui, skaičius 19 gali būti suprantamas kaip paprastasis ir kaip struktūrinis tipas. Tarkime, kaip skaičius jis gali būti dalomas į 1 ir 9, o, pavyzdžiui, rugsėjo 19 diena negali būti daloma. Taigi ar reikšmė yra paprasta, ar struktūrinė priklauso nuo požiūrio į ją.
Kuriant programas, paprastaisiais duomenimis suprantami tie duomenų tipai, kurių apibrėžtas ir neskaidomas reikšmes teikia programavimo kalba. Struktūriniai duomenų tipai programavimo kalbose apibrėžiami tik iš dalies, kadangi programuotojas gauna ne išbaigtus tipus su konkrečiomis reikšmių aibėmis, o priemones tiems tipams sudaryti. Galutinai tipą aprašo pats programuotojas. Pavyzdžiui, Paskalio programavimo kalboje vienaip aprašomas masyvo tipas, kitaip failo ar įrašo struktūriniai duomenų tipai.
Duomenys jungiami į struktūras tam, kad būtų paprasčiau juos saugoti, peržiūrėti ir persiųsti. Kai persiųsti reikia visą duomenų struktūrą, labai patogu tą veiksmą užrašyti vienu priskyrimo sakiniu. Kompiuteriui taip pat ekonomiškiau persiųsti visą struktūrinę reikšmę iš karto. Pavyzdžiui, kai operuojama tik atskiru komponentu, o kiti neliečiami – užuot išardę visą duomenų struktūrą, programuotojas gali patekti į jos vidų ir operuoti atskirais jos komponentais. Taigi operacijos su struktūrine reikšme turi būti suprantamos kaip operacijos su kompiuterio atmintimi, dėl ko visas darbas gali būti atliekamas daug greičiau.
Naudojant specialų abstrahavimo mechanizmą galima sukurti abstraktųjį duomenų tipą. Šio tipo duomenims yra būdinga tai, kad jų reikšmės, žiūrint iš vidaus yra struktūrinės, o žiūrint iš išorės tokio tipo reikšmės yra kaip paprastasis duomuo.
Taigi duomenų tipų klasifikacijoje yra svarbu, iš kieno pozicijos į juos žiūrime: iš kūrėjo (iš vidaus), ar iš vartotojo (iš išorės). Paprastaisiais tipais laikome tuos, kuriuos matome tik iš išorės ir nekreipiame dėmesio kaip jie atrodo iš vidaus. Struktūriniai – tie, į kuriuos geriau žiūrėti iš vidaus. Kai struktūrinio tipo vidus pasidaro per daug sudėtingas ir galime į jį nekreipti dėmesio arba bent nerodyti kitiems, naudojame jį abstrakčiojo duomenų tipo pavidalu.
Duomenų tipo vidų atspindi jo realizacija, t. y. jo sandara ir veiksmai su jo komponentais. Paprastiesiems duomenų tipams būdinga mašininė realizacija, struktūriniams – realizacija, dažniausiai vartojama programavimo kalbų transliatoriuose, o abstrakčiųjų duomenų tipų realizacija rašoma programoje, naudojantis programavimo kalbos teikiamomis abstrahavimo priemonėmis.
1.4. Duomenų dinamika
Atmintis duomenims gali būti skiriama tik vieną kartą – programos transliavimo metu, arba keletą kartų – kiekvieno programos bloko kūrimo metu. Pirmuoju atveju, gaunama didžiausia veiksmų ekonomija, o antruoju – atmintis skirstoma dažniau, todėl tokia ekonomija negaunama. Dėl šios priežasties stengiamasi mažinti duomenų dinamiškumą ir kuo didesnę atminties skyrimo veiksmų dalį atlikti kuo rečiau.
Duomenų dinamiškumą galima nagrinėti trimis lygiais [4]:
1. kai kinta atminties kiekis vienai paprastai reikšmei saugoti;
2. kintant struktūrinio duomenų tipo komponentų skaičiui;
3. keičiasi kintamųjų skaičius.
Atminties kiekis vienai paprastai reikšmei saugoti priklauso nuo galimo skirtingų reikšmių skaičiaus. Pavyzdžiui savaitės dienos gali būti išreikštos sveikaisiais skaičiais, kintančiais intervale nuo 1 iki 7. Tačiau programavimo kalboje galimas reikšmių skaičius priklauso nuo konkretaus pasirinkto duomens tipo.
Struktūrinio duomenų tipo komponentų skaičius gali būti pastovus arba kintamas. Pavyzdžiui, Paskalio kalboje struktūra su pastoviu komponentų skaičiumi yra masyvas ar įrašas. Tiek konkretaus masyvo rėžiai, tiek įrašo komponentai yra fiksuojami jų sukūrimo momentu ir išlieka visą programos vykdymo laiką. Jeigu masyvų rėžius, arba įrašo elementus keistume, tai gautumėme dinamines struktūras, kurioms keičiantis kiekvieną kartą reikėtų perskirstyti ir kompiuterio atmintį. Todėl programavime dažniausiai naudojami statiniai masyvai, nors kartais jiems suteikiama ir dinaminių savybių.
Dinaminės duomenų struktūros pavyzdys gali būti eilė. Jos ilgis keičiamas, kai atliekama programa. Eilės komponentai neturi individualių požymių ir į eilę įrašomi ar skaitomi nuosekliai, vienas paskui kitą. Plačiau ši struktūra aptariama antrojoje darbo dalyje.
Kintamieji paprastai turi vardus ir jie aprašomi programoje. Šių kintamųjų skaičius yra fiksuotas programos tekste ir vykdant programą nėra keičiamas. Taigi kintamieji, kurių vardai aprašyti programoje, vadinami statiniais. Atminties skirstymo metu statinių kintamųjų vardai tvirtai susiejami su kompiuterio atminties adresais.
Be statinių, naudojami ir dinaminiai kintamieji. Dinaminiai kintamieji gaunami panaudojus rodyklės tipą. Rodyklė tai adresas kompiuterio atmintyje. Rodyklės tipas yra paprastasis, statinis. Rodyklės identifikuoja dinaminius kintamuosius, kurių reikšmės sukuriamos ir keičiamos atliekant programą. Pačios rodyklės reikšmė taip pat yra sukuriama ar keičiama vykdant programą. Rodyklė išsamiau aptariama antrojoje kursinio darbo dalyje.
Rodyklės yra kompiuterio atminties adresai, o reikšmių skaičių apibrėžia kompiuterio operatyviosios atminties adresų skaičius, todėl visos rodyklės priklauso tam pačiam duomenų tipui. Kadangi programavimas su rodyklėmis yra sudėtingas, todėl bandoma rodykles tipizuoti, t.y jų apraše nurodoma į kokio tipo dinaminį kintamąjį gali rodyti rodyklė [4].
2. TIESIOSIOS DINAMINĖS DUOMENŲ STRUKTŪROS
Dinaminės duomenų struktūros – tai tokios struktūros, kurias programos kūrėjas tvarko ar kuria pačios programos vykdymo metu. Be abejo, naudojamiems dinaminiams kintamiesiems būtinai reikalingas ir dinaminis kompiuterio atminties paskirstymas, kuris dažnai programose gali būti realizuojamas pasinaudojant rodyklėmis.
2.1. Rodyklė
Rodyklė yra paprastas statinis kintamasis, tiesiog saugantis kito kintamojo, kuris jau yra dinaminis, adresą ir tipą. Visada rodyklės kintamasis užima du word tipo laukus, kurie yra paskirstomi tai [4]:
1. pirmajame lauke įrašoma segmento reikšmė;
2. antrajame lauke įrašoma poslinkio reikšmė.
Svarbu paminėti, jog į atminties dalį, kurią nurodo rodyklė, gali būti įrašomas bet koks kintamasis ir jis gali užimti vieną ar kelis iš eilės einančius kompiuterio atminties baitus. Rodyklės gali būti dviejų rūšių: tipizuotos ir netipizuotos. Tai priklauso nuo to, ar jos yra susietos su konkrečiu duomenų tipu. Tipizuotos ir netipizuotos rodyklės Pascal programavimo kalba aprašomos taip, kaip parodyta 2.1.1 pav. [4].
a) b)
type var
pint = ^longint; rodykle: pointer;
var
b: ^byte; {rodo į byte tipo kintamąją}
c: pint; {rodo į longint tipo kintamąjį}
2.1.1 pav. Tipizuotos (a) ir netipizuotos (b) rodyklės aprašymas
Vykdant programą, kompiliatorius išskiria rodyklei 4 baitų atminties sritį.Kadangi šiuose baituose yra atsitiktinės reikšmės, tai rodyklėms reikia priskirti konstantas nil (Pascal kalba), kurios reiškia, kad rodyklė nerodo niekur. Šis priskyrimo veiksmas atliekamas tokiu sakiniu:
a1:= nil
Norėdami rezervuoti tam tikrą dinaminės atminties vietą kintamajam įrašyti, naudojame standartinę procedūrą New, kuri yra užrašoma taip:
procedure New (var a: pointer);
Naudojant šią procedūrą, kintamajam yra surandama mažiausia galima dinaminės atminties sritis, kurioje jis telpa, o šios srities pirmojo baito adresas užrašomas rodyklėje. Konkrečią duomens reikšmę į atmintį galime įrašyti tik įvykdę procedūrą New. Rodyklės dinaminis kintamasis nurodomas naudojant ženklą ^, kuris yra pripašomas po rodyklės vardo. Pavyzdžiui, rodyklė a1^ reiškia, tai, kas užrašyta atminties vietoje, į kurią nukreipia rodyklė a1.
Pabaigus darbą su dinaminiu kintamuoju, turi būti atlaisvinama jo naudota atminties vieta. Šiam procesui yra naudojama keletas procedūrų, priklausomai nuo to, ar buvo naudotos tipizuotos ar netipizuotos rodyklės.
Pirmuoju atveju naudojama standartinė procedūra Dispose. Šios procedūros parametras, kuris yra tipizuota rodyklė, rodo šalinamą dinaminį kintamąjį, o pati procedūra gali būti naudojama tik tuomet, kai rodyklės reikšmė nėra lygi nil, t. y. kai egzistuoja dinaminis kintamasis, į kurį nukreipta rodyklė. Ji aprašoma tokiu sakiniu:
procedure Dispose (var a: pointer);
Antruoju atveju, kai programoje naudojamos netipizuotos rodyklės, dinaminiai atminčiai skirstyti naudojamos GetMem ir FreeMem procedūros ir yra aprašomos taip:
procedure GetMem (var a: pointer; xxx: Word);
procedure FreeMem (var a: pointer; xxx: Word), čia a – rodyklė; xxx – rezervuojamos ar išlaisvinamos atminties dydis.
Daug kartų rezervuodami ir išlaisvindami atmintį dinaminiams kintamiesiems, susiduriame su problema, kai atminties srityse atsiranda klaidų ir reikia išlaisvinti visą atminties fragmentą. Šiam procesui naudojamos procedūros Mark ir Release. Jos aprašomos taip:
procedure Mark (var a: pinter);
procedure Release (var a: pinter);
Taigi pasirinkdami tipizuotas ir netipizuotas rodykles, taip pat naudodami šias anksčiau aprašytas procedūros kompiuterio atminčiai skirstyti, turime atkreipti dėmesį į tai, kad yra rekomenduojama vienoje programoje nenaudoti ir Dispose, ir FreeMem ar Release procedūrų, kadangi procedūra Release panaikina laisvos atminties sąrašą, kuris buvo suformuotas procedūromis Dispose ar FreeMem [4].
2.2. Tiesinis dinaminis sąrašas
Tiesinis dinaminis sąrašas – tai pradžios rodyklė ir rodyklėmis susietų vienodų elementų (dinaminių kintamųjų) seka. Pradedant nuo pradžios rodyklės paeiliui galima pereiti visus elementus. Visada sąrašo paskutiniame elemente yra sąrašo pabaigos požymis – tuščia rodyklė. Skirtingose programavimo kalbose šis elementas žymimas skirtingai, pavyzdžiui, Java kalboje konstanta null, C++ – null, o Pascal kalboje – nil.
a)
pr pr pr.kitas
kintamasis objektas objektas
b)
Pr Pr^ Pr^.sek
2.2.1 pav. Tiesinio dinaminio sąrašo sandara Java (a) ir Pascal (b) kalbomis [1]
Tiesinio dinaminio sąrašo grafinis vaizdas parodytas 2.2.1 pav. Čia elementas vaizduojamas stačiakampiu, padalintu į tiek dalių, kiek yra laukų jo struktūroje: duomenų ir adreso. Duomenų lauke saugomos reikšmės ,kurios šiame pavyzdyje nepateikiamos. Rodyklės tipo lauke saugomos nuorodos į kitą sąrašo objektą, ką galime nesunkiai pastebėti nagrinėdami šį paveikslėlį. Nuoroda yra vaizduojama rodykle, kurios pradžia yra nuorodos lauko viduje. Rodyklė remiasi į elementą vaizduojantį stačiakampį bet kurioje jo vietoje. Jeigu nuoroda neegzistuoja, tai linija nėra brėžiama ir laukas lieka tuščias. Tai reiškia, kad adreso reikšmė neapibrėžta. Tačiau realiose programose tokia situacija yra neleistina. Būtina užrašyti tuščio adreso reikšmę – konstantą null ( C++ ar Java kalba).
Pagal 2.2.1 pav., a dalį, pr yra Java kalbos kintamasis (tiksliau rodyklė į pr objektą, kadangi Java kalboje beveik visos konstrukcijos yra objektai, o Java kintamasis suprantamas ne kaip objektas, o kaip nuoroda (rodyklė) į tą objektą), kuris rodo į sąrašo pradžią. Pr objektas – pirmasis sąrašo objektas, turintis vienintelę ryšio rodyklę (Java kintamąjį), nurodančią pr.kitas objektą – kitą sąrašo elementą.
2.2.1 pav, b dalyje, aprašoma tiesinio dinaminio sąrašo sandara Pascal programavimo kalba. Čia Pr yra sąrašo pradžios rodyklė, Pr^ – pirmasis elementas, Pr^.sek – antrasis lementas. Paskutinio elemento rodyklė rodo sąrašo pabaigą, kuri aprašoma konstanta nil.
2.2.1. Sąrašo formavimas ir naujų elementų įrašymas. Sąrašas, kuriame nėra nei vieno elemento, vadinamas tuščiu. Kuriant naują ar plečiant esantį sąrašą, nauji elementai gali būti jungiami prie sąrašo pradžios, galo ar įterpiami tarp sąrašo elementų. Kaip jau minėjau anksčiau, sąrašo gale visada rašome konstantą nil.
2.2.1.1 pav. Naujo elemento prijungimas sąrašo pradžioje
2.2.1.2 pav. Naujo elemento prijungimas sąrašo gale
2.2.1.3 pav. Naujo elemento įterpimas tarp sąrašo elementų
2.2.2. Sąrašo peržiūrėjimas. Be abejo, kuriant programas, visada svarbus elementas yra jos peržiūrėjimas ir kompiuterio išvedami duomenys. Sąrašų atveju, išvedimas peržiūrėjimui aprašomas tokiu algoritmu:
2.2.2.1 pav. Sąrašo išvedimas peržiūrėjimui
2.2.3. Sąrašo elementų paieška. Norint sąraše rasti tam tikrą elementą, turinčio, pavyzdžiui, reikšmę “x” įprastai naudojamas toks algoritmas: elemento reikšmė “x” yra lyginama su kiekvieno sąraše egzistuojančio elemento duomenimis ir jei jau išėjus iš ciklo vis dar nėra pasiekta sąrašo pabaiga, tuomet ieškomas elementas surastas. Paskalio kalba tai aprašoma taip:
2.2.3.1 pav. Sąrašo elementų paieška
2.2.4. Elementų šalinimas iš sąrašo. Kadangi sąrašai yra kuriami ir įrašomi nauji elementai, tai reikalinga ir galimybė juos pašalinti iš sąrašo. Toks veiksmas atliekamas šiais sakiniais:
2.2.4.1 pav. Elementų šalinimas iš sąrašo
2.3. Elementariosios abstrakčiosios dinaminės duomenų struktūros
2.3.1. Stekas. Stekas (angl. Stack) yra vienas iš dažniausiajai naudojamų duomenų struktūrų. Tai tokia duomenų struktūra, kai prieinamas tik vėliausiai įrašytas elementas: programa gali perskaityti jo reikšmę, jį pašalinti arba prieš jį įrašyti naują.
Stekui apibrėžtos tokios operacijos [3]:
• inicializuoti steką (išskirti vietą stekui kompiuterio atmintyje);
• įterpti elementą x į steką (operacija push(x));
• pašalinti elementą iš steko (operacija pop);
• skaityti steką;
• panaikinti steką (panaikinti vietą stekui kompiuterio atmintyje).
Steką galime nesunkiai suprasti, palyginę jį su padėklų krūva valgykloje. Švarūs padėklai yra padedami ant viršaus ir paimamai tik nuo viršaus, todėl apatinis padėklas, kuris buvo padėtas pirmas, bus paimtas paskutinis, o viršutinis, kuris buvo padėtas vėliausiai, buvo paimtas pirmas. Visa tai apibūdina principas “paskutinis įeina, pirmas išeina” (angl. LIFO – Last In, First Out). Stekas gali būti pavaizduotas grafiškai struktūra, didėjančia arba mažėjančia tik viename gale – viršūnėje (2.3.1.1 pav.).
2.3.1.1 pav. Steko veiksmų iliustracija [1]
2.3.2. Eilė. Eilė (angl. Queue arba FIFO – Fist In, First Out) – tiesinė duomenų struktūra, iš kurios pradžios elementai šalinami ir į kurios galą įrašomi nauji elementai. Eilės tipo duomenų struktūrą apibūdina principas “kas pirmas įeina, tas pirmas išeina”.
Eilei apibrėžtos tokios operacijos [3]:
• inicializuoti eilę (išskirti vietą eilei kompiuterio atmintyje);
• įterpti tam tikrą elementą x į eilę (operacija put(x));
• pašalinti elementą iš eilės (operacija get);
• skaityti eilę;
• panaikinti eilę (panaikinti vietą eilei kompiuterio atmintyje).
Patariama, sudarant eilės tipo duomenų struktūras, aprašyti du kintamuosius pr ir g, kurių vienas rodo eilės pradžią, o kitas – galą. Tai svarbu dėl to, kad taip galima paspartinti elementų įrašymą į šią duomenų struktūrą, nes eilei papildyti nereikia kiekvieną kartą pereiti visų elementų. Galima naudoti tik vieną sąrašo pradžios rodyklę, bet šiuo atveju, įrašant į galą, galo rodyklę reikėtų pasiekti taikant rekursiją ar ciklinį elementų perrinkimą.
2.3.2.1 pav. Eilės veiksmų iliustracija [1]
2.3.2.1 pav. rodyklės pr punktyrinė linija rodo pirmąjį elementą prieš pašalinimą, o ištisinė – jį pašalinus. Rodyklės g punktyrinė linija rodo paskutinįjį elementą prieš įrašymą, o ištisinė – paskutinįjį naujai įrašytą elementą.
Eilę, kaip ir kitus dinamines duomenų struktūras, lengviau suprasti pasitelkus pavyzdžius, kurių vieną aš ir pateiksiu. Eilę galėtumėme palyginti su bilietų kasa: jeigu eilė netuščia, t. y. pr != null, tai gali būti aptarnaujamas ir panaikinamas pirmasis elementas [1]. Svarbu yra tai, kad aptarnavus paskutinį eilės elementą, t. y. esant tuščiai eilei, būtina pažymėti galo rodyklę g =null, o jeigu eilė jau yra tuščia, tai naujai įrašytas elementas tampa pirmuoju ir jį jau rodo ne tik pradžios rodyklė pr, bet ir pabaigos rodyklė g.
2.3.3. Dekas. Dekas (angl DEQue – Double-Ended QUEue) yra tokia duomenų struktūra, į kurią elementai įrašomi arba iš kurios pašalinami viename ir kitame gale. Dekas, kaip ir eilė ar stekas, yra viena iš riboto išrinkimo klasės struktūrų. Dekas dar vadinamas abipusiu steku (ar abipuse eile). Jo programavimas naudojant bazinį masyvo ar rodyklės tipą panašus į steko ar eilės programavimą, tik reikalauja sudėtingesnės realizacijos.
Dekui apibrėžtos tokios operacijos [3]:
• inicializuoti deką (išskirti vietą dekui kompiuterio atmintyje);
• įterpti tam tikrą elementą x į deko pradžią;
• įterpti tam tikrą elementą x į deko pabaigą;
• pašalinti elementą iš deko pradžios;
• pašalinti elementą iš deko pabaigos;
• skaityti deko pradžią;
• skaityti deko pabaigą;
• panaikinti deką (panaikinti vietą dekui kompiuterio atmintyje).
2.3.4. Dvikryptis sąrašas. Dvikryptis dinaminis sąrašas nuo paprasto skiriasi tuo, kad kiekvienas elementas turi antrą rodyklę, rodančią prieš jį esantį elementą. Dvikryptį sąrašą galima suprasti kaip du priešingomis kryptimis sujungtus vienkrypčius sąrašus, todėl jo tvarkymo funkcijos yra panašios į šių sąrašų tvarkymo funkcijas. Pagrindinis skirtumas yra tas, kad tvarkymo operacijose vienu metu reikia formuoti dvi rodykles. Be to, naudojant dvikrypti sąrašą, galima sudaryti universalias elementų įterpimo ir šalinimo operacijas, kurios tinka visiems sąrašo elementams, ne tik galiniams.
Visada pradžioje sąrašas yra tuščias, todėl pirmojo elemento rodyklės pr (pradžia) ir galinio elemento rodyklės g (galas) reikšmės turi būti nulinės – NIL (Pascal kalba).
2.3.4.1 pav. Dvikrypčio sąrašo grafinis vaizdas [1]
2.3.5. Ciklinis (žiedinis) sąrašas. Sprendžiat daugelį uždavinių yra labai patogu naudoti uždaro kelio ciklinį sąrašą, kuriame paskutinis elementas yra gretimas pirmajam (2.3.5.1 pav.).
2.3.5.1 pav. Ciklinio sąrašo grafinis vaizdas[1]
Veiksmai, naudojami su cikliniu sąrašu, yra panašūs į veiksmus su įprastu dinaminiu sąrašu, tačiau nei viename šio sąrašo elemente nėra sąrašo galo požymio. Todėl skaičiavimų pabaiga yra nustatoma lyginant tarpinę rodyklę su sąrašo pradžios rodykle. Jeigu sąraše yra tik vienas elementas, tai rodyklė rodys jį patį.
Cikliniame sąraše patogu sudaryti eilės struktūrą, kas leidžia po paskutinio elemento įterpti naują elementą, prieiti prie pirmojo ir jį pašalinti. Taip yra todėl, kad eilei reikalinga viena, paskutiniojo elemento, rodyklė.
2.3.6. Dvikryptis ciklinis sąrašas. Kiekvienas dvikrypčio sąrašo elementas turi dvi rodykles: kitas ir ankstesnis. Tuo tarpu dvikrypčio ciklino sąrašo paskutiniojo elemento rodyklė kitas rodo pirmąjį, o pirmojo rodyklė ankstesnis – paskutinįjį elementą (2.3.6.1 pav.).
pr
2.3.6.1 pav. Dvikrypčio ciklinio sąrašo grafinis vaizdas [1]
Reikėtų paminėti, kad veiksmus su dvikrypčiu cikliniu sąrašu galima supaprastinti naudojant fiktyvų pradžios elementą. Tokiu atveju sąrašo pradžią nusako jo rodyklė kitas, o galą – rodyklė ankstesnis. Fiktyvus elementas leidžia supaprastinti įrašymo į sąrašą ir šalinimo iš jo operacijas, o sąrašas bus laikomas tuščiu, kai jame liks tik fiktyvus elementas.
3. TIESINIŲ DINAMINIŲ DUOMENŲ STRUKTŪRŲ TAIKYMAI
Dinaminių duomenų struktūrų taikymas yra tiesiogiai susijęs su kompiuterio atminties paskirstymu, todėl šiame skyriuje panagrinėsiu atminties skirstymo ir jos dinaminio naudojimo galimybes ir priemones, išskirdamas tris dažniausiai praktikoje naudojamus atminties valdymo principus.
3.1. Kompiuterio atminties valdymas
Programos vykdymo metu tam tikri duomenys ir programos kodai turi būti saugomi kompiuterio atmintyje. Šiuos duomenis galime suskirstyti į tokias grupes [1]:
• Transliuota programa, vykdomasis modulis.
• Sisteminės programos.
• Vartotojo duomenys.
• Grįžimo ir įėjimo į paprogrames taškai.
• Laikina sritis aritmetiniams reiškiniams skaičiuoti (šaknys, rekursijos ir pan.)
• Įvedimo ir išvedimo sparčioji atmintis
• Įvairūs sisteminiai duomenys (lentelės, periferinių įrenginių būklės informacija ir pan.)
Kalbėdami apie atminties valdymo procesus, būtina paminėti, jog šie procesai itin sudėtingi ir aprėpia ne tik programoms ir duomenims skirtas sritis. Yra įprasta skirti tris kompiuterio atminties valdymo fazes [1]:
1. Pradinis paskirstymas. Kiekvieną kartą vykdant programą, kiekvienas blokas gali turėti savo paskirtį arba būti tuščias. Dėl šios priežasties reikalingas mechanizmas, skirtas užimamos ir laisvos atminties skirstymui.
2. Atminties panaudojimas. Jau panaudotą ir nebereikalingą atminties sritį atminties valdymo sistema turi ją nukreipti pakartotiniam panaudojimui. Atminties panaudojimas priklauso nuo jos skirstymo būdo ir gali būti paprastas, kai perstumiama steko nuoroda, arba labai sudėtinga, kai šiukšlės surenkamos į krūvą.
3. Atminties suglaudimas ir pakartotinis panaudojimas. Panaudota atmintis gali iš karto būti tinkama pakartotiniam naudojimui arba prieš tai ją reikia sutankinti, iš mažų blokų sudarant didesnius. Bendrai panaudota atmintis pakartotinai skiriama taip pat, kaip ir per pradinį skyrimą.
Taip pat norėčiau aptarti tris pagrindinius praktikoje naudojamus atminties valdymo principus:
1. Statinis atminties paskirstymas. Naudojant šį būdą, atminties sritis, išskirta transliavimo metu, nepakinta iki programos vykdymo pabaigos. Šis būdas yra efektyviausias, nes negaištamas laikas atminčiai perskirstyti, tačiau jis netinka rekursinėms programoms ir sudėtingiems dinaminiams duomenims saugoti. Pavyzdžiui, statinis atminties paskirstymas naudojamas FORTRAN programavimo kalboje.
2. Stekinis atminties paskirstymas. Šis metodas yra laikomas paprasčiausiu atminties valdymo metodu. Steke leidžiamos manipuliacijos su tais elementais, kurie yra steko viršūnėje. Atmintyje stekas gali būti pateiktas dviem būdais: nuosekliuoju ir susietuoju. Nuoseklioji forma dažniausiai naudojama tais atvejais, kai reikia sukurti steką, kurio apimtis yra iš anksto žinoma, t. y. yra rezervuojamas atitinkamas atminties blokas. Pirmasis bloko elementas – nuoroda į steko viršūnę, kuri reikalinga, kad būtų galima žinoti, ar stekas yra tuščias. Taip būna tokiu atveju, kai rodyklė rodo pati į save. Susietoji steko forma leidžia šalinti elementus iš atminties, tačiau jai reikia papildomos atminties elementų tarpusavio ryšimas saugoti, o kartu ir iš anksto rezervuoti papildomą atminties sritį.
Duomenų tipas
Rezervuoto bloko ilgis
Panaudota sritis
Nepanaudota sritis
3.1.1 pav. Nuosekliojo steko grafinė interpretacija [1]
Vienintelė steko nuoroda – tai viskas, ko reikia atminčiai valdyti. Ji visada rodo į tuščią žodį. Visa naudojama atmintis yra steke, žemiau pozicijos, kurią rodo steko nuoroda, o laisva atmintis yra už šios pozicijos. Stekinis atminties paskirstymas naudojamas programavimo kalbose, kurios turi lizdines paprogramių, procedūrų ar funkcijų struktūras, t. y., kai šių struktūrų viduje yra kitų paprogramių, procedūrų ar funkcijų aprašai. Kaip pavyzdžius galime paminėti programavimo kalbas PL/1, Modula, PASCAL ir kt.
3. Atminties skyrimas pagal krūvos principą. Krūva vadiname tokią atminties sritį, kuri dalimis ar visa gali būti skiriama arba atpalaiduojama specifiniu būdu, kuris nėra struktūrizuotas. Šiuo atveju didelę reikšmę turi pradinė keltis, naudojimas, suglaudinimas ir pakartotinis panaudojimas. Išskiriami du šios atminties valdymo atvejai [1]:
• Kai tenka krūvoje skirstyti fiksuoto ilgio elementus;
• Kai elementų ilgiai kinta.
Pirmuoju atveju skirstymo mechanizmas yra ganėtinai paprastas. Tam tikra atminties sritis yra suskirstoma į fiktyvų elementų K skaičių, kur N*K=visos srities ilgis. Taip yra aprašomas šiuo atveju taikomas atminties paskirstymo metodo pagrindas. Tam, kad laisvi elementai butų registruojami, yra sukuriamas laisvos atminties sąrašas (LAS), kuris saugomas už krūvos. Čia savo ruožtu saugoma nuoroda į kitą laisvą elementą ir t. t. Sąrašo viršuje esanti nuoroda rodo į tuščią elementą, kurį galima pašalinti iš sąrašo. Tada nuorodą į tą elementą reikia perkelti į sąrašo viršų. Tokiu būdu antrasis elementas tampa pirmuoju. Šalinant elementus, viskas daroma atvirkščiai. Dažnai gali būti sudėtinga surasti elementą – tai darbas, kurį gali atlikti programuotojas arba pati sistema.
Antruoju atveju atminties paskirstymo principas yra panašus kaip ir su fiksuoto ilgio elementais, tačiau susiduriama su keblumais pakartotinai panaudojant laisvą atmintį. Pavyzdžiui, jei LAS atsirastų dvi penkių žodžių ilgio sritys, tai šešių žodžių ilgio elementą sutalpinti būtų sunku. Naudojant kintamo ilgio elementų metodiką, pirmiausia į krūvą žiūrima kaip į vieną LAS bloką su nuoroda į krūvos pradžią. Kai reikalingas blokas iš N žodžių, tai nuoroda perstumiama per N žodžių, o naujai išskirtam elementui suteikiama pradinė krūvos nuoroda. Laisva sritis už krūvos per nuorodą įjungiama į LAS, o kai nuoroda pasiekia srities pabaigą, galima susidariusią laisvą atmintį panaudoti pakartotinai. Tai yra daroma dviem būdais [1]:
• Tiesioginis LAS panaudojimas, kai yra surandamas tinkamo ilgio blokas ir atskiriamas, o likusi dalis grąžinama į LAS;
• LAS suglaudinimas, kai visos laisvos sritys yra perkeliamos į krūvos galą atitinkami pakeičiant ir nuorodą į krūvą.
Tačiau dažniausiai naudojamas kombinuotas metodas, rūšiuojant LAS pagal blokų judėjimo tvarką ir suglaudinant susidariusius likučius.
IŠVADOS
Šiame kursiniame darbe nagrinėtos dinaminės duomenų struktūros ir jų taikymai programose. Pirmasis skyrius yra skirtas bendram susipažinimui su sąvokomis: kintamasis, reikšmė, duomenys, duomenų tipas ir nagrinėja šiuos aspektus. Skyrius baigiamas duomenų dinamikos aptarimu, taip nurodydamas pagrindinę darbo temą, kuri yra plačiau nagrinėjama antrajame skyriuje. Čia aptariamos įvairios dinaminės duomenų struktūros, pradedant nuo paprasčiausios – rodyklė, kuri yra reikalinga ir kitose dinaminėse duomenų struktūrose, pavyzdžiui, tiesiniame dinaminiame sąraše. Toliau nagrinėjamos elementariosios abstrakčiosios dinaminės duomenų struktūros: eilė, stekas, dekas, dvikrypčiai, cikliniai ir dvikrypčiai cikliniai sąrašai. Nagrinėjant šias struktūras, gausiai naudojamos grafinės priemonės, kad darbas būtų kuo aiškesnis. Taip pat pateikiami įvairių naudojamų procedūrų pavyzdžiai Turbo Pascal programavimo kalba. Paskutinėje dalyje trumpai aptariamas dinaminių duomenų struktūrų taikymas realiuose uždaviniuose, taip pat nagrinėjamas kompiuterio atminties valdymo procesas bei jo dinaminės savybės.
Šis kursinis darbas iš esmės skirtas teoriniam dinaminių duomenų struktūrų nagrinėjimui ir analizei, siekiant suprasti bei pateikti svarbiausius jų naudojimo principus ir galimybes. Tęsiant šią temą, būtų tikslinga gilintis į techninę šių struktūrų realizaciją ir konkrečiais įvairių programavimo kalbų pavyzdžiais perteikti jų panaudojimo galimybes.
Apibendrinant šį darbą, galima teigti, kad pradžioje iškelti tikslai įvykdyti: vykdant teorinę įvairių literatūros šaltinių analizę, aptartos įvairios dinaminės duomenų struktūros, apibūdintas jų panaudojimas ir visa tai iliustruota grafiškai. Svarbiausia tai, kad dinaminės struktūros suteikia programuotojui gerokai didesnę duomenų panaudojimo glimybę, kadangi atsiranda galimybė dinamiškai valdyti kompiuterio atmintį ir panaudoti optimalų jos kiekį.
LITERATŪRA IR ŠALTINIAI
1. Baniulis, K., Tamulynas, B. Duomenų struktūros: vadovėlis. – Kaunas: Technologija, 2003. – 283 p.
2. Grigas G. Duomenų tipai. – Vilnius: Žuvėdra, 1997. – 263 p.
3. Juozapavičius, A. Duomenų struktūros ir algoritmai: mokomoji priemonė. – Vilnius: Vilniaus universiteto leidykla, 1997. – 93 p.
4. Programinė įranga: paskaitų konspektai. – Vilnius, 2005. Dėstytoja Ona Barčkutė.
5. Vidžiūnas A., Blonskis J. Dinaminės duomenų struktūros. – Kaunas: Vytauto Didžiojo universiteto leidykla, 1998. – 63 p.
6. Vidžiūnas A. C++ duomenų tipai ir struktūros. – Kaunas: Smaltija, 1999. – 240 p.