szit

Ez az oldal csak olvasható. Megtekintheted a forrását, de nem változtathatod meg. Ha úgy gondolod, hogy ez helytelen, kérdezd az Adminisztrátorokat!
[[oktatas:programozás|< Programozás]]

====== Elemi adatszerkezetek ======

  * **Szerző:** Sallai András
  * Copyright (c) 2011, Sallai András
  * Szerkesztve: 2011, 2014, 2021, 2024, 2025
  * 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:

<code java SimpleStack.java>
import java.util.ArrayList;

public class SimpleStack<T> {
    private ArrayList<T> 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();
    }
}

</code>

A Java nyelvbe beépített verem:

<code java src/App.java>
import java.util.Stack;

public class App {
    public static void main(String[] args) throws Exception {
        Stack<Integer> stack = new Stack<>();
        stack.push(45);
        stack.push(27);
        stack.push(18);
        stack.push(31);

        System.out.println(stack.size());
        System.out.println(stack.pop());
        System.out.println(stack.size());
        System.out.println(stack.peek());
        System.out.println(stack.empty());
        System.out.println(stack.isEmpty());        
    }
}

</code>

<code java src/App.java>
import java.util.ArrayDeque;
import java.util.Deque;

public class App {
    public static void main(String[] args) throws Exception {
        Deque<Integer> stack = new ArrayDeque<>();
        stack.push(45);
        stack.push(27);
        stack.push(18);
        stack.push(31);

        System.out.println(stack.size());
        System.out.println(stack.pop());
        System.out.println(stack.size());
        System.out.println(stack.peek());
        //Nincs empty() függvény
        System.out.println(stack.isEmpty());        
    }
}
</code>

===== 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|}}

<code java SimpleQueue.java>
import java.util.ArrayList;

public class SimpleQueue<T> {
    private ArrayList<T> 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
    }
}
</code>

A Java beépített sor használata:

<code java src/App.java>
import java.util.ArrayDeque;
import java.util.Queue;

public class App {
    public static void main(String[] args) throws Exception {
        Queue<Integer> queue = new ArrayDeque<>();
        queue.add(35);
        queue.add(25);
        queue.add(48);

        System.out.println(queue.size());
        
        //Kivesszük az elsőnek betett elemet:
        System.out.println(queue.poll());
        System.out.println(queue.size());
        System.out.println(queue.isEmpty());
    }
}
</code>

===== 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:
<code java>
class Elem {
    Object adat;
    Elem kovetkezo;
}
</code>

C nyelven:
<code c>
struct telem {
    Object adat;
    struct telem *kovetkezo;
}
</code>



{{:oktatas:programozás:lancolt_lista_ketiranyban_lancolt.png|}}

Egy elem leírása Java nyelven

<code java>
class Elem {
    Object adat;
    Elem elozo;
    Elem kovetkezo;
}
</code>

===== 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 ====

<code java>
class Elem {
    Object adat;
    Elem szulo;
    Elem bal;
    Elem jobb;
}
</code>

==== 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:
<code java>
static void preorder(Elem elem) {
	if(elem != null) {
		System.out.println(elem.adat);
		preorder(elem.bal);
		preorder(elem.jobb);
	}
}
</code>

==== 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:
<code java>
static void inorder(Elem elem) {
	if(elem != null) {			
		inorder(elem.bal);
		System.out.printf("%c ", elem.adat);
		inorder(elem.jobb);
	}
}
</code>
==== 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:
<code java>
static void postorder(Elem elem) {
	if(elem != null) {			
		postorder(elem.bal);
		postorder(elem.jobb);
		System.out.printf("%c ", elem.adat);
	}
}
</code>


==== 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|}}
<code java 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);

    }

}
</code>