文档介绍：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，其行、列域值分别存放稀疏矩阵的行数与列数。
例如，稀疏矩阵
注意：其十字链表表示的稀疏矩阵如