文档介绍：Add the author and the accompanying title
软件技术基础二叉树
第二章下基本数据结构及其运算
此文档后面有赠送常用PPT图标,方便大家修订排版编辑
第二章基本数据结构及其相同值的多个元素占用一个存储单元；
零元素不分配存储单元，
一、能够采用压缩存储的矩阵
对称矩阵:存储主对角线以上下的元素；
上下三角矩阵:只存储三角阵元素；
带状矩阵:只存储带状元素；
稀疏矩阵:只存储非零元素；
大量相同元素矩阵:存储某元素和重复个数，
二、下三角矩阵的压缩存储
开辟一个长度为n n+1 /2的一维数组B,然后一行接一行地依次存放A中下三角部分的元素，
以行为主压缩存储
以列为主压缩存储
三、对称矩阵的压缩存储
对称矩阵的元素满足：aij = aji 1 ≤ i ,j ≤ n
因此将n×n 个元素压缩存放到 n n+1 /2 个单元的一维数组S n n+1 /2 中，
按行存放 aij的地址为：
对称矩阵的压缩存储举例
存于一维数组S 6
S 6 = a11, a21, a22, a31, a32, a33
1 2 3 4 5 6
LOC a31 =3 3-1 /2+1= 4
LOC a22 =2 2-1 /2+2= 3
LOC a21 =2 2-1 /2+1= 2
设有A3x3矩阵:
四、对角矩阵的压缩存储
在三对角矩阵中,三条对角线以外的元素均为零,并且,除了第一行与最后一行外,其他每一行均只有三个元素为非零,因此,n阶三对角矩阵共有3n-2个非零元素，
对角矩阵的压缩存储
以行为主存放：
一般稀疏矩阵的表示
如果一个矩阵中绝大多数的元素值为零,只有很少的元素值非零,则称该矩阵为稀疏矩阵，
一、三列二维数组表示
1 非零元素所在的行号i；
2 非零元素所在的列号j；
3 非零元素的值V，
即每一个非零元素可以用下列三元组表示：
i,j,V
例如,上述稀疏矩阵A中的8个非零元素可以用以下8个二元组表示以行为主的顺序排列：
1,3,3 1,8,1 3,1,9 4,5,7 5,7,6 6,4,2 6,6,3 7,3,5
为了表示上的唯一性,除了每一个非零元素用一个三元组表示外,在所有表示非零元素的三元组之前再添加一个三元组： I,J,t
其中I表示稀疏矩阵的总行数,J表示稀疏矩阵的总列数,t表示稀疏矩阵中非零元素的个数，
上述稀疏矩阵A可以用以下9个三元组表示：
7,8,8 1,3,3 1,8,1
3,1,9 4,5,7 5,7,6
6,4,2 6,6,3 7,3,5
其中第一个三元组表示了稀疏矩阵的总体信息总行数,总列数、非零元素个数 ,
其后的8个三元组依次以行为主排列表示稀疏矩阵中每一个非零元素的信息所在的行号、列号以及非零元素值，
为了使各三元组的结构更紧凑,通常将这些三元组组织成三列二维表格的形式,一般又表示成三列二维数组的形式,并简称为三列二维数组，
举例:
为了便于在三列二维数组B中访问稀疏矩阵A中的各元素,通常还附设两个长度与稀疏矩阵A的行数相同的向量POS与NUM,
POS k 表示稀疏矩阵A中第k行的第一个非零元素如果有的话在三列二维数组B中的行号,
NUM k 表示稀疏矩阵A中第k行中非零元素的个数,
这两个向量之间存在以下关系：
POS 1 ＝2
POS k ＝POS k-1 十NUM k-1 ,2 ≤ k ≤ m
举例
二、十字链表
每个结点有五个域：行域、列域、值域、向下域与向右域，
row
col
val
行域
列域
值域
向下域
向右域
down
right
十字链表表示稀疏矩阵
1 稀疏矩阵的每一行与每一列均用带表头结点的循环链表表示，
2 表头结点中的行域与列域的值均置为0 即row＝0,col＝0 ，
3 行、列链表的表头结点合用,且这些表头结点通过值域即val 相链接,并再增加一个结点作为它们的表头结点H,其行、列域值分别存放稀疏矩阵的行数与列数，
例如,稀疏矩阵
注意： in P7