专做化妆品的网站,wordpress5更换后台主题,泰安新浪乐居房产网,WordPress使用微博外链1. 什么是稀疏矩阵
稀疏矩阵是指矩阵中大多数元素为零的矩阵。
从直观上讲#xff0c;当元素个数低于总元素的30%时#xff0c;这样的矩阵被称为稀疏矩阵。
由于该种矩阵的特点#xff0c;我们在存储这种矩阵时#xff0c;如果直接采用二维数组#xff0c;就会十分浪费…1. 什么是稀疏矩阵
稀疏矩阵是指矩阵中大多数元素为零的矩阵。
从直观上讲当元素个数低于总元素的30%时这样的矩阵被称为稀疏矩阵。
由于该种矩阵的特点我们在存储这种矩阵时如果直接采用二维数组就会十分浪费空间因为其中大多数元素都是重复的零。
稀疏矩阵的三元组表表示法
对于稀疏矩阵的压缩存储采用只存储非零元素的方法。
由于稀疏矩阵中非零元素的分布没有规律因此在存储非零元素值得同时还必须存储该非零元素在矩阵中的位置信息即行号和列号。
也就是采用三元组的结构存储 为处理方便将稀疏矩阵中非零元素对应的三元组行号依次增大进行存放。
这也就解释了为什么稀疏矩阵是非零元素占比小于30%的矩阵。
因为采取三元组的结构储存一个元素会占用三个单元的空间只有当零元素占比小于30%时这种存储结构才能在空间上有较明显的收益。
稀疏矩阵三元组表的类型定义
#define ElementType int//一个三元组元素
typedef struct
{int row, col;//非零元素行下标和列下标ElementType e;
}Triple;//稀疏矩阵
typedef struct
{Triple* data;//非零元素的三元组表int m, n, len;//矩阵行数列数非零元素个数int capacity;//容量
}TSMatrix; 2. 对稀疏矩阵进行基本操作
//初始化稀疏矩阵
void TSMInite(TSMatrix* ps)
{assert(ps);ps-data NULL;ps-m TSM_ROWMAX;ps-n TSM_COLMAX;ps-len 0;ps-capacity 0;
}//销毁稀疏矩阵
void TSMDestroy(TSMatrix* ps)
{assert(ps);free(ps-data);ps-data NULL;ps-len 0;ps-capacity 0;
}//检查扩容
void CheckCapacity(TSMatrix* ps)
{assert(ps);if(ps-capacity ps-len){int newcapacity ps-capacity 0 ? 4 : ps-capacity * 2;Triple* tmp (Triple*)realloc(ps-data, newcapacity * sizeof(Triple));if(tmp NULL){perror(realloc);exit(-1);}ps-data tmp;ps-capacity newcapacity;}
}//插入元素
void ElemInsert(TSMatrix* ps, Triple x)
{assert(ps);CheckCapacity(ps);if(ps-len 0){ps-data[ps-len] x;}if(x.row ps-data[0].row){for(int j ps-len; j 0; j--){ps-data[j] ps-data[j - 1];}ps-data[0] x;}elsefor(int i 0; i ps-len; i){if(x.row ps-data[i].rowx.row ps-data[i 1].row||i ps-len - 1){for(int j ps-len; j i 1; j--){ps-data[j] ps-data[j - 1];}ps-data[i 1] x;break;}}ps-len;
}//打印元素
void TSMPrint(TSMatrix ps)
{for(int i 0; i ps.len; i){printf(row %d col %d e %d\n, ps.data[i].row, ps.data[i].col, ps.data[i].e);}printf(\n);
}
这些函数基本是以顺序表操作函数为蓝本写的目的是为了方便我们实现稀疏矩阵的转置。
只不过插入元素的函数需要确保插入之后三元组的行号是依次递增的。
3. 稀疏矩阵的转置
需要强调的是矩阵的常规存储是二维的而三元组表存储是一维的由于矩阵存储结构的变化也带来了运算方法的不同必须认真分析。
3.1 稀疏矩阵转置的经典算法
void TransMatrix(ElementType source[m][n], ElementType dest[n][m])
{int i, j;for(i 0; i m; i)for(j 0; j n; j)dest[j][i] source[i][j];
}
这个算法是针对传统的二维数组的存储方式。
3.2 用三元组表实现稀疏矩阵的转置
假设A和B是稀疏矩阵source和dest的三元组表则实现转置的简单方法如下 1. 三元组表A的行列互换就可以得到B中的元素。 2. 转置后的矩阵的三元组表B中的三元组不是以“行序为主序”存储的为保证三元组表B也是以“行序为主序”进行存放的则需要对该三元组表B按行下标即A的列下标以递增顺序重新排列。 上图中的步骤很容易实现但是重新排序势必会大量移动元素从而影响算法的效率。
为避免上述简单转置算法中重新排序引起的元素移动可采取接下来的两种处理方法。
3.2.1 列序递增转置法
算法思想
这里的列序指的是A的列也就是按照A的列序来将元素转置到B中。
即将A的第一列全部转置到B中得到B的第一行后再将A的第二列全部转置到B中以此类推。
代码
//列序递增转置法
void TSMSwitch1(TSMatrix A, TSMatrix* B)
{assert(B);TSMDestroy(B);B-data (Triple*)malloc(A.capacity * sizeof(Triple));B-capacity A.capacity;B-len A.len;B-m A.n;B-n A.m;int j 0;//记录B当前空位for(int k 0; k A.n; k){for(int i 0; i A.len; i){if(A.data[i].col k){B-data[j].row A.data[i].col;B-data[j].col A.data[i].row;B-data[j].e A.data[i].e;j;}}}
}
分析
这种算法确实使得我们不用再单独进行排序但是双重循环依然造成了较高的时间复杂度OA.n * A.len。
那么我们能否降低该算法的时间复杂度呢
如果能那么我们的着手点一定是想办法优化掉二重循环。
可以发现该算法中二重循环出现的原因在于必须将A的第一列全部转置之后才能转置第二列每列转置需要重新扫描一次A。
那么我们有没有办法使得各列同时进行存放呢这样就只用扫描一次A了。
3.2.2 一次定位快速转置法
算法思想
如果我们知道A的每一列有多少个元素那么就可以推知B中每一行的起始位置。
这样一来假如某次在A中扫描到第n列的元素我们就可以直接将其放到B中的第n行所在位置而不用先放完一列再放下一列。
所以我们准备进行三次循环 1. 定义数组num数组的下标表示A的列遍历A并将每一列元素的个数记录在num中。 2. 定义数组position数组下标表示B的行遍历position根据A每一列元素的个数得到对应行的起始位置。 3. 遍历A根据position数组将A中的元素转置到B的对应行。 代码
//一次定位快速转置算法
void TSMSwitch2(TSMatrix A, TSMatrix* B)
{assert(B);TSMDestroy(B);B-data (Triple*)malloc(A.capacity * sizeof(Triple));B-capacity A.capacity;B-len A.len;B-m A.n;B-n A.m;int num[B-m];int position[B-m];memset(num, 0, B-m * sizeof(int));memset(num, 0, B-m * sizeof(int));for(int i 0; i A.len; i){num[A.data[i].col];}position[0] 0;for(int row 1; row B-m; row){position[row] position[row - 1] num[row - 1];}for(int i 0; i A.len; i){B-data[position[A.data[i].col]].row A.data[i].col;B-data[position[A.data[i].col]].col A.data[i].row;B-data[position[A.data[i].col]].e A.data[i].e;position[A.data[i].col];}
}
算法分析
显然一次定位快速转置算法的时间效率要高得多它在时间性能上由于列序递增转置法但在空间耗费上增加了两个辅助向量空间即num和position。
由此可见算法在时间上的节省是以更多的储存空间为代价的。
