Pole je nejjednodušší, nejstarší a nejčastěji používaná datová struktura v informatice. V paměti je uloženo jako lineárně uspořádaná posloupnost prvků stejného typu, ke kterým lze přistupovat pomocí tzv. indexu. Ten lze chápat jako vzdálenost požadovaného prvku od počátku (prvního prvku) pole - tedy jako souřadnici v jednorozměrném prostoru.

Pokud z důvodu přehlednosti či intuitivnosti používáme k adresaci prvku indexů více (třeba N), mluvíme o poli N-rozměrném. Počet rozměrů pole odpovídá počtu souřadnic (indexů), kterými je popsáno umístění každého jednotlivého prvku v paměti. V tom případě bývá pole v paměti uloženo jako "pole polí", nebo jako pole jednorozměrné, jehož index je přepočí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ů).

diagram

Situace v paměti

Adresa paměťové buňkyIndex hodnotyHodnota
proměnná POLEukazatel na 0x01A2
.........
0x01A2POLE+05
0x01A3POLE+1-24
0x01A4POLE+288
0x01A5POLE+33
0x01A6POLE+4922
.........

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 o větší (resp. menší) volný prostor (který nemusí být k dispozici!), do kterého překopíruje stávající data. Původní pole následně uvolní. Větší pohodlí programátora je vykoupeno větší režií. Menší dynamická pole se však většinou lépe realizují pomocí dynamických seznamů.

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 3x4, uložené v "poli polí":

diagram

Situace v paměti

Adresa paměťové buňkyIndex hodnotyHodnota
proměnná POLEukazatel na 0x5A01
.........
0x5A01POLE+0ukazatel na 0x6122
0x5A02POLE+1ukazatel na 0x6132
0x5A03POLE+2ukazatel na 0x610A
.........
0x610APOLE[2]+00
0x610BPOLE[2]+10
0x610CPOLE[2]+21
.........
0x6122POLE[0]+01
0x6123POLE[0]+10
0x6124POLE[0]+20
.........
0x6132POLE[1]+00
0x6133POLE[1]+11
0x6134POLE[1]+20
.........

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 \times 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ňkyIndex hodnotyHodnota
proměnná POLEukazatel na 0x5A01
.........
0x5A01POLE+01
0x5A02POLE+10
0x5A03POLE+20
0x5A04POLE+30
0x5A05POLE+41
0x5A06POLE+50
0x5A07POLE+60
0x5A08POLE+70
0x5A09POLE+81
.........

Příklad v jazyce Java

Jednorozměrné pole

// deklarace s výchozími hodnotami

int pole1 [] = {1, 0, 5, -4, 55};
// univerzálnější deklarace

int pole2 [];
pole2 = new int [5];
pole2 [0] = 1;
pole2 [1] = 0;
pole2 [2] = 5;
pole2 [3] = -4;
pole2 [4] = 55;
// výpis jednoho prvku

System.out.println (pole1 [3]);
// výpis celého pole

for (int i=0; i < pole1.length; i++)
{
  System.out.println (pole1 [i]);
}

Dvojrozměrné pole

// deklarace s výchozími hodnotami

int matice1 [][] = {{1, 0, 0}, {0, 1, 0}, {0, 0, 1}};
// univerzálnější deklarace

int matice2 [][];
matice2 = new int [3][3];
matice2[0] = new int [3];
matice2[0][0] = 1;
matice2[0][1] = 0;
matice2[0][2] = 0;
matice2[1] = new int [3];
matice2[1][0] = 0;
matice2[1][1] = 1;
matice2[1][2] = 0;
matice2[2] = new int [3];
matice2[2][0] = 0;
matice2[2][1] = 0;
matice2[2][2] = 1;
// výpis jednoho prvku

System.out.println (matice1 [0][2]);
// výpis celého pole

for (int r=0; r < matice1.length; r++) {
  for (int s=0; s < matice1[r].length; s++) {
    System.out.print(matice1[r][s] + " ");
  }
  System.out.println();
}