Az adatszerkezetek (DS) oktatóanyaga az adatstruktúra alap- és haladó fogalmait tartalmazza. Adatstruktúra oktatóanyagunk kezdőknek és profiknak készült.

Az adatstruktúra az adatok tárolásának és rendszerezésének egyik módja, hogy hatékonyan felhasználhatók legyenek.

Az Adatstruktúra oktatóanyagunk az adatszerkezettel kapcsolatos összes témát tartalmazza, például tömb, mutató, struktúra, csatolt lista, verem, sor, grafikon, keresés, rendezés, programok stb.

Mi az adatstruktúra?

Az adatstruktúra neve önmagában jelzi, hogy az adatokat a memóriában rendezi. Számos módja van az adatoknak a memóriában való rendszerezésének, mivel az egyik adatszerkezetet, azaz a C nyelvű tömböt már láttuk. A tömb memóriaelemek gyűjteménye, amelyben az adatokat szekvenciálisan, azaz egymás után tárolják. Más szóval azt mondhatjuk, hogy a tömb folyamatosan tárolja az elemeket. Ez az adatok rendszerezése adatszerkezetek tömbjének segítségével történik. Vannak más módok is a memóriában lévő adatok rendszerezésére. Lássuk a különböző típusú adatstruktúrákat.

Az adatstruktúra nem akármilyen programozási nyelv, mint például C, C++, java stb. Ez egy olyan algoritmuskészlet, amelyet bármilyen programozási nyelvben használhatunk a memóriában lévő adatok strukturálására.

A memóriában lévő adatok strukturálásához „n” számú algoritmust javasoltak, és ezeket az algoritmusokat absztrakt adattípusoknak nevezik. Ezek az absztrakt adattípusok a szabályok összességét jelentik.

Az adatstruktúrák típusai

Kétféle adatstruktúra létezik:

különben ha bash

• Primitív adatstruktúra
• Nem primitív adatstruktúra

Primitív adatstruktúra

A primitív adatstruktúrák primitív adattípusok. Az int, char, float, double és pointer azok a primitív adatstruktúrák, amelyek egyetlen értéket tartalmazhatnak.

Nem primitív adatstruktúra

A nem primitív adatstruktúra két típusra oszlik:

• Lineáris adatstruktúra
• Nem lineáris adatstruktúra

Lineáris adatstruktúra

Az adatok szekvenciális elrendezését lineáris adatszerkezetnek nevezik. Az erre a célra használt adatszerkezetek: tömbök, csatolt lista, veremek és sorok. Ezekben az adatstruktúrákban egy elem csak egy másik elemhez kapcsolódik lineárisan.

Amikor egy elem 'n' számú elemhez kapcsolódik, amelyet nemlineáris adatszerkezetként ismerünk. A legjobb példa erre a fák és a grafikonok. Ebben az esetben az elemek véletlenszerűen vannak elrendezve.

gépirat kapcsoló

A következő témakörökben röviden tárgyaljuk a fenti adatstruktúrákat. Most látni fogjuk azokat a gyakori műveleteket, amelyeket ezeken az adatstruktúrákon végezhetünk.

Az adatstruktúrák a következőképpen is osztályozhatók:

Statikus adatstruktúra:Ez egy olyan típusú adatstruktúra, ahol a méret a fordítási időben kerül lefoglalásra. Ezért a maximális méret rögzített.Dinamikus adatstruktúra:Ez egy olyan típusú adatstruktúra, ahol a méret a futási időben kerül lefoglalásra. Ezért a maximális méret rugalmas.

Főbb műveletek

Az adatstruktúrákon végrehajtható főbb vagy általános műveletek a következők:

Keresés:Az adatstruktúra bármely elemére rákereshetünk.Válogatás:Egy adatstruktúra elemeit növekvő vagy csökkenő sorrendbe rendezhetjük.Beillesztés:Adatstruktúrába is beilleszthetjük az új elemet.Frissítés:Az elemet frissíthetjük is, azaz kicserélhetjük egy másik elemre.Törlés:Elvégezhetjük a törlési műveletet is az elem adatszerkezetből való eltávolítására.

Melyik adatstruktúra?

Az adatstruktúra egy módja annak, hogy az adatokat úgy rendszerezzük, hogy azok hatékonyan felhasználhatók legyenek. Itt hatékonyan használtuk a szót, ami mind a tér, mind az idő tekintetében. Például a verem egy ADT (absztrakt adattípus), amely tömböket vagy csatolt lista adatstruktúrát használ a megvalósításhoz. Ezért arra a következtetésre jutottunk, hogy szükségünk van bizonyos adatszerkezetre egy adott ADT megvalósításához.

Egy ADT elmondja mit meg kell tenni, és az adatstruktúra megmondja hogyan meg kell tenni. Más szóval azt mondhatjuk, hogy az ADT adja meg a tervrajzot, míg az adatstruktúra a megvalósítási részt. Felmerül a kérdés: hogyan lehet megtudni, hogy egy adott ADT-hez melyik adatszerkezetet kell használni?

Mivel a különböző adatstruktúrák megvalósíthatók egy adott ADT-ben, de a különböző megvalósításokat időben és térben összehasonlítják. Például a Stack ADT megvalósítható tömbökkel és csatolt listákkal is. Tegyük fel, hogy a tömb időhatékonyságot, míg a linkelt lista térhatékonyságot biztosít, tehát az aktuális felhasználó igényeinek leginkább megfelelőt választja ki.

Az adatszerkezetek előnyei

Az adatstruktúra előnyei a következők:

Hatékonyság:Ha megfelelő az adatstruktúra kiválasztása egy adott ADT megvalósításához, az nagyon hatékonyvá teszi a programot időben és térben.Újrahasználhatóság:Az adatstruktúra újrafelhasználhatósága azt jelenti, hogy több ügyfélprogram is használhatja az adatstruktúrát.Absztrakció:Az ADT által meghatározott adatstruktúra az absztrakció szintjét is biztosítja. A kliens nem láthatja az adatstruktúra belső működését, így nem kell aggódnia a megvalósítási rész miatt. A kliens csak a felületet láthatja.

Adatszerkezetek indexe

DS alapok

• DS Bevezetés
• Ds aszimptotikus elemzés
• DS szerkezet

DS Array

• 2D tömb

DS linkelt lista

• Linkelt lista
  • Beillesztés az elején
  • Beillesztés a végén
  • Beszúrás a megadott csomópont után
  • Törlés az elején
  • Törlés a végén
  • Törlés a megadott csomópont után
  • Bejárás
  • Keresés
• Duplán linkelt lista
  • Beillesztés az elején
  • Beillesztés a végén
  • Beszúrás a megadott csomópont után
  • Törlés az elején
  • Törlés a végén
  • Adatot adott csomópont törlése
  • Bejárás
  • Keresés
• Körkörös linkelt lista
  • Beillesztés az elején
  • Beillesztés a végén
  • Törlés az elején
  • Törlés a végén
  • Bejárás
  • Keresés
• Kör alakú kettős lista
  • Beillesztés az elején
  • Beillesztés a végén
  • Törlés az elején
  • Törlés a végén

DS Stack

• Tömb megvalósítás
• Kapcsolt lista megvalósítása

DS Tail

• Tömb megvalósítás
• Kapcsolt lista megvalósítása
• Körkörös sor

DS Tree

véletlenszerű sql sorrendben

• Fa
• Bináris fa
  • Előrendelés Traversal
  • In-order Bejárás
  • Utólagos bejárás
• Bináris keresőfa
  • Keresés a BST-ben
  • Beillesztés a BST-be
  • Törlés a BST-ben
• AVL fa
  • Beillesztés az AVL fába
    • LL Forgatás
    • LR forgatás
    • RL forgatás
    • RR forgatás
  • Törlés az AVL-fában
• B Fa
• B+ fa
• Piros fekete fa

DS Graph

• DS Graph
• Grafikon megvalósítása
• BFS algoritmus
• DFS algoritmus
• Feszítőfának
  • Prim algoritmusa
  • Kruskal algoritmusa

DS keresés

• Lineáris keresés
• Bináris keresés

DS rendezés

• Buborékos rendezés
• Vödör rendezés
• Fésű rendezés
• Számláló rendezés
• Halom rendezés
• Beszúrás rendezése
• Összevonási rendezés
• Gyors rendezés
• Rendezés Radix
• Kijelölés rendezése
• Shell rendezés
• Bitonikus rendezés
• Koktél rendezés
• Ciklikus rendezés
• Tim Sort

Interjú kérdések

c kód abs

• Egyedül hivatkozott lista létrehozására és megjelenítésére szolgáló program
• A program létrehozza az n csomópont egyedileg összekapcsolt listáját, és megszámolja a csomópontok számát
• A program n csomópontból álló, egyedileg összekapcsolt listát hoz létre, és azt fordított sorrendben jeleníti meg
• Program egy új csomópont törlésére az egyedileg csatolt lista elejéről
• Egy új csomópont törlésére szolgáló program az egyedileg csatolt lista közepéről
• Program egy csomópont törlésére az egyszeresen hivatkozott lista végéről
• Program annak meghatározására, hogy egy egyedileg összekapcsolt lista a palindrom
• Program, amely megkeresi a maximális és minimális értékű csomópontot egy egyedileg csatolt listából
• Program egy új csomópont beszúrására az egyedileg csatolt lista közepére
• Program egy új csomópont beszúrására az egyedileg csatolt lista elejére
• Program egy új csomópont beszúrására az egyedileg csatolt lista végére
• Program, amely eltávolítja az ismétlődő elemeket egy egyedileg összekapcsolt listából
• Egyedül hivatkozott lista elemeinek keresésére szolgáló program
• Program az egyedileg csatolt lista elemeinek rendezésére
• A program egy egyedileg összekapcsolt listában lévő csomópontok felcserélésére adatcsere nélkül
• A program az egyszeresen hivatkozott lista utolsó elemének felcserélésére az elsőről

Duplán linkelt listás programok

• Program, amely egy adott bináris fát duplán linkelt listává konvertál
• Program duplán linkelt lista létrehozására hármas fából
• Program, amely létrehoz egy duplán linkelt listát N csomópontból, és megszámolja a csomópontok számát
• Program, amely létrehoz egy duplán linkelt listát N csomópontból, és megjeleníti azt fordított sorrendben
• Program duplán linkelt lista létrehozására és megjelenítésére
• Program egy új csomópont törlésére a duplán linkelt lista elejéről
• Program egy új csomópont törlésére a duplán linkelt lista végéről
• Program egy új csomópont törlésére a duplán linkelt lista közepéről
• Program, amely megkeresi a maximális és minimális értékű csomópontot egy duplán linkelt listából
• Program egy új csomópont beszúrására a duplán linkelt lista elejére
• Program egy új csomópont beszúrására a duplán linkelt lista végére
• Program egy új csomópont beszúrására a duplán linkelt lista közepére
• Program, amely eltávolítja az ismétlődő elemeket egy kettős hivatkozású listáról
• Program a duplán linkelt lista N csomópontonkénti elforgatására
• Program elem keresésére duplán linkelt listában
• Program a duplán linkelt lista elemeinek rendezésére

Circular Linked List Programs

• Program, amely létrehoz egy kör alakú linkelt listát N csomópontból, és megszámolja a csomópontok számát
• Program, amely létrehoz egy kör alakú linkelt listát N csomópontból, és megjeleníti azt fordított sorrendben
• Program egy kör alakú linkelt lista létrehozására és megjelenítésére
• Program egy új csomópont törlésére a kör alakú linkelt lista elejéről
• Program egy új csomópont törlésére a kör alakú linkelt lista végéről
• Program egy új csomópont törlésére a kör alakú linkelt lista közepéről
• Program, amely megkeresi a maximális és minimális értékű csomópontot egy kör alakú linkelt listából
• Program egy új csomópont beszúrására a kör alakú linkelt lista elejére
• Program egy új csomópont beszúrására a kör alakú linkelt lista végére
• Program egy új csomópont beszúrására a kör alakú linkelt lista közepére
• Program az ismétlődő elemek eltávolítására egy kör alakú linkelt listáról
• Program elem keresésére egy kör alakú linkelt listában
• Program a kör alakú linkelt lista elemeinek rendezésére

Fa programok

• Program a bináris fa páratlan és páros szintű csomópontjainak összege közötti különbség kiszámítására
• Program egy bináris keresőfa létrehozására, valamint törlés és sorrendbejárás végrehajtására
• Program a bináris fát bináris keresőfává alakítani
• Program annak meghatározására, hogy minden levél ugyanazon a szinten van-e
• Program annak meghatározására, hogy két fa azonos-e
• Program egy bináris fa maximális szélességének megtalálására
• Program a bináris fa legnagyobb elemének megtalálására
• Program a fa maximális mélységének vagy magasságának meghatározására
• Program, amely megkeresi a bináris fában a legnagyobb távolságra lévő csomópontokat
• Program a legkisebb elem megtalálására egy bináris fában
• Program, amely megkeresi egy bináris fa összes csomópontjának összegét
• Program a lehetséges bináris keresőfák teljes számának megkeresésére N kulccsal
• Program a bináris fa megvalósításához a linkelt lista segítségével
• Program egy csomópont keresésére a bináris fában

Előfeltétel

Az adatstruktúra megtanulása előtt rendelkeznie kell a C nyelv alapismereteivel.

Közönség

Adatstruktúra oktatóanyagunk a kezdők és a profik számára készült.

Probléma

Biztosítjuk, hogy ebben az adatszerkezeti oktatóanyagban nem talál problémát. De ha bármilyen hiba van, kérjük, tegye közzé a kapcsolatfelvételi űrlapon.