Felhasználói eszközök

Eszközök a webhelyen


oktatas:programozas:elemi_adatszerkezetek

< Programozás

Elemi adatszerkezetek

  • Szerző: Sallai András
  • Copyright © Sallai András, 2011, 2014, 2021
  • Licenc: GNU Free Documentation License 1.3

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.

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.

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.

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.

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

Gráfok

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.

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.

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

A bináris fa

Minden elemnek legfeljebb két gyermekeleme van.

Nem bináris

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

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.

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.

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

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

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

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

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

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

Irodalom

Könyvek

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

Linkek

Függelék

Láncolt lista példa

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);
 
    }
 
}
oktatas/programozas/elemi_adatszerkezetek.txt · Utolsó módosítás: 2021/05/14 17:48 szerkesztette: admin