数据结构与算法 三元组转置算法（稀疏矩阵） |
您所在的位置：网站首页 › 三元矩阵的转置 › 数据结构与算法 三元组转置算法（稀疏矩阵） |
数据结构与算法 三元组转置算法（稀疏矩阵）
|
三元组稀疏矩阵转置算法及相关讨论
本篇文章介绍稀疏矩阵中的数据如何存储的更加高效，以及矩阵转置的优良算法------三元组稀疏矩阵转置算法。 稀疏矩阵定义：矩阵中非零元素的个数远远小于矩阵元素的总数，并且非零元素的分布没有规律，通常认为矩阵中非零元素的总数比上矩阵所有元素总数的值小于等于0.05时，则称该矩阵为稀疏矩阵(sparse matrix)。 稀疏因子：矩阵中的有效数据量 / 矩阵总元素量 * 100 % 稀疏因子小于5%的矩阵称为稀疏矩阵。 假设一个 M * N 阶，稀疏因子为 3%的稀疏矩阵，若用全存储方式申请空间，则空间利用率只有 3%。 这空间利用率太低了！那么如何高效利用空间？首要解决存储方式：仅存储有效数据。 为了不丢失信息，需要存储数据和数据所在位置信息。 有两种方式可以完成，三元组法和十字交叉链表法。今天介绍三元组法~ 三元组方式表达稀疏矩阵关于用三元组方式表达稀疏矩阵，有一个默认的原则: 在三元组数组中，数据一定(必须)是按照行下标升序，行下标相同，则，按列下标升序排列。 为了简化问题，有关initSparsellatrix()函数的，由用户从键盘输入稀疏矩阵数据的操作中要求，用户必须保证按照前述的原则录入数据。 假设这是我们要存储的稀疏矩阵（6行7列）  
下面我们用三个信息量（行 列 值）来表示矩阵中的有效元素。从而去构造一个三元组数组。 " | " 左边表示有效元素顺序下标，" | " 右边表示该有效元素的行、列、值（参考上图右）。 只要用户按照上述要求输入稀疏矩阵行阶、列阶、有效元素个数，以及右图的三个信息量，就可以得到稀疏矩阵。我们主要通过show()函数输出矩阵，代码在最下面~ 三元组稀疏矩阵转置算法 
矩阵转置运算，将生成一个新的矩阵(应该申请一个新的矩阵控制头， 和一组新的三元组数组) ; 原矩阵与目标矩阵的行阶、列阶，互换。 普通方法： 若是用普通的方法则需要先将原三元组数组每个元素中的行与列的值分别赋值给新三元组数组列与行的值，然后再把原三元组数组每个元素中存储的数据值赋值给新三元组数组的数据值；再将原三元组的数据按照行下标升序，（若行下标相同，则按列下标升序排列。）这样的方法重新排序，才能生成处理后的三元组数组，再调用show函数（将三元组数组输出成稀疏矩阵形式），就可以实现稀疏矩阵的转置。 但，众所周知，排序是很浪费时间的操作！如果数据量庞大，那么它将耗费大量时间！降低整个操作效率！所以这里就要重点介绍这个神奇的三元组转置矩阵算法啦！它的构思是真的很巧妙啊~ 三元组稀疏矩阵转置算法分析：（可直接看图片手工过程） 原矩阵的列变成了现矩阵的行，所以我们将以现矩阵的行下标定位，比如第一行有三个有效元素，那么第二行的第一个元素下标就要从现数组下标为3的地方开始存储（前面三个元素存储下标为0，1，2），同理若第二行有两个有效元素的话，第三行的第一个有效元素就要从现数组下标为5的地方开始存储。这些个下标定位的值将会被我们存进我们申请好的一个定位数组中！ 当现数组所有行下标定位计算完成后，我们再去遍历一遍原数组。遍历时，将原三元组数组每个元素中的行与列的值分别赋值给新三元组数组列与行的值，然后再把原三元组数组每个元素中存储的数据值赋值给新三元组数组的数据值。最重要的一步操作是，当遍历到每一个原三元组元素时，需要将定位数组|以这个原三元组元素的列下标|为下标的数值|加一，否则下一个数据会覆盖上一个数据！ 如果有兴趣或者觉得文字写的繁琐，可以看下手工过程~懂了的话直接跳过哦！ 
好了，最后一步就是调用show()函数，得到转置后的稀疏矩阵！ 有没有发现它的条件（行升序，列升序）成了它最大的优势，我们只需给下标定位，不需要管中间存储元素的顺序，因为原三元组的行和列都是按照升序排列的。所以按照顺序遍历下来，现三元组的元素下标一定也是符合条件的！时间复杂度O(2n)。 上代码! sparseMatrix.h #ifndef _MEC_SPARSE_MATRIX #define _MEC_SPARSE_MATRIX #include "mec.h" typedef int USER_TYPE; typedef struct TRIPLE { int row; int col; USER_TYPE value; }TRIPLE; typedef struct SPARSE_MATRIX { TRIPLE *triple; int maxRow; int maxCol; int count; // 有效元素个数 }SPARSE_MATRIX; boolean initSparseMatrix(SPARSE_MATRIX **m, int maxRow, int maxCol, int count); void destorySparseMatrix(SPARSE_MATRIX **m); void showSparseMatrix(const SPARSE_MATRIX *m); SPARSE_MATRIX *revangeMatrix(const SPARSE_MATRIX *sm); #endifsparseMatrix.c #include #include #include "mec.h" #include "sparseMatrix.h" boolean initSparseMatrix(SPARSE_MATRIX **m, int maxRow, int maxCol, int count) { if (NULL == m || NULL != *m || maxRow maxCol = maxCol; (*m)->count = count; // TODO 实现从键盘输入count个有效数据，每个数以三元组方式录入 // 用户输入数据时，由用户自己保证数据录入时的顺序！ int index; int row; int col; USER_TYPE value; for (index = 0; index triple[index].row = row; (*m)->triple[index].col = col; (*m)->triple[index].value = value; } return TRUE; } void destorySparseMatrix(SPARSE_MATRIX **m) { if (NULL == m || NULL == *m) { return; } free((*m)->triple); free(*m); *m = NULL; } /* 6 7 11 0 0 7 0 1 3 0 3 4 1 0 2 1 6 5 2 4 8 3 1 6 4 0 3 4 1 7 4 6 9 5 4 1 typedef struct SPARSE_MATRIX { TRIPLE *triple; int maxRow; 6 int maxCol; 7 int count; 11 }SPARSE_MATRIX; typedef struct TRIPLE { int row; int col; USER_TYPE value; }TRIPLE; */ void showSparseMatrix(const SPARSE_MATRIX *m) { // 这里应充分利用三元组表示稀疏矩阵的基本原则： // 按行升序；行相同，按列升序。 int row; int col; int index = 0; int value; for (row = 0; row maxRow; row++) { for (col = 0; col maxCol; col++) { if (row == m->triple[index].row && col == m->triple[index].col) { value = m->triple[index++].value; } else { value = 0; } printf("%5d", value); } printf("\n"); } } static void getRowElementCount(int *array, const SPARSE_MATRIX *ma) { int index; for (index = 0; index count; index++) { ++array[ma->triple[index].col + 1]; } } static void rollAdd(int *array, int count) { int index; for (index = 1; index maxCol + 1; int index; int t; indexArray = (int *) calloc(sizeof(int), count); getRowElementCount(indexArray, resMatrix); rollAdd(indexArray, count); for (index = 0; index count; index++) { t = resMatrix->triple[index].col; tagMatrix->triple[indexArray[t]].row = resMatrix->triple[index].col; tagMatrix->triple[indexArray[t]].col = resMatrix->triple[index].row; tagMatrix->triple[indexArray[t]].value = resMatrix->triple[index].value; indexArray[t]++; } free(indexArray); } SPARSE_MATRIX *revangeMatrix(const SPARSE_MATRIX *sm) { SPARSE_MATRIX *result = NULL; result = (SPARSE_MATRIX *) calloc(sizeof(SPARSE_MATRIX), 1); result->triple = (TRIPLE *) calloc(sizeof(TRIPLE), sm->count); result->maxRow = sm->maxCol; result->maxCol = sm->maxRow; result->count = sm->count; revange(sm, result); return result; }test.c #include #include "sparseMatrix.h" int main() { int maxRow; int maxCol; int count; SPARSE_MATRIX *smOne = NULL; SPARSE_MATRIX *smTwo = NULL; printf("请输入稀疏矩阵行阶、列阶和有效元素个数:"); scanf("%d %d %d", &maxRow, &maxCol, &count); initSparseMatrix(&smOne, maxRow, maxCol, count); showSparseMatrix(smOne); smTwo = revangeMatrix(smOne); printf("转置后:\n"); showSparseMatrix(smTwo); destorySparseMatrix(&smOne); destorySparseMatrix(&smTwo); return 0; }结果展示： “mec.h” 要看的话点这里！ 直接滑到底看~ |
【本文地址】
今日新闻 |
推荐新闻 |