Od vynálezu počítačov ľudia používajú výraz „ Údaje “ označuje informácie o počítači, prenášané alebo uložené. Existujú však údaje, ktoré existujú aj v typoch objednávok. Dáta môžu byť čísla alebo texty napísané na kúsku papiera vo forme bitov a bajtov uložených v pamäti elektronických zariadení alebo fakty uložené v mysli človeka. Keď sa svet začal modernizovať, tieto údaje sa stali dôležitým aspektom každodenného života každého človeka a rôzne implementácie im umožnili ukladať ich inak.

Údaje je súbor faktov a čísel alebo súbor hodnôt alebo hodnôt špecifického formátu, ktorý sa vzťahuje na jeden súbor hodnôt položiek. Dátové položky sa potom klasifikujú do podpoložiek, čo je skupina položiek, ktoré nie sú známe ako jednoduchá primárna forma položky.

Uvažujme o príklade, kde možno meno zamestnanca rozdeliť na tri podpoložky: First, Middle a Last. ID pridelené zamestnancovi sa však vo všeobecnosti bude považovať za jednu položku.

Postava 1: Reprezentácia dátových položiek

Vo vyššie uvedenom príklade sú položky ako IČO, Vek, Pohlavie, Prvý, Stred, Posledný, Ulica, Lokalita atď. Naproti tomu Meno a Adresa sú skupinové dátové položky.

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

Dátová štruktúra je odbor informatiky. Štúdium štruktúry údajov nám umožňuje pochopiť organizáciu údajov a riadenie toku údajov s cieľom zvýšiť efektivitu akéhokoľvek procesu alebo programu. Štruktúra údajov je osobitný spôsob ukladania a organizácie údajov v pamäti počítača, takže tieto údaje možno v prípade potreby v budúcnosti ľahko vyhľadať a efektívne využiť. Údaje možno spravovať rôznymi spôsobmi, napríklad logický alebo matematický model pre špecifickú organizáciu údajov je známy ako dátová štruktúra.

Rozsah konkrétneho dátového modelu závisí od dvoch faktorov:

1. Po prvé, musí byť dostatočne načítaný do štruktúry, aby odrážal definitívnu koreláciu údajov s objektom reálneho sveta.
2. Po druhé, formácia by mala byť taká jednoduchá, že sa dá prispôsobiť efektívnemu spracovaniu údajov, kedykoľvek je to potrebné.

Niektoré príklady dátových štruktúr sú polia, prepojené zoznamy, zásobník, front, stromy atď. Dátové štruktúry sa široko používajú takmer vo všetkých aspektoch informatiky, t. j. dizajn kompilátorov, operačné systémy, grafika, umelá inteligencia a mnoho ďalších.

Dátové štruktúry sú hlavnou súčasťou mnohých algoritmov informatiky, pretože umožňujú programátorom efektívne spravovať údaje. Zohráva kľúčovú úlohu pri zlepšovaní výkonu programu alebo softvéru, keďže hlavným cieľom softvéru je čo najrýchlejšie ukladať a získavať údaje používateľa.

sql vyberte z viacerých tabuliek

Základné terminológie súvisiace s dátovými štruktúrami

Dátové štruktúry sú stavebnými kameňmi akéhokoľvek softvéru alebo programu. Výber vhodnej dátovej štruktúry pre program je pre programátora mimoriadne náročná úloha.

Nasleduje niekoľko základných terminológií používaných vždy, keď sú zahrnuté dátové štruktúry:

údaje:Dáta môžeme definovať ako elementárnu hodnotu alebo súbor hodnôt. Napríklad meno a ID zamestnanca sú údaje týkajúce sa zamestnanca.Dátové položky:Jedna jednotka hodnoty je známa ako dátová položka.Položky skupiny:Údajové položky, ktoré majú podriadené údajové položky, sú známe ako skupinové položky. Napríklad meno zamestnanca môže mať meno, stredné a priezvisko.Základné položky:Dátové položky, ktoré sa nedajú rozdeliť na podpoložky, sú známe ako elementárne položky. Napríklad ID zamestnanca.Entita a atribút:Trieda určitých objektov je reprezentovaná entitou. Pozostáva z rôznych atribútov. Každý atribút symbolizuje špecifickú vlastnosť danej entity. Napríklad,

Entity s podobnými atribútmi tvoria an Súprava entít . Každý atribút množiny entít má rozsah hodnôt, množinu všetkých možných hodnôt, ktoré je možné priradiť konkrétnemu atribútu.

Termín „informácia“ sa niekedy používa pre údaje s danými atribútmi zmysluplných alebo spracovaných údajov.

Lúka:Jedna elementárna jednotka informácie symbolizujúca atribút entity je známa ako pole.Záznam:Súbor rôznych údajových položiek sa nazýva záznam. Napríklad, ak hovoríme o zamestnaneckej entite, jej meno, id, adresa a pracovná pozícia môžu byť zoskupené tak, aby vytvorili záznam pre zamestnanca.Súbor:Súbor rôznych záznamov jedného typu entity je známy ako súbor. Ak je napríklad 100 zamestnancov, v súvisiacom súbore bude 25 záznamov obsahujúcich údaje o každom zamestnancovi.

Pochopenie potreby dátových štruktúr

Keďže aplikácie sú čoraz zložitejšie a množstvo údajov sa každým dňom zvyšuje, čo môže viesť k problémom s vyhľadávaním údajov, rýchlosťou spracovania, vybavovaním viacerých požiadaviek a mnohým ďalším. Dátové štruktúry podporujú rôzne metódy na efektívnu organizáciu, správu a ukladanie údajov. Pomocou dátových štruktúr môžeme jednoducho prechádzať dátovými položkami. Dátové štruktúry poskytujú efektívnosť, opätovnú použiteľnosť a abstrakciu.

Prečo by sme sa mali učiť dátové štruktúry?

1. Dátové štruktúry a algoritmy sú dva kľúčové aspekty informatiky.
2. Dátové štruktúry nám umožňujú organizovať a ukladať údaje, zatiaľ čo algoritmy nám umožňujú zmysluplne spracovávať tieto údaje.
3. Učenie sa dátových štruktúr a algoritmov nám pomôže stať sa lepšími programátormi.
4. Budeme schopní napísať kód, ktorý bude efektívnejší a spoľahlivejší.
5. Budeme tiež schopní rýchlejšie a efektívnejšie riešiť problémy.

Pochopenie cieľov dátových štruktúr

Dátové štruktúry spĺňajú dva doplnkové ciele:

správnosť:Dátové štruktúry sú navrhnuté tak, aby správne fungovali pre všetky druhy vstupov na základe oblasti záujmu. Správne povedané, správnosť tvorí primárny cieľ dátovej štruktúry, ktorý vždy závisí od problémov, ktoré má dátová štruktúra riešiť.Účinnosť:Dátové štruktúry tiež vyžadujú, aby boli efektívne. Mal by spracovať údaje rýchlo bez využitia mnohých počítačových zdrojov, ako je pamäťový priestor. V stave v reálnom čase je efektívnosť dátovej štruktúry kľúčovým faktorom pri určovaní úspechu a neúspechu procesu.

Pochopenie niektorých kľúčových funkcií dátových štruktúr

Niektoré z významných funkcií dátových štruktúr sú:

Robustnosť:Vo všeobecnosti sa všetci počítačoví programátori zameriavajú na vytváranie softvéru, ktorý poskytuje správny výstup pre každý možný vstup spolu s efektívnym vykonávaním na všetkých hardvérových platformách. Tento typ robustného softvéru musí spravovať platné aj neplatné vstupy.Prispôsobivosť:Vytváranie softvérových aplikácií, ako sú webové prehliadače, textové procesory a internetový vyhľadávač, zahŕňa obrovské softvérové ​​systémy, ktoré vyžadujú správnu a efektívnu prácu alebo vykonávanie po mnoho rokov. Softvér sa navyše vyvíja v dôsledku nových technológií alebo neustále sa meniacich podmienok na trhu.Opätovná použiteľnosť:Funkcie ako Opätovná použiteľnosť a Prispôsobivosť idú ruka v ruke. Je známe, že programátor potrebuje veľa zdrojov na vytvorenie akéhokoľvek softvéru, čo z neho robí nákladný podnik. Ak je však softvér vyvinutý opakovane použiteľným a prispôsobiteľným spôsobom, potom ho možno použiť vo väčšine budúcich aplikácií. Spustením kvalitných dátových štruktúr je teda možné vytvoriť opätovne použiteľný softvér, ktorý sa javí ako nákladovo efektívny a časovo nenáročný.

Klasifikácia dátových štruktúr

Dátová štruktúra poskytuje štruktúrovaný súbor premenných, ktoré navzájom súvisia rôznymi spôsobmi. Tvorí základ programovacieho nástroja, ktorý označuje vzťah medzi dátovými prvkami a umožňuje programátorom efektívne spracovávať dáta.

Dátové štruktúry môžeme rozdeliť do dvoch kategórií:

1. Primitívna dátová štruktúra
2. Neprimitívna dátová štruktúra

Nasledujúci obrázok zobrazuje rôzne klasifikácie dátových štruktúr.

ako skontrolovať blokované čísla v systéme Android

Obrázok 2: Klasifikácia dátových štruktúr

Primitívne dátové štruktúry

Primitívne dátové štruktúrysú dátové štruktúry pozostávajúce z čísel a znakov, ktoré prichádzajú vstavané do programov.
1. S týmito dátovými štruktúrami možno manipulovať alebo ich ovládať priamo pomocou inštrukcií na úrovni stroja.
2. Základné dátové typy ako napr Integer, Float, Character , a Boolean patria pod primitívne dátové štruktúry.
3. Tieto dátové typy sa tiež nazývajú Jednoduché dátové typy , keďže obsahujú znaky, ktoré sa nedajú ďalej deliť

Neprimitívne dátové štruktúry

Neprimitívne dátové štruktúrysú dátové štruktúry odvodené od primitívnych dátových štruktúr.
1. S týmito dátovými štruktúrami nie je možné manipulovať ani ich priamo ovládať pomocou inštrukcií na úrovni stroja.
2. Zameranie týchto dátových štruktúr je na vytvorenie súboru dátových prvkov, ktoré sú buď homogénne (rovnaký dátový typ) resp heterogénne (rôzne typy údajov).
3. Na základe štruktúry a usporiadania dát môžeme tieto dátové štruktúry rozdeliť do dvoch podkategórií –
   1. Lineárne dátové štruktúry
   2. Nelineárne dátové štruktúry

Lineárne dátové štruktúry

Dátová štruktúra, ktorá zachováva lineárne spojenie medzi svojimi dátovými prvkami, je známa ako lineárna dátová štruktúra. Usporiadanie údajov sa vykonáva lineárne, kde každý prvok pozostáva z nasledovníkov a predchodcov okrem prvého a posledného prvku údajov. V prípade pamäte to však nemusí byť pravda, pretože usporiadanie nemusí byť sekvenčné.

Na základe alokácie pamäte sa lineárne dátové štruktúry ďalej delia na dva typy:

Statické dátové štruktúry:Dátové štruktúry s pevnou veľkosťou sú známe ako statické dátové štruktúry. Pamäť pre tieto dátové štruktúry je pridelená v čase kompilátora a ich veľkosť nemôže používateľ po kompilácii zmeniť; údaje v nich uložené sa však dajú zmeniť.
The Pole je najlepším príkladom štruktúry statických údajov, pretože má pevnú veľkosť a jej údaje možno neskôr upraviť.Dynamické dátové štruktúry:Dátové štruktúry s dynamickou veľkosťou sú známe ako dynamické dátové štruktúry. Pamäť týchto dátových štruktúr je alokovaná v čase spustenia a ich veľkosť sa počas spustenia kódu mení. Okrem toho môže užívateľ zmeniť veľkosť, ako aj dátové prvky uložené v týchto dátových štruktúrach počas behu kódu.
Prepojené zoznamy, zásobníky , a Chvosty sú bežné príklady dynamických dátových štruktúr

Typy lineárnych dátových štruktúr

Nasleduje zoznam lineárnych dátových štruktúr, ktoré bežne používame:

1. Polia

An Pole je dátová štruktúra používaná na zhromažďovanie viacerých dátových prvkov rovnakého dátového typu do jednej premennej. Namiesto ukladania viacerých hodnôt rovnakých dátových typov v samostatných názvoch premenných by sme ich mohli všetky uložiť spolu do jednej premennej. Toto vyhlásenie neznamená, že budeme musieť zjednotiť všetky hodnoty rovnakého typu údajov v akomkoľvek programe do jedného poľa tohto typu údajov. Ale často sa vyskytnú prípady, keď niektoré špecifické premenné rovnakého dátového typu spolu súvisia spôsobom vhodným pre pole.

Pole je zoznam prvkov, kde každý prvok má v zozname jedinečné miesto. Dátové prvky poľa zdieľajú rovnaký názov premennej; každý však nesie iné indexové číslo nazývané dolný index. K akémukoľvek dátovému prvku zo zoznamu môžeme pristupovať pomocou jeho umiestnenia v zozname. Kľúčovou vlastnosťou polí je teda to, že údaje sú uložené v súvislých pamäťových miestach, čo používateľom umožňuje prechádzať cez dátové prvky poľa pomocou ich príslušných indexov.

Obrázok 3. Pole

Polia možno rozdeliť do rôznych typov:

Jednorozmerné pole:Pole s iba jedným riadkom dátových prvkov je známe ako jednorozmerné pole. Je uložený na vzostupnom mieste uloženia.Dvojrozmerné pole:Pole pozostávajúce z viacerých riadkov a stĺpcov dátových prvkov sa nazýva dvojrozmerné pole. Je tiež známy ako Matrix.Multidimenzionálne pole:Multidimenzionálne pole môžeme definovať ako pole polí. Viacrozmerné polia nie sú viazané na dva indexy alebo dve dimenzie, pretože môžu obsahovať toľko indexov, koľko je podľa potreby.

Niektoré aplikácie Array:

1. Môžeme uložiť zoznam dátových prvkov patriacich do rovnakého dátového typu.
2. Pole funguje ako pomocné úložisko pre iné dátové štruktúry.
3. Pole tiež pomáha ukladať dátové prvky binárneho stromu s pevným počtom.
4. Pole funguje aj ako úložisko matíc.

2. Prepojené zoznamy

A Prepojený zoznam je ďalším príkladom lineárnej dátovej štruktúry používanej na dynamické ukladanie kolekcie dátových prvkov. Dátové prvky v tejto dátovej štruktúre sú reprezentované uzlami, ktoré sú spojené pomocou odkazov alebo ukazovateľov. Každý uzol obsahuje dve polia, informačné pole pozostáva zo skutočných údajov a pole ukazovateľa pozostáva z adresy nasledujúcich uzlov v zozname. Ukazovateľ posledného uzla prepojeného zoznamu pozostáva z nulového ukazovateľa, pretože neukazuje na nič. Na rozdiel od polí môže používateľ dynamicky upravovať veľkosť prepojeného zoznamu podľa požiadaviek.

Obrázok 4. Prepojený zoznam

linuxové klávesové skratky

Prepojené zoznamy možno rozdeliť do rôznych typov:

Jednotlivo prepojený zoznam:Jednotlivo prepojený zoznam je najbežnejším typom prepojeného zoznamu. Každý uzol má údaje a pole ukazovateľa obsahujúce adresu nasledujúceho uzla.Dvojito prepojený zoznam:Dvojito prepojený zoznam pozostáva z informačného poľa a dvoch ukazovateľov. Informačné pole obsahuje údaje. Prvé pole ukazovateľa obsahuje adresu predchádzajúceho uzla, zatiaľ čo ďalšie pole ukazovateľa obsahuje odkaz na nasledujúci uzol. Môžeme teda ísť oboma smermi (dozadu aj dopredu).Kruhový prepojený zoznam:Kruhový prepojený zoznam je podobný ako samostatne prepojený zoznam. Jediný kľúčový rozdiel je v tom, že posledný uzol obsahuje adresu prvého uzla, čo tvorí kruhovú slučku v kruhovom prepojenom zozname.

Niektoré aplikácie prepojených zoznamov:

1. Prepojené zoznamy nám pomáhajú implementovať zásobníky, fronty, binárne stromy a grafy vopred definovanej veľkosti.
2. Môžeme tiež implementovať funkciu operačného systému pre dynamickú správu pamäte.
3. Prepojené zoznamy tiež umožňujú implementáciu polynómov pre matematické operácie.
4. Circular Linked List môžeme použiť na implementáciu operačných systémov alebo funkcií aplikácií, ktoré Round Robin vykonávanie úloh.
5. Kruhový prepojený zoznam je tiež užitočný pri prezentácii, kde sa používateľ po zobrazení poslednej snímky vyžaduje vrátiť sa na prvú snímku.
6. Dvojito prepojený zoznam sa používa na implementáciu tlačidiel dopredu a dozadu v prehliadači na pohyb dopredu a dozadu na otvorených stránkach webovej lokality.

3. Hromady

A Stoh je lineárna dátová štruktúra, ktorá nasleduje LIFO (Last In, First Out) princíp, ktorý umožňuje operácie ako vkladanie a vymazávanie z jedného konca zásobníka, t.j. Zásobníky možno implementovať pomocou súvislej pamäte, poľa a nesúvislej pamäte, prepojeného zoznamu. Príklady stackov v reálnom živote sú hromady kníh, balíček kariet, hromady peňazí a mnohé ďalšie.

Obrázok 5. Príklad zásobníka zo skutočného života

Vyššie uvedený obrázok predstavuje skutočný príklad zásobníka, kde sa operácie vykonávajú iba z jedného konca, ako je vkladanie a vyberanie nových kníh z hornej časti zásobníka. Znamená to, že vkladanie a odstraňovanie v zásobníku je možné vykonať iba z hornej časti zásobníka. V danom čase máme prístup len k vrchom zásobníka.

Primárne operácie v zásobníku sú nasledovné:

TAM:Operácia na vloženie nového prvku do zásobníka sa nazýva Push Operation.Pop:Operácia na odstránenie alebo vymazanie prvkov zo zásobníka sa nazýva Pop Operation.

Obrázok 6. Zásobník

Niektoré aplikácie zásobníkov:

1. Zásobník sa používa ako dočasná skladovacia štruktúra pre rekurzívne operácie.
2. Zásobník sa tiež používa ako pomocná skladovacia štruktúra pre volania funkcií, vnorené operácie a odložené/odložené funkcie.
3. Volania funkcií môžeme spravovať pomocou Stacks.
4. Zásobníky sa tiež používajú na vyhodnotenie aritmetických výrazov v rôznych programovacích jazykoch.
5. Zásobníky sú tiež užitočné pri konverzii infixových výrazov na postfixové výrazy.
6. Zásobníky nám umožňujú kontrolovať syntax výrazu v programovacom prostredí.
7. Pomocou Zátvoriek môžeme spárovať zátvorky.
8. Zásobníky možno použiť na obrátenie reťazca.
9. Zásobníky sú užitočné pri riešení problémov na základe spätného sledovania.
10. Hromady môžeme použiť v hĺbkovom vyhľadávaní v grafe a prechádzaní stromov.
11. Zásobníky sa používajú aj vo funkciách operačného systému.
12. Zásobníky sa používajú aj vo funkciách UNDO a REDO pri úprave.

4. Chvosty

A Fronta je lineárna dátová štruktúra podobná zásobníku s určitými obmedzeniami na vkladanie a odstraňovanie prvkov. Vloženie prvku do frontu sa vykonáva na jednom konci a odstránenie sa vykonáva na druhom alebo opačnom konci. Môžeme teda dospieť k záveru, že dátová štruktúra Queue sa riadi princípom FIFO (First In, First Out) na manipuláciu s dátovými prvkami. Implementáciu frontov možno vykonať pomocou polí, prepojených zoznamov alebo zásobníkov. Niektoré príklady frontov v reálnom živote sú rad pri pokladni, eskalátor, umývačka áut a mnoho ďalších.

Obrázok 7. Reálny príklad fronty

Vyššie uvedený obrázok je skutočnou ilustráciou pokladne lístkov do kina, ktorá nám môže pomôcť pochopiť poradie, kde je vždy prvý obslúžený zákazník, ktorý príde ako prvý. Zákazník, ktorý príde ako posledný, bude nepochybne obsluhovaný ako posledný. Oba konce fronty sú otvorené a môžu vykonávať rôzne operácie. Ďalším príkladom je linka s občerstvením, kde je zákazník vložený zozadu, zatiaľ čo zákazník je odstránený na prednej strane po poskytnutí služby, o ktorú požiadal.

Toto sú hlavné operácie frontu:

abeceda čísel

Zaradiť do poradia:Vloženie alebo pridanie niektorých dátových prvkov do frontu sa nazýva Enqueue. Vkladanie prvku sa vždy vykonáva pomocou zadného ukazovateľa.Dequeue:Vymazanie alebo odstránenie dátových prvkov z frontu sa nazýva dequeue. Odstránenie prvku sa vždy vykonáva pomocou predného ukazovateľa.

Obrázok 8. Fronta

Niektoré aplikácie frontov:

1. Fronty sa vo všeobecnosti používajú v operácii šírky vyhľadávania v grafoch.
2. Fronty sa používajú aj v operáciách plánovača úloh operačných systémov, ako je napríklad vyrovnávacia pamäť klávesnice na ukladanie kláves stlačených používateľmi a tlačová vyrovnávacia pamäť na ukladanie dokumentov vytlačených tlačiarňou.
3. Fronty sú zodpovedné za plánovanie CPU, plánovanie úloh a plánovanie disku.
4. Prioritné fronty sa využívajú pri operáciách sťahovania súborov v prehliadači.
5. Fronty sa tiež používajú na prenos údajov medzi periférnymi zariadeniami a CPU.
6. Fronty sú tiež zodpovedné za spracovanie prerušení generovaných používateľskými aplikáciami pre CPU.

Nelineárne dátové štruktúry

Nelineárne dátové štruktúry sú dátové štruktúry, kde dátové prvky nie sú usporiadané v sekvenčnom poradí. Vkladanie a odstraňovanie údajov tu nie je možné lineárnym spôsobom. Medzi jednotlivými dátovými položkami existuje hierarchický vzťah.

Typy nelineárnych dátových štruktúr

Nasleduje zoznam nelineárnych dátových štruktúr, ktoré bežne používame:

1. Stromy

Strom je nelineárna dátová štruktúra a hierarchia obsahujúca kolekciu uzlov tak, že každý uzol stromu ukladá hodnotu a zoznam odkazov na iné uzly ('deti').

Stromová dátová štruktúra je špecializovaná metóda na usporiadanie a zhromažďovanie údajov v počítači, aby sa mohli efektívnejšie využívať. Obsahuje centrálny uzol, štrukturálne uzly a poduzly spojené cez hrany. Môžeme tiež povedať, že štruktúra údajov stromu pozostáva zo spojených koreňov, konárov a listov.

Obrázok 9. Strom

Stromy možno rozdeliť do niekoľkých typov:

Binárny strom:Stromová dátová štruktúra, kde každý nadradený uzol môže mať najviac dve potomky, sa nazýva binárny strom.Binárny vyhľadávací strom:Binárny vyhľadávací strom je stromová dátová štruktúra, v ktorej môžeme ľahko udržiavať triedený zoznam čísel.AVL strom:AVL strom je samovyvažujúci binárny vyhľadávací strom, kde každý uzol uchováva dodatočné informácie známe ako Balančný faktor, ktorého hodnota je buď -1, 0 alebo +1.B-strom:B-strom je špeciálny typ samovyvažujúceho binárneho vyhľadávacieho stromu, kde každý uzol pozostáva z viacerých kľúčov a môže mať viac ako dve deti.

Niektoré aplikácie stromov:

1. Stromy implementujú hierarchické štruktúry v počítačových systémoch, ako sú adresáre a súborové systémy.
2. Stromy sa tiež používajú na implementáciu navigačnej štruktúry webovej stránky.
3. Pomocou Stromov môžeme vygenerovať kód ako Huffmanov kód.
4. Stromy sú tiež nápomocné pri rozhodovaní v herných aplikáciách.
5. Stromy sú zodpovedné za implementáciu prioritných frontov pre funkcie plánovania OS založené na prioritách.
6. Stromy sú tiež zodpovedné za analýzu výrazov a príkazov v kompilátoroch rôznych programovacích jazykov.
7. Stromy môžeme použiť na ukladanie dátových kľúčov na indexovanie pre systém správy databáz (DBMS).
8. Spanning Trees nám umožňuje smerovať rozhodnutia v počítačových a komunikačných sieťach.
9. Stromy sa používajú aj v algoritme hľadania cesty implementovanom v aplikáciách umelej inteligencie (AI), robotiky a videohier.

2. Grafy

Graf je ďalším príkladom nelineárnej dátovej štruktúry, ktorá obsahuje konečný počet uzlov alebo vrcholov a hrán, ktoré ich spájajú. Grafy sa používajú na riešenie problémov reálneho sveta, v ktorom označujú problémovú oblasť ako sieť, ako sú sociálne siete, okruhové siete a telefónne siete. Napríklad uzly alebo vrcholy grafu môžu predstavovať jedného používateľa v telefónnej sieti, zatiaľ čo okraje predstavujú spojenie medzi nimi cez telefón.

Dátová štruktúra grafu G sa považuje za matematickú štruktúru pozostávajúcu zo sady vrcholov V a sady hrán E, ako je uvedené nižšie:

G = (V,E)

Obrázok 10. A Graf

Vyššie uvedený obrázok predstavuje graf, ktorý má sedem vrcholov A, B, C, D, E, F, G a desať hrán [A, B], [A, C], [B, C], [B, D], [B, E], [C, D], [D, E], [D, F], [E, F] a [E, G].

V závislosti od polohy vrcholov a hrán možno grafy rozdeliť do rôznych typov:

Null Graph:Graf s prázdnou množinou hrán sa nazýva nulový graf.Triviálny graf:Graf, ktorý má iba jeden vrchol, sa nazýva triviálny graf.Jednoduchý graf:Graf bez vlastných slučiek ani viacerých hrán je známy ako jednoduchý graf.Viacnásobný graf:Graf sa nazýva Multi, ak pozostáva z viacerých hrán, ale bez vlastných slučiek.Pseudograf:Graf so samoslučkami a viacerými hranami sa nazýva pseudograf.Neorientovaný graf:Graf pozostávajúci z neusmernených hrán je známy ako nesmerovaný graf.Riadený graf:Graf pozostávajúci z nasmerovaných hrán medzi vrcholmi je známy ako smerovaný graf.Pripojený graf:Graf s aspoň jednou cestou medzi každým párom vrcholov sa nazýva pripojený graf.Odpojený graf:Graf, v ktorom neexistuje žiadna cesta medzi aspoň jedným párom vrcholov, sa nazýva Odpojený graf.Bežný graf:Graf, kde všetky vrcholy majú rovnaký stupeň, sa nazýva regulárny graf.Kompletný graf:Graf, v ktorom majú všetky vrcholy hranu medzi každým párom vrcholov, sa nazýva úplný graf.Graf cyklu:O grafe sa hovorí, že je to cyklus, ak má aspoň tri vrcholy a hrany, ktoré tvoria cyklus.Cyklický graf:O grafe sa hovorí, že je cyklický vtedy a len vtedy, ak existuje aspoň jeden cyklus.Acyklický graf:Graf s nulovými cyklami sa nazýva acyklický graf.Konečný graf:Graf s konečným počtom vrcholov a hrán je známy ako konečný graf.Nekonečný graf:Graf s nekonečným počtom vrcholov a hrán je známy ako nekonečný graf.Bipartitný graf:Graf, v ktorom môžu byť vrcholy rozdelené do nezávislých množín A a B a všetky vrcholy množiny A by mali byť spojené len s vrcholmi prítomnými v množine B s niektorými hranami, sa nazýva bipartitný graf.Rovinný graf:O grafe sa hovorí, že je rovinný, ak ho dokážeme nakresliť v jednej rovine s dvoma hranami, ktoré sa navzájom pretínajú.Eulerov graf:O grafe sa hovorí, že je Euler práve vtedy a len vtedy, ak sú všetky vrcholy párne stupne.Hamiltonovský graf:Prepojený graf pozostávajúci z hamiltonovského okruhu je známy ako hamiltonovský graf.

Niektoré aplikácie grafov:

1. Grafy nám pomáhajú reprezentovať trasy a siete v dopravných, cestovateľských a komunikačných aplikáciách.
2. Grafy slúžia na zobrazenie trás v GPS.
3. Grafy nám tiež pomáhajú reprezentovať prepojenia v sociálnych sieťach a iných sieťových aplikáciách.
4. Grafy sa využívajú v mapovacích aplikáciách.
5. Grafy sú zodpovedné za zobrazenie preferencií používateľov v aplikáciách elektronického obchodu.
6. Grafy sa používajú aj v inžinierskych sieťach na identifikáciu problémov, ktorým sú vystavené miestne alebo obecné podniky.
7. Grafy tiež pomáhajú riadiť využitie a dostupnosť zdrojov v organizácii.
8. Grafy sa tiež používajú na vytváranie máp odkazov na dokumenty webových stránok, aby sa zobrazila konektivita medzi stránkami prostredníctvom hypertextových odkazov.
9. Grafy sa používajú aj v robotických pohyboch a neurónových sieťach.

Základné operácie dátových štruktúr

V nasledujúcej časti budeme diskutovať o rôznych typoch operácií, ktoré môžeme vykonávať na manipuláciu s údajmi v každej dátovej štruktúre:

Priebeh:Prechádzať dátovou štruktúrou znamená pristupovať ku každému dátovému prvku presne raz, aby mohol byť spravovaný. Napríklad pri tlači mien všetkých zamestnancov v oddelení sa vyžaduje prechod.Vyhľadávanie:Vyhľadávanie je ďalšia operácia dátovej štruktúry, ktorá znamená nájsť umiestnenie jedného alebo viacerých dátových prvkov, ktoré spĺňajú určité obmedzenia. Takýto dátový prvok môže alebo nemusí byť prítomný v danej množine dátových prvkov. Pomocou operácie vyhľadávania môžeme napríklad nájsť mená všetkých zamestnancov, ktorí majú prax viac ako 5 rokov.Vloženie:Vkladanie znamená vkladanie alebo pridávanie nových dátových prvkov do kolekcie. Operáciu vloženia môžeme použiť napríklad na pridanie údajov o novom zamestnancovi, ktorého spoločnosť nedávno prijala.vymazanie:Vymazanie znamená odstránenie alebo vymazanie konkrétneho dátového prvku z daného zoznamu dátových prvkov. Operáciu vymazania môžeme použiť napríklad na vymazanie mena zamestnanca, ktorý opustil prácu.Triedenie:Triedenie znamená usporiadanie dátových prvkov vo vzostupnom alebo zostupnom poradí v závislosti od typu aplikácie. Operáciu triedenia môžeme použiť napríklad na usporiadanie mien zamestnancov v oddelení v abecednom poradí alebo na odhadnutie troch najlepších výkonov v mesiaci usporiadaním výkonov zamestnancov v zostupnom poradí a extrahovaním podrobností o troch najlepších.Zlúčiť:Zlúčiť znamená spojiť dátové prvky dvoch zoradených zoznamov, aby sa vytvoril jeden zoznam zoradených dátových prvkov.Vytvoriť:Create je operácia používaná na rezervovanie pamäte pre dátové prvky programu. Túto operáciu môžeme vykonať pomocou deklaračného príkazu. Vytvorenie dátovej štruktúry môže prebiehať buď počas:
1. Čas kompilácie
2. Beh programu
   Napríklad, malloc() funkcia sa používa v jazyku C na vytvorenie dátovej štruktúry.
Výber:Výber znamená výber konkrétneho údaja z dostupných údajov. Môžeme vybrať akékoľvek konkrétne údaje zadaním podmienok vo vnútri slučky.Aktualizácia:Operácia Aktualizácia nám umožňuje aktualizovať alebo upravovať údaje v dátovej štruktúre. Akékoľvek konkrétne údaje môžeme aktualizovať aj zadaním niektorých podmienok v rámci cyklu, ako je operácia výberu.Rozdelenie:Operácia Splitting nám umožňuje rozdeliť dáta do rôznych podčastí, čím sa skráti celkový čas dokončenia procesu.

Pochopenie abstraktného typu údajov

Podľa Národný inštitút pre štandardy a technológie (NIST) dátová štruktúra je usporiadanie informácií, zvyčajne v pamäti, pre lepšiu účinnosť algoritmu. Dátové štruktúry zahŕňajú prepojené zoznamy, zásobníky, fronty, stromy a slovníky. Môže ísť aj o teoretickú entitu, napríklad meno a adresu osoby.

Z vyššie uvedenej definície môžeme konštatovať, že operácie v dátovej štruktúre zahŕňajú:

1. Vysoká úroveň abstrakcií, ako je pridanie alebo vymazanie položky zo zoznamu.
2. Vyhľadávanie a triedenie položky v zozname.
3. Prístup k položke s najvyššou prioritou v zozname.

Kedykoľvek dátová štruktúra vykonáva takéto operácie, je známa ako an Abstraktný typ údajov (ADT) .

Môžeme ho definovať ako množinu dátových prvkov spolu s operáciami s dátami. Pojem „abstrakt“ sa vzťahuje na skutočnosť, že údaje a základné operácie na nich definované sa skúmajú nezávisle od ich implementácie. Zahŕňa to, čo môžeme urobiť s údajmi, nie ako to môžeme urobiť.

Implementácia ADI obsahuje štruktúru úložného priestoru na uloženie dátových prvkov a algoritmov pre základnú prevádzku. Všetky dátové štruktúry, ako je pole, prepojený zoznam, front, zásobník atď., sú príkladmi ADT.

zoznam uzlov v jazyku Java

Pochopenie výhod používania ADT

V skutočnom svete sa programy vyvíjajú ako dôsledok nových obmedzení alebo požiadaviek, takže úprava programu vo všeobecnosti vyžaduje zmenu v jednej alebo viacerých dátových štruktúrach. Predpokladajme napríklad, že chceme vložiť nové pole do záznamu zamestnanca, aby sme mali prehľad o ďalších podrobnostiach o každom zamestnancovi. V takom prípade môžeme zvýšiť efektivitu programu nahradením poľa prepojenou štruktúrou. V takejto situácii je prepisovanie každej procedúry, ktorá využíva upravenú štruktúru, nevhodné. Preto je lepšou alternatívou oddelenie dátovej štruktúry od jej implementačných informácií. Toto je princíp používania abstraktných dátových typov (ADT).

Niektoré aplikácie dátových štruktúr

Nasledujú niektoré aplikácie dátových štruktúr:

1. Dátové štruktúry pomáhajú pri organizácii údajov v pamäti počítača.
2. Dátové štruktúry tiež pomáhajú pri reprezentácii informácií v databázach.
3. Dátové štruktúry umožňujú implementáciu algoritmov na vyhľadávanie údajov (napríklad vyhľadávací nástroj).
4. Dátové štruktúry môžeme použiť na implementáciu algoritmov na manipuláciu s údajmi (napríklad textové procesory).
5. Môžeme tiež implementovať algoritmy na analýzu údajov pomocou dátových štruktúr (napríklad dataminers).
6. Dátové štruktúry podporujú algoritmy na generovanie údajov (napríklad generátor náhodných čísel).
7. Dátové štruktúry tiež podporujú algoritmy na kompresiu a dekompresiu údajov (napríklad pomôcka zip).
8. Dátové štruktúry môžeme použiť aj na implementáciu algoritmov na šifrovanie a dešifrovanie údajov (napríklad bezpečnostný systém).
9. Pomocou Data Structures môžeme vytvoriť softvér, ktorý dokáže spravovať súbory a adresáre (napríklad správca súborov).
10. Môžeme tiež vyvinúť softvér, ktorý dokáže vykresliť grafiku pomocou dátových štruktúr. (Napríklad webový prehliadač alebo softvér na vykresľovanie 3D).

Okrem tých, ako už bolo spomenuté, existuje mnoho ďalších aplikácií dátových štruktúr, ktoré nám môžu pomôcť vytvoriť akýkoľvek požadovaný softvér.