Elemi adatszerkezetek

• Szerző: Sallai András
• Copyright © 2011, Sallai András
• Szerkesztve: 2011, 2014, 2021
• Licenc: CC BY-SA 4.0
• Web: https://szit.hu

A verem, angolul stack. A veremben több adatot tárolhatunk, de mindig csak az utoljára betett adatot vehetjük ki.

Az alábbiakban egy tömbön megvalósított verem sematikus ábráját látjuk, ahol számokat tárolunk.

Itt az utoljára betett szám az 50-es, ezt tudjuk kivenni elsőként.

Működése alapján angolosan LIFO-nak nevezzük az adatszerkezetet; a Last In First Out szavakból.

A sorok vagy angolul queue. Az elsőként betett elemet tudjuk kivenni elsőként a sorból. Működése alapján, angolosan ezt FIFO adatszerkezetnek nevezzük; A First In First Out szavakból.

Az objektumok lineáris sorrendben követik egymást. Minden adathoz tartozik egy mutató is. A mutató mindig a következő adatra mutat.

Az utolsó adat mutatója vagy nem mutat sehova, vagy az első elemre mutat. Ha nem mutat sehova ezt egy NIL céllal szokás jelölni.

Egy elem leírása Java nyelven:

class Elem {
    Object adat;
    Elem kovetkezo;
}

C nyelven:

struct telem {
    Object adat;
    struct telem *kovetkezo;
}

Egy elem leírása Java nyelven

class Elem {
    Object adat;
    Elem elozo;
    Elem kovetkezo;
}

Pontok halmaza, amelyeket vonalakkal kötünk összes. A pontokat csúcsoknak, a vonalakat éleknek nevezzük.

A gráfok csúcsokból és a csúcsokat összekötő élekből állnak.

Ha a csúcspontok számozottak, vagy más módon jelöltek, akkor címkézett gráfról beszélünk.

Ha az élek nyílhegyben végződnek, akkor irányított gráfról beszélünk.

Ha a gráfunk körmentes, akkor fagráfnak nevezhetjük.

Ha több fagráfunk is van, nevezhetjük erdőnek.

A fák előnye a listákkal szemben, hogy gyorsabb a bejárásuk.

A gráfelmélet alapján a fa:

• körmentes (két elem között csak egyetlen út létezik)
• összefüggő egyszerű gráfok

A számítástechnikában általában gyökeres fákkal dolgozunk. Ezt figyelembe véve a meghatározása következő lehet:

Csomópontok halmaza, amit élek kötnek össze, a következő feltételekkel:

• létezik egy kitüntetett csomópont a gyökér
• minden a gyökértől különböző elemet egy éllel kötünk a szülőjéhez
• bármely nem gyökér elemtől a szülőkön keresztül, eljuthatunk a gyökérig

A közbenső elemeket ha gyökérként jelöljük meg, az alatta elhelyezkedő elemekkel részfát alkotnak.

A fa magasság a fa szintjeinek száma.

Minden elemnek legfeljebb két gyermekeleme van.

Előfordulhat kettőnél több leágazás.

Kiegyensúlyozott fáról beszélünk, ha az egyes szinteken a részfák magasságágának ingadozása nem nagyobb egynél.

Bináris keresőfáról beszélünk, ha minden szülőre igaz, hogy balra a nála kisebb elemek helyezkednek el, jobb a nála nagyobb elemek.

Bináris kereső fa építése:

• elhelyezzük az első elemet gyökérként
• ha következő elem kisebb mint az előző, akkor
  • a gyökérelemtől balra helyezzük el
• ellenben
  • jobbra helyezzük el
• A már bevitt elemeket végigjárva, ha csomópontnál kisebb akkor
  • balra megyünk
• ellenben jobbra

• beszúrás
• törlés

class Elem {
    Object adat;
    Elem szulo;
    Elem bal;
    Elem jobb;
}

A fák bejárásának lehetséges módjai:

• szélességi bejárás
• mélységi bejárás

Mélységi bejárás háromféle sorrendje az informatikában:

• preorder bejárás
• inorder bejárás
• postorder bejárás

• a gyökér elem
• majd a baloldali részfa preorder bejárása
• jobboldali részfa preorder bejárása

Preorder bejárás java nyelven:

static void preorder(Elem elem) {
	if(elem != null) {
		System.out.println(elem.adat);
		preorder(elem.bal);
		preorder(elem.jobb);
	}
}

• baloldal részfa inorder bejárása
• gyökér elem
• jobboldali részfa inorder bejárása

Java megvalósítás:

static void inorder(Elem elem) {
	if(elem != null) {			
		inorder(elem.bal);
		System.out.printf("%c ", elem.adat);
		inorder(elem.jobb);
	}
}

• baloldali részfa posztorder bejárása
• jobboldali részfa posztorder bejárása
• végül a gyökér elem

Java megvalósítás:

static void postorder(Elem elem) {
	if(elem != null) {			
		postorder(elem.bal);
		postorder(elem.jobb);
		System.out.printf("%c ", elem.adat);
	}
}

• Thomas H. Cormen, Charles E. Leierson, Ronald L. Rivest, Clifford Stein: Új algoritmusok

• http://www.dkrmg.sulinet.hu/~lutter/szakkor/ (2021)
• http://hu.wikibooks.org/wiki/Programoz%C3%A1s/Algoritmusok (2021)

Program01.java

class Szam {
 
    Integer szam;
    Szam kov;
}
 
public class Mutatok {
 
    public static void main(String[] args) {
 
        Szam elso = new Szam();
        Szam akt = new Szam();
        elso=akt;
        Szam uj;
 
        uj =  new Szam();
        uj.szam = 27;
        akt.kov = uj;
        akt = uj;
 
        uj = new Szam();
        uj.szam = 45;
        akt.kov = uj;
        akt = uj;
 
        uj = new Szam();
        uj.szam = 82;
        akt.kov = uj;
        akt = uj;
 
 
        //Kiíratás
        akt = elso.kov;
        System.out.println("Kiíratás");
        do {
            System.out.println(akt.szam);
            akt = akt.kov;
        } while (akt != null);
 
    }
 
}