Menu

Úvod do datových struktur v C ++

introduction data structures c

Vyzkoušejte Náš Nástroj Pro Odstranění Problémů

Úvodní kurz o datových strukturách v C ++.

„Datovou strukturu lze definovat jako organizovaný sběr dat, který pomáhá programu přistupovat k datům efektivně a rychle, takže celý program může fungovat efektivně. '

Víme, že ve světě programování jsou data centrem a vše se točí kolem dat. Musíme provádět veškeré datové operace včetně ukládání, vyhledávání, třídění, organizování a přístupu k datům efektivně a teprve potom může náš program uspět.

=> Prohlédněte si úplný seznam výukových programů C ++ zde.

Úvod do datových struktur v C ++ (1)

Co se naučíte:

Přehled

Musíme najít nejúčinnější způsob ukládání dat, který nám pomůže vytvořit dynamická řešení. Při vytváření takových řešení nám pomáhá datová struktura.

Při organizování nebo uspořádání dat do struktur musíme zajistit, aby uspořádání představovalo téměř objekt reálného světa. Zadruhé, toto uspořádání by mělo být dostatečně jednoduché, aby k němu měl kdokoli snadný přístup a mohl jej kdykoli požadovat.

V této sérii se podrobně seznámíme se základní i pokročilou datovou strukturou. Dozvíme se také podrobně o různých technikách vyhledávání a třídění, které lze provádět na datových strukturách.

Po seznámení s touto sérií tutoriálů by se měl čtenář dobře seznámit s každou datovou strukturou a jejím programováním.

Pojďme si projít některé pojmy, které používáme při práci s datovými strukturami:

Například,vzít konkrétního studenta. Student může mít následující podrobnosti, jak je znázorněno na obrázku.

Příklad - datová struktura

  • Data: Je to elementární hodnota. Na výše uvedeném obrázku může být studentem číslo role data.
  • Skupinová položka: Toto je datová položka, která má více než jednu podpoložku. Na výše uvedeném obrázku má Student_name křestní jméno a příjmení.
  • Záznam: Jedná se o kolekci datových položek. Ve výše uvedeném příkladu tvoří datové položky jako číslo role studenta, jméno, třída, věk, hodnocení atd. Společně záznam.
  • Subjekt: Je to třída záznamů. Ve výše uvedeném diagramu je student entita.
  • Atribut nebo pole: Vlastnosti entity se nazývají atributy a každé pole představuje atribut.
  • Soubor: Soubor je sbírka záznamů. Ve výše uvedeném příkladu může mít studentská entita tisíce záznamů. Soubor tedy bude obsahovat všechny tyto záznamy.

Čtenář by si měl být vědom všech těchto pojmů, protože je občas používáme při používání různých datových struktur.

Datové struktury jsou hlavním stavebním kamenem programu a jako programátoři bychom měli být opatrní, jakou datovou strukturu použít. Přesná datová struktura, která se má použít, je nejtěžším rozhodnutím, pokud jde o programování.

Pojďme diskutovat o potřebě datové struktury v programování.

Potřeba datové struktury v programování

Vzhledem k tomu, že množství dat stále roste, aplikace se stávají stále složitějšími, a proto je pro programátora obtížné spravovat tato data i software.

Typicky může aplikace kdykoli čelit následujícím překážkám:

# 1) Hledání velkého množství dat: S velkým množstvím zpracovávaných a ukládaných dat může být náš program kdykoli požádán o vyhledání konkrétních dat. Pokud jsou data příliš velká a nejsou správně uspořádána, získání požadovaných dat bude trvat hodně času.

Když používáme datové struktury k ukládání a organizaci dat, získávání dat se stává rychlejším a snadnějším.

# 2) Rychlost zpracování: Neuspořádaná data mohou mít za následek nízkou rychlost zpracování, protože při načítání a přístupu k datům bude zbytečně mnoho času.

Pokud při ukládání správně uspořádáme data v datové struktuře, nebudeme ztrácet čas aktivitami, jako je načítání, pokaždé je organizujeme. Místo toho se můžeme soustředit na zpracování dat, abychom vytvořili požadovaný výstup.

# 3) Více simultánních požadavků: Mnoho aplikací dnes potřebuje provést současný požadavek na data. Tyto žádosti by měly být zpracovány efektivně, aby aplikace běžely hladce.

Pokud jsou naše data uložena jen náhodně, nebudeme schopni zpracovat všechny souběžné požadavky současně. Je tedy moudré rozhodnutí uspořádat data do správné datové struktury, aby se minimalizovala doba zpracování souběžných požadavků.

Klasifikace datové struktury

Datové struktury používané v C ++ lze klasifikovat následujícím způsobem.

Klasifikace datových struktur

Datová struktura je způsob organizace dat. Můžeme tedy klasifikovat datové struktury, jak je znázorněno, do primitivních nebo standardních datových struktur a neprimitivních nebo uživatelem definovaných datových struktur.

Viděli jsme všechny datové typy podporované v C ++. Jelikož se jedná také o způsob organizace dat, říkáme, že jde o standardní datovou strukturu.

Ostatní datové struktury nejsou primitivní a uživatel je musí před použitím v programu definovat. Tyto uživatelem definované datové struktury se dále dělí na lineární a nelineární datové struktury.

Lineární datová struktura

Lineární datové struktury mají všechny své prvky uspořádané lineárně nebo sekvenčně. Každý prvek v lineární datové struktuře má předchůdce (předchozí prvek) a následníka (další prvek)

Lineární datové struktury se dále dělí na statické a dynamické datové struktury. Statické datové struktury mají obvykle pevnou velikost a jakmile je jejich velikost deklarována v době kompilace, nelze ji změnit. Dynamické datové struktury mohou dynamicky měnit svou velikost a přizpůsobit se.

Nejpopulárnějším příkladem lineární statické datové struktury je pole.

Pole

Pole je sekvenční kolekce prvků stejného typu. Ke každému prvku pole lze přistupovat pomocí jeho polohy v poli, která se nazývá index nebo dolní index pole. Název pole odkazuje na první prvek v poli.

pole

Výše uvedené je pole ‚a 'z n prvků. Prvky jsou očíslovány od 0 do n-1. Velikost pole (v tomto případě n) se také nazývá dimenze pole. Jak je znázorněno na výše uvedeném obrázku, název pole odkazuje na první prvek pole.

Pole je nejjednodušší datovou strukturou a je efektivní, protože k prvkům lze přistupovat přímo pomocí dolních indexů. Chceme-li získat přístup k třetímu prvku v poli, musíme říct pouze (2).

Přidání nebo odstranění prvků pole je ale obtížné. Proto používáme pole pouze v jednoduchých aplikacích nebo v aplikacích, kde není vyžadováno přidávání / mazání prvků.

Populární lineární dynamické datové struktury jsou propojeny seznam, zásobník a fronta.

Spojový seznam

Propojený seznam je kolekce uzlů. Každý uzel obsahuje datový prvek a ukazatel na další uzel. Uzly lze přidávat a mazat dynamicky. Propojený seznam může být jednotlivě propojený seznam, ve kterém má každý uzel ukazatel pouze na další prvek. U posledního prvku je další ukazatel nastaven na null.

V seznamu s dvojnásobným propojením má každý uzel dva ukazatele, jeden na předchozí uzel a druhý na další uzel. Pro první uzel je předchozí ukazatel null a pro poslední uzel je další ukazatel null.

Spojový seznam

Jak je znázorněno na obrázku výše, začátek seznamu se nazývá hlava, zatímco konec propojeného seznamu se nazývá ocas. Jak je uvedeno výše, každý uzel má ukazatel na další prvek. Můžeme snadno přidat nebo odstranit prvky změnou ukazatele na další uzel.

Zásobník

Zásobník je lineární datová struktura, ve které lze prvky přidávat nebo odebírat pouze z jednoho konce známého jako „Horní část“ zásobníku. Tímto způsobem zásobník vykazuje typ přístupu do paměti typu LIFO (Last In, First Out).

Zásobník

Jak je uvedeno výše, prvky v zásobníku jsou vždy přidány na jednom konci a také odebrány ze stejného konce. Tomu se říká „Top“ zásobníku. Když je prvek přidán, posune se dolů do zásobníku a horní část zásobníku se zvýší o jednu pozici.

Podobně, když je prvek odstraněn, horní část zásobníku se sníží. Když je zásobník prázdný, horní část zásobníku je nastavena na -1. Na zásobníku jsou prováděny dvě hlavní operace „Push“ a „Pop“.

Fronta

Fronta je další lineární datovou strukturou, ve které jsou prvky přidávány na jednom konci zvaném „vzadu“ a odstraněny z jiného konce zvaného „vpředu“. Fronta demonstruje FIFO (First In, First Out) typ metodiky přístupu do paměti.

Fronta

Výše uvedený diagram ukazuje frontu se zadním a předním koncem. Když je fronta prázdná, zadní a přední ukazatel se shodují.

Nelineární datová struktura

V nelineárních datových strukturách nejsou data uspořádána postupně, místo toho jsou uspořádána nelineárně. Prvky jsou navzájem spojeny v nelineárním uspořádání.

Nelineární datové struktury jsou stromy a grafy.

Otázky a odpovědi k rozhovoru se zbytkem API

Stromy

Stromy jsou nelineární víceúrovňové datové struktury, které mají hierarchický vztah mezi prvky. Prvky stromu se nazývají Uzly.

Uzel nahoře se nazývá kořen stromu. Kořenový adresář může mít jeden nebo více podřízených uzlů. Následující uzly mohou mít také jeden nebo více podřízených uzlů. Uzly, které nemají podřízené uzly, se nazývají listové uzly.

Stromy

Ve výše uvedeném diagramu jsme ukázali strom se 6 uzly. Z těchto tří uzlů jsou uzly listu, jeden nejvyšší uzel je kořen a ostatní jsou podřízené uzly. V závislosti na počtu uzlů, podřízených uzlech atd. Nebo na vztahu mezi uzly máme různé typy stromů.

Grafy

Graf je sada uzlů s názvem vrcholy vzájemně propojeny pomocí volaných odkazů Hrany . Grafy mohou mít uvnitř cyklus, tj. Stejný vrchol může být výchozím i koncovým bodem konkrétní cesty. Stromy nikdy nemohou mít cyklus.

Grafy

Výše uvedený diagram je neorientovaný graf. Můžeme mít také směrované grafy, kde hrany reprezentujeme pomocí směrovaných šipek.

Operace s datovou strukturou

Všechny datové struktury provádějí na svých prvcích různé operace.

Jsou společné pro všechny datové struktury a jsou uvedeny takto:

  • Hledání: Tato operace se provádí k vyhledání konkrétního prvku nebo klíče. Nejběžnějšími vyhledávacími algoritmy jsou sekvenční / lineární vyhledávání a binární vyhledávání.
  • Třídění: Operace řazení zahrnuje uspořádání prvků v datové struktuře v určitém pořadí vzestupně nebo sestupně. Pro datové struktury jsou k dispozici různé třídicí algoritmy. Mezi nejoblíbenější patří Quicksort, Selection sort, Merge sort atd.
  • Vložení: Operace vložení se zabývá přidáním prvku do datové struktury. Toto je nejdůležitější operace a v důsledku přidání prvku se změní uspořádání a musíme se postarat o to, aby datová struktura zůstala nedotčena.
  • Vymazání: Operace odstranění odstraní prvek z datové struktury. Stejné podmínky, které je třeba vzít v úvahu pro vložení, musí být splněny také v případě operace odstranění.
  • Traverzování: Říkáme, že procházíme datovou strukturou, když navštěvujeme každý prvek ve struktuře. Pro provedení určitých specifických operací s datovou strukturou je nutný pohyb.

V našich následujících tématech se nejprve naučíme různé techniky vyhledávání a řazení, které se mají provádět na datových strukturách.

Výhody datové struktury

  • Abstrakce: Datové struktury jsou často implementovány jako abstraktní datové typy. Uživatelé přistupují pouze k jeho vnějšímu rozhraní bez obav o základní implementaci. Datová struktura tedy poskytuje vrstvu abstrakce.
  • Účinnost: Správná organizace dat vede k efektivnímu přístupu k datům a tím k zefektivnění programů. Zadruhé můžeme vybrat správnou datovou strukturu v závislosti na našich požadavcích.
  • Opakovaná použitelnost: Můžeme znovu použít datové struktury, které jsme navrhli. Mohou být také zkompilovány do knihovny a distribuovány klientovi.

Závěr

S tímto uzavíráme tento návod na úvod do datových struktur. Stručně jsme v tomto kurzu představili každou z datových struktur.

V našich dalších výukách prozkoumáme více o datových strukturách spolu s různými technikami vyhledávání a třídění.

=> Klikněte sem a získejte Absolute C ++ Training Series.

Doporučené čtení

^