[教育]05 数组和矩阵2012.ppt

* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * 对角矩阵公式 K=2(i-1)+j-1 |i-j|≤1 (k=0,1,2???3n-2) 稀疏矩阵 如果m×n矩阵中只有少量的非零值元素，并且这些非零值元在矩阵中的分布没有一定规律，若定义 称δ为矩阵的稀疏因子，则通常认定 δ≤0.05 的矩阵为稀疏矩阵。 例如稀疏矩阵M 　　　  稀疏矩阵的压缩存储 如果采用二维数组表示稀疏矩阵，则缺点是： 浪费空间。因为存放了大量没有用的零值元素。 浪费时间。指在进行矩阵的运算中进行了很多与零元素的运算。 解决稀疏矩阵存储的办法是：压缩存储。 三元组顺序表存储稀疏矩阵 稀疏矩阵压缩存储的做法是只存放矩阵中的非零值元。以便不作和零值元进行的运算，并易于从一对行列号直接找到矩阵中的元素；易于找到同一行或同一列的非零值元。 三元组顺序表存储稀疏矩阵 一个三元组（i，j，e）唯一确定了稀疏矩阵中的一个非零值元,为此可以用三元组顺序表来表示稀疏矩阵，并且三元组顺序表中的元素是“以行为主”有序排列的。 三元组顺序表的结构定义 　　#define maxsize=12500; 　　 // 假设非零元个数的最大值为12500 　　typedef struct { // 三元组结点结构 　int i, j;　// 非零元的行号和列号 　　　 ElemType e; // 非零元的值 　　} Triple; 　　　　  typedef struct { 　　Triple data[maxsize + 1]; 　 // 非零元三元组表，data[0] 未用 　　int mu, nu, tu;　　　 // 矩阵的行数、列数和非零元的个数 } TSMatrix;　// 三元组顺序表 M 的三元组顺序表 例5-1 三元组求稀疏矩阵的转置运算 解题分析 假设前面所列举的矩阵M的转置矩阵为T，则按照三元组顺序表存储结构的定义，得到 T的三元组顺序表。 T的三元组顺序表 三元组转置运算，有两种方法 （1）低效三元组矩阵转置算法 按照T.data中的次序依次在M.data 中查找后转置。 for (col=1; col=nu; ++col) for (row=1; row=mu; ++row) T[col][row] = M[row][col]; 其时间复杂度为 O(mu×nu). 低效三元组转置运算 由于三元组表中元素的顺序约定为以行序为主序，即在 T 中非零元的排列次序是以它们在 M 中的列号为主序的。因此转置的主要操作就是要确定M中的每个非零元在T的三元组顺序表中的位序，即分析两个矩阵中值相同的非零元分别在 M.data 和 T.data 中的位序之间的关系是什么。 例如：M.data 中第2个元素(1,5,-7)转置到T中的位序为4，为什么？因为该元在M中的列号为5，行号为1，又 M 中前4列中非零元的总数为3。换句话说，T 中前4行中只有3个非零元，而值为-7的非零元是 T 中第5行的第一个非零元，当然在 T.data 中应该位居第4。 低效三元组矩阵转置算法 （2）高效的三元组矩阵转置算法 直接按照M.data中的次序依次进行转置。 操作步骤为： 1.求 M 矩阵的每一列中非零元的个数 　　 for (col=1; col=M.nu; ++col) num[col] = 0; for (t=1; t=M.tu; ++t) ++num[M.data[t].j]; 2.确定T的每一行中第一个非零元在 T.data 中的序号 cpot[1] = 1; for (col=2; col=M.nu; ++col