4.2.1 矩陣的數(shù)組表示

【數(shù)據(jù)結(jié)構(gòu)】數(shù)組和字符串（一）：矩陣的數(shù)組表示

4.2.2 特殊矩陣的壓縮存儲

??矩陣是以按行優(yōu)先次序?qū)⑺芯仃囋卮娣旁谝粋€(gè)一維數(shù)組中。但是對于特殊矩陣，如對稱矩陣、三角矩陣、對角矩陣和稀疏矩陣等, 如果用這種方式存儲，會出現(xiàn)大量存儲空間存放重復(fù)信息或零元素的情況，這樣會造成很大的空間浪費(fèi)。為節(jié)約存儲空間和算法（程序）運(yùn)行時(shí)間，通常會采用壓縮存儲的方法。

• 對角矩陣：指除了主對角線以外的元素都為零的矩陣，即對 任意 i ≠ j (1≤ i , j ≤n)，都有M(i, j)=0。由于只有主對角線上有非零元素，只需存儲主對角線上的元素即可。
• 三角矩陣：指上三角或下三角的元素都為零的矩陣。同樣地，只需存儲其中一部分非零元素，可以節(jié)省存儲空間。
• 對稱矩陣：指矩陣中的元素關(guān)于主對角線對稱的矩陣。由于對稱矩陣的非零元素有一定的規(guī)律，可以只存儲其中一部分元素，從而減少存儲空間。
• 稀疏矩陣：指大部分元素為零的矩陣。傳統(tǒng)的按行優(yōu)先次序存儲方法會浪費(fèi)大量空間來存儲零元素，因此采用壓縮存儲的方法更為合適。常見的壓縮存儲方法有：壓縮稠密行（CSR）、壓縮稠密列（CSC）、坐標(biāo)列表（COO）等。

a. 對角矩陣的壓縮存儲

【數(shù)據(jù)結(jié)構(gòu)】數(shù)組和字符串（二）：特殊矩陣的壓縮存儲：對角矩陣——一維數(shù)組

b~c. 三角、對稱矩陣的壓縮存儲

【數(shù)據(jù)結(jié)構(gòu)】數(shù)組和字符串（三）：特殊矩陣的壓縮存儲：三角矩陣、對稱矩陣——一維數(shù)組

d. 稀疏矩陣的壓縮存儲——三元組表

【數(shù)據(jù)結(jié)構(gòu)】數(shù)組和字符串（四）：特殊矩陣的壓縮存儲：稀疏矩陣——三元組表

e. 壓縮稀疏行（Compressed Sparse Row，CSR）矩陣

??壓縮稀疏行（Compressed Sparse Row，CSR）是一種常用的稀疏矩陣存儲格式。CSR存儲格式通過壓縮非零元素的行指針和列索引，以及存儲非零元素的值，來有效地表示稀疏矩陣。它包含以下幾個(gè)關(guān)鍵組成部分：

• row_ptr（行指針數(shù)組）：它是一個(gè)長度為rows + 1的數(shù)組，用于存儲每一行在col_indices和elements數(shù)組中的起始索引位置。row_ptr[i]表示第i行的元素在col_indices和elements數(shù)組中的起始位置，而row_ptr[i+1] - row_ptr[i]表示第i行的非零元素個(gè)數(shù)。
• col_indices（列索引數(shù)組）：它是一個(gè)長度為num_elements的數(shù)組，用于存儲每個(gè)非零元素對應(yīng)的列索引。col_indices[i]表示第i個(gè)非零元素所在的列索引。
• elements（元素?cái)?shù)組）：它是一個(gè)長度為num_elements的數(shù)組，用于存儲每個(gè)非零元素的值。elements[i]表示第i個(gè)非零元素的值。

??CSR存儲格式的主要優(yōu)點(diǎn)是有效地壓縮了稀疏矩陣的存儲空間，只存儲非零元素及其對應(yīng)的行和列信息。此外，CSR格式還支持高效的稀疏矩陣向量乘法和稀疏矩陣乘法等操作。

結(jié)構(gòu)體

typedef struct {int row;int col;int value;
} Element;typedef struct {int rows;int cols;int num_elements;Element* elements;int* row_ptr;int* col_indices;
} CSRMatrix;

• Element 結(jié)構(gòu)體表示矩陣中的一個(gè)元素，包含三個(gè)成員變量：row（行索引）、col（列索引）和 value（元素值）。

• CSRMatrix 結(jié)構(gòu)體表示一個(gè)CSR矩陣，包含了矩陣的行數(shù) rows、列數(shù) cols、非零元素的個(gè)數(shù) num_elements，以及三個(gè)指針成員變量 elements、row_ptr 和 col_indices。

創(chuàng)建CSR矩陣

CSRMatrix createCSRMatrix(int rows, int cols, int num_elements) {CSRMatrix matrix;matrix.rows = rows;matrix.cols = cols;matrix.num_elements = num_elements;matrix.elements = (Element*)malloc(num_elements * sizeof(Element));matrix.row_ptr = (int*)malloc((rows + 1) * sizeof(int));matrix.col_indices = (int*)malloc(num_elements * sizeof(int));return matrix;
}

• createCSRMatrix 函數(shù)用于創(chuàng)建一個(gè)CSR矩陣。
• 接受矩陣的行數(shù)、列數(shù)和非零元素的個(gè)數(shù)作為參數(shù)，并返回創(chuàng)建的CSR矩陣。
• 在函數(shù)內(nèi)部，通過動(dòng)態(tài)內(nèi)存分配分別為 elements、row_ptr 和 col_indices 分配內(nèi)存空間，并將 row_ptr 數(shù)組的所有元素初始化為0，最后返回創(chuàng)建的矩陣。

元素設(shè)置

void setElement(CSRMatrix* matrix, int row, int col, int value) {if (row < 0 || row >= matrix->rows) {printf("Invalid row index.\n");return;}int index = matrix->row_ptr[row];matrix->elements[index].row = row;matrix->elements[index].col = col;matrix->elements[index].value = value;matrix->col_indices[index] = col;matrix->row_ptr[row]++;  // 遞增索引值
}

??setElement 函數(shù)可用于設(shè)置（修改）CSR矩陣中某個(gè)位置的元素值。

• 接受一個(gè)指向CSR矩陣的指針 matrix，以及要設(shè)置的元素的行索引、列索引和值作為參數(shù)。
• 在函數(shù)內(nèi)部，首先檢查行索引是否有效，如果無效則打印錯(cuò)誤信息并返回。
• 然后，根據(jù)行索引找到對應(yīng)行的起始位置，將元素的行索引、列索引和值分別賦給對應(yīng)的矩陣元素，并更新 col_indices 數(shù)組和 row_ptr 數(shù)組中的值。

初始化

void initializeCSRMatrix(CSRMatrix* matrix, int* values, int* row_indices, int* col_indices, int num_elements) {for (int i = 0; i < num_elements; i++) {matrix->elements[i].value = values[i];matrix->elements[i].row = row_indices[i];matrix->elements[i].col = col_indices[i];matrix->col_indices[i] = col_indices[i];matrix->row_ptr[row_indices[i]]++;}int sum = 0;for (int i = 0; i <= matrix->rows; i++) {int temp = matrix->row_ptr[i];matrix->row_ptr[i] = sum;sum += temp;}
}

??initializeCSRMatrix 函數(shù)用于初始化CSR矩陣的數(shù)據(jù)。

• 接受一個(gè)指向CSR矩陣的指針 matrix，以及包含非零元素的值、行索引和列索引的數(shù)組，以及非零元素的個(gè)數(shù)作為參數(shù)。
• 通過遍歷非零元素?cái)?shù)組，將值、行索引和列索引分別賦給對應(yīng)的矩陣元素，并更新 col_indices 數(shù)組和 row_ptr 數(shù)組中的值。row_ptr 數(shù)組的每個(gè)元素表示對應(yīng)行的非零元素在 elements 數(shù)組中的起始位置，通過累加非零元素的個(gè)數(shù)來計(jì)算每行的結(jié)束位置。

打印矩陣

void printCSRMatrix(CSRMatrix matrix) {printf("CSR Matrix:\n");printf("Rows: %d, Cols: %d, Num Elements: %d\n", matrix.rows, matrix.cols, matrix.num_elements);printf("Values: ");for (int i = 0; i < matrix.num_elements; i++) {printf("%d ", matrix.elements[i].value);}printf("\n");printf("Row Pointer: ");for (int i = 0; i <= matrix.rows; i++) {printf("%d ", matrix.row_ptr[i]);}printf("\n");printf("Column Indices: ");for (int i = 0; i < matrix.num_elements; i++) {printf("%d ", matrix.col_indices[i]);}printf("\n");
}
void printMatrixForm(CSRMatrix matrix) {printf("Matrix Form:\n");for (int i = 0; i < matrix.rows; i++) {for (int j = 0; j < matrix.cols; j++) {int value = 0;for (int k = matrix.row_ptr[i]; k < matrix.row_ptr[i + 1]; k++) {if (matrix.elements[k].col == j) {value = matrix.elements[k].value;break;}}printf("%d ", value);}printf("\n");}
}

• printCSRMatrix 函數(shù)用于打印CSR矩陣的信息：它接受一個(gè)CSR矩陣作為參數(shù)，并打印矩陣的行數(shù)、列數(shù)、非零元素的個(gè)數(shù)以及 elements、row_ptr 和 col_indices 數(shù)組的內(nèi)容。
• printMatrixForm 函數(shù)用于以矩陣形式打印CSR矩陣。它接受一個(gè)CSR矩陣作為參數(shù)，并按矩陣的行數(shù)和列數(shù)遍歷矩陣元素，通過遍歷 row_ptr 數(shù)組和 col_indices 數(shù)組來獲取每個(gè)位置的元素值，并打印出矩陣的形式。

銷毀CSR矩陣

void destroyCSRMatrix(CSRMatrix* matrix) {free(matrix->elements);free(matrix->row_ptr);free(matrix->col_indices);matrix->elements = NULL;matrix->row_ptr = NULL;matrix->col_indices = NULL;
}

主函數(shù)

int main() {int rows = 9;int cols = 3;int num_elements = 5;CSRMatrix matrix = createCSRMatrix(rows, cols, num_elements);int col_indices[] = {0, 0, 0, 0, 1};int row_indices[] = {3, 5, 7, 8, 7};int values[] =      {2, 1, 3, 1, 4};initializeCSRMatrix(&matrix, values, row_indices, col_indices, num_elements);printCSRMatrix(matrix);printMatrixForm(matrix);destroyCSRMatrix(&matrix);return 0;
}

代碼整合

#include <stdio.h>
#include <stdlib.h>
#include <string.h>typedef struct {int row;int col;int value;
} Element;typedef struct {int rows;int cols;int num_elements;Element* elements;int* row_ptr;int* col_indices;
} CSRMatrix;CSRMatrix createCSRMatrix(int rows, int cols, int num_elements) {CSRMatrix matrix;matrix.rows = rows;matrix.cols = cols;matrix.num_elements = num_elements;matrix.elements = (Element*)malloc(num_elements * sizeof(Element));matrix.row_ptr = (int*)malloc((rows + 1) * sizeof(int));matrix.col_indices = (int*)malloc(num_elements * sizeof(int));memset(matrix.row_ptr, 0, (rows + 1) * sizeof(int));return matrix;
}
void initializeCSRMatrix(CSRMatrix* matrix, int* values, int* row_indices, int* col_indices, int num_elements) {for (int i = 0; i < num_elements; i++) {matrix->elements[i].value = values[i];matrix->elements[i].row = row_indices[i];matrix->elements[i].col = col_indices[i];matrix->col_indices[i] = col_indices[i];matrix->row_ptr[row_indices[i]]++;}int sum = 0;for (int i = 0; i <= matrix->rows; i++) {int temp = matrix->row_ptr[i];matrix->row_ptr[i] = sum;sum += temp;}
}void setElement(CSRMatrix* matrix, int row, int col, int value) {if (row < 0 || row >= matrix->rows) {printf("Invalid row index.\n");return;}int index = matrix->row_ptr[row];matrix->elements[index].row = row;matrix->elements[index].col = col;matrix->elements[index].value = value;matrix->col_indices[index] = col;matrix->row_ptr[row]++;  // 遞增索引值
}void printCSRMatrix(CSRMatrix matrix) {printf("CSR Matrix:\n");printf("Rows: %d, Cols: %d, Num Elements: %d\n", matrix.rows, matrix.cols, matrix.num_elements);printf("Values: ");for (int i = 0; i < matrix.num_elements; i++) {printf("%d ", matrix.elements[i].value);}printf("\n");printf("Row Pointer: ");for (int i = 0; i <= matrix.rows; i++) {printf("%d ", matrix.row_ptr[i]);}printf("\n");printf("Column Indices: ");for (int i = 0; i < matrix.num_elements; i++) {printf("%d ", matrix.col_indices[i]);}printf("\n");
}
void printMatrixForm(CSRMatrix matrix) {printf("Matrix Form:\n");for (int i = 0; i < matrix.rows; i++) {for (int j = 0; j < matrix.cols; j++) {int value = 0;for (int k = matrix.row_ptr[i]; k < matrix.row_ptr[i + 1]; k++) {if (matrix.elements[k].col == j) {value = matrix.elements[k].value;break;}}printf("%d ", value);}printf("\n");}
}void destroyCSRMatrix(CSRMatrix* matrix) {free(matrix->elements);free(matrix->row_ptr);free(matrix->col_indices);matrix->elements = NULL;matrix->row_ptr = NULL;matrix->col_indices = NULL;
}int main() {int rows = 9;int cols = 3;int num_elements = 5;CSRMatrix matrix = createCSRMatrix(rows, cols, num_elements);int col_indices[] = {0, 0, 0, 0, 1};int row_indices[] = {3, 5, 7, 8, 7};int values[] =      {2, 1, 3, 1, 4};initializeCSRMatrix(&matrix, values, row_indices, col_indices, num_elements);printCSRMatrix(matrix);printMatrixForm(matrix);destroyCSRMatrix(&matrix);return 0;
}