O matrice dinamică este o matrice având elemente de tip “int”, asupra căreia se pot efectua următoarele operații:
- se adaugă o linie nouă la matrice
- se adaugă o coloană nouă la matrice
- se extinde matricea la dreapta prin alipirea la ea a unei alte matrici având același număr de linii (practic, coloanele celei de-a doua matrici se adaugă în continuarea coloanelor primei matrici)
- se extinde matricea în jos prin alipirea la ea a unei alte matrici având același număr de coloane (practic, liniile celei de-a doua matrici se adaugă în continuarea liniilor primei matrici)
Fiecare matrice dinamică este stocată pe disc în câte un fișier binar.
Cerință
Sarcina voastră este să îl ajutați pe Howard să implementeze în cadrul unui fișier header denumit “matdin.h” următoarele funcții:
void Init(char* prefix);
Această funcție realizează orice initializări aveți nevoie. Șirul “prefix” indică faptul că numele oricarui fișier pe care îl creați trebuie să înceapă cu șirul “prefix”.
int CreateMatrix();
Această funcție creează o matrice nouă, goală (având 0 linii și 0 coloane) și îi asociază un identificator unic (un număr întreg). Identificatorul matricii nou create este întors ca rezultat al funcției.
void GetMatrixDimensions(int id, int* nrows, int* ncols);
Această funcție setează conținutul de la adresele de memorie ale pointer-ilor nrows și ncols la numărul de linii, respectiv de coloane, ale matricii având identificatorul id.
void AppendRow(int id, int* elems);
Această funcție adaugă un rând nou la matricea cu identificatorul id. Pointer-ul elems pointează către o zonă de memorie ce conține elementele de pe rândul nou adăugat (în ordine crescătoare a coloanelor). Numărul de elemente adăugate este egal cu numărul de coloane ale matricii (din momentul adăugării rândului nou).
void AppendColumn(int id, int* elems);
Această funcție adaugă o coloană nouă la matricea cu identificatorul id. Pointer-ul elems pointează către o zonă de memorie ce conține elementele de pe coloana nou adaugată (în ordine crescătoare a liniilor). Numărul de elemente adăugate este egal cu numărul de linii ale matricii (din momentul adăugarii coloanei noi).
int** GetSubMatrix1(int id, int start_row, int start_col, int end_row, int end_col);
Această funcție întoarce o submatrice în memorie ce conține toate elementele dintre liniile start_row și end_row (inclusiv) și dintre coloanele start_col și end_col (inclusiv) ale matricii dinamice cu identificatorul id. Liniile și coloanele unei matrici dinamice sunt numerotate începând de la 0.
int** GetSubMatrix2(int** base_submatrix, int start_row, int start_col, int end_row, int end_col);
Această funcție întoarce o submatrice în memorie ce conține elementele dintre liniile start_row și end_row (inclusiv) și dintre coloanele start_col și end_col (inclusiv) ale submatricii base_submatrix. base_submatrix este o submatrice întoarsa anterior de un apel al functiilor GetSubMatrix1 sau GetSubMatrix2. Liniile și coloanele unei submatrici sunt numerotate începand de la 0. Submatricea nou creată trebuie să se suprapună peste submatricea base_submatrix. Mai exact, atunci când se modifică un element al noii submatrici, elementul corespunzător din base_submatrix trebuie să se modifice și el în mod automat (și invers).
void PutSubMatrix(int** submatrix);
Scrie elementele submatricii “submatrix” peste elementele corespunzătoare din matricea dinamică ale cărei elemente le conține. submatrix a fost întoarsă anterior de un apel al funcțiilor GetSubMatrix1 sau GetSubMatrix2.
void ExtendRight(int id1, int id2);
Extinde la dreapta matricea dinamică cu identificatorul id1 prin alipirea matricii dinamice cu identificatorul id2. Practic, coloanele matricii dinamice id2 sunt adăugate în continuare coloanelor matricii id1. Cele două matrici dinamice vor avea același număr de linii în momentul apelului acestei funcții.
void ExtendDown(int id1, int id2);
Extinde în jos matricea dinamică cu identificatorul id1 prin alipirea matricii dinamice cu identificatorul id2. Practic, liniile matricii id2 sunt adăugate în continuarea liniilor matricii id1. Cele două matrici dinamice vor avea același număr de coloane în momentul apelului acestei funcții.
int GetNumberOfElementsBetweenValues(int id, int vmin, int vmax);
Întoarce numărul de elemente ale matricii dinamice cu identificatorul id a căror valoare este cuprinsă în intervalul [vmin,vmax].
void Finish();
În cadrul acestei funcții veți salva datele necesare în fișiere (sau, în funcție de implementare, doar veți închide fișierele deschise), pentru a fi disponibile la rulări ulterioare. De asemenea, tot în cadrul acestei funcții va trebui să eliberați toate zonele de memorie alocate dinamic (și nedezalocate încă) de funcțiile voastre.
Exemplu de fișier main.c care ilustrează utilizarea funcțiilor cerute:
#include <stdio.h>
#include "matdin.h"
int main() {
Init("datafile");
int mid0 = CreateMatrix();
/* Întrucat matricea are 0 coloane în acest moment, nu conteaza ce parametru dam ca pointer catre zona de memorie ce contine elementele noii linii. */
AppendRow(mid0, NULL);
AppendRow(mid0, NULL);
int col0[] = { 3, 4 };
AppendColumn(mid0, col0);
int col1[] = { 5, 6 };
AppendColumn(mid0, col1);
int mid1 = CreateMatrix();
AppendColumn(mid1, NULL);
int row0[] = { 7 };
AppendRow(mid1, row0);
int row1[] = { 8 };
AppendRow(mid1, row1);
int nl0, nc0, nl1, nc1;
/* Trebuie sa obtinem nl0 == 2 și nc0 == 2. */
GetMatrixDimensions(mid0, &nl0, &nc0); /*
Trebuie sa obtinem nl1 == 2 și nc1 == 1. */
GetMatrixDimensions(mid1, &nl1, &nc1);
/* Întrucat cele 2 matrici au acelasi număr de linii, putem extinde una din ele la dreapta cu cealalta matrice. */
/* Extindem matricea dinamica mid1 la dreapta cu matricea dinamica mid0. In urma extinderii, mid1 va avea 2 linii și 3 coloane. */
ExtendRight(mid1, mid0);
/* Extindem în jos matricea dinamica mid1 cu ea insasi. In urma extinderii, mid1 va avea 4 linii și 3 coloane. */
ExtendDown(mid1, mid1);
/* Obtinem o submatrice s1 ce contine toata matricea dinamica mid1. */
int** s1 = GetSubMatrix1(mid1, 0, 0, 3, 2);
/* Afisam submatricea s1. */
int i, j;
for (i = 0; i <= 3; i++) {
for (j = 0; j <= 2; j++) printf("%d ", s1[i][j]);
printf("\n");
}
/* Obtinem o submatrice s2 ce se suprapune peste submatricea s1. Mai exact, ea va contine doar liniile 1 și 2 și coloana 1 din s1. */
int **s2 = GetSubMatrix2(s1, 1, 1, 2, 1);
/* Daca modificam s2[0][0], va trebui sa se modifice automat și s1[1][1]. */
s2[0][0]++;
printf("%d %d\n", s2[0][0], s1[1][1]);
/* Scriem submatricea s2 peste elementele din matricea dinamica peste care se suprapune. */
PutSubMatrix(s2);
/* Obtinem o noua submatrice s3, care trebuie sa aiba aceleasi elemente ca și s2. */
int **s3 = GetSubMatrix1(mid1, 1, 1, 2, 1);
for (i = 0; i <= 1; i++) printf("%d\n", s2[i][0] - s3[i][0]);
/* Calculam numărul de elemente din mid1 cuprinse Între 4 și 7 (inclusiv). */
int num_elems = GetNumberOfElementsBetweenValues(mid1, 4, 7);
printf("%d\n", num_elems);
Finish();
return 0;
}
Autor: Mugurel Ionuț Andreica
Data: 13.01.2012