当前课程知识点：数据结构 > 第4章 数组 > 4.4 稀疏矩阵的压缩存储 > 讲解（下）
刚才，我们介绍的常规转置算法
它的时间复杂度之所以比较高
是因为我们将待转置的矩阵
A当中所有的三元组，都扫描了若干轮
每一轮
判断当前扫描的三元组
它的j是否等于外层的循环变量col
如果相等，就把它放到B.data中合适的位置
现在，我们想降低这个时间复杂度
我们能不能做到：只扫描A当中所有的三元组一轮，每扫描到一个三元组
我们去计算它在B当中应该出现的位置呢
如果我们知道了这个位置，直接放就可以了
比如，0、1、12，交换i、j
变成1、0、12
如果我们知道
1、0、12应该放到下标2这个位置
那我们就可以直接放
问题是你怎么知道1、0、12应该放到下标
2这个位置呢
我们现在这样来分析
我们知道，B当中第一个非0元，也就是下标为0的
这个非0元，它一定是B这个矩阵
的第一行非0元，这是毫无疑问的
因为，我们存放B当中非0元的时候
是按照B的行序来存放的，B当中第一行的首个非0元
它应该是A当中第一列的首个非0元
因为是转置
B当中的每一行是来自于A当中对应的那一列的
A当中第一列的首个非0元，也就是这个-3
它应该出现在B当中的第一个非0元的位置，交换行、列下标
变成0、2、-3
我们确定了第一列首个非0元的位置
我们还知道第一列非0元的个数
该列有2个，那么，它的下一列
第二列的首个非0元在B当中出现的位置，不就是前一列
第一个非0元位置
加上该列非0元的个数吗
也就是，0加2得到2
所以
A当中首个非0元
它的j下标是1
也就是第二列，它在B当中出现的位置就是
0加上2
这样
我们就能够得到每一个非0元的位置
然后，直接把它们放到
B.data中合适的位置，就可以了
这就是快速转置所基于的算法思想
为了达到这个效果
我们引入两个辅助的数组，第一个数组
A中每一列非0元的个数
我们把它放到num数组的某一个元素当中
比如，num[i]表示
A当中第i列非0元的个数
然后，第二个数组
是pos
它表示
A中每一列首个非0元，注意是首个非0元，在B当中出现的位置
刚才，我们在这边分析的时候，曾经介绍过
每一列的首个非0元的位置
加上该列的非0元个数
就是它的下一列首个非0元
在B当中应该出现的位置
我们来初始化这个pos
pos[0]
肯定是0，刚才我们已经分析过了，B.data中第一行的首个非0元，就是A.data中
第一列的首个非0元
所以，pos[0]就是0
pos[j]是多少呢
前面也分析了，第j列首个非0元的位置
就是它前一列首个非0元的位置
加上前一列非0元的个数
这是一个递推公式
num这个数组比较容易统计，每一列非0元的个数
比如，A的第一列2个
第二列2个
第四列只有1个；pos的首个值是0
这个2怎么得来的呢
就是这二者相加，得到2
这二者相加，得到4
这二者相加，得到6
现在，我们就把pos这个数组当中的每一个元素初始化出来了
下面我们要做的事情，就是依次读入A中的每一个三元组
直接放到B.data中的合适位置
我们只扫描A当中三元组一轮，只循环非0元个数次
一个单层的循环，就可以了
每取得p指向的非0元，就把它放到B.data中
合适的位置，就可以了啊
现在，我们来看具体的算法实现
我们将以三元组表示的稀疏矩阵A，把它转置到B当中
快速转置
两个辅助的数组
我们把它们放到这里
现在，我们来看代码
B的行数是A的列数
B的列数是A的行数
非0元个数没有变化
然后，我们声明这两个数组，num和pos
我们只给了一个值
根据C语言的语法规则
剩下的值都是默认值0
第一个for循环，是用来统计
A当中每一列非0元的个数的，我们是循环t次
也就是，取出每一个非0元
看这个非0元
它的j值是多少
用这个j值，作为num数组元素的下标
就是将相应的num分量自增1，表示
这一列上有一个非0元
这个比较简单
再来看第二个并列的for循环，循环1到n-1一共n次，很显然是扫描A的列数
因为pos
它的长度就是A的列数
每一列首个非0元的位置
应该是它前一列首个非0元的位置
加上前一列非0元个数
这直接用到了前面的这个递推公式
pos[0]的值
我们已经给出来了
就是0
第三个for循环，才是完成转置的操作
大家看到，它就是一个单层的for循环，0到t-1，依次取得每一个非0元，用p来指向，取得的这个非0元
我们把它放到tr这个变量里面
因为后面会用到多次
我们取出非0元的列号，也就是j
然后，去查pos这个辅助的数组，列号是1
我们查j为1的pos，发现是2
那么，直接把0、1、12交换i、j，变成1、0、12，放到下标为2的位置
1、0、12在这里
这两行代码
就是交换i、j
值没有变化
还有这一行代码
这行代码将tr.j作为pos的下标，自增1
也就是说，我们刚才将pos[1]这个值
取出来是2
作为第一个非0元0、1、12的存放位置
放完了之后，应该怎么做呢
这里将它自增了1，变成了3
这里为什么要加1呢
我们待会会看到。重复刚才的过程
取出下一个非0元0、2、9，j值是2，查表发现是4
于是，0、2、9直接放到4的位置
变成2、0、9
然后
将4修改成5，自增1
再取出下一个非0元，j下标是0
找pos[0]，是0
那么，直接将2、0、-3变成0、2、-3，放到0的位置
变成
0、2、-3
将这里的0自增1，变成1；再下一个
j值是5
那么，查pos[5]，发现是7
于是，2、5、14变成
5、2、14
直接放到7的位置
然后，这里的7再自增1
再下一个，到现在为止
我们第一次遇到了之前遇到过的j值
我们刚才遇到了一个2
现在又有一个2
那A当中
第三行第二列这个非0元，很明显在B当中，应该是紧接着这个非0元来存放的
这个非0元
我们放到了下标4这个位置
那么3、2、24交换i、j之后，变成2、3、24
很明显
应该紧接着它去放
所以，我们之前将
pos[2]
自增了1，变成了5
以方便去放B当中同一行的下一个非0元，或者说
A当中同一列的下一个非0元
那么，3、2、24直接放到5的位置
变成2、3、24
这里加1的意义，就体现在这里
剩下的几个非0元
我们按照刚才的规则，直接放就可以了
这个算法它的时间复杂度是多少呢
通过分析
第一个for循环执行了t次，第二个for循环执行了n次
第三个for循环执行了t次
所以就是2t+n，极端情况下，t和m*n是同量级的
也就是，极端情况下，所有的元素都是非0元
这时候，算法的时间复杂度就是
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 归并排序
--讲解
--作业
-讨论
