1 DATU STRUKTŪRAS 4. lekcija – Masīva jēdziens. Matricas jēdziens un interpretācija. Elementa meklēšana vektorā. Deskriptors un tā lietojums. Vektora adresēšanas. - презентация

1 1 DATU STRUKTŪRAS 4. lekcija – Masīva jēdziens. Matricas jēdziens un interpretācija. Elementa meklēšana vektorā. Deskriptors un tā lietojums. Vektora adresēšanas funkcijas noteikšana. Divdimensiju masīva adresēšanas funkcija. Vairākdimensiju masīvi un to adresēšanas funkcija.

2 2 Masīva jēdziens (1) Masīvs (array) – vienkāršākais strukturētais datu tips. Vēsturiski – pirmā programmēšanas valodā realizēta datu struktūra. Masīvi – visbiežāk lietotās fundamentālās datu struktūras. Masīvs – regulāra datu struktūra. Masīva elementi izvietoti dimensiju virzienā, katram elementam masīvā ir noteikts pozīcijas numurs, piemēram, A [2, 1, 3].

3 3 Masīva jēdziens (1) Masīvs ir homogēna (viendabīga) datu struktūra. Visiem elementiem ir vienāda uzbūve un viens un tas pats tips, ko sauc par bāzes tipu. Masīvs – datu struktūra, kuras elementu pieejai izmanto brīvpiekļuves metodi (random access method). Apstrādei pieejams jebkurš elements jebkurā secībā, izmantojot indeksizteiksmes, piemēram, A [i, j, k] Masīvs - lineāra datu struktūra. Elementu sasaistes raksturs: viens –ar- vienu.

4 4 Masīva jēdziens (2) Masīva tipa apraksts valodā Pascal: type T = array [I] of B; var A: T; I – indeksa tips, par to var būt tikai skalārs ordināls tips. Parasti to definē kā diapazona tipu ar indeksa augšējo un apakšējo robežvērtību: lo.. hi B – bāzes tips, par to var būt jebkurš datu tips, skalārs vai strukturēts datu tips, predefinēts vai lietotāja definēts datu tips.

5 5 Masīva jēdziens (2) Viendimensijas masīva X apraksta piemērs: var X: array [ ] of real; I B X [1] – masīva X pirmais elements, X [100] – masīva X pēdējais elements, X [i], i = 2, 3,...,99 - masīva X tekošais elements, X [i+1] – tā pēctecis, X [i-1] – tā priekštecis.

6 6 Masīva jēdziens Ir 3 pamatoperācijas masīva elementu apstrādei, pie kam 3. operācija ir arī realizējama, izmantojot pirmās divas. type T = array [I] of B; var X, Y: T; C: B; 1) C:= X[i]; kur i – tipam I atbilstoša indeksizteiksme. {izguves operācija Retrieve} 2) X[i]:= e; kur e – bāzes tipam B atbilstoša izteiksme. {labošanas operācija Update}

7 7 Masīva jēdziens 3) Y:= X; ekvivalents ar for i:= 1 to n do Y [i]:= X [i]; {kopēšanas operācija Copy} Viendimensijas masīvu sauc par vektoru. Divdimensijas masīvu sauc par matricu. Masīva dimensiju skaitu praktiski ierobežo datorresursi, teorētiski šādu ierobežojumu nav.

8 8 Piemēri 1) type Row = array [ ] of real; Card = array [1.. 80] of char; Vector = array [ ] of integer; var A: Row; X, Y: Card; Q: Vector;

9 9 Piemēri 2) type Ind1 = ; Ind2 = ; Matrix = array [Ind1, Ind2] of real; var M: Matrix; 3) type Ind1 = ; Ind2 = ; Matrix = array [Ind1] of array [Ind2] of real; I B var M: Matrix;

10 10 Matricas jēdziens un interpretācija (1) Valodā Pascal iespējami 2 matricas interpretācijas veidi: 1) matrica ir divdimensiju masīvs, kura elementi izvietoti rindās un kolonnās, šādi matrica tiek interpretēta matemātikā. Programmēšanas valodās matricas interpretācija ir plašāka. const lo1 = 1; hi1 = 3; lo2 = 1; hi2 = 4; type Ind1 = lo1.. hi1; Ind2 = lo2.. hi2; B = real; Matrix = array [Ind1, Ind2] of B; var A: Matrix;

11 11 Matricas jēdziens un interpretācija (2) j A [1,1] A[1,2] A[1,3] A[1,4] i A [2,1] A[2,2] A[2,3] A[2,4] A [3,1] A[3,2] A[3,3] A[3,4] Masīva elements ir mainīgais ar indeksiem: A [i,j],i = 1, 2, 3; j = 1, 2, 3, 4. (vispārējā gadījumā i = lo1, lo1+1,..., hi1, j = lo2, lo2+1,..., hi2). Katrai dimensijai jāuzdod sava indeksizteiksme. Mainīgais A – pārstāv visus masīva elementus, piemēram: writeln (A);

12 12 Matricas jēdziens un interpretācija (3) 2) matrica ir vektors, kura elementi savukārt ir vektori (array of array). Šādi masīvu var interpretēt, piemēram, valodā Pascal: const lo1 = 1; hi1 = 3; lo2 = 1; hi2 =4; type Ind1 = lo1.. hi1; Ind2 = lo2.. hi2; B = real; Matrix = array [Ind1] of array [Ind2] of B; var A: Matrix; j A [1][1] A[1][2] A[1][3] A[1][4] i A [2][1] A[2][2] A[2][3] A[2][4] A [3][1] A[3][2] A[3][3] A[3][4]

13 13 Elementa meklēšana vektorā (1) Bieži lietota operācija darbā ar datu struktūrām. Ir 3 meklēšanas algoritmi (metodes): 1) lineārā jeb secīgā meklēšana: const N = 500; type I = 1.. N; I1 = 0.. N; B = integer; T = array [I] of B; var A: T; k: I1; X: B;... {meklēšanas atslēga}

14 14 Elementa meklēšana vektorā (2) repeat {elementa meklēšana} k:= k + 1 until (A[k] = X) or (k = N); if A[k] <> X then writeln (Nesekmīga meklēšana) else writeln (k, X); Lineārās meklēšanas operācijas izpildes efektivitāte: 0(n)

15 15 Elementa meklēšana vektorā (3) 2) lineārā meklēšana, izmantojot robežmarķiera metodi: const N = 500; type I = 1.. N + 1; I1 = 0.. N + 1; B = integer; T = array [I] of B; var A: T; k: I1; X: B;... k:= 0; A [N + 1]:= X; {robežmarķieris} repeat {elementa meklēšana} k:= k + 1 until A [k] = X; if k > N then writeln (Nesekmīga meklēšana) else writeln (k, X);

16 16 Elementa meklēšana vektorā (4) 3) binārā meklēšana (dihotomijas metode): const N = 500; type I = 1.. N; B = real; T = array [I] of B; var A: T; i, j,k: I; X : B;... i:= 1; j:= N; {meklēšanas diapazons} repeat {elementa meklēšana} k = (i + j) div 2; {viduspunkts} if A [k] < X then i:= k + 1 {atmet augšējo apakšs.} else j:= k -1 {atmet apakšējo apakšs.} until (A[k] = X) or (i > j); if A[k] = X then writeln (k, X) else writeln (Nesekmīga meklēšana);

17 17 Elementa meklēšana vektorā (5) Lineārām meklēšanas operācijas efektivitāte: O(log 2 N) k N 1 k - 1 k + 1 i = 1 if A [k] < X then i:= k +1 k = (i + j) div 2; if A [k] > X then j := k -1 j = N atmet augš. apakšsar. atmet apakš. apakšsar.

18 18 Deskriptors un tā lietojums (1) Fiziskai datu struktūrai, kas ir masīvs, tiek piekārtots informatīvs ieraksts, ko sauc par deskriptoru un kurā sakopotas vispārīgas ziņas par attiecīgo masīvu. Deskriptoru parasti izveido kompilators, un tas paredzēts, lai masīvu apstrādes procesā indeksizteiksmju vērtības pārveidotu fiziskas datu struktūras lauka adresēs. Deskriptors ir ieraksts, kas sastāv no laukiem, kuru skaits, garums un raksturlielumi ir atkarīgi no masīva apraksta, piemēram:

19 19 Vektora deskriptora uzbūve Vektora deskriptors: var A: array [ ] of real; A real 6 addr (A[-3]) 1 -3 C 0 2 C 1 A[-3]A[-2] A[-1] A[0]A[1]A[2] 6 baiti

20 20 Vektora adresēšanas funkcijas noteikšana const lo =... ; hi =... ; {indeksa robežvērtības - uzdod lietotājs} type I = lo.. hi; {indeksa tips} B =... ; {vektora elementu tips - uzdod lietotājs} var A: array [I] of B; {vektors A} Elementu skaits N = hi – lo + 1 Vektora adresēšanas funkcija (Adrress Mapping Function, AMF)

21 21 Vektora adresēšanas funkcijas noteikšana A - vektora nosaukums Bāzes tips B Elementa garums L Vektora sākumadrese b Dimensiju skaits d parasti rakstzīmes parasti koda veidā vesels skaitlis adrese – vesels skaitlis vesels skaitlis, d = 1 indeksa robežvērtības adresēšanas funkcijas konstantes lo hi C0C0 C1C1

22 22 Vektora adresēšanas funkcijas noteikšana (turpinājums) b + (i - lo)* L - attālums līdz i-ajam elementam A[lo] A[lo+1]... A[i]... A[hi] b + (i - lo)* L L baiti addr (A[i] ) = b + (i - lo)* L = = (b - L * lo) + i*L = C 0 + C 1 * i C 1 = L C 0 = b - L*lo

23 23 Piemērs var A: array [3.. 7] of integer; lo = 3; hi = 7; L = 2; Pieņemsim, ka b = 500. C 1 = L = 2; C 0 = b – lo*C 1 = *2 = 494 addr (A[i]) = i – lineāra funkcija

24 24 Vektora elementu adresācija datora pamatatmiņā AdreseElements A [3] A [4] A [5] A [6] A [7] addr (A [3]) = *3 = 500; addr (A [5]) = *5 = 504; addr (A [7]) = *7 = 508;

25 25 Matricas adresēšanas funkcija const lo1 =... ; hi1=... ; {indeksa i robežvērtības - uzdod lietotājs} lo2 =... ; hi2 =... ; {indeksa j robežvērtības - uzdod lietotājs} type Ind 1 = lo1.. hi1; {indeksa i tips} Ind 2 = lo2.. hi2; {indeksa j tips} B =... ; {masīva elementu tips - uzdod lietotājs} Matrix = array [Ind 1, Ind 2] of B; {matricas tips} var A: Matrix;

26 26 Matricas adresēšanas funkcijas noteikšana

27 27 Matricas adresēšanas funkcijas noteikšana (turpinājums) addr (A[i, j]) = b + (i – lo 1 ) (hi 2 – lo 2 + 1)*L + (j – lo 2 )*L = attālums līdz attālums i-tai rindai līdz j-ajam elementam rindā i = C 0 +C 1 * i + C 2 * j - divargumentu lineāra funkcija C 2 = L; C 1 = (hi 2 – lo 2 + 1)*C 2 C 0 = b – C 1 *lo 1 – C 2 *lo 2

28 28 Piemērs constlo 1 = 1; hi 1 = 3; lo 2 = 1;hi 2 = 4; typeInd1 = lo 1.. hi 1 ; Ind2 = lo 2.. hi 2 ; B = real; T = array [Ind1, Ind2] of B; varA: T;

29 29 Matricas elementu adresācija datora pamatatmiņā lo 1 = 1;hi 1 = 3; lo 2 = 1;hi 2 = 4; L = 6; b = 500; C 2 = L = 6; C 1 = (hi 2 – lo 2 +1)*C 2 = (4 – 1 + 1)*6 = 24; C 0 = b – C 1 *lo 1 – C 2 *lo 2 = 500 – 24*1 – 6*1 = 470. addr (A [i,j]) = i + 6j

30 30 Divdimensiju masīva adresēšanas funkcija (3) addr (A [1, 2]) = *1 + 6*2 = 506 addr (A [1, 1]) = *1 +6*1 = 500 addr (A [3, 1]) = *3 + 6*1 = 548 addr (A [3, 4]) = *3 + 6*4 = 566 Elementu skaits n = 12. Lauka garums = 12*6 = 72 baiti. Pēdējā elementa adrese = (72 – 6) = 566.

31 31 Vairākdimensiju masīvi un to adresēšanas funkcijas (1) Masīva dimensiju skaits – to praktiski ierobežo tikai datorsistēmas arhitektūra un resursi. Atmiņas apjoms un tā apstrādes laiks strauji pieaug, pieaugot dimensiju skaitam. Ja definēts masīvs ar d dimensijām un L baitiem viena elementa attēlošanai atmiņā, tad viss masīvs atmiņā aizņems L*(hi 1 – lo 1 +1)*(hi 2 – lo 2 + 1) *... *(hi d – lo d +1) baitus, piemēram: var A: array [ , , 1.. 4] of integer; L = 2; d = 3. Masīvs atmiņā aizņems apmēram baitus.

32 32 Vairākdimensiju masīvi un to adresēšanas funkcijas (2) Uzskatīsim, ka vispārējā gadījumā definēts šāds vairākdimensiju masīvs: var A: array [ lo 1.. hi 1,..., lo d.. hi d ] of B; Mēģināsim vispārināt adresēšanas funkcijas konstanšu C 0, C 1, un C d noteikšanas metodiku un formulas: C d = L (elementu garums baitos)... C k-1 = (hi k – lo k + 1) * C k,k = d, d -1,..., 2... C 0 = b – C 1 *lo 1 – C 2 *lo 2 -..C d * lo d addr (A [i 1, i 2,..., i d ) = C 0 + C 1 *i 1 + C 2 *i C d *i d Vairākdimensiju masīvu elementi datora atmiņā tiek izvietoti viens aiz otra tā, ka visstraujāk izmainās pēdējais indekss, bet vislēnāk – pirmais indekss.

33 33 Piemērs Definēts trīsdimensiju masīvs: var A: array [1.. 2, 1.. 2, 1.. 2] of integer; N = 8; Atmiņas lauka garums ir 8*2 = 16 baiti. b = 500; L = 2; d = 3. Adresēšanas funkcijas konstantes: C 3 = L =2; C 2 = (hi 3 – lo 3 + 1)*C 3 = 2*2 = 4; C 1 = (hi 2 – lo 2 + 1)*C 2 = 2*4 = 8; C 0 = b – C 1 *lo 1 – C 2 *lo 2 – C 3 *lo 3 = 500 – 8*1 – 4*1 -2*1 = 486; Adresēšanas funkcija: addr (A [i, j, k]) = i + 4j +2k;

34 34 Trīsdimensiju masīva attēlojums Masīva loģiskā struktūra Fiziskā struktūra addr(A[1,1,2]) = 486+8*1+4*1+2*2 = 502; addr(A[2,2,2]) = 486+8*2+4*2+2*2 = 514; addr(A[1,1,1]) = 486+8*1+4*1+2*1 = 500;