用三元组表示稀疏矩阵的乘法PPT课件

1 用三元组表实现稀疏矩阵的乘法运算 2 两个矩阵相乘也是矩阵的一种常用的运算 设矩阵M是m1 n1矩阵 N是m2 n2矩阵 若可以相乘 则必须满足矩阵M的列数n1与矩阵N的行数m2相等 才能得到结果矩阵Q M N 一个m1 n2的矩阵 数学中矩阵Q中的元素的计算方法如下 其中 1 i m1 1 j n2 3 根据数学上矩阵相乘的原理 我们可以得到矩阵相乘的经典算法 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 Q i j M i k N k j 4 图5 17Q M N 图5 17给出了一个矩阵相乘的例子 当矩阵M N是稀疏矩阵时 我们可以采用三元组表的表示形式来实现矩阵的相乘 5 图5 18矩阵M N Q的三元组表 6 经典算法中 不论M i k N k j 是否为零 都要进行一次乘法运算 而实际上 这是没有必要的 采用三元组表的方法来实现时 因为三元组只对矩阵的非零元素做存储所以可以采用固定三元组表a中的元素 i k Mik 1 i m1 1 k n1 在三元组表b中找所有行号为k的的对应元素 k j Nkj 1 k m2 1 j n2 进行相乘 累加 从而得到Q i j 即以三元组表a中的元素为基准 依次求出其与三元组表b的有效乘积 7 算法中附设两个向量num first 其中num row 表示三元组表b中第row行非零元素个数 1 row m2 first row 表示三元组表b中第row行第一个非零元素所在的位置 显然 first row 1 1指向三元组表b中第row行最后一个非零元素的位置 first 1 1 first row first row 1 num row 1 2 row m2 1 这里 first m2 1 1表示最后一行最后一个非零元素的存储位置 当三元组表a中第i行非零元素的列号等于三元组表b中非零元素的行号时 则元素相乘并将结果累加 8 图5 19Q M N 9 图5 20图5 19中矩阵N对应的向量num row first row Row1234 5 Num row 2111First row 13456 10 defineMAXSIZE1000 非零元素的个数最多为1000 defineMAXROW1000 矩阵最大行数为1000 typedefstruct introw col 该非零元素的行下标和列下标 ElementTypee 该非零元素的值 Triple typedefstruct Tripledata MAXSIZE 1 非零元素的三元组表 data 0 未用 intfirst MAXROW 1 三元组表中各行第一个非零元素所在的位置 intm n len 矩阵的行数 列数和非零元素的个数 TriSparMatrix 11 具体算法如下 该算法的时间主要耗费在乘法运算及累加上 其时间复杂度为O A len B n 当A len接近于A m A n时 该算法时间复杂度接近于经典算法的时间复杂度O A m A n B n 12 稀疏矩阵的链式存储结构 十字链表与用二维数组存储稀疏矩阵比较 用三元组表表示的稀疏矩阵不仅节约了空间 而且使得矩阵某些运算的运算时间比经典算法还少 但是在进行矩阵加法 减法和乘法等运算时 有时矩阵中的非零元素的位置和个数会发生很大的变化 如A A B 将矩阵B加到矩阵A上 此时若还用三元组表表示法 势必会为了保持三元组表 以行序为主序 而大量移动元素 13 在十字链表中 矩阵的每一个非零元素用一个结点表示 该结点除了 row col value 以外 还要有以下两个链域 right 用于链接同一行中的下一个非零元素 down 用于链接同一列中的下一个非零元素 14 图5 23十字链表的结构 15 十字链表的结构类型说明如下 typedefstructOLNode introw col 非零元素的行和列下标 ElementTypevalue structOLNode right down 非零元素所在行表 列表的后继链域 OLNode OLink typedefstruct OLink row head col head 行 列链表的头指针向量 intm n len 稀疏矩阵的行数 列数 非零元素的个数 CrossList 16 CreateCrossList CrossList M 采用十字链表存储结构 创建稀疏矩阵M scanf 17 else 寻找行表中的插入位置 for q M row head i q right 完成插入 18 广义表 广义表 顾名思义 也是线性表的一种推广 广义表被广泛地应用于人工智能等领域的表处理语言LISP语言中 在LISP语言中 广义表是一种最基本的数据结构 就连LISP语言的程序也表示为一系列的广义表 19 在第2章中 线性表被定义为一个有限的序列 a1 a2 a3 an 其中ai被限定为是单个数据元素 广义表也是n个数据元素 d1 d2 d3 dn 的有限序列 但不同的是 广义表中的d i既可以是单个元素 还可以是一个广义表 通常记作 GL d1 d2 d3 dn GL是广义表的名字 通常广义表的名字用大写字母表示 n是广义表的长度 若其中di是一个广义表 则称di是广义表GL的子表 在广义表GL中 d1是广义表GL的表头 而广义表GL其余部分组成的表 d2 d3 dn 称为广义表的表尾 由此可见广义表的定义是递归定义的 因为在定义广义表时又使用了广义表的概念 20 D 空表 其长度为零 A a b c 表长度为2的广义表 其中第一个元素是单个数据a 第二个元素是一个子表 b c B A A D 长度为3的广义表 其前两个元素为表A 第三个元素为空表D C a C 长度为2递归定义的广义表 C相当于无穷表C a a a 其中 A B C D是广义表的名字 下面以广义表A为例 说明求表头 表尾的操作 head A a表A的表头是a tail A b c 表A的表尾是 b c 广义表的表尾一定是一个表 21 从上面的例子可以看出 1 广义表的元素可以是子表 而子表还可以是子表 由此可见 广义表是一个多层的结构 2 广义表可以被其它广义表共享 如广义表B就共享表A 在表B中不必列出表A的内容 只要通过子表的名称就可以引用该表 3 广义表具有递归性 如广义表C 22 由于广义表GL d1 d2 d3 dn 中的数据元素既可以是单个元素 也可以是子表 因此对于广义表来说 我们难以用顺序存储结构来表示它 通常我们用链式存储结构来表示 表中的每个元素可用一个结点来表示 广义表中有两类结点 一类是单个元素结点 另一类是子表结点 任何一个非空的广义表都可以分解成表头和表尾两部分 反之 一对确定的表头和表尾可以唯一地确定一个广义表 由此 一个表结点可由三个域构成 标志域 指向表头的指针域和指向表尾的指针域 而元素结点只需要两个域 标志域和值域 23 typedefenum ATOM LIST ElemTag ATOM 0 表示原子 LIST 1 表示子表 typedefstructGLNode ElemTagtag 标志位tag用来区别原子结点和表结点 union AtomTypeatom 原子结点的值域atom struct structGLNode hp tp htp 表结点的指针域htp 包括表头指针域hp和表尾指针域tp atom htp atom htp是原子结点的值域atom和表结点的指针域htp的联合体域 GList 24 25 图5 25广义表的另一种结点结构 表结点 原子结点 26 27 typedefenum ATOM