1 DATU STRUKTŪRAS 3. lekcija – Datu struktūras jēdziens. Datu struktūras un to klasifikācija. Rakstzīmju virknes jēdziens.

2 Datu struktūras (data structure) jēdziens Datu organizācijas un datu elementu sasaistes raksturs, iespējamo vērtību kopums un iespējamo operāciju kopums ir datu struktūra. Datu struktūra ir jebkuram informācijas objektam piemītoša īpašība. Datu struktūra ir jebkuras programmēšanas sistēmas vai vides neatņemama sastāvdaļa. Teorētiskās un praktiskās zināšanas par datu struktūrām ir nepieciešamas, izstrādājot: o informācijas sistēmas o datu bāzu pārvaldības sistēmas o mākslīgā intelekta sistēmas o lēmumu pieņemšanas un vadības sistēmas o ekspertu sistēmas o imitācijas un modelēšanas sistēmas o programmēšanas valodu kompilatorus o operētājsistēmas u.c.

3 DS klasifikācija (1) Vienkāršas datu struktūras ir tādas DS, kurām atbilstošās vērtības ir skalāra tipa dati, kas nav sadalāmas sīkākās sastāvdaļās jeb datu elementos. Vienkāršas datu struktūras ir predefinētajiem skalāro datu tipiem char, integer, real, boolean, kā arī lietotāja definētajiem skalāro datu tipiem atbilstošās vērtības: char – A, 7, * integer – 10, -5, 7890 boolean – true, false real – 1.23, 7.0, 1E-5

4 DS klasifikācija (2) Fundamentālas datu struktūras ir tādas DS, kurām atbilstošās vērtības ir elementu kopums, kas sadalāms sastāvdaļās jeb komponentos. Fundamentālās datu struktūras bieži izmanto, lai veidotu saliktas datu struktūras ar sarežģītāku uzbūvi. Fundamentālām DS atbilstošās vērtības ir predefinētie vai lietotāja definētie strukturētā tipa dati, piemēram, virknes – predefinētais datu tips string, masīvi – predefinētais datu tips array, ieraksti – predefinētais datu tips record. var A: array [ 1.. 3, 1.. 3] of integer; A [i, j] – masīva elements, piemēram, A [1, 2] => 5

5 DS klasifikācija (3) Lineārās datu struktūrās (masīvi, ieraksti, saraksti); Nelineārās datu struktūrās (koki, grafi, daudzkāršsaistīti saraksti). Svarīga DS īpašība ir DS elementu sasaiste un sakārtotība. Atkarībā no tā DS ir iedalāmas: Par operatīvām DS sauc tādas DS, kuras tiek izvietotas un apstrādātas datora pamatatmiņā. DS datora diskatmiņā sauc par failu (datņu) struktūrām. Failu struktūras elements ir faila ieraksts. Savstarpēji saistītu failu struktūrās glabātu sarakstu kopums veido datu bāzi. Izvēli starp operatīvām DS un failu struktūrām nosaka piekļuves un apstrādes efektivitātes, kā arī atmiņas apjoma apsvērumi.

6 DS klasifikācija (4) Atkarībā no tā, kā mainās datu struktūras uzbūve, operējot ar šīm DS, tās ir iedalāmas: Statiskās DS (masīvi, ieraksti, tabulas) Pusstatiskās DS (steki, rindas) Dinamiskās DS (saistīti saraksti, koki, grafi) Atkarībā no tā, vai datu struktūras elements satur kāda cita DS elementa adresi (norādi uz nākamo vai iepriekšējo elementu), DS ir iedalāmas: Saistītās DSNesaistītās DS

7 DS klasifikācija (5) Atkarībā no tā, vai elementu izvietojums datu struktūrā ir patvaļīgs un nav determinēts vai arī datu struktūrā elementi izvietoti pēc kādas noteiktas pazīmes, DS ir iedalāmas: 1) sakārtotās (ordered) datu struktūrās; 2) nesakārtotās (nonordered) datu struktūrās.

8 Biežāk lietotās datu struktūras (1) kopa (angl. set) sasaiste (relationship ) Datu struktūru, kurā starp elementiem nav nekādas citas sasaistes kā vienīgi tās, ka visi elementi pieder pie noteikta datu kopuma, sauc par kopu. Kopā starp elementiem nav sasaistes. Kopā nav elementa, ko var saukt par pirmo, pēdējo vai tekošo. Kopas piemēri: 1) studenti grupā, kuri mācās angļu valodu; 2) grāmatas par informācijas tehnoloģiju utml.

9 Biežāk lietotās datu struktūras (2) Datu struktūru, kurā elementu sasaistes raksturs ir viens ar vienu (one-to- one), sauc par lineāru datu struktūru. Lineārā datu struktūrā katram elementam ir noteikts kārtas numurs, tajā ir elements, ko sauc par pirmo, un elements, kas ir pēdējais. Visiem elementiem, izņemot pirmo un pēdējo, ir viens vienīgs priekštecis (predecessor) un viens vienīgs pēctecis (successor). Pirmajam elementam nav priekšteča, bet pēdējam elementam nav pēcteča. Lineārās datu struktūras lieto visbiežāk. Lineārās datu struktūras ir masīvi, ieraksti, faili un saraksti. Tās arī izmanto kā pamatelementus, veidojot datu struktūras ar sarežģītu uzbūvi.

10 Biežāk lietotās datu struktūras (3) Datu struktūru, kurā elementu sasaistes raksturs ir viens ar vairākiem (one-to- many), sauc par koku (tree) jeb hierarhisku datu struktūru. Hierarhisks nozīmē to, ka datu struktūras elementi izvietoti vairākos līmeņos. Kokā ir unikāls elements, ko sauc par saknes virsotni. Katram elementam ir viens, vairāki vai neviens pēctecis, ko sauc par bērnu (child) un viens vienīgs priekštecis, ko sauc par vecāku (parient). Saknes virsotnei nav priekšteča, bet var būt pēcteči. Koka virsotnes, kurām nav pēcteču, sauc par lapām (leaf). Visbiežāk lieto bināros kokus, kuros katrai virsotnei nav vairāk kā 2 pēcteči. Katrs pēctecis ir kreisais bērns vai labais bērns. Virsotnes (node) kokā savienotas ar šķautnēm (edge). līmeņi koks (tree)

11 Biežāk lietotās datu struktūras (4) Datu struktūru, kurā elementu sasaistes raksturs ir vairāki ar vairākiem (many-to-many), sauc par grafu (graph) jeb tīklveida datu struktūru. Grafā nav elementa, ko sauc par pirmo vai par pēdējo. Katram elementam ir vairāki pēcteči un vairāki priekšteči. Elementi savienoti ar lokiem. Darbā ar grafiem svarīga operācija ir īsākā ceļa meklēšana starp virsotnēm. Grafus plaši lieto, uzdodot dažādus procesus, to stāvokļus un norises, ar grafu palīdzību risina arī optimizācijas problēmas. Kokus un grafus sauc arī par nelineārām datu struktūrām. grafs (graph)

12 Biežāk lietotās datu struktūras n -1 n... viens ar vienu līmeņi viens ar vairākiemvairāki ar vairākiem

13 Datu struktūras izstrādes procesa shēma DS elementu uzbūve DS elementu sasaiste Domēns Operācijas Specifikācija Projektēšana Ieviešana DS attēlojums atmiņā DS izstrāde (development): 1) specifikācija (specification); 2) projektēšana (design); 3) ieviešana (implementation).

14 Datu struktūras attēlojuma paņēmieni un modeļi (1) 1. paņēmiens: adresevārds 1000Aivars 1008Markus 1016Edgars 1024Dainis 1032Centis Ja zināma i-tā saraksta elementa adrese, tad i + 1 – saraksta elementa adrese ir aprēķināma šādi: adrese i+1 = adrese i + l (l = 8, i = 1, 2,..., n-1) Vektoriālā attēluma forma, izmantojot pozicionēšanu

15 Datu struktūras attēlojuma paņēmieni un modeļi (2) 2. paņēmiens: adresevārds 1000Aivars Centis 1024Dainis 1032Edgars Markus Saraksta elementa adreses aprēķins: l * (ord(pb) – ord ('A')) (l=8, ord(A)=65, pb – vārda pirmais burts) Vektoriālā attēluma forma, izmantojot hešēšanu jeb jaukšanu Hešfunkciju lietojums elementa vietas noteikšanai sarakstā Kolīzijas un to novēršana

16 Datu struktūras attēlojuma paņēmieni un modeļi (3) 3. paņēmiens: adresevārdspēcteča adrese – sākumadrese 1000Aivars Centis Dainis Edgars Markus --- saraksta beigas Saistītā attēlojuma forma ar elementu sasaisti Saistīšana nozīmē, ka elementi sarakstā sasaistīti ar rādītājiem un ka jālieto arī speciāli piekļuves rādītāji, izpildot saraksta apstrādes operācijas

17 Datu struktūras elementu identifikācija (1) Lineāru un nelineāru DS elementiem ir vienāda uzbūve. Elementu veido 2 lauki: 1) informatīvs lauks data, kurā sakopota plaša un daudzveidīga informācija par DS elementu. Visai bieži šo lauku definē kā ierakstu, vienkāršākajā gadījumā – kā rakstzīmju virkni; 2) atslēgas lauks key, kas satur unikālu informāciju jeb kodu, kas viennozīmīgi identificē DS elementu. Parasti DS nav vairāki elementi ar vienu un to pašu atslēgu. Atslēgas laukam var uzdot jebkuru skalāru ordināro tipu vai virknes tipu string.

18 Datu struktūras elementu identifikācija (2) 1) vektoriālā formā attēlots saraksts: ListInstance L: List current n el [1] el [2]... el [current]... el [n] el [MaxSize]... - tekošā elementa kārtas numurs - elementu skaits saraksts brīvā atmiņa

19 Vektoriālā formā attēlotā saraksta elementa uzbūve DS elementa uzbūve: el [i], i = 1, 2,..., n datakey datu tips DataType, jebkurš datu tips, skalārs vai strukturēts datu tips KeyType, jebkurš skalārs ordināls datu tips vai virknes tips string ieraksta tips StdElement

20 Vektoriālā formā aprakstītā saraksta elementa apraksts KeyType – jebkurš skalārs ordināls tips vai virknes tips string, DataType – jebkurš tips, strukturēts vai skalārs. const MaxSize = 100; {maksimālais elementu skaits} typeDataType = string; {jebkurš datu tips} KeyType = integer; {skalārs ordināls datu tips vai string} StdElement = record {saraksta elementa tips} data: DataType; {informatīvs datu lauks} key: KeyType {unikālas atslēgas lauks} end; Saraksts el ir viendimensijas masīvs, kas ir definējams šādi: el: array [1.. MaxSize] of StdElement;

21 Datu struktūras elementu identifikācija 2) saistītā formā attēlots saraksts: el next tail current... nil head el next el next pēd. elem. 2. elem. 1. elem. Node data key tips DataType tips KeyType tips StdElement - ieraksta tips el

22 Saistītā formā attēlotas datu struktūras elementa apraksts const MaxSize = 100; {maksimālais elementu skaits} type DataType = string; {jebkurš datu tips} KeyType = integer; {skalārs ordināls datu tips vai string} StdElement = record data: DataType; {informatīvs datu lauks} key: KeyType {unikālas atslēgas lauks} end; NodePointer = ^ Node; {rādītāja datu tips} Node = record {saraksta elementa tips} el: StdElement; next: NodePointer {rādītājalauks} end;

23 Datu struktūras projektējuma vērtēšana (1) Projektējot DS, jārisina šādas problēmas: 1) jānovērtē datu struktūras apstrādes operāciju izpildes laiks; 2) jāizvēlas, vai tiks veidota statiska vai dinamiska datu struktūra; 3) jānoskaidro, vai iespējams, ka datu struktūras elementiem varētu būt mainīgs garums; 4) jānovērtē algoritmu izpildes efektivitāte (sarežģītības pakāpe); 5) jāizvēlas, vai datu struktūra, strādājot ar to, tiks izvietota pamatatmiņā vai diskatmiņā. Piemēram: izveidots saraksts ar N elementiem, katrs saraksta elements ir kāds vārds, piemēram, Aivars. Sarakstā jāsameklē vārds Edgars un, ja meklēšana beigusies sekmīgi, jānosaka tā pozīcijas numurs.

24 Datu struktūras projektējuma vērtēšana (2) 1. paņēmiens – saraksts izvietots pamatatmiņā: const N = 500; {elementu skaits sarakstā} type Name = string [8]; {saraksta elementu tips} Arr = array [1.. N] of Name; {masīva tips} var List: Arr; {saraksts} i: 0.. N; Test: Name; i:= 0; repeat {meklēšana sarakstā} i:= i+1; Test:= List [i] until (Test = Edgars) or (i = N);

25 Datu struktūras projektējuma vērtēšana (3) 2. paņēmiens – saraksts izvietots diskatmiņā: const N = 500; {elementu skaits sarakstā} type Name = string [8]; {saraksta elementu tips} FL = file of Name; {faila tips} var List: FL; {saraksts} i: 0.. N; Test: Name; i:= 0; repeat {meklēšanā sarakstā} i:= i+1; read (List, Test) until (Test = Edgars) or (i = N);

26 Datu struktūras projektējuma vērtēšana (3a) Priekšrocības: 1. paņēmiens – meklēšanas operācija ir ātrdarbīga; 2. paņēmiens – praktiski nav ierobežojumu DS apjomam (elementu skaitam); Trūkumi: 1. paņēmiens – DS apjoms ir ierobežots; 2. paņēmiens – meklēšanas operācija ir lēndarbīga.

27 Metrika, efektivitāte, veiktspēja (efficiency, performance) (1) Bieži izpildāmas operācijas: 1) meklēšanas operācija – reducējama uz salīdzināšanu. Operācijas izpildes ātrumu nosaka salīdzinājumu skaits; 2) elementa dzēšana sarakstā – reducējama uz elementu pārvietošanu par 1 pozīciju virzienā uz dzēšamo elementu. Lai novērtētu algoritma efektivitāti izmanto: 1) salīdzināšanas vai pārsūtīšanas operāciju skaitu; 2) kopējo operatoru skaitu, alternatīvo zarojumu daudzumu, cikla izvietojuma dziļumu; 3) pierakstu matemātiskās kārtas veidā, piemēram, O(n).

28 Metrika, efektivitāte, veiktspēja (2) Salīdzinājumu skaits meklēšanas procesā: E c = n + 1, n – elementu skaits. Meklēšanas laiks: t = C 1 E c + C o = C 1 n+1 + C o = C 1 n + C o – lineāra funkcija 2 Izteiksmes lieluma kārtu nosaka tikai vislielākais operands, mazākie operandi vērtējumu būtiski neietekmē. 2 n t O(n)

29 Metrika, efektivitāte, veiktspēja (3) Dažu izteiksmju kārtas: n (n - 1) O(n 2 ) 2 15 log 2 n + 3n + 7O(n) 2n log 2 n + 0,1n 2 + 5O(n 2 ) 6 log 2 n + 3n + 7 O(1) 2n – 5 n t O(n 2 ) n t O(log 2 n) n t O(1)

30 Algoritmu veiktspējas vērtējums Kārtan = 8n = 128n = 1024n = 10 6 O (n) = O (n 2 ) O ( n) O (log 2 n) O (n log 2 n)

31 Algoritmu veiktspējas salīdzinājums (1) Meklēšanas laiks t 2 > t 1 - ja elementu skaits neliels, t 3 < t 4 - ja sarakstā daudz elementu. n t O (log 2 n) O (n) n n1n1 n2n2 t4t4 t3t3 t2t2 t1t1

32 Algoritmu veiktspējas salīdzinājums (2) Tātad, ja sarakstā elementu skaits ir n 1, un tas neliels, pilnīgi iespējams, ka lineārās meklēšanas algoritms būs efektīvāks nekā binārās meklēšanas algoritms (t 1 < t 2 ). Jā sarakstā elementu skaits ir n 3, kas ir pietiekami liels, tad binārās meklēšanas algoritma lietojums būs efektivitāks nekā lineārās meklēšanas algoritma gadījumā (t 3 < t 4 ). Ir iespējams tāds saraksta elementu skaits n 2, kura gadījumā abu algoritmu izpildes efektivitāte būs līdzvērtīga.

33 Algoritmu veiktspējas salīdzinājums (3) Piemēram, ja n=1024, tad, lai vajadzīgo elementu sameklētu šai sarakstā, lineārās meklēšanas algoritma lietojuma gadījumā vidēji būtu nepieciešams pārbaudīt pusi no saraksta, t.i., vidēji būtu jāsalīdzina 512 elementi, bet binārās meklēšanas algoritma lietojuma gadījumā vajadzīgais elements vissliktākājā izkārtojuma gadījumā būtu sameklējams pēc 10 salīdzināšanas reizēm (log = 10). Jāatzīmē tomēr, ka binārās meklēšanas algoritms ir izmantojams tikai tad, ja sarakstā elementi ir sašķiroti.

34 Rakstzīmju attēlošana ar mainīgu bitu skaitu (1) Ja bitu skaits rakstzīmes kodā n = 8, iespējams kodēt 2 8 = 256 rakstzīmes. Pieņemsim, ka ir teksts, kurā ir tikai 8 rakstzīmes. Tā kā 8 = 2 3, tad šo tekstu ir iespējams kodēt arī tā, ka katrai rakstzīmei paredz tikai 3 bitu kombināciju. Ir zināms šo 8 rakstzīmju lietojuma biežums (%): abcdefgh Uzdevums: atrast tādu attēlojuma formu, lai šis teksts aizņemtu vismazāk vietas atmiņā. Rakstzīmju lietojuma biežums kādā tekstā

35 Rakstzīmju attēlošana ar mainīgu bitu skaitu (2) Sāk ar to, ka izveido mežu, ko veido koki ar vienu vienīgu saknes virsotni, kas satur rakstzīmes lietojuma biežumu: Virsotnes sakārtotas lietojuma biežuma dilšanas secībā. Divas virsotnes, kurām ir viszemākais lietojuma biežums, apvieno binārajā kokā ar jaunu saknes virsotni un 2 zarojuma virsotnēm: Kokus atkal sakārto virsotņu vērtību dilšanas secībā:

36 Rakstzīmju attēlošana ar mainīgu bitu skaitu (3) Procesu turpina, vēlreiz apvienojot 2 virsotnes ar viszemākajiem lietojuma biežumiem, pēc tam kokus atkal sakārto saknes virsotņu vērtību dilšanas secībā: Vēlreiz atkārtojot procesu, iegūst šādu bināro koku:

37 Rakstzīmju attēlošana ar mainīgu bitu skaitu (4) Līdzīgā veidā procesu atkārtojot vēl 4 reizes, iegūst rezultējošo bināro koku: a b c d e f g h Rakstzīmju lietojuma biežuma vērtības atrodas binārā koka lapu virsotnēs. Binārajā kokā katrai kreisajai šķautnei piešķir vērtību 0, labajai – 1.

38 Rakstzīmju attēlošana ar mainīgu bitu skaitu (5) Katras rakstzīmes attēlojuma kods ir bitu virkne ceļā no saknes virsotnes uz lapas virsotni. Ir 8 šādi ceļi: rakstzīmekodslietojuma biežums a 040 b c d e f g H

39 Rakstzīmju attēlošana ar mainīgu bitu skaitu (6) Iegūto kodu sauc par Hafmena (Huffman) kodu. Tam piemīt tāda īpašība, ka nevienas rakstzīmes kods nav vienāds ar prefiksu kādas citas rakstzīmes kodā. Tāpēc no Hafmena koda var iegūt oriģinālo 8 bitu kodu. Lietojot Hafmena kodu teksta kodēšanai, būtu nepieciešami n (40*1 + 20*3 + 10*3 + 8*4 +8*4 + 5*4 + 5*5 +4*5)=2,59n biti 100 Atmiņas ietaupījums: 8n / 2,59n 3 – Hafmena kodu salīdzinot ar 8 bitu kodu 3n / 2,59n 1,15 – Hafmena kodu salīdzinot ar 3 bitu kodu

40 Rakstzīmju virknes jēdziens (1) 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); 1 maksimālais garums tekošais garums maksimālais garums

41 Rakstzīmju virknes jēdziens (2) Attēlā parādīts mainīgā garuma virknes attēlojums datora atmiņā: tek. gar tg... baiti max gar. neizmantoti baiti teksts Tekošais garums aizņem 0. baitu, tā maksimālā vērtība: = FF 16 = Tekošā garuma baits apstrādei tieši nav pieejams, bet to apstrādei var padarīt pieejamu, uzklājot tam kādu byte tipa mainīgo: var S: string [80]; L: byte absolute S; S:=ABC; writeln(L, S); {izvadīs 3 un ABC}

42 Rakstzīmju virknes jēdziens (3) 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.

43 Rakstzīmju virknes tipa specifikācija (1) 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 MaxLength definē kā konstanti, piemēram: const MaxLength = 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.

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

45 Rakstzīmju virknes attēlojuma modeļi (1) 1. paņēmiens – modelī paredzēts speciāls lauks tekošā garuma attēlošanai, virknes attēlošanai izmanto vektoriālā formā attēlotu modeli: strlen data [1] data [2]... data [strlen]... data [MaxLength] tekošais garums virknes teksts brīvās pozīcijas StringInstance S: String

46 Rakstzīmju virknes attēlojuma modeļi (2) Pēc 1. paņēmiena attēlotās rakstzīmju virknes attēlojuma modeļa apraksts: const MaxLength = 500; {maksimālais garums - uzdod lietotājs} type StringLen = 0.. MaxLength; {tekošā garuma tips} StringPos = 1.. MaxLength; {elementa pozīcijas tips} String = ^ StringInstance; {virknes rādītāja tips} StringInstance = record {virknes modeļa tips} strlen: StringLen; data: array [StringPos] of char end;

47 Rakstzīmju virknes attēlojuma modeļi (3) 2. paņēmiens – lieto vektoriālo attēlojuma formu, bet nav paredzēts lauks tekošā garuma attēlošanai. Aiz virknes pēdējās rakstzīmes ieraksta virknes beigu pazīmi. Parasti izmanto vadības rakstzīmi NULL, kuras kods ir Var paredzēt arī tādu paņēmienu, ka viss pārpalikušais vektors tiek aizpildīts ar šo vadības rakstzīmi. To sauc arī par robežmarķiera metodi.

48 Rakstzīmju virknes attēlojuma modeļi (3) 2. paņēmiena galvenais trūkums: pirms operāciju izpildes jāsameklē virknes beigas, tā ir O(n) kārtas meklēšanas operācija. const MaxLength = 500; type StringLen = 0.. MaxLength; StringPos = 1.. MaxLength; String = ^ StringInstance; StringInstance = array [ 1.. MaxLength +1] of char; data [1] data [2]... data [strlen]... data [MaxLength] teksts brīvās pozīcijas StringInstance S: String NULL virknes beigu pazīme (kontrolmarķieris)

49 Rakstzīmju virknes attēlojuma modeļi (3) 3. paņēmiens: virknes attēlošanai izmanto saistītā formā attēlotu modeli. Rakstzīmju virknes teksts tiek sadalīts fragmentos (chunk) ar vienādu garumu, izņemot pēdējo posmu, kas var būt arī īsāks. head datanext tail strlen... nil S: String StringInstance Chunk

50 Saistītā formā attēlotās rakstzīmju virknes apraksts const MaxLength = 500; {virknes maksimālais garums} ChunkSize = 10; {fragmenta garums} type ChunkPos = 1.. ChunkSize; StringLen = 0.. MaxLength; ChPointer = ^ Chunk; {elementu rādītāja tips} Chunk = record {virknes elementa fragments} data: array [ChunkPos] of char; next: ChPointer end; String = ^ StringInstance; StringInstance = record {vadības struktūra} head: ChPointer; {virknes sākuma rādītājs} tail: ChPointer; {virknes beigu rādītājs} strlen: StringLen {virknes tekošais garums} end;