当前课程知识点：数据结构 > 第4章 数组 > 4.3 特殊矩阵的压缩存储 > 讲解
本节，我们来学习特殊矩阵的压缩存储
在实际应用当中
很多矩阵，它们的值分布是有一定规律的
为了节省内存
我们没必要存放矩阵当中所有元素的值
我们只存放其中一部分
这就叫做压缩存储
在压缩存储之后，我们要能还原回之前想表示的这个矩阵
现在，我们来看第一类特殊矩阵，对称矩阵
对称矩阵，元素是沿着主对角线对称的
比如，这两个5
这两个17，等等
换句话说
矩阵中的aij元素，是等于aji的
很明显
我们没有必要存放下矩阵中全部的n^2个元素
而是只存储主对角线，及其一侧的值，就可以了
比如，我们只存图中绿色的区域
也就是矩阵的下三角部分
当然，你存上三角，也是可以的
好，现在，我们用一个一维数组A
并且以行为主序，来存放绿色区域的元素
比如，第0行，存放1个元素，10
因为这里的i、j，都是下标
都是从0开始的
所以，我们使用了第0行这种称法
这个希望大家要注意
好，下一行，也就是第1行，存放2个元素，5、7
第2行，存放3个元素，3、12、20
第3行，存放最后的4个元素
现在，我们一般化
对于n阶的对称矩阵，一共要存多少个元素呢
换句话说
数组A的长度是多少呢
通过刚才的分析
我们能明显看出
在绿色区域中，每一行的元素个数
其实与行号是存在某种联系的
比如，右边这个表格，列出了每一行存放的元素个数
与该行的行号之间的关系
第0行，存了1个
第1行，存了2个
第i行，应该是i+1个
最后一行(也就是第n-1行)，存了n个
所以，存放的元素总个数，就是1累加到n
也就是n(n+1)/2
对于这样一个数组A
我们如何根据任意给定的下标i、j，找到对应的元素aij呢
毕竟，你压缩存储了之后，你还要能还原回压缩前的矩阵啊
我们来分析一下i、j的大小关系
先看当i>=j的时候
i>=j，元素应该是落在绿色区域内的
原因很简单
因为主对角线上，元素的i、j下标是相等的
现在i>=j，说明aij是出现在矩阵的下三角位置的
也就是绿色的区域
现在，aij在绿色的区域
而绿色区域的元素，我们是存了的
于是，我们就应该在数组A中，去找aij
现在问题是，aij到底在A中的哪个下标位置呢
很简单
我们就看aij前面，一共存了多少个元素，就行了
还是看右边这个表格
aij所在的行
它上面，一共有i行
别忘了，i、j都是从0开始的
也就是，行号从0到i-1的这一共i行
这i行一共有多少个元素呢
就是1累加到i，也就是这里的这一项
哎
然后，在aij本行
位于它前面的元素，一共有j个
所以，j跟刚才红色框框住的相加
就是aij元素在A中的下标了
我们再来看另一种情况
当i i 这时候，aij应该是位于绿色区域之外的 但绿色区域之外的元素 我们根本就没存 那怎么找到aij的值呢 别忘了，我们现在压缩存储的是对称矩阵，aij虽然没存 但我们存了aji，aji不就在绿色区域里面吗 所以，这时候，我们只需要交换一下上面这个下标中的i和j 就得到了aij在A中的下标了 这是对称矩阵 我们再来看第二类特殊矩阵，上/下三角矩阵 这里，我们以下三角矩阵为例 下三角矩阵 那些位于主对角线一侧的元素 都是某一个常数c 比如这个图 这个常数c啊，通常是0 但也有可能是其他非0的值 对于这样的矩阵 我们也没必要存放所有的n^2个元素 而是跟刚才的对称矩阵类似 只存放主对角线及其一侧的值，以及这个常数c，就可以了 同样，我们用一维数组A来做压缩存储，也是按行为主序来存放 那么，数组A这时候的长度是多少呢 很简单，就比刚才讲的对称矩阵多了这个单元 因为多存了一个常数c 前面的多个单元，跟刚才的对称矩阵都是一样的 都是一个下三角矩阵 所以，这时候的A 它的长度就是之前的对称矩阵的长度，再加上一个1 也就是这个 那么，我们怎么去找到给定的i、j下标对应的aij元素呢 跟刚才一样 就是看aij是不是落在我们存的那个下三角区域里面 如果在 也就是当i>=j的时候 我们就直接在数组A中找 这时候，aij所在的下标，跟之前的对称矩阵是一模一样的 因为A这个数组，它前面的那些单元 也就是除了最后一个元素之外的那些单元 跟对称矩阵是完全一致的 所以，这时候，aij就在这个下标位置 另外一种情况，i 很明显 这时候，aij就不在下三角位置了 不在下三角，那就在上三角 上三角里面都是常数c 所以，这时候aij的值，就是常数c C 但是常数c从哪里才能找到呢 不就是A的最后一个下标n(n+1)/2，这个位置吗 接下来，我们来看最后一类特殊矩阵，对角矩阵 对角矩阵中的非零元素，仅出现在以主对角线为中心的带状区域 而其余位置的元素都是0 所以，对角矩阵有时也称为带状矩阵 比如这个图，绿色区域 实际上是由3条对角线组成的 故称为5阶的三对角矩阵 因为，主对角线左右两侧的对角线条数都是一样的 所以，带状区域中的对角线总条数k，一定是一个奇数 比如这里的3 既然只有带状区域中的元素分布没有规律 因此，我们就只存储该带状区域的元素，就可以了 存的时候 我们依然是按矩阵的行为主序来存 大家看这里的一维数组A 第0行，存2个；第1行，存3个；第2行，存3个 一直往后 最后一行，又回到了2个 那么，这样一个一维数组，总共要存多少个元素呢 为了方便计算 我们可以这样看 红色的主对角线上，是有n个元素的 紧挨其左侧的蓝色对角线上，有n-1个元素 现在，假设k是5 也就是说 如果蓝色对角线的左侧还有一条对角线 那么，这条对角线上的元素个数，将继续以1递减 右侧也是类似的 因此，带状区域上的非零元个数 一定是关于矩阵阶数n和对角线条数k的某个函数 这里由于时间关系 我们就直接给出来了，是这个 具体的推导过程，我们将在本节课程的讨论中详细给出 当然，同学们也可以尝试着自己推导一下 其实也比较简单 对于我们这里给出的对角矩阵 n=5，k=3 那就是3*5-(9-1)/4，等于13 也就是说 一维数组A的长度就是13 它们的下标 就是0到12 有了一维数组A之后 我们要解决的问题仍然是，如何根据A还原回压缩存储前的对角矩阵 也就是说 给定任意i、j下标，如何确定aij的值 通过分析，我们不难发现 当i、j之差的绝对值超过了(k-1)/2的时候 aij应该是位于带状区域之外的 为什么是这样呢，我们这样看 最左侧的对角线，也就是那条蓝色的对角线 它上面的元素，i下标减去j下标的值 都是等于(k-1)/2，也就是1 比如这里的21、34 也就是说，如果i>j 并且i-j比(k-1)/2还要大 那，aij就位于最左侧对角线的左下区域(这一部分) 它们都是0 与之对称的，如果i 并且i-j比-(k-1)/2还要小 这时候，aij就位于最右侧对角线的右上区域，它们也是0 所以，我们综合这两种情况 当i减j的绝对值超过了(k-1)/2的时候 也就是这个条件，这时候，aij的值就是0 比如，这里的a31，还有a04等等 它们都是满足这个条件的 所以，元素的值都是0 那另外的情况呢 当|i-j|<=(k-1)/2的时候(这个条件) 那aij又是多少呢 这时候，我们很难像前面的两种特殊矩阵那样，算出一个通项公式 因为这时候，aij在数组A中的下标 实际上取决于i、j、n、k它们的具体值 我们只能根据它们的具体值来计算 待会我们会看到 比如，我们现在要去找a32，a32应该是它 (注意)i、j都是从0开始 容易知道，a32所在行的上面，实际上存了3行 这3行分别有2、3、3个元素 再看a32所在的那一行 它前面存了多少个元素呢 我们刚才分析过了 对于a32，它的i下标减去j下标，也就是3-2，等于1 说明，a32就位于最左侧的对角线上 因为这时候，(k-1)/2就是1 它就是该行存的第一个元素 所以，在a32前面，没有存其他的任何元素 它在A中的下标就是2+3+3，就是A[8] 对应的值，就是这里的21 我们再换一个元素，比如a34，在这儿 也是类似的，只不过这时候 它的i下标减去j下标，3-4，等于-1 也就是-(k-1)/2 说明a34就位于最右侧的对角线上 它是该行的第3个元素 换句话说 在这一行，a34前面，一共存了两个元素 所以，a34在A中的下标就是2+3+3，再加一个2 这个2+3+3，跟刚才的a32是一样的 都是它上面的3行存放的元素 这里的加2，是表示在a34那一行，a34前面存了两个元素 所以就是A[10]，对应的值就是-6 好，这是对角矩阵
-讲解
-作业
-讨论1
-讨论2
-1.1 数据结构是什么
--讲解
--作业
-1.2 概念和术语
--讲解
--作业1
--作业2
-1.3 抽象数据类型
--讲解（上）
--讲解（下）
--作业
-1.4 算法及其设计要求
--讲解
--作业
-1.5 算法分析与度量
--讲解（上）
--讲解（下）
--作业1
--作业2
--讨论
-2.1 概念及ADT
--讲解
--作业
-2.2 线性表的顺序实现——顺序表
--讲解（上）
--讲解（中）
--讲解（下）
--作业1
--作业2
-2.3 线性表的链式实现——链表
--讲解（上）
--讲解（中）
--讲解（下）
--作业1
--作业2
-2.4 线性表的应用——多项式
--讲解
--作业
-讨论
-3.1 栈的定义及ADT
--讲解
--作业
-3.2 栈的顺序实现——顺序栈
--讲解
--作业
-3.3 栈的应用
--讲解
--作业
-3.4 栈与递归
--讲解（上）
--讲解（下）
--作业
-3.5 队列的定义及ADT
--讲解
--作业
-3.6 队列的顺序实现——循环队列
--讲解（上）
--讲解（下）
--作业
-讨论
-4.1 数组的定义
--讲解
--作业
-4.2 数组的顺序实现
--讲解
--作业1
--作业2
-4.3 特殊矩阵的压缩存储
--讲解
--作业
-4.4 稀疏矩阵的压缩存储
--讲解（上）
--讲解（下）
--作业
-讨论
-5.1 概念及术语
--讲解
--作业
-5.2 二叉树及其性质
--讲解
--作业1
--作业2
-5.3 二叉树的存储
--讲解
--作业
-5.4 二叉树的遍历及创建
--讲解（上）
--讲解（下）
--作业
-5.5 线索二叉树
--讲解
--作业
-5.6 树与森林
--讲解
--作业
-5.7 Huffman树
--讲解（上）
--讲解（下）
--作业
-讨论
-6.1 概念和术语
--讲解
--作业
-6.2 存储与实现
--讲解（上）
--讲解（下）
--作业
-6.3 遍历
--讲解（上）
--讲解（下）
--作业
-6.4 最小生成树
--讲解（上）
--讲解（下）
--作业1
--作业2
-6.5 拓扑排序
--讲解
--作业
-6.6 最短路径
--讲解
--作业
-讨论
-7.1 概念和术语
--讲解
--作业
-7.2 静态查找表
--讲解（上）
--讲解（下）
--作业
-7.3 二叉排序树
--讲解（上）
--讲解（下）
--作业
-7.4 平衡二叉树
--讲解
--作业
-7.5 哈希表
--讲解（上）
--讲解（下）
--作业
-讨论
-8.1 概念
--讲解
--作业
-8.2 插入排序
--讲解（上）
--讲解（下）
--作业
-8.3 交换排序
--讲解（上）
--讲解（下）
--作业
-8.4 选择排序
--讲解（上）
--讲解（中）
--讲解（下）
--作业
-8.5 归并排序
--讲解
--作业
-讨论
