Structurile de date și evaluarea complexității algoritmului. Structuri de date: concept general, implementare. Cele mai simple structuri de date: coadă, stivă. Folosind o stivă și notație poloneză inversă

Traducere
Mod de recuperare

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. Programatorii buni se gândesc 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ă acestea sunt în esență doar 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

O stivă este o structură de date de bază care permite adăugarea sau eliminarea elementelor doar la început. 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 gândită ca o linie la un 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 în nicio ordine anume, fără a le repeta. Nu numai că vă permite să adăugați și să eliminați elemente, există câteva alte funcții importante care pot fi aplicate 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 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ă returneze același număr. 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 apoi 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 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. Ele sunt proiectate astfel încât timpul fiecărei operații să fie proporțional cu logaritmul numărului total de 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 pentru a efectua căutări rapide asupra lor - 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. Într-un heap maxim, cheia oricărui nod este întotdeauna mai mare sau egală cu cheile descendenților săi. Î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.

O condiție necesară pentru construirea 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 prelucrarea 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), iar în cazul general - tablouri multidimensionale;

· structuri dinamice:

Secvențe de simboluri, numere;

Cozi;

Copaci;

O alegere de 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 soluții eficiente la probleme.

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 XVIII, cât și în secolele XIX, 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 reprezentarea computerizată a structurilor abstracte, folosim structuri de date, care sunt un set de variabile, eventual de diferite tipuri de 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țiunile tipice pe liste sunt: parcurgerea unei liste, căutarea unui element dat, inserarea unui element imediat după sau înaintea unui 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 o 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 o legătură 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 sunt definite atât elementele precedente, cât și cele 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ă- un caz special al unei liste liniare cu legături unice pentru care sunt definite două operații: adăugarea unui element în partea de sus a stivei (înaintea primului element) și îndepărtarea unui element din partea de sus a stivei (eliminarea primului element).

Exemplul 3. Să luăm în considerare problema determinării echilibrului parantezelor de diferite tipuri într-o 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 apropiat de termenul 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. Pe arbore sunt definite următoarele operații: adăugarea unui element în arbore, eliminarea unui element din arbore, parcurgerea arborelui, căutarea unui element în 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, pentru nodurile arborelui este îndeplinită condiția ca toate valorile elementelor subarborelui din stânga să fie mai mici decât valoarea rădăcinii arborelui, iar toate valorile elementelor subarborelui din dreapta sunt mai mare decât valoarea rădăcinii, atunci se numește un astfel de arbore 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 obiectelor complexe și a funcționării sistemelor. De exemplu, pentru a descrie o rețea de calculatoare, un sistem de transport, o 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, când descrieți sistemul rutier rusesc folosind un grafic, lungimea drumului (greutatea marginii graficului) care leagă anumite așezări (vârfurile graficului) este importantă. 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țiuni este adesea folosit pentru a rezolva diverse probleme, atunci este util să veniți cu o modalitate de organizare a datelor care vă permite să efectuați aceste operațiuni particulare cât mai eficient posibil. După ce o astfel de metodă a fost inventată, atunci când rezolvăm o problemă specifică, putem presupune că avem o „cutie neagră” (o vom numi o structură de date), despre care se știe că în ea sunt stocate date de un fel, şi care poate efectua unele operaţii asupra acestor date. Acest lucru vă permite să scăpați de detalii și să vă concentrați pe caracteristicile specifice ale sarcinii. Î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 de programare școlară de bază, Programul Exemplu menționează lanțuri de caractere (șiruri), numere, liste, arbori și grafice ca obiecte procesate. Cu toate acestea, în lucrările practice, numai o matrice este menționată din datele unei structuri complexe (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, de exemplu, 0. Procedura de parcurgere recurstivă a arborelui 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 a rezolva cu succes problemele olimpiadei în informatică. Astfel, la etapa a IV-a a districtului federal a Olimpiadei All-Russian de informatică din 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.

Conceptul unui model de date

Modele de date

Un model de date este un instrument pentru modelarea unui domeniu arbitrar.

Model de date este un set de reguli pentru generarea structurilor de date într-o bază de date, operațiunile asupra acestora, precum și constrângerile de integritate care determină conexiunile și valorile de date permise, precum și succesiunea modificărilor acestora. Deci, modelul de date constă din trei părți:

Un set de tipuri de structuri de date.

Aici putem face o analogie cu limbaje de programare, care au și tipuri predefinite de structuri de date, cum ar fi date scalare, vectori, matrice, structuri (de exemplu, tip structîn limbaj C), etc.

Un set de operatori sau reguli de inferență care pot fi aplicate oricăror exemple valide ale tipurilor de date enumerate la (1) pentru a găsi, deduce sau transforma informațiile conținute în orice părți ale acestor structuri în orice combinații.

Astfel de operațiuni sunt: crearea și modificarea structurilor de date, introducerea de date noi, ștergerea și modificarea datelor existente, căutarea datelor în diferite condiții.

Un set de reguli generale de integritate care definesc direct sau indirect setul de stări consistente ale unei baze de date și/sau setul de modificări ale stării acesteia.

Regulile de integritate sunt determinate de tipul de date și de domeniul subiectului. De exemplu, valoarea atributului Tejghea este un număr întreg, adică poate consta doar din numere. Și limitările domeniului sunt de așa natură încât acest număr nu poate fi mai mic de zero.

Acum să aruncăm o privire mai atentă la seturile care alcătuiesc modelul de date.

Structurarea datelor se bazează pe utilizarea conceptelor de „agregare” și „generalizare”. Una dintre primele opțiuni pentru structurarea datelor a fost propusă de Asociația pentru Limbaje de Procesare a Datelor (Conference on Data Systems Languages, CODASYL) (Fig. 2.1).

Fig.2.1 Compoziția structurilor de date conform versiunii CODASYL

Element de date– cea mai mică unitate de date numită pe care SGBD-ul o poate accesa direct și cu ajutorul căreia sunt construite toate celelalte structuri. Pentru fiecare element de date trebuie definit tipul acestuia.

Agregat– o colecție numită de elemente de date într-o înregistrare care poate fi considerată ca un întreg unic. Un agregat poate fi simplu (incluzând doar elemente de date, Fig. 2.2, a) și compus (inclusiv, împreună cu elementele de date, alte agregate, Fig. 2.2, b).

Fig.2.2 Exemple de unități: a) unitate simplă și b) unitate compusă

Record– o colecție numită de elemente de date sau elemente de date și agregate. O înregistrare este un agregat care nu face parte din niciun alt agregat; poate avea o structură ierarhică complexă deoarece agregarea poate fi aplicată de mai multe ori. Se face o distincție între un tip de înregistrare (structura sa) și o instanță de înregistrare, de exemplu. o înregistrare cu valori specifice elementelor de date. O înregistrare descrie proprietățile unei entități software (instanță). Uneori termenul „înregistrare” este înlocuit cu termenul „grup”.

Un exemplu de înregistrare care conține informații despre un angajat este prezentat în Fig. 2.3.

Fig.2.3 Exemplu de intrare de tip ANGAJAT

Această înregistrare conține mai multe elemente de date ( Numărul permisului, Poziția, Sexul etc.) și trei unități: unități simple Numele complet Și Abordare și agregat care se repetă Telefoane . (Un agregat care se repetă poate fi inclus într-o înregistrare de orice număr de ori.)

Printre elementele de date (câmpurile de înregistrare), una sau mai multe chei câmpuri. Valorile câmpurilor cheie vă permit să clasificați entitatea căreia îi aparține o anumită înregistrare. Se apelează cheile cu valori unice potenţial. Fiecare cheie poate reprezenta un agregat de date. Una dintre chei este desemnată ca cheie primară, restul sunt secundare. Cheia principala identifică o instanță a unei înregistrări, valoarea acesteia trebuie să fie unică și necesară pentru înregistrările de același tip. De exemplu în Fig. 2.3 cheile potențiale sunt câmpuri Numărul permisului Și Pașaport , și este mai potrivit să selectați câmpul ca cheie primară Numărul permisului , deoarece în mod clar ocupă mai puțină memorie decât datele pașapoartelor.

Kit(sau atitudine de grup) – o colecție numită de înregistrări care formează o structură ierarhică pe două niveluri. Fiecare tip de set reprezintă o relație între două sau mai multe tipuri de înregistrare. Pentru fiecare tip de set, un tip de înregistrare este declarat drept proprietar al setului, iar tipurile de înregistrare rămase sunt declarate ca membri ai setului. Fiecare instanță a unui set trebuie să conțină o singură instanță a unei înregistrări de tip proprietar și atâtea instanțe de înregistrări de tip membru al setului câte sunt asociate proprietarului. Pentru o relație de grup, se face și o distincție între tip și instanță.

Este convenabil să descrii relațiile de grup folosind o diagramă Bachman, care este numită după unul dintre dezvoltatorii modelului de date de rețea. O diagramă Bachmann este un grafic direcționat, ale cărui vârfuri corespund unor grupuri (tipuri de înregistrări), iar arcele corespund relațiilor de grup (Fig. 2.4).

Orez. 2.4 Exemplu de diagramă Bachmann pentru un fragment din baza de date City

Iată o intrare ca POLICLINICĂ este proprietarul înregistrărilor de tip LOCUITOR examinare clinică . Tipul de înregistrare ORGANIZARE este și proprietarul unor înregistrări ca LOCUITOR și sunt conectați printr-o relație de grup muncă . Înregistrări de tip REU și tip LOCUITOR sunt proprietarii înregistrărilor de tip APARTAMENT cu relații în consecință servi Și locui . Astfel, o înregistrare de același tip poate fi membru al unei relații și proprietar al alteia.

Bază de date– o colecție numită de instanțe de grupuri și relații de grup. Acesta este cel mai înalt nivel de structurare a datelor.

Notă: structurarea datelor conform CODASYL este utilizată în modelele de date de rețea și ierarhice. Modelul relațional adoptă o structurare diferită a datelor bazată pe teoria mulțimilor.

Traducere

Desigur, poți fi un programator de succes fără cunoștințe sacre despre structurile de date, dar acestea sunt absolut indispensabile în unele aplicații. De exemplu, atunci când trebuie să calculați calea cea mai scurtă între două puncte de pe o hartă sau să găsiți un nume într-o agenda telefonică care conține, de exemplu, un milion de intrări. Ca să nu mai vorbim că structurile de date sunt folosite tot timpul în programarea sportivă. Să ne uităm la unele dintre ele mai detaliat.

Coadă

Deci salută-l pe Loopy!

Loopy îi place să joace hochei cu familia sa. Și prin „joc” vreau să spun:

Când țestoasele zboară în poartă, sunt aruncate în vârful stivei. Rețineți că prima țestoasă adăugată la grămadă este prima care o părăsește. Se numeste Coadă. La fel ca în cozile pe care le vedem în viața de zi cu zi, primul element adăugat în listă este primul care îl părăsește. Această structură se mai numește FIFO(Primul Intrat, Primul Ieșit).

Dar operațiunile de inserare și ștergere?

Q = def insert(elem): q.append(elem) #adăugați un element la sfârșitul cozii print q def delete(): q.pop(0) #eliminați elementul zero din coada print q

Grămadă

După un joc atât de distractiv de hochei, Loopy face clătite pentru toată lumea. Ea le pune într-o grămadă.

Când toate clătitele sunt gata, Loopy le servește întregii familii, una câte una.

Rețineți că prima clătită pe care o face va fi servită ultima. Se numeste Grămadă. Ultimul element adăugat în listă va fi primul care îl părăsește. Această structură de date mai este numită LIFO(Ultimul intrat, primul ieşit).

Adăugarea și eliminarea elementelor?

S = def push(elem): #Adăugați un element la stivă - Push s.append(elem) print s def customPop(): #Eliminați un element din stivă - Pop s.pop(len(s)-1) imprimare s

Morman

Ați văzut vreodată un turn de densitate?

Toate elementele de sus în jos sunt amplasate în locurile lor, în funcție de densitatea lor. Ce se întâmplă dacă arunci un obiect nou înăuntru?

Va ocupa spațiu în funcție de densitatea sa.

Cam așa funcționează Morman.

O grămadă este un arbore binar. Aceasta înseamnă că fiecare element părinte are doi copii. Și deși numim această structură de date o grămadă, ea este exprimată printr-o matrice obișnuită.
De asemenea, heap-ul are întotdeauna o înălțime de logn, unde n este numărul de elemente

Figura arată un max-heap bazat pe următoarea regulă: copii Mai puțin părintească. Există, de asemenea, grămezi de min-heap, unde copiii sunt întotdeauna Mai mult părintească.

Câteva funcții simple pentru lucrul cu grămezi:

Heap global currSize global def parent(i): #Obțineți indexul părintelui pentru elementul i-lea return i/2 def left(i): #Obțineți copilul din stânga al i-lea element return 2*i def dreapta (i): #Obțineți copilul drept al i-a revenire (2*i + 1)

Adăugarea unui element la un heap existent
Pentru început, adăugăm un element chiar în partea de jos a mormanei, adică. până la sfârșitul matricei. Apoi îl schimbăm cu elementul său părinte până când se potrivește.

Algoritm:

Adăugați un element chiar în partea de jos a mormanului.
Comparați elementul adăugat cu cel părinte; Dacă comanda este corectă, ne oprim.
Dacă nu, schimbați elementele și reveniți la punctul anterior.

Cod:

Def swap(a, b): #swap elementul cu index a pentru elementul cu index b temp = heap[a] heap[a] = heap[b] heap[b] = temp def insert(elem): global currSize index = len(heap) heap.append(elem) currSize += 1 par = parent(index) flag = 0 while flag != 1: if index == 1: #Am atins indicatorul elementului rădăcină = 1 elif heap > elem : #Dacă indexul elementului rădăcină este mai mare decât indicele elementului nostru - elementul nostru este în locul său flag = 1 else: # Schimbați elementul părinte cu swap(par, index) index = par par = parent(index) ) grămada de imprimare
Numărul maxim de treceri ale buclei while este egal cu înălțimea arborelui, sau logn, prin urmare complexitatea algoritmului este O(logn).

Recuperarea elementului heap maxim
Primul element din grămada este întotdeauna maximul, așa că îl vom elimina pur și simplu (după ce ne-am amintit mai întâi) și îl vom înlocui cu cel mai jos. Vom pune apoi grămada în ordinea corectă folosind funcția:

MaxHeapify().

Algoritm:

Înlocuiți elementul rădăcină cu elementul inferior.
Comparați noul element rădăcină cu copiii săi. Dacă sunt în ordinea corectă, opriți-vă.
Dacă nu, înlocuiți elementul rădăcină cu unul dintre copii (mai mic pentru min-heap, mai mare pentru max-heap) și repetați pasul 2.

Def extractMax(): global currSize if currSize != 0: maxElem = heap heap = heap #Înlocuiți elementul rădăcină cu ultimul heap.pop(currSize) #Eliminați ultimul element currSize -= 1 #Reduceți dimensiunea heap maxHeapify( 1) return maxElem def maxHeapify(index): global currSize lar = index l = left(index) r = right(index) #Calculați care element copil este mai mare; dacă este mai mare decât cel părinte, schimbați locurile dacă l<= currSize and heap[l] >grămada: lar = l dacă r<= currSize and heap[r] >heap: lar = r if lar != index: swap(index, lar) maxHeapify(lar)
Din nou, numărul maxim de apeluri la funcția maxHeapify este egal cu înălțimea arborelui, sau logn, ceea ce înseamnă că complexitatea algoritmului este O(logn).

Facem o grămadă din orice matrice aleatorie
Bine, există două moduri de a face asta. Primul este să introduceți fiecare element în grămada unul câte unul. Este simplu, dar complet ineficient. Complexitatea algoritmului în acest caz va fi O(nlogn), deoarece funcția O(logn) va fi executată de n ori.

O modalitate mai eficientă este să utilizați funcția maxHeapify pentru „ sub-grămădii', de la (currSize/2) la primul element.

Complexitatea va fi O(n), iar dovada acestei afirmații, din păcate, depășește scopul acestui articol. Trebuie doar să înțelegeți că elementele din porțiunea currSize/2 până la currSize a heap-ului nu au copii, iar majoritatea „sub-heap-urilor” formate în acest fel vor avea o înălțime mai mică decât autentificarea.

Def buildHeap(): global currSize for i in range(currSize/2, 0, -1): #al treilea argument din range() este pasul de căutare, în acest caz determină direcția. print heap maxHeapify(i) currSize = len(heap)-1

Serios, de ce sunt toate astea?

Sunt necesare grămezi pentru a implementa un tip special de sortare numit, destul de ciudat, „ sortare grămadă" Spre deosebire de „sortarea prin inserție” și „sortarea cu bule” mai puțin eficiente, cu complexitatea lor teribilă O(n2), „sortarea grămezilor” are complexitatea O(nlogn).

Implementarea este indecent de simplă. Continuați să scoateți secvențial elementul maxim (rădăcină) din heap și să îl scrieți în matrice până când heap-ul este gol.

Def heapSort(): for i in range(1, len(heap)): print heap heap.insert(len(heap)-i, extractMax()) #inserați elementul maxim la sfârșitul matricei currSize = len( grămada)-1
Pentru a rezuma toate cele de mai sus, am scris câteva rânduri de cod care conțin funcții pentru lucrul cu heap-ul, iar pentru fanii OOP, am formatat totul ca o clasă.

Ușor, nu-i așa? Aici vine sărbătorirea Loopy!

Hash

Loopy vrea să-și învețe copiii să recunoască forme și culori. Pentru a face acest lucru, ea a adus acasă un număr mare de figuri colorate.

După un timp, țestoasele au devenit complet confuze

Așa că a scos o altă jucărie pentru a ușura puțin procesul.

A devenit mult mai ușor, pentru că țestoasele știau deja că figurile sunt sortate după formă. Dacă am eticheta fiecare pilon?

Țestoasele trebuie acum să verifice un stâlp cu un anumit număr și să-l aleagă pe cel potrivit dintr-un număr mult mai mic de cifre. Ce se întâmplă dacă avem și un stâlp separat pentru fiecare combinație de formă și culoare?

Să presupunem că numărul coloanei este calculat după cum urmează:

Numele complet vară tre pătrat
f+i+o+t+r+e = 22+10+16+20+18+6 = Coloana 92

Kra somnoros Drept triunghi
k+p+a+p+p+i = 12+18+1+17+18+33 = Coloana 99

Știm că 6*33 = 198 de combinații posibile, ceea ce înseamnă că avem nevoie de 198 de piloni.

Să numim această formulă pentru calcularea numărului coloanei - Funcția hash.

Cod:
def hashFunc(piece): words = piece.split(" ") #split the string into words color = words shape = words poleNum = 0 for i in range(0, 3): poleNum += ord(colour[i]) - 96 poleNum += ord(shape[i]) - 96 return poleNum
(cu chirilic este puțin mai complicat, dar am lăsat-o așa pentru simplitate. - aproximativ)

Acum, dacă ar fi să aflăm unde este stocat pătratul roz, putem calcula:
hashFunc(„pătrat roz”)

Acesta este un exemplu de tabel hash în care locația elementelor este determinată de o funcție hash.
Cu această abordare, timpul petrecut căutând orice element nu depinde de numărul de elemente, adică. O(1). Cu alte cuvinte, timpul de căutare într-un tabel hash este o valoare constantă.

Bine, dar să presupunem că căutăm „ mașină amel Drept triunghi” (dacă, desigur, culoarea „caramel” există).

HashFunc(„dreptunghi caramel”)
ne va returna 99, care este același număr pentru dreptunghiul roșu. Se numeste " Coliziune" Pentru a rezolva o coliziune folosim „ Metoda lanțului”, implicând că fiecare coloană stochează o listă în care căutăm înregistrarea de care avem nevoie.

Așa că punem dreptunghiul de bomboane pe cel roșu și alegem unul când funcția hash indică acel pilon.

Cheia pentru un tabel hash bun este alegerea unei funcții hash adecvate. Acesta este, fără îndoială, cel mai important lucru în crearea unui tabel hash, iar oamenii petrec o cantitate imensă de timp dezvoltării funcțiilor hash de calitate.
În tabelele bune, nicio poziție nu conține mai mult de 2-3 elemente; în caz contrar, hashingul nu funcționează bine și trebuie să schimbați funcția hash.

Încă o dată, căutați independent de numărul de elemente! Putem folosi tabele hash pentru orice are o dimensiune gigantică.

Tabelele hash sunt, de asemenea, folosite pentru a găsi șiruri și subșiruri în bucăți mari de text folosind algoritmul Rabin-Karp sau algoritm Knuth-Morris-Pratt, care este util, de exemplu, pentru identificarea plagiatului în lucrările științifice.

Cred că putem termina aici. În viitor, intenționez să mă uit la structuri de date mai complexe, de ex. grămada FibonacciȘi Arborele segmentului. Sper că ați găsit acest ghid informal interesant și util.

Tradus pentru Habr blocat

O condiție necesară pentru stocarea informațiilor în memoria computerului este capacitatea de a converti aceste informații într-o formă potrivită pentru un computer. Dacă această condiție este îndeplinită, este necesar să se determine o structură adecvată special pentru informațiile existente, una care să ofere setul necesar de capabilități pentru a lucra cu aceasta.

Lista de apeluri

Aici, structura este înțeleasă ca o modalitate de prezentare a informațiilor prin care un set de elemente individuale formează ceva unificat, determinat de relația lor între ele. Atunci când sunt aranjate după anumite reguli și conectate logic între ele, datele pot fi procesate foarte eficient, deoarece structura comună pentru acestea oferă un set de posibilități de gestionare a acestora - unul dintre motivele prin care se obțin rezultate înalte în rezolvarea anumitor probleme.

Dar nu fiecare obiect este reprezentat într-o formă arbitrară și poate că există o singură metodă de interpretare pentru el, prin urmare, cunoașterea tuturor structurilor de date existente va fi un avantaj incontestabil pentru programator. Astfel, de multe ori trebuie să alegeți între diferite metode de stocare a informațiilor, iar performanța produsului depinde de această alegere.

Vorbind despre tehnologia non-computerică, este posibil să nu arătăm niciun caz în care informația să aibă o structură evidentă. Un bun exemplu sunt cărțile cu conținut variat. Acestea sunt împărțite în pagini, paragrafe și capitole și au de obicei un cuprins, adică o interfață pentru utilizarea lor. Într-un sens larg, fiecare creatură vie are o structură; fără ea, materia organică cu greu ar putea exista.

Este probabil ca cititorul să fi întâlnit structuri de date direct în informatică, de exemplu, cele construite într-un limbaj de programare. Acestea sunt adesea denumite tipuri de date. Acestea includ: matrice, numere, șiruri de caractere, fișiere etc.

Metodele de stocare a informațiilor, numite „simple”, adică indivizibile în părți componente, sunt de preferat să fie studiate împreună cu un limbaj de programare specific, sau să 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 matricei. De exemplu, matricele unidimensionale (vectori) și bidimensionale (matrici) sunt cel mai des întâlnite.

Primele au un singur indice, cele din urmă – 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ă sub forma unui tabel, ale cărui elemente sunt accesate prin numele matricei, precum și numerele de rând și coloane la intersecția cărora se află elementul: A, unde i este numărul rândului, j este numărul coloanei.

Lucrul cu matrice poate diferi în anumite moduri în diferite limbaje de programare, dar principiile de bază sunt de obicei aceleași peste tot. În limbajul Pascal, accesul la o matrice unidimensională și bidimensională are loc exact așa cum se arată mai sus și, de exemplu, în C++ o matrice bidimensională ar trebui specificată după cum urmează: A[i][j]. Elementele matricei sunt numerotate secvenţial. Limbajul de programare influențează valoarea la 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 primului este caracterizat de dimensiunea variabilă, adică, pe măsură ce programul se execută, dimensiunea matricei dinamice se poate modifica. Această funcție face lucrul cu date mai flexibil, dar în același timp trebuie să sacrifici performanța, iar procesul în sine devine mai complicat.

Un criteriu obligatoriu pentru o matrice statică, după cum sa spus, este omogenitatea datelor stocate simultan în ea. Când această condiție nu este îndeplinită, matricea este eterogenă. Utilizarea sa se datorează dezavantajelor 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 nu este încă suficient. La urma urmei, o matrice este doar o desemnare generală, un gen pentru un anumit număr de implementări posibile. Prin urmare, este necesar să se decidă o anumită metodă de reprezentare, cu cel mai potrivit tablou.

Liste.

O 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 structuri de date cu acces aleatoriu. Acest tip abstract are mai multe implementări sub formă de structuri de date. Unele dintre ele vor fi discutate aici.

O listă (listă legată) este o structură de date care este un set finit de elemente ordonate conectate între ele prin 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.

Lista legată individual

În lista de mai sus conectată individual, elementul inițial este lista Head (nume arbitrar) și orice altceva se numește coada. Coada listei este formată din elemente împărțite în două părți: informațional (câmpul de informații) și indexical (câmpul următor). Ultimul element, în loc de un pointer, conține un terminator de listă - nil.

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

Listă dublu legată

Capacitatea de a deplasa atât înainte, cât și înapoi este utilă pentru unele operațiuni, dar indicatorii suplimentari necesită mai multă memorie decât este necesară într-o listă echivalentă cu legături unice.

Pentru cele două tipuri de liste descrise mai sus, există un subtip numit listă circulară. Puteți face o listă circulară dintr-o listă legată individual, adăugând doar un indicator la ultimul element, astfel încât să se refere la 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 folosind tipul „listă”, dar acestea, de regulă, sunt în mare măsură similare cu cele discutate, așa că vor fi omise aici.

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

Grămadă.

Grămadă

O stivă se caracterizează prin faptul că elementele sale pot fi accesate doar de la un capăt, numit vârful stivei, cu alte cuvinte: o stivă este o structură de date care funcționează conform principiului LIFO (last in - first out). Este mai bine să descrieți această structură de date sub forma unei liste verticale, 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 doar să puneți un articol în partea de sus a stivei.

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

Coadă.

Structura de date Queue folosește principiul de organizare FIFO (First In, First Out). Într-un fel, această metodă este mai corectă decât cea prin care funcționează stiva, deoarece regula simplă care stă la baza cozilor obișnuite din diverse magazine și spitale este considerată destul de corectă și tocmai aceasta stă la baza acestei structuri. Fie ca această observație să fie un exemplu. Strict vorbind, o coadă este o listă în care elemente pot fi adăugate doar la sfârșit și pot fi eliminate de cealaltă parte, numită începutul listei.

Coadă

Dec

Deque (coadă cu două capete) este o stivă cu două capete. Într-adevăr, în ciuda traducerii specifice, un pachet poate fi definit nu numai ca o coadă bidirecțională, ci și ca o stivă care are două capete. Aceasta înseamnă că acest tip de listă permite adăugarea de elemente la început și la sfârșit, și același lucru este valabil și pentru operația de recuperare.

Dec

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ă prin însumarea celor două tipuri anterioare de listă.

Grafice.

Ramura matematicii discrete care se ocupă cu studiul grafurilor se numește teoria grafurilor. Teoria graficelor examinează în detaliu conceptele cunoscute, proprietățile, metodele de reprezentare și domeniile de aplicare 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, puteți 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 orientate, cât și a celor neorientate.

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

Marginile graficului nu trebuie să fie drepte, iar vârfurile sunt desemnate precis prin numere, așa cum se arată în figură. În plus, există 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 și intră în vârful F, atunci o astfel de muchie se numește buclă.

Graficele sunt utilizate pe scară largă în structurile create de om, de exemplu, în rețelele de calculatoare și de transport și în tehnologiile web. Metodele speciale de reprezentare permit utilizarea graficului în informatică (în calculatoare). Cele mai faimoase dintre ele: „Matricea de vecinătate”, „Matricea de incidente”, „Lista de vecinătate”, „Lista marginilor”. Primele două, după cum sugerează și numele, folosesc o matrice pentru a reprezenta graficul, iar ultimele două folosesc o listă.

Copaci.

Arborele neordonat

Un copac ca obiect matematic este o abstractizare din unitățile omonime 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 copacii matematici cu rădăcina situată în partea de sus, adică toate ramurile „cresc” de sus în jos. Se știe că în natură nu este deloc așa.

Deoarece un arbore este în esență 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 acesta, iar din nodul rădăcină în sine puteți ajunge la oricare dintre nodul existent. arborele de vârfuri, care decurge din proprietatea de conectare 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 arbore are un singur strămoș, sau dacă este un nod rădăcină, 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.

Puteți efectua multe operații pe un arbore, cum ar fi găsirea de elemente, ș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 parcurgerea arborelui. Există mai multe metode de soluționare. Cele mai populare dintre ele sunt: bypass simetric, direct și invers. În timpul traversării înainte, nodurile strămoșilor sunt vizitate înaintea descendenților lor, iar în traversarea inversă, situația este inversată în mod corespunzător. Într-o traversare simetrică, subarborele arborelui principal sunt vizualizați pe rând.

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