Dnes se zaměříme na jednoduchou datovou strukturu - pole. Probereme také vztah mezi poli a ukazateli a dojde i na oblíbené programátorské chyby.
9.12.2004 13:00 | Jan Němec | czytane 103504×
RELATED ARTICLES
KOMENTARZE
Pole
Používat proměnné už umíme. Definovat jednoduchou proměnnou, přiřadit do ní
hodnotu a někdy později ji zase načíst není nic těžkého. Dnes si ukážeme, jak
lze jednou definicí vytvořit proměnných více a jak k nim budeme přistupovat.
Pokud chceme takto hromadně definovat nějaký počet proměnných určitého typu,
napíšeme
například
Překladač vyhradí souvislý kus paměti pro deset proměnných typu int. Tato
konstrukce se nazývá pole. Velikost pole musí být známa již v době překladu,
nelze tedy psát třeba
kde n je obyčejná proměnná. K jednotlivým proměnným lze přistupovat pomocí
indexu v hranatých závorkách, například
a[0] = 5;
a[7] = a[1] + 15;
Index pole (narozdíl od velikosti pole v definici) nemusí být konstanta, takže
pokud třeba chceme vyplnit pole tak, aby na pozici i bylo číslo 2*i, nebudeme
otrocky psát
int a[10];
a[0] = 0;
a[1] = 2;
a[2] = 4;
/* ... */
a[9] = 18;
ale použijeme for cyklus
int i;
int a[10];
for (i = 0; i < 10; i++)
a[i] = 2 * i;
Všimněte si, že pole velikosti n má prvky od na pozicích od
0 do n - 1.
Oblíbenou chybou je přístup k prvku na pozici n. Je to chyba o to
nebezpečnější, že jazyk C nekontroluje meze polí, z hlediska překladače
je tedy zcela v pořádku příkaz
a přeloží se jako "do paměti těsně za pole a vlož číslo 20 se všemi důsledky,
které to bude mít". Za polem a může být volné místo, jiná proměnná, adresa
kódu po návratu z funkce, případně i paměť, do které nemáme právo psát atd.
Chování takového programu pak závisí na platformě, překladači a někdy i
na náhodě. Známé chyby spojené někdy až s vykonáním nepřátelského kódu jsou
obvykle právě důsledky špatného hlídání mezí polí v programu. Útočník (například
přes Internet) zadá programu delší vstup, než je velikost připraveného pole,
a díky programátorské chybě nebude tento vstup odmítnut nebo zkrácen.
Do vstupu přidá kus kódu pro daný procesor a nakonec i přepíše adresu
pro návrat z funkce na tento kód. Výše uvedený postup samozřejmě závisí
na architektuře napadeného počítače a nemusí být ve všech případech možný.
Podobně jako běžnou proměnnou lze i pole inicializovat již při definici.
int a[5] = {1, 2, 3, 4, 5};
/* nebo i */
int b[5] = {1, 2};
Inicializačních hodnot může být méně než je velikost pole. V tom případě
se naplní začátek pole a zbývající hodnoty nejsou definovány.
Běžným příkladem pro začínající programátory, který ukazuje praktickou
použitelnost pole je třídění.
/* Nesetříděné pole*/
int a[10] = {8, 4, 2, 5, 0, 9, 7, 6, 3, 1};
int i, j, m, tmp;
for (i = 0; i < 9; i++) {
/* Najdi minimum nesetříděné části pole */
m = i;
for (j = i + 1; j < 10; j++)
if (a[m] > a[j]) m = j;
/* v a[m] je minimum, prohoď a[m] a a[i] */
tmp = a[i];
a[i] = a[m];
a[m] = tmp;
}
Prvkem pole může být jakýkoli typ. Tím typem může být opět pole, takže lze
vytvářet nejen pole např. intů ale i pole polí intů. Říká se tomu vícerozměrné
pole. Takové pole pak má dva indexy.
int matice[6][3];
int i, j;
for (i = 0; i < 6; i++)
for (j = 0; j < 3; j++)
matice[i][j] = i + j;
Lze samozřejmě vytvářet i tří a vícerozměrné pole. Statická inicializace
vícerozměrného pole se provádí stejně jako u jednorozměrného. Dvourozměrné
pole reprezentující funkci xor by vypadalo asi takhle:
int xor[2][2] = {{0, 1}, {1, 0}};
Norma C zaručuje, že prvky pole následují v paměti bezprostředně za sebou.
Toho lze u vícerozměrných polí využít k různým způsobům indexace jednoho prvku.
Při definici
se vyhradí místo pro šest tříprvkových polí intů, souvislý kus
paměti o velikosti 6 * 3 * sizeof(int) bytů. Díky toleranci C a absenci
kontroly mezí polí pak můžeme třeba místo matice[1][0] psát matice[0][3].
Výraz matice[0][3] znamená první int za polem matice[0], tedy první int
pole matice[1], tedy matice[1][0]. Vícerozměrné pole tak můžeme adresovat
jen pomocí posledního indexu, v konkrétních příkladech to může být
(zejména z důvodů efektivity) výhodnější.
Pole a ukazatele
V Céčku je pole do značné míry kompatibilní s ukazatelem. Identifikátor pole
bez indexu v hranatých závorkách se chová jako konstantní ukazatel na první
prvek pole. Konstantní ukazatel znamená ukazatel, jehož hodnotu nelze měnit,
lze však měnit obsah paměti, na niž ukazuje. Typ ukazatele je stejný jako typ
prvků pole.
int i[3]; /* pole tří intů */
int *pi; /* ukazatel na int */
pi = i; /* pi míří na začátek pole, tedy na i[0] */
*pi = 1; /* totéž, jako i[0] = 1; */
Naopak neprojde
neboť pole samo (nikoliv jeho obsah) je konstantní. Kompatibilita polí a
ukazatelů je obousměrná, k ukazateli lze přistupovat jako k poli.
pi[2] = 5;
printf("%i\n", pi[2]);
Podmínkou samozřejmě je, že ukazatel míří na nějakou paměť, k níž máme přístup.
Počítání s ukazateli
S ukazateli lze provádět některé aritmetické operace. Lze k němu přičíst nebo
od něj odečíst nějaké číslo, dva ukazatele stejného typu lze také porovnávat a
odečítat.
int i;
char *s = "linuxsoft.cz";
/* s teď ukazuje na písmeno 'l'*/
char *p = s + 4;
/* přičtení čísla k ukazateli, p míří o čtyři znaky dál, tedy na 'x' */
p--;
/* totéž jako p = p - 1 nebo jako p -= 1, teď míří p na 'u' */
i = p - s;
/* Rozdíl dvou ukazatelů, o kolik prvků se liší. V i bude 3 */
if (p <= s) puts("Něco nefunguje.");
/* Porovnání ukazatelů, který ukazuje na vyšší paměť? Lze použít všechny
porovnávací operátory včetně == */
Je důležité vědět, že celá ukazatelová aritmetika počítá s jednotkami
velikosti typu ukazatele a nikoli s byty. Například ukazatel na int zvětšený
v Céčku o jedničku míří do paměti o sizeof(int) výše a nikoli na druhý byte
původního intu. Podobně rozdíl dvou ukazatelů typu int * mířících na dva
sousední prvky pole intů (takže faktický rozdíl v paměti je sizeof(int) bytů)
nebude sizeof(int), ale jedna.
Díky kompatibilitě ukazatelů a polí si může programátor vybrat, jakým stylem
bude psát. Přístup k paměti v syntaxi pole je určitě přehlednější, ale
přístup přes ukazatele může za určitých okolností vést k efektivnějšímu kódu.
Týká se to zejména překladačů se špatnou optimalizací nebo složitějších
algoritmů.
Vynulovat pole můžeme dvěma způsoby:
int a[10];
int i;
for (i = 0; i < 10; i++)
a[i] = 0;
nebo
int a[10];
int *p, *pkonec;
/* do pkonec dej ukazatel za pole */
pkonec = a + 10;
p = a;
/* dokud p míří na adresu, která není za polem, do *p dej nulu a zvětši
p o jeden prvek (respektive o sizeof(int) bytů) */
while (p < pkonec) *p++ = 0;
První způsob řešení je určitě přehlednější.
Pokračování příště
Příště se podíváme na uživatelský vstup a řetězce.