用数组表示特殊矩阵(续) 对角矩阵是指所有的非零元素都集中在主对角线及以 它为中心的其他对角线上。如果1,那么数组元素 al[l[jl=0。 n下面是一个3对角矩阵: 00a0, 0 a1.0a1,1a42 n- n-2 -n-2an-1n-1 北京大学信息学院 版权所有,转载或翻印必究 Page 21
北京大学信息学院 ©版权所有，转载或翻印必究 Page 21 用数组表示特殊矩阵（续） ◼ 对角矩阵是指所有的非零元素都集中在主对角线及以 它为中心的其他对角线上。如果|i-j|>1，那么数组元素 a[i][j]=0。 ◼ 下面是一个3对角矩阵： a0,0 a0,1…….. 0 a1,0 a1,1 a12…… an-1,n-2 0 an-1,n-2 an-1n-1
稀疏矩阵 ■稀疏矩阵中的非零元素非常少,而且分布也不规律 稀疏因子 ■用来描述稀疏矩阵的非零元素情况,它定义为在mXn的矩阵 中,有t个非零元素,则稀疏因子为: m x n 通常当这个值小于0.05时,可以认为是稀疏矩阵 般使用三元组(i,j,a;)来顺序存储稀疏矩阵,其 中1是该元素的行号,j是该元素的列号,8,是该元素 的值 北京大学信息学院 版权所有,转载或翻印必究 Page 22
北京大学信息学院 ©版权所有，转载或翻印必究 Page 22 稀疏矩阵 ◼ 稀疏矩阵中的非零元素非常少，而且分布也不规律 ◼ 稀疏因子 ◼ 用来描述稀疏矩阵的非零元素情况，它定义为在m ×n的矩阵 中，有t个非零元素，则稀疏因子为: ◼ 通常当这个值小于0.05时，可以认为是稀疏矩阵 ◼ 一般使用三元组(i, j, aij )来顺序存储稀疏矩阵，其 中i是该元素的行号，j是该元素的列号，aij是该元素 的值 m n t =
稀疏矩阵的十字链表 十字链表有两组链表组成 行和列的指针序列 链表中的每一个结点都包含两个指针,一个指向它的同一行 的下一个元素,一个指向它的同一列的下一个元素 列链表头指针 行链表头指针 p151p26 0 2 北京大学信息学院 版权所有,转载或翻印必究 Page 23
北京大学信息学院 ©版权所有，转载或翻印必究 Page 23 稀疏矩阵的十字链表 ◼ 十字链表有两组链表组成 ◼ 行和列的指针序列 ◼ 链表中的每一个结点都包含两个指针，一个指向它的同一行 的下一个元素，一个指向它的同一列的下一个元素
十字链表的ADT template≤ Class t> class olnode private: int row,col;/矩阵的行和列 T element;矩阵中存储的数据 ANOde< T>N right;down;∥指向下一个结点的指针 public OLNodeoright=NULL; down=NULL; 北京大学信息学院 版权所有,转载或翻印必究 Page 24
北京大学信息学院 ©版权所有，转载或翻印必究 Page 24 十字链表的ADT template<class T> class OLNode { private: int row,col;//矩阵的行和列 T element;//矩阵中存储的数据 OLNode<T>* right,*down;//指向下一个结点的指针 public: OLNode(){right=NULL;down=NULL;}; };
十字链表的建立 ■建立矩阵的算法如下: 首先为行头结点和列头结点申请空间,大小分别为 矩阵的行列数 ■将三元组根据情况分别加入到链表中 如果三元组中的行列号错误,则退出,否则继续 n先处理行链表的问题 如果该行头结点为空,则建立一个新的头结点,内容 为该三元组 如果不为空则从头结点开始查找,找到该三元祖的正 确位置如果该位置已经存在数据,则修改之,否则生 成相应的结点插入进去 类似地处理列链表头 北京大学信息学院 版权所有,转载或翻印必究 Page 25
北京大学信息学院 ©版权所有，转载或翻印必究 Page 25 十字链表的建立 ◼ 建立矩阵的算法如下： ◼ 首先为行头结点和列头结点申请空间，大小分别为 矩阵的行列数 ◼ 将三元组根据情况分别加入到链表中 ◼ 如果三元组中的行列号错误，则退出，否则继续 ◼ 先处理行链表的问题 ◼ 如果该行头结点为空，则建立一个新的头结点，内容 为该三元组 ◼ 如果不为空则从头结点开始查找，找到该三元祖的正 确位置如果该位置已经存在数据，则修改之，否则生 成相应的结点插入进去 ◼ 类似地处理列链表头