角矩阵 对角 对角矩阵是指所有的非零元素都集中在主对角 线及以它为中心的其他对角线上。如果 ij>1,那么数组元素ailj|=0。 下面是一个3对角矩阵 0,0c0、1 0 a1.0a 1,1s1.2… n a n n-h.n- 北京大学信息学院张铭编写 版权所有,转载或翻印必究 Page 16
北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 16 对角矩阵 对角矩阵是指所有的非零元素都集中在主对角 线及以它为中心的其他对角线上。如果 |i-j|>1，那么数组元素a[i][j]=0。 下面是一个3对角矩阵： a0,0 a1,1 a0,1 a1,0 an-1,n-2 an-1,n-1 an-2,n-1 a1,2 0 0 …… …… ……
稀疏矩阵 ■稀疏矩阵中的非零元素非常少,而且分布也不 规律 0007005 01500000 00060170 078000220 11000000 00420000 北京大学信息学院张铭编写 版权所有,转载或翻印必究 Page
北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 17 稀疏矩阵 稀疏矩阵中的非零元素非常少，而且分布也不 规律 × ⎛ ⎞ ⎜ ⎟ ⎜ ⎟ ⎜ ⎟ − = ⎜ ⎟ ⎜ ⎟ ⎜ ⎟ ⎜ ⎟ ⎜ ⎟ ⎝ ⎠ 6 7 0 0 0 7005 0 15 0 0 0 0 0 0 0 0 6 0 17 0 A 0 78 0 0 0 22 0 11 0 0 0 0 0 0 0 0 42 0 0 0 0
稀疏因子 在m×n的矩阵中,有t个非零元素,则稀疏 因子为 n x n 当这个值小于0.05时,可以认为是稀疏矩阵 ■三元组(i,j,a;:):输入/输出常用 i是该元素的行号 j是该元素的列号 aa;是该元素的值 北京大学信息学院张铭编写 版权所有,转载或翻印必究 Page 18
北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 18 稀疏因子 在m ×n的矩阵中，有t个非零元素，则稀疏 因子为: 当这个值小于0.05时，可以认为是稀疏矩阵 三元组(i, j, aij )：输入/输出常用 i是该元素的行号 j是该元素的列号 aij是该元素的值 m n t × δ =
稀疏矩阵的十字链表 十字链表有两组链表组成 行和列的指针序列 每个结点都包含两个指针:同一行的后继,同一列的后继 列链表头指针 030 056 表 15 200 头 指 02 北京大学信息学院张铭编写 版权所有,转载或翻印必究 Page
北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 19 稀疏矩阵的十字链表 十字链表有两组链表组成 行和列的指针序列 每个结点都包含两个指针：同一行的后继，同一列的后继 0 3 0 0 5 6 2 0 0 0 1 3 1 1 5 2 0 2 列链表头指针 行 链 表 头 指 针 1 2 6 ∧ ∧ ∧ ∧ ∧ ∧
列链表头指针 十字链表的建立 表 26 头 指 ■建立矩阵的算法如下:针 首先为行头结点和列头结点申请空间,大小分别为 矩阵的行列数 将三元组根据情况分别加入到链表中 如果三元组中的行列号错误,则退出,否则继续 先处理行链表的问题 如果该行头结点为空,则建立一个新的头结点,内容 为该三元组 如果不为空则从头结点开始査找,找到该三元祖的正 确位置如果该位置已经存在数据,则修改之,否则生 成相应的结点插入进去 类似地处理列链表头 北京大学信息学院张铭编写 版权所有,转载或翻印必究 Page 20
北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 20 十字链表的建立 建立矩阵的算法如下： 首先为行头结点和列头结点申请空间，大小分别为 矩阵的行列数 将三元组根据情况分别加入到链表中 如果三元组中的行列号错误，则退出，否则继续 先处理行链表的问题 如果该行头结点为空，则建立一个新的头结点，内容 为该三元组 如果不为空则从头结点开始查找，找到该三元祖的正 确位置如果该位置已经存在数据，则修改之，否则生 成相应的结点插入进去 类似地处理列链表头 0 1 3 1 1 5 2 0 2 列链表头指针 行 链 表 头 指 针 1 2 6 ∧ ∧ ∧ ∧ ∧ ∧