第5章数组和广义表 5.2稀疏矩阵《算法与数据结构（C＆Java）（第2版）》 同步教学（电子工业出版社）

第五章 数组和广义表 5.1 数组的定义 5.2 数组的顺序表示和实现 5.3 矩阵的压缩存储 5.3.1 特殊矩阵 5.3.2 稀疏矩阵 5.4 广义表的定义 5.5 广义表的存储结构 5.3.2 稀疏矩阵 什么是稀疏矩阵？简单说，设矩阵A中有s个非零元素，若s远远小于矩阵元素的总数（即s<<m×n），则称A为稀疏矩阵。 单击此处编辑母版文本样式 第二级 第三级 第四级 第五级 精确地说，设在的矩阵A中，有s个非零元素。令 e=s/(m*n)，称e为矩阵的稀疏因子。通常认为e≦0.05时称之为稀疏矩阵。在存储稀疏矩阵时，为了节省存储单元，很自然地想到使用压缩存储方法。但由于非零元素的分布一般是没有规律的，因此在存储非零元素的同时，还必须同时记下它所在的行和列的位置（i,j)。反之，一个三元组(i,j,aij)唯一确定了矩阵A的一个非零元。因此，稀疏矩阵可由表示非零元的三元组及其行列数唯一确定。 单击此处编辑母版文本样式 第二级 第三级 第四级 第五级 例如，下列三元组表： ((1,2,12)(1,3,9),(3,1,- 3),(3,6,14),(4,3,24), (5,2,18),(6,1,15),(6,4,-7)) 加上(6,7，8)这一对行、列值便可作为下列矩阵M的另一种描述。而由上述三元组表的不同表示方法可引出稀疏矩阵不同的压缩存储方法。 0 12 9 0 0 0 0 0 0 -3 0 0 15 0 0 0 0 0 0 0 12 0 0 0 18 0 -3 0 0 0 0 14 0 9 0 0 24 0 0 0 0 24 0 0 0 0 0 0 0 0 0 –7 0 18 0 0 0 0 0 0 0 14 0 0 0 15 0 0 –7 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 图5.4 稀疏矩阵M和T M= T= 单击此处编辑母版文本样式 第二级 第三级 第四级 第五级 一、三元组顺序表 假设以顺序存储结构来表示三元组表，则可得到稀疏矩阵的一种压缩存储方法——三元顺序表。 #define maxsize 10000 typedef int datatype; typedef struct{ int i,j; /* 行列号 */ datatype v; /* 元素值 */ }triplet; 以上先定义了数组每一元素的数据类型，下面将完整定义保存三元组的数据结构 单击此处编辑母版文本样式 第二级 第三级 第四级 第五级 typedef struct{ triplet data[maxsize]; /* 三元组表 */ int m,n,t; /* 行数、列数、非零元素个数 */ }tripletable; /* 稀疏矩阵类型 */ 设A为tripletable型的结构变量，图5.4中所示的稀疏矩阵 M 的三元组的表示如下： i j v 0 1 12 0 2 9 2 0 -3 2 5 14 3 2 24 4 1 18 5 0 15 5 3 -7 单击此处编辑母版文本样式 第二级 第三级 第