Structură de date

De la Wikipedia, enciclopedia liberă.
Salt la navigare Salt la căutare

În informatică , o structură de date este o entitate utilizată pentru a organiza un set de date în memoria computerului și, în cele din urmă, pentru a le stoca într-o memorie de masă . Alegerea structurilor de date care trebuie utilizate este strict legată de cea a algoritmilor ; pentru aceasta, ele sunt adesea considerate împreună. De fapt, alegerea structurii datelor afectează inevitabil eficiența de calcul a algoritmilor care o manipulează.

Structura datelor este o metodă de organizare a datelor, deci este independentă de ceea ce este conținut de fapt. Fiecare limbaj de programare oferă instrumente, mai mult sau mai puțin sofisticate, pentru a defini structurile de date sau pentru a agrega date de tip omogen sau eterogen. Aceste instrumente sunt de obicei modulare.

Mai formal, limbile oferă un set predefinit de tipuri de date elementare, iar structurile de date sunt instrumente pentru construirea unor tipuri de date agregate mai complexe.

Operația de construcție a unei variabile de tip complex de date se numește „instanțiere” și poate avea loc atât în ​​timpul compilării programului ( timp de compilare ), cât și în timpul execuției acestuia ( runtime ).

Structurile de date diferă în primul rând pe baza operațiunilor care pot fi efectuate asupra acestora și a serviciilor oferite. Acest lucru permite studierea unei abstracții de la implementare.

Structuri de date abstracte

Pictogramă lupă mgx2.svg Același subiect în detaliu: tip de date abstract .

Vorbim despre structuri de date abstracte atunci când vrem să distingem structurile în sine de implementările lor; o structură abstractă de date poate fi implementată în moduri diferite în diferite limbaje de programare, sau chiar în același limbaj.

Constructori de structuri de date

Matrice sau vector

O matrice este o structură de date omogenă, care conține un număr finit de elemente toate de același tip, de exemplu un vector de 10 numere întregi. Aceste elemente sunt identificate printr-un index numeric, care variază de obicei de la 0 la numărul maxim de elemente minus unul. Dimensiunea vectorului trebuie declarată în momentul creării sale. Vectorii de diferite dimensiuni alcătuiesc diferite tipuri de date. Accesarea unui element dintr-o matrice are un cost de calcul constant, în timp ce adăugarea sau eliminarea elementelor în poziții aleatorii poate fi destul de costisitoare, de obicei apanajul matricelor dinamice .

Înregistrare sau structură

O înregistrare este o structură de date care poate fi eterogenă sau omogenă. În primul caz conține o combinație de elemente care pot fi de diferite tipuri, de exemplu un număr întreg, un număr în virgulă mobilă și un caracter text. Elementele care îl compun se numesc și câmpuri și sunt identificate printr-un nume.

Clasă

O clasă este o construcție tipică a limbajelor orientate obiect și constă dintr-o înregistrare căreia îi sunt asociate și operații sau metode .

Compoziția constructorilor

Acești constructori pot fi combinați în mod liber pentru a da naștere unor structuri mai complexe. De exemplu, este posibil să se reprezinte o matrice bidimensională de dimensiune ca vector de dimensiune având ca elemente ale vectorilor de lungime . Din nou, putem defini o matrice de cinci sute de elemente, fiecare dintre ele fiind o înregistrare formată din patru șiruri și doi vectori, fiecare conținând patru vectori de trei caractere.

Structurile de date obținute prin compunerea acestor constructori se mai numesc „statice”, deoarece ocuparea memoriei lor este definită în momentul compilării sau cel mult în momentul instanțierii. De exemplu: programul decide că are nevoie de o serie de 100 de elemente pentru a-și procesa datele și le alocă, adică angajează memoria necesară. Din acest moment, matricea va avea o dimensiune fixă, adică va fi întotdeauna compusă din 100 de elemente și va păstra ocupată memoria necesară până la terminarea programului sau când nu va fi distrus. Schimbarea lungimii matricei este posibilă, dar foarte costisitoare în ceea ce privește resursele de calcul și, prin urmare, este o operațiune evitată pe cât posibil (a se vedea tablourile dinamice ).

Limita structurilor de date statice constă în faptul că acestea sunt slab adaptate problemelor în care numărul de date care urmează a fi procesate nu este cunoscut a priori și / sau variază semnificativ în timpul executării programului.

Structuri dinamice de date

Structurile de date dinamice se bazează pe utilizarea datelor pointer și pe alocarea dinamică a memoriei . Elementele pot fi alocate (și alocate) după cum este necesar, legate între ele în moduri diferite, iar aceste legături se pot modifica ele însele în timpul executării programului. Spațiul de memorie necesar pentru a aloca pointeri și operațiunile necesare pentru a le menține, constituie costul suplimentar al structurilor dinamice de date.

În absența indicatorilor, este, de asemenea, posibil să construiți structuri dinamice de date folosind matrice, renunțând în același timp la flexibilitatea în utilizarea memoriei: o matrice de dimensiuni suficiente este alocată pentru a conține toate elementele pe care credeți că trebuie să le gestionați și, în schimb, indicii indicilor sunt folosiți în matrice.

Structurile dinamice de date se pot adapta pentru a reprezenta orice situație. Cele mai comune tipuri sunt prezentate aici.

Listă

Exemplu de listă

O listă este un set de „noduri” conectate liniar. Nodurile sunt înregistrări care conțin o „sarcină utilă” de date și un indicator către următorul articol din listă. Ordinea în care nodurile sunt conectate definește o ordine între ele. Un nod acționează ca capul listei și de aici este posibil să accesați toate nodurile din listă. Cunoscând un nod din listă, este posibil să accesați următoarele noduri, dar nu și cele anterioare.

Costul accesării unui nod din listă crește odată cu dimensiunea listei. Cunoscând nodul care precede un nod N, este posibil să eliminați N din listă sau să inserați un element înaintea acestuia, într-un timp constant.

Lista bidirecțională sau dublă legată

Lista bidirecțională

În acest caz, nodurile conțin un pointer către nodul anterior și următorul. Folosind sintaxa limbajului C , dat un nod N succesorul său este N->succ , iar precedentul său este N->prec . Trebuie să fie întotdeauna adevărat că N->succ->prec == N Fiecare nod vă permite să accesați toate elementele listei. Elementele „structurale” ale acestei structuri de date, adică cele două indicații conținute în fiecare nod, sunt redundante.

Copac

Exemplu de copac

Un copac este o reprezentare a arborelui în teoria graficelor .

Fiecare nod conține două (sau mai multe) indicii către alte noduri care sunt numite „copii” ai săi. Continuând în metaforă, dat un nod, este posibil să accesați toți descendenții săi. Un copac trebuie să fie lipsit de cicluri, adică un nod nu poate fi un descendent al său, adică nu trebuie să fie posibil să porniți de la un nod, să urmați indicatorii către copii și să reveniți la nodul de pornire. Mai mult, fiecare nod trebuie să fie copilul unui singur tată.

În unele implementări, fiecare nod conține, de asemenea, o legătură cu „tatăl” său, clar distinct de cele către copiii săi.

De obicei, există o relație de ordine între copiii unui nod, definită de ordinea indicatorilor din părinte.

În multe implementări, fiecare nod are un număr fix de copii, cum ar fi doi sau trei. În acest caz vorbim de copaci binari sau ternari. În alte cazuri, numărul copiilor unui nod este arbitrar; acest lucru poate fi gestionat prin stocarea copiilor unui nod într-o listă a unuia dintre tipurile descrise mai sus.

Fiecare nod, în plus față de indicatoarele către nodurile copil, are în mod normal o „sarcină utilă”, adică o bucată de date asociată cu nodul, utilă pentru rezolvarea problemei aplicației.

Copacii se pretează foarte bine la reprezentarea formulelor matematice.

Arborii binari ordonați

Pictogramă lupă mgx2.svg Același subiect în detaliu: Arborele de căutare binară .

Când datele au o relație de ordine totală, ele pot fi reprezentate în mod convenabil în structura arborelui binar.

De exemplu, putem adopta convenția că un nod N se află în subarborele stâng M dacă și numai dacă N < M , altfel N se află în subarborele drept al lui M Un copac cu această proprietate este numit un arbore binar de căutare (BST). În acest fel, căutarea unui element într-un arbore echilibrat ordonat necesită un timp proporțional cu înălțimea arborelui, care în cel mai bun caz este proporțional cu logaritmul numărului de elemente, în timp ce inserarea unui element într-un arbore ordonat arborele necesită, de asemenea, respectarea proprietății de sortare descrise anterior. În funcție de ordinea inserțiilor, arborele se poate dezechilibra și, prin urmare, poate avea frunze la adâncimi foarte diferite una de cealaltă, provocând ineficiențe în căutare. Prin urmare, uneori este necesar ca structura de date să fie echipată și să fie supusă unei operații de echilibrare forțată care să minimizeze înălțimea arborelui.

Grafic

Graficul este o generalizare a arborelui. Fiecare nod are un număr arbitrar de noduri „învecinate” și poate conține bucle. În general, o sarcină utilă poate fi asociată atât cu nodurile, cât și cu legăturile dintre ele.

Masă Hash

Un tabel hash este o structură de date care este utilă pentru căutarea rapidă a unui element dintr-un set bazat pe o cheie, adică un subset al caracteristicilor elementului. Se calculează un hash cheie pentru fiecare element de stocat. O matrice este apoi construită, indexată de valoarea hash, ca elemente de pointer la liste de noduri care se potrivesc cu această valoare hash. Dacă funcția hash este bine aleasă, statistic listele vor avea lungimi echilibrate.

Pentru a căuta un element, se calculează valoarea lui hash, se selectează elementul matrice corespunzător și se derulează prin listă până când este găsit.

Containere

Structurile de date descrise mai sus pot fi utilizate pentru a crea unele tipuri de containere de utilizare frecventă, care pot forța un anumit mod de acces la date.

Stivă sau stivă

O stivă este o structură de date LIFO ( Last In First Out ). Se face de obicei cu tablouri sau liste.

Coadă

O coadă este o structură de date FIFO ( First In First Out ). Se face de obicei cu tablouri sau liste.

Matrice asociativă

Este o structură de date găsită în multe limbaje de scriptare . Se compune dintr-un tablou, ale cărui elemente sunt identificate totuși printr-o cheie de tip arbitrar, mai degrabă decât printr-un index numeric. Pentru a accesa un element, cheia acestuia este plasată de obicei între paranteze drepte, în locul indexului. Dacă nu există niciun element cu cheia respectivă, veți primi o eroare sau o valoare convențională.

Șabloane de structură a datelor

Implementarea manuală a structurilor dinamice de date este o sarcină repetitivă, predispusă la erori. Din acest motiv, s-au folosit diverse metode pentru a separa definiția structurilor de date de utilizarea lor în algoritmi .

Unele limbi oferă instrumentul șablon , care vă permite să scrieți funcții sau clase parametrice în ceea ce privește tipul de argumente sau unii membri ai clasei care pot fi utilizați în mod normal.

Un șablon este instanțiat prin specificarea tipului de argumente ale funcției sau a membrilor clasei nespecificați în definiție, construind o funcție sau o clasă.

În acest fel, este posibil să scrieți o clasă de listă generică în ceea ce privește conținutul, cu metodele necesare pentru a manipula o listă și apoi să o utilizați pentru a gestiona atât listele de numere întregi, cât și listele de obiecte complexe.

STL și Generics

Un efort important de a construi o bibliotecă de structuri de date generice în ceea ce privește tipul de date stocate este Biblioteca de șabloane standard (a se vedea STL pe site-ul web SGI ), bazată pe conceptul de a furniza un instrument pentru a compune ortogonal date, containere (structuri de date ) și algoritmi . În STL, un instrument important pentru conectarea structurilor și algoritmilor de date într-un mod generic sunt iteratorii , o generalizare a pointerilor.

STL este o bibliotecă de clase C ++ .

Limbajul Java , pe de altă parte, are două modalități de a gestiona structurile de date fundamentale prezente în limbaj. Până la versiunea 1.4, gestionarea containerelor se făcea cu moștenire în loc de șabloane. De aceea, containerele conțin obiecte de tipul „Obiect”, un tip din care descind toate clasele definite în Java; În consecință, în Java nu este la fel de ușor să vă asigurați că toate obiectele plasate într-un container aparțin unui anumit tip. De la versiunea 1.5, au fost introduse generice , care se comportă foarte similar cu șabloanele C ++ și rezolvă multe dintre problemele legate de turnarea superioară a containerelor „vechi”.

Elemente conexe

Alte proiecte

linkuri externe

Controlul autorității Tezaur BNCF 63819 · LCCN (EN) sh85035862 · GND (DE) 4011146-5 · BNF (FR) cb119313298 (dată) · NDL (EN, JA) 01.167.757
Informatică Portal IT : accesați intrările Wikipedia care se ocupă cu IT