Tartalomjegyzék

< Programozás

Elemi adatszerkezetek

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.

Java nyelven:

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

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.

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

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:

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:

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:

Műveletek fákkal

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:

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

Preorder bejárás

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

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

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

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