1 DATU STRUKTŪRAS Praktiskās nodarbības doc. Natālija Prokofjeva

2 DATU STRUKTŪRAS 2. nodarbība –Rādītāji. Rakstzīmju virkne.

3 Datu tipa (data type) jēdziens Datu tips ir: 1) iespējamo vērtību kopums; 2) operāciju kopums šo vērtību apstrādei. 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. Šiem datu tipiem atbilstošie mainīgie, konstantes un funkcijas pieņem vērtības, ar kurām datu apstrādes procesā tiek izpildītas dažādas darbības: datu ievade, aprēķini vai kāda cita apstrādes operācija, datu izvade un tml.

4 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

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

6 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

7 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)

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

9 Rakstzīmju virknes jēdziens Programmēšanas valodā Pascal rakstzīmju virkni iespējams definēt divējādi: 1) kā mainīga garuma rakstzīmju virkni, virknes aprakstā izmantojot predefinēto datu tipu string: type Text1 = string; Text2 = string [80]; var S: Text1; Q: Text2 ; S:= RTU; Q:=RIGA; S:= ; read(Q); writeln(Q); Strādājot ar mainīga garuma virknēm, lieto divu garumu jēdzienus: 1 maksimālais garums 255, noklusējot 255; 0 tekošais garums maksimālais garums.

10 Rakstzīmju virknes jēdziens 2) kā fiksēta garuma rakstzīmju virkni, virknes aprakstā izmantojot predefinēto datu tipu array: type Text1 = array [1..255] of char; Text2 = array [1..80] of char; var S:= Text1; Q:= Text2; S:= RTU; Q:= RIGA; writeln(S, Q); {izvadīs 335 rakstzīmes} Lieto tikai maksimālā garuma jēdzienu. Tas var būt arī > 255.

11 Rakstzīmju virknes tipa specifikācija Elementi: rakstzīmju virknes elementi ir alfabēta ASCII rakstzīmes. Katra rakstzīme atmiņā aizņem 1 baitu. Struktūra: rakstzīmju virknes elementiem ir lineāra sasaiste. Katram elementam ir unikāla pozīcija rakstzīmju virknē. Pirmais elements atrodas 1. pozīcijā. Domēns: visas iespējamās rakstzīmju kombinācijas ar garumu 0, 1,..., MaxLength. Maksimālo garumu MaxLenght definē kā konstanti, piemēram: const MaxLenght = 500; Datu tipi: String – rakstzīmju virknes rādītāja tips, StringPos = 1.. MaxLength – rakstzīmju virknes pozīcijas tips, StringLen = 0.. MaxLength – rakstzīmju virknes tekošā garuma tips.

12 Rakstzīmju virknes modelis un tā apraksts strlen data [1] data [2]... data [strlen]... data [MaxLength] tekošais garums virknes teksts brīvās pozīcijas StringInstance S: String const MaxLength = 500; type StringLen = 0..MaxLength; StringPos = 1.. MaxLength; String = ^ StringInstance; StringInstance = record strlen: StringLen; data: array [StringPos] of char end;

13 Rakstzīmju virknes apstrādes operācijas Apkalpošanas operācijas PamatoperācijasPapildoperācijas Create Terminate Lenght Empty Full Append Concatenate Substring Delete Insert Match Find ReadString WriteString MakeEmpty Remove Equal Reverse Polindrome u.c.

14 Apkalpošanas operācijas procedure Create (var S: String; var created: boolean); {Izveido jaunu tukšu rakstzīmju virkni S^} begin new(S); S^.strlen := 0; created := true end; procedure Terminate (var S: String; var created: boolean); {Likvidē rakstzīmju virkni S^} begin if created then begin S^.strlen := 0; created := false end end;

15 Apkalpošanas operācijas function Length (S: String): StringLen; {Nosaka rakstzīmju virknes S^ tekošo garumu} begin Length := S^.strlen end; function Empty (S: String): boolean; {Pārbauda, vai rakstzīmju virkne S^ ir tukša} begin Empty := S^.strlen = 0 end;

16 Apkalpošanas operācijas function Full (S: String): boolean; {Pārbauda, vai rakstzīmju virkne S^ ir pilna} begin Full := S^.strlen = MaxLength end;

17 Pamatoperācijas procedure Append (var S: String; ch: char); {Rakstzīmju virknei S^ galā pievieno rakstzīmi ch} begin if not Full(S) then with S^ do begin data[strlen+1] := ch; strlen := strlen+1 end end;

18 Pamatoperācijas procedure Concatenate (var S1: String; var S2: String); {Rakstzīmju virknei S1^ galā pievieno rakstzīmju virkni S2^} var i: StringPos; k: StringLen; begin if not Empty(S2) then begin {nosaka pievienojamo rakstzīmju skaitu} if Length(S1)+Lenhth(S2) <= MaxLength then k := Length(S2) else k := MaxLength- Length(S1); with S1^ do begin {savirknēšana} for i := 1 to k do data[strlen+i] := S2^.data[i]; strlen := strlen+k end end;

19 Pamatoperācijas procedure Substring (S1: String; var S2: String; pos: StringPos: len: StringLen); {No rakstzīmju virknes S1^, sākot ar pozīciju pos, izdala apakšvirkni S2^, kuras garums ir len} var i: StringPos; begin if ( len > 0) and (Length(S1) >= pos+len-1) then with S2^ do begin {izveido apakšvirkni S2} for i := 1 to len do data[i] := S1^.data[pos+i-1]; strlen := len end end;

20 Pamatoperācijas procedure Delete (var S: String; pos: StringPos; len: StringLen); {Rakstzīmju virknē S^, sākot ar pozīciju pos, dzēš apakšvirkni, kuras garums ir len} var i: StringLen; begin if ( len > 0) and (Length(S) >= pos+len-1) then with S^ do begin {dzēš apakšvirkni} for i := pos+len to strlen do data[i-len] := data[i]; strlen := strlen-len end end;

21 Pamatoperācijas procedure Insert (var S1: String; S2: String; pos: StringPos); {Rakstzīmju virknē S1^, sākot ar pozīciju pos, iestarpina rakstzīmju virkni S2^} var len1, len2, len: StringLen; i: StringPos; begin len1 := Length(S1); len2 := Lenhth(S2); {fiksē virkņu tekošos garumus} len := len1+len2; if (not Empty(S2)) and ( len <= MaxLength) and (pos <=len1+1) then with S1^ do begin {atbrīvo vietu iestarpināmajai virknei S2^} for i := len1 downto pos do data[i+len2] := data [i]; {apakšvirkni S2^ izvieto virknē S1^} for i := 1 to len2 do data[pos+i-1] := S2^.data[i]; strlen := strlen+len2 end end;

22 Pamatoperācijas function Match (S1, S2: String; pos: StringPos): boolean; {Pārbauda, sākot ar pozīciju pos, vai rakstzīmju virkne S1^ satur apakšvirkni S2^} var i, last: StringPos; continue: boolean; begin i := 1; last := Length(S2); {uzdod pārbaudes diapazonu} continue := true; Match := false; {sākumvērtības} if (not Empty(S2)) and (Length(S1) >= Length(S2)+pos-1) then while continue and (S2^.data[i] = S1^.data[pos]) do {sakritības pārbaude} if i = last then begin { pārbaude beidzas sekmīgi} continue :=false; Match :=true end else begin {pārbaudi turpina} i := i+1; pos := pos+1 end end;

23 Pamatoperācijas function Find (S1, S2: String; pos: StringPos): StringLen; {Lineārās meklēšanas algoritms. Rakstzīmju virknē S1^, sākot ar pozīciju pos, meklē apakšvirkni S2^. Meklēšanas rezultāts ir tā pozīcija, sākot ar kuru apakšvirkne sameklēta, vai arī 0, ja meklēšana beigusies nesekmīgi} var kbegin, kend: StringPos; found: boolean; begin kbegin := pos; kend := Length(S1)-Length(S2)+1; {meklēšanas diapazons} found := false; {sākumvērtība} while (not found) and (kbegin <= kend) do {apakšvirknes meklēšana} if Match(S1, S2, kbegin) then found := true {meklēšana pabeigta sekmīgi} else kbegin := kbegin+1; {uzdod nākamo meklēšanas pozīciju} if found then Find := kbegin else Find :=0 {meklēšanas rezultāts} end;

24 Pamatoperācijas procedure ReadString (var S: String); {Ar tastatūru ievada rakstzīmju virkni S^} var ch := char; begin writeln(Ievadiet rakstzīmju virkni vienā ievadrindā); MakeEmpty(S); {virkne S^ kļūst tukša} while not eoln do {virknes ievade, kamēr vien nav nospiests taustiņš Enter} if Length(S) < MaxLength then begin read(ch); {ievada kārtējo rakstzīmi} Append(S, ch) {ievadīto rakstzīmi pievieno virknei S^ galā} end end;

25 Pamatoperācijas procedure WriteString (S: String); {Rakstzīmju virkni S^ izvada displeja ekrānā} var i: StringPos; begin if not Empty(S) then with S^ do begin for i := 1 to strlen do write(data[i]); {virknes S^ teksta izvade} writeln; readln {gaida, kamēr tiek nospiests taustiņš Enter} end end;

26 Papildoperācijas procedure MakeEmpty (var S: String}; {Rakstzīmju virkni S^ padara par tukšu virkni} begin S^.strlen := 0 end; procedure Remove (var S: String; pos: StringPos; var ch: char); {No rakstzīmju virknes S^ pozīcijas pos aizvāc rakstzīmi ch} var i: StringPos; begin if not Empty(S) then with S^ do begin ch := data[pos]; {dzēšamo rakstzīmi piešķir mainīgajam ch} for i := pos+1 to strlen do {dzēš virknes rakstzīmi pozīcijā pos} data[i-1] := data[i]; strlen := strlen-1 end end;

27 Papildoperācijas procedure Remove (var S: String; pos: StringPos; var ch: char); {No rakstzīmju virknes S^ pozīcijas pos aizvāc rakstzīmi ch} var i: StringPos; begin if not Empty(S) then with S^ do begin ch := data[pos]; {dzēšamo rakstzīmi piešķir mainīgajam ch} for i := pos+1 to strlen do {dzēš virknes rakstzīmi pozīcijā pos} data[i-1] := data[i]; strlen := strlen-1 end end;

28 Papildoperācijas procedure Reverse (var S: String); {Rakstzīmju virkni S^ apgriež otrādi (reversē)} var i: StringPos; ch: char; begin if Length(S) > 1 then with S^ do for i := 1 to ( strlen div 2 ) do {no 1.pozīcijas līdz viduspunktam} begin {izpilda virknes reversēšanu} ch := data[i]; data[i] := data[strlen-i+1]; data[strlen-i+1] := ch end end;

29 Papildoperācijas function Equal (S1, S2: String): boolean; {Pārbauda, vai rakstzīmju virknes S1^ un S2^ ir identiskas} var len1, len2: StringLen; begin len1 := Length(S1); len2 := Length(S2); {fiksē virkņu tekošos garumus} Equal := false; {sākumvērtība} if ( len1 = 0 ) and ( len2 = 0) then Equal := true {tukšas virknes ir identiskas} else if len1 = len2 then Equal := Match(S1, S2, 1) {sakritības pārbaude} end;

30 Papildoperācijas function Polindrome (S: String): boolean; {Pārbauda, vai rakstzīmju virkne S^ ir vienādi lasāma no sākuma un no beigām} var P: String; begin Polindrome := true; {sākumvērtība} if Length(S) > 1 then {ja virknē vairāk kā 1 rakstzīme} begin new(P); {izveido dinamisku rakstzīmju virknes eksemplāru P^} P^.data := S^.data; {virkni S^ dublē virknē P^} P^.strlen := S^.strlen; Reverse(P); {rakstzīmju virkni P^ reversē} Polindrome := Equal(S, P) {pārbauda, vai abas virknes ir identiskas} end end;