Výukový program Data Structures (DS) poskytuje základné a pokročilé koncepty dátovej štruktúry. Náš tutoriál Data Structure je určený pre začiatočníkov aj profesionálov.

Štruktúra údajov je spôsob, ako ukladať a organizovať údaje tak, aby sa dali efektívne využívať.

Náš tutoriál o štruktúre údajov obsahuje všetky témy štruktúry údajov, ako sú pole, ukazovateľ, štruktúra, prepojený zoznam, zásobník, front, graf, vyhľadávanie, triedenie, programy atď.

Čo je dátová štruktúra?

Názov dátovej štruktúry sám o sebe naznačuje, že organizuje dáta v pamäti. Existuje mnoho spôsobov, ako organizovať dáta v pamäti, ako sme už videli jednu z dátových štruktúr, t.j. pole v jazyku C. Pole je súbor pamäťových prvkov, v ktorých sú dáta ukladané postupne, t.j. jeden po druhom. Inými slovami, môžeme povedať, že pole ukladá prvky nepretržite. Táto organizácia údajov sa vykonáva pomocou radu údajových štruktúr. Existujú aj iné spôsoby usporiadania údajov v pamäti. Pozrime sa na rôzne typy dátových štruktúr.

Štruktúra údajov nie je žiadny programovací jazyk ako C, C++, java atď. Je to súbor algoritmov, ktoré môžeme použiť v akomkoľvek programovacom jazyku na štruktúrovanie údajov v pamäti.

Na štruktúrovanie údajov v pamäti bol navrhnutý počet „n“ algoritmov a všetky tieto algoritmy sú známe ako abstraktné typy údajov. Tieto abstraktné dátové typy sú množinou pravidiel.

Typy dátových štruktúr

Existujú dva typy dátových štruktúr:

zip príkaz v linuxe

• Primitívna dátová štruktúra
• Neprimitívna dátová štruktúra

Primitívna dátová štruktúra

Primitívne dátové štruktúry sú primitívne dátové typy. Int, char, float, double a pointer sú primitívne dátové štruktúry, ktoré môžu obsahovať jednu hodnotu.

Neprimitívna dátová štruktúra

Neprimitívna dátová štruktúra je rozdelená do dvoch typov:

• Lineárna dátová štruktúra
• Nelineárna dátová štruktúra

Lineárna dátová štruktúra

Usporiadanie údajov sekvenčným spôsobom je známe ako lineárna dátová štruktúra. Dátové štruktúry používané na tento účel sú polia, prepojený zoznam, zásobníky a fronty. V týchto dátových štruktúrach je jeden prvok spojený len s druhým prvkom v lineárnej forme.

Keď je jeden prvok pripojený k 'n' počtu prvkov známym ako nelineárna dátová štruktúra. Najlepším príkladom sú stromy a grafy. V tomto prípade sú prvky usporiadané náhodne.

mb na gb

Vyššie uvedené dátové štruktúry v krátkosti rozoberieme v nasledujúcich témach. Teraz uvidíme bežné operácie, ktoré môžeme vykonávať s týmito dátovými štruktúrami.

Dátové štruktúry možno tiež klasifikovať ako:

Statická dátová štruktúra:Je to typ dátovej štruktúry, kde je veľkosť pridelená v čase kompilácie. Preto je maximálna veľkosť pevne stanovená.Dynamická dátová štruktúra:Je to typ dátovej štruktúry, kde je veľkosť pridelená v čase spustenia. Preto je maximálna veľkosť flexibilná.

Hlavné operácie

Hlavné alebo bežné operácie, ktoré možno vykonať s dátovými štruktúrami, sú:

Hľadá sa:Môžeme hľadať akýkoľvek prvok v dátovej štruktúre.Triedenie:Prvky dátovej štruktúry môžeme triediť buď vzostupne alebo zostupne.Vloženie:Nový prvok môžeme vložiť aj do dátovej štruktúry.Aktualizácia:Prvok môžeme tiež aktualizovať, t.j. prvok môžeme nahradiť iným prvkom.vymazanie:Môžeme tiež vykonať operáciu delete na odstránenie prvku z dátovej štruktúry.

Ktorá dátová štruktúra?

Štruktúra údajov je spôsob organizácie údajov tak, aby sa dali efektívne využívať. Tu sme použili slovo efektívne, čo z hľadiska priestoru aj času. Napríklad zásobník je ADT (abstraktný dátový typ), ktorý na implementáciu používa buď polia alebo dátovú štruktúru prepojeného zoznamu. Preto sme dospeli k záveru, že na implementáciu konkrétneho ADT potrebujeme určitú dátovú štruktúru.

ADT hovorí čo je potrebné urobiť a dátová štruktúra hovorí ako má sa to urobiť. Inými slovami, môžeme povedať, že ADT nám poskytuje plán, zatiaľ čo dátová štruktúra poskytuje implementačnú časť. Teraz vyvstáva otázka: ako sa dá zistiť, ktorá dátová štruktúra sa má použiť pre konkrétny ADT?.

Pretože rôzne dátové štruktúry môžu byť implementované v konkrétnom ADT, ale rôzne implementácie sa porovnávajú v čase a priestore. Napríklad Stack ADT môže byť implementovaný ako polia, tak aj prepojený zoznam. Predpokladajme, že pole poskytuje efektívnosť času, zatiaľ čo prepojený zoznam poskytuje efektívnosť priestoru, takže sa vyberie to, ktoré najlepšie vyhovuje požiadavkám aktuálneho používateľa.

Výhody dátových štruktúr

Výhody dátovej štruktúry sú nasledujúce:

Účinnosť:Ak je výber dátovej štruktúry na implementáciu konkrétneho ADT správny, robí program veľmi efektívnym z hľadiska času a priestoru.Opätovná použiteľnosť:Štruktúra údajov poskytuje opätovnú použiteľnosť, čo znamená, že štruktúru údajov môže používať viacero klientskych programov.Abstrakcia:Štruktúra údajov špecifikovaná ADT tiež poskytuje úroveň abstrakcie. Klient nevidí vnútorné fungovanie dátovej štruktúry, takže sa nemusí starať o implementačnú časť. Klient vidí iba rozhranie.

Index dátových štruktúr

Základy DS

• Úvod DS
• Ds asymptotická analýza
• Štruktúra DS

DS Array

• 2D pole

Prepojený zoznam DS

• Prepojený zoznam
  • Vloženie na začiatok
  • Vloženie na koniec
  • Vloženie za určený uzol
  • Vymazanie na začiatku
  • Odstránenie na konci
  • Odstránenie po zadanom uzle
  • Prechádzanie
  • Hľadá sa
• Dvojito prepojený zoznam
  • Vloženie na začiatok
  • Vloženie na koniec
  • Vloženie za určený uzol
  • Vymazanie na začiatku
  • Odstránenie na konci
  • Vymazanie uzla s danými údajmi
  • Prechádzanie
  • Hľadá sa
• Kruhový prepojený zoznam
  • Vloženie na začiatok
  • Vloženie na koniec
  • Vymazanie na začiatku
  • Vymazanie na konci
  • Prechádzanie
  • Hľadá sa
• Kruhový dvojitý zoznam
  • Vloženie na začiatok
  • Vloženie na koniec
  • Vymazanie na začiatku
  • Vymazanie na konci

DS Stack

• Implementácia poľa
• Implementácia prepojeného zoznamu

DS chvost

• Implementácia poľa
• Implementácia prepojeného zoznamu
• Kruhový rad

Strom DS

wumpus svet

• Strom
• Binárny strom
  • Predobjednajte si Traversal
  • Priebeh v poradí
  • Prechod po objednávke
• Binárny vyhľadávací strom
  • Hľadá sa v BST
  • Vloženie do BST
  • Vymazanie v BST
• Strom AVL
  • Vloženie do stromu AVL
    • Rotácia LL
    • LR rotácia
    • Rotácia RL
    • Rotácia RR
  • Odstránenie v strome AVL
• B strom
• Strom B+
• Červený čierny strom

DS graf

• DS graf
• Implementácia grafov
• Algoritmus BFS
• Algoritmus DFS
• Spanning Tree
  • Primov algoritmus
  • Kruskalov algoritmus

Vyhľadávanie DS

• Lineárne vyhľadávanie
• Binárne vyhľadávanie

Triedenie DS

• Bublinové triedenie
• Triediť vedro
• Triediť hrebeňom
• Počítanie Triediť
• Hromadné triedenie
• Triedenie vloženia
• Zlúčiť triedenie
• Rýchle triedenie
• Zoradiť Radix
• Výber Zoradiť
• Shell Sort
• Bitonic Tried
• Triediť koktaily
• Cyklické triedenie
• Tim Sort

Otázky na pohovor

synchronizácia vlákien

• Program na vytvorenie a zobrazenie samostatne prepojeného zoznamu
• Program na vytvorenie samostatne prepojeného zoznamu n uzlov a spočítanie počtu uzlov
• Program na vytvorenie samostatne prepojeného zoznamu n uzlov a jeho zobrazenie v opačnom poradí
• Program na odstránenie nového uzla zo začiatku samostatne prepojeného zoznamu
• Program na vymazanie nového uzla zo stredu jednotlivo prepojeného zoznamu
• Program na odstránenie uzla z konca samostatne prepojeného zoznamu
• Program na určenie, či je palindrómom jednotlivo prepojený zoznam
• Program na nájdenie uzla maximálnej a minimálnej hodnoty z jednotlivo prepojeného zoznamu
• Program na vloženie nového uzla do stredu jednotlivo prepojeného zoznamu
• Program na vloženie nového uzla na začiatok samostatne prepojeného zoznamu
• Program na vloženie nového uzla na koniec jednotlivo prepojeného zoznamu
• Program na odstránenie duplicitných prvkov z jedného prepojeného zoznamu
• Program na vyhľadávanie prvku v jednotlivo prepojenom zozname
• Program na triedenie prvkov jednotlivo prepojeného zoznamu
• Program na výmenu uzlov v jednotlivo prepojenom zozname bez výmeny údajov
• Program na výmenu posledného prvku jednotlivo prepojeného zoznamu za prvý

Programy s dvojitým prepojením

• Program na konverziu daného binárneho stromu na zoznam s dvojitým odkazom
• Program na vytvorenie dvojito prepojeného zoznamu z ternárneho stromu
• Program na vytvorenie dvojito prepojeného zoznamu N uzlov a spočítanie počtu uzlov
• Program na vytvorenie dvojito prepojeného zoznamu N uzlov a jeho zobrazenie v opačnom poradí
• Program na vytvorenie a zobrazenie zoznamu s dvojitým odkazom
• Program na odstránenie nového uzla od začiatku dvojito prepojeného zoznamu
• Program na odstránenie nového uzla z konca zoznamu s dvojitým prepojením
• Program na odstránenie nového uzla zo stredu zoznamu s dvojitým prepojením
• Program na nájdenie uzla maximálnej a minimálnej hodnoty z dvojito prepojeného zoznamu
• Program na vloženie nového uzla na začiatok dvojito prepojeného zoznamu
• Program na vloženie nového uzla na koniec zoznamu s dvojitým prepojením
• Program na vloženie nového uzla do stredu zoznamu s dvojitým prepojením
• Program na odstránenie duplicitných prvkov z dvojito prepojeného zoznamu
• Program na rotáciu dvojito prepojeného zoznamu podľa N uzlov
• Program na vyhľadávanie prvku v dvojito prepojenom zozname
• Program na triedenie prvkov dvojito prepojeného zoznamu

Kruhové programy prepojeného zoznamu

• Program na vytvorenie kruhového prepojeného zoznamu N uzlov a počítanie počtu uzlov
• Program na vytvorenie kruhového prepojeného zoznamu N uzlov a jeho zobrazenie v opačnom poradí
• Program na vytvorenie a zobrazenie kruhového prepojeného zoznamu
• Program na odstránenie nového uzla od začiatku kruhového prepojeného zoznamu
• Program na odstránenie nového uzla z konca kruhového prepojeného zoznamu
• Program na odstránenie nového uzla zo stredu kruhového prepojeného zoznamu
• Program na nájdenie uzla maximálnej a minimálnej hodnoty z kruhového prepojeného zoznamu
• Program na vloženie nového uzla na začiatok kruhového prepojeného zoznamu
• Program na vloženie nového uzla na koniec kruhového prepojeného zoznamu
• Program na vloženie nového uzla do stredu kruhového prepojeného zoznamu
• Program na odstránenie duplicitných prvkov z kruhového prepojeného zoznamu
• Program na vyhľadávanie prvku v kruhovom prepojenom zozname
• Program na triedenie prvkov kruhového prepojeného zoznamu

Stromové programy

• Program na výpočet rozdielu medzi súčtom nepárnych úrovní a párnych úrovní binárneho stromu
• Program na zostavenie binárneho vyhľadávacieho stromu a vykonanie vymazania a prechodu po poradí
• Program na konverziu binárneho stromu na binárny vyhľadávací strom
• Program na zistenie, či sú všetky listy na rovnakej úrovni
• Program na určenie, či sú dva stromy identické
• Program na nájdenie maximálnej šírky binárneho stromu
• Program na nájdenie najväčšieho prvku v binárnom strome
• Program na nájdenie maximálnej hĺbky alebo výšky stromu
• Program na nájdenie uzlov, ktoré sú v maximálnej vzdialenosti v binárnom strome
• Program na nájdenie najmenšieho prvku v binárnom strome
• Program na nájdenie súčtu všetkých uzlov binárneho stromu
• Program na nájdenie celkového počtu možných binárnych vyhľadávacích stromov pomocou N kľúčov
• Program na implementáciu binárneho stromu pomocou prepojeného zoznamu
• Program na vyhľadávanie uzla v binárnom strome

Predpoklad

Predtým, ako sa naučíte Data Structure, musíte mať základné znalosti C.

publikum

Náš návod na štruktúru údajov je navrhnutý tak, aby pomohol začiatočníkom aj profesionálom.

Problém

Uisťujeme vás, že v tomto návode na štruktúru údajov nenájdete žiadny problém. Ak sa však vyskytne nejaká chyba, napíšte ju do kontaktného formulára.