Pole

Pole je jednou ze základních a nejstarších datových struktur. Jedná se o souvislou lineární posloupnost homogenních prvků v paměti, jejichž pravidelné uspořádání zaručuje rychlý přístup ke každému z nich. Každý prvek je jednoznačně určen adresou prvního prvku pole a dalším přirozeným číslem (tzv. indexem) označujícím vzdálenost požadovaného prvku od začátku pole. Absolutní adresa prvku je pak vypočtena jako součet těchto dvou čísel.

Někdy se z důvodu větší přehlednosti či intuitivnosti používá k adresaci prvku indexů více (například N). Potom se mluví o poli N-rozměrném. Počet rozměrů pole odpovídá počtu indexů, kterými je popsáno umístění každého jednotlivého prvku v paměti. Vícerozměrná pole bývají v paměti uložena jako „pole polí“, nebo jako pole jednorozměrná, jejichž index je vypočítán ze všech indexů pomocí tzv. mapovací funkce (viz níže).

Jednorozměrná pole

V jednorozměrných polích je každý prvek určen právě jedním indexem (souřadnicí). Jednorozměrná pole se nejčastěji používají pro ukládání vektorů (pole čísel) a řetězců (pole znaků).

pole se čtyřmi prvky

Situace v paměti
Adresa paměťové buňky Index hodnoty Hodnota
proměnná POLE ukazatel na 0×01A2
…
0×01A2 POLE+0 5
0×01A3 POLE+1 –24
0×01A4 POLE+2 88
0×01A5 POLE+3 3
…
Příklad v jazyce Java

Takto se s jednorozměrnými poli pracuje v jazyce Java:

kód v jazyce Java - Zobrazit

  1. // deklarace s výchozími hodnotami
  2.  
  3. int pole1 [] = {1, 0, 5, -4, 55};
  4.  
  5. // univerzálnější deklarace
  6.  
  7. int pole2 [];
  8. pole2 = new int [5];
  9. pole2 [0] = 1;
  10. pole2 [1] = 0;
  11. pole2 [2] = 5;
  12. pole2 [3] = -4;
  13. pole2 [4] = 55;
  14.  
  15. // výpis jednoho prvku
  16.  
  17. System.out.println (pole1 [3]);
  18.  
  19. // výpis celého pole
  20.  
  21. for (int i=0; i < pole1.length; i++)
  22. {
  23.   System.out.println (pole1 [i]);
  24. }

Pole v dnešních programovacích jazycích mají zpravidla pevně danou velikost (počet prvků x velikost prvku), ale některé interpretované jazyky jejich velikost dokáží měnit automaticky podle potřeby. Při nedostatečné kapacitě pole požádá program operační systém (či virtuální stroj) o větší volný prostor (který však nemusí být k dispozici!), do kterého překopíruje stávající data. Původní pole se následně uvolní. Větší pohodlí programátora je vykoupeno větší režií.

Vícerozměrná pole

Matice a tabulky jsou příkladem polí dvojrozměrných. Každý prvek určují dvě souřadnice – index řádku a index sloupce. Trojrozměrné pole je zase podobné Rubikově kostce. Pole vyšších rozměrů si již představit neumíme, ale přesto se hojně v programech používají a jsou velmi užitečná.

ukázka jednotkové matice 3×3, uložené v „poli polí“

ukázka trojrozměrného „pole polí polí“

Situace v paměti – pole polí
Adresa paměťové buňky Index hodnoty Hodnota
proměnná POLE ukazatel na 0×5A01
…
0×5A01 POLE+0 ukazatel na 0×6122
0×5A02 POLE+1 ukazatel na 0×6132
0×5A03 POLE+2 ukazatel na 0×610A
…
0×610A POLE[2]+0 0
0×610B POLE[2]+1 0
0×610C POLE[2]+2 1
…
0×6122 POLE[0]+0 1
0×6123 POLE[0]+1 0
0×6124 POLE[0]+2 0
…
0×6132 POLE[1]+0 0
0×6133 POLE[1]+1 1
0×6134 POLE[1]+2 0
…
Mapovací funkce

Použitím mapovací funkce lze ušetřit nějakou tu paměť za cenu dodatečných výpočtů při indexaci. Jak na to? Prvky vícerozměrného pole postupně (po řádcích či po sloupcích) uložíme do pole jednorozměrného. Požadovaný prvek pak nalezneme tak, že všechny indexy nejprve předložíme tzv. mapovací funkci, které je převede na jediný index v tomto jednorozměrném poli. K její sestavení však musíme znát maximální počet prvků v každém rozměru pole.

Mapovací funkce naleznou uplatnění i tam, kde s jiným než jednorozměrným polem pracovat nemůžeme (jednoduché procesory, staré programovací jazyky).

Dvojrozměrné pole na jednorozměrné

Takto vypadá mapovací funkce, která mapuje dvojrozměrné pole o velikosti M x N do pole jednorozměrného (M je počet prvků v jednom řádku):

€€ f(x,y) = x + M \cdot y €€
N-rozměrné pole na jednorozměrné

Zobecněním mapovací funkce z předchozího výkladu získáme návod na sestavování mapovacích funkcí i pro pole vyšších rozměrů (Ni je maximální počet prvků v rozměru i).

€€ f(x_1,...,x_n) = x_1 + \sum_{i=2}^{n} N_i \cdot x_i €€
Situace v paměti – mapovací funkce

Pro převod indexů bude použita tato mapovací funkce (viz níže):

€€ i = x + 3 \cdot y €€
Adresa paměťové buňky Index hodnoty Hodnota
proměnná POLE ukazatel na 0×5A01
…
0×5A01 POLE+0 1
0×5A02 POLE+1 0
0×5A03 POLE+2 0
0×5A04 POLE+3 0
0×5A05 POLE+4 1
0×5A06 POLE+5 0
0×5A07 POLE+6 0
0×5A08 POLE+7 0
0×5A09 POLE+8 1
…
Příklad v jazyce Java

Takto se v Jave pracuje s dvojrozměrným polem:

kód v jazyce Java - Zobrazit

  1. // deklarace s výchozími hodnotami
  2.  
  3. int matice1 [][] = {{1, 0, 0}, {0, 1, 0}, {0, 0, 1}};
  4.  
  5. // univerzálnější deklarace
  6.  
  7. int matice2 [][];
  8. matice2 = new int [3][3];
  9. matice2[0] = new int [3];
  10. matice2[0][0] = 1;
  11. matice2[0][1] = 0;
  12. matice2[0][2] = 0;
  13. matice2[1] = new int [3];
  14. matice2[1][0] = 0;
  15. matice2[1][1] = 1;
  16. matice2[1][2] = 0;
  17. matice2[2] = new int [3];
  18. matice2[2][0] = 0;
  19. matice2[2][1] = 0;
  20. matice2[2][2] = 1;
  21.  
  22. // výpis jednoho prvku
  23.  
  24. System.out.println (matice1 [0][2]);
  25.  
  26. // výpis celého pole
  27.  
  28. for (int r=0; r < matice1.length; r++)
  29. {
  30.   for (int s=0; s < matice1[r].length; s++)
  31.   {
  32.     System.out.print (matice1[r][s] + " ");
  33.   }
  34.   System.out.println ();
  35. }

Reference