Datové struktury a algoritmy C ++
Datové struktury a algoritmy C ++ - znamená uspořádání nebo uspořádání prvků určitým způsobem. Když říkáme, že musíme uspořádat prvky, mohou být tyto prvky uspořádány do různých forem. Například ponožky mohou být uspořádány různými způsoby. Stačí si to nechat ve své skříni a všechno zmatené. Nebo to můžete udržovat úhledně složené. Nejlepší způsob může být skládání a uspořádání barev. Takže pro hledání určité dvojice ponožek je třetí uspořádání perfektní.
Podobným způsobem organizace ponožek lze Data také uspořádat různými způsoby nebo formami. Tyto různé způsoby organizace dat se nazývají struktura dat. Podívejme se na formální definici datové struktury a základů datových struktur a algoritmů.
Datové struktury a algoritmy C ++:
Logický nebo matematický model konkrétní organizace dat.
NEBO
Jedná se o zvláštní způsob uspořádání dat v počítači, aby bylo možné je použít.
Podobně jako ponožky; jiná organizace seznamových datových struktur a algoritmů C ++ je -
- Pole
- Spojový seznam
- Zásobník
- Fronta
- Strom
- Graf
- Hash Table
- Halda
- Evidence
- Tabulky
Tyto datové struktury a algoritmy C ++ jsou při programování velmi důležité. Dobrý programátor vždy klade důraz spíše na strukturu dat než na kód. Každý programovací jazyk pracuje na různých datových strukturách a algoritmech v C ++. Datové struktury dostupné v C ++ jsou následující.
- Pole
- Spojový seznam
- Zásobník
- Fronta
- Strom
- Graf
- Hash Table
- Halda
Pojďme si to projednat jeden po druhém:
# 1 Pole
Pole je nejjednodušší typ datových struktur a algoritmů C ++. Pole je definováno jako sekvenční kolekce datových prvků stejného typu s pevnou velikostí. Např. A0 = 12, a1 = 21, a2 = 14, a3 = 15…. Můžeme reprezentovat jednorozměrné pole, jak je znázorněno na obrázku:
Kde
0, 1, 2, 3… ..n se nazývá index nebo index
a (1), a (2), … a (n) se nazývá indexová proměnná
Může to být 1-rozměrný, 2-rozměrný, 3-rozměrný a tak dále vícerozměrný.
V paměťovém poli se ukládají do sousedících paměťových umístění.
Nejnižší adresa odpovídá prvnímu prvku
Nejvyšší adresa odpovídá poslednímu prvku
Můžeme deklarovat 1-D (1-rozměrné) pole v C ++ následovně
dataType arrayName (arraySize);
Např. Int číslo (5);
Inicializace pole v C ++
num = (23, 10, 12, 3, 6);
Deklaraci a inicializaci můžeme kombinovat do jednoho prohlášení následovně.
int num = (23, 10, 12, 3, 6);
Pokud chceme dynamicky alokovat velikost pole, měli bychom nový operátor následovat
int * a = new int (velikost);
Nevýhodou pole je vkládání a mazání prvků je pomalé jako v uspořádaném poli a jeho pevné velikosti.
# 2 Propojený seznam
Seznam odkazuje na lineární sbírku položek. Propojený seznam je řada spojených uzlů (datový prvek), jak je znázorněno na obrázku 3. Uzel záhlaví ukazuje na první uzel seznamu a poslední uzel ukazuje na NULL označenýÆ. Protože každý uzel obsahuje alespoň.
- Část dat (jakýkoli typ)
- Ukazatel na další uzel v seznamu
Propojený seznam je reprezentován v paměti pomocí dvou polí. Jedno pole ukládá informace nazvané info, která jsou data, která mají být uložena, a další ukládá pole s dalším ukazatelem nazvané LINK, což je adresa dalšího uzlu.
Výhodou propojeného seznamu v poli:
Pole i propojený seznam představují reprezentaci seznamu položek v paměti. Důležitým rozdílem je způsob, jakým jsou položky propojeny. Hlavním omezením pole je vložení prvku do pole a odstranění prvku z uspořádaného pole je obtížné, protože ostatní prvky musí být přesunuty. Vkládání a mazání prvků z propojeného seznamu je velmi jednoduché.
Naučte se navrhovat a přizpůsobovat programy pro různé platformy. Kódování, testování, ladění a implementace softwarových aplikací. Rozvíjejte dovednosti, které zajistí hladký chod aplikací.
Typy propojeného seznamu jsou:
1. Seznam jednotlivě propojených : obsahuje pouze jedno propojené pole, které obsahuje adresu dalšího uzlu v seznamu, a podané informace, které obsahují informace, které mají být uloženy.
2. Jeden kruhový propojený seznam je pouze jeden seznam, ale poslední uzel seznamu obsahuje adresu prvního uzlu místo nulové. To je obsah hlavičky a další pole posledního uzlu jsou stejné.
3. Dvojitě propojený seznam obsahuje dvě propojená pole předchozí a následující. Dříve propojené pole, které drží adresu předchozího uzlu v seznamu, a další propojené pole drží adresu dalšího uzlu v seznamu a uložené informace drží informace jako úložiště.
4. Double Circular Connected List je dvojitě propojený seznam, ale další pole posledního uzlu obsahuje adresu prvního uzlu namísto null.
Doporučené kurzy
- Kurz na VB.NET
- Školení programování datových věd
- Online kurz ISTQB
- Školicí kurz Kali Linux
Implementace propojeného seznamu v C ++ zahrnuje vytvoření uzlu, vymazání uzlu ze seznamu, vložení nově vytvořeného uzlu do seznamu a prohledání uzlu pomocí konkrétního klíče.
Kód pro vytvoření uzlu je uveden následovně:
Vložení uzlu do seznamu zahrnuje tři případy
1. Vložení uzlu na začátek znamená vložení nově vytvořeného uzlu jako počátečního uzlu. Pro vložení uzlu na začátku nejprve vytvořte nový uzel a vytvořte nový bod uzlu na starý začátek a poté začněte aktualizovat začátek tak, aby ukazoval na nový uzel, jak je znázorněno na obrázku níže:
Kód pro vložení uzlu na začátku:
2. Vložení uzlu do ocasu znamená vložení nově vytvořeného uzlu jako posledního uzlu. Chcete-li vložit uzel jako koncový uzel, musíte vytvořit nový uzel a učinit starý poslední uzlový bod novým uzlem a pak aktualizovat koncový bod tak, aby ukazoval na nový uzel.
3. Vložení uzlu na danou pozici zahrnuje vytvoření nového dočasného uzlu. Poté musí být nalezeno místo vložení nově vytvořeného uzlu.
Kód pro vložení uzlu do dané pozice:
Odstranění uzlu ze seznamu zahrnuje odstranění uzlu z existujícího seznamu. Vymazání uzlu ze seznamu odkazů je jednoduché než vložení uzlu do seznamu. V C ++ je kód pro odstranění uzlu uveden následovně:
Při procházení uzlem konkrétním klíčem (hodnotou) ze seznamu bude prohledán uzel ze seznamu, jehož informace se budou shodovat s klíčem daného uzlu. Následující kód C ++ bude procházet seznamem. datové struktury a algoritmy C ++
Zásobník č. 3
Hromada je seznam prvků, do kterých může být prvek vložen nebo smazán pouze na jednom konci, nazývaný horní část zásobníku. Vezměme si příklad věže Hanoj. Tady, když musíme vložit disk, musíme jej vložit pouze shora a podobně se disk vyjme pouze shora.
Stack používá princip LIFO, což znamená, že funguje v pořadí Last in First Out. To je poslední prvek přidaný do zásobníku je první prvek odebrání. Na zásobníku tedy lze provádět čtyři základní operace:
- Isempty: Tato operace zjistí, zda je zásobník prázdný.
- Push : Tato operace přidá novou položku do zásobníku.
- Pop: Tato operace odstraní položku z naposledy přidané položky zásobníku.
- Nahoru: Tato operace vrátí položku, která byla přidána do zásobníku naposledy.
Následující obrázek je příkladem stohu, kde se vkládání do stohu a vyjímání ze stohu položky provádí od vrcholu stohu a nikde jinde.
Přetečení zásobníku
Podmínka vyplývající z pokusu o vložení prvku do plného zásobníku.
Stack underflow
Podmínka vyplývající z pokusu o otevření prázdného zásobníku.
Zde jsme ukázali některé push a pop operace na zásobníku. Předpokládejme, že na začátku je zásobník prázdný, pak jsme přidali F, A, M, R, N. Pak dvakrát pop a stiskneme N, H, B, T, K, O, P.
Implementace zásobníku:
Lze jej implementovat pomocí pole nebo propojeného seznamu.
Následující kód ukazuje, jak je zásobník implementován v C ++ pomocí třídy. Zde je definována jedna třída pojmenovaná jako zásobník, ve které bylo vytvořeno pole pojmenované jako tyč s dynamickou velikostí a dvě hlavní funkce push a pop.
Přetečení zásobníku: Když nahoře> = velikost-1
Zásobní podtečení: Když je horní <0
Související články: -
Zde je několik článků, které se vztahují k datovým strukturám a algoritmům C ++, které vám pomohou získat podrobnější informace o algoritmech C ++ a datových strukturách a algoritmech, takže laskavě projděte odkaz uvedený níže. pokud se vám líbí struktury dat článku a algoritmy C ++, napište nám svůj cenný komentář.
- Kódy pro programovací jazyk C ++
- Linux vs Ubuntu
- C ++ Interview otázky, které musíte znát
- Otázky týkající se datových struktur a algoritmů | Nejužitečnější
- Nejlepší článek pro algoritmy a kryptografii (příklady)
- 8 úžasných algoritmů rozhovory otázky a odpovědi
- Úžasný průvodce pro Kali Linux vs Ubuntu
- C ++ Vector vs Array: Jaké jsou nejlepší funkce