A tömb egy olyan változó, amely több azonos típusú adatot tartalmaz. A tömb (futásidei) hossza a létrehozásakor kerül megállapításra, és attól kezdve a tömb egy állandó méretű adatszerkezet.
A tömb egy eleme egyike a tömbben található tagoknak, mely a tömbben elfoglalt helye (indexe) alapján érhető el.
Ha különböző típusú adatokat akarunk tárolni egy szerkezeten belül, vagy olyan szerkezetre van szükség, melynek mérete dinamikusan módosítható, akkor használjunk a tömb helyett olyan gyűjtemény implementációkat, mint az ArrayList.
Fontos megjegyezni, hogy a tömbök objektumok, eltérően a C nyelvtől. Ez sok mindenben befolyásolja a működését.
10.1. Tömbök létrehozása és használata
Következzen az ArrayDemo nevű program, mely létrehoz egy tömböt, adatokkal tölti fel, majd kiírja tartalmát:
public class ArrayDemo {
public static void main(String[] args) {
int[] anArray;
anArray = new int[10];
for (int i = 0; i < anArray.length; i++) {
anArray[i] = i;
System.out.print(anArray[i] + " ");
}
System.out.println();
}
}
A program kimenete:
0 1 2 3 4 5 6 7 8 9
Tömbök deklarálása
Ez a sor egy példaprogramból való, és egy tömb típusú változót deklarál:
int[] anArray;
Mint minden másfajta változó deklarálásakor, a tömb deklarálása is két részből áll: a tömb típusa és a tömb neve. A tömb típusa a tömb[] formátumban írható, ahol a típus a tömb által tartalmazott elemek típusa, a [] pedig azt jelzi, hogy tömbről van szó. A tömb minden eleme azonos típusú! A fenti példa int[] tömböt használ, tehát az anArray nevű tömb int típusú egészek tárolására lesz alkalmas. Néhány más típust tárolni képes tömb létrehozása:
float[] anArrayOfFloats;
boolean[] anArrayOfBooleans;
Object[] anArrayOfObjects;
String[] anArrayOfStrings;
Így is írható a deklaráció:
float anArrayOfFloats[];
Ez a forma nem ajánlott, mert a zárójelek jelzik, hogy tömbről van szó, így azok a típussal tartoznak össze, nem pedig a tömb nevével.
A tömb változók deklarálásával – mint bármely más nem primitív változóéval – sem jön létre tényleges tömb, és nem foglal le helyet a memóriában az elemek számára. A példakódban explicit módon kell létrehozni a tömböt és elnevezni anArray-nek.
Tömbök létrehozása
Tömb létrehozható explicit módon a Java new operátora segítségével. A példaprogram következő részében 10 egész tárolására szolgáló tömbhöz elegendő memóriát foglalunk le, és elnevezzük a már korábban deklarált anArray-nek.
anArray = new int[10];
Általában tömb létrehozásakor használni kell a new operátort, majd a tömb elemeinek típusát és végül a tömb méretét kell megadni szögletes zárójelek között:
new elemtípus[tömbméret];
Ha a new operátort kihagytuk volna a példaprogramból, a fordító leállt volna következő hibaüzenettel:
ArrayDemo.java:4: Variable anArray may not have been initialized.
Tömb kezdőérték beállítása
Használható a tömbök létrehozására és inicializálására a következő rövid formula:
boolean[] answers = {true, false, true, true, false};
Ilyekor a tömb nagyságát a {} közé írt elemek száma határozza meg.
Tömbelemek elérése
Most, hogy már megtörtént a memóriafoglalás a tömb számára, a program értékeket rendel a tömb elemeihez.
for (int i = 0; i < anArray.length; i++) {
anArray[i] = i;
System.out.print(anArray[i] + " ");
}
A kód ezen része azt mutatja be, hogy ahhoz, hogy hivatkozni tudjuk a tömb bármely elemére beírás vagy kiolvasás céljából, a tömb nevéhez egy []-et kell írni. A zárójelben (változó vagy egyéb kifejezés segítségével) írt érték az elérni kívánt tömbelem indexét jelöli.
Megjegyzés: A tömb (mivel objektum), tudja, hogy mekkora a mérete, és milyen index használható az indexelés során. Érvénytelen index esetén (a C nyelvvel szemben) a hiba futás közben egyértelműen kiderül: a futtatókörnyezetet egy ArrayIndexOutOfBoundsExeption típusú kivételt dob.
Tömb méretének meghatározása
A tömb méretének meghatározásához használható:
Tömbnév.length;
Figyelem! Azok, akiknek új a Java programnyelv, gyakran üres zárójelet raknak a length után. Ez nem működik, mert a length nem metódus! A length egy csak olvasható adattag, melyet a Java platform nyújt minden tömb számára.
A for ciklus a programunkban bejárja az anArray minden elemét, értéket adva nekik. A ciklus anArray.length–et használ a ciklus végének megállapításához.
10.2. Objektum tömbök
A tömbök tárolhatnak referencia típusú elemeket a primitív típusokhoz hasonlóan. Ezeket a tömböket is nagyrészt ugyanúgy kell létrehozni, mint a primitív típust tárolókat. A következő ArrayOfStringsDemo nevű program három String objektumot tárol, és kiírja őket kisbetűsítve.
public class ArrayOfStringsDemo {
public static void main(String[] args) {
String[] anArray = { "String One",
"String Two",
"String Three" };
for (int i = 0; i < anArray.length; i++) {
System.out.println(anArray[i].toLowerCase());
}
}
}
A program kimenete:
string one
string two
string three
A JDK 5.0–ás és későbbi verziói esetén lehetőség van a tömb elemeinek bejárásához egy újabb szintaktika alkalmazására. Ezt – más nyelvekben használt nevük alapján – for-each ciklusnak is szokás hívni. Figyelni kell azonban arra, hogy a ciklust ugyanúgy a for kulcsszó vezeti be, mint a hagyományos for ciklust.
String[] anArray = {"String One","String Two","String Three"};
for (String s : anArray) {
System.out.println(s.toLowerCase());
}
A következő ArrayOfIntegersDemo nevű program feltölti a tömböt Integer objektumokkal.
public class ArrayOfIntegersDemo {
public static void main(String[] args) {
Integer[] anArray = new Integer[10];
for (int i = 0; i < anArray.length; i++) {
anArray[i] = new Integer(i);
System.out.println(anArray[i]);
}
}
}
A program kimenete:
0
1
2
3
4
A következő programrészlet létrehoz egy tömböt, de nem rak bele semmit:
Integer[] anArray = new Integer[5];
Ez egy potenciális hibázási lehetőség, melyet az újdonsült Java programozók gyakran elkövetnek, amikor objektum tömböket használnak. Miután a fenti kódsor végrehajtódik, a tömb létrejött és képes 5 Integer objektum tárolására, bár a tömbnek még nincs eleme. Üres. A programnak explicit módon létre kell hoznia az objektumokat, és belerakni a tömbbe. Ez nyilvánvalónak tűnik, habár sok kezdő azt gondolja, fenti kódrészlet létrehozza az üres tömböt és még 5 üres objektumot is a tömbbe. Ha a tömbelemek létrehozása nélkül próbálunk azokra hivatkozni, akkor a futtatókörnyezetet NullPointerException-t fog dobni.
A probléma előfordulása még veszélyesebb, ha a tömb létrehozása a konstruktorban, vagy más kezdőérték állítással történik, és máshol használjuk a programban.
10.3. Tömbök tömbjei
Tömbök tartalmazhatnak tömböket. A következő példaprogram létrehoz egy tömböt, és kezdeti értékadásnál négy másodlagos tömböt, használ:
public class ArrayOfArraysDemo {
public static void main(String[] args) {
String[][] cartoons =
{
{ "Flintstones", "Fred", "Wilma", "Pebbles", "Dino" },
{ "Rubbles", "Barney", "Betty", "Bam Bam" },
{ "Jetsons", "George", "Jane", "Elroy", "Judy", "Rosie", "Astro" },
{ "Scooby Doo Gang", "Scooby Doo", "Shaggy", "Velma", "Fred", "Daphne" }
};
for (int i = 0; i < cartoons.length; i++) {
System.out.print(cartoons[i][0] + ": ");
for (int j = 1; j < cartoons[i].length; j++) {
System.out.print(cartoons[i][j] + " ");
}
System.out.println();
}
}
}
A program kimenetele:
Flintstones: Fred Wilma Pebbles Dino
Rubbles: Barney Betty Bam Bam
Jetsons: George Jane Elroy Judy Rosie Astro
Scooby Doo Gang: Scooby Doo Shaggy Velma Fred Daphne
Vegyük észre, hogy mindegyik másodlagos tömb különböző hosszúságú. A melléktömbök nevei cartoons[0], cartoons[1], és így tovább.
Mint az objektumok tömbjeinél, létre kell hoznunk a másodlagos tömböket a tömbön belül. Ha nem használunk kezdeti paraméterinicializálást, akkor a következőhöz hasonló kódot kell írnunk:
public class ArrayOfArraysDemo2 {
public static void main(String[] args) {
int[][] aMatrix = new int[4][];
for (int i = 0; i < aMatrix.length; i++) {
aMatrix[i] = new int[5];
for (int j = 0; j < aMatrix[i].length; j++) {
aMatrix[i][j] = i + j;
}
}
for (int i = 0; i < aMatrix.length; i++) {
for (int j = 0; j < aMatrix[i].length; j++) {
System.out.print(aMatrix[i][j] + " ");
}
System.out.println();
}
}
}
A program kimenetele:
0 1 2 3 4
1 2 3 4 5
2 3 4 5 6
3 4 5 6 7
Meg kell adni a tömb hosszúságát, amikor létrehozzuk. Tehát egy tömbnek, ami tartalmaz másodlagos tömböket, meg kell adni a hosszúságát, amikor létrehozzuk, de nem kell megadni a másodlagos tömbök hosszúságát is.
10.4. Tömbök másolása
Használhatjuk a System osztály arraycopy metódust, hogy adatokat másoljunk hatékonyan egyik tömbből a másikba. Az arraycopy metódus öt paramétert vár:
public static void arraycopy(Object source, int srcIndex, Object dest, int destIndex, int length)
A két Object paraméter rámutat a kiinduló és a cél tömbre. A három int paraméter jelzi a kezdő helyet a forrás és a céltömbön belül, és az elemek számát, amennyit másolni akarunk.
A következő kép illusztrálja, hogyan megy végbe a másolás:
Tömb másolása
A következő ArrayCopyDemo program használja az arraycopy metódust, ami az elemeket a copyFrom tömbből a copyTo tömbbe másolja.
public class ArrayCopyDemo {
public static void main(String[] args) {
char[] copyFrom = { 'd', 'e', 'c', 'a', 'f', 'f', 'e', 'i', 'n', 'a', 't', 'e', 'd' };
char[] copyTo = new char[7];
System.arraycopy(copyFrom, 2, copyTo, 0, 7);
System.out.println(new String(copyTo));
}
}
A program kimenetele:
caffein
A következő képen lehet látni az arraycopy metódus működését:
arraycopy
Az eredménytömböt létre kell hozni, mielőtt meghívódik az arraycopy metódus, és elég nagyméretűnek kell lennie, hogy beleférjenek a másolandó tömb elemei.
Többdimenziós tömbök
Sok feladat megoldásához az egydimenziós tömb struktúra már nem elegendő, vagy túl bonyolulttá tenné a kezelést. Ha például gyűjteni szeretnénk havonként és azon belül naponként a kiadásainkat. A kiadások számok, de a napokhoz rendelt indexek nehézkesek lennének, mert február 1-hez a 32-t, június 1-hez már a 152-es index tartozna. Egyszerűbb, ha a kiadásainkat két indexel azonosítjuk. Az egyik jelentheti a hónapot, a másik a napot. Ha már az évet is szeretnénk tárolni, akkor egy újabb index bevezetésére van szükségünk.
Nézzük meg egy egyszerű példán keresztül a deklarációt. Töltsünk fel egy 3x3 mátrixot véletlen számokkal és írassuk ki őket mátrix fromában a képernyőre.
static void Main(string[] args)
{
int[,] tm = new int[3,3];
int i, j ;
Random rnd = new Random();
for (i = 0; i < 3; i++)
{
for (j = 0; j < 3; j++)
{
tm[i,j] = rnd.Next(10,20);
Console.Write("{0} ",tm[i,j]);
}
Console.WriteLine();
}
Console.ReadLine();
}
Látható, hogy a deklarációkor a két indexet úgy jelezzük, hogy egy vesszőt teszünk a zárójelbe, majd a példányosításkor megadjuk az egyes indexekhez tartozó elemszámot.
A kétdimenziós tömböt feltölteni elemekkel, illetve kiíratni azokat elég két ciklus, ahol az egyik ciklusváltozó az egyik indextartományt futja végig, míg a másik ciklusváltozó a másik tartományt. Ha nem két, hanem többdimenziós tömböt használunk, akkor a ciklusok számma ennek megfelelúően fog nőni.
A példában látható, hogy a mátrix forma megtartás érdekében egyszerűen a sorok elemeit egymás mellé Write utasítás alkalmazásával írattuk ki. A belső ciklus minden sor kiírásáért felelős, így a sorok végén a soremelésről gondoskodtunk a WriteLine utasítással, melynek nem volt paramétere.
A kétdimenziós tömböt feltölthetjük kezdőértékkel, hasonlóan az egydimenziós esethez:
int[,] tm2 = new int[2,2] {{1,2},{3,4}};
Tekintsük a következő feladatot:
Töltsünk fel egy 3x3 mátrixot a billentyűzetről egész számokkal. Írassuk ki a szokásos formátumban, majd generáljuk a transzponáltját, és ezt is írassuk ki.
A szükséges tömb és ciklusváltozók deklarálása:
int[,] tm = new int[4,4];
int i, j ;
Töltsük fel a mátrixot billentyűzetről egész számokkal:
for (i = 0; i < 3; i++)
for (j = 0; j < 3; j++)
{
Console.Write("Kérem a {0}. sor {1}. oszlop elemét: ",i,j);
tm[i,j] = int.Parse(Console.ReadLine());
}
Írassuk ki a tömb elemeit mátrix formában:
Console.WriteLine("Az eredeti mátrix: ");
for (i = 0; i < 3; i++)
{
for (j = 0; j < 3; j++)
Console.Write("{0} ",tm[i,j]);
Console.WriteLine();
}
Ez futás közben így néz ki:
Deklaráljunk egy tr tömböt a transzponált mátrix elemeinek. Majd generáljuk le az eredeti tm tömbből. A transzponált mátrixot az eredeti mátrix sorainak és oszlopainak felcserélésével kapjuk.
int[,] tr = new int[3,3];
for (i = 0; i < 3; i++)
for (j = 0; j < 3; j++)
tr[i,j] = tm[j,i];
Újra ki kell íratni egy tömböt, most a transzponált mátrixot.
for (i = 0; i < 3; i++)
{
for (j = 0; j < 3; j++)
Console.Write("{0} ",tr[i,j]);
Console.WriteLine();
}
A program futtatását bemutató képernyő:
Vegyük észre, hogy a két kiíratásban csak a tömb neve a különböző. Feleslegesen írjuk le kétszer ugyanazt a kódot. Erre jobb megoldást ad az eljárásokról és függvényekről szóló fejezet.
A tömb egy olyan változó, amely több azonos típusú adatot tartalmaz. A tömb hossza a létrehozáskor dől el, és attól kezdve a tömb egy állandó méretű adatszerkezet.
A tömböket egy fiókos szekrényhez lehetne hasonlítani, amelyekben az egyes fiókokban egy-egy adatot helyezünk el. A fiókokra a sorszámukkal (A tömbben elfoglalt helye.) hivatkozunk. A sorszámozást nullával kezdjük! Ha valamelyik fiók tartalmára szükségünk van, akkor megadjuk, hogy hányadik fiókról van szó és kiolvassuk a tartalmát.
Példa: (Ha szükségünk van a 100-as számra, akkor a 3-as indexű fiókot kell "kihúzni"!)
0 1 2 3 4 5 6 7 8 9
10 2 34 100 1 0 5 67 76 99
Lehetőségünk van arra is, hogy olyan tömböket hozzunk létre, amelyek tömböket tartalmaznak (tömbök tömbjei).
8.1. Tömbök deklarálása, kezdőértékük beállítása
A tömb deklarálása a többi váltózóéhoz hasonlóan két részből áll: meg kell adni a tömb típusát és a tömb nevét.
Szintaktika:
<elemtípus>[] <tömbAzonosító>; pl. int[] szamok;
A [] tömbképző operátort a tömbAzonosító után is tehetjük.
<elemtípus> <tömbAzonosító>[]; pl. int szamok[];
A deklarálás során nem hoztuk még létre a tömböt, egyelőre csak a referenciának (memóriacímnek) foglaltunk helyet. A tömböt a Javában külön létre kell hozzuk a new operátorral!
Szintaktika:
new elemtípus[<méret>];
pl. new int [10];//Itt egy olyan integer típusú adatelemeket tartalmazó tömböt hoztunk létre, amely 10 db elemet tartalmaz.
A deklarációt és a létrehozást egy lépésben is elvégezhetjük.
Például:
int szamok[] = new int[10] ;
A deklarálás során (inicializáló blokkal) a tömb elemeinek kezdeti értékek is adhatók.
Szintaktika:
<elemtípus>[] <tömbAzonosító> = {<érték0>, <érték1>, ...};
pl. Készítsünk egy String típusú tömböt, amely a hét napjait tartalmazza!
String[] napok = {"Hétfő","Kedd","Szerda","Csütörtök","Péntek","Szombat", "Vasárnap"};
8.2. Tömbelemek elérése
A tömb egyes elemeire az indexükkel hivatkozhatunk.
Szintaktika:
<tömbAzonosító>[index];
pl. szamok[3] = 2; // A 4. fiókba (3-as indexű) betettük a 2-es számot.
8.3 Tömb méretének meghatározása
Minden tömb objektumnak van egy length konstansa, amely megadja a tömb hosszát.
(Egyszerűen azt, hogy hány adat található meg benne?)
tömbAzonosító.length
pl. (A napok tömbnél, amely a hét napjait tartalmazza.)
System.out.println(napok.length); >> 7
8.4. Objektumtömbök
A tömbökben tárolhatunk referencia típusú elemeket is. A létrehozásuk olyan mint a primitív típusú elemeket tartalmazó tömböké.
Nézzünk meg egy egyszerű példát, ahol a tömbben három String objektumot tárolunk:
A tömb elemeinek a bejárásához használhatunk egy speciális programozói eszközt, az un. for-each ciklust.
Szintaktika:
for(<típus> <változó> : <objektum>)
<utasítás vagy blokk>
Példa:
8.5. Tömbök tömbjei
A tömbök tartalmazhatnak tömböket, tetszőleges mélységben egymásba ágyazva.
Szintaktika:
Deklarálás: <elemtípus>[][] ... [] <tömbAzonosító>;
Létrehozás: new <elemtípus> [méret0][méret1]...[méretn-1];
Tömb elemeinek elérése: <tömbAzonosító> [index0][index1]...[indexn-1]
Példa: (Egy tömbben elhelyezünk másik 3 tömböt.)
Az egyszerű adattípusok ismertetését a tömbökkel kezdjük. Az sem okozna zavart, ha ezt a fejezet nem szerepelne jegyzetünkben, tekintettel arra, hogy a tömböket ismerjük a programozási kurzusokból. Mégis, célszerű néhány jellemző megállapítást tenni ezzel az alapvető struktúrával kapcsolatban.
A tömbök legfontosabb tulajdonsága az, hogy elemei – indexeléssel – közvetlenül elérhetők. Ezt ADT szintű tulajdonságnak tekinthetjük.
A tömbről ADS szinten „tömbszerű” képünk van, de az elemek rákövetkezősége alapján irányított gráfként is felfoghatunk egy tömböt. Ez az absztrakció a láncolt ábrázolás felé mutat.
Az megvalósítás során, az ADS szinttel összhangban, ritkán választjuk a tömb láncolt ábrázolását (ahogyan- fordítva – a listák esetében sem gyakori a tömbös megvalósítás).
A tömbökről nem könnyű megmondani a felhasználás egy körében vagy konkrét esetében, hogy saját műveletekkel rendelkező önálló típusnak, vagy csupán a reprezentáció adatszerkezetének tekinthetők.
A tömbök dimenziószámmal rendelkeznek; a vektor egydimenziós, míg a mátrix kétdimenziós ismert struktúra; de magasabb dimenziós tömbök használata sem ritka. A tömb erősen szemléletes fogalom; három dimenzióig könnyű elképzelni, lerajzolni a szerkezetüket.
Ma már egy többdimenziós tömb, például egy mátrix nem juttatja eszünkbe, hogy a további lépésként egydimenziós tömbbel kellene reprezentálni. Ez annak köszönhető, hogy a programozási nyelvek elemi lehetőségként kínálják a többdimenziós tömbök használatát. Érdemes azonban tudatosítani, hogy többdimenziós tömbök a számítógép memóriában egydimenziósként ábrázolódnak.
Speciális több dimenziós tömbök (például alsóháromszög-mátrix) helytakarékos egydimenziós ábrázolásáról olyakor magunk gondoskodunk.
Ezeket a gondolatokat valamivel részletesebben is kifejtjük a következő pontokban.
3.1. A tömb absztrakt adattípus
Legyen T az E alaptípus feletti k(≥1) dimenziós tömb típus. Vezessük be az
indexhalmazt, ahol Ij=[1..nj] .
(Megjegyezzük, hogy az indexelés 1 helyett kezdődhetne általában mj-vel is, de az egyszerűség kedvéért 1-et fogunk használni.)
Az A T tömbnek így n= elemet tárol, amelyek halmazát jelöli. A T tömbhöz tartozik, mint a típus meghatározó komponense, egy indexfüggvény, amely kölcsönösen egyértelmű leképezést létesít az indexhalmaz és a elemek halmazbeli indexei között, ezáltal egyértelmű leképzést valósít meg az indexhalmaz és a tömb elemei között. A tömbelemek egyértelműen és közvetlenül elérhetővé válnak az indexfüggvény alkalmazásával.
Bevezetjük az A[1..n1,1..n2,...,1..nk] jelölést az A tömbre, amely magában foglalja az indexhalmazát és utal arra, hogy az indexkifejezések és a tömbelemek közötti kapcsolat is adott, így annak alapján az elemekre – indexeléssel – lehet közvetlenül hivatkozni.
Bevezetjük az A jelölést a tömbelemek indexelésére. Ha a fenti indexfüggvény szerint f() = j, akkor ez az indexelés az ajelemet választja ki
A =aj
Az indexelés mechanizmusát (absztrakt megközelítésben) a 3.1. ábra szemlélteti.
A kép (nagyobb változata) külön ablakban is megtekinthető.
3.1. ábra. Tömb absztrakt adattípus
A tömb műveleteinek köre szerény: a most bevezetett indexeléssel lekérdezhetjük a tömb elemeit, emellett módosíthatjuk is azokat. A tömb a mérete nem változik; nem lehet a tömbbe egy új elemet beszúrni, és nem lehet a tömbből egy elemet kitörölni.
A szokás elnevezések szerint k=1 esetén a vektorról, k=2 esetén a mátrixról beszélünk.
Vissza a tartalomjegyzékhez
3.2. A tömb absztrakt adatszerkezet
A tömböktől elválaszthatatlan a szerkezetükről alkotott kép, amely jórészt a matematikai tanulmányaink során alakult ki. Ezen a kép alapján például egy cellákból álló lineáris vagy „négyzethálós” sémában helyezzük el (az egy, illetve kétdimenziós) tömb elemeit. A 3.2. ábrán egy mátrix szokásos ábrája látható.
A kép (nagyobb változata) külön ablakban is megtekinthető.
3.2. ábra. Tömb szemléletes képe (ADS)
Az absztrakt adatszerkezet bevezetésével a fenti f indexfüggvény a háttérbe húzódik, hiszen azt lehet mondani például a fenti kétdimenziós tömb esetén, hogy mondjuk az A[2,3]=40 elem a 2. sor 3. eleme, vagyis az indexkifejezést vizuálisan megjelenítettük az ADS szintű sémával.
Szemléletünk számára tehát a vektor egy beosztásokkal ellátott szalag, a 2-dimenziós tömb egy mátrix, a 3-dimenziós tömb egy cellákra osztott téglatest alakját ölti gondolatainkban.
Az előző, bevezető jellegű 2. fejezet szerint, az absztrakt adatszerkezetet általában egy olyan irányított gráf szemlélteti, amelyben az élek az adatelemek közötti rákövetkezéseket jelenítik meg. Egy k-dimenziós tömb elemeinek általában, a dimenziók határát kivéve, k számú rákövetkezőjük van. Formálisan is bevezethetjük a j szerinti rákövetkezés fogalmát:
kövjA[]=A[]()
A 3.3. ábra egy kétdimenziós tömb, az A[1..3,1..4] mátrix absztrakt gráfszerkezetét mutatja. Ez egy olyan ortogonális struktúra, amelyben minden csúcsból két él vezet a tömbbeli rákövetkezőkhöz.
A kép (nagyobb változata) külön ablakban is megtekinthető.
3.3. ábra. Tömb gráfja (ADS)
Valójában a tömbről nem ilyen képet őrzünk fejünkben, ahogyan a verem sem egy lineáris gráf formájában rögzül a memóriánkban. Annyiban azonban mégsem fölösleges a gráfos szemlélet, mert közelebb hozza a ritka mátrixok láncolt ábrázolásának ötletét.
Vissza a tartalomjegyzékhez
3.3. A tömb megvalósításai
Ebben a pontban két ritkán felmerülő kérdést érintünk. Az egyik a többdimenziós tömbök egydimenziós ábrázolására vonatkozik. A magasszintű programnyelvek elfedik előlünk ennek szükségességét, azonban hasznos lehet megismerni a fordítóprogramokba épített tárolási elvet. A másik kérdés a nagyméretű, de kevés adatot tartalmazó tömbök helytakarékos tárolására vonatkozik. Bemutatjuk a ritka kitöltöttségű mátrixok láncolt ábrázolásának módszerét.
3.3.1. Aritmetikai reprezentáció
Egy adatszerkezet aritmetikai ábrázolása során az adatelemeket egy tömbben helyezzük el, az eredeti strukturális összefüggéseket pedig függvények formájában adjuk meg.
Az adatokat tároló tömb lehet egy- vagy többdimenziós. Szemléletünk számára egy többdimenziós tömb már annyira egyszerű adatszerkezet, hogy nem szükséges mindig újra meggondolni az egydimenziós elhelyezés lehetőségét. A programnyelvek is megerősítenek ebben, hiszen a többdimenziós tömbök használatát az alapvető lehetőségek között nyújtják.
A tömb adattípus ismertetésekor azonban, legalább ezen a helyen egyszer, érdemes szóba hozni azt, hogy a többdimenziós tömbök elemeit még el kell helyezni a szalagszerű egydimenziós memóriában.
A szekvenciális tárolást általában a sorfolytonos vagy oszlopfolytonos módszerrel szokás megoldani. (Azzal még itt sem foglalkozunk, hogy a tárolás végállomása egy bájtokból álló vektor, és a bájtokat – még tovább finomítva – bitek sorozata alkotja.)
A 3.4. ábrán a korábban is szereplő mátrixnak az egydimenziós tárolást illusztrálja, mindkét elhelyezési stratégia szerint.
A kép (nagyobb változata) külön ablakban is megtekinthető.
3.4. ábra. Kétdimenziós tömb egydimenziós tárolása
A kapcsolatot az elemek mátrixban elfoglalt pozíciója és az új helye között index-függvényekkel adjuk meg. Egy kétdimenziós tömbre, például a sorfolytonos esetben ez a következő:
ahol és . Esetünkben például, ha az elemet keressük a sorfolytonosan kialakított B tömbben, akkor azt a (2 - 1)4 + 3 = 7 indexű helyen találjuk: B[7] = 40.
Ezzel a kérdéssel a további fejezetekben nem foglalkozunk. Ezután már egy többdimenziós tömböt is az ábrázolás eszközének tekintünk.
3.3.2. Láncolt ábrázolás
Bizonyos (jobbára gazdasági) problémák modellezése nagyméretű mátrixok alkalmazásához vezet. Előfordul azonban, hogy a mátrix csekély értékes adatot tárol. Ilyenkor gondolhatunk arra a reprezentálási módra, amelyet a 3.5. ábrán láthatunk.
A ritka mátrixok láncolt ábrázolásában csak az értékes elemek szerepelnek. Alkalmazhatunk egyirányú láncolást, amelyben minden elemtől a sor- és oszlopbeli rákövetkezőjéhez irányít a két tárolt pointer. A sorok és az oszlopok „bejárataira”, pontosabban az első bennük szereplő elemre, egy-egy fejelem mutat, amelyek maguk is egy-egy listát alkotnak. A két fejelem lista egy közös fejelemből érhető el.
A kép (nagyobb változata) külön ablakban is megtekinthető.
3.5. ábra. Ritka mátrix láncolt ábrázolása
Az ábra nem csak a helytakarékosság lehetőségét érzékelteti, hanem azt is, hogy ezzel az ábrázolási móddal feladtuk az elemek közvetlen indexelhetőségét és csak meglehetős nehézkességgel tudunk eljutni az elemekhez.
Az elemek elérését, illetve a struktúrában való mozgást valamelyest javítja, ha kétirányú láncolást alkalmazunk, mind a sorokban és az oszlopokban, mind pedig a két fejelem-listában.
Azt a kérdést, hogy alkalmazzuk-e adott esetben ezt a tárolási formát, két szempont dönti el. Egyik a helytakarékosság kérdése: az értékes mátrixelemek (várható) számának és méretének ismerete esetén könnyen kiszámítható, hogy előnyösebb-e ez az ábrázolás, mint a hagyományos. Ehhez csak a pointerek számát kell meghatározni, amelyet a memóriacím helyfoglalásával (ami általában 2 vagy 4 bájt) szorozva kell a memóriaigény számításában figyelembe venni.
A másik mérlegelendő szempont az, hogy mennyire támogatják a feldolgozó eljárások megvalósíthatóságát a láncolt adatszerkezeten való közlekedés korlátozott lehetőségei. A mai memóriakapacitások mellett lehet, hogy ez a súlyosabb szempont. Ha arra gondolunk például, hogy hogyan kellene két ritka mátrix összegét előállítani, akkor látható, hogy a láncolt ábrázolás mellett a legegyszerűbb feladat megoldása is körülményessé válhat.
Vissza a tartalomjegyzékhez
3.4. Speciális tömbök
A tömbök egydimenziós ábrázolásával azért sem fölösleges megismerkedni, mert találkozhatunk olyan adatszerkezetekkel, amelyeknél azt magunk valósítjuk meg. Ezek az adatszerkezetek általában olyan mátrixok, amelyeknek jelentősen kisebb helyen is tárolhatók, például azért, mert az elemek jó része hiányzik, és a hiány, ezzel együtt értékes rész is szabályos tartományt képez.
A kép (nagyobb változata) külön ablakban is megtekinthető.
3.6. ábra. Alsó-háromszögmátrix sorfolytonos ábrázolása
A 3.6. ábrán látható alsóháromszög-mátrixban a főátló fölötti elemek hiányoznak. Az értékes elemeket sorfolytonos módon elhelyezve egy egydimenziós tömbbe memória-takarékos tárolást valósítunk meg, hiszen így a helyfoglalás közelítőleg a felére csökken.
Egy -es négyzetes mátrix esetén az alsó háromszög tárolásához szükséges cellák száma: . Megállapodás szerint, az értékes elemek után még egy nullát is elhelyezünk.
Ez az átpakolási stratégia az alábbi index-függvénnyel válik követhetővé:
(A nulla elem tárolása egy általánosabb eljárás következménye. Ha ugyanis a mátrixban lenne néhány olyan elem, amelyek nagyobb számban ismétlődnek egy-egy szabályos tartományban, akkor ezeket rendre elegendő egy-egy példányban tárolni, amennyiben az eredeti előfordulási helyeik egy indexfüggvénybe foglalhatók.)
Nincsenek megjegyzések:
Megjegyzés küldése