【数据结构原理】稀疏矩阵 - THE SPARSE MATRIX 数据结构

目录

稀疏矩阵（THE SPARSE MATRIX）
0x00 ADT
0x01 ADT - 稀疏矩阵
0x02 稀疏矩阵的表示
0x03 矩阵的转置 - Transposing A Matrix
0x04 矩阵乘
稀疏矩阵（THE SPARSE MATRIX） 0x00 ADT
稀疏矩阵：若矩阵
文章图片
中非零元素的个数远小于零元素的个数，我们称
文章图片
为稀疏矩阵
如果用一个二维数组来表示稀疏矩阵，就要用大量的空间来存储相同的值（0），不仅如此，当矩阵很大时，这种实现方式是行不通的，因为大多数编译器对数组的大小都有限制的。

文章图片

0x01 ADT - 稀疏矩阵

文章图片

0x02 稀疏矩阵的表示
我们可以唯一地表示矩阵中的任何元素，我们可以利用 row，col，value 的方式存储和定位稀疏矩阵中的非零元素，这种存储稀疏矩阵的方式称为三元组 Triple。

by a triple .

我们组织三元组，使行指数按升序排列，在具有相同行指数的三元组中，按列指数的升序排列。
为了确保操作能够停止，我们必须知道行和列的数量，以及矩阵中的非零元素的数量。

// Sparse_Matrix Create(max_row, max_col) ::=#define Max_TERMS 101 /* maximum number of terms +1*/ typedef struct { int col; int row; int value; } term; term a[MAX_TERMS];

文章图片

0x03 矩阵的转置 - Transposing A Matrix

<一个简单的算法>
对于每一行的
文章图片

取元素
文章图片
并储存它
作为转置的元素
文章图片

在我们处理完前面的所有元素之前，我们不会确切的知道在转置中吧元素

文章图片

放在了哪里，比如：

文章图片

需要连续的插入。我们必须移动元素以保持顺序正确。
我们可以通过通过使用列的索引来确定元素在矩阵中的位置，来避免这种数据移动。
对于第

文章图片
列的所有元素，将元素

文章图片
放在元素

文章图片
中。

[Program 2.8]

文章图片

时间复杂度：

文章图片

如果

文章图片
，

文章图片
变为

文章图片
。

一个使用密集表示的转置算法

for (j = 0; j < columns; j++) for (i = 0; i < rows; i++) b[j][i] = a[i][j];

时间复杂度：

文章图片

通过使用更多一点的存储空间来实现更好的算法

fast_transpose

该算法，首先确定原始矩阵每一列的元素数量。
该数字给出了转置矩阵中每一行的元素数。

文章图片

时间复杂度：

文章图片

如果

文章图片
，
那么

文章图片
变为

文章图片

使用了额外的数组，row_terms 和 starting_pos 。
如果我们把起始位置放到 row_terms 使用的空间里，我们就可以把空间减少到一个数组。

0x04 矩阵乘法
给出两个矩阵

文章图片
和

文章图片
，其中

文章图片
是

文章图片
，

文章图片
是

文章图片

乘积矩阵

文章图片
为

文章图片
，它的

文章图片
元素为：

文章图片

文章图片

<使用密集表示法的矩阵乘法算法>

for (i = 0; i < rows_a; i++) { for (j = 0; j < cols_b; j++) { sum = 0; for (k = 0; k < cols_a; k++) sum += a[i][k]*b[k][j]; d[i][j] = sum; } }

时间复杂度：

文章图片

注意，两个稀疏矩阵的乘积可能就不再是稀疏的了。例如：
【【数据结构原理】稀疏矩阵 - THE SPARSE MATRIX】

文章图片

[Program 2.10]
矩阵

文章图片
分别存储在数组

文章图片
中，

文章图片
的转置存储在 new_b 中。
使用变的变量：

row - 目前正在与B的列相乘的A的行 row_begin - 当前行的第一个元素在a中的位置 column - 目前正在与A的某一行相乘的B的列 totald - 乘积矩阵D的当前元素数 i, j - 用于连续检查A行和B列中的元素的指针

void mmult(term a[], term b[], term d[]) /* multiply two sparse matrices */ { int i, j, column, totalb = b[0].value, totald = 0; int rows_a = a[0].row, cols_a = a[0].col, totala = a[0].value; int cols_b = b[0].col; int row_begin = 1, row = a[1].row, sum = 0; term new_b[MAX_TERMS]; if (col_a != b[0].row) { fprintf(stderr, “Incompatible matrices\n”); exit(1); } fast_transpose(b, new_b); /* set boundary condition */ a[totala+1].row = rows_a; new_b[totalb+1].row = cols_b; new_b[totalb+1].col = -1; for (i = 1; i <= totala; ) { column = new_b[1].row; for (j = 1; j <= totalb+1; ) { /* multiply row of a by column of b */ if (a[i].row != row) { storesum(d, &totald, row, column, &sum); i = row_begin; for ( ; new_b[j].row == column; j++) ; column = new_b[j].row; } else if (new_b[j].row != column) { storesum(d, &totald, row, column, &sum); i = row_begin; column = new_b[j].row; } else switch (COMPARE(a[i].col, new_b[j].col)) { case –1 : /* go to next term in a */ i++; break; case 0 : /* add terms, go to next term in a and b */ sum += (a[i++].value * new_b[j++].value); break; case 1 : /* go to next term in b */ j++; } } /* end of for j <= totalb+1 */ for ( ; a[i].row == row; i++) ; row_begin = i; row = a[i].row; } /* end of for i <= totala */ d[0].row = row_a; d[0].col = cols_b; d[0].value = https://www.it610.com/article/totald; }

注意，我们在 a 和 new_b 中都引入了一个附加项：

a[totala+1].row = rows_a; new_b[totalb+1].row = cols_b; new_b[totalb+1].col = -1;

时间复杂度
for 循环前：

fast transpose - O(cols_b + totalb) time.

外层 for 循环被迭代了rows_a 次：
在每次迭代中，乘积矩阵D的一行由内部 for 循环计算，在每个迭代中，i或者j两者都增加1，或者i被重置到 row_begin
j 的最大总增量为 totalb+1。那么当第k行被处理时，i最多可以增加几次，i最多被重置到row_begin的cols_b次。因此，i的最大总增量是cols_b-。内层for循环需要