Tömb (programozás): definíció, indexelés, típusok és méretezés
Tudj meg mindent a tömbökről: definíció, indexelés, típusok és méretezés programozásban — egyszerű magyarázat, példák és gyakorlati tippek kezdőknek és haladóknak.
A programozási nyelvekben a tömb egy olyan adatszerkezet, amely több, egymást követő elemet tárol. Tipikusan az elemek ugyanannak a típusnak felelnek meg (például csak egész számok, csak karakterláncok stb.), így statikusan típusos nyelvekben egy tömb nem tárolhat különböző típusú elemeket egyazon tömbön belül. Dinamikusan típusos nyelvekben (például Python vagy JavaScript) viszont a beépített listák/array-ek gyakran engednek heterogén értékeket is, ezért fontos különbséget tenni a "tömb" fogalma és a nyelv konkrét implementációja között.
Indexelés és elemek elérése
Minden tömb eleméhez hozzárendelt pozíciót, azaz indexet használunk az adott elem eléréséhez. Egyes nyelvekben az első elem indexe 0 (például C, Java, JavaScript), más rendszerekben az első index 1 (néhány matematikai könyvtár és régebbi nyelvek esetén). Egyes modern nyelvek további kényelmi lehetőségeket is biztosítanak, például Python-ban negatív indexelés a végétől számolva ér el elemeket.
Az indexelés hatása a memóriacímekre: sok nyelv és implementáció a tömböt folyamatos memóriablokként tárolja, ezért egy elem címe kiszámítható a tömb kezdőcíme és az index segítségével (például C-ben: cím = base + index * sizeof(elem)). Ez magyarázza, miért gyors (O(1)) az adott indexű elem elérése a legtöbb környezetben. Ugyanakkor egyes magasabb szintű nyelvek határellenőrzést végeznek (bounds checking), és kilépés vagy kivétel keletkezik, ha az index kívül esik a megengedett tartományon.
Amikor a programozó a szám segítségével tudja az adott elemet előhívni.
Típusok és reprezentációk
- Egydimenziós tömbök: leggyakoribb forma, egyszerű lineáris lista fix vagy dinamikus mérettel.
- Multidimenziós tömbök: mátrixok (2D) és magasabb dimenziós tömbök; implementációként lehetnek valóban tömb-szerű (folytonos) reprezentációk vagy tömbök tömbjeként (pl. Java-ban egy 2D tömb valójában tömbök tömbje).
- Tömb a memóriában: lehet közvetlenül az elemeket tárolni egymás mellett (pl. int tömb C-ben), vagy tárolhat pointereket/ referenciákat, amelyek más helyeken lévő objektumokra mutatnak (pl. objektumokat tartalmazó tömbök Java-ban).
Méretezés: statikus vs. dinamikus tömbök
Amikor a programozó létrehoz egy tömböt, gyakran meg kell adnia a tömb méretét. Ez a méret határozza meg, hogy hány elem tárolható benne. Két alapvető megközelítés:
- Statikus tömbök: a méret létrehozáskor meghatározott és nem változtatható (például C nyelvű tömbök). Ha több elemet szeretnénk tárolni, új tömböt kell létrehozni, és az adatokat át kell másolni az új helyre.
- Dinamikus tömbök/vektorok: magasabb szintű könyvtári konténerek (például C++ std::vector, Java ArrayList) képesek dinamikusan növelni a kapacitást. Ezek általában belső másolással oldják meg a növelést: ha megtelik a belső tömb, egy nagyobbat hoznak létre és átmásolják az elemeket (amortizált O(1) beszúrási költség jellegzetes).
Műveletek és komplexitás
- Elérés (index alapján): általában O(1).
- Iterálás: minden elem megvizsgálása O(n).
- Keresés: rendezett tömb esetén bináris kereséssel O(log n), általános esetben lineáris kereséssel O(n).
- Beszúrás/törlés: ha a közepébe szúrunk vagy onnan törlünk, általában elemek eltolása szükséges O(n); a végére történő beszúrás dinamikus tömbnél amortizált O(1).
Tömbök több dimenzióban
2D vagy többdimenziós tömbök esetén fontos megérteni az elrendezést:
- Sor-major (row-major): sorok egymás után a memóriában (pl. C).
- Oszlop-major (column-major): oszlopok egymás után (pl. Fortran).
- Az elrendezés befolyásolja a cache-hatékonyságot és a hatékony futtatási mintázatot nagy adathalmazoknál.
Tömbök a gyakorlatban — rövid példák
- C: int a[5]; — statikus méretű tömb, az elemek ugyanazon típusúak.
- Java: int[] a = new int[5]; — tipikusan típusbiztos, határellenőrzést végez a JVM.
- Python: a = [1, "kettő", 3.0] — a beépített lista heterogén értékeket is tárolhat.
Tipikus hibák és megfontolások
- Off-by-one hibák: helytelen indexelésnél (pl. i <= n helyett i < n) könnyen futási hibák keletkeznek.
- Kivételek és határellenőrzés: egyes nyelvek kivételt dobnak (IndexOutOfBounds), míg mások undefined behavior-t eredményezhetnek (C-ben olvasható írás kívül eső indexre).
- Méret és memória: nagy tömbök jelentős memóriát foglalhatnak; ha a méret változhat, érdemes dinamikus konténert vagy más adatszerkezetet választani.
Összefoglalás
A tömb alapvető és hatékony adatszerkezet, amely egyszerű leképezést biztosít indexek és értékek között. Használatakor figyelembe kell venni a típuskövetelményeket, az indexelés módját, a megvalósítás memóriabeli sajátosságait és azt, hogy szükség van-e statikus vagy dinamikus méretezésre. A megfelelő tömbtípus kiválasztása jelentősen befolyásolja a program teljesítményét és memóriakezelését.
Táblák C-ben
A C programozási nyelvben a tömbök így hozhatók létre:
Ez egy egész számokból álló tömböt hoz létre, amely 5 egész számot képes tárolni. A programozó most egész számokat tárolhat a tömbben a következő módon:
A programozó így használhat egy értéket a tömbben:
Táblák Java-ban
A Java programozási nyelvben a tömbök így hozhatók létre:
Ez egy egész számokból álló tömböt hoz létre, amely 5 egész számot képes tárolni. A programozó most egész számokat tárolhat a tömbben a következő módon:
A programozó így használhat egy értéket a tömbben:
Kérdések és válaszok
K: Mi az a tömb a programozási nyelvekben?
V: A tömb a programozási nyelvekben több azonos típusú elem tárolásának módja.
K: Milyen típusú elemek tárolhatók egy tömbben?
V: Egy tömbben csak azonos típusú elemek, például egész számok vagy karakterláncok tárolhatók.
K: Mi az index egy tömbben?
V: Az index egy szám, amelyet egy tömb minden egyes eleméhez hozzárendelnek, hogy a programozó az adott elemet az adott szám segítségével érhesse el.
K: Hogyan határozzuk meg egy tömb első elemének indexét?
V: Egyes programozási nyelvekben az első elem indexe 0, míg más programozási nyelvekben ez az érték 1.
K: Mit kell megadnia a programozónak egy tömb létrehozásakor?
V: A programozónak meg kell adnia a tömb méretét, azaz a tömbben tárolható elemek számát.
K: Miért nem lehet megváltoztatni egy tömb méretét?
V: A tömb mérete nem változtatható, mert a tömb létrehozásakor kerül beállításra.
K: Mit kell tennie a programozónak, ha több elemet szeretne tárolni, mint amennyit a tömb mérete megenged?
V: Ha a programozó több elemet akar tárolni, mint amennyit a tömb mérete megenged, akkor egy új, nagyobb méretű tömböt kell létrehoznia.
Keres