Matrice (tip de date)

O matrice este o structură de date care stochează un set de valori (elemente de matrice) identificate printr-un index sau un set de indici care preiau valori întregi (sau convertibile) dintr-un interval continuu dat. O matrice unidimensională poate fi gândită ca o implementare a unui tip de date abstracte, un vector. În unele limbaje de programare, un tablou poate fi numit și un tabel, un rând, un vector, o matrice.

Dimensiunea unui tablou este numărul de indici necesari pentru a adresa în mod unic un element din matrice [1] . După numărul de indici utilizați, tablourile sunt împărțite în unidimensionale, bidimensionale, tridimensionale etc.

Forma sau structura matricei - informații despre numărul de dimensiuni și dimensiunea (lungimea) matricei pentru fiecare dintre dimensiuni [2] ; poate fi reprezentat printr-o matrice unidimensională [3] .

O caracteristică a unui tablou ca structură de date (spre deosebire de, de exemplu, o listă legată ) este complexitatea computațională constantă a accesării unui element de matrice prin index [4] . Array se referă la structurile de date cu acces aleatoriu .

În cel mai simplu caz, o matrice are o lungime constantă în toate dimensiunile și poate stoca doar date de un tip specificat în descriere. Un număr de limbi acceptă, de asemenea, matrice dinamice , a căror lungime se poate modifica în timpul execuției programului, și matrice eterogene , care pot stoca date de diferite tipuri în diferite elemente. Unele tipuri de matrice specifice utilizate în diferite limbi și implementări sunt matrice asociativă , arbore de segmente , listă V , matrice paralelă , matrice dispersă .

Principalele avantaje ale utilizării tablourilor sunt ușurința de a calcula adresa unui element după indexul său (deoarece elementele matricei sunt situate una după alta), același timp de acces la toate elementele, dimensiunea redusă a elementelor (ele constau doar dintr-un câmp informativ). Printre dezavantaje se numără incapacitatea de a elimina sau adăuga un element fără a-i muta pe alții atunci când se utilizează rețele statice și, atunci când se utilizează rețele dinamice și eterogene, performanța mai lentă din cauza supraîncărcării menținerii dinamicii și eterogenității. Când lucrați cu matrice cu o implementare C (cu pointeri) și fără controale suplimentare, o eroare tipică de rulare este amenințarea depășirii matricei și coruperii datelor.

Opțiuni de implementare

Un tablou este un set ordonat de elemente, fiecare dintre ele stochează o singură valoare, identificată prin unul sau mai mulți indici. În cel mai simplu caz, o matrice are o lungime constantă și stochează unități de date de același tip, iar numerele întregi acționează ca indici.

Numărul de indici de matrice utilizați poate fi diferit: tablourile cu un index se numesc unidimensionale, cele cu doi se numesc bidimensionale și așa mai departe. Matrice unidimensională - corespunde vag unui vector în matematică; bidimensional („rând”, „coloană”) - matrice . Cel mai frecvent sunt utilizate tablourile cu unul sau doi indici; mai rar - cu trei; un număr şi mai mare de indici este extrem de rar.

Primul element al unui tablou, în funcție de limbajul de programare , poate avea un index diferit. Există trei tipuri principale de matrice: bazat pe zero (bazat pe zero), bazat pe unul (bazat pe unul ) și bazat pe o anumită valoare dată de programator ( bazat pe n ). Numărarea de la zero este mai tipică pentru limbajele de programare de nivel scăzut , deși se găsește și în limbajele de nivel înalt, de exemplu, este folosit în aproape toate limbile din familia C. Într-o serie de limbi ( Pascal , Ada , Modula-2 ), un interval de indici poate fi definit ca un interval arbitrar de valori de orice tip de date care poate fi transformat într-un număr întreg, adică numere întregi, simboluri, enumerații, chiar booleeni (în acest din urmă caz, o matrice are două elemente indexate prin valorile „True” și „False”).

Un exemplu de matrice fixă în Pascal {Matrice unidimensională de numere întregi. Numerotarea elementelor de la 1 la 15} a : matrice [ 1 .. 15 ] de Integer ; {Matrice bidimensională de caractere. Numerotarea coloanelor după tipul de octeți (de la 0 la 255) pe rânduri de la 1 la 5} multiArray : matrice [ Byte , 1 .. 5 ] de Char ; {Matrice unidimensională de șiruri. Numerotarea cuvintelor (de la 0 la 65536)} rangeArray : matrice [ Word ] of String ; Exemplu de matrice fixă în C int Matrice [ 10 ]; // Matrice unidimensională: numere întregi, dimensiunea 10; // Numerotarea elementelor — de la 0 la 9. double Array [ 12 ][ 15 ]; // Matrice bidimensională: // numere reale cu precizie dublă, // dimensiune 12 cu 15; // Numerotare: pe rânduri - de la 0 la 11, // pe coloane - de la 0 la 14.

În unele limbaje de programare, tablourile multidimensionale sunt create pe baza unor tablouri unidimensionale, în care elementele sunt tablouri [5] .

Exemplu de matrice 2D JavaScript //Creează o matrice bidimensională de numere: var array = [ [ 11 , 12 , 13 , 14 , 15 , 16 ], // Primul rând este o matrice [ 21 , 22 , 23 , 24 , 25 , 26 ] , // Al doilea [ 31 , 32 , 33 , 34 , 35 , 36 ] // Al treilea ]; // Ieșire matrice către consolă: array . forEach (( subArray ) => { // Pentru fiecare sub-matrice, subArray . forEach (( item ) => { // pentru fiecare dintre elementele sale, console . log ( item ); // imprimă acest element în consolă. }); });

Suportul pentru matrice de index (propria sintaxă de declarație, funcții pentru lucrul cu elemente și așa mai departe) se găsește în majoritatea limbajelor de programare de nivel înalt . Dimensiunea maximă admisă a matricei, tipurile și intervalele de valori ale indexului, restricțiile asupra tipurilor de elemente sunt determinate de limbajul de programare sau de un traducător specific .

În limbajele de programare care permit programatorului să-și declare propriile tipuri , în general este posibil să se creeze un tip „matrice”. În definirea unui astfel de tip, sunt specificate tipurile și/sau intervalele de valori ale fiecărui indici și tipul elementelor matricei. Tipul declarat poate fi folosit ulterior pentru a defini variabile, parametri formali și valori returnate ale funcției. Unele limbi acceptă operații de atribuire pentru variabile de matrice (când o operație atribuie toate elementele unui tablou valorilor elementelor corespunzătoare ale altei matrice).

Declarație de tip matrice în Pascal tip TArrayType = matrice [ 0 .. 9 ] de Integer ; (* Matricele care au următorii parametri: 1. Dimensiune - 10 celule; 2. Tip de elemente adecvate pentru stocare - - numere întregi în intervalul [−32 768; 32 767], - sunt declarate de un tip de operand numit „TArrayType” .*) var arr1 , arr2 , arr3 : TArrayType ; (* Declarația a trei variabile matrice de același tip („TArrayType”) de mai sus. *)

În limbajul de programare APL , o matrice este tipul principal de date (o matrice zero-dimensională se numește scalar, o matrice unidimensională se numește vector, iar o matrice bidimensională se numește matrice) [3] . În plus față de atribuirea matricei, acest limbaj acceptă operații aritmetice vectoriale și matrice, fiecare dintre acestea fiind efectuată de o comandă, operații de deplasare a datelor în matrice și sortarea rândurilor matriceale.

Matrice dinamice

Matricele sunt numite dinamice, a căror dimensiune se poate modifica în timpul execuției programului. Matricele obișnuite (non-dinamice) sunt numite și fixe sau statice .

Matricele dinamice pot fi implementate atât la nivelul limbajului de programare, cât și la nivelul bibliotecilor de sistem. În al doilea caz, matricea dinamică este un obiect al bibliotecii standard și toate operațiunile cu aceasta sunt implementate în cadrul aceleiași biblioteci. Într-un fel sau altul, suportul pentru matrice dinamice implică următoarele caracteristici:

Descrierea matricei dinamice. La nivel de limbaj, aceasta poate fi o construcție sintactică specială; la nivel de bibliotecă, poate fi un tip de date de bibliotecă a cărui valoare este declarată în mod standard. De regulă, atunci când descrieți (creați) o matrice dinamică, dimensiunea sa inițială este specificată, deși acest lucru nu este necesar.
Operația de determinare a mărimii curente a unui tablou dinamic.
Operația de modificare a dimensiunii unui tablou dinamic.

Un exemplu de structuri pentru lucrul cu matrice dinamice în Delphi :

var // Descrieri ale tablourilor dinamice byteArray : Array of Byte ; // Matrice unidimensională multiArray : Matrice de șir de caractere ; // Matrice multidimensională ... SetLength ( byteArray , 1 ) ; // Setați dimensiunea matricei la 1 element. byteArray [ 0 ] := 16 ; // Element de scriere. SetLength ( byteArray , Length ( byteArray ) + 1 ) ; // Mărește dimensiunea matricei cu un byteArray [ Length ( byteArray ) - 1 ] := 10 ; // Scrieți valoarea ultimului element. WriteLn ( byteArray [ Lungime ( byteArray ) - 1 ]) ; // Afișează ultimul element al matricei. ... SetLength ( multiArray , 20 , 30 ) ; // Setați dimensiunea unui tablou bidimensional multiArray [ 10 , 15 ] := 12 ; // Scrie valoarea SetLength ( multiArray , 10 , 15 ) ; // Reduceți dimensiunea lui WriteLn ( Length ( multiArray ) , ' ' , Length ( multiArray [ 0 ])

Matrice eterogene

O matrice este numită eterogenă , în diferitele elemente ale căror valori legate de diferite tipuri de date pot fi scrise direct . O matrice care stochează pointeri către valori de diferite tipuri nu este eterogenă, deoarece datele stocate efectiv în matrice aparțin unui singur tip - tipul „pointer”. Matricele eterogene sunt convenabile ca structură universală pentru stocarea seturilor de date de tipuri arbitrare. Implementarea eterogenității necesită complicarea mecanismului de suport al matricei în traducătorul de limbă.

Lucrul cu memoria

O modalitate tipică de a implementa o matrice statică omogenă (stocarea datelor de același tip) este alocarea unui bloc continuu de memorie cu un volum de , unde este dimensiunea unui element și sunt dimensiunile intervalelor de index (adică, numărul de valori pe care le poate lua indicele corespunzător). La accesarea unui element de matrice cu un index, adresa elementului corespunzător este calculată ca Ordinea indicilor în formula de calcul a adresei poate fi diferită. (Acest mod corespunde implementării în majoritatea compilatoarelor C ; în Fortran , ordinea indexului este inversată [2] ). $S\cdot m_{1}\cdot m_{2}\cdot \dots m_{n)$ $S$ $m_{1},\dots m_{n}$ $(i_{1},i_{2},\dots i_{n})$ $B+S\cdot \left(\left(\dots \left(i_{\text{1p}}m_{1}+i_{\text{2p}}\right)\cdot m_{2}+ \dots +i_{(n-1){\text{p}}}\right)\cdot m_{n-1}+i_{n{\text{p}}}\right)$ $B$ ${\displaystyle i_{k\mathrm {p} ))$ $k$

Astfel, adresa unui element cu un set dat de indici este calculată în așa fel încât timpul de acces la toate elementele tabloului să fie teoretic același; cu toate acestea, pot afecta diferite valori ale întârzierilor de răspuns de la RAM la celulele situate pe diferite elemente de memorie, dar în practica programării la nivel înalt, astfel de subtilități, cu rare excepții, sunt neglijate.

Modul obișnuit de a implementa matrice eterogene este de a stoca separat valorile elementelor în sine și de a plasa pointeri către aceste elemente în blocul de memorie al matricei (organizat ca o matrice omogenă obișnuită, descrisă mai sus). Deoarece pointerii către valori de orice tip tind să aibă aceeași dimensiune, este posibil să se mențină simplu calculul adresei, deși există o suprasarcină suplimentară pentru alocarea și accesarea valorilor elementelor.

Matricele dinamice pot folosi același mecanism de aspect ca și matricele statice, dar cu o memorie suplimentară alocată pentru extindere și adăugarea de mecanisme pentru redimensionarea și mutarea conținutului matricei în memorie.

De asemenea, matricele dinamice și eterogene pot fi implementate prin utilizarea unor metode fundamental diferite de stocare a valorilor în memorie, de exemplu, liste simple sau duble legate. Asemenea implementări pot fi mai flexibile, dar de obicei necesită cheltuieli suplimentare. În plus, de obicei nu îndeplinesc cerința de timp constant de acces la elemente.

Note

↑ Drot V. L., Novikov F. A. „Explanatory Dictionary of Modern Computer Vocabulary”, Dimension of an array . Data accesului: 18 octombrie 2012. Arhivat din original pe 3 iulie 2013. (nedefinit)
↑ 1 2 Barteniev, 2000 .
↑ 1 2 Magariu, 1983 .
↑ Wirth, 1989 , 1.6 Array.
↑ Michael McMillan. Structuri de date și algoritmi cu JavaScript (engleză) . - O'Reilly Media , 2014. - P. 30-32. — ISBN 978-1-4493-7396-2 .

Literatură

Wirth N. Algoritmi și structuri de date = Algoritmi și structuri de date. — M .: Mir, 1989. — 360 p. — ISBN 5-03-001045-9 .
Magariu N.A. Limbajul de programare APL. - M . : „Radio și comunicare”, 1983. - 96 p.
Barteniev O. V. Modern Fortran. - Ed. a III-a, add. şi revizuită .. - M . : Dialog-MEPhI, 2000. - 449 p.

Structuri de date
Liste	matrice listă legată individual listă dublu legată Lista de trecere
Copaci	B-arborele Arborele de căutare binar arborele AVL Copac roșu-negru morman
Contează	Graficul dirijat Graficul aciclic direcționat Diagrama de decizie binară Hipergraf
Alte	Tabel de hash Grămadă

Tipuri de date
Ininterpretabil	Pic Ciuguli octet qubit Trata Trăsătură Cuvânt
Numeric	Întreg punct fix punctul de plutire Raţional Complex Lung interval
Text	Simbolic Şir
Referinţă	Abordare Legătură Indicator Înveliș
Compozit	Tip de date algebrice ( generic ) Clasă Tip produs ( Scrie Tuplu structura ) Un obiect Consolidare ( etichetat ) Pereche comandată
abstract	matrice Listă Întoarce-te Grămadă Matrice asociativă (afișare, hartă ) Multe multiset Tip Grafic
Alte	Logic Inferior Superior Polimorfă Funcţional enumerabil Colectie Excepție Gen ( Metaclasă ) Monadă Semafor curgere gol
subiecte asemănătoare	Tip de date abstracte tip primitiv Structură de date Generic variabilă de tip Interfață Constructor (OOP) Constructor (FP) Constructor de tip Tip turnare Prototip Tip sistem