Štruktúry a algoritmy dát C ++

Štruktúra údajov a algoritmy C ++ - znamená usporiadanie alebo usporiadanie prvkov konkrétnym spôsobom. Keď hovoríme, že musíme usporiadať prvky, tieto prvky môžu byť usporiadané do rôznych foriem. Napríklad ponožky môžu byť usporiadané rôznymi spôsobmi. Môžete to jednoducho nechať vo svojej skrinke. Alebo to môžete nechať úhľadne zložené. Najlepším spôsobom je skladanie a usporiadanie farieb. Takže pri hľadaní konkrétneho páru ponožiek je tretie usporiadanie perfektné.

Podobným spôsobom organizácie ponožiek môžu byť údaje usporiadané aj rôznymi spôsobmi alebo formami. Tieto rôzne spôsoby usporiadania údajov sa nazývajú dátová štruktúra. Pozrime sa na formálnu definíciu dátovej štruktúry a základov dátových štruktúr a algoritmov.

Štruktúry dát a algoritmy C ++:

Logický alebo matematický model konkrétnej organizácie údajov.

OR

Je to zvláštny spôsob organizácie údajov v počítači, aby sa dali použiť.

Podobne ako ponožky; iná organizácia zoznamových dátových štruktúr a algoritmov C ++ je -

  1. rad
  2. Prepojený zoznam
  3. Stoh
  4. fronta
  5. strom
  6. graf
  7. Hašovací stôl
  8. halda
  9. záznamy
  10. stoly

Tieto dátové štruktúry a algoritmy C ++ sú pri programovaní veľmi dôležité. Dobrý programátor vždy kladie dôraz skôr na štruktúru údajov než na kód. Každý programovací jazyk pracuje na rôznych dátových štruktúrach a algoritmoch v C ++. Dátové štruktúry, ktoré sú k dispozícii v C ++, sú nasledujúce.

  1. rad
  2. Prepojený zoznam
  3. Stoh
  4. fronta
  5. strom
  6. graf
  7. Hašovací stôl
  8. halda

Poďme to diskutovať jeden po druhom:

# 1 Pole

Pole je najjednoduchším typom dátových štruktúr a algoritmov C ++. Matica je definovaná ako sekvenčná zbierka dátových prvkov rovnakého typu s rovnakou veľkosťou. Napr. A0 = 12, a1 = 21, a2 = 14, a3 = 15 … Môžeme reprezentovať jednorozmerné pole, ako je znázornené na obrázku:

Kde

0, 1, 2, 3… ..n sa nazýva index alebo index

a (1), a (2), … a (n) sa nazýva indexová premenná

Môže byť 1-rozmerný, 2-rozmerný, 3-rozmerný a tak ďalej viacrozmerný.

V pamäťovom poli sa ukladá na susediace pamäťové miesta.

Najnižšia adresa zodpovedá prvému prvku

Najvyššia adresa zodpovedá poslednému prvku

V C ++ môžeme deklarovať 1-D (1-rozmerné) pole nasledovne

dataType arrayName (arraySize);

Napr. Č. 5;

Inicializácia poľa v C ++

num = (23, 10, 12, 3, 6);

Deklaráciu a inicializáciu môžeme kombinovať do jedného vyhlásenia nasledovne.

int num = (23, 10, 12, 3, 6);

Ak chceme dynamicky alokovať veľkosť poľa, mali by sme nového operátora nasledovať

int * a = nový int (veľkosť);

Nevýhodou je, že vkladanie a mazanie prvkov je pomalé ako v usporiadanom poli a jeho ukladaní v pevnej veľkosti.

Zoznam prepojení # 2

Zoznam sa vzťahuje na lineárnu zbierku položiek. Prepojený zoznam je séria spojených uzlov (dátový prvok), ako je to znázornené na obrázku 3. Uzol hlavičky ukazuje na prvý uzol zoznamu a posledný uzol ukazuje na NULL označenýÆ. Pretože každý uzol obsahuje najmenej.

  1. Časť údajov (akýkoľvek typ)
  2. Ukazovateľ na nasledujúci uzol v zozname

Prepojený zoznam je reprezentovaný v pamäti pomocou dvoch polí. Jedno pole ukladá informácie nazývané informácie, ktoré sú údajmi, ktoré sa majú uložiť, a iné ukladá pole s nasledujúcim ukazovateľom s názvom LINK, ktoré je adresou nasledujúceho uzla.

Výhoda prepojeného zoznamu v poli:

Pole aj prepojený zoznam sú znázornením zoznamu položiek v pamäti. Dôležitým rozdielom je spôsob, akým sú položky vzájomne prepojené. Hlavným obmedzením poľa je vloženie prvkov do poľa a vymazanie prvkov z usporiadaného poľa je ťažké, pretože ostatné prvky sa musia presunúť. Vloženie a vymazanie prvkov z prepojeného zoznamu je veľmi jednoduché.

Poznámka: Staňte sa vývojárom C ++
Naučte sa navrhovať a prispôsobovať programy pre rôzne platformy. Kódovanie, testovanie, ladenie a implementácia softvérových aplikácií. Rozvíjať zručnosti na zabezpečenie plynulého chodu aplikácií.

Typy prepojeného zoznamu sú:

1. Zoznam jednotlivo prepojených : obsahuje iba jedno prepojené pole, ktoré obsahuje adresu nasledujúceho uzla v zozname, a zadané informácie, ktoré obsahujú informácie, ktoré sa majú uložiť.

2. Jeden kruhový zoznam je iba zoznam, ale posledný uzol zoznamu obsahuje adresu prvého uzla namiesto hodnoty null. To je obsah hlavy a nasledujúce pole posledného uzla sú rovnaké.

3. Zdvojený zoznam obsahuje dve prepojené polia predchádzajúce a nasledujúce. Doteraz prepojené pole, ktoré obsahuje adresu predchádzajúceho uzla v zozname, a ďalšie prepojené pole obsahuje adresu nasledujúceho uzla v zozname a uložené informácie uchovávajú informácie ako ukladací priestor.

4. Double Circular linked List je dvojnásobne prepojený zoznam, ale ďalšie pole posledného uzla obsahuje adresu prvého uzla namiesto nulovej hodnoty.

Odporúčané kurzy

  • Kurz na VB.NET
  • Tréning programovania dátových vied
  • Online kurz ISTQB
  • Školiaci kurz Kali Linux

Implementácia prepojeného zoznamu v C ++ zahŕňa vytvorenie uzla, vymazanie uzla zo zoznamu, vloženie novovytvoreného uzla do zoznamu a vyhľadávanie uzla pomocou konkrétneho kľúča.

Kód pre vytvorenie uzla je daný nasledovne:

Vloženie uzla do zoznamu zahŕňa tri prípady

1. Vloženie uzla na začiatok znamená vloženie novovytvoreného uzla ako počiatočného uzla. Na vloženie uzla na začiatku najskôr vytvorte nový uzol a urobte nový uzol tak, aby bol starý, a potom začnite aktualizovať tak, aby ukazoval na nový uzol, ako je to znázornené na obrázku nižšie:

Kód pre vloženie uzla na začiatok:

2. Vloženie uzla do chvosta znamená vloženie novo vytvoreného uzla ako posledného uzla. Ak chcete vložiť uzol ako koncový uzol, musíte vytvoriť nový uzol a urobiť starý posledný uzlový bod novým uzlom a potom aktualizovať koncový bod tak, aby ukazoval na nový uzol.

3. Vloženie uzla na danú pozíciu zahŕňa vytvorenie nového dočasného uzla. Potom musí byť nájdené miesto vloženia novovytvoreného uzla.

Kód na vloženie uzla do danej polohy:

Vymazanie uzla zo zoznamu zahŕňa odstránenie uzla z existujúceho zoznamu. Vymazanie uzla zo zoznamu odkazov je jednoduché ako vloženie uzla do zoznamu. V C ++ je kód na vymazanie uzla uvedený nasledovne:

Prechádzanie uzlom konkrétnym kľúčom (hodnotou) zo zoznamu vyhľadá uzol zo zoznamu, ktorého informácie sa budú zhodovať s kľúčom daného uzla. Nasledujúci kód C ++ prejde zoznamom. dátové štruktúry a algoritmy C ++

Zásobník č. 3

Stoh je zoznam prvkov, do ktorých sa prvok môže vkladať alebo vymazávať iba na jednom konci, ktorý sa nazýva vrch stohu. Zoberme si príklad veže v Hanoji. Tu, keď musíme vložiť disk, musíme ho vložiť iba zhora a podobne sa disk vyberie iba zhora.

Stack používa princíp LIFO, čo znamená, že funguje v poradí Last in First Out. To je posledný prvok, ktorý bol pridaný do stohu, je prvý prvok odstránenia. Na zásobníku je teda možné vykonať štyri základné operácie:

  • Isempty: Táto operácia zistí, či je zásobník prázdny.
  • Push : Táto operácia pridá novú položku do zásobníka.
  • Pop: Táto operácia odstráni položku z naposledy pridanej položky zásobníka.
  • Hore: Táto operácia vráti položku, ktorá bola pridaná do zásobníka naposledy.

Nasledujúci obrázok je príkladom stohu, kde sa vkladanie do stohu a vyberanie zo stohu predmetu uskutočňuje od vrchu stohu a nikde inde.

Pretečenie zásobníka

Stav vyplývajúci z pokusu o zatlačenie prvku na plný balík.

Zásobník pod prietokom

Stav vyplývajúci z pokusu o otvorenie prázdneho zásobníka.

Tu sme ukázali niektoré push a pop operácie na zásobníku. Predpokladajme, že spočiatku je zásobník prázdny, potom sme pridali F, A, M, R, N. Potom dvakrát pop a stlačte N, H, B, T, K, O, P.

Implementácia Stack:

Môže sa implementovať pomocou poľa alebo prepojeného zoznamu.

Nasledujúci kód zobrazuje, ako je zásobník implementovaný v jazyku C ++ pomocou triedy. Tu je definovaná jedna trieda pomenovaná ako zásobník, v ktorej sa vytvorilo pole pomenované ako palica s dynamickou veľkosťou a dve hlavné funkcie push a pop.

Pretečenie zásobníka: Keď hore> = veľkosť-1

Podtok zásobníka: Keď je horný <0

Súvisiace články: -

Tu je niekoľko článkov, ktoré súvisia s dátovými štruktúrami a algoritmami C ++, ktoré vám pomôžu získať podrobnejšie informácie o algoritmoch C ++ a údajových štruktúrach a algoritmoch, takže si láskavo prečítajte odkaz uvedený nižšie. Ak sa vám páči štruktúra údajov a algoritmy článku C ++, potom nám pošlite svoj hodnotný komentár.

  1. Kódy pre programovací jazyk C ++
  2. Linux verzus Ubuntu
  3. C ++ Interview otázky, ktoré musíte vedieť
  4. Otázky týkajúce sa rozhovorov o dátových štruktúrach a algoritmoch Najužitočnejší
  5. Najlepší článok pre algoritmy a kryptografiu (príklady)
  6. 8 úžasných algoritmov rozhovory otázky a odpovede
  7. Úžasný sprievodca pre Kali Linux vs Ubuntu
  8. C ++ Vector vs Array: Aké sú najlepšie funkcie

Kategórie:

Vývoj softvéru