Setul de date 0007
Matricea A nu are elemente nenule, iar matricea A are elemente nenule.

10. Matrice

2.1 Alocarea de memorie

2.2 Modelul masivului unidimensional
2.3 Modelul masivului bidimensional
2.4 Referirea elementelor
2.5 Initializarea
2.6 Inserarea

2.7 Interschimbul de elemente

2.8 Stergerea

2.9 Copierea

2.10 Concatenarea

2.11 Biblioteci

back data structures curricula

2.1 Alocarea de memorie
Se efectueaza static prin instructiuni de forma:
tip nume_masiv[dim_1];
tip nume_masiv[dim_1][dim_2];
tip nume_masiv[dim_1][dim_2][dim_3];
.............................
tip nume_masiv[dim_1][dim_2][dim_3]...[dim_n];
Lungimea zonei de memorie alocata este:
L=lg(tip)*dim_1*dim_2*dim_3*....*dim_n
Pentru definirea:
float alfa[10][14];
L(alfa)=lg(float)*10 * 14= 4*10*14=560 baiti
....................
....................
....................
....................
....................
....................
....................
....................
revenire

2.2 Modelul masivului unidimensional
Pentru definirea:
tip alfa[n]; se definesc proprietatile:
adr(alfa[0])=adresa
adr(alfa[i])=adr(alfa[i-1])+L(tip)
adr(alfa[i])=adresa+(i-1)*L(tip)
L(alfa[0])=L(alfa[1])=.....=L(alfa[n-1])=L(tip)
succ(alfa[i])=alfa[i+1]
pred(alfa[i])=alfa[i-1]
pred(alfa[0])=NULL
succ(alfa[n-1])=NULL
tip(alfa[0])=tip(alfa[1])=....=tip(alfa[n-1])
daca se memoreaza un masiv bidimensional simetric, este rezonabil sa se memoreze numai jumatate din elementele sale.
Pentru un masiv cu m linii si m coloane, simetric, numai m(m+1)/2 elemente sunt diferite.
Mewmorarea se efectueaza intr-un vector.
....................
....................
....................
....................
....................
....................
....................
....................
revenire

2.3 Modelul masivului bidimensional
Pentru masivul:
tip nume[dim_1][dim_2];
elementele se refera cu expresia nume[i][j], i=0,1,2,3,...,dim_1 - 1, j=0,1,2,...,dim_2-1. tip(nume[0][0])=tip(nume[0][1])=....=tip(nume[dim_1-1][dim_2-1])
L(nume[0][0])=L(nume[0][1])=..............=L(nume[dim_1-1][dim_2-1])
La calculele de adresa se are in vedere faptul ca linearizarea se face pe linie, elementele masivului sunt un sir definit prin:
nume[0][0], nume[0][1], nume[0][2],... nume[0][dim_2-1], nume[1][0], nume[1][1], nume[1][2].........., nume[1][dim_2-1], nume[2][0]...........nume[i][0],nume[i][1],.......,nume[i][dim_2-1],...........nume[dim_1-1][0], nume[dim_1-1][1],...., nume[dim_1-1][dim_2-1]
Pentru calculul adresei elementului de pe linia i si coloana j se utilizeaza relatia:
adr(nume[i][j])=adr(nume[0][0])+ (i*dim_2)*L(tip) + j*L(tip) ....................
....................
....................
....................
....................
....................
....................
....................
revenire

2.4 Referirea elementelor
Referirea elementelor:
- direct a[i],b[i][j], c[i][j][k]
- folosint pointeri *(a+i), *(*(b+i)+j), *(*(*(c+i)+j)+k)
....................
....................
....................
....................
....................
....................
....................
....................
revenire

2.5 Initializarea
Initializarea se realizeaza:
- la definire cand numarul de linii si numarul de coloane corespund si matricei initializate
- la definire numai partial
- de la tastatura
- prin citire dintr-un fisier
- prin copiere dintr-o alta matrice
- prin atribuire
- ca rezultat al unor calcule.
....................
....................
....................
....................
....................
....................
....................
....................
revenire

2.6 Inserarea
Inserarea unui element intr-un vector presupune:
- identificarea pozitiei K
- deplasarea spre dreapta
- atribuirea elementului K a valorii.
Inserarea in matrice se efectueaza ca:
- inserare de linie
- inserare de coloana.
Procedurile de inserare presupune depasari si atribuiri.
....................
....................
....................
....................
....................
....................
....................
....................
revenire

2.7 Interschimbul de elemente
Procedura care realizeaza interschimul care ca parametri:
- nume masiv
- dimensiune masiv
- pozitia elementului_1 de interschimb
- pozitia elementului2 de interschimb.
Pentru interschimbul a doua elemente a[i][j][k] si a[t][h][s] dintr-un masiv tridimensional, trebuie sa existe in lista de parametri:
M - numarul de masive bidimensionale
N - numarul de linii din masivul bidimensional
K - numarul de coloane din masivul bidimensional.
Masivul tridimensional este vazut aici ca vector de masive bidimensionale.
- coordonalele elementului i,j,k
- coordonatele t,h,s.
Interschimbul presupune secventa:
temp=a[i][j][k];
a[i][j][k]=a[t][h][s];
a[t][h][s]=temp;
....................
....................
....................
....................
....................
....................
....................
....................
revenire

2.8 Stergerea
Este operatia opusa inserarii.
Se produce deplasarea spre stanga.
Se diminueaza numarul de componente de referit din vector.
Pentru matrice se sterg:
- linii
- coloane.
Trebuie identificate liniile si coloanele.
Se produce deplasare elemente.
Se modifica numarul de linii sau de coloane care se refera.
....................
....................
....................
....................
....................
....................
....................
....................
revenire

2.9 Copierea
Copierea este mod de initializare.
Se copiaza matrice sau vectori integral sau partial.
Pentru copierea unui masiv tridimensional c[][][] intr-un masiv a[][][] se scrie secventa:
for(i=0;i for(j=0;j for(k=0;k a[i][j][k]=c[i][j][k];
Copierea se efectueaza direct sau schimband pozitiile indicilor.
Secventa:
for(i=0;i for(j=0;j a[i][j]=b[j][i];
copiaza in matricea a[][] transpusa matricei b[][].
....................
....................
....................
....................
....................
....................
....................
....................
revenire

2.10 Concatenarea
Concatenarea se realizeaza:
- prin construirea unei noi structuri omogene
- prin copierea intr- structura a celei care face obiectul concatenarii.
Daca se concateneaza vectorii:
int a[23];
int b[41];
varianta de creare a unei noi structuri presupune definirea:
int c[23+41];
dupa care:
- se copiaza in c[] elementele lui a[]
- se copiaza in c[] in continuare elementele lui b[].
In cazul in care a[] este definit cu 64 de elemente din care 23 sunt initializate, concatenarea va presupune atribuirea a[23+j]=b[j], j=0,1,2,..,41.
....................
....................
....................
....................
....................
....................
....................
....................
revenire

2.11 Biblioteci
Pentru calcule matriceale se construiesc biblioteci care implementeaza:
- operatiile de calcul: adunare, scadere, inmultire, inversare, generare
- operatii de initializare
- operatii de lucru cu blocuri
- operatii de conversie
- operatii in interiorul masivului: adunare linii, adunare coloane
- calcule norme
- numarare elemente dupa o conditie
- reducerea de dimensiuni prin eliminare linii sau coloane nule.
Cu cat bibliotecile sunt mai bogate, cu atat sansa de a solutiona cat mai multe probleme este mai mare.
Bibliotecile trebuie sa aiba un mod omogen de referire elemente si de construire liste de parametri.
Bibliotecile trebuie sa contina proceduri generali si sa introduca multe teste pentru a le face fiabile.
Procedura pentru copierea unui bloc de m1 linii si n1 coloane din matricea a definita cu m2 linii si n2 coloane incepand cu elementul a[h][f]presupune:
- testarea daca m1 - testarea daca pozitia primului element de unde incepe copierea este in matrice, adica h - testarea daca ultimul element din bloc se gaseste in matricea initiala h+m1 Numai daca toate aceste conditii sunt respectare se trece la copierea blocului.
Procedura returneaza:
0 - daca operatia de copiere s-a facut corect
1 - daca nu s-a facut copierea pentru ca se dorea copierea unui bloc mai mare decat matricea initiala
2 - blocul iese din matrice la stanga
3 - blocul iese din matrice la dreapta
4 - blocul ierse din matrice in ambele directii.
Lista mesajelor de eroare trebuie sa fie bogata.
La aceeasi eroare corespunde un singur cod.
La erori diferite corespund diferite coduri.
....................
....................
....................
....................
....................
....................
....................
....................
revenire