Tömbök

Tömbök

Tömb, mint absztrakt adattípus

Algoritmusok tervezésekor gyakran előfordul, hogy adatok sorozatával kell dolgozni, vagy mert az input adatok sorozatot alkotnak, vagy mert a feladat megoldásához kell. Tegyük fel, hogy a sorozat rögzített elemszámú (\(n\)) és mindegyik komponensük egy megadott (elemi vagy összetett) típusból \(E\) való érték. Ekkor tehát egy olyan összetett adathalmazzal van dolgunk, amelynek egy eleme \(A = (a_0, \dots, a_{n-1})\), ahol \(a_{i} \in E, \forall i \in (0, \dots, n-1)\)-re. Ha az ilyen sorozatokon a következő műveleteket értelmezzük, akkor egy (absztrakt) adattípushoz jutunk, amit tömb típusnak nevezünk. Jelöljük ezt a tömb típust \(T\)-vel, amely tömb elemei \(E\) típusú adatok, a \(0, \dots, n-1\) intervallumot pedig jelöljük \(I\)-vel, ezekkel az értékekkel tudunk majd a tömb elemeire hivatkozni!

Művelet megnevezése	Művelet leírása
Kiolvas (\(\rightarrow\) A: T, \(\rightarrow\) i: I, \(\leftarrow\) x: E)	Az A tömb i. értékét kiolvassa és eltárolja az x változóban.
Módosít(\(\leftrightarrow\) A: T, \(\rightarrow\) i: I, \(\rightarrow\) x: E)	Az A tömb i. értékét módosítja az x értékkel.
Értékadás (\(\leftarrow\) A: T, \(\rightarrow\) X: T)	Az A tömb felveszi az X tömb típusú kifejezés értékét.

Tömb, mint virtuális adattípus

Amikor egy tömböt szeretnénk létrehozni, annak deklarációja nagyon hasonlít ahhoz, ahogy adott típusból egyetlen adat deklarációját megadjuk, annyi különbség van, hogy a változó neve kiegészül egy szögletes zárójel párral, ami között megadjuk a tömb méretét, azaz azt az elemszámot, amennyi elemet el szeretnénk tárolni a tömbben. Azaz:

típus változónév[elemszám];

Konkrét példával:

char ct[t]; //létrehoz egy 5 darab char típusú elem eltárolására szolgáló tömböt
unsigned short int it[20]; //20 elemű unsigned short int tömb

Természetesen a tömb típussal is definiálhatunk új típust:

typedef típus újnév[elemszám];

Például:

typedef int tomb20[20];
tomb20 t;

Művelet absztrakt szinten	Művelet virtuális megvalósítása
Kiolvas (\(\rightarrow\) A: T, \(\rightarrow\) i: I, \(\leftarrow\) x: E)	x = A[i];
Módosít(\(\leftrightarrow\) A: T, \(\rightarrow\) i: I, \(\rightarrow\) x: E)	A[i] = x;
Értékadás (\(\leftarrow\) A: T, \(\rightarrow\) X: T)	Nincs direkt megvalósítás! Használható a memcpy(), vagy a \(C^{11}\) szabvány után a biztonságosabb memcpy_s() függvény.

Fontos megjegyezni, hogy a C nyelvben az indexelés mindig 0-val kezdődik. Azaz egy int t[20]; deklaráció esetén a tömb elemei a t[0], \(\dots\), t[19] lesznek. Figyelni kell arra, hogy a C-ben nincs indexhatár-ellenőrzés. Ez azt jelenti, hogy a fenti példánál maradva tudunk hivatkozni a t[-1], vagy esetleg t[20] elemekre is, ami lehet, hogy látszólag rögtön nem okoz problémát, de nagyon csúnya futási hibákat eredményezhet amiatt, hogy a memória egy olyan területét érjük el, amin más adat van.

Általános tömb típus, mint absztrakt adattípus

Az eddigiekben a tömbben tárolt elemek típusa egyszerű típus volt, a tömb indexelése egy dimenzión mozgott. Azonban elképzelhető, hogy az adatokat célszerűbb több dimenzióban tárolni. Gondoljunk egy táblázatra, amelynek oszlopai és sorai vannak, az egyes elemeket pedig a sor és oszlop sorszámok segítségével a legegyszerűbb meghatározni.

Éppen ezért, a tömböket definiálhatjuk általános módon is, ahol eltérően az előző definíciótól a tömbben tárolt adatok \(E\) típusa mellett indexek egy sorozatát adjuk meg. Ehhez legyenek \(I_1, \dots, I_k\) tetszőleges sorrendi típusok, ahol az
\(I = I_1 \times \dots \times I_k = \{ (i_1, \dots, i_k) |i_1 \in I_1, \dots, i_k \in I_k \}\)
halmaz, amely az \(I_1 \times \dots \times I_k\) halmazok direktszorzatából áll, megadja az indexek halmazát. Képezhetjük azt a \(T = Tomb( I_1 \times \dots \times I_k, E)\) új típust, amelynek értékhalmaza az \(I\)-ből \(E\)-be való függvények halmaza, azaz: \(\{ A|A : i \rightarrow E \}\). A \(k\)-t a tömb dimenziójának nevezzük.

Nem meglepő módon egy általános tömb esetében hasonló műveletekre számítunk, mint az egyszerű, egy dimenziós esetben, a különbség csupán az indexek megadásában van:

Művelet megnevezése	Művelet leírása
Kiolvas (\(\rightarrow\) A: T, \(\rightarrow\) i1: I1, \(\dots\), ik:Ik , \(\leftarrow\) x: E)	Az A tömb (i1, \(\dots\),ik) komponensát kiolvassa és eltárolja az x változóban.
Módosít(\(\leftrightarrow\) A: T, \(\rightarrow\) i1: I1, \(\dots\), ik:Ik , \(\rightarrow\) x: E)	Az A tömb (i1, \(\dots\),ik)komponensét módosítja az x értékkel.
Értékadás (\(\leftarrow\) A: T, \(\rightarrow\) X: T)	Az A tömb felveszi az X tömb típusú kifejezés értékét.

Általános tömb típus, mint virtuális adattípus

Könnyen ésszrevehetjük, hogy egy T = Tomb( I1\(\times \dots \times\) Ik, E) típus felfogható úgy, mint egy olyan egyszerű, egy dimenziós T = Tomb( I1 , T1) tömb, amely T1 = Tomb( I2 \(\times \dots \times\) Ik, E) típusú tömböket tárol. Továbbá az sem jelent megkötést, hogy minden egyes Ij intervallum [0 .. Nj] alakú legyen, hiszen bármely [n..m] intervallum elemei egyszerűen transzformálhatóak a [0..(m-n)] intervallumra. Ezek alapján a C nyelven már létre tudunk hozni többdimenziós tömb típust is:
typedef E T[N1][N2] ...[Nk];

Művelet absztrakt szinten	Művelet virtuális megvalósítása
Kiolvas (\(\rightarrow\) A: T, \(\rightarrow\) i1: I1, \(\dots\), ik:Ik , \(\leftarrow\) x: E)	x = A[i1]...[ik];
Módosít(\(\leftrightarrow\) A: T, \(\rightarrow\) i1: I1, \(\dots\), ik:Ik , \(\rightarrow\) x: E)	A[i1]...[ik] = x;
Értékadás (\(\leftarrow\) A: T, \(\rightarrow\) X: T)	Nincs direkt megvalósítás! Használható a memcpy(), vagy a \(C^{11}\) szabvány után a biztonságosabb memcpy_s() függvény.

Tömb inicializálása

Amikor egy tömböt létrehozunk, akkor lehetőségünk van arra, hogy annak elemeit kezdőértékekkel lássuk el. Például:

int t[][3] = {
    { 1, 2, 3 },  { 4, 5, 6 },  { 7, 8, 9 }
};
int t1[4][3] = {
    { 1, 2, 3 },  { 4, 5, 6 },  { 7, 8, 9 }
};
int t2[][3] = {
    { 1 },  { 4 },  { 7 },  { 9 }
};

A fenti példában a t tömb egy 3*3-as tömb. Bár az első dimenzió mérete nincs megadva, az a kezdőértékek számából kiolvasható. A t2-es tömbnél viszont látjuk, hogy maga a tömb 4*3-as, de látszólag ugyanúgy van inicializálva, mint a t tömb. Ha ezt a 2 dimenziós tömböt egy táblázatnak képzeljük el, akkor ez egy 4 soros, 3 oszlopos táblázat, aminek az utolsó sora a szabvány szerint 0-val inicializálódik. A t3-as tömbnél nem adjuk meg az első dimenzió méretét, ezt az inicializálásból ki tudjuk találni, hogy 4. A nem inicializált elemek itt is 0 értéket vesznek fel.

Ha tehát tömböt kezdőértékkel deklarálunk, akkor az első dimenzió mérete elhagyható, mert az a kezdőértékek számából kiolvasható. De ha kevesebb kezdőértéket adunk meg, mint amekkora tömbre később szükségünk van, akkor ezt a méretet is meg kell adni.

Inicializálás

Ha egy tömböt hiányosan inicializálunk (de inicializálunk), akkor a hiányzó elemeket 0-val (vagy azzal ekvivalens értékkel) tölti fel a fordító. Ha egy tömböt nem inicializálunk (hiányosan sem), az elemei definiálatlanok maradnak, nem kapnak kezdőértéket.

Általános tömb típus, mint fizikai adattípus

A tömbök esetében nagyon fontos látnunk, hogy az egyes elemeket hogyan is tárolja el egy-egy C program, mivel látni fogjuk, hogy ezen ismeret fogja segíteni azt, hogy akár pointerekkel hivatkozzunk egy-egy tömb elemre. A lehetséges gépi megvalósítás vizsgálatánál abból kell kiindulni, hogy a memória lineáris szerkezetű. Tömb típusú változó számára történő helyfoglalás azt jelenti, hogy minden tömbelem, mint változó számára memóriát kell foglalni. Feltehetjük, hogy egy adott tömb változóhoz a tömbelemek számára foglalt tárterület összefüggő mezőt alkot.

A megvalósítás azt jelenti, hogy a lefoglalt memóriaterület kezdőcíme és az i1 , \(\dots\) ik indexkifejezések értékéből kell meghatározni egy adott A tömb A[i1]\(\dots\)[ik] elemének a címét. Gyakorlatilag látható, hogy adott indexre ezt egyértelműen meg kell tudni határozni, így újabb műveletként felvehetjük a tömbökhöz a Cím(A[i1]\(\dots\)[ik]) címfüggvényt is. Ami egyértelmű, hogy a Cím függvény felírható t0 + TCF(i1 , \(\dots\) ik) alakban is, ahol t0 az A változóhoz foglalt memóriamező kezdőcíme, a TCF függvény pedig a tömb típus által meghatározott és tömb-címfüggvénynek nevezzük.

Ahhoz, hogy a tömböket hatékonyan tudjuk kezelni, ennek a TCF függvénynek egyszerűnek, gyorsan számolhatónak kell lennie az t0 + TCF(i1, \(\dots\) ik) értékek függvényében. Egydimenziós esetben adja magát a képlet, ha tudjuk, hogy egy tömbelem mérete c, akkor az i. elem kezdőcíme i*c távolságra lesz a tömb kezdőcímétől (itt kihasználjuk azt is, hogy a tömbök indexelése 0-tól kezdődik).

Ha ezt általánosítani szeretnénk tetszőleges dimenzióra, könnyen megtehetjük, ha ismerjük a tömb paramétereit. Tegyük fel, hogy adott egy E T[N1]\(\dots\)T[Nk]; tömb deklarációnk. Mivel feltehetjük, hogy ez is egy egy dimenziós tömb, amely minden eleme egy tömb, melynek típusa E T[N2]\(\dots\)T[Nk], így felhasználva az előbbi egy dimenziós megoldást kapjuk, hogy T[i1] offszetje (azaz tömbön belüli címe) i1 \(\cdot\)c1, ahol c1 = sizeof(E T[N2]\(\dots\)T[Nk]).

Ennek mintájára már adott T[i1] [i2] offszetje is, ami i1 \(\cdot\)c1 + i2\(\cdot\)sizeof(E T[N3]\(\dots\)T[Nk]).

Általánosan tehát T[i1]\(\dots\) [ik] offszetje i1 \(\cdot\)c1 + \(\dots\) + ik \(\cdot\)ck, ahol \(\forall\) i-re, amire 1 \(\leq\) i < k, arra ci = sizeof(E[N\(_{i+1}\)] \(\dots\)[Nk]) és ck = sizeof(E).

Ha a tömbméretet konstansként adtuk meg, akkor a c1, \(\dots\), ck konstansok fordítási időben kiszámíthatóak. Éppen ezért az eredeti C standard nem is engedi a statikus tömböket csak úgy deklarálni, ha a méretük ismert fordítási időben. Ha a tömbünk méretét változóval adtuk meg, akkor a c\(_1\), \(\dots\), c\(_k\) konstansok kiszámítása futásidőben történik.

Ez tulajdonképpen a tömbelemek index szerinti lexikografikus rendezését adja meg, azaz ha (i1, \(\dots\), ik) \(<_{lex}\) (j1, \(\dots\), jk) akkor és csak akkor teljesül, ha a legkisebb u indexre, amire iu \(\neq\) ju, ott iu < ju.

Kétdimenziós esetben (E T\([\)N\(]\)\([\)M\(]\)) például a lexikografikus rendezés az alábbiak szerint működik. A memóriában a tömb elemek egymás után (egy dimenzióban) kapnak helyet:


Míg logikailag egy 2 dimenziós táblázatot alkotnak:


Nagyon fontos újra és újra kihangsúlyozni, hogy a tömbök használata nagy körültekintést igényel, hiszen a C program végrehajtása közben nincs indexhatár-ellenőrzés. Ha adott egy double m[10][10]; deklaráció, akkor az m[0][10] és az m[1][0] hivatkozások megegyeznek, ráadásul a C mind a kettőt el is fogadja. Ez néha persze jó is, mert így lehetőség van arra, hogy tetszőleges dimenziós tömböt akár egy dimenziósként végigjárjunk, ha a művelet, amit végzünk a tömbelemeken független azok dimenziójától (pl. ilyen lehet az inicializálás, vagy ha egyszerűen össze akarom adni az letárolt értékeket, ...)

Az alábbi kódrészletben a két dimenziós tömböt egyetlen ciklussal inicializáljuk, viszont a kiíratásnál fontos a dimenzió, hiszen szeretnénk, ha megfelelő táblázat alakban látnánk a tömböt:

int i, j, a[3][3];
for (i = 0; i < 9; ++i)
    a[0][i] = i;
for (i = 0; i < 3; ++i) {
    for(j = 0; j < 3; ++j)
        printf("%d ", a[i][j]);
    printf("\n");
}

Kimenet

0 1 2
3 4 5
6 7 8

Tömb, mint paraméter

Egy függvény paramétere lehet tömb típusú is. Ilyen esetben azonban nem történik teljes értékmásolás, hanem csak a tömb címe (vagyis egy pointer) kerül átadásra, így a tömb elemein végzett bármely módosítás az eredeti tömbön kerül végrehajtásra. Mivel C-ben nincs indexhatár-ellenőrzés, és a paraméterként átadott tömbnek csak a címét kapja meg a függvény, ezért ha a függvény T paramétertípusa E típusú elemekből álló egydimenziós tömb, ennek a pontos méretét a függvény deklarációjában nem kell megadni.

AzE típus méretét viszont pontosan ismerni kell, tehát ha a T többdimenziós tömb típus, azaz E is legalább egydimenziós tömb típus, akkor E minden dimenziójának a méretét pontosan fel kell tüntetni, azaz csak T legelső dimenziójának mérete hagyható el. Például:

bool ciklikus(int n, int A[]);
int fgv(int tomb[][10][3]);