Ëåêöèÿ 12

Ðàáîòà ñ ìàòðèöàìè.

Ñïîñîáû ðàçìåùåíèÿ ìàòðèöû â ïàìÿòè

1. Äâîéíûå èíäåêñû

double matr[100][200]; - ìàòðèöà ðàçìåðîâ 100 ñòðîê íà 200 ñòîëáöîâ

matr[i][j] – ýëåìåíò i-é ñòðîêè è j-ãî ñòîëáöà

Âîïðîñ: ÷òî òàêîå matr[i] - ?

Çàäà÷à 1. Ïåðåìíîæèòü äâå ìàòðèöû

void mult(double m1[100][200], double m2[200][300], double m3[100][300]) {

int i, j, k;

for (i = 0; i < 100; i++) {

for (j = 0; j < 300; j++) {

m3[i][j] = 0;

for (k = 0; k < 200; k++) {

m3[i][j] += m1[i][k] * m2[k][j];

}

}

}

}

Ìàòðèöà 100 ñòðîê íà 200 ñòîëáöîâ

Ìàòðèöà äîëæíà ðàçìåùàòüñÿ â ïàìÿòè ïî ñòðîêàì.

Ïàìÿòü:

… [0][0] [0][1] [0][2] [0][3] … [0][199] [1][0] [1][1] [1][2] … [1][199] ... [99][0] [99][1] … [99][199] …

×òî òàêîå matr[0]? Ýòî àäðåñ íà÷àëà ìàòðèöû

×òî òàêîå matr[1]? Ýòî àäðåñ ñòðîêè ñ íîìåðîì 1

Âîïðîñ: ÷òî òàêîå matr[i]? Îòâåò: ýòî àäðåñ ñòðîêè ñ íîìåðîì i

2. Ðåàëèçàöèÿ ìàòðèöû íà áàçå îäíîìåðíîãî ìàññèâà

Çàäà÷à 2.  ôàéëå input.txt íàõîäÿòñÿ ðàçìåðû ìàòðèöû (äâà öåëûõ ÷èñëà: êîëè÷åñòâî ñòðîê è êîëè÷åñòâî ñòîëáöîâ) è åå ýëåìåíòû.

Ñ÷èòàòü ìàòðèöó èç ôàéëà, íàéòè ñòîëáåö ñ ìèíèìàëüíûì ýëåìåíòîì è âû÷åñòü åãî èç âñåõ îñòàëüíûõ ñòîëáöîâ.

Ïîëó÷èâøóþ ìàòðèöó âûâåñòè â ôàéë output.txt (ðàçìåðû íå âûâîäèòü).

 ñëó÷àå íåêîððåêòíûõ äàííûõ ïðîãðàììà äîëæíà âîçâðàùàòü -1, â îñòàëüíûõ ñëó÷àÿõ 0.

 ïðîãðàììå äîëæíû âûçûâàòüñÿ ôóíêöèè.

Ìàòðèöà N * K => âåêòîð ðàçìåðîì M = N*K

a[i][j] ↔ array[k]

i, j → k

k → i, j

Ìàòðèöà:

a₀₀ a₀₁ a_{02 …}

a₁₀ a₁₁ a_{12 …}

...

a_i0 a_i1 a_{i2 …} a_{ij ...} a_{i(K-1) /* i-ÿ ñòðîêà */}

...

a_{(N-1)0 ...}

Âåêòîð:

array₀ array_{1 …} array_(M-1)

Çàìå÷àíèå. Ïåðåä i-é ñòðîêîé — ðîâíî i ñòðîê, â êàæäîé ñòðîêå — K ýëåìåíòîâ.

Ïîýòîìó íîìåð ýëåìåíòà a_i0 â ìàòðèöå: i * K, à íîìåð a_ij = j + i * K

#include <stdio.h>

void process(double *matr, int N, int K);

void process(double *matr, int N, int K) {

double minElement;

int minElColumn = 0; /* ìèíèìàëüíûé ýëåìåíò íàõîäèòñÿ â êîëîíêå 0 */

int i, j;

minElement = matr[0];

for (i = 0; i < N; i++) {

for (j = 0; j < K; j++) {

if (matr[j + i * K] < minElement) {

minElement = matr[j + i * K]; /* ìèíèìàëüíûé ýëåìåíò íàõîäèòñÿ â êîëîíêå j */

minElColumn = j;

}

}

}

for (j = 0; j < K; j++) {

if (j != minElColumn) {

for (i = 0; i < N; i++) {

matr[j + i * K] -= matr[minElColumn + i * K]

}

}

}

}

int main(void) {

FILE *IN, *OUT;

double *matr;

int N, K, i, j;

IN = fopen("input.txt", "r");

if (IN == NULL) {

printf("File not opened\n");

return -1;

}

if (fscanf(IN, “%d%d”, &N, &K) != 2) {

printf("Not enough data\n");

fclose(IN);

return -1;

}

if ((N <= 0) || (K <= 0)) {

printf("Wrong matrix size\n");

fclose(IN);

return -1;

}

matr = (double*)malloc(N * K * sizeof(double)); /* sizeof(matr[0]) */

if (matr == NULL) {

printf("Memory not allocated\n");

fclose(IN);

return -1;

}

for (i = 0; i < N * K; i++) {

if (fscanf(IN, "%lf", &matr[i]) != 1) {

printf("Not enough numbers\n");

free(matr);

fclose(IN);

return -1;

}

}

fclose(IN);

process(matr, N, K);

OUT = fopen("output.txt", "w"); /* "out___.txt" – îáðàçåö */

if (OUT == NULL) {

printf("File output.txt not opened\n");

return -1;

}

for (i = 0; i < N; i++) {

for (j = 0; j < K; j++) {

fprintf(OUT, "%lf ", matr[j + i * K]);

}

fprintf(OUT, "\n");

}

fclose(OUT);

free(matr);

return 0;

}

2a. Ðåàëèçàöèÿ ìàòðèöû íà áàçå íåñêîëüêèõ îäíîìåðíûõ ìàññèâîâ

Ìîæíî òàêæå ðåàëèçîâûâàòü ìàòðèöó íà áàçå íåñêîëüêèõ îäíîìåðíûõ ìàññèâîâ:

äëÿ êàæäîé ñòðîêè ìàòðèöû âûäåëÿòü îòäåëüíûé ìàññèâ è àäðåñà ýòèõ ñòðîê òîæå ñîáðàòü â îòäåëüíûé ìàññèâ.

…

double **matr;

matr = (double**)malloc(N * sizeof(double));

if (matr == NULL) {

printf("Memory not allocated\n");

fclose(IN);

return -1;

}

for (i = 0; i < N; i++) {

matr[i] = (double*)malloc(K * sizeof(double));

if (matr[i] == NULL) {

printf("Memory not allocated\n");

/* îñâîáîäèòü âñþ çàõâà÷åííóþ äî ýòîãî ïàìÿòü è çàêðûòü ôàéë! */

return -1;

}

}

for (i = 0; i < N; i++) {

for (j = 0; j < K; j++) {

if (fscanf(IN, "%lf", &matr[i][j]) != 1) {

printf("Not enough numbers\n");

free(matr);

fclose(IN);

return -1;

}

}

}

fclose(IN);

process(matr, N, K);

…

for (i = 0; i < N; i++) {

free(matr[i]);

}

free(matr);

return 0;

}

Ïðåèìóùåñòâà 2à ïåðåä 2 — åñòåñòâåííîå èñïîëüçîâàíèå èíäåêñîâ i è j: [i][j]

Íåäîñòàòêè:

1) ìíîãî ëèøíåé ðàáîòû è ëèøíåãî êîäà

2) èçëèøíèé ðàñõîä ðåñóðñîâ ñèñòåìû:

a) ðàñõîä ïàìÿòè: ïàìÿòü ïðè âûçîâå malloc() âûäåëÿåòñÿ ðàçìåðîì 2^M. Òî åñòü ïðè êàæäîì çàõâàòå ïàìÿòè òåðÿåòñÿ ìíîãî áàéòîâ ïàìÿòè.

b) ðàñõîä ìàøèííîãî âðåìåíè: êàæäîå îïåðàöèÿ âûäåëåíèÿ ïàìÿòè òðåáóåò ìíîãî âðåìåíè.

Âûâîä: èñïîëüçîâàòü ìåòîä 2, à íå 2à)