1 DATU STRUKTŪRAS 2. lekcija – Datu jēdziens. Datu tipa jēdziens. Datu tipu klasifikācija

2 Informācijas jēdziens Enciklopēdijas vārdnīcā informācija raksturojas kā vispār zinātnisks jēdziens, kas iekļauj informācijas apmaiņu starp cilvēkiem, cilvēku un automātu, automātu un automātu; signālu apmaiņu dzīvnieku un augu pasaulē; pazīmju nodošanu no šūnas šūnā, no organisma organismā Informācija ir jebkuras ziņas par objektu, procesu un notikumu no apkārtējās pasaules.

3 Datu (data) jēdziens Dati un informācija ir sinonīmiski jēdzieni, kas tomēr nav identiski. Dati ir formalizētā veidā attēlota informācija jaunas informācijas iegūšanai. Datiem ir noteikta uzbūve jeb struktūra. Struktūra ir datu elementu saistības raksturs un to izkārtojums objektā vai sistēmā.

4 Datu tipa (data type) jēdziens Matemātikā datus klasificē pēc noteiktām pazīmēm un īpašībām. Ir skaitliskie dati un loģiskie dati. Skaitliskie dati iedalāmi veselos, reālos un kompleksos skaitļos. Dati glabājas datoru atmiņā, un datori operē ar datiem. Šie dati ir klasificējami pēc datu tipiem. Katrā programmēšanas valodā ir definēti savi konkrēti datu tipi.

5 Datu tips nosaka: vērtību tipu iespējamu vērtību apgabalu atmiņas apjomu un datu glabāšanas formātu pieļaujamās operācijas un funkcijas

6 Datu tipu klasifikācija Datu tips Skalārs datu tipsStrukturēts datu tips Predefinēts skalārs datu tips Lietotāja definēts skalārs datu tips Predefinēts strukturēts datu tips Lietotāja definēts strukturēts datu tips

7 Predefinēts skalārs datu tips char integer (byte, word, shortint, longint) real (double, single, extended) boolean

8 Lietotāja definēts skalārs datu tips uzskaitāmais datu tips diapazona datu tips lietotāja datu tips rādītāja datu tips

9 Predefinēts strukturēts datu tips virknes tips (string) masīva tips (array) ieraksta tips (record) kopas tips (set) faila tips (file) objekta tips (object)

10 Lietotāja definēts strukturēts datu tips tabulas (table) saraksti (list) steki (stack) rindas (queue) koki (tree) grafi (graph)

11 Uzskaitāmais tips Aprakstot šo tipu, programmētājs uzdod (uzskaita) visas tās vērtības, kuras mainīgajam varēs piešķirt, ja tas būs aprakstīts kā šī tipa mainīgais. Uzskaitāmā tipa mainīgie programmā var pieņemt tikai tādas vērtības, kuras uzskaitītas vērtību sarakstā. Piemēram: Type Vasara=('Junijs', 'Julijs', 'Augusts'); Uzskaitāmajam tipam pieļaujamas tikai salīdzināšanas operācijas, tam pielietojamas standartfunkcijas: Succ(x) -> uzdod aiz simbola x sekojošu simbolu no vērtību saraksta; Pred(x) -> uzdod aiz simbola x iepriekšējo simbolu no vērtību saraksta; Ord(x) -> uzdod simbola x kārtas numuru konkrētā simbolu kopā.

12 Piemērs Program Week; Type Week = (Monday, Tuesday, Wednesday, Thursday, Friday, Saturday, Sunday); Var Day: Week; Begin Day := Thursday; if (Day = Sunday) or (Day = Saturday) then Writeln('Brīvdiena') else Writeln(' Darbadiena'); End. Vērtību sakārtots kopums

13 Diapazona datu tips Jebkuram skalāram lielumam, izņemot daļskaitļus, var izveidot jaunu skalāru lielumu ar vērtību ierobežojumu kādā intervālā (diapazonā). Intervāla noteikšana paaugstina programmas drošību, ekonomē atmiņas izmantošanu, kā arī programmas izpildes laikā kontrolē piešķiršanas operācijas. Intervālu (diapazonu) var noteikt: 1) tipu apraksta daļā; Type =.. ; 2) mainīgo apraksta daļā; Var [,..]:.. ; kur - apakšējā robeža; - augšējā robeža.

14 Operācijas const X = 50; Y = 10; Type Interval = ; Gads = ; Scale = 2 * (X - Y)..(X + Y); Var burts: 'A'..'Z'; atzime: 1..10; Ar ierobežotiem mainīgiem saistītas kārtības operācijas ORD, SUCC, PRED, kā arī salīdzināšanas operācijas: >,, >=,<=.

15 Piemērs Kārtības operācijas nosaka elementa numuru, kas atbilst uzdoto vērtību sarakstam. Šis numurs sākas ar nulli (pirmais elements), kam seko vieninieks (otrais elements), utt. Tātad, ja uzdod mainīgo vērtības: CIPARS:='2'; BURTS:='B'; DIENA:=OTR; Tād izpildot rindiņu: WRITE (CIPARS, ORD(CIPARS), BURTS, ORD (BURTS), DIENA); Iegūsim: 2 50 B 66 1 Šeit '2' - mainīga CIPARS vērtība, '50' - cipara '2' kods, 'B' - mainīgā BURTS vērtība, '66' - burta 'B' kods, '1' - vērtības OTR numurs mainīgajam diena. VAR CIPARS: '0'..'9'; BURTS: 'A'..'Z'; DIENA: (PIR, OTR, TRE, CET, PIE, SES, SVE);

16 Masīva tips (array) Katrs programmā lietotais masīvs ir jānodefinē, piešķirot nosaukumu un norādot dimensiju skaitu, masīvu maksimālo elementu skaitu un elementu tipu. Var : Array [.. ] of ; kur, - jebkurš vesels skaitlis. Piemēram: Var Diena : Array [1..7] of String; masīva elementu indeksu vērtības, 1 – masīva elementu mazākais indekss (masīva Diena 1. elementa indekss); 7 – masīva elementu lielākais indekss (masīva Diena pēdējā elementa indekss).

17 Ieraksts (record) Ieraksts ir datu struktūra, kurā sakopoti dažāda tipa un dažāda garuma dati. Atsevišķu ieraksta lauku sauc par ieraksta komponenti. Datu tips ir jāuzdod katrai ieraksta komponentei, datu tips var būt jebkurš - skalārs vai strukturēts. type Date = record Day: ; Month: ; Year: ; end; work = record id: string [20]; start: Date; stop: Date; end;

18 Ieraksts (record) (2) Ieraksta lauki var būt izvietoti vairākos hierarhijas līmeņos. Lai organizētu piekļuvi ieraksta laukiem, lieto selektoru – saliktu nosaukumu, kurā ieraksta mainīgo un atsevišķas komponentes nosaukumu atdala ar punktu. Katram hierarhijas līmenim jāparedz punkts un lauka nosaukums.

19 Ieraksts (record) (3) Piemēram: var Q: work; Saliktie nosaukumi: Q.id – piekļuve darba nosaukumam, Q.start.Year – piekļuve darba uzsākšanas gadam, Q.stop.Day – piekļuve darba pabeigšanas dienai. writeln(Q.id, Q.start.Year, Q.stop.Day); Ieraksta lauku apstrādei plaši lieto operatoru with, piemēram: with Q do writeln(id, start.Year, stop.Day);

20 Kopas tips (set) Daži aprēķini pamatojas uz kopu jēdziena. Lai PASCAL valodā uzdotu kopu, jāpārskata tās elementi: PROGRAM KOPA; VAR A: SET OF 'A'..'Z'; B: CHAR; BEGIN A: = ['A','D','Q']; READ (B); WRITE (B IN A); END. "TRUE", ja tiks ievadīts viens no kopas A burtiem. Citos gadījumos dators paziņos: "FALSE"

21 Piemēri Datora visu simbolu kopa: VAR M: SET OF CHAR; Noteikta intervāla veselo skaitļu kopa: VAR G: SET OF ; Visu ciparu kopa: VAR C: SET OF '0'..'9';

22 Faila tips (file) Fails - tā ir informāciju elementu kopa (skaitļu, simbolu, kodu), kas pēc fiksēta nosaukuma pieejama datoram (magnētiskais disks, magnētiskā lenta, optiskais disks utt.). Par failu var programma, teksts, tabula, datora ekrāna kopija, katalogs, burtu grafiskie kodi un tml. Fails var būt tukšs, t.i., nesatur nevienu elementu, izņemot faila nosaukumu. Tāda gadījumā saka, ka faila garums ir vienāds ar nulli. Citos gadījumos garumu (apjomu) mēra baitos. Piemēram, ja failā atrodas kādas grāmatas teksts, kas sastāv no simboliem, tad runā par faila garuma baitiem, jo katram simbolam atbilst viens baits. Bet, ja failā atrodas piemēram, 130 veselie skaitļi, tad faila garums ir 260 baiti, jo viens veselais skaitlis datorā aizņem divus baitus. Līdzīgā kārtā var izvērtēt jebkura faila garumu.

23 Operācijas Atvēršana Gatavo failu lasīšana Jauno failu ierakstīšana Aizvēršana

24 Datu tipu raksturojumi Praktiski katrā programmēšanas valodā ir iebūvēts vienkāršo datu tipu komplekts; var būt arī līdzekļi, kas nodrošina iespēju definēt jaunus tipus. Datu tipa specifikācija raksturo datu tipu: kādas vērtības var pieņemt attiecīgie mainīgie, kā tos var izmantot, kādas operācijas un funkcijas tiem var pielietot utt. Datu tipa realizāciju izvēlas kompilatora izstrādātājs (pamatojoties uz specifikāciju, aparatūru un savu gaumi): kā novietot datus atmiņā, pēc kādiem algoritmiem aprēķināt funkciju un operāciju rezultātus, kādā mērā var izmantot iebūvētos datu tipus un iebūvētās operācijas.

25 Pamatelementi Datu tipa specifikācijas pamatelementi ir: atribūti, kas raksturo dotā tipa datu objektus (tipa nosaukums un precizējoši parametri) vērtības, kuras var pieņemt dotā tipa datu objekti operācijas, kuras nosaka iespējamās manipulācijas ar dotā tipa datu objektiem

26 Operācijas Pēc operandu skaita izdala šādas operāciju grupas: unāras operācijas: viens operands un viens rezultāts, piemēram, x++; bināras operācijas: divi operandi un viens rezultāts, piemēram, x+y; operācijas ar lielāku operandu skaitu (sastopamas samēra reti), piemēram: (x>0)?sqrt(x):-x*x;

27 Datu tipa realizācijas pamatelementi: datu objektu attēlošanas veids datora atmiņā operāciju attēlošanas veids - operāciju realizācijas algoritmi

28 Datu objekts Datu objekts ir viens vai vairāki datu elementi, kas glabājas datora atmiņā kā viens vesels. Dažus datu objektus nosaka (definē) programmētājs (piemēram, mainīgos un konstantes), citus datu objektus nosaka (veido pēc nepieciešamības) sistēma (piemēram, apakšprogrammu aktivizācijas ieraksti). Katram datu objektam ir noteikts dzīves laiks, piemēram, globālie dati eksistē visu laiku, kamēr izpildās programma, bet lokālie dati dzīvo tikai kamēr izpildās "dzimtā" apakšprogramma.

29 Mainīgais Mainīgais ir datu objekts, kuru programmētājs tieši definēja un nosauca. Uzskata, ka mainīgais ir tāds datu objekts, kura vērtību var mainīt, pielietojot piešķires operāciju, un parasti tas notiek vairākas reizes tā dzīves laikā. Konstante ir datu objekts, kura vārds ir saistīts ar vienu vērtību dzīves laika gaitā. Piemēram, programmas fragmentā: const int Max=100; int Av=Max/2; /* Max=100 ir konstante ar vārdu, "2" - burtiskā konstante, Av - mainīgais. */

30 Datu apraksts Datu apraksts ir speciāls operators, kas paziņo translatoram informāciju par datu objektu vārdiem un tipiem. Datu apraksta vieta programmā nosaka arī to dzīves laiku (globālie un lokālie dati). Ir dažādi datu apraksta varianti: tiešs apraksts (katra objekta tips ir tieši norādīts) pēc noklusēšanas (tipu nosaka objekta vārds)

31 Datu apraksts nodrošina: optimizāciju, efektīvi izvietojot datus atmiņā atmiņas vadības optimizāciju, izmantojot informāciju par objektu dzīves laiku (piemēram, ja vairāki objekti aprakstīti vienā vietā apakšprogrammas sākumā, tad pēc apakšprogrammas izpildes var "izmest" no atmiņas visu datu bloku uzreiz) iespēju izvēlēties pareizu operācijas variantu, ja tā ir pārslogota tipu kontroli.

32 Tipu kontrole Statiskā tipu kontrole iespējama valodās, kurās visi dati ir aprakstīti (tieši vai pēc noklusēšanas). Dinamiskā tipu kontrole nepieciešama, ja datu apraksti netiek izmantoti un datu tipu nosaka to vērtības (kas var mainīties programmas izpildes laikā). dinamiskā tipu kontrole statiskā tipu kontrole

33 Rādītāja datu tips Rādītājs - baita adrese atmiņā. tipizēts rādītājs un netipizēts rādītājs Piemērs: Var p1: ^integer; p2: ^real; Var p: pointer;

34 Operācijas := ; 1) rādītājs 2) funkcija, kuras vērtība ir rādītājs 3) konstante NIL salīdzināšanas operācijas: =,, = Piemērs: const p: ^ real = NIL; begin... if p = NIL then NEW(p);... dispose(p); p := NIL;... end;

35 Piemēri Var p1,p2: ^integer; p3: ^real; pp: pointer; p1 := p2; p1 := p3; pp := p3; p1 := pp; Kļūda! i^ := 2; r^ := 2*pi; r^ := sqr(r^) + i^ - 17;

36 Netipizēts rādītājs Lai strādāt ar netipizēto rādītāju, izmanto šādas procedūras: GETMEM(P,SIZE) - atmiņas rezervēšana FREEMEM(P,SIZE) – atmiņas atbrīvošana P – netipizēts rādītājs, SIZE - izmērs baitos.