Felhasználói eszközök

Eszközök a webhelyen


oktatas:programozas:elemi_adatszerkezetek

Különbségek

A kiválasztott változat és az aktuális verzió közötti különbségek a következők.

Összehasonlító nézet linkje

oktatas:programozas:elemi_adatszerkezetek [2019/08/21 17:03] (aktuális)
admin létrehozva
Sor 1: Sor 1:
 +[[oktatas:​programozás|<​ Programozás]]
 +
 +====== Elemi adatszerkezetek ======
 +
 +
 +
 +  * **Szerző:​** Sallai András
 +  * Copyright (c) Sallai András, 2011, 2014
 +  * Licenc: GNU Free Documentation License 1.3
 +  * Web: http://​szit.hu
 +
 +
 +
 +===== Vermek =====
 +
 +A verem, angolul stack. ​
 +A veremben több számot tárolhatunk,​ de mindig csak az utoljára betett ​
 +számot vehetjük ki. 
 +
 +Az alábbiakban egy tömbön megvalósított verem sematikus ábráját látjuk.
 +
 +{{:​oktatas:​programozás:​verem.png|}}
 +
 +Itt az utoljára betett szám az 50-es. Ezt a számot vagyunk képesek kivenni. ​
 +
 +Működése alapján angolosan **LIFO**-nak nevezzük az adatszerkezetet;​ a **Last In First Out** szavakból.
 +
 +===== Sorok =====
 +
 +A sorok vagy angolul queue. Az elsőként betett elem kerül ki elsőnek a sorból.
 +A működése alapján angolosan ezt **FIFO** adatszerkezetnek nevezzük; ​
 +A **First In First Out** szavakból.
 +
 +{{:​oktatas:​programozás:​sor.png|}}
 +
 +===== Láncolt listák =====
 +
 +Az objektumok lineáris sorrendben követik egymást.
 +
 +{{:​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|}}
 +
 +
 +{{:​oktatas:​programozás:​graf_002.png|}}
 +
 +{{:​oktatas:​programozás:​graf_003_cimkezett.png|}}
 +
 +{{:​oktatas:​programozás:​graf_004_iranyitott.png|}}
 +
 +{{:​oktatas:​programozás:​graf_005_fagraf.png|}}
 +
 +{{:​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://​infoc.eet.bme.hu/​ea12.php
 +  * http://​www.dkrmg.sulinet.hu/​~lutter/​szakkor/​
 +  * http://​hu.wikibooks.org/​wiki/​Programoz%C3%A1s/​Algoritmusok
 +===== 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>​
  
oktatas/programozas/elemi_adatszerkezetek.txt · Utolsó módosítás: 2019/08/21 17:03 szerkesztette: admin