稀疏矩阵转置.ppt

一、三元组顺序表 类型定义 矩阵转置 稀疏矩阵转置 快速稀疏矩阵转置 多媒体演示 描述稀疏矩阵转置的过程演示在CD 算法分析(M--T) q=0; 以原始矩阵的列K(1---M.nu)开始查询并转换 1)从第一列开始,扫描一切非零的数据总数目为M.tu(p=0…M.nu-1) M.data[p].j==K的话,则将M.data[p]-?T.data[q]转换,其中变换其(I,j,data)—(j,I,data),并且p++,q++; 如果M.data[p].j!=K时,p++ K++; 2)从第二列开始,扫描一切非零的数据总数目为M.tu(p=0…M.nu-1) M.data[p].j==K的话,则将M.data[p]-?T.data[q]转换,其中变换其(I,j,data)—(j,I,data),并且p++,q++; 如果M.data[p].j!=K时,p++ …… 规律：循环执行为O(M.nu*M.tu) 描述快速转置算法 见电子书22-42页参考课件 for (i=1; i=m1; ++i) for (j=1; j=n2; ++j) { Q[i][j]=0; for(k(0---n1-1) Q[i][j]+=M[i][k]*N[k][j] 稀疏矩阵相乘的规则 对于M,N矩阵求出其Rpos值 从M.mu行开始运算（arow) M.data[p].j N.data.i== M.data[p].j M的第arrow行的所有非零 P:M.rpos[arrow]…. M.rpos[arrow+1]-1 M.data[p].j 列 N的M.data[p].j 行的非零元素乘 与 求出以此列为N的行号的所有非零元素 出…. * 稀疏矩阵 所谓稀疏矩阵,是指矩阵中有大部分的值相同或值为零的元素,且这些元素的分布没有规律. 只需存储非零元,或再用一个单元存储值相同的元素 以常规方法，即以二维数组表示 高阶的稀疏矩阵时产生的问题: 1) 零值元素占了很大空间; 2) 计算中进行了很多和零值的运算， 遇除法，还需判别除数是否为零; 1) 尽可能少存或不存零值元素; 解决问题的原则: 2) 尽可能减少没有实际意义的运算; 3) 操作方便; 即: 能尽可能快地找到 与下标值 (i, j) 对应的元素; 能尽可能快地找到 同一行或同一列的非零值元; 随机稀疏矩阵的压缩存储方法: 一、三元组顺序表 二、行逻辑联接的顺序表 三、 十字链表 #define MAXSIZE 12500 typedef struct { int i, j; //该非零元的行下标和列下标 ElemType e; // 该非零元的值 } Triple; // 三元组类型 一、三元组顺序表 typedef union { Triple data[MAXSIZE + 1]; int mu, nu, tu; } TSMatrix; // 稀疏矩阵类型 可以这样存储 18 2 5 15 1 6 -7 4 6 24 3 4 14 6 3 -3 1 3 9 3 1 12 2 1 e j i 8 7 6 tu nu mu 行数 列数 元素数值 所在行 所在列 元素值 保持行序 如何求转置矩阵？ 用“三元组”表示时如何实现？ 1 2 14 1 5 -5 2 2 -7 3 1 36 3 4 28 2 1 14 5 1 -5 2 2 -7 1 3 36 4 3 28 用常规的二维数组表示时的算法 其时间复杂度为: O(mu×nu) for (col=1; col=nu; ++col) for (row=1; row=mu; ++row) T[col][row] = M[row][col]; 实现三元组表存储的稀疏矩阵的转置运算 18 2 5 15 1 6 -7 4 6 24 3 4 14 6 3 -3 1 3 9 3 1 12 2 1 v j i 8 7 6 tu nu mu 18 5 2 15 6 1 -7 6 4 24 4 3 14 3 6 -3 3 1 9 1 3 12 1 2 v j i 8 6 7 tu nu mu 24 4 3 -7 6 4 14 3 6 9 1 3 18 5 2 12 1 2 15 6 1 -3 3 1 v j i 8 6 7 tu nu mu 18 2 5 1