Saturs
1. Jēdziens par datu struktūru. Datu
struktūru klasifikācija (Fiziska un loģiska).................................................................................... 2
2. Vektori
un masīvi.............................................................................................................................................................................. 2
3. Steks,
divu steku uzturēšana............................................................................................................................................................. 2
4. Rinda................................................................................................................................................................................................. 2
5. Vienvirziena
saraksti......................................................................................................................................................................... 2
6. Divvirzienu
saraksti.......................................................................................................................................................................... 2
7. Aritmētiskas
izteiksmes pieraksta formas. Aritmētiskas izteiksmes pārveidošana uz postfisko
formu. Izteiksmes vērtību aprēķināšana. 3
8. Grafs,
ar to saistītie jēdzieni. Grafa uzdošana.................................................................................................................................... 3
9. Grafa,
attēlošana atmiņā.................................................................................................................................................................... 3
10. Grafa
apstaigāšanas algoritmi......................................................................................................................................................... 3
11. Koks,
ar koku saistītie jēdzieni. Teorēma par koku....................................................................................................................... 3
12. N-ārs
koks, binārs koks. Binārā koka paveidi. Attēlošana atmiņā.................................................................................................. 3
13. Binārais
meklēšanas koks.............................................................................................................................................................. 4
14. AVL
koks...................................................................................................................................................................................... 4
15. Bināra
koka apstaigāšana............................................................................................................................................................... 4
16. Pavedienu
koki.............................................................................................................................................................................. 4
17. Koku
pielietojumu piemēri............................................................................................................................................................ 4
18. Kaudzes......................................................................................................................................................................................... 4
19. Tabula........................................................................................................................................................................................... 4
1. Jēdziens par datu struktūru. Datu struktūru klasifikācija (Fiziska un loģiska)
Par datiem sauc jebkuru informāciju, kura tiek
aplūkota uzdevuma risināšanas gaitā. Datus var aplūkot kā informācijas vienību
kopumu, starp kuriem ir noteiktas attiecības. Šīs attiecības sauc par datu struktūru.
Datus glabā kā bitu virknes. Sarežģītas datu
vienības ir datu tips, kas raksturojas ar datu tipa vērtību kopu un ar
operācijām, ko var veikt ar datiem. Piemēram: BOOLEAN: 0 –1 vai True – False.
Tos var salīdzināt.
Datu struktūra ir kopums no datu elementiem,
un katrs elements ir datu elements un otrais ir saites elements.
Struktūras var loģiskas un fiziskas. Loģisko un fizisko struktūru
atšķirību var parādīt ar masīva palīdzību. Piemēram. Dots 3X3 masīvs: loģiskā
struktūra izskatās
123
456
789
bet atmiņā masīvs attēlojas kā rindiņas (vai kolonas) no trijiem
elementiem 123,456,789,. Tā ir fiziskā struktūra. Vienai loģiskai struktūrai var būt dažādās
fiziskās struktūras t..i. masīvu var attēlot pa rindām un pa kolonām.
Datu struktūras var klasificēt pēc dažādiem
kritērijiem:
1.
vai eksistē saites elements, vai tas ir tukšs: saistītas, nesaistītas.
2.
vai datu struktūrā ir mainīgs elementu skaits statisks(masīvs), daļēji
statisks(steks), dinamisks (kopa u.t.t.); Pēc sakārtošanas veida: lineārs
(masīvs – katram elementam var noteikt kurš ir iepriekšējais(nākošais))
2. Vektori un masīvi
Par vektoru sauc viendimensionālu masīvu, t.i.
elementus kopu, kuri atrodas vienā rindā (kolonā).
Par masīvu sauc viena tipa datu sarakstu, Lai nodefinētu norādu uz kaut
kādu masīva elementu, var izmantot izteiksmi, kura sastāv no masīva vārda un
indeksa. Katra masīva elementus var uzskatīt par neatkarīgo mainīgo.
Atmiņā masīvu attēlo linearizācijas ceļā, un
ir vairāki veidi , kā to darīt. Masīvs
ir statiska un nesaistīta struktūra. Ar masīvu var veikt sekojošas
operācijas: ierakstīt vērtību, nolasīt elementu. Par masīvu var pateikt, cik
vietas tas aizņem atmiņā, var atrast norādi uz pirmo elementi, un var atrast
masīva elementa adresi pēc formulas adr(m[I])=m+n*I (viendimesnionālam
masīvam), kur m-norāde uz 1.elementu, n –cik vietas aizņem viens masīva
elements un I – elementa numurs; vai adr(m[i,j])=m+(n*k)+I+(r*j)
(divdimensionālam masīvam, kur r rindu skaits, k - kolonu skaits.
3. Steks, divu steku uzturēšana
Par steku sauc rezerves atmiņas apgabalu, kurā
programmas ieraksta datus par stāvokli. Steks ir sakārtota datu struktūra,
kurai piemīt īpašība – pēdējais atnāca, pirmais aizgāja. Programmas stekā var
ierakstīt procedūru vai funkciju datus, parametrus, lokālus mainīgos.
Steks ir daļēji statiska struktūra. Ir
noteikts steka garums. Stekā var ierakstīt elementu un izņemt pēdējo.
Divus stekus var uzzīmēt vienā masīvā. Tad no viena masīva gala
(sākuma) var veidot vienu steku, un no otra )(beigas) – otru steku.
4. Rinda
Par rindu sauc tādu datu struktūru, no kuras
elementus ( pēc stingras definīcijas) var izņemt pēc noteiktas kārtības – tādā
secībā, kurā tiek ievietoti: pirmais atnāca – pirmais aizgāja. Rindai piemīt
divas operācijas: jauna elementa pielikšana klāt, un visvecākā izņemšana no rindas.
Eksistē divpusējas rindas – tā ir tāda datu struktūra, kurai elementus var
ielikt un izņemt no abām pusēm.
Rinda ir daļēji statiska, nesaistīta un
lineāra datu struktūra. Rindā var būt noteikts elementu skaits. Rindai ir divas
norādes: uz sākumu un beigām. Sākumā abas norādes ir nulles. Tad, kad tās sakrīt,
rinda ir tukša. Izņemšanas laikā, izņem to, uz kuru norāda 1.bulta, un tā
norādīs uz nākošo. Kad rinda ir pilna, tad norādes (abas) norāda uz pirmo
elementu. Trūkums ir tāds, ka vajag
definēt masīvu par vienu elementu vairāk, lai norādes, kad rinda ir pilna un
tukša, nesakristu elementu skaits pēc formulas S=(S+1)mod(M+1). M+1 – cik ir
elementu masīvā.
5. Vienvirziena saraksti
Par sarakstu sauc sakārtotu lineāru secību.
Visi elementi ir saistīti ar norādi uz citu elementu. Saraksta elementam ir
divi lauki – datu elements un norāde.
=>OX=>OX=>…=> (O-datu elements. X-norāde). Ja norāde ne uz
kurieni nenorāda, tad tā ir tukša norādi jeb nil. Ar vienvirziena sarakstu var
veikt sekojošas darbības: meklēt
vajadzīgo elementu; ielikt elementu vajadzīgā vietā; izmest elementu.
6. Divvirzienu saraksti
Par divvirzienu sarakstu sauc sakārtotu
elementu secību, kura ir trīs lauki: datu elements (O), norāde uz nākošo
elementu - (X), norāde uz iepriekšējo elementu - (H). Ja norāde uz ne uz
kurieni nenorāda, tad tā ir tukša norāde jeb nil. Pateicoties divvirzienu
sarakstam, sarakstu var apstrādāt no abām pusēm – uz priekšu un atpakaļ.
Ar divvirzienu sarakstu var veikt sekojošas
darbības: meklēt vajadzīgo elementu;
ielikt elementu vajadzīgā vietā; izmest elementu.
7. Aritmētiskas izteiksmes pieraksta formas. Aritmētiskas izteiksmes pārveidošana uz postfisko formu. Izteiksmes vērtību aprēķināšana.
Aritmētiskas izteiksmes var pārveidot trīs
veidos: prefiksā, postfiksā un infiksā formā.
Postfikso pierakstīšanas formu sauc par rotāciju. Tas ir aritmētiskās izteiksmes
pieraksta veids, kad operators atrodas pēc operandiem (bez iekavām). Piemēram
dota izteiksme: A=((B*C)+(D*(E-F))), postfiksā izskatās ABC*DEF-*+=., prefiksā pierakstīšanas
gaitā no sākuma pieraksta operāciju, pēc tam operandu =>: A+*BC*D-EF, Infiksā pierakstīšanas veids ir
apzīmējumu sistēma, kurā divvietīgus operandus pieraksta starp argumentiem, un vienvietīgus
– pirms argumenta.
8. Grafs, ar to saistītie jēdzieni. Grafa uzdošana
Par grafu
sauc galīgu plaknes punktu kopu, kura zīmējumā var būt bultas no vien punkta
uz citiem. Par grafu sauc algebrisku
sistēmu G=(V,Y), kur katram X<-V(-| xYx) . Kopas V elementus sauc par
virsotnēm. Grafa pārīšus sauc par lokiem jeb šķautnēm. Par ceļu grafā sauc
virsotņu X1…xk virkni, ja xiYx(I+1), ja j=1..k-1. Par grafa G=(V,Y) virsotņu
tuvības matricu sauc attiecības Y matricu.
Grafa īpašības: 1) grafs ir saistīts, ja
nesatur ciklus; 2) grafs nesatur ciklus, ja virsotņu skaits ir V un šķautņu
skaits ir V-1; 3) grafs ir saistīts, ja tam ir V-1 šķautņu; 4) grafs nesatur ciklus un ja tiek pievienota vien
šķautne veidojas cikls; 5) grafs ir saistīts ja kaut viena šķautne tiek
pievienota, tad tas kļūst nesaistīts; 6) katras divas virsotnes savieno viens
ceļš.
9. Grafa, attēlošana atmiņā
Atmiņā grafs tiek attēlots ar matricas
palīdzību, kura glabājas ar divdimensionāla masīva palīdzību, ja dots grafs ar
n virsotnēm, tad veido N*N matricu, ja starp I un J virsotnēm eksistē saistība, tad vietā [i,j] tiek
ierakstīts 1 pretējā gadījumā 0.
10. Grafa apstaigāšanas algoritmi
Grafu var apstaigāt divos veidos, parasti,
izmantojot rindu, t.i. dziļumā un plašumā. Dziļumā apstaigāšanas metode ir
sekojoša. Pa pašu kreisāko ceļu iet līdz pēdējai virsotnei, pēc tam apskata
labāko ceļu u.t.t.
Plašumā apstaigāšanas metode sekojoša – no
sākuma tiek aplūko viena virsotne pēc tam nākošā līmeņa virsotnes – tās, ar
kurām ir saistīta dotā, pēc tam nākošā līmeņa virsotne u.t.t
11. Koks, ar koku saistītie jēdzieni. Teorēma par koku.
1. Grafu ar vienu virsotni sauc par koku.
2. Koka virsotnei, pievienojot jaunu šķautni un jaunu virsotni, iegūto
grafu sauc par koku.
(Neorientētu) grafu sauc par koku, ja tas ir sakarīgs un nesatur
nevienu ciklu
Punktu A sauc par
koka sakni.
Punktus no A līdz K sauc par koka virsotnēm.
Nogriežņus AB līdz GK sauc par koka šķautnēm
jeb zariem.
Punkti B un C ir virsotnes A bērni; D,E,F – virsotnes B bērni; u.t.t.
Par lapām sauc virsotnes, kurām nav bērnu.
Punktus B un C sauc par kaimiņiem.
Grafu sauc par koku, ja no vienas virsotnes līdz otrai eksistē tikai
viens ceļš.
Teorēma. Pilnam bināram kokam lapu skaits ir iekšējo virsotņu skaits.
Kokam ir arī līmeņi.
Sakne – 1.līmenis
(0)
Bērni – 2.līmenis (1)
Mazbērni – 3.līmenis (2) u.t.t.
Teorēma: Katram bināram kokam ar X līmeni
maksimāli iespējamās 2^(X-1) virsotnes
Teorēma: pavisam virsotnes pilnā kokā ir
2^x-1.
12. N-ārs koks, binārs koks. Binārā koka paveidi. Attēlošana atmiņā.
Koku sauc par n-āru, ja no vienas puses iziet līdz N šķautnēm jeb
N apakškoku.
Koku sauc par bināru, ja no vienas virsotnes iziet divas šķautnes.
Koku sauc par pabeigtu, ja lapas ne vairāk kā 2.līmeņos un visas lapas
ir no kreisās puses.
Ja zinām virsotnes indeksu (saknei=1), var atrast ka virsotnei ar
indeksu X kreisais bērns =2X, labais bērns 2X+1. Virsotnei X vecāks ir veselā
daļa no (X/2), Labais kaimiņš (X) – ja X – pāru = X+1
Kreisais (X) ja x
– nepāru = X-1
Binārais meklēšanas koks ir tāda datu struktūra, kad katrai koka
virsotnei pieraksta datus, ka visi kreisie apakškoki mazāki par doto virsotni
un visi labie apakškoki lielāki par doto virsotni.
Par AVL koku sauc tādu bināro meklēšanas koku, kuram katrai virsotnei
labās un kreisās apakškoka dziļumi atšķiras ne vairāk kā par 1.
13. Binārais meklēšanas koks
Koku sauc par bināru, ja no vienas virsotnes
iziet divas šķautnes.
Binārais meklēšanas koks ir tāda datu struktūra, kad katrai koka
virsotnei pieraksta datus, ka visi kreisie apakškoki mazāki par doto virsotni
un visi labie apakškoki ir lielāki par doto virsotni.
14. AVL koks
Par AVL koku sauc tādu bināro meklēšanas koku,
kuram katrai virsotnei labās un kreisās apakškoka dziļumi atšķiras ne vairāk kā
par 1.
15. Bināra koka apstaigāšana.
Eksistē trīs binārā koka apstaigāšanas
algoritmi: inorder, postorder, preorder.
Inorder apstaigāšanas realizējas tādā veidā, ka no sākuma tiek aplūkots
kreisais apakškoks, pēc tam pati virsotne un pēdējais tiek aplūkots labais apakškoks.
Postorder apstaigāšanas realizējas tādā veidā, ka no sākuma tiek
aplūkots kreisais apakškoks, pēc tam labais apakškoks, pēc tam virsotne.
Preorder apstaigāšanas realizējas tādā veidā, ka no sākuma tiek
aplūkota virsotnei, pēc tam kreisais apakškoks, pēc tam labais apakškoks.
16. Pavedienu koki.
Glabājot bināro koku atmiņā, rodas tukšas
norādes. Un lai tas nebūtu – tiek ieviests pavedienu koks, kura kreisa tukšā
norāde aizstājas ar norādi, kura izdrukātos pirms dotās virsotnes inorder
apstaigāšanas laikā, un labā tukšā norāde aizstājas ar norādi, kura izdrukātos
pēc dotās virsotnes inorder apstaigāšanas laikā.
Lai glabātu koku ir lietderīgi nodefinēt
papildus vidus laukus, kuri sastāv no viena bita 1 vai 0. Bits 1 nozīmē, ka ir norāde
uz citu elementu, 0 – ka nav.
Tādēļ ir vieglāka apstaigāšana, jo tā veidojas bez steka un rekursijas.
Lai uzrakstītu apstaigāšanas algoritmu vajadzētu uzrakstīt funkciju,
kuras argumenti ir norāde uz virsotni, un atgriež norādi.
Function insuc(X);
S:=x.right
If x.,rightbit = 1 then
While s.leftbit = 1 do
S:=s.leftbit
Return s
End.
Procedure inorder(T);
Head:=T;
Loop
T:=Insuc(T);
If T=Head then return(T)
Print(T.data)
Forever
End.
17. Koku pielietojumu piemēri.
Kokus var pielietot, risinot dažādus
uzdevumus, Kokus var pielietot, risinot algebriskus uzdevumus. Piemēram,
varbūtību teorijā. Eksistē ar loģiskās izteiksmes koki. Izmantojot kokus var
attēlot cilvēku radniecības attiecības.
18. Kaudzes
Par kaudzi sauc tādu pabeigtu lineāro koku, kuram katram apakškokam
sakuma atslēga ir lielākā apakškokā.
19. Tabula
Par tabulu sauc tādu datu struktūru, kura
parasti sastāv no ierakstu virknes, katrai no kuriem ir individuālais
identifikators jeb atslēga un satur kādas vērtības. Parasti tabulu glabā
atmiņā, kā rakstu masīvu, kā sarakstu ar norādēm vai kā masīvu ar dažādiem datu
tipiem, kuriem ir kopīga indeksācijas shēma. Tabulai ir kolonas, kurām ir
nosaukumi. Tabulai ir bezgalīgi daudz rindiņas. Tabulās var arī meklēt informāciju
pēc dotās atslēgas.
Nav komentāru:
Ierakstīt komentāru