A InfoWiki wikiből

A lap 2009. november 14., 21:58-kori változata

Vektorok

Magasszintű Programozási Nyelvek I.

Imperatív, procedurális nyelvek alapjai

Hernyák Zoltán

Kezdőlap

Jegyzetek

Tartalomjegyzék

Gyakorlatok

Vizsgatematika

Programok C# nyelven

Vektorok

Gyakori probléma, hogy annyi adattal kell dolgoznunk, hogy kényelmetlen és zavaró lenne minden egyes adatnak saját változót deklarálni. Kényelmesebb lenne egyetlen változót használnunk, amely egy időben több adat tárolását is képes lenne megoldani. Az elv hasonló, mint a szemétkosár. Kényelmesebb összegyűjteni a szemétdarabkáinkat egy konténerbe, mint egyesével kezelni őket.

Ennek feltétele, hogy a sok (több) adat egyforma típusú legyen. A második félévben (OOP) látni fogjuk, hogy ennek gyakorlatilag semmi akadálya nincs, ha adataink alapvetően különböző típusúnak látszanak is, akkor is mindíg megoldható, hogy egyforma típusúnak látszódjanak (típuskompatibilitás).

Ebben a félévben azonban csak azzal az esettel foglalkozunk, amikor az adataink tényleg egyforma típusúak. Például egy adott időszak napi átlaghőmérséklet adatai. Ha az időszak két hónap, akkor körülbelül 60 darab double adattal kell egy időben dolgoznunk.

double a = 1.2;

A fenti kódban létrehoztunk egyetlen double tárolására képes változót. Az alábbi kódban létrehozunk egy 60 double tárolására képes változót:

double[] t;

A fenti t változó típusában (double[]) látszik, hogy itt nem egyetlen double, hanem több double adat összefogását kell elvégeznünk. A tényleges darabszám egyelőre nem látszik.

Összetett adattípusok

A fenti példában szereplő t változó alapvetően különbözik a korábban használt, egyszerű double változóktól. Az alaptípusának neve mögött szereplő két szögletes zárójel a tömb képző típusmódosító operátor jele. Jelenéte arra hívja fel a figyelmet, hogy nem egyetlen double, hanem sok double fog a t változóba kerülni.

Az ilyen típusú változókat, amelyek egy időben több érték tárolására is képesek - összetett típusú változóknak nevezzük. Ez a tulajdonságuk alapvetően megkülönbözteti őket az egyszerű típusoktól, amelybe eső változók egy időben csak egyetlen értéket tartalmazhatnak.

Műveletek

Nem kell persze nagy dolgokra számítani. Az összetett típusú változókkal jellemzően nem lehet műveletet végezni, valójában egy időben mindíg csak egyik elemükkel dolgozunk (egy érték). Ezen egy elemük már elemi típusú értékként viselkedik, tehát rá minden művelet alkalmazható, amit az adott egyszerű típusra megismertünk.

Jellemzés

Összetett adattípusokból is több van, őket különböző jellemzőik különböztetik meg egymástól:

• tárolási kapacitás: ebből alapvetően két fajta van:
  • statikus kapacitás: az ilyen típusok képesek ugyan sok adat tárolására, de ezen adatok számát jó előre meg kell határozni. Az adott változó végig ugyanennyi adatot tárol, sem többet sem kevesebbet. Az adatok darabszámát a változó létrehozásakor rögzíteni kell.
  • dinamikus kapacitás: az ilyen változókban tárolt adatok száma időben változhat. Új adatot tehetünk be, korábban betett adatot később törölhetünk. A változó létrehozásakor esetleg megadható egy kezdeti darabszám, de ettől később bármikor eltérhetünk könnyedén. Előfordul az az eset is, amikor a változó létrehozásakor még nincs is benne egy adat sem (nulla elemszám).

• memóriabeli elhelyezkedés: ez a jellemző azt mutatja, hogy a sok adat a memóriában hogyan helyezkedik el. Ezt a jellemzőt tárolási reprezentációnak is szokták nevezni:
  • folytonos: a tárolt adatok a memória egy összefüggő területén helyezkendnek el, általában szorosan egymás mellett, mögött.
  • szétszórt: a folytonos ellentéte, az egyes elemek egymástól akár nagyobb távolságra is elhelyezkedhetnek, nem jellemzi ezt a távolságot semmi, oda kerülnek, ahol szabad hely volt a memóriában abban a pillanatban.

• típusosság: nem feltétlenül igaz, hogy a sok adat mindíg egyforma típusú, bár az adott összetett típus ezt kötelezővé teheti:
  • homogén: az ilyen összetett adattípus megköveteli, hogy az összes adat egyforma típusú legyen
  • inhomogén: ez esetben nem követelmény, hogy minden adat egyforma típusú legyen

• adathozzáférési stratégia: ez egy bonyolult jellemző. azt mutatja meg, hogy amennyiben szükségünk van valamely, az összetett típusú változónkban tárolt n sorszámú adatra, akkor milyen lépéssorozat kell az érték előkereséséhez
  • direkt hozzáférés: a legjobb, ez esetben az adott adat sorszámának ismeretében az adat azonnal elérhető. Az adatelérés sebessége (ideje) nem az n értékétől függ (egyenletes sebesség)
  • szekvenciális: az n sorszámú adat eléréséhez minden előtte lévő elemet el kell érni (a feldolgozás az első adattal kezdődik, és halad sorban amíg el nem érjük az n sorszámút). Ekkor nyilvánvaló, hogy ha n kicsi, akkor gyorsabban hozzá tudunk férni az értékhez, mint nagyobb n esetekben
  • FIFO: speciálisan a sor (az ékezetek hiánya nem hiba) adatszerkezet jellemzője. Az adatok csakis abban a sorrendben kerülhetnek feldolgozásra, amilyen sorrendben az adatszerkezetbe bekerültek (first in first out)
  • LIFO: speciális a verem adatszerkezet jellemzője. Az adatok csakis fordított sorrendben dolgozhatók fel, mint amilyen sorrendben az adatszerkezetbe bekerültek (last in first out)

Vannak további, nagyon speciális adatelérések, mint az indexelt szekvenciális, a hash, a logaritmikus, stb. A fentiekről azért nem írunk részletesen, mert ez inkább az Algoritmusok és Adatszerkezetek tárgy témája.

Példák

A részletes tárgyalást mellőzve adunk egy listát, amely az egyes (az informatikában előforduló) összetett adatszerkezeteket jellemzi:

• tömb: statikus, homogén, folytonos, direkt
• lista: dinamikus, homogén, folytonos, direkt
• láncolt lista: dinamikus, homogén, szétszórt, szekvenciális
• verem: dinamikus, homogén, folytonos, fifo
• sor: dinamikus, homogén, folytonos, lifo
• rekord: statikus, inhomogén, folytonos, direkt
• fa: dinamikus, homogén, szétszórt, (egyfajta) szekvenciális
• szótár: dinamikus, homogén, folytonos v. szétszórt, hash

Vektorok

A vektorok speciális (egydimenziós) tömbök (igazából a tömb a fenti jellemzőkkel bíró típusok összefoglaló neve). Ezért a vektorok statikus, homogén, folytonos, direkt elérésű összetett adatszerkezetek.

Mivel homogének, létrehozásukkor meg kell adni az alaptípust. Ez szerepel a double[] típusnévben. A [] operátor jelzi, hogy nem egy double-ről beszélünk, hanem több double-ről.

A vektor statikus, vagyis induláskor meg kell adni a méretét. Ez nem szerepel a double[] típusnévben. Ez ugyanis absztrakt típusnév, az összes double alaptípusból álló vektor közös típusneve. Konkrét double vektor esetén konkrét méretet kell adni. Ezt a t változó kezdőértékének beállításakor kell közölni:

double[] t = new double[30];

Ebben az esetben a new operátor a memóriafoglalást jelöli (a konkrét méretű double vektornak konkrét mennyiségű memóriaterületet kell lefoglalni. Ebben a példában ez 30*8=240 byte. Ezt a new operátor az alaptípus helyigényéből (egy double 8 byte), és a méretből (30 darab double) önállóan számolja ki (valójában ezt az értéket a fordítóprogram fordításkor számolja ki, a generált kódban a new mögött már a konkrét 240 érték szerepel, a new-t ugyanis csak a méret érdekli, a felhasználási cél és mód már nem).

Amennyiben a fenti kezdőértékadást nem adjuk ki, a t változó nem képes egyetlen double adat tárolására sem. Az ilyen próbálkozásokat a fordítóprogram még fordításkor kiszúrja, és szintaktikai hibával leáll. Bár a vektor típusú változó deklarációja, és a helyfoglalás elválhat egymástól, de ritkán történik ilyen. Jellemzően a vektor deklarálásakor annak helyfoglalása is megtörténik.

double[] t;
...
t = new double[30];

Vektor feltöltése billentyűzetről

Egy (a példában szereplő) 30 elemű double vektorba 30 különböző double érték tárolható. A vektorok elemei induláskor típusuknak megfelelő nulla kezdőértékkel rendelkeznek. A szám (int, double,...) típusú vektorok ezért induláskor már 0-kal vannak feltöltve. Ettől eltérő értéket elhelyezhetünk a vektor valamely elemében egy értékadó utasítással. Ekkor meg kell mondani, melyik elembe kívánunk értéket írni. Az elemeket sorszámukkal azonosítjuk, a sorszámok 0-tól indulnak.

double[] t = new double[30];
int i = 0;
while (i<30)
{
  Console.Write("Kérek egy számot");
  double x = double.Parse( Console.ReadLine() );
  t[i] = x;
  i++;
}

A vektor valamely elemére hivatkozás során meg kell adni a vektor nevét (t), és a sorszámot (i), a sorszámot a vektor neve mögé írt szögletes zárójelpárba kell elhelyezni. A t[i] olvasata: a t vektor i. eleme, vagy a t vektor i sorszámú eleme.

A fenti esetben a tömbbe a billentyűzetről beírt számokat helyezzük el. Figyeljük meg, hogy a sorszámok tárolására, kezelésére az i változót használjuk. A sorszámok mindíg egész számok, egész a sorszámozást végző változónk mindíg int (vagy valamelyik testvére). A vektor első elemének sorszáma 0, ezért az i változónkba ezt az értéket helyezzük el induláskor. Az első bekért szám a t[0] pozícióra kerül. Az i++ miatt a sorszámunk lép egyet, és a következő bekért szám már a t[1] pozícióra kerül. Az i<30 miatt az utolsó sorszám, amire végrehajtódik a szám elhelyezés a vektorban az a t[29] pozíció. Ugyan az i ekkor is nő egyet, de i=30-ra már nem kerül végrehajtásra a ciklus.

Megjegyzés: a fenti kódban az x változóra igazából nincs szükség, a bekért értéket közvetlenül a vektorba is elhelyezhetjük:

double[] t = new double[30];
int i = 0;
while (i<30)
{
  Console.Write("Kérek egy számot");
  t[i] = double.Parse( Console.ReadLine() );
  i++;
}

Vektor feltöltése véletlen számokkal

A fenti megoldáshoz nagyon hasonló, amikor a vektort nem billentyűzetről, hanem véletlen számokkal töltjük fel:

double[] t = new double[30];
Random rnd = new Random();
int i = 0;
while (i<30)
{
  t[i] = rnd.Next(1,100);
  i++;
}

Vektor kiírása a képernyőre

Gyakran van arra szükség, hogy a vektorban lévő elemeket a képernyőre is kiírjuk. Ez szolgálhat ellenőrzési szerepet (látni akarjuk, hogy a vektorban tényleg benne vannak a számok, és melyek azok). Amikor a vektort véletlen számokkal töltjuk fel, természetes igény azokat meg is tekinteni.

...
int i = 0;
while (i<30)
{
  Console.WriteLine("{0}. sorszámú elem={1}",i,t[i]);
  i++;
}

Amikor sok elemről van szó, egy takarékosabb megoldást szoktunk választani: az elemeket a képernyőre egymás mellé, pl. vesszővel elválasztva írjuk ki:

...
int i = 0;
while (i<30)
{
  Console.Write("{0}, ",t[i]);
  i++;
}
Console.WriteLine();

A bezáró üres Console.WriteLine() szerepe, hogy az utolsóként kiírt vektorelem mögött álló kurzort a következő sor elejére rakja át, így megakadályozva, hogy a program következő kiírásai ugyanide kerüljenek.