1-AIN-140: Princípy počítačov - hardvér - 3. cvičenie
Ak potrebujeme do pamäte uložiť viacero hodnôt, môžeme použiť niekoľko premenných - napríklad a, b, c, ... V tom prípade bude počet hodnôt pevne stanovený počtom premenných, ktoré takto využijeme. Ak by sme potrebovali spracovať viac ako 10 hodnôt, asi by to nebolo veľmi praktické, program by začal byť zbytočne komplikovaný. Naviac, ak počet hodnôt v okamihu, keď píšeme program, nepoznáme, nemožno ani určiť, koľko takýchto premenných použiť. V tom prípade môžeme použiť špeciálny typ premennej - pole (po anglicky array), ktoré označuje N-ticu hodnôt rovnakého typu. Pomocou premennej typu pole môžeme v pamäti vyhradiť miesto pre niekoľko hodnôt, ktoré budú uložené jedna za druhou a ku všetkým sa dostaneme pomocou tej istej premennej.
V jazyku C vytvoríme pole takto:
int p[10];
pričom namiesto typu int môžeme pre položky poľa stanoviť akýkoľvek iný typ. Číslo v hranatých zátvorkách určuje počet prvkov poľa, v jazyku C sú polia indexované od 0, takže:
p[0] = 42; // takto priradíme hodnotu do "prvého" prvku poľa (niekedy mu hovoríme "nultý")
p[9] = 100; // toto je posledný prvok 10-prvkového poľa (indexy 0..9)
Indexovať polia možno aj pomocou číselnej premennej, napríklad:
//vypíš prvých n prvkov poľa:
for (int i = 0; i < n; i++)
printf("%d ", p[i]);
Ak chceme na mieste, kde pole definujeme, hneď určiť jeho prvky, môžeme použiť takúto inicializáciu:
int p[5] = { 7, 7, 0, 0, 7 };
alebo aj takto:
int p[] = { 7, 7, 7 }; // 3-prvkové pole s indexami 0..2
Na rozdiel od niektorých vyšších jazykov, v jazyku C sa vo všeobecnosti nedá zistiť veľkosť poľa, pretože sa jeho počet prvkov kvôli efektivite do pamäte neukladá - C-čko je nízkoúrovňový jazyk, ktorý sa snaží vyhnúť všetkému navyše, čo nie je nevyhnutné. Preto napríklad ak chceme vytvoriť funkciu, ktorá vypíše všetky prvky poľa, potrebujeme jej odovzdať cez iný argument počet jeho prvkov:
void vypis_pole(int p[], int n)
{
for (int i = 0; i < n - 1; i++)
printf("%d,", p[i]);
if (n > 0) printf("%d\n", p[n - 1]);
}
Vráťme sa ale ešte raz na začiatok a pozrime sa, ako jazyk C rozumie premennej typu pole. Definícia:
int p[3];
obsadí v pamäti 3 za sebou idúce položky typu int (jeden int väčšinou zaberá 4 bajty) a premenná p "obsahuje" adresu prvej položky poľa. Situácia teda môže vyzerať napríklad takto:
adresa pamäť
| ... | adresa 30000125H je v tomto príklade
|-------| zvolená náhodne - pole je umiestnené
/---> 30000125H | p[0] | "niekde" v pamäti, tam, kde je miesto,
| | . . . | napr. na adrese 30000125H
/-------\ | | |
p | 25H | | | . . . |
| . . . |--/ | |
| 01H | | . . . |
| . . . | | |
| 00H | |-------|
| . . . | 30000129H | p[1] |
| 30H | | . . . |
\-------/ | |
| . . . | všimnite si vľavo, že hodnota p sa v pamäti
| | (na mnohých počítačoch) ukladá po bajtoch
| . . . | v opačnom poradí: pre 4-bajtové číslo 30000125H
| | je najskôr uložený najmenej významný bajt (25H),
|-------| potom druhý najmenej významnamný bajt (01H), atď,
3000012DH | p[2] | a až na koniec najvýznamnejší bajt (30H).
| . . . | (architektúra Little Endian - začína sa menej významnejšími bajtami)
| | - to ale pre nás nie je teraz až tak dôležité,
| . . . | lebo s týmito jednotlivými bajtami teraz nepracujeme
| | a naviac - v prípade poľa sa táto adresa v skutočnosti
| . . . | do pamäte neukladá - to iba v prípade smerníkov o ktorých
| | sa dozvieme viac čoskoro...
|-------|
| ... | v každom prípade však: printf("%u\n", p); // vypíše 805306661 = 30000125H
Keď už sme načali tému poradia ukladania bajtov v pamäti pre viac-bajtové číselné typy (Little Endian vs. Big Endian),
tak si uvedomme, kedy na tomto poradí záleží. Kým dáta neopustia ten istý počítač, kde vznikli, k problémom nedochádza
- všetky údaje sú ukladané v rovnakom poradí bajtov. Ak však takéto viacbajtové čísla (napr. hodnotu typu int)
zapíšeme do súboru a potom tento súbor otvoríme na inom počítači, alebo tam tieto údaje rovno pošleme cez sieť,
môže dôjsť k vážnym problémom - rovnaký program v jazyku C na druhom počítači kvôli tomu ako s údajmi pracuje
procesor, prečíta bajty v nesprávnom poradí a získa celkom iné hodnoty, ako mal! Preto pri prenášaní údajov
medzi rôznymi počítačmi nie je vhodné používať priamy binárny zápis údajov, ale radšej len dohodnuté formáty
s presne stanoveným formátom ukladania hodnôt (a to sa týka nielen poradia bajtov, ale aj zarovnávania
štruktúr na adresy deliteliteľné 2, 4, alebo inou mocninou 2). Zaujalo vás to? Prečítajte si tento
článoček.
Naspäť k poliam. Ak teraz do poľa zapíšeme nejaké hodnoty, napríklad:
p[0] = 1;
p[1] = 100; // == 64H
p[2] = 1000; // == 3E8H
Situácia v pamäti bude vyzerať takto:
adresa pamäť
| ... |
|-------|
/---> 30000125H | 01H |
| p[0] | . . . |
/-------\ | | 00H |
p | 25H | | | . . . |
| . . . |--/ | 00H |
| 01H | | . . . |
| . . . | | 00H |
| 00H | |-------|
| . . . | 30000129H | 64H |
| 30H | p[1] | . . . |
\-------/ | 00H |
| . . . |
| 00H |
| . . . |
| 00H |
|-------|
3000012DH | E8H |
p[2] | . . . |
| 03H |
| . . . |
| 00H |
| . . . |
| 00H |
|-------|
| ... |
Vidíme, že premenná p sa správa ako "šípka", čiže smerník. A naozaj, rozdiel medzi poľom a smerníkom v jazyku C je minimálny - premenná typu pole sa dá použiť aj ako smerník. Čo je to ale ten smerník?
Premenná typu smerník je taká premenná uložená niekde v pamäti, v ktorej je adresa, kde sa nachádza nejaká hodnota. Čiže napr. v premennej typu smerník na int (napr. "int *x;") nie je uložená hodnota typu int, ale adresa miesta v pamäti, kde sa nejaká hodnota typu int nachádza. V smerníku môže byť aj adresa 0, čo väčšinou znamená, že smerník práve neukazuje na žiadnu hodnotu. Nulu tam môžeme priamo priradiť: int *x = 0; V smerníku môže byť aj nejaká iná - napr. náhodná adresa, na ktorej sa žiadna hodnota nenachádza. Ba čo horšie, taká adresa niekedy označuje miesto v pamäti, ktoré ani nepatrí danému procesu, alebo patrí, ale na tom mieste sú nejaké iné premenné. Použitie takéhoto smerníka s omylom nesprávne nastavenou adresou, mysliac si, že na nejakú hodnotu ukazoval, môže spôsobiť poriadnu galibu = chybu, ktorá sa veľmi ťažko hľadá, lebo sa nemusí hneď prejaviť.
Pre nasledujúci kus kódu:
int x = 654321; // 654321 = 0009FBF1H
int *ptr = &x; // unárny operátor & vráti adresu, kde je uložená premenná, ktorá je jeho argumentom
teda situácia v pamäti môže vyzerať napríklad takto:
adresa pamäť
| ... |
|-------|
10000321H | F1H | <-----\ 10000321H a 10000532H sú náhodné (vymyslené) adresy
x | . . . | |
| FBH | |
| . . . | |
| 09H | |
| . . . | |
| 00H | |
|-------| |
10000325H | | |
| . . . | |
|~~ ~ ~~| |
.
... .
.
|~ ~~ ~ | |
| . . . | | premenná ptr je smerník, ktorý ukazuje na miesto v pamäti,
| | | ktoré zaberá premenná x, čiže v skutočnosti obsahuje
|-------| | jej adresu 10000321H (v tomto príklade)
10000532H | 21H | --------/ aj premenná ptr je uložená niekde v pamäti
ptr | . . . | (na rozdiel od adresy prvého prvku poľa p v predchádzajúcom príklade)
| 03H |
| . . . |
| 00H |
| . . . |
| 10H |
|-------|
| ... |
Vidíme, že pole a smerník sú skoro to isté, len "adresa z poľového smerníka" nie je uložená v pamäti - keď je raz pole zadefinované, tak vždy ukazuje na to isté miesto v pamäti, je to konštanta. Naopak, "adresa zo smerníkóvého smerníka" :-) je uložená v smerníkovej premennej, ktorá je kdesi v pamäti - ako ptr na predchádzajúcom obrázku. Je to preto, že smerník sa môže meniť a raz ukazovať na nejakú jednu hodnotu typu int, inokedy na inú hodnotu typu int. Nový príklad:
int x = 3, y = 5;
int *ptr = &x; // teraz ptr ukazuje na x
printf("%d\n", *ptr); // operátor * aplikovaný na smerník z neho vytiahne hodnotu, na ktorú ukazuje
ptr = &y; // a teraz ptr ukazuje na y
printf("%d\n", *ptr); // vypísala sa najskôr hodnota 3 a teraz hodnota 5
No a keďže hodnoty poľa sú v pamäti uložené pekne za sebou a smerník môže ukazovať na položky rovnako ako pole, tak sa smerník dá používať aj ako pole. Napríklad takto:
int pole[] = {1, 2, 3, 4, 5};
int *ptr;
ptr = pole; // teraz smerník ptr ukazuje na prvú položku poľa, ale hodnoty poľa sú v pamäti stále iba 1x!
for (int i = 0; i < 5; i++)
printf("%d ", ptr[i]); // smerník sa používa aj ako pole
a nielen to, keďže smerník je premenná, tak ho môžeme meniť tak, aby postupne prechádzal cez jednotlivé prvky poľa, aha:
int pole[] = {1, 2, 3, 4, 5};
int *ptr = pole;
for (int i = 0; i < 5; i++)
printf("%d ", *(ptr++)); // ptr++ posunie smerník na ďalšiu položku typu int (čiže ho zväčší o 4, keďže int zaberá 4 bajty)
// pred jeho posunutím sa však použije (vypíše) hodnota, na ktorú ukazoval
v prípade, že naše pole obsahuje nenulové čísla a je ukončené nulou, môžeme to zapísať aj takto:
int pole[] = {1, 2, 3, 4, 5, 0};
int *ptr = pole;
while (*ptr) // ak ptr ukazuje na nulovú položku, podmienka nebude splnená a cyklus skončí
printf("%d ", *(ptr++));
Zhrnutie: Videli sme, že so smerníkmi dokážeme počítať skoro ako s číslami (veď sú to čísla = adresy!). Okrem toho, na miestach, kde sa používa pole, je rovnako dobre možné
použiť namiesto toho smerník. A v skutku, indexovanie poľa, napríklad pole[i] kompilátor v skutočnosti najskôr preloží na *(pole + i), pričom pole
v tomto výraze funguje presne ako smerník.
Na záver si vyriešme nasledujúce úlohy, ktoré využívajú pole:
1. funkcia int rovnake(int[] a, int[] b, int n) zistí, či dve polia a[] a b[] rovnakej dĺžky n obsahujú rovnaké prvky - v tom prípade vráti 1, inak vráti 0:
#include <stdio.h>
int rovnake(int a[], int b[], int n)
{
for (int i = 0; i < n; i++)
if (a[i] != b[i]) return 0;
return 1;
}
// iný zápis pomocou smerníkov
int rovnake2(int *a, int *b, int n)
{
while (n--) if (*(a++) != *(b++)) return 0;
return 1;
}
int main()
{
int x[] = {1, 2, 3, 4, 5}; // pole dĺžky 5 môžeme použiť aj ako pole dĺžky 4
int y[] = {1, 2, 3, 4};
int z[] = {1, 3, 2, 4};
printf("rovnake x,y: %d\n", rovnake(x, y, 4));
printf("rovnake y,z: %d\n", rovnake(y, z, 4));
printf("rovnake2 x,y: %d\n", rovnake2(x, y, 4));
printf("rovnake2 y,z: %d\n", rovnake2(y, z, 4));
return 0;
}
2. funkcia je_aritmeticka(int[] p, int n) zistí, či prvky poľa tvoria aritmetickú postupnosť - v tom prípade vráti 1, inak vráti 0:
#include <stdio.h>
int je_aritmeticka(int a[], int n)
{
if (n < 3) return 1;
int delta = a[1] - a[0];
for (int i = 2; i < n; i++)
if (a[i] - a[i - 1] != delta) return 0;
return 1;
}
// trochu exotickejšie riešenie
int je_aritmeticka2(int *a, int n)
{
if (n-- < 3) return 1;
int delta = *(a + 1) - *a;
a++;
while (--n) if ((*(a + 1) - *a) != delta) return 0; else a++;
return 1;
}
int main()
{
int x[] = {3, 7, 11, 15, 19};
int y[] = {2, 4, 8, 16};
int z[] = {9, 10, 11, 12};
printf("aritmeticka x: %d\n", je_aritmeticka(x, 5));
printf("aritmeticka2 x: %d\n", je_aritmeticka2(x, 5));
printf("aritmeticka y: %d\n", je_aritmeticka(y, 4));
printf("aritmeticka2 y: %d\n", je_aritmeticka2(y, 4));
printf("aritmeticka z: %d\n", je_aritmeticka(z, 4));
printf("aritmeticka2 z: %d\n", je_aritmeticka2(z, 4));
return 0;
}
3. funkcia kombinacie(int[] p, int n, int k), ktorá vypíše všetky k-prvkové podmnožiny n-prvkovej množiny uloženej v poli p.
#include <stdio.h>
int kombi[100]; // najviac 100-prvkové podmnožiny
void kombinuj(int velkost, int p[], int n, int k)
{
if (velkost == k) // dalšia podmnožina vytvorená
{
for (int i = 0; i < velkost; i++)
printf("%d ", kombi[i]);
printf("\n");
}
else // potrebujeme ešte (k - velkost) prvkov a máme k dispozícii ešte n
{
if (n > k - velkost) kombinuj(velkost, p + 1, n - 1, k); // buď p[0] nezaradíme, ak si to ešte môžeme dovoliť
kombi[velkost] = p[0];
kombinuj(velkost + 1, p + 1, n - 1, k); // alebo ho zaradíme - to môžeme spraviť vždy
}
}
void kombinacie(int p[], int n, int k)
{
kombinuj(0, p, n, k);
}
int main()
{
int x[] = {3, 7, 11, 15, 19, 21};
kombinacie(x, 5, 2); // 2-prvkové podmnožiny 5-prvkovej množiny
kombinacie(x, 6, 3); // 3-prvkové podmnožiny 6-prvkovej množiny
return 0;
}
V úlohách cvičenia 3 a domácej úlohy si precvičíme prácu s poľom.