Meniul
Acasăexcela

Structurarea datelor. Conceptul de bază de date și bancă de date. Clasificarea bazelor de date. Tipuri de modele de date: ierarhice, de rețea, relaționale. Tipuri și structuri de date

Ce tipuri de structuri de date există? (Puteți indica numele structurii într-un anumit limbaj de programare) Aș dori să le cunosc scopul, punctele forte și părţile slabe. Mă interesează și clasificarea, este scrisă corect în wiki? Lista structurilor de date Nu este necesar încă un răspuns detaliat pentru fiecare structură, doar pe scurt, de exemplu, spuneți care este avantajul acestei structuri față de altele (de exemplu, cel mai timp rapid acces la un element, abilitatea de a schimba dinamic cantitatea de memorie etc.) Poate nu ar trebui să răspunzi la toate odată, brusc volumul răspunsului va fi semnificativ, te poți dezabona pentru cel puțin una dintre structurile pe care le ai știu bine și voi adăuga informații la postarea principală. Va fi foarte convenabil să aveți o astfel de listă în fața ochilor, puteți să o verificați imediat și să selectați ceea ce aveți nevoie.

1. Structuri liniare de date sunt structuri de date în care trecerea de la un element de date la altul nu depinde de niciunul conditii logice, adică în structurile liniare se folosesc numai conexiuni necondiţionate de elemente.

1.1 Lista Poate fi la fel ca o matrice, dar vă permite să adăugați elemente în orice locație, să eliminați elemente din orice locație și să obțineți numărul curent de elemente.

1.2 Matrice asociativă

1.3 Tabel hash este o matrice obișnuită cu o adresare neobișnuită specificată de o funcție hash. Cea mai bună alegere dacă nu aveți nevoie să sortați informații, ci doar acces rapid Pentru ea. Memoria suplimentară este irosită.

avantaje:

  • O proprietate importantă a tabelelor hash este că, în baza unor ipoteze rezonabile, toate cele trei operațiuni (căutare, inserare, ștergere a elementelor) sunt finalizate în medie în timp O(1), cu un timp în cel mai rău caz de O(n).

defecte:

  • Repetați nu în ordinea crescătoare a tastelor
  • Nevoia de „rehashing” atunci când numărul de obiecte stocate crește (?)
  • este imposibil să se implementeze operații suplimentare cu rulare rapidă MIN, MAX și un algoritm pentru parcurgerea tuturor perechilor stocate în ordinea crescătoare sau descrescătoare a tastelor (?)
  • nu menține ordinea și nu păstrează ordinea elementelor (?)
  • posibilitatea de coliziuni

forma generala de descriere a structurilor:

Scopul principal, descriere

Operațiuni suportate

Avantaje

Defecte

Implementare gata într-un limbaj de programare (numele funcției sau al clasei)

simboluri

(?) - în îndoială, vă rugăm să corectați dacă este scris greșit sau, dimpotrivă, să o confirmați pentru a elimina ambiguitatea.

editarea continuă...

Subiectul acestui articol se referă din nou teoria programarii, deci va trebui să apelezi la diverse clasificări și să operezi în termeni matematici. Structurile de date sunt practic primul lucru predat în timpul cursurilor de formare. Evaluarea complexității algoritmilor este a doua. Poate părea că aceste două probleme au puțină legătură, dar nu este cazul și, pe măsură ce povestea progresează, va deveni clar de ce. Nu voi intra în detalii, deoarece practica arată că în procesul de acumulare a experienței, doar cele mai importante lucruri rămân în capul tău. După părerea mea, asta se întâmplă în orice domeniu de activitate. Voi încerca să subliniez ce îmi rămâne în cap cu privire la aceste probleme.

Clasificarea structurilor de date

Structură de date este o formă de stocare și prezentare a informațiilor. Definiția este foarte vagă, așa că experții folosesc diverse forme de clasificare și clarificare. Structurile de date pot fi simple sau complexe: reprezintă o unitate atomică de informație sau un set de date de același tip. Structurile simple de date sunt caracterizate, de exemplu, prin numere întregi, reale, logice, tip de text etc. Structurile complexe de date sunt împărțite în seturi dinamice și statice. Dinamic în proces ciclu de viață vă permit să le schimbați dimensiunea (adăugați și eliminați elemente), dar cele statice nu. Și, în sfârșit, conform organizării relațiilor dintre elementele structurilor complexe de date, există următoarea clasificare:

  • Liniar
    • Matrice
    • Listă
    • Lista conexe
    • Coadă
    • Tabel de hash
  • Ierarhic
    • Arbori binari
    • copaci N-ari
    • Lista ierarhică
  • Reţea
    • Grafic simplu
    • Graficul dirijat
  • Tabular
    • Tabel bazei de date relaționale
    • Matrice bidimensională
  • Alte

    • Clasificarea de mai sus este departe de a fi completă. Elementele structurilor de date complexe pot fi atât instanțe ale structurilor de date simple, cât și instanțe ale structurilor de date complexe, de exemplu o structură de date pădure este o listă de arbori disjunși. Acum voi încerca să dau scurta descriere clasele enumerate de structuri complexe de date. Primul nivel de clasificare se bazează pe diferențele în modul în care elementele individuale sunt abordate și căutate într-un set de structuri complexe de date.

    Structuri liniare de date

    Un element al unei structuri de date liniare este caracterizat printr-un număr de serie sau index într-o secvență liniară de elemente.

    Matrice– acesta este în static structura liniara de acelasi tip date, optimizate pentru operațiuni de căutare pentru un element după indexul său. Locația neechivocă a unui element în memorie este asigurată tocmai de același tip de elemente din matrice și este determinată de produsul indicelui său de dimensiunea memoriei ocupată de un element.

    Line array.
    Adresa(element(index)) = cell_size * index.

    Listă– este o structură de date liniară dinamică în care fiecare element se referă fie numai la cel precedent – listă liniară unidirecțională, sau la precedentul și următorul după - listă dublu liniară. Avantajul acestei structuri de date, pe lângă capacitatea de a schimba dimensiunea, este ușurința de implementare. De asemenea, datorită prezenței referințelor, fiecare element dintr-o listă, spre deosebire de o matrice, poate ocupa o cantitate diferită de memorie. Adresa primului element dintr-o listă liniară este determinată în mod unic de adresa listei în sine.

    Lista conexe este o variantă a unei liste liniare obișnuite, optimizată pentru operațiuni de adăugare și eliminare de elemente. Optimizarea este că elementele lista legată nu trebuie să fie localizate unul după altul în memorie. Ordinea elementelor este determinată de referința la primul element (care nu trebuie să fie chiar la începutul memoriei alocate listei) și de succesiunea referințelor la elementele rămase ale listei.


    Lista conexe.

    Grămadă este o structură de date liniară dinamică pentru care sunt definite doar două operații de schimbare a unui set de elemente: adăugarea unui element la sfârșit și eliminarea ultimului element. De asemenea, ei spun că stiva implementează principiul LIFO (Last in, First Out) - ultimul care vine și primul care pleacă. De exemplu, în timpul execuției codul programului, calculatorul, atunci când trebuie să apeleze o procedură sau o funcție, plasează mai întâi un pointer către locul în care a fost apelat pe stivă, astfel încât atunci când execuția codului său este finalizată, să revină corect la următoarea instrucțiune după punctul de apel. Această structură de date este numită stivă de apeluri de subrutine.

    Grămadă.

    Coadă- o structură de date dinamică, fără stivă, foarte asemănătoare, cu singura diferență că implementează principiul FIFO (First in, First out) - primul intrat și primul ieșit. După cum sugerează și numele, nu trebuie să cauți departe exemple în viața reală. În programare, cozile sunt folosite, de exemplu, pentru a procesa evenimente interfața cu utilizatorul, solicitările clienților și alte solicitări de informații.

    Coadă.

    Tabel de hash– cel mai complex tip de structuri de date dinamice liniare. Un tabel hash este optimizat pentru a găsi rapid elemente prin calcularea adresei elementului ca valoare hash. Argumentul funcției hash este o anumită cheie asociată cu elementul, de exemplu, numărul său de secvență. Pentru a garanta valori hash unice pentru valorile cheie unice (pentru a evita coliziunile), tabelul hash, pe lângă algoritmii inteligenți, folosește și RAM cu generozitate. Utilizarea tabelelor hash trebuie justificată și luată în considerare cu atenție.

    Structuri ierarhice de date

    Un element dintr-o structură de date ierarhică este caracterizat printr-o legătură către un element superior din ierarhie (sau legături către elemente subordonate) și (opțional) un număr de serie în succesiunea liniară a nivelului său (liste ierarhice).

    Copaci– o structură de date ierarhică dinamică reprezentată de un singur nod rădăcină și descendenții acestuia. Numărul maxim de copii ai fiecărui nod determină dimensiunea arborelui. Alocați separat binar sau arbori binari, deoarece sunt utilizați în algoritmii de sortare și căutare: fiecare nod al binarului arborele de căutare corespunde unui element dintr-o mulțime sortată, toți copiii săi „stânga” corespund elementelor mai mici, iar toți copiii săi „dreapta” corespund elemente mari. Fiecare nod din arbore este identificat în mod unic printr-o secvență de noduri care nu se repetă de la rădăcină la el - o cale. Lungimea căii este nivelul nodului din ierarhia arborescentă. Pentru arborii binari sau binari, se disting următoarele: tipuri de traversare recursivă toate elementele sale (ordinea în care sunt vizitate elementele fiecărui nod este indicată în acolade, începând de la rădăcină):

    • direct sau prefix
      (nodul, subarborele stânga, subarborele din dreapta);

    • revers sau postfix
      (subarborele stânga, subarborele din dreapta, nodul);

    • simetric sau infix
      (subarborele stânga, nodul, subarborele din dreapta);

    Pentru a afișa elementele în ordine crescătoare, arborele de căutare trebuie parcurs într-o ordine simetrică. Pentru ca elementele să fie înăuntru ordine inversă, în timpul procesului de traversare este necesar să se schimbe ordinea subarborilor vizitați.


    Arbore binar.

    Lista ierarhică– o simbioză între o listă liniară și un arbore. Fiecare element de listă poate fi, de asemenea, începutul unei liste la următorul nivel de ierarhie. Un exemplu de listă ierarhică este structura forumurilor de pe Internet: o secvență de mesaje formează o listă liniară, în timp ce mesajele care sunt răspunsuri la alte mesaje generează noi fire de discuție.


    Lista ierarhică.

    Structuri de date de rețea

    Un element dintr-o structură de date de rețea este caracterizat printr-un set de conexiuni cu alte elemente învecinate. În astfel de structuri de date, nici elementele inițiale, nici elementele rădăcină nu sunt alocate în mod explicit.

    Grafic– o structură dinamică de date de rețea, reprezentată printr-un set de vârfuri și muchii – conexiuni între vârfuri. Fiecare vârf poate fi conectat la orice număr de alte vârfuri sau la el însuși. Nu mai există o ierarhie clară aici. Dacă considerăm nodurile arborelui ca vârfurile unui grafic, iar conexiunile dintre nodurile arborelui de diferite niveluri ierarhice ca marginile graficului, atunci arborele însuși poate fi considerat un grafic care nu conține cicluri sau un grafic aciclic. Dacă fiecare margine a unui grafic are o direcție definită, atunci este un grafic direcționat. Pe lângă direcție, fiecare margine a graficului poate avea propria sa greutate. Folosind un grafic, de exemplu, ei modelează rețelele de transport iar problemele de optimizare a fluxurilor de trafic sunt rezolvate. Volumul de muncă sau, dimpotrivă, debitului traseele de transport sunt date de greutatea marginilor corespunzătoare.


    Grafic.
    Graficul dirijat.

    Un element dintr-o structură de date tabelară este caracterizat de un index bidimensional: indexul de rând și indexul de coloană la intersecția căreia se află. Exemple de structuri de date tabulare sunt tabelele.


    Evaluarea complexității algoritmului

    Prin evaluarea complexității algoritmilor, nu ne referim la efortul intelectual pe care autorii l-au depus în dezvoltarea lor, ci la dependența numărului de operații elementare efectuate de un computer de volumul de informații procesate. De exemplu, cum va depinde numărul de comparații a două numere de lungimea secvenței originale în timpul funcționării algoritmului de sortare? Am restrâns puțin definiția intenționat, deoarece în cele ce urmează vom vorbi doar despre numărul de operații elementare. De fapt, complexitatea algoritmului este determinată nu numai de numărul de operații, ci și de cantitatea de resurse de calcul implicate în rezolvarea problemei și, în primul rând, memorie cu acces aleator. Cu cât algoritmul este mai simplu, cu atât este probabil să funcționeze mai mult. Algoritmii complecși și rapidi folosesc adesea structuri de date auxiliare și, ca rezultat, consumă memorie suplimentară. Legea conservării energiei sau „trebuie să plătești pentru tot”. Un exemplu de „optimizare marginală” a fost discutat mai devreme - un tabel hash. Personal nu știu cum este structurat un tabel hash și cum arată funcțiile hash (presupun că nu este ușor), dar timpul necesar pentru a căuta elemente după cheie practic nu depinde de dimensiunea tabelului. În continuare, o mică teorie.

    Complexitatea algoritmilor este evaluată folosind instrumente matematice analiza asimptoticăși obținerea unei estimări de complexitate asimptotică.

    Estimarea complexității asimptotice notat cu litera greacă Θ (theta).

    f(n) = Θ(g(n)), dacă există c1, c2>0 și n0 astfel încât c1*g(n)n0.

    Funcția g(n) este o estimare precisă asimptotic a complexității algoritmului - funcția f(n), inegalitatea de mai sus se numește egalitate asimptotică, iar notația Θ în sine simbolizează setul de funcții care cresc „la fel de repede” ca funcția g(n) - adică e. până la înmulțirea cu o constantă. După cum rezultă din inegalitatea de mai sus, estimarea Θ este atât o estimare superioară, cât și una inferioară a complexității. Nu este întotdeauna posibil să se obțină o estimare în această formă, astfel încât estimările superioare și inferioare sunt uneori determinate separat.

    Scor de dificultate superior notat cu litera greacă Ο (omicron) și este un set de funcții care cresc nu mai repede decât g(n).

    f(n)= Ο(g(n)), dacă există c>0 și n0 astfel încât 0n0.

    Scor de dificultate mai mic notat cu litera greacă Ω (omega) și este mulțimea de funcții care cresc nu mai lent decât g(n).

    f(n)= Ω(g(n)), dacă există c>0 și n0 astfel încât 0n0.

    În consecință: o estimare asimptotică există numai dacă limitele inferioare și superioare ale complexității algoritmului coincid. În practica analizării algoritmilor, estimarea complexității este cel mai adesea înțeleasă ca estimarea superioară a complexității. Acest lucru este destul de logic, deoarece cel mai important lucru este să estimați timpul în care algoritmul este garantat să își finalizeze activitatea și nu timpul în care cu siguranță nu se va finaliza.

    Lucrul cu structuri liniare de date

    Ei bine, în concluzie, voi da estimări ale complexității operațiilor de bază cu structuri de date liniare, și anume adăugarea, ștergerea și căutarea unui element după index sau cheie. Operațiile elementare, în acest caz, sunt operațiuni de comparare, enumerare, calcul de adrese sau rearanjare a elementelor unui set de structuri de date. ÎN masă rotativă, pe lângă estimarea de complexitate superioară, sunt date și componentele bibliotecii corespunzătoare structurilor de date enumerate. Astfel, structurile de date liniare de bază sunt deja pregătite și disponibile pentru toți dezvoltatorii software pe platformă.

    O condiție necesară construcţia algoritmului este formalizarea datelor, adică reducerea informaţiei la unele model informativ (cm. " Modele de informare"), deja descris și studiat. Când se găsește un astfel de model, se spune că este definit structură abstractă a datelor.

    Structura abstractă a datelor descrie caracteristicile și proprietățile unui obiect, relaţieîntre elementele obiectului, cât mai bine posibil operațiuni asupra unui obiect sau a unei clase de obiecte date.

    Una dintre sarcinile informaticii este de a găsi forme de reprezentare a informației care sunt convenabile pentru prelucrare computerizată. Informatica ca știință exactă funcționează cu obiecte formale (descrise strict matematic). Astfel de obiecte - de bază structuri de date abstracte utilizate în informatică sunt:

    · numere întregi;

    · numere reale;

    · simboluri;

    · valori logice.

    Pentru prelucrarea computerizată a acestor obiecte în limbaje de programare, sunt adecvate tipuri de date(cm. " Tipuri de date"). Obiectele de bază pot fi combinate în structuri mai complexe prin adăugarea de operații asupra structurii ca întreg și reguli de acces la elementele individuale ale acestei structuri de date abstracte.

    Aceste structuri de date abstracte includ:

    · vectori (matrice finite);

    · tabele (matrice) și în caz general- tablouri multidimensionale;

    · structuri dinamice:

    Secvențe de simboluri, numere;

    Cozi;

    Copaci;

    O alegere cu succes a structurii de date este adesea cheia pentru crearea unui algoritm eficient și a unui program care îl implementează: folosind analogia structurilor de date și a obiectelor reale, puteți găsi solutii eficiente sarcini.

    Rețineți că structurile enumerate există indiferent de implementarea lor în timpul programării. Ei au lucrat cu aceste structuri de date atât în ​​secolele al XVIII-lea, cât și în secolele al XIX-lea. secolele al XIX-lea, când mașina de calcul nu fusese încă inventată. Putem dezvolta un algoritm în termenii unei structuri de date abstracte, dar pentru a implementa algoritmul într-un limbaj de programare specific, trebuie să găsim o modalitate de a-l reprezenta în termeni. tipuri de dateȘi operatori suportat de acest limbaj de programare (vezi „ Operatori de limbaj de programare"). Pentru reprezentare pe calculator se folosesc structuri abstracte structuri de date, care reprezintă un set de variabile, probabil tipuri variate date combinate într-un anumit fel. Pentru a construi structuri precum un vector, tabel, șir, secvență, majoritatea limbajelor de programare au standard tipuri de date: matrice unidimensională, matrice bidimensională, șir, fișier (mai rar o listă), respectiv. Organizarea altor structuri de date, în primul rând structuri dinamice, a cărui dimensiune se modifică în timpul execuției programului, programatorul trebuie să implementeze independent, folosind tipuri de date de bază. Să luăm în considerare astfel de structuri mai detaliat.

    Liste

    Lista liniară- o succesiune de elemente înrudite liniar pentru care sunt permise operațiunile de adăugare a elementelor la un loc arbitrar din listă și de ștergere a oricărui element. O listă liniară este identificată în mod unic printr-un indicator către începutul listei. Operațiile tipice pe liste sunt: ​​parcurgerea listei, căutarea unui element dat, inserarea unui element imediat după sau înainte anumit element, ștergerea unui element dat, îmbinarea a două liste într-una singură, împărțirea unei liste în două sau mai multe liste etc.

    Într-o listă liniară pentru fiecare element, cu excepția primul, Există anterior element; pentru fiecare element cu excepția ultimul, Există Următorul element. Astfel, toate elementele listei sunt ordonate. Cu toate acestea, procesarea unei liste liniare cu legături unice nu este întotdeauna convenabilă, deoarece nu există nicio posibilitate de deplasare în direcția opusă - de la sfârșitul listei până la început. Într-o listă liniară, puteți parcurge toate elementele doar deplasându-vă secvențial de la elementul curent la următorul, începând de la primul, acces direct la i al-lea element este imposibil.

    Exemplul 1. Ordinea înregistrărilor numelor cititorilor în computerul bibliotecarului determină relația „anterior-următorul”. De regulă, înregistrările în sine au proprietate suplimentară- sunt ordonate alfabetic. Operațiunile de adăugare a unui cititor nou și, dacă este necesar, de ștergere a unuia vechi sunt implementate pe această listă. Dacă, în plus, se țin evidențe ale cărților emise fiecărui cititor, atunci este convenabil să se reprezinte fiecare astfel de evidență, folosind din nou o listă de cărți emise.

    Liste de apeluri- aceeași structură ca o listă liniară, dar cu comunicare suplimentarăîntre ultimul și primul element, adică următorul element după ultimul element este primul element.

    Într-o listă circulară, spre deosebire de una liniară toate elementele sunt egale(deoarece pentru fiecare element atât cele precedente, cât și articolele următoare). Selectarea „primului” și „ultimul” elemente dintr-o listă de inel este foarte arbitrară, deoarece de fapt structura listei nu are elemente alocate explicit!

    Exemplul 2.În multe jocuri, copiii folosesc contoare pentru a-și alege un lider, pentru a se împărți în echipe etc. De regulă, contoarele sunt lungi, iar copiii (fără să știe ei înșiși) organizează o listă circulară. Relația „anterior-următorul” este determinată de direcția în care se numără liderul. O operațiune tipică într-o astfel de structură este eliminarea unui element din listă menținând în același timp structura circulară.

    Listele liniare, în care operațiunile de inserare, ștergere și acces la valorile elementelor sunt efectuate numai pe elementele cele mai exterioare (primul sau ultimul), au primit nume speciale.

    Grămadă - caz special o listă liniară unică legată pentru care sunt definite două operații: adăugarea unui element în partea de sus a stivei (înaintea primului element) și eliminarea unui element din partea de sus a stivei (eliminarea primului element).

    Exemplul 3. Luați în considerare problema determinării echilibrului parantezelor tipuri variateîn expresie aritmetică. De exemplu, doriți să analizați dacă parantezele dintr-o expresie care conține paranteze și paranteze drepte sunt echilibrate: ? Pentru a rezolva această problemă vom folosi o structură dinamică date grămadă. Să prezentăm un algoritm pentru rezolvarea acestei probleme pas cu pas. Vom folosi următoarea notație:

    i- numărul simbolului analizat;

    n- numărul de caractere din expresie.

    1. i = 0.

    2. i = i + 1.

    3. Dacă in, apoi treceți la pasul (4), altfel dacă stiva este goală, atunci afișăm mesajul „parantezele sunt echilibrate”, în caz contrar afișăm mesajul „ parantezele nu sunt echilibrate" Sfârșitul algoritmului.

    4. Dacă i Al-lea simbol este diferit de simbolurile parantezei, apoi treceți la pasul (2).

    5. Dacă i Simbolul este egal cu „(” sau „[”, apoi îl punem pe stivă, trecem la pasul (2).

    6. Dacă i Al-lea simbol este „)”, apoi verificăm partea de sus a stivei: dacă există „(” în partea de sus a stivei, atunci îl scoatem din stivă; trecem la pasul (2), în caz contrar afișăm mesajul „ parantezele nu sunt echilibrate" Sfârșitul algoritmului.

    7. Dacă i Al-lea caracter este „]”, apoi verificăm partea de sus a stivei: dacă există „[” în partea de sus a stivei, atunci îl scoatem din stivă; treceți la pasul (2), altfel afișam mesajul „ parantezele nu sunt echilibrate" Sfârșitul algoritmului.

    Coadă- un caz special al unei liste liniare unic legate pentru care sunt permise doar două operații: adăugarea unui element la sfârșitul (coada) cozii și eliminarea unui element de la începutul (capul) cozii.

    Conceptul de coadă este într-adevăr foarte aproape de termen de zi cu zi"coadă". O coadă de clienți într-un magazin este bine descrisă în ceea ce privește această structură de date.

    Copaci

    Copac este o colecție de elemente numite noduri, în care este selectat un element ( rădăcină), iar elementele rămase sunt împărțite în seturi disjunse (subarbori), fiecare dintre ele fiind un arbore, iar rădăcina fiecărui subarbore este descendent rădăcina copacului, adică toate elementele sunt interconectate printr-o relație (strămoș-descendent). Ca urmare, se formează o structură ierarhică a nodurilor. Sunt numite nodurile care nu au copii frunze. Deasupra copacului definit urmatoarele operatii: adăugarea unui element într-un arbore, eliminarea unui element dintr-un arbore, traversarea unui arbore, căutarea unui element într-un arbore.

    Exemplul 4. Un arbore este cea mai convenabilă structură de date pentru reprezentarea unui arbore genealogic, care poate fi folosită pentru a rezolva problemele de determinare a gradului de relație dintre două persoane.

    Copacii sunt folosiți și pentru a determina strategiile câștigătoare în jocuri (vezi articolul „ Jocuri. Strategii câștigătoare"), și pentru construirea diverselor modele de informații (vezi " Modele de informare”).

    Un rol deosebit de important în informatică îl joacă așa-numitul arbori binari.

    Arbore binar- un caz special al unui arbore în care fiecare nod poate avea nu mai mult de doi descendenți, care sunt rădăcinile subarborelui din stânga și din dreapta.

    Dacă, în plus, este îndeplinită condiția pentru nodurile arborelui ca toate valorile elementelor subarborelui din stânga să fie mai mici decât valoarea rădăcinii arborelui și toate valorile elementelor subarborelui din dreapta valoare mai mare rădăcină, atunci se numește un astfel de copac arbore binar de căutareși este conceput pentru a căuta rapid elemente. Algoritmul de căutare într-un astfel de arbore funcționează astfel: valoarea căutată este comparată cu valoarea rădăcinii arborelui și, în funcție de rezultatul comparației, căutarea fie se termină, fie continuă doar în stânga sau numai în dreapta. subarbore, respectiv. Numărul total de operațiuni de comparare nu va depăși așa-numitul înălțimea copacului- numărul maxim de elemente de pe traseul de la rădăcina copacului la una dintre frunze. Deci, înălțimea copacului prezentat în figură este 4.

    Grafice

    Grafic este un set de elemente numite culmi grafic împreună cu un set de relații între aceste vârfuri, numite coaste grafic. O interpretare grafică a acestei structuri de date este un set de puncte corespunzătoare vârfurilor, dintre care unele perechi sunt conectate prin linii sau săgeți care corespund muchiilor. În acest din urmă caz, graficul este numit orientat(vezi și articolele „ Modele grafice " Și " Modele tabulare ”).

    Datorită faptului că obiectele cu structură arbitrară pot fi descrise folosind grafice, graficele sunt principalele mijloace de descriere a structurilor. obiecte complexeși funcționarea sistemelor. De exemplu, pentru a descrie rețea de calculatoare, sistem de transport, structură ierarhică (un arbore este unul dintre tipurile de grafic). Diagramele algoritmului (vezi „ Modalități de a scrie algoritmi”) sunt, de asemenea, grafice.

    Dacă fiecărei muchii i se atribuie și un anumit număr ( greutate), atunci se numește un astfel de grafic ponderat. De exemplu, atunci când descrieți sistemul rutier rusesc folosind un grafic, ceea ce este important este lungimea drumului (greutatea marginii graficului) care leagă anumite aşezări(vârfurile graficului). Mai mult, în figură, lungimile marginilor corespunzătoare nu trebuie să corespundă greutăților care le sunt atribuite, spre deosebire de o foaie de drum.

    Exemplul 5. Este convenabil să rezolvi următoarea problemă în termenii unui grafic ponderat. Guvernul rus elaborează un plan pentru construirea de autostrăzi moderne care să facă legătura între orașe cu o populație de peste un milion de oameni. Ce fel de drumuri ar trebui construite astfel încât dintr-un astfel de oraș să se poată ajunge în oricare altul prin autostrăzi noi, iar lungimea totală a drumurilor să fie minimă?

    Această problemă din teoria grafurilor are o soluție simplă și exactă. Putem începe să planificăm o rețea de drumuri, începând din orice oraș, de exemplu, Sankt Petersburg. Să-l conectăm cu cel mai apropiat oraș de peste un milion. Apoi, la fiecare pas, rețelei existente se adaugă cel mai scurt drum, care poate conecta un oraș încă neconectat la rețea cu unul dintre orașele deja incluse în rețea. Numărul de drumuri va fi astfel mai mic decât numărul de orașe.

    O structură abstractă de date - un grafic - poate fi reprezentată într-un program în mai multe moduri, de ex. folosind diferite tipuri de date. De exemplu, un grafic poate fi descris folosind o listă de muchii, definind fiecare muchie cu o pereche de vârfuri și, opțional, o greutate. Stocarea graficelor tabelare a devenit cea mai răspândită (vezi „ Modele tabulare"), numit si matricea de adiacenta, adică o matrice bidimensională, să zicem A, unde pentru un grafic neponderat (sau 1), dacă muchia dintre vârfuri iȘi j există și (sau 0) în caz contrar. Pentru un grafic ponderat A[i][j] este egală cu greutatea muchiei corespunzătoare, iar absența unei muchii într-un număr de probleme este indicată convenabil cu infinit. Pentru graficele nedirecționate, matricea de adiacență este întotdeauna simetrică față de diagonala principală ( i = j). Folosind matricea de adiacență, este ușor să verificați dacă există o muchie în grafic care conectează un vârf i cu varf j. Principalul său dezavantaj este că matricea de adiacență necesită ca cantitatea de memorie să fie suficientă pentru a stoca N 2 valori pentru un grafic care contine N vârfuri, chiar dacă există mult mai puține muchii în grafic decât N 2 .

    La explicarea conceptului structuri de date Puteți folosi următoarea ilustrație.

    Când rezolvați orice problemă, este necesar să lucrați cu date si efectuarea de operatiuni asupra acestora. Setul acestor operații pentru fiecare sarcină, în general, este diferit. Cu toate acestea, dacă un anumit set de operații este adesea folosit în rezolvare diverse sarcini, atunci este util să veniți cu o modalitate de organizare a datelor care vă permite să efectuați exact aceste operațiuni cât mai eficient posibil. După ce se inventează o astfel de metodă, la rezolvare sarcina specifica putem presupune că avem o „cutie neagră” (o vom numi structură de date), despre care se știe că în ea sunt stocate date de un fel și care poate efectua anumite operațiuni asupra acestor date. Acest lucru vă permite să scăpați de detalii și să vă concentrați asupra trasaturi caracteristice sarcini. În interiorul (adică într-un computer) această „cutie neagră” poate fi implementată în diferite moduri, dar ar trebui să ne străduim să obținem cea mai eficientă implementare (rapidă și eficientă din punct de vedere al memoriei) posibil.

    Standardul educațional de stat prevede studierea diferitelor structuri de date atât în ​​cursul de bază al școlii primare, cât și în liceu. În cursul programării școlii de bază în Exemplu de program lanțuri de caractere (șiruri), numere, liste, arbori, grafice sunt menționate ca obiecte procesate. Cu toate acestea, în munca practica dintre datele unei structuri complexe, este menționată doar o matrice (vezi articolul „ Operații cu matrice"). În școala de bază, se pare că are sens să studiem structurile rămase în primul rând atunci când construiești modele grafice și alte modele (vezi secțiunea IV a enciclopediei).

    Un program aproximativ pentru o școală specializată implică lucrul cu numere, matrice, șiruri, liste și arbori. Ca o ilustrare simplă a lucrului cu liste, puteți alege să organizați stiva folosind o matrice unidimensională și o variabilă întreagă care indică partea de sus a stivei („partea de jos” a stivei este întotdeauna în primul element al matricei). ). Pe lângă problema verificării echilibrului parantezelor prezentată în articol, puteți studia funcționarea unui calculator stivă folosind exemplul unui algoritm pentru conversia unei expresii aritmetice în notație poloneză inversă ( postfixînregistrare) din cea cu care suntem obișnuiți infixînregistrarea și calcularea în continuare a valorii unei expresii aritmetice.

    Un arbore binar poate fi, de asemenea, reprezentat cu ușurință în memoria computerului folosind o matrice unidimensională, primul element al matricei stochând rădăcina arborelui și descendenții nodului arborelui stocați în i-al-lea element al matricei va fi localizat în 2 i-m și (2 i+ 1)-lea elemente, respectiv. Dacă un nod nu are descendent, atunci elementul corespunzător va fi egal cu, de exemplu, 0. Procedura recursiva traversarea copacilor tși imprimarea elementelor sale în acest caz va arăta astfel:

    ordinea procedurii(i:intger);

    dacă t[i]<> 0 apoi

    Puteți citi despre implementarea listelor și tablourilor folosind variabile dinamice, de exemplu, în cartea clasică a lui N. Wirth „Algoritmi și structuri de date”.

    Programul pentru școala de specialitate include și algoritmi grafici. În special, este menționată căutarea celei mai scurte căi dintr-un grafic. Pentru un graf neponderat, această problemă poate fi rezolvată, de exemplu, folosind algoritmul „căutare în lățimea întâi”, când mai întâi sunt marcate vârfurile graficului conectate printr-o muchie la vârful original, apoi toate vârfurile conectate la cele marcate etc. . Pentru un grafic ponderat, algoritmul lui Dijkstra este cel mai des folosit (a se vedea, de exemplu, articolul lui E.V. Andreeva „Olimpiade în informatică. Căi către vârf”, „Informatică” nr. 8/2002). Cunoașterea unor astfel de algoritmi este necesară pentru o soluție de succes probleme la olimpiadeîn informatică. Astfel, la etapa IV district federal Olimpiada integrală ruseascăîn informatică, în 2007, a fost propusă problema „Șanțuri și tranșee”, a cărei soluție s-a rezumat la găsirea celei mai scurte căi într-un grafic ponderat.

    Structura de date este o unitate de program care vă permite să salvați și să procesați o mulțime de același tip sau logic informatii aferente V dispozitive de calcul. Dacă doriți să adăugați, să găsiți, să modificați sau să ștergeți informații, cadrul oferă un pachet specific de opțiuni care formează interfața sa.

    Ce include conceptul de structură a datelor?

    Acest termen poate avea mai multe semnificații similare, dar totuși distincte. Acest:

    • tip abstract;
    • implementarea unui tip abstract de informații;
    • o instanță a unui tip de date, cum ar fi o anumită listă.

    Dacă vorbim despre structura datelor în contextul programării funcționale, atunci aceasta este o unitate specială care se păstrează în timpul modificărilor. Se poate vorbi informal despre ea ca o singură structură, în ciuda faptului că ar putea exista versiuni diferite.

    Ce formează structura?

    Se formează folosind referințe și operații asupra acestora într-un limbaj de programare specific. Merită să spui asta tipuri diferite structuri adecvate pentru implementare aplicatii diferite, unele, de exemplu, au o specializare complet îngustă și sunt potrivite doar pentru producerea sarcinilor stabilite.

    Dacă luăm arbori B, atunci aceștia sunt de obicei potriviti pentru formarea bazelor de date și numai pentru ei. În același timp, tabelele hash sunt încă folosite peste tot în practică pentru a crea diverse dicționare, de exemplu, pentru a demonstra numele de domenii în adresele de internet ale computerului, și nu doar pentru a forma baze de date.

    În timpul dezvoltării acestui sau aceluia software, complexitatea implementării și calitatea funcționalității programelor depind direct de aplicare corectă structuri de date. Această înțelegere a lucrurilor a dat impuls dezvoltării metodelor formale de dezvoltare și a limbajelor de programare, unde structurile, mai degrabă decât algoritmii, sunt plasate în poziții de conducere în arhitectura programului.

    Este de remarcat faptul că multe limbaje de programare au tip instalat modularitatea, care permite structurilor de date să fie utilizate în siguranță în diverse aplicații. Exemple notabile sunt Limbaje Java, C# și C++. Acum, structura clasică a datelor utilizate este prezentată în biblioteci standard de limbaje de programare sau este încorporată direct în limbajul în sine. De exemplu, tabelele hash sunt construite în Lua, Python, Perl, Ruby, Tcl și altele. Aplicat pe scară largă bibliotecă standardșabloane în C++.

    Compararea structurii în programarea funcțională și imperativă

    Merită menționat imediat că proiectarea structurilor pentru limbaje funcționale mai dificil decât pentru cele imperative, din cel puțin două motive:

    1. De fapt, toate structurile folosesc adesea atribuirea în practică, care nu este folosită într-un stil pur funcțional.
    2. Structuri funcționale- acestea sunt sisteme flexibile. În programarea imperativă, versiunile vechi sunt pur și simplu înlocuite cu altele noi, dar în programarea funcțională totul funcționează ca înainte. Cu alte cuvinte, în programarea imperativă structurile sunt efemere, dar în programarea funcțională sunt permanente.

    Ce include structura?

    Adesea, datele cu care lucrează programele sunt stocate în matrice, constante sau lungimi variabile încorporate în limbajul de programare utilizat. Matricea este cea mai simplă structură cu informaţie însă, pentru rezolvarea unor probleme, este necesară o eficienţă mai mare a unor operaţii, de aceea se folosesc alte structuri (mai complexe).

    Cea mai simplă matrice este potrivită pentru acces frecvent componentele instalate prin indici și modificările acestora, iar îndepărtarea elementelor din mijloc funcționează conform principiului O(N)O(N). Dacă trebuie să eliminați elemente pentru a rezolva anumite probleme, va trebui să utilizați o structură diferită. De exemplu, un arbore binar (std::set) vă permite să faceți acest lucru în O(logN)O(log⁡N), dar nu acceptă lucrul cu indici; efectuează doar parcurgerea elementelor unul câte unul și căutându-le după valoare. Astfel, putem spune că structura diferă în operațiunile pe care este capabilă să le efectueze, precum și în viteza cu care sunt efectuate. Ca exemplu, merită luate în considerare cele mai simple structuri care nu oferă beneficii de eficiență, dar cu siguranță au set set operațiuni susținute.

    Grămadă

    Acesta este unul dintre tipurile de structuri de date, prezentate sub forma unui tablou simplu limitat. Stiva clasică acceptă doar trei opțiuni:

    • Împingeți un element pe stivă (Dificultate: O(1)O(1)).
    • Scoaterea unui element din stivă (Complexitate: O(1)O(1)).
    • Verificarea dacă stiva este goală sau nu (Dificultate: O(1)O(1)).

    Pentru a explica cum funcționează o stivă, putem folosi analogia borcanului cu cookie-uri în practică. Imaginați-vă că există mai multe fursecuri în partea de jos a vasului. Mai poți pune câteva bucăți deasupra, sau poți, dimpotrivă, să iei o prăjitură deasupra. Fursecurile rămase vor fi acoperite de cele de sus și nu veți ști nimic despre ele. Așa funcționează lucrurile cu stiva. Pentru a descrie conceptul, se folosește abrevierea LIFO (Last In, First Out), care subliniază faptul că componenta care a intrat ultima în stivă va fi prima care va fi scoasă din acesta.

    Coadă

    Acesta este un alt tip de structură de date care acceptă același set de opțiuni ca o stivă, dar are o semantică opusă. Abrevierea FIFO (First In, First Out) este folosită pentru a descrie coada, deoarece elementul care a fost adăugat primul este eliminat primul. Numele structurii vorbește de la sine - principiul de funcționare este complet identic cu cozile care pot fi văzute într-un magazin sau supermarket.

    Dec

    Acesta este un alt tip de structură de date, care se mai numește și coadă dublă. Opțiunea acceptă următorul set de operații:

    • Introduceți elementul la început (Dificultate: O(1)O(1)).
    • Extrageți componenta de la început (Dificultate: O(1)O(1)).
    • Adăugarea unui element la final (Dificultate: O(1)O(1)).
    • Extragerea unui element de la capăt (Complexitate: O(1)O(1)).
    • Verificarea dacă puntea este goală (Dificultate: O(1)O(1)).

    Liste

    Această structură data definește o secvență de componente înrudite liniar pentru care sunt permise operațiuni de adăugare a componentelor în orice loc din listă și de ștergere. O listă liniară este specificată de un indicator către începutul listei. Operații tipice pe liste: parcurgerea, căutarea unei anumite componente, inserarea unui element, eliminarea unei componente, îmbinarea a două liste într-un singur întreg, împărțirea unei liste într-o pereche și așa mai departe. Este de remarcat faptul că într-o listă liniară, pe lângă prima, există o componentă anterioară pentru fiecare element, fără a include ultimul. Aceasta înseamnă că componentele listei sunt într-o stare ordonată. Da, procesarea unei astfel de liste nu este întotdeauna convenabilă, deoarece nu există posibilitatea de a vă deplasa în direcția opusă - de la sfârșitul listei până la început. Cu toate acestea, într-o listă liniară puteți parcurge toate componentele pas cu pas.

    Există și liste de apeluri. Aceasta este aceeași structură ca o listă liniară, dar are o legătură suplimentară între prima și ultima componentă. Cu alte cuvinte, următoarea componentă după ultimul element este prima componentă.

    Elementele din această listă sunt egale. Selectarea primului și ultimului este o convenție.

    Copaci

    Aceasta este o colecție de componente numite noduri, în care există o componentă principală (una) sub forma unei rădăcini, iar toate celelalte sunt împărțite în multe elemente disjunctive. Fiecare set este un copac, iar rădăcina fiecărui copac este un copil al rădăcinii copacului. Cu alte cuvinte, toate componentele sunt conectate între ele prin relații strămoș-copil. Ca rezultat, se poate observa o structură ierarhică a nodurilor. Dacă nodurile nu au copii, atunci se numesc frunze. În arbore sunt definite următoarele operații: adăugarea unei componente și ștergerea acesteia, parcurgerea, căutarea unei componente. Arborii binari joacă un rol special în informatică. Ce este? Acesta este un caz special al unui arbore, în care fiecare nod nu poate avea mai mult de o pereche de copii, care sunt rădăcinile subarborelui stâng și drept. Dacă, în plus față de nodurile arborelui, este îndeplinită condiția ca toate valorile componentelor subarborelui din stânga să fie mai mici decât valorile rădăcinii și valorile componentelor din dreapta subarborele sunt mai mari decât rădăcina, atunci un astfel de arbore se numește arbore binar de căutare și este destinat găsind rapid elemente. Cum funcționează algoritmul de căutare în acest caz? Valoarea de căutare este comparată cu valoarea rădăcină și, în funcție de rezultat, căutarea fie se termină, fie continuă, dar exclusiv în subarborele din stânga sau din dreapta. Numărul total de operațiuni de comparare nu va depăși înălțimea arborelui (acest cel mai mare număr componente pe drumul de la rădăcină la una dintre frunze).

    Grafice

    Graficele sunt o colecție de componente, numite vârfuri, împreună cu un set de relații între aceste vârfuri, numite muchii. Interpretare grafică Această structură este prezentată sub forma unui set de puncte care corespund vârfurilor, iar unele perechi sunt conectate prin linii sau săgeți, care corespund muchiilor. Ultimul caz sugerează că graficul ar trebui să fie numit direcționat.

    Graficele pot fi folosite pentru a descrie obiecte din orice structură; ele sunt principalele mijloace de descriere a structurilor complexe și a funcționării tuturor sistemelor.

    Mai multe detalii despre structura abstractă

    Pentru a construi un algoritm, este necesară formalizarea datelor sau, cu alte cuvinte, este necesară aducerea datelor la un anumit model de informații care a fost deja cercetat și scris. Odată găsit modelul, se poate spune că s-a stabilit structura abstractă.

    Aceasta este structura principală de date care demonstrează caracteristicile, calitățile unui obiect, relația dintre componentele obiectului și operațiunile care pot fi efectuate asupra acestuia. Sarcina principală este de a căuta și afișa forme de prezentare a informațiilor care sunt convenabile pentru corectarea computerului. Merită menționat imediat că informatica, ca știință exactă, operează cu obiecte formale.

    Structurile de date sunt analizate de următoarele obiecte:

    • Numere întregi și numere reale.
    • Valori booleene.
    • Simboluri.

    Pentru a procesa toate elementele de pe un computer, există algoritmi și structuri de date adecvate. Obiecte tipice pot fi combinate în structuri complexe. Puteți adăuga operații asupra lor, reguli la anumite componente ale acestei structuri.

    Structura de organizare a datelor include:

    Dacă toate elementele sunt alese cu succes, atunci aceasta va fi cheia formării algoritmi eficientiși structuri de date. Dacă aplicați analogia structurilor și obiectelor reale în practică, puteți rezolva eficient problemele existente.

    Este de remarcat faptul că toate structurile de organizare a datelor există separat în programare. Au lucrat mult la ele în secolele al XVIII-lea și al XIX-lea, când nu era nicio urmă de calculator.

    Este posibil să dezvoltați un algoritm în termeni de structură abstractă, dar pentru a implementa algoritmul într-un limbaj de programare specific, va trebui să găsiți o tehnică de reprezentare a acestuia în tipurile de date, operatori care sunt suportați limbaj specific programare. Pentru a crea structuri precum un vector, tabel, șir, secvență, multe limbaje de programare au tipuri clasice date: matrice unidimensională sau bidimensională, șir, fișier.

    Ne-am ocupat de caracteristicile structurilor de date, acum merită să acordăm mai multă atenție înțelegerii conceptului de structură. Când rezolvați absolut orice problemă, trebuie să lucrați cu unele date pentru a efectua operațiuni pe informații. Fiecare sarcină are propriul set de operații, dar un anumit set este folosit în practică mai des pentru a rezolva diverse sarcini. În acest caz, este util să veniți cu un anumit mod de organizare a informațiilor care să vă permită să efectuați aceste operațiuni cât mai eficient. De îndată ce a apărut această metodă, puteți considera că aveți o „cutie neagră” în care vor fi stocate date de un anumit fel și care va începe să efectueze anumite operațiuni cu datele. Acest lucru vă va permite să scăpați de detalii și să vă concentrați pe deplin asupra trăsăturilor caracteristice ale sarcinii. Această „cutie neagră” poate fi implementată în orice mod, dar este necesar să ne străduim pentru implementarea cât mai productivă posibilă.

    Cine trebuie să știe asta?

    Programatorii începători care doresc să-și găsească locul în acest domeniu, dar nu știu unde să meargă, ar trebui să se familiarizeze cu informațiile. Acestea sunt elementele de bază în fiecare limbaj de programare, așa că ar fi o idee bună să învățați imediat despre structurile de date și apoi să lucrați cu ele în exemple concreteși cu un anumit limbaj. Nu trebuie să uităm că fiecare structură poate fi caracterizată prin reprezentări logice și fizice, precum și un set de operații asupra acestor reprezentări.

    Nu uitați: dacă vorbiți despre cutare sau cutare structură, atunci țineți cont de reprezentarea ei logică, deoarece reprezentare fizică complet ascunsă de „observatorul extern”.

    În plus, rețineți că reprezentarea logică este complet independentă de limbajul de programare și computer, în timp ce reprezentarea fizică, dimpotrivă, depinde de traducători și de tehnologia informatică. De exemplu, o matrice bidimensională în Fortran și Pascal poate fi reprezentată într-un mod identic, iar reprezentarea fizică în același calculator va fi diferit în aceste limbi.

    Nu vă grăbiți să începeți să învățați structuri specifice; cel mai bine este să înțelegeți clasificarea lor, să vă familiarizați cu toate în teorie și, de preferință, în practică. Merită să ne amintim că variabilitatea este o caracteristică importantă a structurii și indică o poziție statică, dinamică sau semistatică. Aflați elementele de bază înainte de a trece la lucruri mai globale, acest lucru vă va ajuta să dezvoltați în continuare.

    • Traducere

    Ekaterina Malakhova, editor independent, a adaptat un articol de Beau Carnes despre principalele tipuri de structuri de date în special pentru blogul Netology.

    „Programatorii răi se gândesc la cod. Programatori buni Gândiți-vă la structurile de date și la relațiile lor.” Linus Torvalds, creatorul Linux.

    Structurile de date joacă un rol important în procesul de dezvoltare a software-ului și sunt, de asemenea, întrebări frecvente în interviurile dezvoltatorilor. Vestea bună este că sunt în esență drepte formate speciale pentru organizarea și stocarea datelor.

    În acest articol, vă voi arăta cele mai comune 10 structuri de date. Pentru fiecare dintre ele sunt furnizate videoclipuri și exemple ale implementării lor în JavaScript. Pentru a vă ajuta să exersați, am inclus și câteva exerciții din versiunea beta a noului curriculum freeCodeCamp.

    În articol, ofer exemple de implementare a acestor structuri de date în JavaScript; ele vor fi utile și dacă utilizați un limbaj de nivel scăzut precum C. Multe limbaje de nivel înalt, inclusiv JavaScript, au deja implementări încorporate ale majorității structurile de date pe care le vom discuta. Cu toate acestea, astfel de cunoștințe vor fi un avantaj serios în căutarea unui loc de muncă și vor fi utile atunci când scrieți coduri de înaltă performanță.

    Liste legate

    O listă legată este una dintre structurile de date de bază. Este adesea comparat cu o matrice, deoarece multe alte structuri pot fi implementate folosind fie o matrice, fie o listă legată. Aceste două tipuri au avantaje și dezavantaje.

    Așa funcționează o listă legată

    O listă legată constă dintr-un grup de noduri care formează împreună o secvență. Fiecare nod conține două lucruri: datele reale pe care le stochează (aceasta poate fi orice tip de date) și un pointer (sau link) către următorul nod din secvență. Există, de asemenea, liste dublu legate: în ele, fiecare nod are un pointer atât către elementul următor, cât și către cel anterior din listă.

    Operațiunile de bază dintr-o listă legată includ adăugarea, ștergerea și căutarea unui element din listă.

    Complexitatea temporală a unei liste legate ════════ ╗ ║ Algoritm ║Valoare medie ║ Cel mai rău caz ║ ╠════════════════════════ ═══════ ════ ╬═════════ ══════╣ ║ Spațiu ║ O(n) ║ O(n) ║ ║ ║ Căutare O(n) ║ Int(n) ║ Int(n) ║ ║ O (1) ║ O (1) ║ ║ Ștergeți ║ O (1) ║ O (1) ║ ╚═══════════╩══════════════ ═══╩═════ ═════ ═════╝

    Exerciții de la freeCodeCamp

    Stive

    Stiva este structură de bază date, care vă permite să adăugați sau să eliminați elemente doar la începutul acesteia. Este ca un teanc de cărți: dacă vrei să te uiți la cartea din mijlocul teancului, mai întâi trebuie să le scoți pe cele de deasupra.

    Stiva este organizată conform principiului LIFO (Last In First Out). Aceasta înseamnă că ultimul element pe care îl adăugați în stivă va fi primul care va ieși din el.


    Așa funcționează stiva

    Stivele pot efectua trei operațiuni: adăugarea unui element (push), eliminarea unui element (pop) și afișarea conținutului stivei (pip).

    Complexitatea timpului de stivă ═══════╗ ║ Algoritm ║Valoare medie ║ Cel mai rău caz ║ ╠═════════════════════════════ ═════════ ╬ ══════════ ═════╣ ║ Spațiu ║ O(n) ║ O(n) ║ ║ Căutare ║ O(n) ║ Int( ║) ║ O(n) ║ ║ O(1) ║ ║ Şterge ║ O( 1) ║ O(1) ║ ╚═══════════╩═══════════════════════ ══╩ ═════ ══════ ════╝

    Exerciții de la freeCodeCamp

    Cozile

    Această structură poate fi reprezentată ca o coadă în magazin alimentar. Cel care a venit chiar de la început este servit primul - la fel ca în viață.


    Așa funcționează coada

    Coada este aranjată conform principiului FIFO (First In First Out). Aceasta înseamnă că puteți șterge un element numai după ce toate elementele adăugate anterior au fost eliminate.

    O coadă vă permite să efectuați două operații de bază: adăugarea de elemente la sfârșitul cozii ( coadă) și scoateți primul element ( scoate la coadă).

    Complexitatea timpului de coadă ═══════╗ ║ Algoritm ║Valoare medie ║ Cel mai rău caz ║ ╠══════════════════════════════ ═════════ ╬ ══════════ ═════╣ ║ Spațiu ║ O(n) ║ O(n) ║ ║ Căutare ║ O(n) ║ Int( ║) ║ O(n) ║ ║ O(1) ║ ║ Şterge ║ O( 1) ║ O(1) ║ ╚═══════════╩═══════════════════════ ══╩ ═════ ══════ ════╝

    Exerciții de la freeCodeCamp

    Seturi



    Așa arată multe

    Un set stochează valorile datelor fără de o anumită ordine fără a le repeta. Vă permite nu numai să adăugați și să eliminați elemente: există mai multe funcții importante, care poate fi aplicat la două seturi simultan.

    • O uniune combină toate elementele din două seturi diferite într-unul singur (fără duplicate).
    • Intersecția analizează două mulțimi și creează una alta din acele elemente care sunt prezente în ambele mulțimi originale.
    • Diferența afișează o listă de elemente care se află într-un set, dar nu în altul.
    • Subset produce o valoare booleană care indică dacă un set include toate elementele altui set.
    Exemplu de implementare în JavaScript

    Exerciții de la freeCodeCamp

    Hartă

    O hartă este o structură care stochează date în perechi cheie/valoare, unde fiecare cheie este unică. Uneori se mai numește și matrice asociativă sau un dicționar. Harta este adesea folosită pentru a găsi rapid date. Vă permite să faceți următoarele lucruri:
    • adăugați perechi la colecție;
    • eliminați perechile din colecție;
    • schimba o pereche existentă;
    • căutați o valoare asociată cu o anumită cheie.

    Așa funcționează structura hărții

    Exerciții de la freeCodeCamp

    Tabele de hash

    Așa funcționează un tabel hash și o funcție hash

    Un tabel hash este o structură asemănătoare hărții care conține perechi cheie/valoare. Utilizează o funcție hash pentru a calcula un index într-o matrice de blocuri de date pentru a găsi valoarea dorită.

    De obicei, o funcție hash ia un șir de caractere ca intrare și emite o valoare numerică. Pentru aceeași intrare, funcția hash ar trebui să revină acelasi numar. Dacă două intrări diferite sunt trimise la același rezultat, are loc o coliziune. Scopul este să avem cât mai puține astfel de cazuri.

    Deci, atunci când introduceți o pereche cheie/valoare într-un tabel hash, cheia este trecută prin funcția hash și transformată într-un număr. Acest număr este utilizat ulterior ca cheie reală, care îi corespunde o anumită valoare. Când introduceți din nou aceeași cheie, funcția hash o va procesa și va returna același rezultat numeric. Acest rezultat va fi apoi folosit pentru a găsi valoarea asociată. Această abordare reduce semnificativ timpul mediu de căutare.

    Complexitatea temporală a unui tabel hash ════════ ═╗ ║ Algoritm ║Medie ║ Cel mai rău caz ║ ╠════════════════════════════ ════════ ═══ ═╬════════ ═══════╣ ║ Spațiu ║ O(n) ║ O(n) ║ ║ ║ ║ ║ ║ ║ ║ ║ ║ ║ O (1) ║ o (n) ║ ║ ștergeți ║ o (1) ║ o (n) ║ ╚═══════════╩══════════════ ═══╩════ ═════ ══════╝

    Exerciții de la freeCodeCamp

    Arborele de căutare binar


    Arborele de căutare binar

    Un arbore este o structură de date formată din noduri. Are următoarele proprietăți:

    • Fiecare copac are un nod rădăcină (sus).
    • Un nod rădăcină are zero sau mai multe noduri copil.
    • Fiecare nod copil are zero sau mai multe noduri copil și așa mai departe.
    Un arbore de căutare binar are două proprietăți suplimentare:
    • Fiecare nod are până la două noduri copil (descendenți).
    • Fiecare nod este mai mic decât copiii săi din dreapta, iar copiii săi din stânga sunt mai mici decât el însuși.
    Arborele de căutare binar vă permit să găsiți, adăugați și eliminați rapid elemente. Sunt proiectate astfel încât timpul fiecărei operații să fie proporțional cu logaritmul numărul total elemente din arbore.

    Complexitatea temporală a unui arbore de căutare binar ═══════ ╗ ║ Algoritm ║Valoare medie ║Cel mai rău caz ║ ╠════════════════════════════ ═══════ ════ ╬═════════ ═════╣ ║ Spațiu ║ O(n) ║ O(n) ║ ║ ║ Căutare ║ ║ Înregistrare ║ ║ Înregistrare ║ ║ ║ O(log n) ║ O(n) ║ ║ Şterge ║ O (log n) ║ O(n) ║ ╚═══════════╩═══╩════════════════ ═════╩════ ════ ══════╝


    Exerciții de la freeCodeCamp

    Arborele de prefix

    Un arbore de prefix (încărcat) este un tip de arbore de căutare. Stochează datele în etichete, fiecare dintre acestea reprezentând un nod în arbore. Astfel de structuri sunt adesea folosite pentru a stoca cuvinte și a performa cautare rapida pe ele - de exemplu, pentru funcția de completare automată.

    Acesta este modul în care funcționează arborele de prefix

    Fiecare nod din arborele de prefix de limbă conține o literă a cuvântului. Pentru a forma un cuvânt, trebuie să urmați ramurile copacului, trecând câte o literă. Arborele începe să se ramifică atunci când ordinea literelor diferă de alte cuvinte din el sau când cuvântul se termină. Fiecare nod conține o literă (date) și o valoare booleană care indică dacă este ultima din cuvânt.

    Privește ilustrația și încearcă să formezi cuvintele. Începeți întotdeauna cu nodul rădăcină în partea de sus și mergeți în jos. Acest arbore conține următoarele cuvinte: minge, liliac, păpușă, face, prost, cămin, trimite, simț.

    Exerciții de la freeCodeCamp

    Morman binar

    Heap-ul binar este o altă structură de date bazată pe arbore. Fiecare nod din el nu are mai mult de doi copii. Este, de asemenea, un arbore perfect: asta înseamnă că toate nivelurile din el sunt complet umplute cu date, iar ultimul este umplut de la stânga la dreapta.


    Așa funcționează grămada minimă și maximă

    Un heap binar poate fi minim sau maxim. În heap-ul maxim, cheia oricărui nod este întotdeauna mai multe chei descendenții săi sau egali cu ei. Într-un heap minim, totul funcționează invers: cheia oricărui nod este mai mică sau egală cu cheile descendenților săi.

    Ordinea nivelurilor într-un heap binar este importantă, spre deosebire de ordinea nodurilor din același nivel. Ilustrația arată că în heap-ul minim de la al treilea nivel, valorile nu sunt în ordine: 10, 6 și 12.


    Complexitatea temporală a heap-ului binar ════════ ═╗ ║ Algoritm ║ Medie ║ Cel mai rău caz ║ ╠═════════════════════════ ═════════ ══ ══╬═══════ ════════╣ ║ Spațiu ║ O(n) ║ O(n) ║═══════╣ ║ Spațiu ║ O(n) ║ O(n) ║ ║ ║ Căutare O(n) ║ Înt(n) ║ ║ O(1) ║ O(log n) ║ ║ Şterge ║ O (log n) ║ O (log n) ║ ║ Peek ║ O(1) ║ O(1) ║ ╚══════════ ═╩══════════ ════════╩══════════════════

    Exerciții de la freeCodeCamp

    Grafic

    Graficele sunt colecții de noduri (vertice) și conexiuni între ele (margini). Se mai numesc și rețele.

    Graficele sunt împărțite în două tipuri principale: direcționate și nedirecționate. În graficele nedirecționate, muchiile dintre noduri nu au nicio direcție, în timp ce muchiile din graficele direcționate au.

    Cel mai adesea, un grafic este reprezentat în una din două forme: poate fi o listă de adiacență sau o matrice de adiacență.


    Graficul ca matrice de adiacență

    O listă de adiacență poate fi gândită ca o listă de elemente, cu un nod în stânga și toate celelalte noduri la care se conectează în dreapta.

    O matrice de adiacență este o grilă de numere în care fiecare rând sau coloană corespunde unui nod diferit din grafic. La intersecția rândului și coloanei există un număr care indică prezența unei conexiuni. Zerourile înseamnă că lipsește; unități - că există o conexiune. Pentru a indica greutatea fiecărei conexiuni, sunt folosite numere mai mari decât unu.

    Există algoritmi speciali pentru vizualizarea muchiilor și vârfurilor în grafice - așa-numiții algoritmi de traversare. Principalele lor tipuri includ căutarea pe lățimea întâi ( căutarea pe lățimea întâi) și în profunzime ( căutarea în profunzime). Alternativ, ele pot fi folosite pentru a determina cât de aproape sunt anumite vârfuri ale graficului de nodul rădăcină. Videoclipul de mai jos arată cum să efectuați o căutare pe lățime în JavaScript.