文档介绍：关于矩阵及其基本算法
第1页，讲稿共33张，创作于星期二
矩阵及其基本算法
矩阵的表示
矩阵的基本运算
小结和应用举例
第2页，讲稿共33张，创作于星期二
一、矩阵的表示
三角矩阵的压缩表示法
稀疏矩阵的三元组表示法环判断两个矩阵是否相等。
在三元组表示方法中，我们如果保证非零元素是按照从上到下，从左到右的顺序储存的，则可以用一个循环直接判断。但如果不能保证，则需要二重循环。因此在未加说明的情况下，三元组表示法均需要按顺序保存各个元素。
在十字链表表示方法中，我们需要依次遍历每一个非零行（或者列）。
第15页，讲稿共33张，创作于星期二
矩阵的线性运算
矩阵的数乘: B=kA
在任何一种表示法中，我们都可以通过遍历所有元素的方法完成数乘运算。
矩阵的加法: C=A+B
在二维数组表示法中，我们可以通过二重循环来进行矩阵加法
在稀疏矩阵中，注意到结果中的非零元素所在的位置必对应A或B中的一个非零元素，所以加法运算不会在A和B中原非零元素之外的其他位置上生成新的非零元素。
第16页，讲稿共33张，创作于星期二
矩阵的线性运算(2)
考虑三元组表示法中的矩阵加法。由于都需要按顺序储存各个元素，我们应当按顺序对每个A或B中非零的位置做加法。
下面有一个例子：
第17页，讲稿共33张，创作于星期二
矩阵的线性运算(3)
我们记录两个矩阵A，B的当前非零元素序号pA和pB。为了保证结果的有序性，我们每次比较这两个当前元素的位置。
如果A的当前位置靠前，则把A的第pA个元素加入矩阵C，并使pA=pA+1
如果B的当前位置靠前，则把B的第pB个元素加入矩阵C，并使pB=pB+1
如果当前位置相同，则先使pA=pA+1, pB=pB+1。如果A的第pA-1个元素和B的第pB-1个元素的和不为零，则把它加到矩阵C中。
第18页，讲稿共33张，创作于星期二
矩阵的线性运算(4)
十字链表表示法下的加法可以一行行的做。即：
如果A的当前行号比B小，把A的当前行整个复制到C中。
如果B的当前行号比A小，把B的当前行整个复制到C中。
否则把A的当前行和B的当前行的合并结果加入C中。
第三种情况和三元组表示下的加法很类似，只是下标pA,pB换成了指针。
同样的，需要注意两个非零元素之和可能等于零，从而不能插入到结果中
第19页，讲稿共33张，创作于星期二
矩阵的转置(1)
矩阵的转置
在二维数组中，转置可以通过简单的坐标变换得到
在三元组表示法中，在对每个元素进行坐标变换后还需要进行一次排序，以维持元素位置的有序性。
在十字链表表示法中，我们不仅需要对每个结点进行坐标变换，还需要交换行链表和列链表，以及更改每个结点四个方向的指针，实现比较麻烦。
第20页，讲稿共33张，创作于星期二
矩阵的转置(2)
二维数组的转置可以通过下列代码来实现：
void MatrixT(TMatrix A)
{
TMatrix B;
=; =;
for(int i=1;i<=;i++)
for(int j=1;j<=;j++)
[j][i]=[i][j];
return B;
}
对代码稍作修改，我们可以对矩阵进行旋转和镜像变换生成8个新矩阵
第21页，讲稿共33张，创作于星期二
矩阵的转置(3)
前面提到过，三元组表示法中，矩阵的转置可以通过坐标变换后排序来实现。
不过，我们通常使用的是另外一种方法。这种方法不用排序，而速度也更快。
快速转置算法：直接写到正确的位置。
首先，求出每一列第一非零元素转置后的序号。这一步只需要统计一下每列的非零元素的个数就可以了。
由于每一列的元素在转置以后的先后次序保持不变，每个元素就可以直接写到该行的下一个空闲位置。
第22页，讲稿共33张，创作于星期二
矩阵的转置(4)
请看下面的例子：
各列非零元素个数为：2,3,0,1
各列第一个元素序号：0,2,5,5
0 1 2 3 4 5
1
2
3
4
5
6
第23页，讲稿共33张，创作于星期二
矩阵乘法(1)
矩阵乘法
在二维数组表示中，最简单的方法就是对每个元素用循环累加出结果，二重循环枚举每个元素，共三层循环。
在三元组表示中，对于A中的一个元素Aij，我们只需要访问B中第j行所有元素Bjk，把每个乘积Aij ×Bjk加到Cik中。这样，每遍历A的一行元素，就计算出了C的一行元素。和快速转置算法类似，我们可以事先算出B的每行元素的下标范围，再用一个循环依次考虑A中的每个元素就可以了。
十字链表在本质上是三元组的链式存储，所以乘法和三元组差别不大，但是实现却麻烦得多。该方法的好处在于，