Adatszerkezetek
Adatszerkezetek: ingyenes interaktív szimuláció a StudyFi Labből. Közvetlenül a böngészőben fut, regisztráció és telepítés nélkül.
Veremek, sorok, listák, fák és gráfok
Kísérletek
Verem
A verem úgy működik, mint egy tányérkupac: csak a tetejére teszel (push) és csak onnan veszel el (pop), így ami utoljára jött, az megy el elsőként (LIFO). A top mutató jelzi a tetejét; a push és a pop is O(1). Ezt használja a szerkesztő Visszavonás funkciója, a böngésző Vissza gombja és a függvényhívások (hívási verem).
Próbáld ki: Tedd be az 1, 2, 3 számot, majd háromszor pop — fordított sorrendben jönnek ki. Utána próbálj meg egy kilencedik push-t.
Sor
A sor úgy működik, mint a pénztári sor: az új elemek hátul állnak be (enqueue, rear mutató), és elöl távoznak (dequeue, front mutató), így aki elsőként jött, elsőként megy (FIFO). Tömbben körkörös pufferként tároljuk: mindkét mutató az utolsó hely után visszaugrik a 0. helyre, ezért az enqueue és a dequeue is O(1). Sorok kezelik a nyomtatási feladatokat, a szerverkéréseket és a videó pufferelését.
Próbáld ki: Kapcsold be a körkörös nézetet, tegyél be hat számot, vegyél ki négyet, majd tegyél be még négyet — a rear a 7. helyről a 0.-ra ugrik.
Láncolt lista
Minden csomópont egy értéket és egy next hivatkozást tárol a következő csomópontra; az utolsó null-ra mutat, a lista a head mutatónál kezdődik. Az elejére beszúrni O(1), de az i. pozícióhoz vagy egy keresett értékhez csomópontról csomópontra kell lépkedni — O(n). A tömbbel ellentétben semmit sem kell eltolni, csak átkötni a mutatókat; így működnek a lejátszási listák, az előzmények és a szabad memóriablokkok listái.
Próbáld ki: Keresd meg az utolsó értéket, és számold meg a mutató lépéseit, aztán szúrj be az elejére — az mindig egyetlen lépés.
Bináris keresőfa
Minden csomópontban a kisebb értékek balra, a nagyobbak jobbra kerülnek. A keresés és a beszúrás ezért egyetlen úton halad a gyökértől, és O(h) ideig tart, ahol h a fa magassága — kiegyensúlyozott fánál h ≈ log₂ n. A törlésnek három esete van: a levél egyszerűen eltűnik, az egygyerekes csomópontot a gyereke váltja, a kétgyerekes pedig átveszi az inorder rákövetkezője értékét. Az inorder bejárás rendezve adja az értékeket; hasonló fák működtetik az adatbázis-indexeket.
Próbáld ki: Töröld a gyökeret — két gyereke van, így látod a rákövetkező keresését. Aztán próbáld ki a „Rendezett értékek beszúrása” gombot: a fa listává fajul, a magasság n-re nő.
Gráf: BFS és DFS
A szélességi keresés (BFS) sorból veszi a csúcsokat: előbb a kezdőpont összes szomszédját látogatja meg, aztán azok szomszédait — rétegenként, így a legkevesebb élből álló utat találja meg. A mélységi keresés (DFS) veremből veszi a csúcsokat, és amilyen mélyre csak tud, lemegy, mielőtt visszalép. Mindkettő minden csúcsot és élt egyszer jár be: O(V + E). A BFS-t útvonaltervezők és az „ismerősök ismerősei” használják, a DFS labirintust old meg és köröket keres.
Próbáld ki: Lépkedj a 0. csúcstól, és hasonlítsd össze a sort a veremmel. Aztán állítsd a kezdőpontot a 7. csúcsra — a bejárási sorrend teljesen megváltozik.
Gyakori kérdések
Mi az a(z) Adatszerkezetek?
Adatszerkezetek: ingyenes interaktív szimuláció a StudyFi Labből. Közvetlenül a böngészőben fut, regisztráció és telepítés nélkül. Veremek, sorok, listák, fák és gráfok
Ingyenes a(z) Adatszerkezetek?
Igen. A(z) Adatszerkezetek teljesen ingyenes. Böngészőben fut számítógépen, tableten és telefonon, és nem kell hozzá fiók.
Mit fedezhetek fel ebben: Adatszerkezetek?
Verem, Sor, Láncolt lista, Bináris keresőfa, Gráf: BFS és DFS.
Mit mutat a(z) „Verem” kísérlet?
A verem úgy működik, mint egy tányérkupac: csak a tetejére teszel (push) és csak onnan veszel el (pop), így ami utoljára jött, az megy el elsőként (LIFO). A top mutató jelzi a tetejét; a push és a pop is O(1). Ezt használja a szerkesztő Visszavonás funkciója, a böngésző Vissza gombja és a függvényhívások (hívási verem).
Mit mutat a(z) „Sor” kísérlet?
A sor úgy működik, mint a pénztári sor: az új elemek hátul állnak be (enqueue, rear mutató), és elöl távoznak (dequeue, front mutató), így aki elsőként jött, elsőként megy (FIFO). Tömbben körkörös pufferként tároljuk: mindkét mutató az utolsó hely után visszaugrik a 0. helyre, ezért az enqueue és a dequeue is O(1). Sorok kezelik a nyomtatási feladatokat, a szerverkéréseket és a videó pufferelését.
Dolgozatra készülsz?
Töltsd fel a jegyzeteidet, és a StudyFi szókártyákat, teszteket és podcastokat készít belőlük.