Ce sunt structurile de date în C și cum să le folosești?

Introducere

Pentru început, o structură de date este o colecție de elemente de date care sunt păstrate împreună sub un singur nume sau titlu și este un mod specific de stocare și asamblare a datelor, astfel încât datele să poată fi utilizate eficient.

Tipuri

Structurile de date sunt predominante și utilizate în aproape fiecare sistem software. Unele dintre cele mai comune exemple de structuri de date sunt matrice, cozi, stive, liste legate și arbori.

Aplicații

În proiectarea compilatoarelor, sistemelor de operare, realizarea bazelor de date, aplicații de inteligență artificială și multe altele.

Clasificare

Structurile de date sunt clasificate în două categorii: structuri de date primitive și structuri de date neprimitive.

1. Primitive: Sunt tipurile de date de bază care sunt suportate de un limbaj de programare. Un exemplu comun al acestei clasificări sunt numerele întregi, caractere și boolean.

2. Non-Primitive: Aceste categorii de structuri de date sunt create folosind structuri de date primitive. Exemplele includ stive legate, liste legate, grafice și arbori.

Matrice

O matrice este o simplă colecție de elemente de date care au același tip de date. Aceasta înseamnă că o matrice de numere întregi de tip poate stoca numai valori întregi. O matrice de date de tip float poate stoca valori care corespund tipului de date float și nimic altceva.

Elementele stocate într-o matrice sunt accesibile liniar și sunt prezente în blocuri adiacente de memorie la care se poate face referire folosind un index.

Declararea unui Array

În C, o matrice poate fi declarată ca:

tipul_date nume[lungime];

De exemplu,

int ordine[10];

Linia de cod de mai sus creează o matrice de 10 blocuri de memorie în care poate fi stocată o valoare întreagă. În C, valoarea indexului matricei începe de la 0. Deci valorile indexului vor varia de la 0 la 9. Dacă vrem să accesăm orice valoare anume din acea matrice, trebuie pur și simplu să tastam:

printf(comanda[numar_index]);

O altă modalitate de a declara o matrice este următoarea:

data_type array_name[size]={lista de valori};

De exemplu,

int marks[5]={9, 8, 7, 9, 8};

Linia de comandă de mai sus creează o matrice având 5 blocuri de memorie cu valori fixe în fiecare dintre blocuri. Pe un compilator de 32 de biți, memoria de 32 de biți ocupată de tipul de date int este de 4 octeți. Deci, 5 blocuri de memorie ar ocupa 20 de octeți de memorie.

Un alt mod legitim de a inițializa matrice este:

int semne [5] = {9 , 45};

Această comandă va crea o matrice de 5 blocuri, ultimele 3 blocuri având 0 ca valoare.

O altă modalitate legitimă este:

int semne [] = {9 , 5, 2, 1, 3,4};

Compilatorul C înțelege că sunt necesare doar 5 blocuri pentru a încadra aceste date într-o matrice. Prin urmare, va inițializa o serie de mărci de nume de dimensiunea 5.

În mod similar, o matrice 2-D poate fi inițializată în felul următor

int marks[2][3]={{9,7,7},{6, 2, 1}};

Comanda de mai sus va crea o matrice 2-D având 2 rânduri și 3 coloane.

Citiți: Idei și subiecte de proiect pentru structura datelor

Operațiuni

Există unele operații care pot fi efectuate pe matrice. De exemplu:

1. traversând o matrice
2. Inserarea unui element în matrice
3. Căutarea unui anumit element din matrice
4. Ștergerea unui anumit element din matrice
5. Îmbinând cele două matrice și,
6. Sortarea matricei — în ordine crescătoare sau descrescătoare.

Dezavantaje

Memoria alocată matricei este fixă. Aceasta este de fapt o problemă. Să spunem, am creat o matrice de dimensiunea 50 și am accesat doar 30 de blocuri de memorie. Cele 20 de blocuri rămase ocupă memorie fără nicio utilizare. Prin urmare, pentru a rezolva această problemă, avem o listă legată.

Lista legată

Linked List, la fel ca matricele stochează datele în serie. Principala diferență este că nu stochează totul dintr-o dată. În schimb, stochează datele sau pune la dispoziție un bloc de memorie atunci când este necesar. Într-o listă legată, blocurile sunt împărțite în două părți. Prima parte conține datele reale.

A doua parte este un indicator care indică următorul bloc dintr-o listă legată. Pointerul stochează adresa următorului bloc care deține datele. Mai există un indicator cunoscut sub numele de indicator de cap. head indică primul bloc de memorie din lista legată. În continuare este reprezentarea listei legate. Aceste blocuri sunt denumite și „noduri”.

sursă

Inițializarea listelor conectate

Pentru a inițializa lista de linkuri, creăm un nod de nume de structură. Structura are două lucruri. 1. Datele pe care le deține și 2. Pointerul care indică următorul nod. Tipul de date al pointerului va fi cel al structurii, deoarece indică către nodul structurii.

nodul struct

{

int date;

struct node *next;

};

Într-o listă legată, indicatorul ultimului nod nu va indica nimic sau, pur și simplu, va indica nul.

Citește și: Grafice în structura datelor

Traversarea listelor conectate

Într-o listă legată, indicatorul ultimului nod nu va indica nimic sau, pur și simplu, va indica nul. Așadar, pentru a parcurge o întreagă listă legată, creăm un indicator fals care indică inițial către cap. Și, pentru lungimea listei legate, indicatorul continuă să se deplaseze înainte până când indică spre null sau ajunge la ultimul nod al listei legate.

Adăugarea unui Nod

Algoritmul pentru adăugarea unui nod înaintea unui anumit nod ar fi următorul:

1. setați două indicatori inactiv (ptr și preptr) care să se îndrepte inițial
2. mutați ptr până când ptr.data este egal cu datele înainte de a intenționa să inserăm nodul. preptr va fi cu 1 nod în spatele ptr.
3. Creați un nod
4. Nodul către care indica preptr-ul fals, următorul nod va indica acest nou nod
5. Următorul nod va indica ptr.

Algoritmul pentru adăugarea unui nod după o anumită dată ar fi făcut într-un mod similar.

Avantajele listei conectate

1. Dimensiune dinamică, spre deosebire de o matrice
2. Efectuarea inserării și ștergerii este mai ușoară în lista legată decât într-o matrice.

Coadă

Coada urmează un sistem de tip First In First Out sau FIFO. Într-o implementare a matricei, vom avea doi pointeri pentru a demonstra cazul de utilizare a Queue.

Sursă

FIFO înseamnă practic că valoarea care intră prima în stivă, părăsește mai întâi matricea. În diagrama cozii de mai sus, frontul indicatorului indică valoarea 7. Dacă ștergem primul bloc (decodare), frontul va indica acum valoarea 2. În mod similar, dacă introducem un număr (în coada), să spunem, 3 în poziția 5. Apoi, indicatorul din spate va indica poziția 5.

Condiții de depășire și sub debit

Cu toate acestea, înainte de a introduce o valoare de date în coadă, trebuie să verificăm condițiile de depășire. O depășire va avea loc atunci când există o încercare de inserare a unui element într-o coadă care este deja plină. O coadă se va umple când spate = max_size–1.

De asemenea, înainte de a șterge datele din coadă, ar trebui să verificăm dacă există condiții de subflow. Un underflow va apărea atunci când există o încercare de a șterge un element dintr-o coadă care este deja goală, adică dacă front = null și rear = null, atunci coada este goală.

Grămadă

O stivă este o structură de date în care inserăm și ștergem elemente doar la un capăt, cunoscut și sub numele de vârful stivei. Prin urmare, implementarea stivei este denumită implementare last-in, first-out (LIFO). Spre deosebire de coadă, pentru stivă, avem nevoie doar de un indicator de sus.

Dacă vrem să introducem (împinge) elemente într-o matrice, indicatorul de sus se mișcă în sus sau crește cu 1. Dacă dorim să ștergem (pop) un element, indicatorul de sus scade cu 1 sau coboară cu 1 unitate. O stivă acceptă trei operațiuni de bază: push, pop și peep. Operația Peep este pur și simplu afișarea elementului cel mai de sus din stivă.

Sursă

Învață cursuri de software online de la cele mai bune universități din lume. Câștigă programe Executive PG, programe avansate de certificat sau programe de master pentru a-ți accelera cariera.

Concluzie

În acest articol, am vorbit despre 4 tipuri de structuri de date și anume, matrice, liste legate, cozi și stive. Sper că ți-a plăcut acest articol și rămâi pe fază pentru lecturi mai interesante. Pana data viitoare.

Dacă sunteți interesat să aflați mai multe despre Javascript, dezvoltarea full-stack, consultați programul Executive PG de la upGrad și IIIT-B în dezvoltarea software full-stack, care este conceput pentru profesioniști care lucrează și oferă peste 500 de ore de formare riguroasă, peste 9 proiecte , și misiuni, statutul de absolvenți IIIT-B, proiecte practice practice și asistență pentru locuri de muncă cu firme de top.