[[oktatas:programozás|< Programozás]] ====== Elemi adatszerkezetek ====== * **Szerző:** Sallai András * Copyright (c) 2011, Sallai András * Szerkesztve: 2011, 2014, 2021, 2024 * Licenc: [[https://creativecommons.org/licenses/by-sa/4.0/|CC BY-SA 4.0]] * Web: https://szit.hu ===== Vermek ===== 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. {{:oktatas:programozás:verem.png|}} 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. Java nyelven:


import java.util.ArrayList;

public class SimpleStack {
    private ArrayList elements;

    public SimpleStack() {
        elements = new ArrayList<>();
    }

    public void push(T elem) {
        elements.add(elem);
    }

    public T pop() {
        return elements.remove(elements.size()-1);
    }

    public int size() {
        return elements.size();
    }
}

===== Sorok ===== 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. {{:oktatas:programozás:sor.png|}}


import java.util.ArrayList;

public class SimpleQueue {
    private ArrayList elements;

    public SimpleQueue() {
        elements = new ArrayList<>();
    }

    public void enqueue(T elem) {
        elements.add(elem); // Hozzáadunk egy elemet a sor végéhez
    }

    public T dequeue() {
        if (elements.isEmpty()) {
            throw new RuntimeException("A sor üres, nem lehet kivenni elemet!");
        }
        return elements.remove(0); // Kivesszük a sor elejéről az első elemet
    }

    public int size() {
        return elements.size(); // Visszaadja az aktuális elemek számát a sorban
    }

    public boolean isEmpty() {
        return elements.isEmpty(); // Ellenőrzi, hogy a sor üres-e
    }
}

===== Láncolt listák ===== 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. {{:oktatas:programozás:lancolt_lista_1.png|}} Egy elem leírása Java nyelven:


class Elem {
    Object adat;
    Elem kovetkezo;
}

C nyelven:


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

{{:oktatas:programozás:lancolt_lista_ketiranyban_lancolt.png|}} Egy elem leírása Java nyelven


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

===== Gráfok ===== Pontok halmaza, amelyeket vonalakkal kötünk összes. A pontokat csúcsoknak, a vonalakat éleknek nevezzük. {{:oktatas:programozás:graf_001.png|}} A gráfok csúcsokból és a csúcsokat összekötő élekből állnak. {{:oktatas:programozás:graf_002.png|}} Ha a csúcspontok számozottak, vagy más módon jelöltek, akkor címkézett gráfról beszélünk. {{:oktatas:programozás:graf_003_cimkezett.png|}} Ha az élek nyílhegyben végződnek, akkor irányított gráfról beszélünk. {{:oktatas:programozás:graf_004_iranyitott.png|}} Ha a gráfunk körmentes, akkor fagráfnak nevezhetjük. {{:oktatas:programozás:graf_005_fagraf.png|}} Ha több fagráfunk is van, nevezhetjük erdőnek. {{:oktatas:programozás:graf_006_erdo.png|}} ===== Fák ===== ==== A fákról ==== 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. {{:oktatas:programozás:002_fa_reszei.png|}} A fa magasság a fa szintjeinek száma. ==== A bináris fa ==== Minden elemnek **legfeljebb két gyermekeleme** van. {{:oktatas:programozás:003_binarisfa.png|}} {{:oktatas:programozás:004_binarisfa.png|}} ==== Nem bináris ==== Előfordulhat kettőnél több leágazás. {{:oktatas:programozás:001_fa.png|}} ==== Kiegyensúlyozott fák ==== 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. {{:oktatas:programozás:005_kiegyensulyozottfa.png|}} {{:oktatas:programozás:006_kiegyensulyozatlanfa.png|}} {{:oktatas:programozás:007_tokeletesenkiegyensulyozottfa.png|}} ==== Bináris keresőfák ==== 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. {{:oktatas:programozás:008_binariskeresofa_1.png|}} {{:oktatas:programozás:009_binariskeresofa_2.png|}} {{:oktatas:programozás:008_binariskeresofa_3.png|}} 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 ==== Műveletek fákkal ==== * beszúrás * törlés {{:oktatas:programozás:010_beszurasfaba.png|}} {{:oktatas:programozás:011_torlesfabol.png|}} ==== Egy elem leírása Java nyelven ====


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

==== A fa bejárása ==== 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 {{:oktatas:programozás:fakbejarasa.png|}} ==== Preorder bejárás ==== * a gyökér elem * majd a baloldali részfa preorder bejárása * jobboldali részfa preorder bejárása {{:oktatas:programozás:fapreorderbejaras.png|}} 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);
	}
}

==== Inorder bejárás ==== * baloldal részfa inorder bejárása * gyökér elem * jobboldali részfa inorder bejárása {{:oktatas:programozás:fainorderbejaras.png|}} 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);
	}
}

==== Posztorder bejárás ==== * baloldali részfa posztorder bejárása * jobboldali részfa posztorder bejárása * végül a gyökér elem {{:oktatas:programozás:fapostorderbejaras.png|}} 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);
	}
}

==== Szélességi bejárás ==== {{:oktatas:programozás:szelessegibejaras.png|}} ===== Irodalom ===== ==== Könyvek ==== * Thomas H. Cormen, Charles E. Leierson, Ronald L. Rivest, Clifford Stein: Új algoritmusok ==== Linkek ==== * http://www.dkrmg.sulinet.hu/~lutter/szakkor/ (2021) * http://hu.wikibooks.org/wiki/Programoz%C3%A1s/Algoritmusok (2021) ===== Függelék ===== ==== Láncolt lista példa ==== {{:oktatas:programozás:lancolt_lista_programozasi_nyelvben.png|}}


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);

    }

}