第五章 矩阵.ppt

第五章数组 5 1数组的类型定义 5 3矩阵的压缩存储 5 2数组的顺序表示和实现 5 1数组的类型定义 ADTArray 数据对象 D aj1 j2 ji jn ji 0 bi 1 i 1 2 n 数据关系 R R1 R2 Rn Ri 0 jk bk 1 1 k n且k i 0 ji bi 2 i 2 n ADTArray n数组的维数 bi数组第i维的长度 二维数组的定义 数据对象 D aij 0 i b1 1 0 j b2 1 数据关系 R ROW COL ROW 0 i b1 1 0 j b2 2 COL 0 i b1 2 0 j b2 1 R1R2 基本操作 InitArray A n bound1 boundn DestroyArray A Value A e index1 indexn Assign A e index1 indexn InitArray A n bound1 boundn 操作结果 若维数n和各维长度合法 则构造相应的数组A 并返回OK DestroyArray A 操作结果 销毁数组A Value A e index1 indexn 初始条件 A是n维数组 e为元素变量 随后是n个下标值 操作结果 若各下标不超界 则e赋值为所指定的A的元素值 并返回OK Assign A e index1 indexn 初始条件 A是n维数组 e为元素变量 随后是n个下标值 操作结果 若下标不超界 则将e的值赋给所指定的A的元素 并返回OK 5 2数组的顺序表示和实现 类型特点 只有引用型操作 或改变元素值的操作 没有 改变结构的 加工型操作 2 数组是多维的结构 而存储空间是一个一维的结构 有两种顺序映象的方式 1 以行序为主序 低下标优先 2 以列序为主序 高下标优先 5 2数组的顺序表示和实现 由于计算机内存结构是一维的 线性的 因此 用一维内存存放多维数组就必须按某种次序将数组元素排成一个线性序列 然后将这个线性序列顺序存放在存储器中 行优先顺序也称为低下标优先或左边下标优先于右边下标 具体实现时 按行号从小到大的顺序 先将第一行中元素全部存放好 再存放第二行元素 第三行元素 依次类推 列优先顺序也称为高下标优先或右边下标优先于左边下标 具体实现时 按列号从小到大的顺序 先将第一列中元素全部存放好 再存放第二列元素 第三列元素 依次类推 称为基地址或基址 二维数组A中任一元素ai j的存储位置LOC i j LOC 0 0 b2 i j L 存储映象 存储映象 三维数组 a j1 j2 j3 0 j1 10 j2 20 j3 1以行序为主序 以列序为主序 推广到一般情况 可得到n维数组数据元素存储位置的映象关系 行序为主序 称为n维数组的映象函数 数组元素的存储位置是其下标的线性函数 随机存储结构 其中cn L ci 1 bi ci 1 i n LOC j1 j2 jn LOC 0 0 0 ciji i 1 n 5 3稀疏矩阵的压缩存储 假设m行n列的矩阵含t个非零元素 则称为稀疏因子 通常认为 0 05的矩阵为稀疏矩阵 何谓稀疏矩阵 以常规方法 即以二维数组表示高阶的稀疏矩阵时产生的问题 1 零值元素占了很大空间 2 计算中进行了很多和零值的运算 遇除法 还需判别除数是否为零 1 尽可能少存或不存零值元素 解决问题的原则 2 尽可能减少没有实际意义的运算 3 操作方便 即 能尽可能快地找到与下标值 i j 对应的元素 能尽可能快地找到同一行或同一列的非零值元 1 特殊矩阵非零元在矩阵中的分布有一定规则例如 三角矩阵对角矩阵 2 随机稀疏矩阵非零元在矩阵中随机出现 有两类稀疏矩阵 随机稀疏矩阵的压缩存储方法 一 三元组顺序表 二 行逻辑联接的顺序表 三 十字链表 defineMAXSIZE12500typedefstruct inti j 该非零元的行下标和列下标ElemTypee 该非零元的值 Triple 三元组类型 一 三元组顺序表 typedefunion Tripledata MAXSIZE 1 intmu nu tu 行数列数非零元数 TSMatrix 稀疏矩阵类型 如何求转置矩阵 用常规的二维数组表示时的算法 其时间复杂度为 O mu nu for col 1 col nu col for row 1 row mu row T col row M row col 用三元组表示的稀疏矩阵的转置 1 将矩阵的行列值互换 2 将每个三元组中的i和j相互调换 3 重排三元组之间的次序 用 三元组 表示时如何实现 1214 15 5 22 7 3136 3428 2114 51 5 22 7 1336 4328 a data b data 第一种算法 按照b data中三元组的次序依次在a data中找到对应的三元组进行转置 即按照矩阵a的列序来转置每次扫描矩阵a中的所有三元组 依次找所有第一列的元素 进行转置 再找所有第二列的元素进行转置 依次类推 因为a中是以行序为主序存放非零元 扫描得到的恰是b data中应有的顺序 statustransmatrix tsmatrixM tsmatrix transmatrix 时间复杂度 O nu tu 想在M转置时就知道每个三元组在T中的存储位置 改进方法 首先应该确定T中每行第一个非零元的存储位置即M中每一列的第一个非零元转置后在三元组T中的位置 确定M中每一列的第一个非零元在三元组T中的位置 如何求位置 1 2 15 2 1 15 若知道转置后第一行有几个非零元即可 1 5 5 5 1 5 若知道转置后前四行共有几个非零元即可 求T中任一行第一个非零元的位置 若知道在它前面的第一行有a1个非零元 第二行有a2个非零元 第k行有ak个非零元 它可能就应该放在a1 a2 ak 1的位置上 求 M中每列有多少非零元 表示矩阵M中第col列中非零元素个数就是T中第col行中的非零元素个数 cpot 1 1 cpot col cpot col 1 num col 1 其中 2 col M nu 如何求M中每一列的第一个非零元在三元组T中的位置 51 5 22 7 4328 2115 1336 M T M的col列就是T中的col行 2 4 4 5 6 StatusFastTransposeSMatrix TSMatrixM TSMatrix FastTransposeSMatrix 转置矩阵元素 用下标表示列号 Col M data p j q cpot col q为存放位置T data q i M data p j T data q j M data p i T data q e M data p e cpot col M中的p应该放在T中的q位置 分析算法FastTransposeSMatrix的时间复杂度 时间复杂度为 O M nu M tu for col 1 col M nu col for t 1 t M tu t for col 2 col M nu col for p 1 p M tu p 三元组顺序表又称有序的双下标法 它的特点是 非零元在表中按行序有序存储 因此便于进行依行顺序处理的矩阵运算 然而 若需随机存取某一行中的非零元 则需从头开始进行查找 二 行逻辑链接的顺序表 defineMAXMN500typedefstruct Tripledata MAXSIZE 1 非零元三元组表intrpos MAXMN 1 各行第一个非零元的位置intmu nu tu 矩阵的行数 列数和非零元个数 RLSMatrix 行逻辑链接顺序表类型 修改前述的稀疏矩阵的结构定义 增加一个数据成员rpos 其值在稀疏矩阵的初始化函数中确定 改进方法 首先应该确定M每一列的第一个非零元在三元组T中的位置 指示T中每一行的第一个非零元素在T data中的位置 51 5 22 7 4328 2115 1336 T rpos row 1 2 4 4 5 例如 给定一组下标 求矩阵的元素值 ElemTypevalue RLSMatrixM intr intc p M rpos r while M data p i r value 矩阵乘法的经典算法 for i 1 i m1 i for j 1 j n2 j Q i j 0 for k 1 k n1 k Q i j M i k N k j 其时间复杂度为 O m1 n2 n1 当M i k N k j 均不为零时 乘法才有意义所以只要对两个矩阵的非零元操作即可 使用行逻辑链接顺序表如何完成矩阵相乘 如何由M的行逻辑链接顺序表和N的行逻辑链接顺序表得到Q的行逻辑链接顺序表 Q的行逻辑链接顺序表应当按行号有序存储 只要按M的行号顺序进行处理即可计算Q 1 用到的总是M 1 然后才是Q 2 用到的是M 2 所以是依次的用到M的第一行 第二行 Q 1 1 M 1 1 N 1 1 M 1 2 N 2 1 M 1 n1 N m2 1 Q 1 2 M 1 1 N 1 2 M 1 2 N 2 2 M 1 n1 N m2 2 Q 1 n2 M 1 1 N 1 n2 M 1 2 N 2 n2 M 1 n1 N m2 n2 计算Q 1 用到的总是M 1 每个M第一行中的元素都被反复存取了n2次 把M 1 1 取出来就把它应当参与的运算一次算完如框所示 Q 1 1 M 1 1 N 1 1 M 1 2 N 2 1 M 1 n1 N m2 1 Q 1 2 M 1 1 N 1 2 M 1 2 N 2 2 M 1 n1 N m2 2 Q 1 n2 M 1 1 N 1 n2 M 1 2 N 2 n2 M 1 n1 N m2 n2 Q 1 1 M 1 1 N 1 1 M 1 2 N 2 1 M 1 n1 N m2 1 Q 1 2 M 1 1 N 1 2 M 1 2 N 2 2 M 1 n1 N m2 2 Q 1 n2 M 1 1 N 1 n2 M 1 2 N 2 n2 M 1 n1 N m2 n2 ctemp 把M 1 1 取出来就把它应当参与的运算一次算完如框所示 这是计算Q 1 中的某个分量 保留在数组中 Q 1 1 M 1 1 N 1 1 M 1 2 N 2 1 M 1 n1 N m2 1 Q 1 2 M 1 1 N 1 2 M 1 2 N 2 2 M 1 n1 N m2 2 Q 1 n2 M 1 1 N 1 n2 M 1 2 N 2 n2 M 1 n1 N m2 n2 ctemp 把M 1 1 取出来就把它应当参与的运算一次算完如框所示 这是计算Q 1 中的某个分量 保留在数组中 这样去处理M 1 2 M 1 3 M 1 n1 得到的均为分量 将向数组的对应单元累加 得出最后结果 M 020030300 N 032410000 2 Q 423 400 30 0 4 0 8 6 M data N data Q data 累加器Q的列数 p q 0 2 5 0 4 M的第一行处理完毕 Q 1 1 Q 1 2 4 2 M的第二行处理完毕 3 4 Q 2 1 Q 2 2 请注意 1 指针p顺序处理M中的三元组即可2 对于M的每个非零元 据其列号k 寻找N中的可乘三元组 利用N rpos k 和N rpos k 1 1确定在N中的搜寻范围 3 为得到Q的每一行需用累加器ctemp 保存中间结果 等M中的一行处理完 才能得到Q此行的最后结果 把非零项写入Q data 即可 注 在此过程中还可以完成Q rpos 的初始化 Q初始化 ifQ是非零矩阵 逐行求积for arow 1 arow M mu arow 处理M的每一行ctemp 0 累加器清零计算Q中第arow行的积并存入ctemp 中 将ctemp 中非零元压缩存储到Q data forarow if 两个稀疏矩阵相乘 Q M N 的过程可大致描述如下 StatusMultSMatrix RLSMatrixM RLSMatrixN RLSMatrix MultSMatrix ctemp 0 当前行各元素累加器清零Q rpos arow Q tu 1 同时完成Q rpos 的初始化for p M rpos arow pMAXSIZE returnERROR Q data Q tu arow ccol ctemp ccol if 处理的每一行 M rest M 020030300 N 032410000 2 Q 423 400 30 0 4 0 8 6 M data N data Q data 累加器Q的列数 p q 0 2 5 0 4 M的第一行处理完毕 Q 1 1 Q 1 2 0 4 4 0 8 6 2 M的第二行处理完毕 3 4 Q 2 1 Q 2 2 分析上述算法的时间复杂度 累加器ctemp初始化的时间复杂度为 M mu N nu 求Q的所有非零元的时间复杂度为 M tu N tu N mu 进行压缩存储的时间复杂度为 M mu N nu 总的时间复杂度就是 M mu N nu M tu N tu N mu 若M是m行n列的稀疏矩阵 N是n行p列的稀疏矩阵 则M