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).
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ů).
Adresa paměťové buňky | Index hodnoty | Hodnota |
---|---|---|
proměnná POLE | ukazatel na 0x01A2 | |
... | ... | ... |
0x01A2 | POLE+0 | 5 |
0x01A3 | POLE+1 | -24 |
0x01A4 | POLE+2 | 88 |
0x01A5 | POLE+3 | 3 |
0x01A6 | POLE+4 | 922 |
... | ... | ... |
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ů.
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í":
Adresa paměťové buňky | Index hodnoty | Hodnota |
---|---|---|
proměnná POLE | ukazatel na 0x5A01 | |
... | ... | ... |
0x5A01 | POLE+0 | ukazatel na 0x6122 |
0x5A02 | POLE+1 | ukazatel na 0x6132 |
0x5A03 | POLE+2 | ukazatel na 0x610A |
... | ... | ... |
0x610A | POLE[2]+0 | 0 |
0x610B | POLE[2]+1 | 0 |
0x610C | POLE[2]+2 | 1 |
... | ... | ... |
0x6122 | POLE[0]+0 | 1 |
0x6123 | POLE[0]+1 | 0 |
0x6124 | POLE[0]+2 | 0 |
... | ... | ... |
0x6132 | POLE[1]+0 | 0 |
0x6133 | POLE[1]+1 | 1 |
0x6134 | POLE[1]+2 | 0 |
... | ... | ... |
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).
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):
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).
Pro převod indexů bude použita tato mapovací funkce (viz níže):
Adresa paměťové buňky | Index hodnoty | Hodnota |
---|---|---|
proměnná POLE | ukazatel na 0x5A01 | |
... | ... | ... |
0x5A01 | POLE+0 | 1 |
0x5A02 | POLE+1 | 0 |
0x5A03 | POLE+2 | 0 |
0x5A04 | POLE+3 | 0 |
0x5A05 | POLE+4 | 1 |
0x5A06 | POLE+5 | 0 |
0x5A07 | POLE+6 | 0 |
0x5A08 | POLE+7 | 0 |
0x5A09 | POLE+8 | 1 |
... | ... | ... |
// 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]);
}
// 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();
}