Matrice

Această intrare sau secțiune despre programare nu citează sursele necesare sau cei prezenți sunt insuficienți . Puteți îmbunătăți această intrare adăugând citate din surse de încredere în conformitate cu liniile directoare privind utilizarea surselor .

O matrice ^[1] (numită și vector sau matrice ) în informatică indică o structură de date complexă, statică și omogenă.

Matricele, prezente practic în toate limbajele de programare sau scriptare, sunt inspirate din noțiunea matematică de vector (când sunt unidimensionale) sau matrice (în cazul matricilor bidimensionale). Matricea este în general clasificată ca un constructor de tip : cu alte cuvinte, vă permite să definiți noi tipuri de date pornind de la tipuri preexistente, prin agregarea diferitelor obiecte toate de același tip. Fiecare obiect component este identificat printr-un indice întreg, în cazul unidimensional sau prin D indici întregi în cazul D- dimensional.

Caracteristici

Vectorul a n numere întregi cu numerotare index începând de la 0

O matrice poate fi considerată ca un fel de container, ale cărui cutii sunt numite celule (sau elemente ) ale matricei în sine. Fiecare dintre celule se comportă ca o variabilă tradițională; toate celulele sunt variabile de același tip preexistent, numit tipul de bază al matricei. Prin urmare, vom vorbi despre tipuri precum „matrice de numere întregi”, „matrice de șiruri”, „matrice de caractere” și așa mai departe. Prin urmare, ceea ce se obține prin declararea acestuia este un container static și omogen de valori, variabile sau obiecte . În unele limbi, dimensiunea matricei (adică numărul de celule din care este compusă) este considerată parte a definiției tipului matricei; în acest caz, vom vorbi mai precis despre tipuri precum „matrice de 100 de caractere” sau „matrice de 10 numere întregi”.

Fiecare dintre celulele din matrice este identificată printr-o valoare de index . Indicele este în general numeric, iar valorile pe care indicii le pot presupune sunt numere întregi contigue începând de la 0 ^[2] sau 1 ^[3] sau, mai rar, de la o valoare arbitrară, ca în Pascal. Prin urmare, putem vorbi despre celula cu index 0, index 1 și, în general, index N, unde N este un număr între 0 (sau 1) și valoarea maximă pentru indicii matricei.

Capacitatea de a accesa elemente printr-un index este caracteristica principală a unei matrice. Este posibil să accesați una dintre pozițiile sale generice individual („acces aleatoriu”, ca și pentru memorie), precum și să derulați secvențial în ambele direcții printr-un ciclu iterativ în toate elementele sale sau pornind de la unele dintre ele.

Iată un exemplu care folosește sintaxa C (similară, totuși, cu cea a multor alte limbi) pentru a defini o matrice și a atribui valori elementelor sale:

 vector int [ 10 ]; / * definește variabila numită "vector" ca o matrice de 10 numere întregi * /
 vectorul [ 0 ] = 0 ; / * atribuie valoarea "0" celulei index 0 * /
 vectorul [ 1 ] = 1 ;
 vectorul [ 2 ] = 1 ;
 vectorul [ 3 ] = 2 ;
 vectorul [ 4 ] = 3 ;

(Vectorul indicat mai sus conține primele cinci numere ale secvenței Fibonacci ).

Unele limbi permit indexuri non-numerice, de exemplu șiruri. În acest caz vorbim de tabel hash sau matrice asociativă , deoarece fiecare valoare de șir utilizată ca index este asociată cu o valoare matrice. Să vedem un exemplu în limbajul PHP :

 $ person [ "name" ] = "John" ;
$ person [ "surname" ] = "Smith" ;
$ persoana [ "varsta" ] = 32 ;

După cum puteți vedea, exemplul este foarte similar cu cel precedent; singura diferență relevantă (în afară de o mică diferență pur sintactică între limbi) este că indicele matrice este șir. Mai mult, cititorul expert va putea observa că în PHP nu există o constrângere de „tip bază” fixată pentru toate celulele matricei: primelor două li s-a atribuit un șir , al treilea un număr întreg .

Tablouri multidimensionale

În cele din urmă, trebuie remarcat faptul că o matrice (fie ea asociativă, ca în PHP sau nu) poate avea mai multe dimensiuni. Dacă o matrice are mai multe dimensiuni și mai ales în cazul bidimensional, este adesea denumită „matrice”, referindu-se la noțiunea matematică de matrice din care se inspiră. Diferența este că o matrice are doi (sau mai mulți) indici, fiecare dintre aceștia indexând o dimensiune, iar fiecare element este identificat prin combinația valorilor tuturor indicilor vectorului, într-o ordine predeterminată. Iată un exemplu:

 A [ 0 ] [ 0 ] = 1 ;
A [ 0 ] [ 1 ] = 2 ;
A [ 1 ] [ 0 ] = -1 ;
A [ 1 ] [ 1 ] = 1 ;

În acest exemplu numeric am dat celor patru elemente ale tabloului bidimensional A câteva valori numerice. Fiecare element este identificat în mod unic și, prin urmare, accesibil, numai prin specificarea ambilor indici. Mai mult, nu este posibilă schimbarea poziției indicilor: de fapt elementul A [0] [1], care este egal cu 2, este diferit de elementul A [1] [0], care este egal cu - 1.

Cu toate acestea, în exemplul următor vedem un caz de indexare folosind șiruri:

 $ person [ 0 ] [ "name" ] = "Samuel" ;
$ person [ 0 ] [ "surname" ] = "Smith" ;
$ person [ 1 ] [ "name" ] = "George" ;
$ person [ 1 ] [ "surname" ] = "White" ;

În acest caz, fiecare valoare corespunde unei caracteristici a unei anumite persoane. Primul index, în acest caz numeric (de exemplu, un boboc), identifică o persoană. Al doilea index, în acest caz un șir, indică caracteristica în cauză. În consecință, primul index nu este suficient pentru a accesa un element, deoarece nu indică ce caracteristică avem nevoie; dar nici măcar a doua, pentru că nu indică la ce persoană ne referim. Prin urmare, este combinația ambilor indici pentru a identifica o valoare.

O matrice bidimensională poate fi privită ca un tabel, în care prima coloană conține valorile unui index, primul rând valorile unui alt index și celulele individuale diferitele elemente. Prin aceleași principii, dacă are trei dimensiuni, poate fi vizualizat ca un cub. O matrice ar putea conține, de asemenea, mai mult de trei indici, dar acest lucru se întâmplă doar în cazuri foarte speciale, de exemplu în aplicații științifice sau datawarehousing . O matrice cu trei sau mai multe dimensiuni este definită mai precis ca un tensor .

Matrice și structuri de control

Majoritatea programelor care folosesc tablouri utilizează structura de control „ pentru bucle ” pentru a traversa tablouri, adică pentru a accesa celulele secvențial. Bucla for se pretează foarte natural la utilizarea combinată a matricei tocmai pentru că vă permite să specificați un anumit tip de iterație a unui anumit set de instrucțiuni, controlat de un index care preia un set de valori întregi și adiacente. De exemplu, codul Java pentru imprimarea conținutului unei matrice de n numere întregi ar putea fi după cum urmează:

 for ( int i = 0 ; i < vector . length ; i ++ ) // pentru i crescând cu pasul 1 de la 0 la lungimea vectorului
     Sistem . afară . println ( vectorul [ i ] ); // tipăriți celula i-a

Iată un algoritm simplu pentru calcularea maximului, minimului și mediei unui vector întreg scris folosind limbajul de programare Java:

 if ( vector . lungime ! = 0 ) // verificați dacă vectorul conține cel puțin un element
{ media dublă ;
    int max = vector [ 0 ] , min = vector [ 0 ] , sum = 0 ;
    for ( int i = 1 ; i < vector . length ; i ++ ) // scanare cu pasul 1 de la 0 până la lungimea vectorului
    { if ( vector [ i ]> max )
            max = vector [ i ] ;
        if ( vectorul [ i ] < min )
            min = vector [ i ] ;
        sum + = vector [ i ] ;
    }
    medie = (( dublă ) sumă ) / vector . lungime ;
    Sistem . afară . println ( "Minim:" + min );
    Sistem . afară . println ( "Max:" + max );
    Sistem . afară . println ( "Media:" + media );
}
altceva {
    Sistem . afară . println ( "Vectorul nu conține elemente" );
}

Aspecte de implementare

Tablourile sunt de obicei alocate în zone adiacente ale memoriei computerului . O matrice va ocupa o zonă de memorie a cărei dimensiune totală este dată de mărimea tipului de bază înmulțit cu numărul total de celule. Recuperarea unui element bazat pe index are loc prin adăugarea adresei de memorie de pornire a matricei (cunoscută de compilator sau de interpret ) valoarea indexului înmulțită cu dimensiunea tipului de bază. Astfel, dacă o matrice de numere întregi este alocată adresei de memorie 1000, pe o mașină în care numerele întregi ocupă 4 octeți, al cincilea element al acestuia (care are index 4) va fi alocat la poziția 1000+ (4 * (5-1)) = 1016 . Această regulă permite obținerea de accesuri eficiente la celulele matricei în termeni de timp petrecut, prin mecanisme de adresare indirectă care sunt furnizate de toți procesoarele (și, prin urmare, de toate limbajele mașinilor) sau prin manipularea numerică a indicatorilor din interiorul programului.

Verificați limitele

Același subiect în detaliu: Aliasing (programare) § Matrice .

Unele limbi, în special cele compilate , nu impun mediului de execuție nicio verificare a corectitudinii indexurilor utilizate pentru a accesa o celulă specifică a unui tablou. În consecință, într-un program scris în C, dacă o matrice de 20 de elemente de mărime 2 octeți este alocată adresei 1000, ultima celulă validă are indexul 19 și adresa 1038; dar dacă programatorul , din greșeală, încearcă să acceseze a patruzecea celulă (care nu există), limbajul nu va detecta eroarea și va oferi acces incorect la locația de memorie 1078.

De obicei, aceste limbaje de programare nu determină rezultatul exact al citirii sau scrierii din limitele matricelor, ceea ce face din acest mecanism o sursă de erori în programele care calculează o valoare de index incorectă. Motivul este că dispunerea și alinierea datelor stocate în cadrul programului (prin urmare, corespondența dintre celulele de memorie și celulele matricelor și variabilelor) depind atât de implementarea compilatorului adoptat, cât și de implementarea arhitecturii sistemul pe care va rula programul.

În cel mai bun caz, dacă memoria pe care ați încercat să o accesați nu a fost alocată de program, rezultatul va fi citirea unei valori aleatorii sau scrierea într-o locație de memorie care nu este utilizată nicăieri în program; în cel mai rău caz, este posibil ca acea zonă de memorie să fie alocată în schimb pentru o variabilă sau o altă matrice și, în consecință, programul să-și suprascrie datele, modificându-și execuția într-un mod imprevizibil.

Acest tip de erori la indexarea matricelor sunt, împreună cu erori la indicatoare, printre cele mai frecvente cauze ale funcționării defectuoase a programelor scrise în limbaje C și C ++ . Alte limbaje (de exemplu Java ) necesită ca mediul de execuție în care este lansat programul să blocheze accesul la matrice în afara limitelor stabilite și, eventual, să semnaleze această problemă cu o eroare în cadrul programului.

Notă

Elemente conexe

• Structură de date
• Matrice dinamică
• Matrice asociativă
• Matrice zimțată
• Vector de droguri

Alte proiecte

• Wikimedia Commons conține imagini sau alte fișiere pe tablouri

linkuri externe

• Matrice și Iteratori despre „Învățarea programării”, o carte gratuită despre noțiunile de bază ale programării.

V · D · M Algoritmi de sortare
Teorie	Teoria complexității de calcul · notație Big O · Matrice · Listă · Stack · Coadă · Sortare comparativă · Sortare adaptivă
Algoritmi de schimb	Bubble sortare · Shaker sortare · par-impar sortare · Comb sortare · Gnome sortare · Quicksort
Algoritmi de selecție	Sortare selecție · Sortare grămadă · Smoothsort
Algoritmi de inserție	Inserția sortare · Shell sortare · copac sortare · Bibliotecă sortare · sortare Răbdare
Algoritmi de fuziune	Merge sort · Timsort
Algoritmi necomparativi	Sortare Radix · Sortare cupă · Sortare numărare · Sortare porumbel
Alți algoritmi	Sortarea de rețea · topologică sortare · sortare bitonic · clatite sortare
Algoritmi ineficienți	Sortare stupidă · Sortare Trippel

Portal IT : accesați intrările Wikipedia care se ocupă cu IT