Co jsou datové struktury?

Datová struktura je softwarová jednotka, která umožňuje ukládat a zpracovávat spoustu stejných nebo logicky souvisejících informací v počítačích. Pokud chcete přidat, najít, upravit nebo odstranit informace, bude struktura poskytovat konkrétní balíček možností, což je její rozhraní.

Co obsahuje pojem datové struktury?

Tento termín může mít několik blízkých, ale stále výrazných významů. Jedná se o:

• abstraktní typ;
• implementace abstraktního typu informací;
• Instance datového typu, například konkrétní seznam.

Pokud budeme hovořit o struktuře dat v rámci funkcionálního programování, je to speciální jednotka, která je uložena se změnami. Může být popsán neformálně jako samostatná struktura, přestože mohou existovat různé verze.

Co tvoří strukturu?

Datová struktura se vytváří pomocí typů informací, odkazů a operací na nich v určitém programovacím jazyce. Říká se, že různé typy konstrukcí jsou vhodné pro různé aplikace, některé, například mají velmi úzkou specializaci, a jsou vhodné pro výrobu stanovených cílů pouze.

Pokud vezmeme B-stromy, pak jsou obvykle vhodné pro tvorbu databází a pouze pro ně. Ve stejnou dobu se hash desky používají v širším měřítku v praxi vytvořit různé slovníky, například prokázat názvy domén na internetové adrese PC, a to nejen pro vytvoření základů.

Při vývoji konkrétního softwaru závisí složitost implementace a kvalita funkčnosti programů přímo od správné aplikace datových struktur. Takové chápání věcí dala impuls k rozvoji formálních metod rozvoje a programovacích jazyků, kde je struktura, spíše než algoritmy jsou uváděny na přední pozici v softwarové architektury.

Je třeba poznamenat, že mnoho programovacích jazyků má zavedený typ modularity, který umožňuje, aby byly datové struktury bezpečně použity v různých aplikacích. Silnými příklady jsou jazyky Java, C # a C ++. Nyní je klasická struktura použitých dat prezentována ve standardních knihovnách programovacích jazyků nebo přímo je již zabudována do samotného jazyka. Například tato struktura hash tabulky je vestavěna do Lua, Pythonu, Perl, Ruby, Tcl a dalších. Standardní knihovna šablon v jazyce C ++ je široce používána.

Strukturu porovnáváme v funkčním a imperativním programování

Mělo by být okamžitě stanoveno, že je obtížnější navrhnout struktury pro funkční jazyky než pro imperativní jazyky, přinejmenším existují dva důvody:

1. Ve skutečnosti všechny struktury často používají přiřazení v praxi, které se nepoužívá v čistě funkčním stylu.
2. Funkční struktury jsou flexibilní systémy. Při imperativní programování jsou starší verze jednoduše nahrazeny novými verzemi, ale ve funkčním programování funguje všechno, co funguje. Jinými slovy, v imperativní programovací struktury jsou pomíjivé a funkční jsou trvalé.

Co obsahuje struktura?

Často jsou data, s nimiž programy pracují, uložena v polích vestavěných v programovacím jazyce, konstantě nebo v proměnné délce. Pole je jednoduchá struktura s informacemi, ale některé úkoly vyžadují větší účinnost některých operací, proto se používají další struktury (složitější).

Nejjednodušší pole vhodné pro časté odkazy na součásti namontované na indexy a jejich změn, a odstranit položky z poloviny hlavních funkcí O (N) O (N). Pokud potřebujete odstranit položky k vyřešení konkrétních úloh, budete muset použít jinou strukturu. Například binární strom (std :: set) umožňuje to na O (LOGN) O (log⁡N), ale nepracuje s indexy prováděny výhradně alternativní obchvatu prvky a jejich hledání smyslu. Tak lze říci, že struktura se liší v operacích, které je schopna provádět, stejně jako rychlost jejich výroby. Zvažte například nejjednodušší struktury, které neposkytují zisky efektivity, ale mají dobře definovaný soubor podporovaných operací.

Stack

Jedná se o jeden z typů datových struktur reprezentovaných ve formě omezeného elementárního pole. Klasický zásobník podporuje pouze tři možnosti:

• Přidání prvku do zásobníku (Složitost: O (1) O (1)).
• Vyjmutí položky ze zásobníku (Složitost: O (1) O (1)).
• Zkontrolujte, zda je zásobník prázdný nebo ne (Složitost: O (1) O (1)).

Chcete-li objasnit princip zásobníku, můžete v praxi aplikovat analogii s nádobou cookie. Představte si, že na dně nádoby leží několik sušenek. Nahoře můžete dát pár kusů, nebo můžete naopak vzít jeden cookie z vrcholu. Zbývající soubory cookie budou uzavřeny špičkou a o nich nic nevíte. To je případ zásobníku. Pro popis pojmů používaných akronym LIFO (poslední dovnitř, první ven), který zdůrazňuje, že zásobník složka chycen uvnitř druhé, je první dobře a zpět z nich.

Frontu

Jedná se o jiný typ datové struktury, která podporuje stejnou sadu možností jako zásobník, ale má opačný sémantiku. Při popisu fronty je použita zkratka FIFO (First In, First Out), protože prvně přidaný prvek je nejprve extrahován. Název struktury mluví sám o sobě - ​​princip práce se zcela shoduje s frontami, které lze vidět v obchodě, v supermarketu.

Prosinec

Jedná se o jiný druh datové struktury, který se nazývá také fronta s dvěma konci. Tato volba podporuje následující sadu operací:

• Přidání prvku na začátek (Složitost: O (1) O (1)).
• Výpis komponenty od začátku (Složitost: O (1) O (1)).
• Přidání prvku na konec (Složitost: O (1) O (1)).
• Odběr prvku od konce (Složitost: O (1) O (1)).
• Zkontrolujte, zda jsou paluby prázdné (Složitost: O (1) O (1)).

Seznamy

Tato datová struktura definuje sekvenci lineárně souvisejících komponent, pro které jsou povoleny a smazány operace přidávání komponent do libovolného místa v seznamu. Lineární seznam je určen ukazatelem na začátek seznamu. Typické operace na seznamech: objížďka vyhledávání pro určitou složku, vkládání a mazání komponentu, který kombinuje dva seznamy do jednoho celku, rozpis seznamu pro páru, a tak dále. Za zmínku stojí, že v lineárním seznamu je vedle prvního prvku i předchozí složka pro každý prvek, bez poslední. To znamená, že komponenty seznamu jsou v uspořádaném stavu. Ano, zpracovávání takového seznamu není vždy výhodné, protože neexistuje možnost pohybu v opačném směru - od konce seznamu až po začátek. V lineárním seznamu však můžete projít všechny komponenty krok za krokem.

K dispozici jsou také kruhy. Je to stejná struktura jako lineární seznam, ale má další spojení mezi první a poslední komponentou. Jinými slovy, další komponentou je první složka.

V tomto seznamu jsou prvky stejné. Přiřazení prvního a posledního je podmíněnost.

Stromy

Tato kombinace složek, které jsou označovány jako uzly, což je hlavní (a) složku ve tvaru kořene a všechny zbývající rozdělen do většího počtu disjunktní prvků. Každý soubor je strom a kořen každého stromu je potomkem kořenového stromu. Jinými slovy, všechny komponenty jsou spojeny vztahem předchůdce a dítěte. V důsledku toho můžete sledovat hierarchickou strukturu uzlů. Pokud uzly nemají potomka, jsou nazývány listy. Nad stromem jsou definovány operace, jako je přidání součásti a její mazání, procházení a hledání komponenty. Zvláštní roli v informatice hrají binární stromy. Co to je? Jedná se o zvláštní případ stromu, kde každý uzel nemůže mít víc než dvojici potomků, které jsou kořeny levého a pravého podstromu. Pokud se vedle uzlů stromu je prováděno další podmínku, že všechny hodnoty složek v levém podstromu je menší než hodnoty kořenových a hodnoty složek pravý podstrom větší kořen, strom se nazývá binární vyhledávací strom, a je navržen tak, aby rychle najít položky. Jak funguje vyhledávací algoritmus v tomto případě? Vyhledávací hodnota je porovnána s kořenovou hodnotou a podle výsledku vyhledávání buď končí, nebo pokračuje, ale výhradně v levém nebo pravém podstromu. Celkový počet porovnávacích operací nepřesáhne výšku stromu (to je největší počet komponent na cestě od kořene k jednomu z listů).

Grafy

Grafy jsou sbírka komponent, které se nazývají vrcholy, spolu s souborem vztahů mezi těmito vrcholy, které se nazývají okraje. Grafický výklad této struktury je reprezentován jako soubor bodů, které jsou odpovědné za horní a některé páry jsou spojeny čarami nebo šipkami, což odpovídá žebrům. Poslední případ naznačuje, že graf by měl být volán orientovaný.

Grafy mohou popisovat objekty jakékoli struktury, jsou hlavním prostředkem pro popis komplexních struktur a fungování všech systémů.

Více informací o abstraktní struktuře

Chcete-li vytvořit algoritmus, je třeba formalizovat data, nebo jinými slovy musíte data přenést na konkrétní informační model, který již byl prozkoumán a napsán. Jakmile je model nalezen, lze tvrdit, že je vytvořena abstraktní struktura.

Jedná se o hlavní datovou strukturu, která zobrazuje atributy, kvalitu objektu, vztah mezi součástmi objektu a operace, kterou lze provést přes něj. Hlavním úkolem je najít a zobrazit formuláře pro prezentaci informací, které jsou pohodlné pro opravu počítače. Za zmínku stojí i to, že informatika jako přesná věda jedná s formálními objekty.

Analýza datových struktur se provádí těmito předměty:

• Celá čísla a reálná čísla.
• Booleovské hodnoty.
• Symboly.

Pro zpracování všech prvků v počítači existují odpovídající algoritmy a datové struktury. Typické objekty lze kombinovat do složitých struktur. Na ně můžete přidat operace, pravidla pro určité součásti této struktury.

Struktura datové organizace zahrnuje:

• Vektory.
• Dynamické struktury.
• Tabulky.
• Multidimenzionální pole.
• Počítá.

Pokud budou všechny prvky úspěšně vybrány, bude to klíčem k vytvoření efektivních algoritmů a datových struktur. Pokud aplikujete analogii struktur a reálných objektů v praxi, můžete efektivně řešit stávající problémy.

Za zmínku stojí, že všechny struktury organizace dat existují samostatně v programování. Nad nimi se v osmnáctém a devatenáctém století hodně začalo pracovat, kdy ještě nebyl vidět žádný počítač.

Možné vyvinout algoritmus, pokud jde o abstraktních struktur, ale implementovat algoritmus v určitém programovacím jazyce je nutné najít techniku ​​pro její výkon v datové typy, operátory, které jsou podporovány konkrétním programovacím jazyku. Pro vytvoření struktury, jako je vektor, znak, řetězec sekvence v mnoha programovacích jazycích, jsou klasické typy dat: jednorozměrné nebo dvourozměrné pole, soubor řetězec.

Jaké jsou metodická doporučení pro práci se strukturami?

Zachytili jsme vlastnosti datových struktur, nyní bychom měli věnovat větší pozornost pochopení koncepce struktury. Při řešení absolutně jakéhokoli problému je nutné pracovat s některými daty pro provádění operací s informacemi. Každý úkol má vlastní sadu operací, ale určitá sada se v praxi častěji používá k řešení různých úkolů. V tomto případě je užitečné přijít s určitým způsobem organizování informací, které umožní tyto operace provádět co nejúčinněji. Jakmile se taková metoda objeví, můžete předpokládat, že máte "černou schránku", ve které budou uloženy údaje určitého druhu a které budou provádět určité datové operace. To odvádí detaily a plně se soustřeďuje na charakteristické rysy problému. Tato "černá skříňka" může být provedena jakýmkoli způsobem, zatímco je třeba usilovat o co možná největší produktivní realizaci.

Kdo to potřebuje vědět?

Známí programátoři, kteří chtějí najít své místo v této oblasti, jsou obeznámeni s informacemi, ale nevědí, kam jít. To jsou základy každého programovacího jazyka, takže nebude nadbytečné se okamžitě naučit o datových strukturách a poté, co s nimi pracujete na konkrétních příkladech a konkrétním jazyce. Nemělo by se zapomínat na to, že každá struktura může být charakterizována logickými a fyzickými reprezentacemi, stejně jako souborem operací na těchto reprezentacích.

Nezapomeňte: pokud mluvíte o konkrétní struktuře, pak pamatujte na její logické zastoupení, protože fyzická reprezentace je zcela "skrytá" od "externího pozorovatele".

Navíc si pamatujte, že logická reprezentace je zcela nezávislá na programovacím jazyce a počítači a fyzická reprezentace naopak závisí na překladatelích a počítačích. Například dvojrozměrné pole ve formátech Fortran a Pascal může být zastoupeno stejným způsobem a fyzická reprezentace ve stejném počítači v těchto jazycích se bude lišit.

Nespěchejte, abyste začali učit konkrétní struktury, je nejlepší porozumět jejich klasifikaci, seznámit se se všemi teoreticky a nejlépe v praxi. Stojí za zmínku, že variabilita je důležitou vlastností struktury a naznačuje statickou, dynamickou nebo polostatickou situaci. Naučte se základy dříve, než začnete s více globálními věcmi, což vám pomůže v budoucím vývoji.