Tablouri bidimensionale-generalitati

TABLOURI BIDIMENSIONALE-GENERALITATI

Tablourile sunt structuri de date omogene (date cu aceeasi semnificatie/tip). Intr-un tablou datele pot fi organizate astfel :

dupa un singur criteriu - tablouri unidimensionale sau vectori ;

dupa doua criterii - tablouri bidimensionale sau matrice

Se poate spune ca un tablou bidimensional este o structura de tip tablou unidimensional ale carei componente sunt toate unidimensionale de acelasi tip. Din acest punct de vedere se poate intelege foarte usor modul in care elementul lui se stocheaza in memoria interna si anume se va ocupa o zona compacta de tablouri unidimensionale(elementele) puse cap la cap continuare, in octeti succesivi. Pentru memorarea si prelucrarea datelor organizate ca tablouri bidimensionale, inainte de scrierea unui program trebuie sa cunoastem urmatoarele elemente :

tipul elementelor din tablou(datele cu aceeasi semnificatie)

numarul maxim de elemente din tablou(capacitatea tabloului)

capacitatea tabloului =nrmax_linii*nrmax_coloane

Tabloul ocupa in memoria calculatorului o « suprafata »(array) compusa din locatii invecinate(adiacente). In fiecare locatie este memorata valoarea unui element. Adresa locatiilor incepe de la o valoare de referinta specifica limbajului de programare(corespunzator primei linii), pentru fiecare element din tablou. In memoria calculatorului, tabloul este liniarizat :elementele sunt memorate in locatii adiacente, in ordinea liniilor. Adresarea unui element se face printr-o pereche de indici corespunzatori liniei si coloanei pe care se afla elementul respectiv. Pentru indicele de linie sau indicele de coloana, se pot folosi iepuri diferite de date, ceea ce permite o referire asemanatoare cu cea intalnita la jocul de sah.

Daca se ia in cosiderare tabloul a, declarat astfel:

type linie=array[1..4]

var a:array [1..3] of linie;

atunci zona ocupata de variabila "a" este formata din trei zone succesive numerotate cu 1, 2 si respectiv, 3, de cate 4 valori tip Word(adica de 4*2=8 octeti fiecare),zone care se mai numesc si liniile tabloului bidimensional. Fiecare dintre cele trei linii fiind compusa din cate 4 valori de tip word,rezulta ca tabloul contine 12 componente elementare si ocupa in total 24 de octeti.

Sa presupunem ca cele 12 valori sunt chiar numerele de la 1 la 12.Amplasarea lor in memoria interna va fi urmatoarea :

↑                 ↑ ↑

lin 1 lin 2 lin3

octet o              octet8 octet16

Daca dorim continutul uneia dintre ele, spre exemplu valoarea 5, trebuie sa se indice linia din care face parte si numarul lui 5 in cadrul liniei, adica linia 2 primul element, perechea (2,1).Deoarece structura formata este fixa, toate liniile au acelasi numar de elemente (aici 4), atunci pentru utilizator ea devine o repartizare dreptunghiulara(deasupra 6), de unde rezulta o repartizare si pe coloane, deci doua coordonate pentru un element :(linie i, coloana j).

lin 1→

lin 2→

lin 3→

col1 col 2col 3 col 4

Astfel daca vrem sa accesam valoarea 5 din tablou, atunci, in limbajul PASCAL, vom scrie a[2,1].

In general, pentru un tablou bidimensional cu m linii si n coloane si pentru un i (1 ≤ i ≤ m) si un j (1 ≤ j ≤ n) fixate, adresa de memorie ocupata de elementul situat la intersectia liniei i cu coloana j este :

rang _element = (i-1) ∙ n + j, inmultit cu nr. de octeti ai tipului de baza

Invers, daca se cunoaste rangul elementului si se doreste aflarea perechii (i,j) :

i ← rang div n + 1 , iar j ← rang mod n.

Din cele de mai sus rezulta ca parcurgerea unei linii din tablou presupune trecerea prin toate elementele ei vazute acum drept coloane, deci o prelucrare in limbajul Pascal astfel :

for i :=lin_initiala tu lin_finala do

for j:= col_initialato col_finala do

P

1.1.  OPERATII INTR-UN  TABLOU BIDIMENSIONAL

Datele organizate in tablouri bidimensionale sunt prelucrate element cu element. Dintre cele mai frecvent intalnite prelucrari amintim:

Introducerea valorilor direct de la tastatura

Afisarea valorilor pe ecran

Verificarea unor proprietati

Compararea valorilor(aflarea elementului maxim sau minim)

Simularea unor situatii reale

1.1.1.     Declararea si parcurgerea unui TABLOU BIDIMENSIONAL

Declararea unui tablou bidimensional se poate face in PASCAL in doua moduri :

a) Pornind de la definitia de tablou unidimensional, in care fiecare element este un tablou unidimensional, la randul sau (pe scurt : tabloul bidimensional este un vector de vectori) :

type     nume_linie=array[ J₁..J₂] of tip_element ;

var        nume_tablou:array[ I₁..I₂] of nume_linie;

unde notatiile:

- nume_linie este identificatorul dat tipului de date definit de programator pentru o linie a tabloului ;

- tip_element reprezinta un tip de date cunoscut de catre compilator (standard sau definit anterior de catre programator) si care arata reprezentarea interna a unui element din matrice ;

-nume_tablou este identificatorul dat de programator acestui grup de date ;

-J₁ si J₂ reprezinta limitele de indici pentru elementele dintr-o linie, adica spatiul coloanelor, J₁ ≤ J₂ ;

-I₁ si I₂ reprezinta limitele de indici pentru liniile matricei, I₁ ≤ I₂

Valorile J₁, J₂, I₁, I₂ sunt constante de tip ordinal. Cu ajutorul lor se poate calcula spatiul necesar alocarii tabloului. Intre parantezele drepte pot aparea si domenii intregi : a :array [char, char] of byte ; dar alocarea se poate bloca, deoarece se creeaza structuri prea voluminoase.

defineste o structura a informatiilor referitoare la mediile generale ale elevilor unei clase, prezentate sub forma unui tabel in care pentru fiecare dintre cei 32 elevi exista un rand completat cu cele 18 medii ale sale, valori reale. Deci variabila elevi este un tablou unidimensional de 32 de elemente, iar fiecare element al sau este de tipul medii. Constantele pentru spatiul indicilor sunt: I₁=1, I₂=32, J₁=1, J₂=18.

b) Pornind de la aspectul de spatiu dreptunghiular, cum este perceput mai usor tabloul de catre utilizator :

caz in care declararea se face direct, odata cu definirea variabilei de lucru pentru acel tabel.

defineste aceeasi structura bidimensionala din exemplul de mai sus, dar aici este pus in evidenta tot grupul - clasa- pentru care exista 32 de linii a cate 18 elemente reale fiecare.

Parcurgerea unui tablou bidimensional presupune trecerea prin fiecare linie a acestuia.

Parcurgerea unei linii din tablou presupune trecerea prin toate elementele ei vazute acum drept coloane.

Referirea unui element al tabloului se face prin exprimarea :

Vizualizarea in forma dreptunghiulara, matriceala, a unui tablou bidimensional, t, cu m linii si n coloane va genera configuratia privind accesul la elementele lui prezentata in figura de mai jos :

Daca definim prin P o prelucrare asupra tuturor elementelor tabloului, atunci in limbajul de programare se va proiecta o secventa de tipul :

In particular, pentru un tablou a cu m linii si n coloane, secventa va fi scrisa: