Pole

Z CHWiki

Obsah 1 Co je pole a jak se používá? 1.1 Obecný zápis 1.2 Vícerozměrné pole 1.3 Použítí pole 2 Kdy použít pole? 2.1 Jaké jsou výhody? 2.2 Příklad 3 Algoritmy 3.1 Hledání prvku X v poli P 3.2 Smazání n-tého prvku 3.3 Smazání prvku X 3.4 Přidání prvku X za prvek Y 4 Složitost

[editovat] Co je pole a jak se používá?

Datová struktura pole slouží k uchování více proměných stejného typu.
Potřebujete uložit pět čísel typu int, které mají určitou vnitřní souvislost (pět nejlepších výsledků ve hře, ...) ?

int score[5];

Tento zápis vytvoří pět buněk (dejme tomu, že proměnná typu int zabírá 2B. V paměti se tedy vyhradí prostor pro 10B). Každá buňka zastupuje proměnnou typu int.

[editovat] Obecný zápis

datovy_typ jmeno_promenne[pocet_prvku_pole]

Vytvoří pole jmeno_promenne o n prvcich (n = pocet_prvku_pole), kde každá buňka bude datového typu datovy_typ.

[editovat] Vícerozměrné pole

Pole nemusí představovat pouze vektor (1-D). Nejklasičtějším případem vícerozměrného pole je matice (2-D).

datovy_typ jmeno_promenne[pocet_radku_pole][pocet_sloupcu_pole]

Vytvoří pole jmeno_promenne o n sloupcích (n = pocet_sloupcu_pole) a m řádcích (m = pocet_radku_pole), kde každá buňka bude datového typu datovy_typ.

[editovat] Použítí pole

K jednotlivým buňkám přistupujeme pomocí hranatých závorek [ (Alt + 91), ] (Alt + 93), mezi které vložíme číslo buňky. Chceme např. do buňky číslo 0, proměnné pole score, vložit číslo 5:

score[0] = 5

[editovat] Kdy použít pole?

Pole se hodí všude tam, kde je třeba zpracovat množství dat stejného typu. Mějme záznam (strukturu):

struct clovek{
    int vek;
    char pohlavi;
};

Potřebujete uložit 10 lidí? Použijte pole.

clovek lide[10];

[editovat] Jaké jsou výhody?

Chcete zjistit průměrný věk všech lidí? Díky tomu že můžeme k jednotlivým prvkům přistupovat přes jejich indexy (pozice buňky v poli), je řešení nasnadě (pomocí cyklu):

int souhrny_vek = 0;

for(int i = 0; i<10; i++) {
    souhrny_vek += lide[i].vek;
}

průmerný věk je tedy roven souhrny_vek / pocet_prvku_pole.

i < 10 je zvoleno kvůli velikosti pole lide - 10 prvků.

[editovat] Příklad

Ukážeme si, jak bude vypadat pole pokus po těchto řádcích

int pokus[4]; 

pokus[0] = 5;
pokus[2] = 4;

Vytvoříme pole o čtyřech prvcích typu int. Každá buňka má svůj index - 0,1,2,3. Do buňky číslo 0 (tedy do první) vložíme číslo 5. Do buňky číslo 2 (do třetí) vložíme 4.

Tím že indexy buňek standartně začínají od nuly, nezapomentě že pokud má pole např. 10 prvků (obecně n), tak je index poslední buňky roven 9 (obecně n-1).

[editovat] Algoritmy

Poznámka: MAX(P) vrací nejvyšší index v poli P

[editovat] Hledání prvku X v poli P

1. i = 1
2. Dokud platí: (P[i] není X) a zároveň (i < MAX(P)) opakuj
   1. i = i+1
3. Pokud P[i] == X, vrať i, jinak CHYBA - prvek nenalezen

[editovat] Smazání n-tého prvku

1. i = n
2. Dokud platí: (i < MAX(P))
   1. P[i] = P[i+1]
   2. i = i + 1
3. Smaž(P[i])

[editovat] Smazání prvku X

1. i = Find(X)
2. SmažNtýPrvek(i)

[editovat] Přidání prvku X za prvek Y

1. i = Find(Y)
2. j = MAX(P) - 1
3. Dokud platí: (i < j) opakuj
   1. P[j+1] = P[j]
   2. j = j - 1
4. P[j] = X

[editovat] Složitost

• Hledání n-tého prvku - O(1)
• Hledání prvku X - O(n)
• Smazání n-tého prvku bez posunutí pole - O(1)
• Smazání n-tého prvku - O(n)
• Smazání prvku X - O(n)
• Přidání prvku na konec - O(1)
• Přidání prvku X za prvek Y - O(n)