|
|
知识路径: > 计算机科学基础 > 常用数据结构 > 数组 > 数组和矩阵 >
|
相关知识点:4个
|
|
|
|
稀疏矩阵指矩阵中非零元素很少,且分布没有规律。设二维数组Am×n有N个非零元素,N<<m*n,但它不是特殊矩阵(如对角矩阵)。对稀疏矩阵而言,只存储非零元素。用线性表存储稀疏矩阵的非零元素,除非零元素的值外,还应有一些辅助信息。顺序存储节省存储空间,但插入和删除不方便。稀疏矩阵的表示可用三元组[i,j,aij]来表示,其中,i、j、aij分别表示行列位置和值。由此可见,稀疏矩阵可由表示非零元的三元组和其行列数唯一确定。节点中除元素值外,还有元素所在行、列信息。节点结构如下:
|
|
|
|
对如下图所示的稀疏矩阵,其三元组表示为(1, 2, 12),(1, 3, 9),(3, 1, -3),(3, 6, 14),(4, 3, 24),(5, 2, 18),(6, 1, 15),(6, 3, -7)。
|
|
|
|
|
|
|
可利用三元组表实现矩阵的运算(以行序为主序),如矩阵的转置和矩阵的相乘等。
|
|
|
对于矩阵am×n转置为bn×m,使a[i, j]=b[j, i],其中,1≤i≤n, 1≤j≤m,其实现步骤如下。
|
|
|
|
|
|
按a.data中三元组的次序进行转置,将转置后的三元组置入b中恰当的位置,如能预先确定M中每一列的第一个非零元在b.data中的相应位置,则转置时可直接放入b.data恰当的位置。先求每一列非零元的个数,设num、cpot两个向量,num[col]表示M中第col列非零元个数,cpot[col]的初值表示M中第col列第一个非零元在b.data中的位置。
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|