Tendinta de a micsora spatiul ocupat de anumite date in memoria unui calculator a dus la proiectarea si dezvoltarea a multor algoritmi de compresie .
O matrice rara este o matrice ce contine mai mult de doua treimi valori nule.
O astfel de matrice se poate comprima foarte simplu prin inlocuirea sa in memorie cu trei vectori cu dimensiuni egale cu numarul de elemente nenule din matrice . Pe fiecare pozitie din cei trei vectori se vor gasi rangul liniei, in primul vector, rangul coloanei, in al doilea vector si elementul nenul din matrice in cel de-al treilea vector. Al tr 858b19i eilea vector va fi ordonat dupa primul vector si dupa cel de-al doilea vector.
Programul contine urmatoarele proceduri :
O procedura de alocare si initiere de la tastatura a unei matrice:
void incarcare(float **&a,int m,int n) care primeste ca parametri un pointer catre o matrice de numere reale prin referinta pentru a permite modificarea sa si dimensiunile matricei;
O procedura care verifica daca o matrice este rara:
int ifrar(float **a,int m,int n) care primeste ca parametri un pointer la matrice si dimensiunile matricei si returneaza numarul de elemente nenule din matrice daca aceasta este rara sau 0 daca nu;
O procedura care transforma o matrice rara in cei trei vectori despre care am vorbit mai sus:
void matrara(float **a,int m,int n,int k,int *&v1,int *&v2,float *&v3)
care primeste ca parametri un pointer la matrice, dimensiunile matricei, numarul de elemente nenule din matrice si cate un pointer la fiecare din cei trei vectori care rezulta, primiti prin referinta ;
O procedura care dezaloca o matrice alocata dinamic:
void distruge(float **&a,int m,int n) care primeste ca parametri un pointer la matrice transmis prin referinta si dimensiunile ei;
O procedura care aduna doua matrice rare ce au fost in prealabil comprimate :
int adunare(float *vel1,int *vc1,int *vl1,int n1,float *vel2,int *vc2,int *vl2,int n2,float *&velr,int *&vcr,int *&vlr) care primeste ca parametri trei pointeri catre cei trei vectori corespunzatori primei matrice si dimensiunea lor, trei pointeri catre cei trei vectori corespunzatori celei de-a doua matrice si dimensiunea lor si trei pointeri catre trei vectori corespunzatori matricei rezultate si returneaza dimensiunea vectorilor rezultati;
O procedura care calculeaza diferenta dintre doua matrice rare comprimate in prealabil:
int scadere(float *vel1,int *vc1,int *vl1,int n1,float *vel2,int *vc2,int *vl2,int n2,float *&velr,int *&vcr,int *&vlr) avand aceiasi parametri de intrare si returnand tot dimensiunea vectorilor rezultati.
Programul urmeaza urmatorul algoritm:
P1-Introducerea de la tastatura a dimensiunilor matricelor( matricele trebuie sa aiba aceleasi dimensiuni pentru a le putea aduna sau scadea) ;
P2-Alocarea si initializarea primei matrice prin procedura "incarcare";
P3-Verificarea primei matrice daca este rara prin procedura " ifrar" si daca nu este se afiseaza ca nu este rara si se incheie rularea programului, iar daca este se trece la pasul urmator;
P4-Compresia primei matrice prin procedura " matrar" ;
P5-Dezalocarea primei matrice prin procedura " distruge";
P6-Alocarea si initializarea celei de-a doua matrice prin procedura "incarcare";
P7-Verificarea celei de-a doua matrice daca este rara prin procedura " ifrar" si daca nu este se afiseaza ca nu este rara si se incheie rularea programului, iar daca este se trece la pasul usmator;
P8-Compresia celei de-a doua matrice prin procedura " matrar" ;
P9-Dezalocarea celei de-a doua matrice prin procedura " distruge";
P10-Suma celor doua matrice prin procedura " adunare";
P11-Diferenta celor doua matrice prin procedura " scadere".
Procedura " adunare" are urmatorii pasi:
P1-Alocarea celor trei vectori corespunzatori rezultatului;
P2- Parcurgerea vectorilor primei matrice, iar pentru fiecare iteratie se parcurg pasii P3-P5;
P3- Parcurgerea vectorilor celei de-a doua matrice pana la egalarea rangului liniei si coloanei elementului curent din prima matrice si copierea lor in vectorii rezultanti;
P4-Daca rangul liniei si coloanei sunt aceleasi la elementele curente din cele doua matrice se aduna elementele si se introduce rezultatul in vectorii rezultanti si se sare la P6, altfel se trece prin pasul P5;
P5-daca nu exista in cea de-a doua matrice element nenul pe linia si coloana corespunzatoare elementului curent din prima matrice se copiaza acest element si pozitia sa in matrice in vectorii rezultanti;
P6-Dupa ce se termina de parcurs vectorii primei matrice, se verifica daca in cea de-a doua matrice sunt elemente de rang al liniei sau coloanei mai mare decat al ultimului element din vectorii primei matrice si daca exista astfel de elemente se vor memora aceste elemente in continuare in vectorii matricei rezultate;
P7-Se returneaza lungimea vectorilor rezultati;
Procedura " scadere" urmeaza pasii:
P1-Alocarea si initializarea unui vector auxiliar cu valorile vectorului de elemente corespunzator celei de-a doua matrice, luate cu semn schimbat;
P2-Efectuarea diferentei prin adunarea primei matrice cu matricea a doua inmultita cu -1;
P3-Returnarea lungimii vectorilor rezultati.
#include<iostream.h>
//procedura de compresie a unei matrice rare(normalizarea sa)
void matrara(float a[10][10],int m,int n,int v1[34],int v2[34],float v3[34])
}
//procedura dealocare si incarcare de la tastatura a unei matrice
void incarcare(float a[10][10],int m,int n)
}
//procedura de verificare a unei matrice daca este rara
int ifrar(float a[10][10],int m,int n)
//procedura de adunare a doua matrici rare memorate in vectori
int adunare(float *vel1,int *vc1,int *vl1,int n1,float *vel2,int *vc2,int *vl2,int n2,float velr[67],int vcr[67],int vlr[67])
if((vl1[i]==vl2[j])&&(vc1[i]==vc2[j])) //daca rangul liniei si coloanei sunt
k++;
}
else
}
if(k!=n2) //daca in cea de-a doua matrice sunt elemente de
for(i=k;i<n2;i++) //rang al liniei sau coloanei mai mare decat al
return l; //returneaza lungimea vectorilor rezultati
//procedura de scadere a doua matrice rare memorate fiecare in cate trei vectori
int scadere(float *vel1,int *vc1,int *vl1,int n1,float *vel2,int *vc2,int *vl2,int n2,float velr[67],int vcr[67],int vlr[67])
void main ()
else
cout<<"Nu este matrice rara!!!";
}
else
cout<<"Nu este matrice rara!!!";
}
#include<iostream.h>
//procedura de compresie a unei matrice rare(normalizarea sa)
void matrara(float **a,int m,int n,int k,int *&v1,int *&v2,float *&v3)
}
//procedura dealocare si incarcare de la tastatura a unei matrice
void incarcare(float **&a,int m,int n)
}
//procedura de verificare a unei matrice daca este rara
int ifrar(float **a,int m,int n)
//procedura de dezalocare a unei matrice
void distruge(float **&a,int m,int n)
//procedura de adunare a doua matrici rare memorate in vectori
int adunare(float *vel1,int *vc1,int *vl1,int n1,float *vel2,int *vc2,int *vl2,int n2,float *&velr,int *&vcr,int *&vlr)
if((vl1[i]==vl2[j])&&(vc1[i]==vc2[j])) //daca rangul liniei si coloanei sunt
k++;
}
else
}
if(k!=n2) //daca in cea de-a doua matrice sunt elemente de
for(i=k;i<n2;i++) //rang al liniei sau coloanei mai mare decat al
k=n1+n2-l;
/*delete [k](vlr+l);
delete [k](vcr+l);
delete [k](velr+l);*/
return l; //returneaza lungimea vectorilor rezultati
//procedura de scadere a doua matrice rare memorate fiecare in cate trei vectori
int scadere(float *vel1,int *vc1,int *vl1,int n1,float *vel2,int *vc2,int *vl2,int n2,float *&velr,int *&vcr,int *&vlr)
void main ()
else
cout<<"Nu este matrice rara!!!";
}
else
cout<<"Nu este matrice rara!!!";
}
|
