Asszociatív adatszerkezetek

Olyan halmaz vagy multihalmaz, amelynek az elemeiből részhalmazokat tudunk kiválasztani, ezek átfedhetik egymást. Lényeges, hogy a részhalmazokat milyen szempont szerint választjuk ki. A részhalmazokat meg kell tudni fogni, különböztetni egymástól.

TÖMB

A legismertebb, a leggyakrabban alkalmazott statikus adatszerkezet. A részhalmazok egyeleműek és diszjunktak, és az osztályozásba minden elem be van vonva, ezért minden adatelem megfogható.
A tömb minden eleme egész számok sorozatán keresztül érhető el (ezek az egész számok a tömbindexek), az indexek alkalmazása teszi azt lehetővé, hogy egyelemű részhalmazokat képezzünk.

Az index tetszőleges egész szám lehet, általában egytől kezdődik. Van felső és alsó határa, amelyek az indextartományt definiálják. A tömbhöz hozzátartozik, hogy minden dimenzióban rögzítem az indexek kezdő és végértékét, rögzítek egy intervallumot, ez meghatározza az elemek számát. Az egyes dimenziókban lévő elemek számának szorzata adja a tömb elemszámát.
Ha az adatelemekből egy adott elem kiválasztását egy index segítségével meg tudom valósítani, akkor egydimenziós tömbről vagy vektorról beszélünk.
Ha minden elemet két index segítségével lehet kiválasztani, akkor kétdimenziós tömbről, mátrixról beszélünk. A kétdimenziós tömb sorokból és oszlopokból áll. Eleminek indexelésekor előbb a sor-, majd az oszlopindexeket adjuk meg.

Ha minden elemet három index segítségével lehet kiválasztani, akkor háromdimenziós tömbről beszélünk. A háromdimenziós tömb lapokból áll.

Tetszőleges dimenziójú tömbökről beszélhetünk, mint adatszerkezetekről. A tömb olyan adatszerkezetnek tekinthető, amelyben az elemek értékei egymástól függetlenek, és az elemek a szerkezetben elfoglalt helyük szerint vannak definiálva, így rendezettség az elhelyezés szerint van. Az adatszerkezetet értéktől függetlenül a szerkezet definiálja.


Műveletek
Létrehozás: A szerkezet létrehozása, nem az értékeké. Megmondom a dimenziók számát és minden dimenzióban az indextartományt. A szerkezetet hozom létre, és mivel a szerkezet statikus, így már az elején eldől, hogy a tömb hány elemet tartalmaz. Ebbe a szerkezetbe pakolom bele az elemek értékét.
Bővítés: Nem létezik olyan, hogy új helyre új elem bevitele, mivel a tömb statikus, az adatelemek számát létrehozáskor fixáltam. A bővítés szűkebb változata az, hogy az üres szerkezeti helyekre adatelemet viszek be, azaz átvitt értelemben: megadom azoknak az adatelemeknek az értékét, amelyeket eddig még nem adtam meg.
Törlés: Erről sem beszélhetünk, mert az adatelemek számát nem tudom csökkenteni. Csak logikai törlésről beszélhetünk, mikor az adatelemek értéket egy speciális értékre állítom.
Csere: Indexek alapján bármelyik elemet kiválaszthatom, és értékét felülírhatom.
Elérés: közvetlen. Bármelyik elem a többitől függetlenül megfogható, az indexekkel hivatkozom rá.
Rendezés: Általában egydimenziós tömbnél foglalkozunk vele, ekkor az összes rendezési módszer alkalmazható.
Keresés: Mindenféle tömbnél értelmezhető, és értelmezése reprezentáció-függő. Ha a feltételek adottak, akkor egy dimenziós tömbnél (itt van jelentősége) az összes keresési algoritmus alkalmazható.
Bejárás: Értelmezhető, reprezentáció-függő. Többdimenziós tömböknél igazán érdekes.
Feldolgozás: Az indexeken alapul, azon, hogy segítségükkel bármely elem közvetlenül elérhető, feldolgozható.

A tömböknél a folyamatos és szétszórt tárolás egyaránt alkalmazható. Általában folytonos tárolást alkalmaznak.
A tömb leképzése folytonos társzerkezetre a következőképpen történik. Legyen a kiindulási tömb:

A kétdimenziós tömb első indexeinek tartománya: s...n és második indexeinek tartománya: t...m. Képezzük le ezt a kétdimenziós tömböt folytonos társzerkezetre! A leképezés sor- vagy oszlopfolytonosan történik. Az implementációk nagy része a sorfolytonosat választja. Ez a következőt jelenti:
sorfolytonosan: a_s,t ; a_s,t+1 ; a_s,t+2 ; ... ; a_n,m-1 ; a_n,m ,
oszlopfolytonosan: a_s,t ; a_s+1,t ; a_s+2,t ; ... ; a_n-1,m ; a_n,m.
Elhelyezem az első sor elemeit, utána a második sor elemeit és így tovább. Az oszlopfolytonos tárolás ugyanaz, mint a sorfolytonos, csak oszlopokat veszünk sorban. Ha több mint kétdimenziós tömb van, akkor az indexek végigfutnak az indextartományokon. Sorfolytonos tárolásnál a legutolsó index fut végig a leggyorsabban és az első a leglassabban, oszlopfolytonosnál ez fordítva van.
A tömb bejárása és a tömbben való keresés függ attól, hogy a tömb oszlop- vagy sorfolytonosan van tárolva.

Kérdés az, hogy ha ismerem egy adott tömbelem indexeit, akkor hogyan tudom meghatározni a tárbeli helyét. Ismerni kell a tömb kezdőcímét (k), egy elemének hosszát bájtban (l) és az indexeinek alsó és felső határát minden dimenzióban. Így
egydimenziós tömbnél az i. elem címe : k+l*(i-s),
kétdimenziós tömbnél az a_i,j elem címe: k+l*(i–s)*(m-t+1)+l*(j-t), sorfolytonos tárolás esetén.
Ezeket nevezzük címfüggvényeknek.
Minden adatszerkezet (a többdimenziós tömb is) szimulálható egydimenziós tömb segítségével.

Mátrixok kezelése
Abban az esetben, ha a mátrix háromszög mátrix, azaz a főátló alatt vagy fölött minden elem nulla, a nullértékű elem tárolását meg lehet spórolni. A mátrixot kezeljük vektorként, képezzük le olyan egydimenziós tömbre, amely csak a nem nulla elemeket tartalmazza. A vektor elemeinek száma: m=n*(n+1)/2.

A mátrix leképezése a következő módon történik (sorfolytonos leképezés):

Általánosan a kétdimenziós tömb leképezése egydimenziós tömbre indirekt indexeléssel történik. Egy A tetszőleges kétdimenziós tömböt képezünk le egy V vektorra.
A indexhatárai: (a₁ ... f₁, a₂ ... f₂).
V mérete m*n, ahol m=(f₁-a₁+1), n=(f₂ -a₂+1).
Hozzunk létre egy IV indexvektort, amely elemeinek száma m.
Az IV k. eleme: 1 + (k - 1) * n, ez nem más, mint az A mátrix (a₁ - 1 + k). sora első elemének V-beli indexe.

Ez egy sorfolytonos leképezés, A_i,j=V_t, t=IV_i-a₁₊₁+j-a₂.
Sokszor kell olyan mátrixot használni, amelynek sok eleme nulla, vagy sok azonos értékű eleme van. Ezeket nevezzük ritka mátrixoknak. A kérdés az, hogy ezeket hogyan tudjuk kezelni.

Háromsoros reprezentáció:
A három egydimenziós tömb azonos elemei írnak le egy-egy elemet sorfolytonos ábrázolásban.

A keresés lineáris, mert vagy megtaláljuk a keresett elemet, vagy nagyobb értékűt találunk és akkor 0 lesz a függvény visszatérési értéke. A probléma az, hogy nem tudjuk a sor, az oszlop, és az érték maximális értékét. A tömb statikus adatszerkezet, ezért több helyet kell foglalni, így marad üresen lefoglalt tárrész. A másik gond az, hogy nem lehet közvetlenül elérni az elemet, keresést kell alkalmazni. Ez nem oldható meg, viszont az első probléma szétszórt tárolás esetén megoldható. A tömb statikus voltát dinamikusra viszem.

A mutató vektor dolga, hogy lerendezze az oszlopok kezelését. Értékét úgy állítjuk be, hogy a megfelelő helyre beírjuk a négysoros reprezentáció azon indexét, amelyik megmondja, hogy mely indexnél található az oszlop következő nem nulla eleme. Ennek oszlopfolytonos feldolgozásnál van jelentősége, mert lehetővé teszi, hogy ne kelljen végignézni szekvenciálisan az egészet, hanem megmondja, hogy hol a következő elem az adott oszlopban. A négy sorhoz még két vektort hozzáveszek, melyeket jelöljünk S-sel és O-val. Ez a két vektor úgy van feltöltve, hogy a vektor i. eleme megadja, hogy hol helyezkedik el az i. sor, illetve oszlop első nem nulla eleme a SOR illetve az OSZLOP vektorban, így közvetlenül fel tudok dolgozni bármilyen mátrixot.

TÁBLÁZAT (TABLE)

Asszociatív, dinamikus adatszerkezet, amelyben minden elem két részből áll.

A kulcs és az érték típusa bármilyen lehet, de egy táblázaton belül a kulcsok, értékek típusa megegyező kell, hogy legyen. A kulcs és az érték típusa különböző lehet. Minden táblázati elem kulcsértéke egyedi, így ez a kiválasztási szempont. A táblázat nem más, mint egydimenziós tömb általánosítva, ahol bármely elem a kulcson keresztül érhető el.
Reprezentációja lehet folytonos és szétszórt is, de általában folytonos ábrázolást alkalmaznak. Gyakran úgy tárolják, hogy a kulcsot és az értéket leképezik egy-egy egydimenziós tömbre. Különböző szervezésű táblázatok vannak.

Soros táblázat
A kezelés szempontjából ez a legegyszerűbb táblázat. Akkor érdemes soros táblázatot használni, ha az egyes elemek feldolgozási valószínűsége közel azonos.

Műveletek
Létrehozás: Az elemek az érkezés sorrendjében kerülnek a táblázatba.
Bővítés: A táblázat végére lehet.
Törlés: Meg lehet oldani logikai törléssel és a szabadhelyek elfogyása után szemétgyűjtéssel, és meg lehet oldani fizikai törléssel is. A fizikai törlés az, amikor a törlendő elem mögött lévő elemeket előretolom. A baj csak az, hogy így sok elemet kellene mozgatni, ezért helyette azt alkalmazzák, hogy kitörlik az elemet és a legutolsó elemet a helyére írják. Így csak egy elemet kell mozgatni.
Csere: Minden elem felülírható. Megkeresem az adott kulcsú elemet és felülírom az értékét. Soros táblázatnál nem jelent gondot, ha az értéket és a kulcsot is felül akarom írni, de figyelni kell, hogy a kulcs az előzőekben ne szerepeljen.
Rendezés: Nem értelmezett.
Keresés: Kulcsra vonatkozó teljes keresés.
Bejárás: Soros (az elemek elhelyezésének sorrendjében).
Feldolgozás: Kulcs alapján.

Soros táblázatok akkor alkalmazhatók jól, ha sok elemet akarunk feldolgozni. Ha feltesszük, hogy minden elemet ugyanolyan gyakorisággal dolgozunk fel, akkor ideális, de ez a gyakorlatban persze, hogy nincs így. Az lenne a jó, ha a gyakrabban feldolgozott elemet gyorsabban elérnénk, vagyis a táblázat elején lenne. Ezen okok miatt jött létre az önátrendező tábla.

Önátrendező tábla
Az egyes elemek feldolgozási valószínűsége különböző. Az önátrendező tábla azt a gondolatot valósítja meg, hogy a leggyakrabban használt elemek a tábla elején legyenek. A megoldás nagyon egyszerű. Ha egy elemet feldolgozunk, akkor azt helyezzük a táblázat elejére. Ez a folyamat sok lépés után ahhoz vezet, hogy a legelső helyen a leggyakrabban feldolgozott elem fog állni. Reprezentációjánál szétszórt ábrázolást alkalmaznak, mert itt az átrendezés egyszerű.

Rendezett tábla
Ez általában kulcs alapján történő növekvő rendezettséget jelent. A feldolgozást segíti a rendezés. Az elemeket nem azonos gyakorisággal dolgozom fel, és nem mindegyik elemet.

Műveletek
Létrehozás: Beszúrásos rendezéssel történik.
Bővítés: Beszúrásos rendezéssel történik.
Törlés: Meg lehet oldani logikai törléssel, és a szabadhelyek elfogyása után szemétgyűjtéssel, és meg lehet oldani fizikai törléssel is. A fizikai törlés folyamatos tárolásnál az, amikor a törlendő elem mögött lévő elemeket előretolom. Szétszórt ábrázolásnál igen egyszerűen megoldható.
Csere: Megkeresem és felülírom az adott elemet. A kulcs alapján cserélem az értékrészt, a kulcs cseréje nem engedélyezett. Ha azt is meg akarom cserélni, akkor fizikai törlést és bővítést kell alkalmazni.
Rendezés: Nincs, mert a tábla rendezetten jön létre.
Keresés: Mindkét reprezentációnál alkalmazható a lineáris keresés, folytonosnál a bináris keresés is.
Bejárás: Szekvenciális, logikai sorrend szerint.
Feldolgozás: Kulcs alapján történik.

Kulcstranszformációs táblázatok
Mindig folytonos tármegjelenése van. Kulcs: k; f(k) egy függvény, amelyik a k-t leképezi a címre (minden kulcshoz hozzárendel egy címet, meghatározza az elemek helyét a táblában). Az f egy hash-függvény, a technika pedig a hashing (randomizálás). Az lenne a jó, ha a függvény kölcsönösen egyértelmű lenne, de ez a gyakorlatban ritka. Általában a függvények egyértelműek, ami azt jelenti, hogy különböző kulcsokhoz ugyanazt a címet rendelhetik hozzá. Azon kulcsokat, amelyekhez ugyanazt a címet rendeli, szinonimáknak (túlcsordulásnak) nevezzük.
A kulcsoknak típusa van, így létezik a kulcsoknak egy elvi darabszáma, amit a kulcs típusa megszab. A gyakorlatban általában az elvi lehetőségek töredékét használjuk fel. Ha az elvi és a gyakorlati lehetőségek száma megegyezik, vagy a gyakorlati lehetőségek száma egyenletesen oszlik meg az elvi lehetőségeken belül, akkor kölcsönösen egyértelmű leképezést alkalmazhatunk. Ez a ritkább, általában az elvi lehetőségek száma nagyságrendekkel nagyobb, mint a gyakorlati lehetőségek száma, és az elhelyezés sem egyenletes. Ilyenkor egyértelmű hash-függvényt alkalmazunk. Egy hash-függvénytől elvárjuk, hogy:

• A kulcsokat be kell transzformálnia egy sorszámintervallumba ( [0 - n] ), pontosan oda, ahova tárat lefoglalok.
• A kulcsokat lehetőleg egyenletesen szórja szét, ne legyen sok szinoníma.
• A kulcs lehet numerikus vagy szöveges. Ha szöveges, akkor az első lépésben hozzárendelünk numerikus értéket, pl. a karakterek belső kódját. Ha megválasztottuk a kulcs típusát, az elvi lehetőségek száma eldől.

1. Minden kulcs elő is fordul (vagy majdnem mind)
2. Nagyságrendi különbség van az elvi lehetőségek és a ténylegesen előforduló alkalmazott kulcsok között, de a gyakorlatban előforduló kulcsok valamilyen szabály szerint helyezkednek el az elvi lehetőségeken belül.
3. Nagyságrendi különbség és a gyakorlatban szabályszerűtlenség van az elvi lehetőségek és a ténylegesen előforduló alkalmazott kulcsok között.

Műveletek
Létrehozás: Meg kell becsülni, hogy a gyakorlatban ténylegesen hány kulcs fog előfordulni (m). Ezt követően le kell foglalnom legalább m tárhelyet, de általában 1,2*m tárhelyet biztosítanak, azért hogy biztosan legyen üres hely. Kiválasztok valamilyen hash-függvényt és valamilyen szinonimakezelési technikát. Ezután bepakolom az elemeket. Létrehozás után léteznek üres helyek és élő elemek.
Bővítés: A létrehozás technikájával kerülnek be a táblázatba az új elemek.
Törlés: Nyílt címzésnél csak logikai, másik kettőnél fizikai törlés is van.
Csere: Kulcs alapján keresem meg az elemet, az értékrészét felülírom.
Rendezés: Nincs.
Keresés: Nincs. Kulcs alapján tudom az elemeket feldolgozni, mert nincs fizikai sorrend. Logikai sorrend sincs. A keresésnek nincs alapja, csak kulcs alapján.
Bejárás: Nincs.
Elérés: Az esetek többségében közvetlen.
Feldolgozás: Kulcs alapján.

A kulcstranszformációs táblák előnyösek, ha viszonylag nagyméretűek, és viszonylag statikusak, azaz kevés a karbantartási művelet. A táblázat kevésbé érzékeny rá, hogy egy vagy több elemet dolgozok fel. A legjobb talán az a technika, amikor a táblázaton belül láncolok. Hátránya az, hogy a táblázaton belül nincs rendezettség, a feldolgozás és a karbantartás lassú. Ez a lassúság legjobban a gyorsan változó tábláknál jelentkezik, hiszen ott igen sok a karbantartási művelet.

Egy szintet vissza, vagy vissza a főmenübe.