Clasificări ale structurilor de date

Datele din memoria computerului sunt reprezentate ca o secvență de biți. Secvențele de biți nu sunt bine structurate, ceea ce le face dificil de realizat uz practic. Prin urmare, structurile de date sunt utilizate în practică.

Definiția 1

structura datele sunt un set de elemente de date și relații interne dintre ele.

Exista simpluși integrat structuri de date. Structurile simple de date sunt reduse la biți și organizate direct din biți. Structurile simple includ:

• numeric;
• pic;
• simbolic;
• joc de inteligență;
• indicatoare.

Structurile de date integrate sunt organizate din structuri simple și alte structuri integrate.

ar trebui să se distingă fizicși logic structură de date. Când vorbim despre structura fizică a tipurilor simple, atunci aceasta este înțeleasă ca dimensiunea lor și modul în care biții sunt aranjați în memorie. Din punct de vedere structura logica un tip simplu este o unitate elementară indivizibilă.

Definiția 2

variabilitate structura se numește schimbarea numărului de elemente și a relațiilor dintre ele.

În conformitate cu semnul variabilității, structurile sunt împărțite în

• Static (vecotr, array, set, record, table);
• Dinamic (stivă, coadă, șir, liste liniare legate, liste ramificate, grafice, arbori.).

Elementele dintr-o structură pot fi ordonate sau neordonate. În conformitate cu această caracteristică, structurile sunt împărțite în

• Neliniar (listă legată, grafic, arbore);
• Linear cu distribuție secvențială (vector, șir, matrice, stivă, coadă);
• Linear cu distribuție conexă arbitrară (listă legată individual și dublu).

Structuri simple și tipuri de date

Structurile simple de date sunt numite și structuri primitive sau structuri de bază. În limbajele de programare sunt reprezentate structuri simple de date tipuri simple date. Diferite limbaje de programare au un set ușor diferit de tipuri de date, dar există câteva principii generale.

tipul întreg folosit pentru a reprezenta numărul de obiecte discrete. Numerele întregi pot fi fără semn sau negative. Reprezentarea internăîntregul poate dura 1, 2 sau 4 octeți.

Numerele reale sunt reprezentate ca format virgulă mobilă. Un număr în virgulă mobilă este reprezentat de doi numere întregi- ordine și matisse, precum și semnul.

Când sistem binar calculul B=2.

Tip zecimal Nu toate limbajele de programare sunt acceptate. Un număr de acest tip este reprezentat ca m cifre zecimale din care d cifre sunt la dreapta punctului zecimal.

Pentru cazurile în care trebuie să lucrați cu cifre binare individuale ale unui număr, există tip de date pe biți. Datele din ele sunt reprezentate de un set de biți combinați în octeți sau cuvinte. Toate operațiunile pe tipul de bit implică accesarea fiecărui bit în mod individual.

Variabil tip boolean poate lua una din două valori: adevărat sau fals. O variabilă booleană necesită un octet de memorie. În acest caz, valoarea „fals” este codificată valoare zero octeți și valoarea „adevărată” cu orice valoare diferită de zero.

Tip de caracter vă permite să reprezentați datele ca o secvență de caractere dintr-un set predeterminat. Fiecare caracter al setului este stocat în memorie ca o secvență de biți. Corespondența dintre caractere și astfel de secvențe se numește codificare. Diferite codificări reprezintă caractere ca secvențe de biți de diferite lungimi.

Indicator este o variabilă a cărei valoare este adresa unei locații de memorie. Astfel, indicatorul se referă la un bloc de date, arătând spre prima lui celulă.

Exemple de structuri statice

Pentru a face referire la un element, trebuie să utilizați numele matricei și indexul elementului. Matricele sunt stocate în memorie în celule aranjate una după alta.

Exemplul 1

Fie dat un tablou numit A.

Atunci elementul A este 30.

Exemplul 2

Matrice bidimensională este o matrice, fiecare element fiind el însuși o matrice unidimensională.

Într-o matrice bidimensională, fiecare element are doi indici.

Definiția 4

Înregistrările (matrice hash, matrice asociative) sunt matrice care sunt indexate nu după numere naturale, ci prin șiruri.

Indicele unui element dintr-o astfel de matrice se numește cheie. Elementul este accesat folosind numele și indexul matricei.

Exemplul 3

Să fie dat o matrice hash numită B.

Apoi elementul de matrice B['legumă'] este egal cu 'castravete'.

Exemple de structuri dinamice

Pentru structurile dinamice, memoria este alocată „din mers” în timpul execuției programului. Pentru a lucra cu tipuri de date dinamice în diferite limbaje de programare, pointerii sunt folosiți pe scară largă. Pointerii în sine sunt de tip static.

Grămadă este un vector în care fiecare elementul următor este adresată de un pointer către elementul curent. Figurile arată adăugarea secvențială a elementelor la stivă și extracția secvențială.

Pentru a extrage un element, trebuie mai întâi să extragi toate elementele adăugate după el secvenţial. Elementul adăugat primul poate fi preluat doar ultimul.

Întoarce-te de asemenea, o structură dinamică, care diferă de stivă prin prezența a doi pointeri: la primul și ultimul element al cozii. Elementele noi sunt scrise după ultimul element scris. Și selecția elementelor începe de la prima. Cu acest algoritm, elementul care a fost adăugat primul poate fi obținut primul.

• Traducere

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

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

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

În acest articol, dau exemple de implementări JavaScript ale acestor structuri de date: acestea vor fi, de asemenea, utile dacă utilizați un limbaj de nivel scăzut precum C. Multe limbaje de nivel înalt, inclusiv JavaScript, au deja implementări pentru majoritatea datelor. structuri despre care voi vorbi. Cu toate acestea, astfel de cunoștințe vor fi un avantaj serios atunci când căutați un loc de muncă și vă vor fi utile atunci când scrieți cod de înaltă performanță.

Liste legate

Acesta este modul în care funcționează lista 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 deține (pot 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ă.

Time complexity of a linked list ╗ ║ ║ Algorithm ║ medium meaning ║ worst case ║ ╠ ╠ ╠ ╠ ╠ ╠ ╠ ╠ ╠ ╠ ╠ ╠ ╠ ╠ ╠ ╠ ╠ ╠ ╠ ╠ ╠ ╠ ╠ ╠ ╠ ╠ ╠ ╠ ╠ ╠ ╠ ╠ ╠ ╠ ╠ ╠ ╠ ══════╣ ║ Spațiu ║ O(n) ║ O(n) ║ ║ Căutare ║ O(n) ║ O(n) ║ ║ ║ O(n) ║ ║ Insert O(1) ║ ║ Şterge ║ O (1) O(1) ═════╝

Exerciții de la freeCodeCamp

Stive

Stiva este organizată conform principiului LIFO (Last In First Out) . Aceasta înseamnă că ultimul element pe care l-ați adăugat în stivă va fi primul care îl va părăsi.

Cum funcționează stiva

Pe stive pot fi efectuate trei operații: adăugarea unui element (push), eliminarea unui element (pop) și afișarea conținutului stivei (pip).

Stack Time Complexity ║ Algorithm ║ Media value ║ worst case ║ ╠ ╠ ╠ ╠ ╠ ╠ ╠ ╠ ╠ ╠ ╠ ╠ ╠ ╠ ╠ ╠ ╠ ╠ ╠ ═════╣ ║ Space ║ O(n) ║ O(n) ║ ║ Căutare ║ O(n) ║ O(n) ║ ║ Inserați ║ O(1) ║ O(1) ║ ║ Şterge ║ O(1) O(1) ════╝

Exerciții de la freeCodeCamp

Cozile

Așa se face coada

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

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

Queue time complexity ║ Algorithm ║ Media value ║ worst case ║ ╠ ╠ ╠ ╠ ╠ ╠ ╠ ╠ ╠ ╠ ╠ ╠ ╠ ╠ ╠ ╠ ╠ ╠ ╠ ═════╣ ║ Space ║ O(n) ║ O(n) ║ ║ Căutare ║ O(n) ║ O(n) ║ ║ Inserați ║ O(1) ║ O(1) ║ ║ Şterge ║ O(1) O(1) ════╝

Exerciții de la freeCodeCamp

Seturi

Setul stochează valorile datelor fără ordine anume fără a le repeta. Permite nu numai adăugarea și eliminarea elementelor: există mai multe funcții importante, care poate fi aplicat la două seturi simultan.

• Union combină toate elementele din două seturi diferite, transformându-le într-unul singur (fără duplicate).
• Intersecția analizează cele două mulțimi și  creează încă unul dintre acele elemente care sunt prezente în ambele mulțimi originale.
• Diferența generează o listă de elemente care se află într-un set, dar nu în celălalt.
• Un subset returnează o valoare booleană care indică dacă un set include toate elementele altui set.

Exerciții de la freeCodeCamp

Hartă

• adăugați perechi la colecție;
• eliminați perechile din colecție;
• schimba o pereche existentă;
• căutați valoarea asociată cu o anumită cheie.

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

Exerciții de la freeCodeCamp

Tabele de hash

Cum funcționează tabelul hash și funcția hash

Un tabel hash este o structură asemănătoare hărții care conține perechi cheie/valoare. Folosește 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 ieșire valoare numerică. Pentru aceeași intrare, funcția hash trebuie să returneze același număr. Dacă două intrări diferite sunt hashing cu același rezultat, are loc o coliziune. Scopul este să avem cât mai puține dintre aceste cazuri.

Deci, atunci când introduceți o pereche cheie/valoare într-un tabel hash, cheia trece prin funcția hash și se transformă într-un număr. În cele ce urmează, acest număr este folosit ca cheie reală, care corespunde unei anumite valori. 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 timpului a unui tabel hash ═╗ ║ алchimорит Comp ║среднее значение ║ худший с с сай ║ ║ ╠═══════════╬═════════════════╬══ ╠═══════════╬═════════════════╬══ ╠═══════════╬═════════════════╬══ ╠═══════════╬═════════════════╬══ ╠═══════════╬═════════════════╬══ ╠═══════════╬═════════════════╬══ ╠═══════════╬═════════════════╬══ ══════ ═══════╣ ║ Spațiu ║ O(n) ║ O(n) ║ ║ Căutare ║ O(1) ║ O(n) ║ O(n) ║ O(n) ║ Inert( ║) ║ n) ║ ║ Şterge ║ 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 alcătuită din noduri. Are următoarele proprietăți:

• Fiecare arbore are un nod rădăcină (sus).
• Nodul rădăcină are zero sau mai multe nodurile copil.
• Fiecare nod copil are zero sau mai multe noduri copil și așa mai departe.

• Fiecare nod are până la două noduri copil (copii).
• 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.

Time complexity of a binary search tree ╗ ║ ║ algorithm ║ medium -sized case ║ ╠ ╠ ╠ ╠ ╠ ╠ ╠ ╠ ╠ ╠ ╠ ╠ ╠ ╠ ╠ ╠ ╠ ╠ ╠ ╠ ╠ ╠ ╠ ╠ ╠ ╠ ╠ ╠ ╠ ╠ ╠ ╠ ╠ ╠ ╠ ╠ ╠ ╠ ╠ ═════╣ ║ Spațiu ║ O(n) ║ O(n) ║ ║ Căutare ║ O(log n) ║ O(n) ║ O(n) ║ O(n) ║ Inert ║ ║ ║ n) ║ ║ Şterge ║ O(log n)║ O(n) ══════╝

Exerciții de la freeCodeCamp

arbore de prefix

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, parcurgând câte o literă. Arborele începe să se ramifică atunci când ordinea literelor diferă de alte cuvinte din el sau când un cuvânt se termină. Fiecare nod conține o literă (date) și o valoare booleană care indică dacă este ultimul nod din cuvânt.

Privește imaginea și încearcă să faci cuvinte. Începeți întotdeauna de la nodul rădăcină din 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

Așa sunt aranjate grămezile minime și maxime

Heap-ul binar poate fi minim sau maxim. În heap-ul maxim, cheia oricărui nod este întotdeauna mai mare sau egală cu cheile descendenților săi. În heap-ul minim, totul este aranjat 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.

Exerciții de la freeCodeCamp

Grafic

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 unul din două moduri: poate fi o listă de adiacență sau o matrice de adiacență.

Graficul sub forma unei 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 unui rând și a unei coloane, există un număr care indică prezența unei conexiuni. Zerourile înseamnă că lipsește; unități - că există o conexiune. Numerele mai mari decât unu sunt folosite pentru a indica greutatea fiecărei legături.

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 ( profunzime prima căutare). 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.

O condiție necesară pentru stocarea informațiilor în memoria computerului este capacitatea de a converti tocmai aceste informații într-o formă potrivită pentru computer. În cazul în care această condiție este îndeplinită, este necesar să se determine o structură adecvată în mod specific informațiilor existente, una care să ofere setul necesar de posibilități de lucru cu aceasta.

lista de apeluri

Aici, structura este înțeleasă ca o modalitate de prezentare a informațiilor, prin care totalitatea elementelor individuale formează ceva unificat, datorită relației lor între ele. Aranjate după niște reguli și interconectate logic, datele pot fi procesate foarte eficient, deoarece structura comună pentru acestea oferă un set de opțiuni pentru gestionarea lor - unul dintre lucrurile datorită cărora se obțin rezultate înalte în rezolvarea anumitor probleme.

Dar nu fiecare obiect este reprezentat în liber de la, și poate chiar și pentru el există doar unul singura metoda interpretare, deci un plus cert pentru programator se vor cunoaște toate structurile de date existente. Astfel, de multe ori trebuie să alegeți între diverse metode stocarea informațiilor, iar performanța produsului depinde de această alegere.

Vorbind de tehnologia non-computerică, este posibil să nu arătăm niciun caz în care informația are o structură explicită. bun exemplu sunt cărți de diferite feluri. Ele sunt împărțite în pagini, paragrafe și capitole, au de obicei un cuprins, adică o interfață pentru utilizarea lor. LA în sens larg, fiecare ființă vie are o structură; fără ea, organicele cu greu ar putea exista.

Este probabil ca cititorul să fi avut de-a face cu structurile de date direct în informatică, de exemplu, cele care sunt construite într-un limbaj de programare. Ele sunt adesea denumite tipuri de date. Acestea includ: matrice, numere, șiruri de caractere, fișiere etc.

Metode de stocare a informațiilor, numite „simple”, adică indivizibile în părțile sale constitutive, este de preferat să se studieze împreună cu un limbaj de programare specific sau să se aprofundeze în esența muncii lor. Prin urmare, aici vor fi luate în considerare doar structurile „integrate”, cele care constau din cele simple și anume: tablouri, liste, arbori și grafice.

Matrice.

Un tablou este o structură de date cu un set fix și ordonat de elemente (componente) similare. Accesul la oricare dintre elementele matricei se realizează prin numele și numărul (indexul) acestui element. Numărul de indici determină dimensiunea tabloului. Deci, de exemplu, matricele unidimensionale (vectori) și bidimensionale (matrici) sunt cele mai comune.

Primii au un singur indice, ultimii doi. Fie ca o matrice unidimensională să fie numită A, apoi pentru a avea acces la al-lea element al său, va trebui să specificați numele matricei și numărul elementului necesar: A[i]. Când A este o matrice, aceasta este reprezentată ca un tabel, ale cărui elemente sunt accesate prin numele matricei, precum și numerele rândului și coloanei la intersecția cărora se află elementul: A, unde i este numărul rândului, j este numărul coloanei.

În diferite limbaje de programare, lucrul cu matrice poate diferi oarecum, dar principiile de bază, de regulă, sunt aceleași peste tot. LA limbajul Pascal, matricele unidimensionale și bidimensionale sunt accesate exact așa cum se arată mai sus, dar, de exemplu, în C++ matrice bidimensională ar trebui specificat astfel: A[i][j]. Elementele unui tablou sunt numerotate secvenţial. Limbajul de programare afectează modul în care începe numerotarea. Cel mai adesea, această valoare este 0 sau 1.

Matricele de tipul descris sunt numite statice, dar există și matrice care diferă de ele în anumite moduri: dinamice și eterogene. Dinamismul celui dintâi este caracterizat de volatilitatea dimensiunii, adică, pe măsură ce programul rulează, dimensiunea matricei dinamice se poate modifica. O astfel de funcție face lucrul cu date mai flexibil, dar în același timp trebuie să sacrifici viteza, iar procesul în sine devine mai complicat.

Un criteriu obligatoriu pentru o matrice statică, după cum sa spus, este omogenitatea datelor stocate în ea la un moment dat. Când această condiție nu este satisfăcută, atunci matricea este eterogenă. Utilizarea sa se datorează deficiențelor care există în forma anterioară, dar este justificată în multe cazuri.

Astfel, chiar dacă v-ați hotărât asupra structurii și ați ales o matrice ca aceasta, acest lucru încă nu este suficient. La urma urmei, o matrice este doar desemnare generala, gen pentru un număr de implementări posibile. Prin urmare, este necesar să se determine mod specific vizualizări, cu cea mai potrivită matrice.

Liste.

List este un tip de date abstracte care implementează un set ordonat de valori. Listele diferă de matrice prin faptul că elementele lor sunt accesate secvenţial, în timp ce matricele sunt o structură de date cu acces aleatoriu. Acest tip abstract are mai multe implementări sub formă de structuri de date. Unele dintre ele vor fi analizate aici.

O listă (listă legată) este o structură de date care este un set finit de elemente ordonate legate între ele prin intermediul unor pointeri. Fiecare element al structurii conține un câmp cu anumite informații, precum și un indicator către următorul element. Spre deosebire de o matrice, nu există acces aleatoriu la elementele unei liste.

În lista de mai sus conectată individual, elementul inițial este lista Head (capul listei [nume arbitrar]), iar orice altceva se numește coada. Coada listei este formată din elemente împărțite în două părți: informații (câmpul de informații) și index (câmpul următor). Ultimul element conține un semn al sfârșitului listei, nil, în loc de un pointer.

O listă unică legată nu este foarte convenabilă, deoarece dintr-un punct este posibil să ajungeți doar la următorul punct, trecând astfel la sfârșit. Când, pe lângă un pointer către următorul element, există un pointer către cel precedent, atunci o astfel de listă se numește dublu legată.

listă dublu legată

A fi capabil să vă deplasați atât înainte, cât și înapoi este util pentru unele operații, dar indicatorii suplimentari necesită să le utilizați. Mai mult memorie decât este necesar în lista echivalentă cu legături unice.

Pentru cele două tipuri de liste descrise mai sus, există un subtip numit listă circulară. Puteți transforma o listă legată individual într-o listă circulară adăugând doar un indicator la ultimul element, astfel încât acesta să indice primul. Și pentru unul dublu conectat, sunt necesare două indicatoare: la primul și ultimul element.

lista de apeluri

Pe lângă tipurile de structuri de listă luate în considerare, există și alte modalități de organizare a datelor în funcție de tipul „listă”, dar acestea, de regulă, sunt în multe privințe similare cu cele analizate, așa că vor fi omise aici.

Pe lângă diferențele de relații, listele sunt împărțite pe metode de lucru cu date. Unele dintre aceste metode sunt discutate mai jos.

Grămadă.

Grămadă

Stiva se caracterizează prin faptul că elementul său poate fi accesat doar de la un capăt, numit vârful stivei, cu alte cuvinte: stiva este o structură de date care funcționează conform principiului LIFO (last in - first out, " ultimul intrat - primul ieşit"). Este mai bine să descrieți această structură de date ca o listă verticală, de exemplu, un teanc de unele lucruri, unde pentru a utiliza unul dintre ele trebuie să ridicați toate acele lucruri care se află deasupra ei și puteți pune doar un obiect deasupra stivei.

În lista cu legături singulare afișată, operațiunile asupra elementelor au loc strict de la un capăt: a include elementul doritîn a cincea celulă, este necesar să se excludă elementul care ocupă această poziție. Dacă ar exista, de exemplu, 6 elemente și ar fi necesar să fie introdus și un anumit element în a cincea celulă, atunci două elemente ar trebui să fie deja excluse.

Întoarce-te.

Structura de date Queue folosește principiul de organizare FIFO (First In, First Out). Într-un fel, această metodă este mai justă decât cea pe care funcționează stiva, deoarece regula simplă care stă la baza cozilor obișnuite din diverse magazine, spitalul este considerat destul de corect, și anume el stă la baza acestei structuri. Fie ca această observație să fie un exemplu. Strict vorbind, o coadă este o listă, adăugarea de elemente la care este permisă numai la sfârșitul acesteia, iar extragerea lor se efectuează pe cealaltă parte, numită începutul listei.

Dec

Dec (deque - coadă cu două capete, "coadă în două direcții") - o stivă cu două capete. Într-adevăr, în ciuda traducerii specifice, un deque poate fi definit nu numai ca o coadă bidirecțională, ci și ca o stivă care are două capete. Înseamnă că această specie list vă permite să adăugați elemente la început și la sfârșit și același lucru este valabil și pentru operația de extracție.

Această structură funcționează simultan în două moduri de organizare a datelor: FIFO și LIFO. Prin urmare, poate fi atribuită unei unități de program separată, obținută ca urmare a însumării celor două tipuri anterioare de listă.

Contează.

Ramura matematicii discrete care se ocupă cu studiul grafurilor se numește teoria grafurilor. În teoria grafurilor sunt considerate în detaliu concepte, proprietăți, moduri de reprezentare și aplicații cunoscute ale acestor obiecte matematice. Ne interesează doar acele aspecte ale acestuia care sunt importante în programare.

Un grafic este o colecție de puncte conectate prin linii. Punctele sunt numite vârfuri (noduri), iar liniile sunt numite muchii (arce).

După cum se arată în figură, există două tipuri principale de grafice: direcționate și nedirecționate. În primul, muchiile sunt direcționate, adică există o singură direcție disponibilă între două vârfuri conectate, de exemplu, se poate trece de la vârful 1 la vârful 2, dar nu invers. Într-un grafic conectat nedirecționat, puteți merge de la fiecare vârf la fiecare și înapoi. Un caz special al acestor două tipuri este un grafic mixt. Se caracterizează prin prezența atât a marginilor direcționate, cât și a celor nedirecționate.

Gradul de intrare a unui vârf este numărul de muchii care intră în el, gradul de ieșire este numărul de muchii de ieșire.

Marginile graficului nu trebuie să fie drepte, iar vârfurile sunt desemnate prin numere, așa cum se arată în figură. În plus, există astfel de grafice, cărora li se atribuie o anumită valoare muchiilor, se numesc grafice ponderate, iar această valoare este greutatea muchiei. Când ambele capete ale unei muchii coincid, adică muchia iese din vârful F și intră în el, atunci o astfel de muchie se numește buclă.

Graficele sunt utilizate pe scară largă în structurile create de om, cum ar fi rețelele de calculatoare și de transport și tehnologiile web. Căi speciale reprezentările permit utilizarea unui grafic în informatică (în calculatoare). Cele mai cunoscute dintre ele sunt: ​​Matricea adiacentei, Matricea incidentelor, Lista adiacentei, Lista marginilor. Primele două, după cum sugerează și numele, folosesc o matrice pentru a reprezenta un grafic, iar ultimele două folosesc o listă.

Copaci.

copac neordonat

Un copac ca obiect matematic este o abstractizare din unități similare găsite în natură. Asemănarea structurii arborilor naturali cu grafice de un anumit tip indică ipoteza stabilirii unei analogii între ei. Și anume, cu grafice conectate și, în același timp, aciclice (fără cicluri). Aceștia din urmă în structura lor seamănă cu adevărat cu copacii, dar există unele diferențe, de exemplu, este obișnuit să se înfățișeze arbori matematici cu o rădăcină situată în partea de sus, adică toate ramurile „cresc” de sus în jos. Știm că nu este cazul în natură.

Deoarece un arbore este în mod inerent un grafic, multe dintre definițiile sale coincid cu cele din urmă sau sunt similare intuitiv. Deci, nodul rădăcină (vârful 6) din structura arborescentă este singurul vârf (nodul) caracterizat prin absența strămoșilor, adică astfel încât niciun alt vârf nu se referă la el, iar din nodul rădăcină însuși puteți ajunge la oricare dintre nodurile disponibile. arbore, care decurge din proprietatea de conectivitate a acestei structuri. Nodurile care nu se referă la niciun alt nod, cu alte cuvinte, nu au copii se numesc frunze (2, 3, 9) sau noduri terminale. Elementele situate între nodul rădăcină și frunze sunt noduri intermediare (1, 1, 7, 8). Fiecare nod de arbore are un singur strămoș, sau dacă este nodul rădăcină, atunci nu are niciunul.

Un subarbore este o parte a unui arbore care include un nod rădăcină și toate nodurile sale descendente. Deci, de exemplu, în figură, unul dintre subarbori include rădăcina 8 și elementele 2, 1, 9.

Multe operații pot fi efectuate pe un arbore, cum ar fi găsirea elementelor, ștergerea elementelor și subarbori, inserarea subarborilor, găsirea nodurilor rădăcină pentru unele vârfuri etc.Una dintre cele mai importante operații este traversarea arborilor. Există mai multe metode de soluționare. Cele mai populare dintre ele sunt: ​​bypass simetric, înainte și invers. Într-o traversare înainte, nodurile strămoșilor sunt vizitate înaintea descendenților lor, în timp ce într-o traversare inversă, situația este inversată. Într-o traversare simetrică, subarborele arborelui principal sunt scanați unul câte unul.

Reprezentarea datelor în structura considerată este benefică dacă informația are o ierarhie explicită. De exemplu, lucrul cu date despre genuri și specii biologice, poziții oficiale, obiecte geografice etc necesită o structură exprimată ierarhic, cum ar fi arbori matematici.

Subiectul acestui articol este din nou despre teoria programarii, deci trebuie să apelezi la diverse clasificăriși operează cu termeni matematici. Structurile de date sunt practic primul lucru despre care vorbesc în timpul antrenamentului. Estimarea complexității algoritmilor este a doua. Poate părea că aceste două întrebări sunt puțin legate, dar nu sunt și, pe măsură ce povestea progresează, va deveni clar de ce. Nu voi intra în detalii, pentru că practica arată că în procesul de acumulare a experienței în cap rămâne doar cele mai importante. După părerea mea, asta se întâmplă în orice domeniu de activitate. Voi încerca să spun ce a mai rămas în capul meu 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 diferite forme clasificări și precizări. 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 de date simple sunt caracterizate, de exemplu, de tipul întreg, real, boolean, text etc. Structurile complexe de date sunt împărțite în seturi dinamice și statice. Cele dinamice vă permit să le schimbați dimensiunea (adăugați și eliminați elemente) în timpul ciclului lor de viață, în timp ce 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 legată
  • Întoarce-te
  • Tabel de hash

Această clasificare este departe de a fi completă. Elementele structurilor de date complexe pot fi atât instanțe simple, cât și instanțe ale structurilor de date complexe, de exemplu, o structură de date pădure este o listă de arbori care nu se suprapun. Acum voi încerca să dau o scurtă descriere a claselor enumerate de structuri complexe de date. Primul nivel de clasificare este construit pe baza diferențelor în modul de abordare și căutare a elementelor individuale într-un set de structuri complexe de date.

Structuri liniare de date

Elementul structurii liniare de date este caracterizat prin număr de serie sau un indice dintr-o succesiune liniară de elemente.

matrice- Este înăuntru static structura liniara asemănătoare date care sunt optimizate pentru căutarea unui element după indexul său. Localizarea fără ambiguitate a unui element în memorie este asigurată tocmai de uniformitatea elementelor 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ă- aceasta este o structură de date liniară dinamică în care fiecare element se referă fie numai la cel anterior - listă liniară unidirecțională, sau la precedentul și următorul după acesta - listă liniară bidirecțională. Avantajul acestei structuri de date, pe lângă faptul că este redimensionabilă, este ușurința implementării. De asemenea, datorită prezenței referințelor, fiecare element din 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 legată este o variantă a listei liniare obișnuite, optimizată pentru adăugarea și eliminarea elementelor. Optimizarea constă în faptul că elementele lista legată nu trebuie să fie localizate unul după altul în memorie. Ordinea elementelor este determinată de o referire la primul element (nu trebuie să fie chiar la începutul memoriei alocate listei) și o succesiune de referințe la elementele rămase din listă.

Lista legată.

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) - last in, first out. De exemplu, în timpul execuției codul programului, calculatorul, dacă este necesar să apeleze o procedură sau o funcție, pune mai întâi un pointer către locul apelului său pe stivă, astfel încât la finalizarea execuției codului său să revină corect la instrucțiunea care urmează punctului. a apelului. O astfel de structură de date este numită stivă de apeluri subrutine.

Grămadă.

Întoarce-te- 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, primul ieșit. Pentru exemple în viata reala După cum sugerează și numele, nu trebuie să mergeți departe. În programare, folosind cozi, de exemplu, gestionează evenimente interfața cu utilizatorul, apelurile clienților și alte solicitări de informații.

Întoarce-te.

Tabel de hash este cel mai complex tip de structuri de date dinamice liniare. Tabelul hash este optimizat pentru recuperarea rapidă a elementului prin calculul adresei elementului ca valoare hash. Argumentul funcției hash este o cheie asociată cu elementul, de exemplu, numărul său ordinal. Pentru a garanta valori hash unice pentru valori unice cheie (elimină coliziunile) tabelul hash, pe lângă algoritmii complicati, folosește, de asemenea, cu generozitate RAM. 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 este 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 și determină dimensiunea arborelui. Alocați separat binar sau arbori binari, așa cum 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 elementelor 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 rădăcină - o cale. Lungimea căii este nivelul nodului din ierarhia arborescentă. Pentru arbori 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ă între paranteze, î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 în ordine simetrică. Pentru ca elementele să fie înăuntru ordine inversă, în procesul de traversare este necesar să se schimbe ordinea subarborilor vizitați.

Arbore binar (binar).

Lista ierarhică- o simbioză a unei liste liniare și a unui arbore. Fiecare element al listei poate fi, de asemenea, începutul listei următorului subnivel al ierarhiei. Un exemplu de listă ierarhică este structura forumurilor de pe Internet: o secvență de postări formează o listă liniară, în timp ce postările care sunt răspunsuri la alte postări 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 legături către alte elemente învecinate. În astfel de structuri de date, nici elementul inițial, nici elementul rădăcină nu se disting în mod explicit.

Grafic- structura de date dinamica a retelei, reprezentata printr-un set de varfuri si muchii - conexiuni intre varfuri. Fiecare vârf poate fi conectat la orice număr de alte vârfuri sau la el însuși. Nu există o ierarhie clară aici. Dacă considerăm nodurile de arbore ca vârfuri de graf și legăturile dintre nodurile de arbore de diferite niveluri de ierarhie ca margini ale graficului, atunci arborele în sine poate fi considerat un grafic care nu conține cicluri sau un grafic aciclic. Dacă este definită o direcție pentru fiecare margine a unui grafic, atunci acesta este un grafic direcționat. Pe lângă direcție, fiecare margine a graficului poate avea propria sa greutate. Cu ajutorul unui grafic, de exemplu, se modelează rețelele de transport și se rezolvă problemele pentru optimizarea fluxurilor de trafic. aglomeratie sau invers debitului autostrăzile de transport este dată de greutatea marginilor corespunzătoare.

Grafic.

Graficul orientat.

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ă. Tabelele sunt exemple de structuri de date tabelare.

Estimarea complexității algoritmilor

Prin estimarea complexității algoritmilor, ne referim nu la eforturile intelectuale pe care le-au depus autorii în dezvoltarea lor, ci la dependența numărului de operații elementare efectuate de un computer de cantitatea de informații care este procesată. De exemplu, modul în care numărul de comparații a două numere va depinde de lungimea secvenței originale în timpul funcționării algoritmului de sortare. Am restrâns puțin definiția în mod deliberat, deoarece în viitor 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. Cum algoritm mai simplu, cu atât este mai probabil să funcționeze mai mult. Complex și algoritmi rapizi folosesc adesea structuri de date auxiliare și, ca urmare, consumă memorie suplimentară. Legea conservării energiei sau „trebuie să plătești pentru tot”. Un exemplu de „optimizare marginală” discutată mai devreme este tabelul hash. Personal nu știu cum funcționează un tabel hash și cum arată funcțiile hash (presupun că nu este ușor), dar timpul de căutare a elementelor după cheie practic nu depinde de dimensiunea tabelului. Mai jos este o teorie.

Complexitatea algoritmilor este evaluată cu ajutorul aparatului de matematică 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 exactă 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 de complexitate superioară, cât și una mai mică. 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 mulțimea 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 complexitate 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 analizei algoritmice, estimarea complexității este cel mai adesea înțeleasă ca estimarea complexității superioare. Acest lucru este destul de logic, deoarece cea mai importantă estimare este timpul în care se garantează că algoritmul își va finaliza activitatea și nu timpul în care cu siguranță nu se va finaliza.

Lucrul cu structuri de date liniare

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. operatii elementare, acest caz, sunt operațiunile de comparare, enumerare, calcul de adrese sau permutare a elementelor unui set de structuri de date. LA masă rotativă, pe lângă estimarea de complexitate superioară, sunt date și componentele bibliotecii corespunzătoare structurilor de date enumerate. Astfel, principalele structuri de date liniare sunt deja disponibile și disponibile pentru toți dezvoltatorii de software de pe .

O structură de date este o unitate software care vă permite să salvați și să procesați o mulțime de informații de același tip sau legate logic în dispozitivele de calcul. Dacă doriți să adăugați, să găsiți, să modificați sau să ștergeți informații, structura va oferi un pachet specific de opțiuni care alcătuiesc interfața sa.

Ce include conceptul de structură de date?

Acest termen poate avea mai multe sensuri apropiate, dar totuși distincte. Aceasta:

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

Vorbind despre structura datelor în context programare functionala, atunci aceasta este o unitate specială care este salvată la schimbare. Poate fi descrisă informal ca o singură structură, în ciuda faptului că ar putea exista diverse versiuni.

Ce formează structura?

Se formează folosind legături și operațiuni asupra acestora într-un anumit limbaj de programare. Merită să spui asta tipuri diferite structurile sunt potrivite pentru implementare aplicatii diferite, unele, de exemplu, au o specializare complet îngustă și sunt potrivite doar pentru producerea sarcinilor stabilite.

Dacă luați 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ă utilizate pe scară largă în practică pentru a crea diverse dicționare, de exemplu, pentru a demonstra numele de domenii în adresele de internet ale computerelor, și nu doar pentru a forma baze de date.

În timpul dezvoltării unui anumit software, complexitatea implementării și calitatea funcționalității programelor depind direct de utilizarea corectă a structurilor de date. Această înțelegere a lucrurilor a dat un impuls dezvoltării metodelor formale de dezvoltare și a limbajelor de programare, unde structurile, și nu algoritmii, sunt plasate într-o poziție de lider în arhitectura programului.

Trebuie remarcat faptul că multe limbaje de programare au tip stabilit modularitatea, care permite structurilor de date să fie utilizate în siguranță în diverse aplicații. Exemple proeminente sunt Limbaje Java, C# și C++. Acum structura clasica datele utilizate sunt prezentate în bibliotecile standard ale limbajelor de programare sau direct sunt deja încorporate în limbajul în sine. De exemplu, tabelele hash sunt încorporate î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 pt limbaje funcționale mai dificil decât pentru cele imperative, există cel puțin două motive pentru aceasta:

1. De fapt, toate structurile folosesc adesea atribuirea în practică, care nu este folosită într-un stil pur funcțional.
2. Structuri funcționale 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, în timp ce în programarea funcțională sunt permanente.

Ce include structura?

Adesea, datele cu care lucrează programele sunt stocate în matrice încorporate în limbajul de programare utilizat, o constantă sau în lungime variabilă. O matrice este cea mai simplă structură cu informații, totuși, unele sarcini necesită o eficiență mai mare a unor operații, prin urmare se folosesc alte structuri (mai dificile).

Cea mai simplă matrice este potrivită pentru acces frecvent componentele instalate prin indici și modificarea acestora, iar îndepărtarea elementelor din mijloc operează după principiul O (N) O (N). Dacă trebuie să eliminați elemente pentru a îndeplini anumite sarcini, 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, ci doar străbate elementele unul câte unul și le caută după valoare. Astfel, putem spune că structura diferă în operațiuni, ceea ce este capabilă să realizeze, precum și în viteza de a le face. De exemplu, merită luate în considerare cele mai simple structuri, care nu oferă beneficii în eficiență, dar au exact set set operațiuni susținute.

Grămadă

Acesta este unul dintre tipurile de structuri de date, reprezentate ca o matrice elementară 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 (Complexitate: O(1)O(1)).

Pentru a explica cum funcționează stiva, puteți aplica în practică analogia unui borcan de prăjituri. Imaginați-vă că există mai multe fursecuri pe fundul vasului. Deasupra, mai poti pune cateva bucati, sau poti, dimpotriva, sa ia un fursec de deasupra. Restul fursecurilor vor fi acoperite de cele de sus și nu veți ști nimic despre ele. Așa stau 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 și scoasă din acesta.

Întoarce-te

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 extras primul. Numele structurii vorbește de la sine - principiul de funcționare coincide complet cu cozile, care pot fi văzute într-un magazin, supermarket.

Dec

Acesta este un alt tip de structură de date, cunoscută și sub numele de coadă dublă. Opțiunea acceptă următorul set de operații:

• Aduceți elementul la început (Dificultate: O(1)O(1)).
• Extrageți componenta din origine (Dificultate: O(1)O(1)).
• Introducerea unui element la capăt (Dificultate: O(1)O(1)).
• Îndepărtarea unui element de la capăt (Complexitate: O(1)O(1)).
• Verificarea dacă deque-ul este gol (Complexitate: O(1)O(1)).

Liste

Această structură data definește o secvență de componente conectate liniar pentru care sunt permise operațiunile de adăugare a componentelor în orice loc din listă și eliminarea acesteia. 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, unirea a două liste într-un singur întreg, împărțirea unei liste într-o pereche și așa mai departe. De menționat că într-o listă liniară, pe lângă prima, există o componentă anterioară pentru fiecare element, fără a include și 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 trece prin toate componentele.

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

Elementele din această listă sunt egale. Distincția dintre primul și ultimul este o convenție.

Copaci

Aceasta este o colecție de componente, care se numesc noduri, în care există o componentă principală (una) sub formă de rădăcină, iar toate celelalte sunt împărțite într-un set de elemente care nu se suprapun. 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 prin relații părinte-copil. Ca rezultat, se poate observa o structură ierarhică a nodurilor. Dacă nodurile nu au copii, atunci se numesc frunze. Deasupra arborelui, astfel de operații sunt definite ca: adăugarea unei componente și îndepărtarea acesteia, parcurgerea, căutarea unei componente. Arborii binari joacă un rol special în informatică. Ce este? Acesta este un caz special de arbore, în care fiecare nod poate avea cel mult o pereche de copii care sunt rădăcinile subarborilor din stânga și din dreapta. Dacă, în plus, pentru nodurile arborelui, este de asemenea îndeplinită condiția ca toate valorile componentelor subarborelui din stânga să fie mai mici decât valorile rădăcinii și valorile componentelor subarborele drept sunt mai mari decât rădăcina, atunci un astfel de arbore se numește arbore de căutare binar și este destinat să găsească rapid elemente. Cum funcționează algoritmul de căutare în acest caz? Valoarea căutată este comparată cu valoarea rădăcinii și, în funcție de rezultat, căutarea fie se termină, fie continuă, dar numai î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 traseul de la rădăcină la una dintre frunze).

Contează

Graficele sunt o colecție de componente numite vârfuri împreună cu un set de relații între aceste vârfuri numite muchii. Interpretarea grafică a acestei structuri este prezentată ca un set de puncte care sunt responsabile pentru vârfuri, iar unele perechi sunt conectate prin linii sau săgeți, care corespund muchiilor. Ultimul caz spune că graficul ar trebui numit direcționat.

Graficele pot descrie obiecte din orice structură; ele sunt instrumentul principal pentru descrierea structurilor complexe și a funcționării tuturor sistemelor.

Mai multe despre structura abstractă

Pentru a construi un algoritm, este necesară formalizarea datelor sau, cu alte cuvinte, este necesară aducerea datelor la un anumit model informativ care a fost deja cercetat și scris. Odată ce modelul a fost găsit, se poate argumenta că s-a stabilit o structură abstractă.

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

Analiza structurilor de date este realizată de următoarele obiecte:

• Întregul și numere reale.
• Valori booleene.
• Simboluri.

Pentru procesarea tuturor elementelor pe un computer, există algoritmi și structuri de date adecvate. Obiectele 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:

• Vectori.
• Structuri dinamice.
• Mese.
• Matrice multidimensionale.
• Contează.

Dacă toate elementele sunt alese cu succes, atunci aceasta va fi cheia formării unor algoritmi și structuri de date eficiente. Dacă aplicăm în practică analogia structurilor și obiectelor reale, atunci putem rezolva eficient problemele existente.

Este de remarcat faptul că toate structurile de organizare a datelor există separat în programare. S-a lucrat mult la ele în secolele al XVIII-lea și al XIX-lea, când încă nu se vedea computerul.

Este posibil să se dezvolte un algoritm din punct de vedere al unei structuri abstracte, totuși, pentru a implementa algoritmul într-un limbaj de programare specific, va fi necesar să se găsească o tehnică de reprezentare a acestuia în tipuri de date, operatori, care sunt susținute de un limbaj de programare specific. Pentru a crea structuri precum un vector, tabel, șir, secvență, multe limbaje de programare au tipurile 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ă. La rezolvarea absolută a oricărei probleme, este necesar să se lucreze cu unele date pentru a efectua operațiuni pe informații. Fiecare sarcină are propriul său set de operații, dar unele seturi sunt folosite în practică mai des pentru a rezolva diverse sarcini. În acest caz, este util să veniți cu anumit fel organizarea informaţiei astfel încât aceste operaţiuni să poată fi realizate cât mai eficient. Imediat ce a apărut această metodă, putem presupune că aveți o „cutie neagră” în care vor fi stocate date de un anumit fel și care va efectua anumite operațiuni cu date. Acest lucru vă va permite să vă distrageți atenția de la detalii și să vă concentrați pe deplin trasaturi caracteristice sarcini. Această „cutie neagră” poate fi implementată în orice mod, în timp ce este necesar să ne străduim pentru implementarea cât mai productivă posibilă.

Cine trebuie să știe asta?

Merită să faceți cunoștință cu informațiile pentru programatorii începători care doresc să-și găsească locul în această zonă, dar nu știu unde să meargă. Acestea sunt elementele de bază în fiecare limbaj de programare, așa că nu va fi de prisos să înveți imediat despre structurile de date și apoi să lucrezi cu ele pe exemple specifice și cu un anumit limbaj. Nu trebuie uitat că fiecare structură poate fi caracterizată prin reprezentări logice și fizice, precum și printr-un set de operații asupra acestor reprezentări.

Nu uitați: dacă vorbiți despre o anumită structură, atunci țineți cont de reprezentarea ei logică, deoarece reprezentarea fizică este complet ascunsă de „observatorul din exterior”.

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

Nu vă grăbiți să începeți să învățați structuri specifice, cel mai bine este să înțelegeți clasificarea acestora, să cunoașteți pe toată lumea î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.