Adatszerkezet

Alapvető adatszerkezetek

Array

A legegyszerűbb adatszerkezet a lineáris tömb. Más néven egydimenziós tömb. Egy tömb több azonos típusú értéket (egész, lebegő, karakterlánc stb.) tárol. A tömbön belüli elemek elérése nagyon gyors. A tömb általában rögzített méretű. Miután a tömb méretét az elején meghatároztuk, előfordulhat, hogy a tömb méretét nem lehet növelni anélkül, hogy ne hoznánk létre egy új, nagyobb tömböt, és ne másolnánk az összes értéket az új tömbbe. Az informatikában a tömbi adatszerkezet vagy egyszerűen csak tömb olyan adatszerkezet, amely elemek (értékek vagy változók) gyűjteményéből áll, amelyek mindegyikét legalább egy tömbindex vagy kulcs azonosítja. A tömböt úgy tárolják, hogy az egyes elemek pozíciója az index-tuplikból matematikai képlettel kiszámítható legyen.

Például egy 10 egész számváltozóból álló, 0-tól 9-ig terjedő indexű tömböt 10 szó formájában lehet tárolni a 2000, 2004, 2008, 2036 memóriacímeken, úgy, hogy az i indexű elem a 2000 + 4 × i címet kapja.

Mivel a mátrix matematikai fogalma kétdimenziós rácsként ábrázolható, a kétdimenziós tömböket néha mátrixoknak is nevezik. Egyes esetekben a számítástechnikában a "vektor" kifejezést használják a tömbökre, bár matematikailag inkább a tuplik, mint a vektorok a megfelelőbb megfelelője. A tömböket gyakran használják táblázatok, különösen keresőtáblák megvalósítására; a táblázat szót néha a tömb szinonimájaként használják.

A tömbök a legrégebbi és legfontosabb adatszerkezetek közé tartoznak, és szinte minden program használja őket. Számos más adatszerkezet, például listák és karakterláncok megvalósítására is használhatók. Hatékonyan kihasználják a számítógépek címzési logikáját. A legtöbb modern számítógépben és sok külső tárolóeszközben a memória szavak egydimenziós tömbje, amelynek indexei a címük. A processzorok, különösen a vektorprocesszorok, gyakran tömbműveletekre optimalizáltak.

A tömbök azért hasznosak, mert az elemindexek futás közben kiszámíthatók. Többek között ez a tulajdonság lehetővé teszi, hogy egyetlen iteratív utasítással tetszőlegesen sok elemet dolgozzunk fel egy tömbben. Emiatt egy tömb adatszerkezet elemeinek azonos méretűnek kell lenniük, és ugyanazt az adatreprezentációt kell használniuk. Az érvényes index-tuplik halmaza és az elemek címei (és így az elemcímzési képlet) általában, de nem mindig rögzítettek, amíg a tömb használatban van.

A tömb kifejezést gyakran használják tömb adattípusra, a legtöbb magas szintű programozási nyelv által biztosított adattípusra, amely értékek vagy változók gyűjteményéből áll, amelyek egy vagy több, futásidőben kiszámított index segítségével választhatók ki. A tömbtípusokat gyakran tömbstruktúrákkal valósítják meg; egyes nyelvekben azonban hash-táblákkal, összekapcsolt listákkal, keresőfákkal vagy más adatstruktúrákkal is megvalósíthatók.

Összekapcsolt lista

A kapcsolt adatszerkezet olyan információk/adatok halmaza, amelyek hivatkozásokkal vannak összekapcsolva. Az adatokat gyakran csomópontoknak nevezik. A hivatkozásokat gyakran linkeknek vagy mutatóknak nevezik. Innentől kezdve a továbbiakban a csomópont és a mutató szavakat használjuk ezekre a fogalmakra.

Az összekapcsolt adatszerkezetekben a mutatókat csak az egyenlőség szempontjából dereferenciázzák vagy hasonlítják össze. Így az összekapcsolt adatszerkezetek különböznek a tömböktől, amelyeknél a mutatókat össze kell adni és ki kell vonni.

A kapcsolt listák, a keresési fák és a kifejezésfák mind kapcsolt adatszerkezetek. Fontosak az olyan algoritmusokban is, mint a topológiai rendezés és a halmazegyesítés-keresés.

Stack

A verem egy olyan alapvető adatszerkezet, amely logikailag lineáris struktúraként gondolható el, amelyet egy valódi fizikai verem vagy halom képvisel, egy olyan struktúra, ahol az elemek beszúrása és törlése a verem egyik végén, a verem tetején történik. Az alapkoncepciót úgy lehet szemléltetni, hogy az adathalmazunkat egy tányér- vagy könyvhalomként képzeljük el, ahol csak a legfelső elemet vehetjük le a halomról, hogy eltávolítsunk dolgokat a halomból. Ez a struktúra az egész programozás során használatos.

A verem alapvető megvalósítását "Last In First Out" struktúrának is nevezik; azonban a verem megvalósításainak különböző változatai léteznek.

Alapvetően három művelet végezhető a veremeken. Ezek a következők:

• egy elem beillesztése ("tolása") egy verembe
• egy elem törlése ("popping") a veremről
• a verem legfelső elemének tartalmának megjelenítése ("kukucskálás")

Sorban állás

A várólista egy absztrakt adattípus vagy lineáris adatszerkezet, amelybe az első elemet az egyik végéről (a "farok") illesztik be, és a meglévő elem törlése a másik végéről (a "fej") történik. A várólista egy "First In First Out" struktúra. A "First In First Out" azt jelenti, hogy a sorba elsőként betett elemek először kerülnek ki, az utolsóként betett elemek pedig utoljára kerülnek ki. A sorban állásra példa a várakozó emberek sora. A sorban az első ember megy először, és az utolsó ember megy utoljára.

Egy elemnek a várólistához való hozzáadását "sorba állításnak", egy elemnek a várólistából való eltávolítását pedig "sorból való eltávolításnak" nevezzük.

Grafikon

A gráf egy absztrakt adattípus, amely a matematikából ismert gráf és hipergráf fogalmak megvalósítására szolgál.

Egy gráf adatszerkezet a csomópontoknak vagy csúcsoknak nevezett egységek rendezett párjainak véges (és esetleg változtatható) halmazából, az élekből vagy ívekből áll. A matematikához hasonlóan egy (x,y) élről azt mondjuk, hogy x-ből y-ba mutat, vagy onnan y-ba megy. A csomópontok lehetnek a gráfszerkezet részei, vagy lehetnek külső entitások, amelyeket egészszámos indexek vagy hivatkozások képviselnek. A gráf adatszerkezete minden élhez rendelhet valamilyen élértéket, például egy szimbolikus címkét vagy egy numerikus attribútumot.

Fa

A fa az egyik legerősebb fejlett adatszerkezet. Gyakran megjelenik olyan haladó témákban, mint a mesterséges intelligencia (AI) és a tervezés. Meglepő módon a fa egy sokkal egyszerűbb alkalmazásban - egy hatékony index vezetésében - is fontos.

Ha fát használnak, nagy az esélye annak, hogy indexet használnak. Az index legegyszerűbb típusa a kulcsmezők rendezett listája. A fának általában meghatározott szerkezete van. Egy bináris fa esetében bináris kereséssel bármely elemet megkereshetünk anélkül, hogy minden elemet meg kellene néznünk.

A fa adattípus egyfajta gráf, ami azt jelenti, hogy sok algoritmus, amely egy gráf átjárására készült, egy fával is működik, azonban az algoritmusok nagyon hasonlóak lehetnek, és rendelkezniük kell egy dedikált kezdő csomóponttal, azaz egy olyan csomóponttal, amelyhez nem kapcsolódik más csomópont.

A probléma egy egyszerű rendezett listával akkor jelentkezik, amikor új elemeket kezdünk hozzáadni, és a listát rendezett állapotban kell tartanunk - ez viszonylag hatékonyan megoldható, de némi módosítást igényel. Ráadásul egy lineáris indexet nem könnyű megosztani, mert az egész indexet "zárolni" kell, amikor egy felhasználó szerkeszti, míg egy fa egy "ága" zárolható, a többi ágat pedig a többi felhasználó szerkesztheti (mivel azokat nem érinti).

Hash táblázat

A hash-tábla egy olyan tömb, amelyben minden index egy hash-érték alapján egy összekapcsolt listára mutat. A hash-érték egy hash-függvény által meghatározott érték. A hash-függvény a tárolt adatok alapján egyedi értéket határoz meg. Ez lehetővé teszi az adatok állandó idő alatt történő elérését, mivel a számítógép mindig tudja, hogy hol kell keresni.

Minden csomópont egy másik csomópontra mutat.