Practic, o matrice este un set de obiecte de date similare stocate în locații de memorie secvențială sub o poziție comună sau un nume de variabilă.
În timp ce o listă legată este o structură de date care conține o secvență a elementelor în care fiecare element este legat de elementul său următor. Există două câmpuri într-un element al listei legate. Unul este câmpul Date, iar altul este câmpul de legături. Câmpul Date conține valoarea reală care trebuie stocată și procesată. În plus, câmpul de legături deține adresa următorului element de date din lista conectată. Adresa folosită pentru a accesa un anumit nod este cunoscută ca un pointer.
O altă diferență semnificativă între o matrice și o listă legată este aceea că Array are o dimensiune fixă și trebuie să fie declarat anterior, dar Linked List nu se limitează la mărime și se extinde și contract în timpul execuției.
Diagramă de comparație
| Bazele comparației | mulțime | Lista conectată |
|---|---|---|
| De bază | Este un set consistent al unui număr fix de elemente de date. | Este un set ordonat care cuprinde un număr variabil de elemente de date. |
| mărimea | Specificate în timpul declarației. | Nu este nevoie să specificați; să crească și să se micșoreze în timpul execuției. |
| Alocarea depozitului | Locația elementului este alocată în timpul procesului de compilare. | Poziția elementului este atribuită în timpul executării. |
| Ordinea elementelor | Stocate consecutiv | Stocate la întâmplare |
| Accesarea elementului | Accesat direct sau la întâmplare, adică specificați indicele sau indicele matricei. | Accesat secvențial, adică Traverse pornind de la primul nod din listă de pointer. |
| Inserarea și ștergerea elementului | Slow relativ ca schimbarea este necesar. | Mai ușor, rapid și eficient. |
| In cautarea | Căutarea binară și căutarea liniară | căutare liniară |
| Memorie necesară | Mai puțin | Mai Mult |
| Utilizarea memoriei | ineficace | Eficient |
Definiția Array
O matrice este definită ca un set al unui număr determinat de elemente omogene sau elemente de date. Aceasta înseamnă că o matrice poate conține numai un singur tip de date, fie toate numerele întregi, toate numerele cu puncte variabile sau toate caracterele. Declarația unei matrice este după cum urmează:
int a [10];
Unde int specifică tipul de date sau stochează elementele de stocare a elementelor. "A" este numele unei matrice, iar numărul specificat în paranteze pătrate este numărul de elemente pe care un array le poate stoca, aceasta se numește și dimensiunea sau lungimea matricei.
Să ne uităm la câteva dintre conceptele care trebuie reamintite despre matrice:
- Elementele individuale ale unei matrice pot fi accesate prin descrierea numelui matricei, urmată de index sau index (determinând locația elementului din matrice) în parantezele pătrate. De exemplu, pentru a prelua al 5-lea element al matricei, trebuie să scriem o declarație a [4].
- În orice caz, elementele unei matrice vor fi stocate într-o locație de memorie consecutivă.
- Primul element al matricei are indice zero [0]. Înseamnă că primul și ultimul element vor fi specificate ca [0] și, respectiv, [9].
- Numărul de elemente care pot fi stocate într-o matrice, adică dimensiunea unei matrice sau lungimea acesteia, este dată de următoarea ecuație:
(limita superioară-limita inferioară) + 1
Pentru matricea de mai sus, ar fi (9-0) + 1 = 10. Unde 0 este limita inferioară a matricei și 9 este limita superioară a matricei. - Array-urile pot fi citite sau scrise prin bucla. Dacă citim matricea unidimensională, aceasta necesită o buclă pentru citire și una pentru scrierea (tipărirea) matricei, de exemplu:
A. Pentru citirea unui tablou
pentru (i = 0; i <= 9; i ++)
{scanf ("% d", & a [i]); }
b. Pentru scrierea unui tablou
pentru (i = 0; i <= 9; i ++)
{printf ("% d", a [i]); } - În cazul unei matrice 2-D, ar fi nevoie de două bucle și o matrice n-dimensională similară ar avea nevoie de n bucle.
Operațiile efectuate pe mese sunt:
- Crearea matricei
- Traversând o matrice
- Introducerea de elemente noi
- Ștergerea elementelor necesare.
- Modificarea unui element.
- Îmbinarea matricelor
Exemplu
Următorul program ilustrează citirea și scrierea matricei.
#include #include void main () { int a[10], i; printf("Enter the array"); for ( i= 0; i <= 9; i++) { scanf ( "%d", &a[ i ] ) ; } printf( "Enter the array" ); for (i = 0 ; i <= 9 ; i++) { printf ( "%d\n", a[ i ] ) ; } getch (); }
Definiția Linked List
O listă asociată este o listă specială a unor elemente de date legate una de cealaltă. În acest element fiecare element indică elementul următor care reprezintă ordinea logică. Fiecare element este numit un nod, care are două părți.
Partea INFO care stochează informațiile și POINTER care indică următorul element. După cum știți pentru stocarea adresei, avem o structură de date unică în C numită pointeri. Prin urmare, al doilea câmp al listei trebuie să fie un tip de pointer.
Tipurile de liste legate sunt listate în mod unic, listă dublată, listă circulară, listă circulară dublu legată.
Operațiile efectuate pe Lista conectată sunt:
- Creare
- Traversarea
- inserare
- ștergere
- In cautarea
- înlănțuire
- Afişa
Exemplu
Fragmentul următor ilustrează crearea unei liste asociate:
struct node { int num; stuct node *next; } start = NULL; void create() { typedef struct node NODE; NODE *p, *q; char choice; first = NULL; do { p = (NODE *) malloc (sizeof (NODE)); printf ("Enter the data item\n"); scanf ("%d", & p -> num); if (p == NULL) { q = start; while (q -> next ! = NULL) { q = q -> next } p -> next = q -> next; q -> = p; } else { p -> next = start; start = p; } printf ("Do you want to continue (type y or n) ? \n"); scanf ("%c", &choice) ; } while ((choice == 'y') || (choice == 'Y')); }
Diferențe cheie între matrice și lista conectată
- O matrice este structura de date care conține o colecție de elemente de date similare de tip, în timp ce lista legată este considerată ca structură de date non-primitivă conține o colecție de elemente legate neordonate cunoscute sub numele de noduri.
- În matrice elementele aparțin indiciilor, adică dacă doriți să ajungeți în cel de-al patrulea element, trebuie să scrieți numele variabilei cu indexul sau locația sa în brațul plat.
Într-o listă legată, totuși, trebuie să porniți de la cap și să vă deplasați până când ajungeți la al patrulea element. - În timp ce accesați o matrice de elemente este rapidă în timp ce lista legată are timp liniar, este destul de încet.
- Operații precum introducerea și ștergerea în mese consumă o mulțime de timp. Pe de altă parte, performanța acestor operațiuni în listele asociate este rapidă.
- Arrays sunt de dimensiuni fixe. În schimb, listele legate sunt dinamice și flexibile și se pot extinde și contracta dimensiunile sale.
- Într-o matrice, memoria este atribuită în timpul procesului de compilare în timp ce se află într-o listă asociată, este alocată în timpul execuției sau runtime-ului.
- Elementele sunt stocate consecutiv în tablouri, în timp ce ele sunt stocate aleator în listele legate.
- Cerința de memorie este mai mică datorită datelor reale stocate în indexul din matrice. În schimb, este nevoie de mai multă memorie în Listele asociate datorită stocării elementelor de referință suplimentare și anterioare.
- În plus, utilizarea memoriei este ineficientă în matrice. Dimpotrivă, utilizarea memoriei este eficientă în matrice.
Concluzie
Array și listele legate sunt tipurile de structuri de date care diferă în ceea ce privește structura, metodele de accesare și manipulare, cerința de memorie și utilizarea. Și au un avantaj și un dezavantaj deosebit față de punerea sa în aplicare. În consecință, oricare dintre acestea poate fi folosit ca pe nevoie.
