Meniu

Introducere în structurile de date în C ++

introduction data structures c

Încercați Instrumentul Nostru Pentru Eliminarea Problemelor

Un tutorial introductiv privind structurile de date în C ++.

„Structura datelor poate fi definită ca o colecție organizată de date care ajută un program să acceseze datele eficient și rapid, astfel încât întregul program să poată funcționa într-un mod eficient. „

Știm că în lumea programării, datele sunt centrul și totul se învârte în jurul datelor. Trebuie să facem toate operațiunile de date, inclusiv stocarea, căutarea, sortarea, organizarea și accesarea datelor în mod eficient și numai atunci programul nostru poate avea succes.

=> Consultați aici pentru a explora lista completă de tutoriale C ++.

Introducere în structurile de date în C ++ (1)

Ce veți învăța:

Prezentare generală

Trebuie să găsim cel mai eficient mod de stocare a datelor care ne poate ajuta să construim soluții dinamice. Structura datelor ne ajută să construim astfel de soluții.

În timp ce organizăm sau aranjăm datele în structuri, trebuie să ne asigurăm că aranjamentul reprezintă aproape un obiect din lumea reală. În al doilea rând, acest aranjament ar trebui să fie suficient de simplu, astfel încât oricine să îl poată accesa cu ușurință și să-l proceseze ori de câte ori este necesar.

În această serie, vom învăța în detaliu despre structura de date de bază, precum și despre o structură avansată. De asemenea, vom afla în detaliu despre diverse tehnici de căutare și sortare care pot fi efectuate pe structuri de date.

După ce a învățat această serie de tutoriale, cititorul ar trebui să cunoască bine fiecare structură de date și programarea acesteia.

Să parcurgem câțiva dintre termenii pe care îi folosim atunci când ne ocupăm de structurile de date:

De exemplu,ia un anumit student. Un student poate avea următoarele detalii, așa cum sunt reprezentate pictural.

Exemplu - Structura datelor

  • Date: Este valoarea elementară. În figura de mai sus, numărul nr. De student poate fi date.
  • Element de grup: Acesta este elementul de date care are mai multe sub-elemente. În figura de mai sus, Student_name are prenume și prenume.
  • Record: Este o colecție de elemente de date. În exemplul de mai sus, elementele de date, cum ar fi numărul listei elevului, numele, clasa, vârsta, clasa etc. formează împreună o înregistrare.
  • Entitate: Este o clasă de înregistrări. În diagrama de mai sus, studentul este o entitate.
  • Atribut sau câmp: Proprietățile unei entități se numesc atribute și fiecare câmp reprezintă un atribut.
  • Fişier: Un fișier este o colecție de înregistrări. În exemplul de mai sus, o entitate studentă poate avea mii de înregistrări. Astfel, un fișier va conține toate aceste înregistrări.

Cititorul ar trebui să fie conștient de toți acești termeni, pe măsură ce îi folosim din când în când când folosim diferite structuri de date.

Structurile de date sunt elementul principal al programului și, în calitate de programatori, ar trebui să fim atenți la structura de date de utilizat. Structura exactă a datelor care trebuie utilizată este cea mai dificilă decizie de luat în ceea ce privește programarea.

Să discutăm despre necesitatea structurii datelor în programare.

Necesitatea structurii datelor în programare

Pe măsură ce cantitatea de date continuă să crească, aplicațiile devin din ce în ce mai complexe, prin urmare devine dificil pentru programator să gestioneze aceste date, precum și software-ul.

De obicei, în orice moment, aplicația poate întâmpina următoarele obstacole:

# 1) Căutarea unor cantități mari de date: Cu o cantitate mare de date procesate și stocate, programul nostru poate fi solicitat în orice moment să caute anumite date. Dacă datele sunt prea mari și nu sunt organizate corect, va dura mult timp pentru a obține datele necesare.

Atunci când folosim structuri de date pentru a stoca și organiza date, recuperarea datelor devine mai rapidă și mai ușoară.

# 2) Viteza de procesare: Datele dezorganizate pot duce la o viteză de procesare lentă, deoarece se va pierde mult timp în recuperarea și accesarea datelor.

Dacă organizăm datele corect într-o structură de date în timp ce stocăm, atunci nu vom pierde timpul în activități precum recuperarea, organizarea lor de fiecare dată. În schimb, ne putem concentra asupra procesării datelor pentru a produce rezultatul dorit.

# 3) Mai multe cereri simultane: Multe aplicații din zilele noastre trebuie să facă o cerere simultană de date. Aceste cereri ar trebui procesate eficient pentru ca aplicațiile să ruleze fără probleme.

Dacă datele noastre sunt stocate în mod aleatoriu, atunci nu vom putea procesa simultan toate solicitările simultane. Deci, este o decizie înțeleaptă să aranjați datele într-o structură adecvată a datelor, astfel încât să reduceți la minim timpul de răspuns al solicitărilor.

Clasificarea structurii datelor

Structurile de date utilizate în C ++ pot fi clasificate după cum urmează.

Clasificarea structurilor de date

O structură de date este un mod de organizare a datelor. Deci putem clasifica structurile de date așa cum se arată în structuri de date primitive sau standard și structuri de date neprimitive sau definite de utilizator.

Am văzut toate tipurile de date acceptate în C ++. Deoarece acesta este și un mod de organizare a datelor, spunem că este o structură standard de date.

Celelalte structuri de date sunt neprimitive și utilizatorul trebuie să le definească înainte de a le utiliza într-un program. Aceste structuri de date definite de utilizator sunt clasificate în continuare în structuri de date liniare și neliniare.

Structura de date liniare

Structurile de date liniare au toate elementele lor dispuse în mod liniar sau secvențial. Fiecare element dintr-o structură de date liniară are un predecesor (elementul anterior) și un succesor (elementul următor)

Structurile de date liniare sunt împărțite în continuare în structuri de date statice și dinamice. Structurile de date statice au de obicei o dimensiune fixă ​​și, odată ce dimensiunea lor este declarată la momentul compilării, nu poate fi modificată. Structurile dinamice de date își pot schimba dimensiunea dinamic și se pot acomoda.

Cel mai popular exemplu de structură de date statice liniare este o matrice.

Matrice

O matrice este o colecție secvențială de elemente de același tip. Fiecare element al tabloului poate fi accesat folosind poziția sa în tabloul numit index sau indice al tabloului. Numele matricei indică primul element din matrice.

matrice

Cel de mai sus este un tablou „a” de n elemente. Elementele sunt numerotate de la 0 la n-1. Dimensiunea matricei (n în acest caz) se mai numește și dimensiunea matricei. Așa cum se arată în figura de mai sus, numele matricei indică primul element al matricei.

Matricea este cea mai simplă structură de date și este eficientă, deoarece elementele pot fi accesate folosind direct indicii. Dacă dorim să accesăm al treilea element din matrice, trebuie doar să spunem un (2).

Dar adăugarea sau ștergerea elementelor matrice este dificilă. Prin urmare, folosim matrici numai în aplicații simple sau în aplicații în care nu este necesară adăugarea / ștergerea elementelor.

Structurile de date dinamice liniare populare sunt listate, stivuite și la coadă.

Listă legată

O listă legată este o colecție de noduri. Fiecare nod conține elementul de date și un pointer către nodul următor. Nodurile pot fi adăugate și șterse dinamic. O listă legată poate fi o listă legată individual, în care fiecare nod are un indicator doar către următorul element. Pentru ultimul element, următorul indicator este setat la nul.

În lista dublu legată, fiecare nod are două indicatoare, unul către nodul anterior și cel de-al doilea către nodul următor. Pentru primul nod, indicatorul anterior este nul și pentru ultimul nod, următorul indicator este nul.

Listă legată

Așa cum se arată în figura de mai sus, începutul listei se numește cap, în timp ce sfârșitul listei conectate se numește coadă. După cum se arată mai sus, fiecare nod are un pointer către următorul element. Putem adăuga sau șterge cu ușurință elemente schimbând indicatorul la următorul nod.

Grămadă

Stiva este o structură de date liniară în care elementele pot fi adăugate sau îndepărtate numai dintr-un capăt cunoscut sub numele de „Sus” al stivei. În acest fel, stiva prezintă tipul de acces la memorie LIFO (Last In, First Out).

Grămadă

Așa cum se arată mai sus, elementele din stivă sunt întotdeauna adăugate la un capăt și, de asemenea, eliminate din același capăt. Aceasta se numește „partea de sus” a stivei. Când se adaugă un element, acesta este împins în jos în stivă și partea de sus a stivei este incrementată cu o poziție.

În mod similar, atunci când un element este eliminat, partea de sus a stivei este decrementată. Când o stivă este goală, partea de sus a stivei este setată la -1. Există două operații principale „Push” și „Pop” care se efectuează pe stivă.

Coadă

Coada este încă o altă structură de date liniară în care elementele sunt adăugate la un capăt numit „spate” și șterse de la un alt capăt numit „față”. Coada demonstrează FIFO (First In, First Out) tipul metodologiei de acces la memorie.

Coadă

Diagrama de mai sus arată o coadă cu capetele din spate și din față. Când coada este goală, indicatoarele din spate și din față coincid între ele.

Structură de date neliniară

În structurile de date neliniare, datele nu sunt aranjate secvențial, ci sunt aranjate într-un mod neliniar. Elementele sunt conectate între ele într-un aranjament neliniar.

Structurile de date neliniare sunt Arborii și Graficele.

care este cel mai bun software de recunoaștere a vocii

Copaci

Arborii sunt structuri de date multi-nivel neliniare care au o relație ierarhică între elemente. Elementele arborelui se numesc Noduri.

Nodul din partea de sus se numește rădăcina arborelui. Rădăcina poate avea unul sau mai multe noduri copil. Nodurile ulterioare pot avea, de asemenea, unul sau mai multe noduri copil. Nodurile care nu au noduri copil se numesc noduri frunze.

Copaci

În diagrama de mai sus, am arătat un arbore cu 6 noduri. Dintre aceste trei noduri se află nodurile frunze, unul dintre nodurile de sus este rădăcina și celelalte sunt noduri copil. În funcție de numărul de noduri, noduri copil etc. sau de relația dintre noduri, avem diferite tipuri de copaci.

Grafice

Graficul este un set de noduri numit vârfuri conectate între ele prin intermediul link-urilor numite Margini . Graficele pot avea un ciclu în interior, adică același vârf poate fi un punct de plecare, precum și punctul final al unei anumite căi. Copacii nu pot avea niciodată un ciclu.

Grafice

Diagrama de mai sus este un grafic nedirecționat. De asemenea, putem avea grafice direcționate unde reprezentăm marginile folosind săgeți direcționate.

Operațiuni privind structura datelor

Toate structurile de date efectuează diverse operații asupra elementelor sale.

Acestea sunt comune tuturor structurilor de date și sunt listate după cum urmează:

  • In cautarea: Această operație este efectuată pentru a căuta un anumit element sau o cheie. Cei mai comuni algoritmi de căutare sunt căutarea secvențială / liniară și căutarea binară.
  • Triere: Operația de sortare presupune aranjarea elementelor dintr-o structură de date într-o anumită ordine fie crescătoare, fie descendentă. Există diferiți algoritmi de sortare care sunt disponibili pentru structurile de date. Cele mai populare dintre ele sunt Quicksort, Selection sort, Merge sort etc.
  • Inserare: Operația de inserare se referă la adăugarea unui element în structura datelor. Aceasta este cea mai importantă operație și, ca urmare a adăugării unui element, aranjamentul se schimbă și trebuie să avem grijă ca structura datelor să rămână intactă.
  • Ștergere: Operația de ștergere elimină un element din structura datelor. Aceleași condiții care trebuie luate în considerare pentru inserare trebuie îndeplinite și în cazul operațiunii de ștergere.
  • Traversare: Spunem că traversăm o structură de date atunci când vizităm fiecare element din structură. Traversarea este necesară pentru a efectua anumite operațiuni specifice asupra structurii datelor.

În subiectele noastre ulterioare, vom învăța mai întâi diferitele tehnici de căutare și sortare care trebuie efectuate pe structuri de date.

Avantajele structurii datelor

  • Abstracție: Structurile de date sunt adesea implementate ca tipuri de date abstracte. Utilizatorii accesează doar interfața sa externă fără să se îngrijoreze de implementarea de bază. Astfel, structura datelor oferă un strat de abstractizare.
  • Eficienţă: Organizarea corectă a datelor are ca rezultat accesul eficient al datelor, făcând astfel programele mai eficiente. În al doilea rând, putem selecta structura corectă a datelor în funcție de cerințele noastre.
  • Reutilizare: Putem refolosi structurile de date pe care le-am proiectat. Ele pot fi compilate și într-o bibliotecă și distribuite clientului.

Concluzie

Cu aceasta, încheiem acest tutorial privind introducerea structurilor de date. Am introdus pe scurt fiecare dintre structurile de date în acest tutorial.

În tutorialele noastre ulterioare, vom explora mai multe despre structurile de date împreună cu diversele tehnici de căutare și sortare.

=> Faceți clic aici pentru seria Absolute C ++ Training.

Lectură recomandată

^