稀疏因子 口在mXn的矩阵中,有t个非零元素,则稀疏因 子为: 口当这个值小子0.05时,可以认为是稀疏矩阵 三元组(i,a;):输入输出常用 ai是该元素的行 号 口是该元素的列号 口a是该元素的值 “十一五”国家缀规划教材。张铭,王腾蛟,赵海￡,《飙据结构与算法》,高教社,B0.6
“十一五”国家级规划教材。张铭，王腾蛟，赵海燕，《数据结构与算法》，高教社，2008. 6。 ◼ 稀疏因子 ❑ 在m ×n的矩阵中，有t个非零元素，则稀疏因 子为: ❑ 当这个值小于0.05时，可以认为是稀疏矩阵 ◼ 三元组(i, j, aij )：输入/输出常用 ❑ i是该元素的行号 ❑ j是该元素的列号 ❑ aij是该元素的值 m n t =
稀疏矩阵的十字链表 十字链表有两组链表组成 口行和列的指针序列 a每个结点都包含两个指针:同一行的后继,同一列的后继 列链表头指针 013 056 200 行链表头指针 ∧ L∧∧ 202 ∧∧ “十一五”国家缀规划教材。张铭,王腾蛟,赵海￡,《飙据结构与算法》,高教社,B0.6
“十一五”国家级规划教材。张铭，王腾蛟，赵海燕，《数据结构与算法》，高教社，2008. 6。 稀疏矩阵的十字链表 ◼ 十字链表有两组链表组成 ❑ 行和列的指针序列 ❑ 每个结点都包含两个指针：同一行的后继，同一列的后继 0 3 0 0 5 6 2 0 0 0 1 3 1 1 5 2 0 2 列链表头指针 行 链 表 头 指 针 1 2 6 ∧ ∧ ∧ ∧ ∧ ∧
经典矩阵乘法 Icl.dll[ c3.d3], Bc3.d3 c2.d2, CIcl.d1llc2 d2 d3 C=A×B(C=∑AiBk =c3 for(i=cl; i<=dl; i++) or〔j=c2;j<=d2;j++){ sum for (k=c3; k<=d3; k++) sum=sum +Ai, k*b[kjl; CHi,j=sum; “十一五”国家缀规划教材。张铭,王腾蛟,赵海￡,《飙据结构与算法》,高教社,B0.6
“十一五”国家级规划教材。张铭，王腾蛟，赵海燕，《数据结构与算法》，高教社，2008. 6。 经典矩阵乘法 ◼ 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; }
p=dl-c1+1,m=d3-c3+1,n=d2-c2+1 A为p×m的矩阵,B为m×n的矩阵, 乘得的结果C为p×n的矩阵 经典矩阵乘法所需要的时间代价为 O(p×m×n “十一五”国家缀规划教材。张铭,王腾蛟,赵海￡,《飙据结构与算法》,高教社,B0.6
“十一五”国家级规划教材。张铭，王腾蛟，赵海燕，《数据结构与算法》，高教社，2008. 6。 ◼ 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)
稀疏矩阵乘法 3005 0-100 0 24 10 2000 00 04 列链表头指针 0 ∧∧ 101 行链表头指针 02 102 ∧ finish “十一五”国家缀规划教材。张铭,王腾蛟,赵海￡,《飙据结构与算法》,高教社,B0.6
“十一五”国家级规划教材。张铭，王腾蛟，赵海燕，《数据结构与算法》，高教社，2008. 6。 稀疏矩阵乘法 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 finish