稀硫矩阵的十字链表+字链表的建立 十字链表有两组链表组成 行和列的抛针序列 建立矩阵的算法如下:习 每个结点都包合两个指针:同一行的后繼,同一列的后繼 首先为行头结点和列头结点申请空间,大小分别为 列睡表买指针 矩阵的行列数 将三元组根据情况分别加入到链豪中 如果三元组中的行列号错误,则退出,否则继绘 030 行表头指 头结点为空,则建立一个新的头结点,内容 056 还如案位数息开维要挠魏波元智的廷 处理列链衰头 单息张帖篇写 经典矩阵乘法 [c1..d1][c3.d3],B[c3..d3][ c[c1..d1][c2.d2]。 p=d1-c1+1,m=d3-c3+1, n=d2c2+1; C=AXB (C1=EAlk Bx] ■A为p×m的矩阵,B为mxn的矩 for (i=cl: i<d1: 1++) 阵,乘得的结果C为p×n的矩阵 for(j=c2;j<=2;j++) 经典矩阵乘法所需要的时间代价为 for (k=c3: k<=d3 k+ o(pXmXn cli, sum+ ali, k]*Bkk, j]: 北京大息 权有。印乡究 北大啦孔写 叔新有命剑 稀疏矩阵乘法 稀疏矩阵乘法时间代价 05 ■A为p×m的矩阵,B为m×n的矩阵, 乘得的结果C为p×n的矩阵 若矩阵A中行向量的非零元素个数最多为 ■矩阵B中列向量的非零元素个数最多为t 总执行时间降低为o(t+tb)Xp×n) B ■经典矩阵乘法所需要的时间代价为 o(pXm×n) 大息驰 北大学到4 北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 19 稀疏矩阵的十字链表 „ 十字链表有两组链表组成 „ 行和列的指针序列 „ 每个结点都包含两个指针：同一行的后继，同一列的后继 0 3 0 0 5 6 2 0 0 0 1 3 1 1 5 2 0 2 列链表头指针 行 链 表 头 指 针 1 2 6 ∧ ∧ ∧ ∧ ∧ ∧ 北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 20 十字链表的建立 „ 建立矩阵的算法如下： „ 首先为行头结点和列头结点申请空间，大小分别为 矩阵的行列数 „ 将三元组根据情况分别加入到链表中 „ 如果三元组中的行列号错误，则退出，否则继续 „ 先处理行链表的问题 „ 如果该行头结点为空，则建立一个新的头结点，内容 为该三元组 „ 如果不为空则从头结点开始查找，找到该三元祖的正 确位置如果该位置已经存在数据，则修改之，否则生 成相应的结点插入进去 „ 类似地处理列链表头 0 1 3 1 1 5 2 0 2 列链表头指针 行 链 表 头 指 针 1 2 6 ∧ ∧ ∧ ∧ ∧ ∧ 北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 21 经典矩阵乘法 „ A[c1..d1][ c3..d3]，B[c3..d3][ c2..d2], C[c1..d1][c2..d2]。 „ d3 C＝A×B (Cij＝∑Aik ·Bkj) k=c3 „ for (i=c1; i<=d1; i++) for (j=c2; j<=d2; j++) { sum = 0; for (k=c3; k<=d3; k++) sum = sum + A[i,k]*B[k,j]; C[i，j] = sum; } 北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 22 „ p=d1-c1+1，m=d3-c3+1， n=d2-c2+1； „ A为p×m的矩阵，B为m×n的矩 阵，乘得的结果C为p×n的矩阵 „ 经典矩阵乘法所需要的时间代价为 O(p×m×n) 北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 23 稀疏矩阵乘法 3 0 0 5 0 -1 0 0 2 0 0 0 ⎡ ⎣ ⎢ ⎤ ⎦ ⎥ 0 2 1 0 -2 4 0 0 ⎡ ⎣ ⎢ ⎢ ⎤ ⎦ ⎥ ⎥ × = 0 1 2 1 0 1 0 2 -2 2 1 4 ∧ ∧ ∧ ∧ ∧ 0 6 -1 0 0 4 ⎡ ⎣ ⎢ ⎤ ⎦ ⎥ 6 列链表头指针 行 链 表 头 指 针 0 0 3 0 3 5 ∧ ∧ 1 1 -1 0 2 2 ∧ ∧ ∧ ∧ -1 4 北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 24 稀疏矩阵乘法时间代价 „ A为p×m的矩阵，B为m×n的矩阵， 乘得的结果C为p×n的矩阵 „ 若矩阵A中行向量的非零元素个数最多为 ta „ 矩阵B中列向量的非零元素个数最多为tb „ 总执行时间降低为O((ta+tb)×p×n) „ 经典矩阵乘法所需要的时间代价为 O(p×m×n)