Čo sú zložité zoznamy v dátovej štruktúre. Typy a dátové štruktúry

Nevyhnutnou podmienkou pre zostavenie algoritmu je formalizácia údajov, t.j. prinášanie informácií niektorým informačný model(cm." Informačné modely“) Už popísané a preskúmané. Keď sa takýto model nájde, hovorí sa, že je definovaný. abstraktná dátová štruktúra.

Abstraktná dátová štruktúra popisuje znaky a vlastnosti objektu, vzájomné prepojenie medzi prvkami objektu, rovnako ako je to možné operácií nad daným objektom alebo triedou objektov.

Jednou z úloh informatiky je nájsť formy prezentácie informácií, ktoré sú vhodné na počítačové spracovanie. Informatika ako exaktná veda pracuje s formálnymi (matematicky rigorózne popísanými) objektmi. Takéto predmety - základné abstraktné dátové štruktúry používané v informatike sú:

· celé čísla;

· Reálne čísla;

· Symboly;

· Booleovské hodnoty.

Pre počítačové spracovanie týchto objektov v programovacích jazykoch existujú zodpovedajúce dátové typy(cm." Typy údajov“). Základné objekty je možné spájať do zložitejších štruktúr pridaním operácií nad štruktúrou ako celkom a pravidiel pre prístup k jednotlivým prvkom tejto abstraktnej dátovej štruktúry.

Tieto abstraktné dátové štruktúry zahŕňajú:

· Vektory (konečné polia);

· Tabuľky (matice) a vo všeobecnom prípade - viacrozmerné polia;

Dynamické štruktúry:

Postupnosti symbolov, čísla;

fronty;

Stromy;

Dobrá voľba dátovej štruktúry je často kľúčom k vytvoreniu efektívneho algoritmu a programu, ktorý ho implementuje: pomocou analógie dátových štruktúr a reálnych objektov môžete nájsť efektívne riešenia problémov.

Všimnite si, že uvedené štruktúry existujú bez ohľadu na ich implementáciu v programovaní. Tieto dátové štruktúry sa používali v 18. aj 19. storočí, keď ešte nebol vynájdený počítací stroj. Môžeme navrhnúť algoritmus z hľadiska abstraktnej dátovej štruktúry, ale na implementáciu algoritmu v konkrétnom programovacom jazyku musíme nájsť spôsob, ako ho reprezentovať z hľadiska dátové typy a operátorov podporované týmto programovacím jazykom (pozri „ Operátory programovacieho jazyka“). Na počítačovú reprezentáciu abstraktných štruktúr sa používajú nasledujúce dátové štruktúry, ktoré sú súborom premenných, prípadne rôznych typov údajov, skombinovaných určitým spôsobom. Na vytvorenie štruktúr, ako je vektor, tabuľka, reťazec, sekvencia, vo väčšine programovacích jazykov existujú štandardy dátové typy: jednorozmerné pole, dvojrozmerné pole, reťazec, súbor (menej často zoznam), resp. Organizácia zvyšku dátových štruktúr, na prvom mieste dynamické štruktúry, ktorých veľkosť sa počas vykonávania programu mení, musí programátor vykonať samostatne, pomocou základných dátových typov. Uvažujme o takýchto štruktúrach podrobnejšie.

zoznamy

Zoznam riadkov- postupnosť lineárne spojených prvkov, pre ktoré sú povolené operácie pridávania prvkov na ľubovoľné miesto v zozname a vymazanie ľubovoľného prvku. Lineárny zoznam je jednoznačne identifikovaný ukazovateľom na začiatok zoznamu. Typické operácie so zoznamami sú: prechádzanie zoznamom, nájdenie daného prvku, vloženie prvku bezprostredne za alebo pred konkrétny prvok, vymazanie daného prvku, spojenie dvoch zoznamov do jedného, ​​rozdelenie jedného zoznamu na dva alebo viac zoznamov atď.

V lineárnom zozname pre každú položku okrem prvý, existuje predchádzajúce element; pre každý prvok okrem posledný, existuje Ďalšie element. Všetky prvky zoznamu sú teda usporiadané. Spracovanie lineárneho jednoducho prepojeného zoznamu však nie je vždy vhodné, pretože neexistuje možnosť pohybu v opačnom smere - od konca zoznamu na začiatok. V lineárnom zozname môžete prechádzať všetkými prvkami, iba postupne sa presúvať od aktuálneho prvku k ďalšiemu, počnúc prvým, priamym prístupom k i- prvok nie je možný.

Príklad 1. Poradie záznamov o priezviskách čitateľov v knihovníčkovom počítači určuje vzťah „predchádzajúci – nasledujúci“. Samotné záznamy majú spravidla ďalšiu vlastnosť - sú zoradené podľa abecedy. Nad týmto zoznamom sú implementované operácie pridania novej čítačky a v prípade potreby vymazania starej. Ak sa navyše vedie evidencia o vydaných knihách pre každého čitateľa, potom je vhodné každú takúto evidenciu opäť znázorniť pomocou zoznamu vydaných kníh.

Zoznamy prsteňov- rovnaká štruktúra ako lineárny zoznam, ale s dodatočným spojením medzi posledným a prvým prvkom, to znamená, že prvý prvok je nasledujúci po poslednom prvku.

V kruhovom zozname na rozdiel od lineárneho všetky prvky sú rovnaké(keďže pre každý prvok sú definované predchádzajúce aj nasledujúce prvky). Výber „prvého“ a „posledného“ prvku v zozname zvonení je dosť svojvoľný štruktúra zoznamu nemá žiadne explicitne zvýraznené prvky!

Príklad 2 V mnohých hrách deti používajú počítadlá na výber vedúceho, rozdelenie do tímov atď. Rýmy na počítanie sú spravidla dlhé a deti (bez toho, aby o tom vedeli) organizujú zoznam krúžkov. Predchádzajúci a nasledujúci vzťah je určený tým, akým spôsobom vodca myslí. Typickou operáciou v takejto štruktúre je odstránenie položky zo zoznamu pri zachovaní jej kruhovej štruktúry.

Lineárne zoznamy, v ktorých sa operácie vkladania, vymazávania a prístupu k hodnotám prvkov vykonávajú iba s extrémnymi prvkami (prvý alebo posledný), dostali špeciálne názvy.

Stoh- špeciálny prípad lineárneho jednoducho spojeného zoznamu, pre ktorý sú definované dve operácie: pridanie prvku na vrchol zásobníka (pred prvý prvok) a odstránenie prvku z vrcholu zásobníka (odstránenie prvého prvku).

Príklad 3 Zvážte problém určenia rovnováhy zátvoriek rôznych typov v aritmetickom vyjadrení. Napríklad, chcete analyzovať, či sú zátvorky vo výraze obsahujúcom zátvorky a hranaté zátvorky vyvážené:? Na vyriešenie tohto problému použijeme dynamickú štruktúru údajov stoh... Uveďme algoritmus na riešenie tohto problému krok za krokom. Použijeme nasledujúci zápis:

i- číslo analyzovaného symbolu;

n- počet znakov vo výraze.

1. i = 0.

2. i = i + 1.

3. Ak in, potom prejdite na položku (4), v opačnom prípade, ak je zásobník prázdny, vydáme správu „zátvorky sú vyvážené“, inak vydáme správu „ zátvorky nie sú vyvážené“. Koniec algoritmu.

4. Ak i-tý znak sa líši od zátvoriek, potom prejdite na položku (2).

5. Ak i-tý znak je „(“ alebo „[“), potom ho položíme na zásobník a prejdeme na položku (2).

6. Ak i-tý znak je "")", potom skontrolujeme vrch zásobníka: ak je vrch zásobníka "(", potom ho vytiahneme zo zásobníka; prejdite na položku (2), inak vydáme správu " zátvorky nie sú vyvážené“. Koniec algoritmu.

7. Ak i-tý znak je „]“, potom skontrolujeme vrch zásobníka: ak je vrchol zásobníka „[“, vytiahneme ho zo zásobníka; prejdite na položku (2), inak vypíšeme správu „ zátvorky nie sú vyvážené“. Koniec algoritmu.

Fronta- špeciálny prípad lineárneho jednoducho prepojeného zoznamu, pre ktorý sú povolené len dve operácie: pridanie prvku na koniec (koniec) radu a odstránenie prvku z hlavy (hlavy) radu.

Pojem front je skutočne veľmi blízky bežnému pojmu „front“. Fronta zákazníkov v obchode je dobre opísaná z hľadiska tejto dátovej štruktúry.

Stromy

Drevo je súbor prvkov tzv uzly, v ktorom je vybratý jeden prvok ( koreň) a zvyšok prvkov je rozdelený do nesúvislých množín (podstromov), z ktorých každý je strom a koreň každého podstromu je potomok koreň stromu, t.j. všetky prvky sú spojené vzťahom rodič-dieťa. V dôsledku toho sa vytvára hierarchická štruktúra uzlov. Uzly, ktoré nemajú žiadne deti, sa nazývajú listy... Na strome sú definované nasledujúce operácie: pridanie prvku do stromu, odstránenie prvku zo stromu, prechádzanie stromom, hľadanie prvku v strome.

Príklad 4 Strom je najvhodnejšia dátová štruktúra na znázornenie rodokmeňa, pomocou ktorej môžete vyriešiť problém určenia stupňa vzťahu medzi dvoma ľuďmi.

Stromy sa používajú aj na určenie víťaznej stratégie v hrách (pozri článok „ Hry. Víťazné stratégie"), A na vytváranie rôznych informačných modelov (pozri" Informačné modely”).

Zvlášť dôležitú úlohu v informatike zohráva tzv binárne stromy.

Binárny (binárny) strom- špeciálny prípad stromu, v ktorom každý uzol môže mať najviac dvoch potomkov, čo sú korene ľavého a pravého podstromu.

Ak je navyše pre uzly stromu splnená podmienka, že všetky hodnoty prvkov ľavého podstromu sú menšie ako hodnota koreňa stromu a všetky hodnoty prvkov pravý podstrom sú väčšie ako hodnota koreňa, potom sa takýto strom volá binárny vyhľadávací strom a je navrhnutý tak, aby rýchlo našiel položky. Algoritmus vyhľadávania v takomto strome funguje nasledovne: požadovaná hodnota sa porovná s hodnotou koreňa stromu a v závislosti od výsledku porovnania sa vyhľadávanie buď skončí alebo pokračuje iba vľavo alebo len vpravo. podstrom, resp. Celkový počet porovnávacích operácií nepresiahne tzv výška stromu- maximálny počet prvkov na ceste od koreňa stromu k jednému z listov. Výška stromu znázornená na obrázku je teda 4.

Grafy

Graf je súbor prvkov tzv vrcholy grafu spolu so súborom vzťahov medzi týmito uzlami, tzv rebrá graf. Grafická interpretácia tejto dátovej štruktúry je množina bodov zodpovedajúcich vrcholom, ktorých niektoré dvojice sú spojené čiarami alebo šípkami, ktoré zodpovedajú hranám. V druhom prípade sa nazýva graf orientovaný(pozri aj články “ Grafické modely" a " Tabuľkové modely”).

Vzhľadom na to, že grafy možno použiť na popis objektov ľubovoľnej štruktúry, sú grafy hlavným prostriedkom na popis štruktúr zložitých objektov a fungovania systémov. Napríklad opísať počítačovú sieť, dopravný systém, hierarchickú štruktúru (strom je jednou z odrôd grafu). Blokové diagramy algoritmov (pozri „ Metódy záznamu algoritmov“) Sú tiež grafy.

Ak je navyše každej hrane priradené určité číslo ( váha), potom sa takýto graf nazýva vyvážený... Napríklad pri popise cestného systému v Rusku pomocou grafu je dôležitá dĺžka cesty (váha okraja grafu), ktorá spája určité sídla (vrcholy grafu). V tomto prípade na obrázku nemusia dĺžky zodpovedajúcich hrán zodpovedať im priradeným váham, na rozdiel od cestnej mapy.

Príklad 5. Z hľadiska váženého grafu je vhodné vyriešiť nasledujúci problém. Ruská vláda pripravuje plán výstavby moderných diaľnic spájajúcich mestá nad milión obyvateľov. Aké cesty treba stavať, aby sa z každého takého mesta dalo po nových diaľniciach dostať do akéhokoľvek iného a celková dĺžka ciest bola minimálna?

Tento problém v teórii grafov má jednoduché a presné riešenie. Cestnú sieť môžeme začať plánovať z akéhokoľvek mesta, napríklad z Petrohradu. Spojme to s najbližším miliónovým mestom. Ďalej, v každom kroku sa do existujúcej siete pridá najkratšia cesta, ktorú možno použiť na spojenie mesta, ktoré ešte nie je pripojené k sieti, s jedným z miest, ktoré už je v sieti zahrnuté. Počet ciest tak bude o jednu menej ako miest.

Abstraktnú dátovú štruktúru – graf – možno v programe znázorniť viacerými spôsobmi, t.j. pomocou rôznych dátových typov. Napríklad graf je možné opísať pomocou zoznamu hrán, pričom každú hranu je možné špecifikovať dvojicou vrcholov a v prípade potreby aj váhou. Najrozšírenejšie je tabuľkové ukladanie grafu (pozri „ Tabuľkové modely"), Tiež nazývaný matica susednosti, t.j. povedzme dvojrozmerné pole A, kde pre nevážený graf (alebo 1), ak je hrana medzi vrcholmi i a j existuje a (alebo 0) inak. Pre vážený graf A[i][j] sa rovná hmotnosti zodpovedajúcej hrany a neprítomnosť hrany v mnohých problémoch je vhodne označená nekonečnom. Pre neorientované grafy je matica susednosti vždy symetrická vzhľadom na hlavnú uhlopriečku ( i = j). Pomocou matice susednosti je ľahké skontrolovať, či graf obsahuje hranu spájajúcu vrchol i s vrcholom j... Jeho hlavnou nevýhodou je, že matica susednosti vyžaduje dostatok pamäte na uloženie N 2 hodnoty pre graf obsahujúci N vrcholov, aj keď hrán v grafe je podstatne menej ako N 2 .

Pri vysvetľovaní pojmu dátové štruktúry môžete použiť nasledujúci obrázok.

Pri riešení akéhokoľvek problému je potrebné pracovať údajov a vykonávanie operácií na nich. Vo všeobecnosti je súbor týchto operácií pre každú úlohu odlišný. Ak sa však pri riešení rôznych problémov často používa určitá množina operácií, potom je užitočné prísť so spôsobom usporiadania údajov, ktorý vám umožní vykonávať presne tieto operácie čo najefektívnejšie. Po vynájdení takejto metódy môžeme pri riešení konkrétneho problému predpokladať, že máme „čiernu skrinku“ (nazveme ju dátová štruktúra), o ktorej je známe, že uchováva nejaké údaje a ktorá môže s týmito údajmi vykonávať niektoré operácie. To vám umožní odpútať pozornosť od detailov a zamerať sa na hlavné črty problému. Vo vnútri (tj v počítači) môže byť táto „čierna skrinka“ implementovaná rôznymi spôsobmi a mali by ste sa snažiť o čo najefektívnejšiu implementáciu (rýchlu a ekonomickú, ktorá si vyžaduje pamäť).

Štátny vzdelávací štandard zabezpečuje štúdium rôznych dátových štruktúr tak v základnom kurze základnej školy, ako aj na strednej škole. V kurze programovania na základnej škole Vzorový program uvádza reťazce znakov (reťazce), čísla, zoznamy, stromy a grafy ako spracované objekty. V praktických prácach sa však z údajov komplexnej štruktúry uvádza iba pole (pozri článok „ Operácie poľa“). Na základnej škole sa zdá, že pri konštrukcii grafických a iných modelov má zmysel študovať v prvom rade zvyšok štruktúr (pozri IV. časť encyklopédie).

Príklad programu pre špecializovanú školu zahŕňa prácu s číslami, maticami, reťazcami, zoznamami, stromami. Ako jednoduchú ilustráciu práce so zoznamami si môžete zvoliť usporiadanie zásobníka pomocou jednorozmerného poľa a celočíselnej premennej ukazujúcej na vrch zásobníka ("spodok" zásobníka je vždy v prvom prvku poľa ). Okrem problému kontroly vyváženia zátvoriek uvedeného v článku môžete študovať činnosť kalkulačky zásobníka pomocou príkladu algoritmu na preklad aritmetického výrazu do reverznej poľskej notácie ( postfix záznam) z nášho obvyklého infixovať záznamy a ďalší výpočet hodnoty aritmetického výrazu.

Binárny strom sa dá tiež ľahko reprezentovať v pamäti počítača pomocou jednorozmerného poľa, zatiaľ čo prvý prvok poľa uloží koreň stromu a potomkov uzla stromu uložených v i prvok poľa bude umiestnený v 2 i-m a (2 i+ 1) tý prvok, resp. Ak uzol nemá potomka, potom sa zodpovedajúci prvok bude rovnať, napríklad 0. Postup rekurzívneho prechodu cez strom t a tlač jeho prvkov v tomto prípade bude vyzerať takto:

poradie procedúr (i: celé číslo);

ak t [i]<> 0 potom

O implementácii zoznamov a polí pomocou dynamických premenných si môžete prečítať napríklad v klasickej knihe od N. Wirtha „Algorithms and Data Structures“.

Grafové algoritmy sú tiež zahrnuté v učebných osnovách pre profilovú školu. Spomína najmä nájdenie najkratšej cesty v grafe. Pre nevážený graf je možné tento problém vyriešiť napríklad pomocou algoritmu vyhľadávania na šírku, kedy sa najprv označia vrcholy grafu spojené hranou s pôvodným vrcholom, potom všetky vrcholy spojené s označenými, a tak ďalej. Pre vážený graf sa najčastejšie používa Dijkstrov algoritmus (pozri napr. článok E. V. Andreeva „Olympiády v informatike. Cesty na vrchol“, „Informatika“ č. 8/2002). Znalosť takýchto algoritmov je nevyhnutná pre úspešné riešenie úloh olympiády v informatike. Takže na IV. federálnej okresnej etape celoruskej olympiády v informatike 2007 bol navrhnutý problém „Zákopy a priekopy“, ktorého riešením bolo len hľadanie najkratšej cesty vo váženom grafe.

Spočiatku programovací proces umožňoval programátorovi písať všetky algoritmy priamo v strojovom jazyku. Tento prístup zhoršil už aj tak náročnú úlohu vývoja algoritmov a príliš často viedol k chybám, ktoré bolo potrebné odhaliť a opraviť [proces známy ako ladenie] predtým, ako sa úloha mohla považovať za dokončenú.

Prvým krokom k uľahčeniu programovacej úlohy bolo eliminovanie používania čísel na písanie inštrukcií a operandov priamo vo forme, v akej sa používajú v stroji. Na tento účel sa pri vývoji programov začali vo veľkom využívať mnemotechnické zápisy rôznych príkazov namiesto ich hexadecimálnej reprezentácie. Napríklad namiesto digitálneho kódu príkazu na načítanie registra mohol programátor teraz napísať LOD a namiesto kódu príkazu na skopírovanie obsahu registra do pamäte mohol použiť mnemotechnický zápis STO. Pre zápis operandov boli vyvinuté pravidlá, podľa ktorých mohol programátor niektorým pamäťovým oblastiam priradiť popisné názvy [často sa im hovorí identifikátory] a použiť ich pri písaní programových príkazov namiesto adries zodpovedajúcich pamäťových buniek. Takéto identifikátory sa bežne označujú ako premenné. To zdôrazňuje, že zmenou hodnoty alokovanej v danej sekcii pamäte zmeníme hodnotu spojenú s identifikátorom priradeným tejto sekcii počas vykonávania programu.

Keď je premenná deklarovaná v programe, zvyčajne sa súčasne určuje aj ich typ. Dátový typ určuje tak interpretáciu konkrétnych údajov, ako aj operácie, ktoré s nimi možno vykonávať. Typy údajov zahŕňajú Integer, Real, Character a Boolean.

Typ Integer sa používa na označenie číselných údajov, ktoré sú celými číslami. V pamäti sú najčastejšie zastúpené v binárnom doplnkovom kóde. S celočíselnými údajmi môžete vykonávať bežné aritmetické a porovnávacie operácie.

Typ Real je navrhnutý tak, aby reprezentoval číselné údaje, ktoré môžu obsahovať neceločíselné hodnoty. Zvyčajne sú uložené v pamäti ako binárne čísla s pohyblivou rádovou čiarkou. Operácie, ktoré možno vykonať s údajmi v reálnom čase, sú podobné tým, ktoré sa vykonávajú s údajmi typu celé číslo. Manipulácie, ktoré je potrebné vykonať na pridanie dvoch údajových položiek typu Real, sa však líšia od manipulácií potrebných na vykonanie akcií s premennými typu Integer.

Typ Character sa používa pre údaje pozostávajúce zo znakov, ktoré sú uložené v pamäti ako kódy ASCII alebo UNICODE. Údaje tohto typu možno navzájom porovnávať [určiť, ktorý z dvoch znakov predchádza druhému v abecednom poradí]; skontrolujte, či je jeden znakový reťazec iný, a tiež zreťazte dva reťazce do jedného dlhšieho reťazca, pričom jeden z nich pripojte za druhým [operácia zreťazenia].

Boolean odkazuje na údaje, ktoré môžu mať iba dve hodnoty True a False. Príkladom takýchto údajov je výsledok operácie porovnávania dvoch čísel. Booleovské dátové operácie zahŕňajú kontrolu, či je aktuálna hodnota premennej True alebo False.

Hlavná pamäť stroja je organizovaná vo forme samostatných buniek s postupne sa zvyšujúcimi adresami. Tieto bunky sa však často používajú ako základ pre implementáciu iných metód umiestňovania údajov. Napríklad text sa zvyčajne považuje za dlhý reťazec znakov, zatiaľ čo informácie o predaji možno zobraziť ako obdĺžnikovú tabuľku číselných hodnôt, z ktorých každá predstavuje počet obchodov, ktoré daný zamestnanec uzavrel v daný deň. Výzvou je poskytnúť používateľovi prostriedky na manipuláciu s takýmito abstraktnými štruktúrami, namiesto toho, aby sa ponoril do detailov skutočnej organizácie údajov v hlavnej pamäti stroja. Pre správne používanie počítača je potrebná dobrá znalosť štrukturálnych vzťahov medzi dátami, základné metódy reprezentácie štruktúr v počítači, ako aj metódy práce s nimi. Pre spojenia medzi dátami v počítači sa používajú tieto informačné štruktúry: pole, záznam, zoznam, strom, zásobník, front.

Polia

Pole je štruktúra, ktorá obsahuje niekoľko prvkov rovnakého typu. Indexy sa používajú na usporiadanie prvkov poľa. Indexy sa píšu v zátvorkách za názvom poľa. Pole s jedným indexom sa nazýva jednorozmerné, pole s dvoma dvojrozmernými atď.

Nahrávanie

Záznam je štruktúra, ktorá nemusí byť rovnakého typu. Jednotlivé prvky záznamu sa nazývajú polia. Pole zas môže byť aj rekordné.

záznam študenta (
Krstné meno,
Priezvisko,
Skupina
)

zoznamy

Zoznam je množina záznamov, z ktorých každý obsahuje špeciálne pole – ukazovateľ. Ukazovateľ spája záznam s iným záznamom alebo obsahuje hodnoty Null, ktoré naznačujú, že hodnota ukazovateľa nie je definovaná.

Položky v jednoducho prepojenom zozname majú každý jeden ukazovateľ a sú prepojené v reťazci:

Šípka na obrázku hovorí o obsahu ukazovateľa a slovo Data označuje kolekcie polí, v ktorých sú dáta uložené. Zoznam je možné organizovať pomocou dvojrozmerného poľa, ktorého všetky prvky s prvým indexom rovným 0 sú určené na ukladanie údajov a prvky s prvým indexom rovným 1 sú ukazovatele.

V tomto zozname sú položky obsahujúce písmená anglickej abecedy usporiadané v abecednom poradí. Prvý záznam v zozname obsahuje znak "A", druhý obsahuje "B" atď.

Ak chcete pracovať so zoznamom, musíte byť schopní vykonávať tri základné operácie:

Pass () - prechádzanie alebo pohyb po zozname;
Pridať () - pridanie nového záznamu do zoznamu;
Odstrániť () – vymaže záznam zo zoznamu.

Okrem operácií na prácu so zoznamom sú potrebné ďalšie dve premenné:

premenná Head, ktorá ukladá informácie o prvom zázname v zozname
premenná Current, ktorá ukazuje na aktuálnu položku v zozname

V tabuľke sú zhrnuté popisy niektorých operácií v zozname, ktorých príklad implementácie je uvedený vyššie.

Názov operácie	Pseudokód
Posuňte sa v zozname o jeden krok nižšie	funkcia Pass (aktuálne) ( if (M Null) then Current: = M; návrat (Aktuálny); }
	funkcia Pridať (aktuálne, nové) ( M: = M; M: = Nový; návrat; }
Pridajte do zoznamu položku, na ktorú ukazuje premenná Nová	funkcia Odstrániť (aktuálne) ( if (M Null) then M: = M]; návrat; }

Záznamy v dvojito prepojenom zozname sú navzájom prepojené v reťazci, ale zároveň majú dve polia ukazovateľa. Jeden z nich ukazuje na predchádzajúcu položku v zozname, druhý na nasledujúcu položku. Táto štruktúra vám umožňuje pohybovať sa v zozname dvoma smermi: dopredu a dozadu.

Kruhový zoznam je zoznam, ktorého posledný záznam ukazuje na prvý. V týchto zoznamoch nie je žiadna nulová položka.

Strom je rozvetvený zoznam, ktorého každá položka môže obsahovať viacero ukazovateľov. Záznamy v strome sa nazývajú uzly. Uzly, kde sú všetky ukazovatele prázdne, sa nazývajú listy. Horný počiatočný uzol stromu sa nazýva koreňový uzol. V mnohých problémoch stačí použiť binárne [binárne] stromy, ktorých uzly nemajú viac ako dva ukazovatele.

Príklad. Chcete vyhodnotiť matematický výraz (3 + 7) * (2 / (3-1)). Predstavme si tento výraz ako strom:

Každý uzol tohto stromu je záznamom nasledujúceho formulára:

záznamový uzol (
Prevádzka
číslo
Ľavý ukazovateľ
RightPointer
)

Listy stromu obsahujú čísla, ostatné uzly sú symboly operácií.

Po implementácii opísaného stromu na dvojrozmernom poli dostaneme nasledujúci obrázok:

Ak chcete vypočítať hodnotu stromu, musíte vypočítať hodnoty pravého a ľavého podstromu a potom na nich vykonať výslednú operáciu. Pseudokód algoritmu, ktorý rieši problém, bude vyzerať takto:

funkcia Vypočítať (Aktuálny) (
if (M = Null) then
Výsledok: = M;
inak (
R1: = vypočítajte (M);
R2: = vypočítajte (M);
Výsledok: = R1 (M) R2;
}
návrat (Výsledok);
}

Zásobník je dátová štruktúra typu last-in-first-out. K údajom uloženým v zásobníku sa pristupuje cez hornú časť. Údaje sa do zásobníka vkladajú postupne. Prvok vložený do zásobníka sa najprv objaví v spodnej časti a ak ho chcete zo zásobníka vytiahnuť, musíte najskôr vysunúť všetky dáta, ktoré boli do zásobníka vložené neskôr.

Pri práci so zásobníkom sú možné dve núdzové situácie: pokus o načítanie údajov z prázdneho zásobníka; pokus o zatlačenie položky na stoh, keď počet položiek na stohu dosiahol maximálny povolený počet.

Front je dátová štruktúra prvý dovnútra, prvý von. Vo fronte je premenlivé množstvo údajov. Po zaradení do frontu sa údaje pridajú na chvost, pri načítaní sa odoberú z hlavy.

Tabuľka hash

Hašovanie je technika, ktorá poskytuje priamy prístup k záznamom bez použitia akýchkoľvek ďalších štruktúr. Proces možno zhrnúť nasledovne. Priestor, kde sú uložené dáta, je rozdelený do niekoľkých segmentov. Záznamy sú distribuované cez tieto segmenty podľa nejakého algoritmu nazývaného hashovací algoritmus, ktorý prevádza hodnotu kľúčového poľa na číslo segmentu. Každý záznam je uložený v segmente definovanom týmto procesom. Preto je možné záznam získať hashovaním hodnoty jeho kľúčového poľa a prečítaním záznamov zodpovedajúceho segmentu. Takto zostavená dátová štruktúra sa nazýva hašovacia tabuľka.

Napríklad, ak potrebujete zorganizovať hašovaciu tabuľku na uloženie veľkých písmen anglickej abecedy, potom si môžete vybrať kódy znakov ASCII ako kľúče a hašovací algoritmus odreže najmenej významných päť bitov a vytvorí index prvkov poľa na uloženie. postava na ich základe:

Vo všeobecnosti by mal hašovací algoritmus na základe hodnoty kľúča produkovať hodnotu indexu v rámci poľa a distribuovať kľúče rovnomerne medzi prvky poľa. Nedodržanie poslednej požiadavky vedie k situáciám, keď niekoľko záznamov spadá do rovnakého segmentu. Tieto situácie sa nazývajú kolízie.

Téma tohto článku sa opäť zaoberá teória programovania, takže sa budete musieť uchýliť k rôznym klasifikáciám a pracovať z matematického hľadiska. Dátové štruktúry sú prakticky to prvé, o čom sa počas školenia hovorí. Druhým je odhad zložitosti algoritmov. Môže sa zdať, že tieto dve otázky spolu málo súvisia, ale nie je to tak a postupom príbehu sa ukáže prečo. Nebudem zachádzať do podrobností, keďže prax ukazuje, že v procese získavania skúseností zostáva v hlave len to najdôležitejšie. Podľa mňa sa to deje v akejkoľvek oblasti činnosti. Pokúsim sa načrtnúť, čo mi v týchto otázkach ostalo v hlave.

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

Dátová štruktúra Je to forma uchovávania a prezentácie informácií. Definícia je dosť vágna, takže odborníci používajú rôzne formy klasifikácie a spresnenia. Dátové štruktúry sú jednoduché a zložité: predstavujú atómovú jednotku informácie alebo súbor údajov rovnakého typu. Jednoduché dátové štruktúry sú charakterizované napríklad celočíselným, reálnym, booleovským, textovým typom atď. Komplexné dátové štruktúry sa delia na dynamické a statické množiny. Dynamické v priebehu životného cyklu umožňujú meniť ich veľkosť (pridávať a odoberať prvky), statické nie. A nakoniec, podľa organizácie vzťahov medzi prvkami zložitých dátových štruktúr existuje nasledujúca klasifikácia:

• Lineárne
  • Pole
  • Zoznam
  • Prepojený zoznam
  • Fronta
  • Tabuľka hash

Hierarchický

• Binárne stromy
• N-árne stromy
• Hierarchický zoznam

sieť

• Jednoduchý graf
• Orientovaný graf

Tabuľkový

• Tabuľka relačnej databázy
• Dvojrozmerné pole

Iné

Uvedená klasifikácia nie je ani zďaleka úplná. Prvky zložitých dátových štruktúr môžu byť tak jednoduché, ako aj príklady zložitých dátových štruktúr, napríklad dátová štruktúra les Je zoznam neprekrývajúcich sa stromov. Teraz sa pokúsim stručne popísať uvedené triedy zložitých dátových štruktúr. Prvý stupeň klasifikácie je založený na rozdieloch v spôsobe oslovovania a vyhľadávania jednotlivých prvkov v súbore zložitých dátových štruktúr.

Lineárne dátové štruktúry

Prvok lineárnej dátovej štruktúry je charakterizovaný poradovým číslom alebo indexom v lineárnom slede prvkov.

Pole- je to v statické lineárna štruktúra rovnakého typuúdaje, optimalizované pre operácie na nájdenie prvku podľa jeho indexu. Jednoznačné umiestnenie prvku v pamäti je zabezpečené práve rovnomernosťou prvkov v poli a je určené súčinom jeho indexu a veľkosti pamäte obsadenej jedným prvkom.

Lineárne pole.
Adresa (prvok (index)) = veľkosť_bunky * index.

Zoznam Je dynamická lineárna dátová štruktúra, v ktorej každý prvok odkazuje buď iba na predchádzajúci - jednosmerný lineárny zoznam, alebo na predchádzajúci a nasledujúci - obojsmerný lineárny zoznam... Krása tejto dátovej štruktúry, okrem toho, že sa dá meniť veľkosť, spočíva v jej jednoduchosti implementácie. Tiež kvôli prítomnosti odkazov môže každý prvok v zozname na rozdiel od poľa zaberať iné množstvo pamäte. Adresa prvého prvku v lineárnom zozname je jednoznačne určená adresou samotného zoznamu.

Prepojený zoznam Je variantom bežného lineárneho zoznamu, optimalizovaného na pridávanie a odstraňovanie prvkov. Optimalizácia spočíva v tom, že prvky prepojeného zoznamu sa nemusia v pamäti nachádzať jeden po druhom. Poradie prvkov je určené odkazom na prvý prvok (nemusí byť na úplnom začiatku pamäte vyhradenej pre zoznam) a postupnosťou odkazov na zvyšné prvky zoznamu.

Prepojený zoznam.

Stoh Je dynamická lineárna dátová štruktúra, pre ktorú sú definované iba dve operácie na zmenu množiny prvkov: pridanie prvku na koniec a odstránenie posledného prvku. Tiež hovoria, že zásobník implementuje princíp LIFO (Last in, First Out) - posledný dovnútra a prvý von. Napríklad počas vykonávania programového kódu počítač, ak je potrebné zavolať procedúru alebo funkciu, najprv zatlačí ukazovateľ na miesto svojho volania v zásobníku, takže po dokončení vykonávania jeho kódu , správne sa vráti k nasledujúcemu pokynu za bodom hovoru. Táto dátová štruktúra sa nazýva zásobník volaní podprogramu.

Stoh.

Fronta- veľmi podobná nezásobová, dynamická dátová štruktúra, len s tým rozdielom, že implementuje princíp FIFO (First in, First out) - prvý prišiel a prvý odišiel. Pre príklady v reálnom živote, ako už názov napovedá, netreba chodiť ďaleko. Pri programovaní fronty napríklad spracovávajú udalosti používateľského rozhrania, volania klientov a ďalšie požiadavky na informácie.

Fronta.

Tabuľka hash Ide o najkomplexnejší typ dynamickej lineárnej dátovej štruktúry. Tabuľka hash je optimalizovaná na rýchle nájdenie položiek vypočítaním adresy položky ako hodnoty hash. Argument hašovacej funkcie je kľúč spojený s prvkom, napríklad jeho poradové číslo. Aby sa zaručili jedinečné hašovacie hodnoty pre jedinečné kľúčové hodnoty (zabránenie kolíziám), hašovacia tabuľka okrem zložitých algoritmov veľkoryso využíva aj pamäť RAM. Použitie hašovacích tabuliek musí byť odôvodnené a starostlivo zvážené.

Hierarchické dátové štruktúry

Prvok v hierarchickej dátovej štruktúre je charakterizovaný prepojením na prvok vyššej úrovne v hierarchii (alebo prepojeniami na prvky nižšej úrovne) a (voliteľne) poradovým číslom v lineárnej postupnosti jeho úrovne (hierarchické zoznamy) .

Stromy- dynamická hierarchická dátová štruktúra reprezentovaná jedným koreňovým uzlom a jeho potomkami. Maximálny počet detí každého uzla a určuje rozmer stromu... Samostatne rozlišovať binárne alebo binárne stromy pretože sa používajú v triediacich a vyhľadávacích algoritmoch: každý uzol binárneho súboru vyhľadávací strom priraďuje prvok z nejakej zoradenej množiny, všetky jeho „ľavé“ podradené prvky – k menším prvkom a všetky jeho „pravé“ podriadené prvky – veľké prvky. Každý uzol v strome je jednoznačne identifikovaný sekvenciou neopakujúcich sa uzlov od koreňa po cestu. Dĺžka cesty je úroveň uzla v stromovej hierarchii. Pre binárne alebo binárne stromy sa rozlišujú nasledovné druhy rekurzívneho prechodu všetkých jeho prvkov (kučeravé zátvorky označujú poradie návštevy prvkov každého uzla, počnúc od koreňa):

• priama alebo predpona
  (uzol, ľavý podstrom, pravý podstrom);


• spätný alebo postfix
  (ľavý podstrom, pravý podstrom, uzol);


• symetrické alebo infixové
  (ľavý podstrom, uzol, pravý podstrom);

Ak chcete zobraziť položky vo vzostupnom poradí, prejdite stromom vyhľadávania v symetrickom poradí. Aby sa prvky zobrazovali v opačnom poradí, počas prechodu sa musí zmeniť poradie návštevy podstromov.

Binárny (binárny) strom.

Hierarchický zoznam- symbióza lineárneho zoznamu a stromu. Každý prvok zoznamu môže byť aj začiatkom zoznamu ďalšej podúrovne hierarchie. Príkladom hierarchického zoznamu je štruktúra internetových fór: postupnosť správ tvorí lineárny zoznam, zatiaľ čo správy, ktoré sú odpoveďami na iné správy, vytvárajú nové vlákna diskusie.

Hierarchický zoznam.

Sieťové dátové štruktúry

Prvok v dátovej štruktúre siete je charakterizovaný množinou väzieb s inými – susednými prvkami. V takýchto dátových štruktúrach nie je explicitne zvýraznený ani počiatočný, ani koreňový prvok.

Graf- dynamická sieťová dátová štruktúra, reprezentovaná množinou vrcholov a hrán - väzby medzi vrcholmi. Každý vrchol môže byť spojený s ľubovoľným počtom iných vrcholov alebo sám so sebou. Tu už neexistuje jasná hierarchia. Ak považujeme uzly stromu za vrcholy grafu a spojenia medzi uzlami stromu na rôznych úrovniach hierarchie za okraje grafu, potom samotný strom možno považovať za graf, ktorý obsahujú cykly alebo acyklický graf. Ak je pre každú hranu grafu definovaný smer, potom ide o orientovaný graf. Okrem smeru môže mať každá hrana grafu svoju váhu. Pomocou grafu sa napríklad modelujú dopravné siete a riešia sa problémy optimalizácie dopravného toku. Zaťaženie alebo naopak priechodnosť dopravných ciest je daná hmotnosťou príslušných rebier.

Graf.

Orientovaný graf.

Prvok v tabuľkovej dátovej štruktúre je charakterizovaný dvojrozmerným indexom: indexom riadku a indexom stĺpca, na priesečníku ktorého sa nachádza. Príkladmi tabuľkových dátových štruktúr sú tabuľky.

Odhad zložitosti algoritmov

Odhad zložitosti algoritmov neznamená intelektuálne úsilie, ktoré autori vynaložili pri ich vývoji, ale závislosť počtu elementárnych operácií vykonaných počítačom od množstva spracovávaných informácií. Napríklad, ako bude počet porovnaní dvoch čísel závisieť od dĺžky pôvodnej sekvencie počas činnosti triediaceho algoritmu. Zámerne som definíciu trochu zúžil, keďže ďalej sa budeme baviť len o počte elementárnych operácií. V skutočnosti je zložitosť algoritmu určená nielen počtom operácií, ale aj množstvom výpočtových zdrojov zapojených do riešenia problému a predovšetkým RAM. Čím jednoduchší je algoritmus, tým je pravdepodobnejšie, že sa spustí. Zložité a rýchle algoritmy často využívajú pomocné dátové štruktúry a v dôsledku toho spotrebúvajú dodatočnú pamäť. Zákon zachovania energie alebo „za všetko treba platiť“. Jedným z príkladov „okrajovej optimalizácie“, o ktorej sme už hovorili, je hašovacia tabuľka. Osobne neviem, ako je hašovacia tabuľka usporiadaná a ako hašovacie funkcie vyzerajú (asi to nie je jednoduché), ale na druhej strane, čas vyhľadávania prvkov podľa kľúča prakticky nezávisí od veľkosti tabuľky. Tu je malá teória.

Odhad zložitosti algoritmov sa vykonáva pomocou matematického aparátu asymptotická analýza a odvodenie asymptotického odhadu zložitosti.

Asymptotický odhad zložitosti označuje sa gréckym písmenom Θ (theta).

f (n) = Θ (g (n)), ak existujú c1, c2> 0 a n0 tak, že c1 * g (n) n0.

Funkcia g (n) je asymptoticky presný odhad zložitosti algoritmu - funkcia f (n), vyššie uvedená nerovnosť sa nazýva asymptotická rovnosť a samotný zápis Θ symbolizuje množinu funkcií, ktoré rastú „tak rýchlo ako funkcia g (n), tj e. až po násobenie konštantou. Ako vyplýva z vyššie uvedenej nerovnosti, odhad Θ je súčasne hornou aj dolnou hranicou zložitosti. Nie vždy je možné získať skóre touto formou, preto sa horný a dolný odhad niekedy určuje oddelene.

Horný odhad obtiažnosti označuje sa gréckym písmenom Ο (omikrón) a je to súbor funkcií, ktoré nerastú rýchlejšie ako g (n).

f (n) = Ο (g (n)), ak existuje c> 0 a n0 tak, že 0n0.

Nižší odhad zložitosti označuje sa gréckym písmenom Ω (omega) a je to súbor funkcií, ktoré rastú nie pomalšie ako g (n).

f (n) = Ω (g (n)), ak existuje c> 0 a n0 tak, že 0n0.

V dôsledku toho: asymptotický odhad existuje iba vtedy, ak sa spodná a horná hranica zložitosti algoritmu zhoduje. V praxi analyzovania algoritmov sa odhad zložitosti najčastejšie chápe ako horný odhad zložitosti. Je to celkom logické, keďže najdôležitejší je odhad času, za ktorý algoritmus zaručene dokončí svoju prácu, a nie čas, za ktorý určite nedokončí.

Práca s lineárnymi dátovými štruktúrami

No a na záver uvediem odhady zložitosti základných operácií s lineárnymi dátovými štruktúrami, a to pridávanie, mazanie a vyhľadávanie prvku podľa indexu alebo kľúča. Elementárne operácie sú v tomto prípade operácie porovnávania, enumerácie, výpočtu adresy alebo permutácie prvkov množiny dátovej štruktúry. V kontingenčnej tabuľke sú okrem horného odhadu zložitosti uvedené aj komponenty knižnice zodpovedajúce uvedeným dátovým štruktúram. Základné lineárne dátové štruktúry sú teda pripravené a dostupné pre všetkých vývojárov softvéru na platforme.

Štruktúry a dátové typy. Polia, stromy, zoznamy, grafy. Dátové operácie.

Dáta uložené v pamäti počítača sú súborom núl a jednotiek (bitov). Bity sa kombinujú v poradí: bajty, slová atď. Každá časť pamäte RAM, ktorá môže obsahovať jeden bajt alebo slovo, má priradené poradové číslo (adresu).

Aký význam majú údaje, aké symboly sú vyjadrené - abecedné alebo číselné, čo znamená to alebo ono číslo - to všetko určuje program spracovania. Všetky údaje potrebné na riešenie praktických problémov sú rozdelené do niekoľkých typov a s pojmom typ sa spája nielen reprezentácia údajov v adresnom priestore, ale aj spôsob ich spracovania.

Akékoľvek údaje možno klasifikovať do jedného z dvoch typov: základné (jednoduché), ktorých forma je určená architektúrou počítača, alebo komplexné, navrhnuté používateľom na riešenie konkrétnych problémov.

Jednoduché dátové typy sú symboly, čísla atď. prvkov, ktorých ďalšie drvenie nemá zmysel. Dátové štruktúry (komplexné typy) sa tvoria z elementárnych údajov.

Niektoré štruktúry:

Pole (funkcia s konečnou doménou definície) je jednoduchý súbor dátových prvkov rovnakého typu, prostriedok na prácu so skupinou dát rovnakého typu. Jeden prvok poľa je špecifikovaný indexom. Pole môže byť jednorozmerné, dvojrozmerné atď. Typy ring, stack, queue a deque sú príchute jednorozmerných polí s premenlivou dĺžkou.

Ak pole vždy zaberá súvislú časť pamäte, potom je zoznam najjednoduchším príkladom takzvanej dynamickej dátovej štruktúry. V dynamických dátových štruktúrach je objekt obsiahnutý v rôznych pamäťových oblastiach, ktorých počet a zloženie sa môže počas prevádzky meniť. Jednota takéhoto objektu je udržiavaná kombináciou jeho častí v popise triedy.

Najjednoduchší lineárny zoznam je lineárna postupnosť prvkov. Pre každý z nich, okrem posledného, ​​existuje ďalší prvok a pre každý, okrem prvého - predchádzajúci. Zoznam sa tradične zobrazuje ako postupnosť prvkov, z ktorých každý obsahuje odkaz (ukazovateľ) na nasledujúci a/alebo predchádzajúci prvok, ale všimnite si, že vo fyzickej reprezentácii prvkov zoznamu nemusia byť žiadne prepojenia.

Typický súbor operácií so zoznamom bude zahŕňať pridávanie, mazanie a vyhľadávanie jeho prvkov, výpočet dĺžky zoznamu a postupné spracovanie prvkov (iterovanie) v zozname.

Rovnako ako polia, mnohé knižnice tried zahŕňajú schopnosť popisovať zoznamy a manipulovať s nimi (napríklad CList knižnice tried MFC). Napriek tomu je často potrebné popísať vlastné dátové štruktúry vo forme zoznamov obsahujúcich vhodnejšie operácie pre riešený problém, jednoduchšie (a teda efektívnejšie) ako štandardné, alebo so špecifickými vlastnosťami (napr. zoznamy).

Pri popise zoznamu je reprezentácia každej položky v zozname zvyčajne opísaná ako samostatná trieda. Táto trieda má ako svoj atribút odkaz na nasledujúci a/alebo predchádzajúci prvok.

Záznam (karteziánsky súčin) - súbor dátových prvkov rôznych typov. V najjednoduchšom prípade záznam obsahuje konštantný počet prvkov, ktoré sa nazývajú polia. Súbor záznamov rovnakej štruktúry sa nazýva súbor. (Súbor sa nazýva aj súbor údajov v externej pamäti, napríklad magnetický disk). Aby bolo možné extrahovať jednotlivé záznamy zo súboru, každý záznam má pridelený jedinečný názov alebo číslo, ktoré slúži ako jeho identifikátor a nachádza sa v samostatnom poli. Tento identifikátor sa nazýva kľúč.

Dátové štruktúry ako pole alebo záznam zaberajú v pamäti počítača konštantný objem, preto sa nazývajú statické štruktúry. Mnohé patria aj do statických konštrukcií.

Existuje množstvo štruktúr, ktoré môžu meniť svoju dĺžku – takzvané dynamické štruktúry. Patria sem strom, zoznam, odkaz.

Dôležitou štruktúrou, ktorá na umiestnenie svojich prvkov vyžaduje nelineárny adresný priestor, je strom. Existuje mnoho dátových štruktúr, ktoré môžu byť reprezentované ako stromy. Ide napríklad o klasifikačné, hierarchické, rekurzívne a iné štruktúry.

Zovšeobecnené štruktúry alebo dátové modely.

Vyššie sme uvažovali o niekoľkých typoch štruktúr, ktoré sú zbierkami dátových prvkov: pole, strom, záznam. Zložitejší dátový typ môže zahŕňať tieto štruktúry ako členov. Prvky záznamu môžu byť napríklad pole, zásobník, strom atď.

Existuje široká škála zložitých typov údajov, ale štúdie uskutočnené na veľkom praktickom materiáli ukázali, že medzi nimi možno rozlíšiť niekoľko najbežnejších. Generické štruktúry sa tiež nazývajú dátové modely, pretože sú odrážajú pohľad používateľa na údaje z reálneho sveta.

Každý dátový model musí obsahovať tri komponenty:

Štruktúra údajov – popisuje pohľad používateľa na prezentáciu údajov.

Množina platných operácií vykonaných na dátovej štruktúre. Dátový model predpokladá minimálne prítomnosť jazyka definície údajov (DLL), ktorý popisuje štruktúru ich úložiska, a jazyka manipulácie s údajmi (DMA), ktorý zahŕňa operácie na získavanie a úpravu údajov.

Obmedzenia integrity sú mechanizmus na udržiavanie konzistencie údajov domény na základe formálne opísaných pravidiel.

V procese historického vývoja boli v DBMS použité nasledujúce dátové modely:

Hierarchický – V tomto modeli je jeden hlavný objekt a ostatné – podriadené – objekty, ktoré sú na rôznych úrovniach hierarchie. Vzťahy objektov tvoria hierarchický strom s jedným koreňovým objektom.

Sieťový – sieťový prístup k organizovaniu údajov je rozšírením hierarchického prístupu. V hierarchických štruktúrach musí mať podriadený záznam práve jedného rodiča; v sieťovej dátovej štruktúre môže mať potomok ľubovoľný počet predkov.

V sieťovom dátovom modeli môže byť akýkoľvek objekt nadriadený aj podriadený a môže sa podieľať na vytváraní ľubovoľného počtu vzťahov s inými objektmi.

Relačný – V relatívnom modeli sú údaje rozdelené do množín, ktoré tvoria tabuľkovú štruktúru. Táto štruktúra tabuľky sa skladá z jednotlivých dátových položiek nazývaných polia. Jeden súbor alebo skupina polí sa nazýva záznam.

Metódy prístupu k údajom.

Problémy prezentácie údajov úzko súvisia s operáciami, ktorými sa tieto údaje spracúvajú. Tieto operácie zahŕňajú načítanie, úpravu, vrátane a vylúčenie údajov. Všetky vyššie uvedené operácie sú založené na operácii prístupu, ktorú nemožno brať do úvahy bez ohľadu na spôsob prezentácie.

Pri problémoch s vyhľadávaním sa predpokladá, že všetky dáta sú uložené v pamäti so špecifickou identifikáciou a ak hovoríme o prístupe, znamená to predovšetkým prístup k dátam (nazývané kľúče), ktoré jednoznačne identifikujú súvisiace dátové sady.

Predpokladajme, že potrebujeme zorganizovať prístup k súboru obsahujúcemu množinu identických záznamov, z ktorých každý má jedinečnú hodnotu poľa kľúča. Najjednoduchší spôsob vyhľadávania je postupne prehľadávať každý záznam v súbore, kým nenájdete ten, ktorého hodnota kľúča zodpovedá kritériám vyhľadávania. Je zrejmé, že táto metóda je dosť neefektívna, pretože záznamy v súbore nie sú usporiadané podľa hodnoty poľa kľúča. Triedenie záznamov v súbore tiež nie je použiteľné, pretože je ešte časovo náročnejšie a musí sa vykonať po pridaní každého záznamu. Postupujú teda nasledovne – kľúče sa spolu s ukazovateľmi na zodpovedajúce záznamy v súbore skopírujú do inej štruktúry, čo umožňuje rýchle operácie triedenia a vyhľadávania. Pri prístupe k údajom sa najskôr v tejto štruktúre nájde zodpovedajúca hodnota kľúča a potom sa získa záznam zo súboru z ukazovateľa, ktorý je s ním uložený.

Existujú dve triedy metód, ktoré implementujú prístup ku kľúčovým údajom:

Metódy vyhľadávania stromov,

Hash metódy.

Teória grafov je dôležitou súčasťou výpočtovej matematiky. Pomocou tejto teórie sa rieši veľké množstvo problémov z rôznych oblastí. Graf sa skladá z mnohých vrcholov a mnohých hrán, ktoré spájajú vrcholy. Z hľadiska teórie grafov je úplne jedno, aký význam majú vrcholy a hrany. Vrcholy môžu byť osady a okraje cesty, ktoré ich spájajú, alebo vrcholy sú podprogramy, spojené vrcholmi hranami znamená interakciu podprogramov. Často záleží na smere oblúka v grafe. Ak má hrana smer, nazýva sa oblúk a graf so smerovanými hranami sa nazýva digraf.

Uveďme teraz formálnejšiu základnú definíciu teórie grafov. Graf G je usporiadaná dvojica (V, E), kde V je neprázdna množina vrcholov, E je množina dvojíc prvkov množiny V a dvojica prvkov z V sa nazýva hrana. Usporiadaná dvojica prvkov z V sa nazýva oblúk. Ak sú všetky páry v E usporiadané, potom sa graf nazýva orientovaný.

Cesta je ľubovoľná postupnosť vrcholov v digrafe tak, že v tejto postupnosti môže vrchol b nasledovať po vrchole a iba vtedy, ak z a do b nasleduje oblúk. Podobne môžete definovať cestu pozostávajúcu z oblúkov. Cesta začínajúca v jednom vrchole a končiaca v jednom vrchole sa nazýva cyklus. Graf, v ktorom nie sú žiadne cykly, sa nazýva acyklický.

Dôležitým špeciálnym prípadom grafu je strom.

Definícia: Strom je konečná množina pozostávajúca z jedného alebo viacerých prvkov nazývaných uzly tak, že:

Medzi uzlami existuje vzťah rodič-dieťa;

Existuje len jeden uzol, ktorý nemá zdroj. Nazýva sa koreň;

Všetky uzly okrem koreňa majú iba jeden zdroj; každý uzol môže mať niekoľko detí;

Pôvod generovaný vzťah funguje len jedným smerom, t.j. žiadny potomok nejakého uzla sa nemôže stať jeho predkom.

Počet vytvorených jednotlivých uzlov (počet podstromov daného koreňa) sa nazýva jeho stupeň. Uzol s nulovým stupňom sa nazýva listový alebo koncový uzol. Maximálna hodnota stupňa všetkých uzlov v danom strome sa nazýva stupeň stromu.

Ak sa v strome medzi vygenerovanými uzlami, ktoré majú spoločný zdroj, ich poradie považuje za podstatné, potom sa strom nazýva usporiadaný. Pri problémoch s hľadaním sa takmer vždy zohľadňujú usporiadané stromy.

Usporiadaný strom, ktorého stupeň je najviac 2, sa nazýva binárny strom. Binárny strom sa používa najmä pri vyhľadávaní v RAM. Algoritmus vyhľadávania: najprv sa argument vyhľadávania porovná s kľúčom v koreňovom adresári. Ak sa argument zhoduje s kľúčom, vyhľadávanie je ukončené, ak sa nezhoduje, tak v prípade, keď je argument menší ako kľúč, hľadanie pokračuje v ľavom podstrome a v prípade, že je viac ako kľúč v pravom podstrome. Zvýšením úrovne o 1 zopakujte porovnanie, pričom aktuálny uzol považujete za koreň.

Binárne stromy sú obzvlášť účinné, keď nie je vopred známy súbor kľúčov alebo keď sa tento súbor rýchlo mení. Je zrejmé, že s variabilnou sadou kľúčov je lepšie mať vyvážený strom.

Definícia: Binárny strom sa považuje za vyvážený, ak sa výška ľavého podstromu každého uzla líši od výšky pravého podstromu najviac o 1.

Hašovanie.

Táto metóda sa používa, keď je celá sada kľúčov známa vopred a môže byť umiestnená v pamäti RAM počas trvania spracovania. V tomto prípade je vybudovaná špeciálna funkcia, ktorá jedinečne mapuje množinu kľúčov na množinu ukazovateľov, nazývaná hašovacia funkcia (z anglického „to hash“ – rezať, brúsiť). S takouto funkciou je možné vypočítať adresu záznamu v súbore podľa daného vyhľadávacieho kľúča. Vo všeobecnosti sú kľúčové údaje používané na určenie adresy záznamu usporiadané v tabuľke nazývanej hašovacia tabuľka.

Ak je sada kľúčov vopred neznáma alebo je veľmi veľká, potom sa upustí od myšlienky jednoznačne vypočítať adresu záznamu pomocou jeho kľúča a hašovacia funkcia sa považuje jednoducho za funkciu, ktorá rozptýli sadu kľúčov do súbor adries.

• Preklad

Samozrejme, môžete byť úspešným programátorom aj bez posvätných znalostí dátových štruktúr, tie sú však v niektorých aplikáciách absolútne nenahraditeľné. Napríklad, keď potrebujete vypočítať najkratšiu cestu medzi dvoma bodmi na mape alebo nájsť meno v telefónnom zozname obsahujúcom povedzme milión záznamov. Nehovoriac o tom, že dátové štruktúry sa v športovom programovaní neustále používajú. Pozrime sa na niektoré z nich podrobnejšie.

Fronta

Tak pozdravte Loopy!

Loopy rada hrá hokej so svojou rodinou. A pod pojmom "hrať" mám na mysli:

Keď korytnačky vletia do brány, sú hodené na vrchol hromady. Všimnite si, že prvá korytnačka pridaná do zásobníka odchádza ako prvá. To sa nazýva Fronta... Rovnako ako v tých radoch, ktoré vidíme v každodennom živote, prvá položka pridaná do zoznamu je prvá, ktorá ho opustí. Táto štruktúra je tiež tzv FIFO(Prvý dnu prvý von).

Čo tak operácie vloženia a vymazania?

Q = def insert (elem): q.append (elem) # pridanie položky na koniec fronty print q def delete (): q.pop (0) # odstránenie nulovej položky z frontu print q

Stoh

Po takomto zábavnom hokeji robí Loopy palacinky pre každého. Dá ich na jednu hromadu.

Keď sú všetky palacinky hotové, Loopy ich jednu po druhej naservíruje celej rodine.

Všimnite si, že prvá palacinka, ktorú urobí, bude podávaná ako posledná. To sa nazýva Stoh... Posledná položka pridaná do zoznamu bude prvá, ktorá odíde. Aj táto dátová štruktúra sa nazýva LIFO(Last In First Out).

Pridávať a odstraňovať položky?

S = def push (elem): # Pridanie položky do zásobníka - Push s.append (elem) print s def customPop (): # odstránenie položky zo zásobníka - Pop s.pop (len (s) -1) tlač s

Hromada

Už ste niekedy videli Density Tower?

Všetky prvky zhora nadol sú umiestnené na svojich miestach podľa ich hustoty. Čo sa stane, ak dovnútra vhodíte nový predmet?

Uskutoční sa v závislosti od jeho hustoty.

Takto to funguje Hromada.

Halda je binárny strom. To znamená, že každý rodič má dve deti. A hoci túto dátovú štruktúru nazývame halda, vyjadruje sa v podobe pravidelného poľa.
Tiež halda je vždy logn high, kde n je počet prvkov

Obrázok ukazuje maximálnu hromadu založenú na nasledujúcom pravidle: deti menšie rodič. Sú tam aj min-hromady, kde sú deti vždy viac rodič.

Niekoľko jednoduchých funkcií pre prácu s haldami:

Globálna halda global currSize def parent (i): # Získať rodičovský index i-tého prvku return i / 2 def left (i): # Získať ľavý potomok i-tého prvku return 2 * i def right (i ): # Získajte správne dieťa i-tého výnosu (2 * i + 1)

Pridanie položky do existujúcej haldy
Najprv položku pridáme na úplný spodok haldy, t.j. na koniec poľa. Potom ho prehodíme s rodičom, kým nezapadne na miesto.

Algoritmus:

1. Pridajte položku na úplný spodok haldy.
2. Porovnajte pridaný prvok s rodičom; ak je objednávka správna, zastavíme sa.
3. Ak nie, vymeníme prvky a vrátime sa k predchádzajúcemu bodu.

kód:

Def swap (a, b): # zameňte prvok s indexom a za prvok s indexom b temp = halda [a] halda [a] = halda [b] halda [b] = dočasná def insert (elem): global currSize index = len (hromada) heap.append (elem) currSize + = 1 par = nadradený (index) príznak = 0, zatiaľ čo príznak! = 1: if index == 1: # Dosiahnutý príznak koreňového prvku = 1 elf halda> prvok: # Ak je index koreňového prvku väčší ako index nášho prvku - náš prvok je na mieste príznak = 1 inak: # Vymeňte rodičovský prvok za náš swap (par, index) index = par par = nadradený (index) print hromada
Maximálny počet prechodov cyklu while sa rovná výške stromu alebo logn, preto je zložitosť algoritmu O (logn).

Získanie prvku maximálnej haldy
Prvý prvok v halde je vždy maximum, takže ho jednoducho vymažeme (vopred si to zapamätáme) a nahradíme najnižším. Potom dáme haldu v správnom poradí pomocou funkcie:

MaxHeapify ().

Algoritmus:

1. Vymeňte koreňový prvok za najnižší.
2. Porovnajte nový koreňový prvok s deťmi. Ak sú v správnom poradí, zastavte sa.
3. Ak nie, nahraďte koreňový prvok jedným z potomkov (menší pre minimálnu haldu, väčší pre maximálnu haldu) a zopakujte krok 2.

Def extractMax (): global currSize if currSize! = 0: maxElem = halda halda = halda # Nahraďte koreňový element najnovším heap.pop (currSize) # Odstráňte posledný element currSize - = 1 # Znížte veľkosť haldy maxHeapify ( 1) return maxElem def maxHeapify (index): globálne currSize lar = index l = vľavo (index) r = vpravo (index) # Vypočítajte, ktoré dieťa je väčšie; ak je väčší ako materský, vymeň ak l<= currSize and heap[l] >halda: lar = l ak r<= currSize and heap[r] >halda: lar = r ak lar! = index: swap (index, lar) maxHeapify (lar)
A opäť, maximálny počet volaní funkcie maxHeapify sa rovná výške stromu alebo logn, čo znamená, že zložitosť algoritmu je O (logn).

Vytvorenie hromady ľubovoľného náhodného poľa
Dobre, existujú dva spôsoby, ako to urobiť. Prvým je vložiť každý prvok do haldy jeden po druhom. Je to jednoduché, ale úplne neúčinné. Zložitosť algoritmu v tomto prípade bude O (nlogn), pretože funkcia O (logn) sa spustí n-krát.

Efektívnejším spôsobom je použitie funkcie maxHeapify na „ čiastkové haldy', Od (currSize / 2) po prvý prvok.

Zložitosť sa ukáže ako O (n) a dôkaz tohto tvrdenia, žiaľ, presahuje rámec tohto článku. Len pochopte, že položky v časti hromady currSize / 2 až currSize nemajú žiadne potomky a väčšina takto vytvorených „podhaldov“ bude mať výšku menšiu ako logn.

Def buildHeap (): globálne currSize pre i v rozsahu (currSize / 2, 0, -1): # tretí argument v rozsahu () je iteračný krok, v tomto prípade určuje smer. tlač haldy maxHeapify (i) currSize = dĺžka (hromada) -1

Naozaj, prečo je to všetko?

Na implementáciu špeciálneho typu triedenia, napodiv, nazývaného „ haldy triediť“. Na rozdiel od menej efektívneho „triedenia vložiek“ a „bublinového triedenia“ so svojou strašnou zložitosťou O (n 2) má „triedenie haldy“ zložitosť O (nlogn).

Implementácia je obscénne jednoduchá. Len pokračujte v postupnom načítavaní maximálneho (koreňového) prvku z haldy a zapisujte ho do poľa, kým halda nebude prázdna.

Def heapSort (): pre i v rozsahu (1, dĺžka (hromada)): print halda halda.insert (len (hromada) -i, extraktMax ()) # vložte maximálny prvok na koniec poľa currSize = dĺžka ( hromada) -1
Aby som zhrnul všetko vyššie uvedené, napísal som niekoľko riadkov kódu obsahujúceho funkcie pre prácu s haldou a pre fanúšikov OOP som všetko navrhol vo forme triedy.

Jednoduché, však? A tu je oslavujúci Lupi!

Hash

Loopy chce naučiť svoje deti rozlišovať tvary a farby. K tomu si domov priniesla obrovské množstvo pestrofarebných figúrok.

Po chvíli sa korytnačky konečne poplietli.

Vytiahla teda ďalšiu hračku, aby si veci trochu uľahčila.

Bolo to oveľa jednoduchšie, pretože korytnačky už vedeli, že tvary sú triedené podľa tvaru. Čo ak označíme každý príspevok?

Korytnačky teraz potrebujú skontrolovať stĺp so špecifickým číslom a vybrať si z oveľa menšieho počtu figúrok, ktoré potrebujú. A ak máme aj samostatný stĺpik pre každú kombináciu tvaru a farby?

Povedzme, že číslo príspevku sa vypočíta takto:

Celé meno Leto tre námestie
ph + u + o + t + p + e = 22 + 10 + 16 + 20 + 18 + 6 = stĺpec 92

Kra ospalý rovno obdĺžnik
k + p + a + n + p + i = 12 + 18 + 1 + 17 + 18 + 33 = stĺpec 99

Vieme, že 6 * 33 = 198 možných kombinácií, čo znamená, že potrebujeme 198 pilierov.

Nazvime tento vzorec na výpočet čísla piliera - Hash funkcia.

kód:
def hashFunc (kúsok): words = piece.split ("") # rozdeliť reťazec na slová farba = tvar slov = slová poleNum = 0 pre i v rozsahu (0, 3): poleNum + = ord (farba [i]) - 96 pólNum + = ord (tvar [i]) - 96 návrat pólNum
(Azbuka je trochu zložitejšia, ale pre jednoduchosť som to nechal tak. - približne.)

Ak teraz potrebujeme zistiť, kde je uložený ružový štvorec, môžeme vypočítať:
hashFunc („ružový štvorec“)

Toto je príklad hašovacej tabuľky, kde umiestnenie prvkov určuje hašovacia funkcia.
Pri tomto prístupe čas strávený hľadaním akéhokoľvek prvku nezávisí od počtu prvkov, t.j. O (1). Inými slovami, čas vyhľadávania v hašovacej tabuľke je konštantná hodnota.

Dobre, ale povedzme, že hľadáme „ auto amelly rovno moangle "(ak, samozrejme, farba" karamel "existuje).

HashFunc („karamelový obdĺžnik“)
vráti nám 99, čo je rovnaké ako číslo pre červený obdĺžnik. To sa nazýva " Zrážka“. Na riešenie kolízií používame „ Metóda reťazenia“, čo znamená, že každý stĺpec obsahuje zoznam, v ktorom hľadáme záznam, ktorý potrebujeme.

Takže len položíme karamelový obdĺžnik na červený a vyberieme jeden z nich, keď hashovacia funkcia ukazuje na tento stĺpik.

Kľúčom k dobrej hašovacej tabuľke je výber správnej hašovacej funkcie. Toto je nepochybne najdôležitejšia vec pri vytváraní hašovacej tabuľky a ľudia trávia obrovské množstvo času vývojom kvalitných hašovacích funkcií.
V dobrých tabuľkách žiadna pozícia neobsahuje viac ako 2-3 prvky, inak hashovanie nefunguje dobre a musíte zmeniť funkciu hash.

Opäť vyhľadávanie nezávislé na položke! Hašovacie tabuľky môžeme použiť na čokoľvek, čo je gigantické.

Hash tabuľky sa tiež používajú na nájdenie reťazcov a podreťazcov vo veľkých kúskoch textu pomocou algoritmu Rabin-Karp alebo algoritmus Knut-Morris-Pratt, čo je užitočné napríklad na identifikáciu plagiátov vo vedeckých prácach.

V tomto, myslím, môžeme skončiť. V budúcnosti sa plánujem pozrieť napríklad na zložitejšie dátové štruktúry Fibonacciho hromada a Segmentový strom... Dúfam, že sa táto neformálna príručka ukázala ako zaujímavá a užitočná.

Preložené pre Habr zamknuté na