当前课程知识点：数据结构 > 第4章 数组 > 4.4 稀疏矩阵的压缩存储 > 讲解（上）
本节，我们来学习稀疏矩阵的压缩存储
首先，来看看什么是稀疏矩阵
稀疏矩阵当中，绝大多数的值都是0
那些非0的值，分布是没有规律的
我们必须存放下每一个非0的值
它们的相关信息
现在，我们介绍一种三元组顺序表的存放方式
首先来看，什么是三元组，三元组
实际上对应着每一个非0元的三个信息
也就是i、j行列下标，和aij元素的值本身，利用这三个信息
就能够唯一地确定每一个非0元
这三个信息就叫做三元组
我们现在将所有的三元组，存放在一个一维数组当中
并且按照矩阵的行序来存放
这时候，就构成了一个三元组顺序表
比如右边
每一行的三个信息都是一个三元组
然后，若干个三元组
存放在一个一维数组里面
这个数组里面每一个元素的类型就是三元组类型
并且，在存放的时候
我们是按照矩阵的行序为主序来存放的
比如，我们先存的是12这个非0元，再存的是9这个非0元
这样会保证三元组顺序表当中，i值是非递减的
因为有相同的i
因为每一行可能有多个非0元
但是同一行i
它们的j值一定是严格递增的
因为在存每一行的时候
是先存放前面的列，再存放后面的列
最终，我们再把矩阵的行数和列数存放下
利用这些信息，就可以唯一地确定一个稀疏矩阵
现在，我们来看三元组顺序表的C语言定义
既然是顺序表
涉及到数组
我们就定义一个容量SIZE
它是能够表示的最多的非0元个数
每一个元素的类型，简单起见
我们认为是int型
起一个别名，ElemType
作为元素类型
这个之前我们已经见到很多了
这个结构体
实际上是定义了三元组
Triple这个单词本来就有3的意思
结构体的前两个成员i、j，是作为非0元的下标的，第三个成员是非0元本身的值
然后，我们给这三个信息构成的结构体起个别名Triple
第二个结构体就是若干个非0元
构成的一个数组
它的元素类型就是我们刚才定义的Triple，容量是SIZE
凡是看到数组
除了容量之外
还有一个长度
也就是这个数组里面，哪些元素才是非0元
t这个成员表示
非0元的个数
m和n是表示这个稀疏矩阵
它的行数和列数是多少
然后，我们用Typedef给这样一个结构体起一个别名
叫Matrix(矩阵)
它就是三元组顺序表表示的稀疏矩阵
现在，我们来看打印算法的实现
通过分析
无论矩阵是不是稀疏矩阵
最终总要打印
m*n个元素
因为给定的矩阵是m行n列
一定要打印这么多个元素
在打印的过程当中
我们要判断一下，当前内、外层循环变量
比如i、j，它们是否分别与当前要打印的那个非0元的行、列下标相同
如果是相同的，说明当前要打印的这个元素
它恰好是一个非0元
应该在三元组顺序表当中，找到这个非0元，把它打印出来
如果不相等
只要有一个不相等
说明打印的是一个零元
那直接打印零，就可以了
现在我们给出完整的算法，打印以三元组顺序表表示的稀疏矩阵A
右边是若干个非0元构成的三元组顺序表
外层循环一定执行m次，内层循环一定执行n次
以便打印m*n个元素，我们判断外层循环变量i和内存循环变量j，是否分别等于p指向的非0元的行、列下标
这是我们刚才描述的
当然，还有一个前提是未打印完
A当中所有的非0元
p这个变量，一开始就指向第一个非0元
它的初值是0
如果i、j分别与p指向的非0元的i、j对应相等
这时候就直接打印非0元的信息
注意，这里是后置的自增
先用p的原值
因为，p已经指向第一个非0元了
打印完之后
p再自增，指向下一个非0元
else，如果i、j只要有一个跟非0元的i、j不对应相等
这时候，我们应该打印一个零元
最后
内层循环结束之后
我们打印一个换行
以便让矩阵变成多行
这个算法的时间复杂度，很明显
内、外层循环的次数都是固定的
那就是m*n
我们再来看矩阵的另外一类常用的算法：转置，我们将A转置到B
我们知道
B当中每一个非0元，它的行、列下标
实际上是A当中对应非0元的列、行下标
也就是说，我们只需要交换i、j就行了
并且，把A的行、列数分别赋给B的列、行数，就可以了
但是
在交换之后，要保证B按照A中的j非递减排列
因为
存A的时候
是按照行序来存放的
i是非递减的
要保证交换i、j之后
新的行也是非递减的
通过分析
我们知道
B当中的i
实际上是来自于A当中的j的
B当中的i要非递减
那就按照A当中的j去扫描就可以了
比如，我现在定义一个变量，叫col
它的初值是零
我们将A当中所有的非0元都扫描一遍
按照什么来扫描呢？按照j等于col来扫描，第一轮
我们找出那些j等于0的非0元
然后交换它们的行、列下标
2、0、-3，交换i、j
变成0、2、-3，5、0、15变成
0、5、15
第一轮扫描完了之后
col再加1
再重新扫描，进行第二轮扫描，找出那些j等于1的
0、1、12
变成1、0、12，4、1、18变成
1、4、18
如此下去
直到col
取到了最后一个值
也就是A的列数
我们来总结一下，扫描A中全部三元组n次
这个n
就是A的列数
现在，我们来看完整的算法
将以三元组顺序表表示的稀疏矩阵A转置到B当中
我们引入一个循环变量q
它的初值
就指向B当中的第一个非0元
因为，我们就是把A当中p指向的非0元，放到B当中
q指向的非0员的位置
B的行数是A的列数
B的列数是A的行数
非0元是没有变化的
现在我们开始做循环
col从0开始，一直到最后一列
每次
用p来指向A当中的各个非0元
从0开始，一直到最后一个非0元
判断，如果p指向的非0元的列下标
是等于当前的col
这个外层的循环变量的
我们就把它放到B当中
放的时候
B当中非0元的行下标，是等于A当中非0元的列下表的，交换行、列下标
这两行是对称的
值没有变化
然后，q++，指向待存放的下一个非0元的位置
这个算法，通过分析，外层循环
一共执行了n次，内层循环总是执行t次
所以，它的时间复杂度
是n*t，在极端情况下
t和m*n是一个量级的
也就是说，极端情况下
矩阵当中所有的值都是非0元
t是等于m*n的，这时候的时间复杂度
就变成了m*n^2
你会发现，它甚至超过了不采用压缩存储的稀疏矩阵所对应的转置算法
大家想一下
如果我们存放m*n的一个矩阵
我们不采用压缩存储
我们就存
m*n个元素，用二维数组来存放
对这个二维数组进行转置
只需要外层循环循环m次，内层循环循环n次，就能够转置了
而这里用了压缩存储，它的转置时间复杂度却比m*n还要高一个量级
所以，我们得来改进
下面，我们介绍一种快速转置算法
-讲解
-作业
-讨论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 归并排序
--讲解
--作业
-讨论
