矩阵及其基本算法
计 13 刘汝佳
矩阵及其基本算法
?矩阵的表示
?矩阵的基本运算
?小结和应用举例
一、矩阵的表示
?三角矩阵的压缩表示法
?稀疏矩阵的三元组表示法
?稀疏矩阵的十字链表表示法
矩阵在形式上最直接的表示是一个二维数组，但
是在一些特殊的场合中，我们需要引入一些特殊
的方法来表示一些特殊的矩阵。在本节中，大家
还将了解到以下几种表示方法,
矩阵的二维数组表示法
struct TMatrix
{
int n,m;
int numbers[MAXN+1][MAXN+1];
};
我们用二维数组很容易表示一个矩阵。加上矩阵的维数 M
和 N,我们可以定义一个 TMatrix结构,
这就是矩阵的二维数组表示法。 怎么样，容易吧？
三角矩阵的压缩表示 (1)
? N阶上三角矩阵，对称矩阵和反对称矩阵
都只需要储存主对角线以上的共
(N+1)*N/2个元素。
?因此，我们可以用一个大小为 (N+1)*N/2
的一维数组来表示。
?不过，我们需要一个公式，把每个元素
原来的位置 (i,j)映射到一维数组的下标 k。
三角矩阵的压缩表示 (2)
?我们从上到下，从左到右地储存各个元
素，如下图,
?
?
?
?
?
?
?
?
?
?
?
?
44
3433
242322
14131211
a
aa
aaa
aaaa
?
?
?
?
?
?
?
?
?
?
?
?
10
98
765
4321
a
aa
aaa
aaaa
Aij前面的数的个数为,
计算得,
)1()1(1
1
??????
?
jlni
l
jiink ????? )1)(22(21
稀疏矩阵
?在前面的二维数组表示法中，我们表示
一个 N*M的矩阵需要 N*M个内存单元。
?如果已知矩阵中存在着大量的 0元素，那
么这种表示方法是很浪费空间的。
?由于非零元素的个数 L十分有限，我们可
以只储存下这 L个元素的位置和大小，占
用的空间便会少得多。
稀疏矩阵的三元组表示法
?显然，表示稀疏矩阵最直接的方法就是
仅记录下非零元素的个数 L和这 L个元素
的位置 (row,col)和大小 (value),即下面这
个结构,
struct TMatrix2
{
int l;
int row[MAXL],col[MAXL],value[MAXL];
};
稀疏矩阵的十字链表表示 (1)
? 三元组表示法比较好的解决了稀疏矩阵的空间存储问
题，却忽视了稀疏矩阵可能进行了一些基本操作。
? 考虑两个稀疏矩阵 A和 B相加的问题。对于运算结果矩
阵 C来说，可能会因为正负抵消而产生出很多新的零元
素和非零元素，导致三元组需要进行一些插入和删除
操作。当这些操作很频繁的时候，程序的速度会明显
变慢。
? 在某些特定情况下，我们需要对元素进行检索，由于
三元组的元素之间联系并不紧密，所以检索很不方便。
稀疏矩阵的十字链表表示 (2)
? 为了加强同一行和同一列之间元素的联系，我
们把每一行分别做成一个链表，把每一列也分
别做成一个链表。
? 通过对链表的遍历，我们可以很方便的按顺序
访问到某一特定行或列的所有元素。插入和删
除操作也很方便。
? 这样，我们了建立一种十字型的链表结构，每
个结点有上，下，左，右四个指针和自身的位
置坐标，大小共 7个域。
稀疏矩阵的十字链表表示 (3)
?结点类型如下定义,
struct Tnode
{
int row,col;
int value;
Tnode *left,*right,*up,*down;
};
row,col分别为该非零元素的位置,value为它的值。
left,right,up,down分别为指向四个方向的后继元素。
稀疏矩阵的十字链表表示 (4)
?为了方便的找到每一个包含非零元素的
行和列，我们把所有行串在一起，组成
一个行链表，把所有列也串在一起，组
成一个列链表。像这样,
struct TRow
{
int RowNo;
TNode * firstnode;
};
struct TCol
{
int ColNo;
TNode * firstnode;
};
矩阵表示方法小结
? 矩阵的表示方法和应用是分不开的。
? 我们衡量一种表示方法的优劣，需要从不同的
角度进行分析。
? 适用范围
? 空间需求量
? 基本操作的时间消耗
? 实现的难易程度
? 以上几种方法都在某些方面表现良好而其他方
面不够理想，因此我们需要根据实际需要的侧
重点不同，选择合适的表示方法
二、矩阵的基本运算
?矩阵的判重
?矩阵的线性运算
?矩阵的转置
?矩阵乘法
矩阵的判重
? 在二维数组表示法中，我们可以用一个二重循
环判断两个矩阵是否相等。
? 在三元组表示方法中，我们如果保证非零元素
是按照从上到下，从左到右的顺序储存的，则
可以用一个循环直接判断。但如果不能保证，
则需要二重循环。因此在未加说明的情况下，
三元组表示法均需要按顺序保存各个元素。
? 在十字链表表示方法中，我们需要依次遍历每
一个非零行（或者列）。
矩阵的线性运算
? 矩阵的数乘, B=kA
? 在任何一种表示法中，我们都可以通过遍历所有
元素的方法完成数乘运算。
? 矩阵的加法, C=A+B
? 在二维数组表示法中，我们可以通过二重循环来
进行矩阵加法
? 在稀疏矩阵中，注意到结果中的非零元素所在的
位置必对应 A或 B中的一个非零元素，所以加法运
算不会在 A和 B中原非零元素之外的其他位置上生
成新的非零元素。
矩阵的线性运算 (2)
?考虑三元组表示法中的矩阵加法。由于
都需要按顺序储存各个元素，我们应当
按顺序对每个 A或 B中非零的位置做加法。
?下面有一个例子,
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
090
053
201
070
003
200
020
050
001
矩阵的线性运算 (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中。
矩阵的线性运算 (4)
? 十字链表表示法下的加法可以一行行的做。即,
? 如果 A的当前行号比 B小，把 A的当前行整个复制到 C中。
? 如果 B的当前行号比 A小，把 B的当前行整个复制到 C中。
? 否则把 A的当前行和 B的当前行的合并结果加入 C中。
? 第三种情况和三元组表示下的加法很类似，只
是下标 pA,pB换成了指针。
? 同样的，需要注意两个非零元素之和可能等于
零，从而不能插入到结果中
矩阵的转置 (1)
?矩阵的转置
? 在二维数组中，转置可以通过简单的坐标变换得到
? 在三元组表示法中，在对每个元素进行坐标变换后
还需要进行一次排序，以维持元素位置的有序性。
? 在十字链表表示法中，我们不仅需要对每个结点进
行坐标变换，还需要交换行链表和列链表，以及更
改每个结点四个方向的指针，实现比较麻烦。
矩阵的转置 (2)
? 二维数组的转置可以通过下列代码来实现,
void MatrixT(TMatrix A)
{
TMatrix B;
B.m=A.n; B.n=A.m;
for(int i=1;i<=A.n;i++)
for(int j=1;j<=A.m;j++)
B.numbers[j][i]=A.numbers[i][j];
return B;
}
对代码稍作修改，我们可以对矩阵进行旋转和镜像变换生成 8个新矩阵
矩阵的转置 (3)
? 前面提到过，三元组表示法中，矩阵的转置可
以通过坐标变换后排序来实现。
? 不过，我们通常使用的是另外一种方法。这种
方法不用排序，而速度也更快。
? 快速转置算法：直接写到正确的位置。
? 首先，求出每一列第一非零元素转置后的序号。这一步只需
要统计一下每列的非零元素的个数就可以了。
? 由于每一列的元素在转置以后的先后次序保持不变，每个元
素就可以直接写到该行的下一个空闲位置。
矩阵的转置 (4)
? 请看下面的例子,
?
?
?
?
?
?
?
?
?
?
?
?
0045
0000
0063
2010 各列非零元素个数为,2,3,0,1
各列第一个元素序号,0,2,5,5
?
?
?
?
?
?
?
?
?
?
?
?
0002
0000
4061
5030
0 1 2 3 4 5
1 2 3 4 5 6
矩阵乘法 (1)
?矩阵乘法
? 在二维数组表示中，最简单的方法就是对每个元素用循环累
加出结果，二重循环枚举每个元素，共三层循环。
? 在三元组表示中，对于 A中的一个元素 Aij,我们只需要访问 B
中第 j行所有元素 Bjk,把每个乘积 Aij × Bjk加到 Cik中。这样，
每遍历 A的一行元素，就计算出了 C的一行元素。和快速转置
算法类似，我们可以事先算出 B的每行元素的下标范围，再用
一个循环依次考虑 A中的每个元素就可以了。
? 十字链表在本质上是三元组的链式存储，所以乘法和三元组
差别不大，但是实现却麻烦得多。该方法的好处在于，把中
间结果 Aij × Bjk 加到 Cik时，如果 Cik并不存在，就需要对矩阵
进行插入操作。在十字链表上的插入操作比三元组快得多。
矩阵乘法 (2)
? Strassen矩阵乘法
? 下面，我们来介绍基于二维数组的矩阵相乘算法。
? 考虑两个 2*2矩阵 A和 B相乘。
?
?
?
?
?
?
??
?
?
?
?
?
??
??
??
?
?
?
?
?
?
??
?
?
?
?
?
?
2221
1211
2222122121221121
2212121121121111
2221
1211
2221
1211
cc
cc
babababa
babababa
ABC
bb
bb
B
aa
aa
A
则有：
普通的方法需要进行 8次乘法。
矩阵乘法 (3)
? Strassen的新方法如下,
))((
))((
)(
)(
)(
)(
))((
22212212
12111121
221211
112122
221211
112221
22112211
bbaaV
bbaaU
baaT
bbaS
bbaR
baaQ
bbaaP
???
???
??
??
??
??
???
UQRPc
SQc
TRc
VTSPc
????
??
??
????
22
21
12
11
:则
只需要 7次乘法 !!!
矩阵乘法 (3)
?当矩阵为 2N*2N时，我们可以利用分块矩
阵，分成 2*2个 2N-1*2N-1矩阵，递归求解。
当 N=1时可以直接利用公式得出结果。
?分析指出,Strassen乘法比常规乘法的加
法和乘法运算量都有减少，但存储量增
加，是一种用空间换时间的方法。
?此方法还可以推广到矩阵的求逆运算。
三、小结与应用举例
?矩阵表示小结
?矩阵运算小结
?结束语
?鸣谢
小结 – 矩阵的表示
?矩阵的表示
? 矩阵有三种常用的表示方法：二维数组，三元组和
十字链表。
? 二维数组适合稠密矩阵，表示直观，操作方便
? 三元组是稀疏矩阵最省空间的表示方法之一，它可
以很好的支持线性运算和乘法运算，且编程复杂度
低，是稀疏矩阵表示法的首选。
? 十字链表比三元组占用空间大些，不过仍适合稀疏
矩阵的表示，尤其适用于非零元素个数变化较大的
场合，但不适合转置操作，且编程实现难度较大。
小结 – 矩阵的运算
? 矩阵的运算
? 三种方法都可以通过遍历表的方式判定两个矩阵是否相同。
? 三种表示方法都能较好的支持线性运算。数乘运算只需要遍
历一次所有元素，而稀疏矩阵的加法运算需要进行类似有序
表合并的操作。
? 二维数组的转置只需要进行坐标变换，三元组还需要排序，
而十字链表需要更新多个指针域。转置可以推广到平面点阵
图象的变换，这时一般采用数组来表示矩阵。
? 矩阵乘法的算法有很多种。基于数组的算法中,Strassen算法
是一种以空间换时间的算法。稀疏的乘法不是依次计算结果
的每个元素，而是依次考虑 A和 B的每对元素对结果的贡献。
结束语
? 在前面的内容中，我们讨论了矩阵的表示和基本运
算。希望这些内容能开阔大家的眼界，启发大家的
思维，激发大家进一步学习的兴趣。
? 这些内容只是矩阵中最最基本的东西。像初等变换，
矩阵求逆，求特征值等方面并为涉及到。但是如果
能熟练的掌握以上内容，相信各位各方面的能力都
会有显著的提高。
? 每一个内容都有它存在的理由，每一种方法都体现
出一种思路。前面提到的快速转置,Strassen矩阵乘
法等算法都值得我们去思考。
鸣 谢
? 感谢吴老师给我这次与大家交流的机会。
? 感谢各位同学，特别是我的室友在我准备期间
给我支持和鼓励
? 感谢一位不愿意我透露其姓名的同学协助我校
对本幻灯片
? 感谢大家专心听完我的《矩阵及其基本算法,
同学们辛苦了！
计 13 刘汝佳
矩阵及其基本算法
?矩阵的表示
?矩阵的基本运算
?小结和应用举例
一、矩阵的表示
?三角矩阵的压缩表示法
?稀疏矩阵的三元组表示法
?稀疏矩阵的十字链表表示法
矩阵在形式上最直接的表示是一个二维数组，但
是在一些特殊的场合中，我们需要引入一些特殊
的方法来表示一些特殊的矩阵。在本节中，大家
还将了解到以下几种表示方法,
矩阵的二维数组表示法
struct TMatrix
{
int n,m;
int numbers[MAXN+1][MAXN+1];
};
我们用二维数组很容易表示一个矩阵。加上矩阵的维数 M
和 N,我们可以定义一个 TMatrix结构,
这就是矩阵的二维数组表示法。 怎么样，容易吧？
三角矩阵的压缩表示 (1)
? N阶上三角矩阵，对称矩阵和反对称矩阵
都只需要储存主对角线以上的共
(N+1)*N/2个元素。
?因此，我们可以用一个大小为 (N+1)*N/2
的一维数组来表示。
?不过，我们需要一个公式，把每个元素
原来的位置 (i,j)映射到一维数组的下标 k。
三角矩阵的压缩表示 (2)
?我们从上到下，从左到右地储存各个元
素，如下图,
?
?
?
?
?
?
?
?
?
?
?
?
44
3433
242322
14131211
a
aa
aaa
aaaa
?
?
?
?
?
?
?
?
?
?
?
?
10
98
765
4321
a
aa
aaa
aaaa
Aij前面的数的个数为,
计算得,
)1()1(1
1
??????
?
jlni
l
jiink ????? )1)(22(21
稀疏矩阵
?在前面的二维数组表示法中，我们表示
一个 N*M的矩阵需要 N*M个内存单元。
?如果已知矩阵中存在着大量的 0元素，那
么这种表示方法是很浪费空间的。
?由于非零元素的个数 L十分有限，我们可
以只储存下这 L个元素的位置和大小，占
用的空间便会少得多。
稀疏矩阵的三元组表示法
?显然，表示稀疏矩阵最直接的方法就是
仅记录下非零元素的个数 L和这 L个元素
的位置 (row,col)和大小 (value),即下面这
个结构,
struct TMatrix2
{
int l;
int row[MAXL],col[MAXL],value[MAXL];
};
稀疏矩阵的十字链表表示 (1)
? 三元组表示法比较好的解决了稀疏矩阵的空间存储问
题，却忽视了稀疏矩阵可能进行了一些基本操作。
? 考虑两个稀疏矩阵 A和 B相加的问题。对于运算结果矩
阵 C来说，可能会因为正负抵消而产生出很多新的零元
素和非零元素，导致三元组需要进行一些插入和删除
操作。当这些操作很频繁的时候，程序的速度会明显
变慢。
? 在某些特定情况下，我们需要对元素进行检索，由于
三元组的元素之间联系并不紧密，所以检索很不方便。
稀疏矩阵的十字链表表示 (2)
? 为了加强同一行和同一列之间元素的联系，我
们把每一行分别做成一个链表，把每一列也分
别做成一个链表。
? 通过对链表的遍历，我们可以很方便的按顺序
访问到某一特定行或列的所有元素。插入和删
除操作也很方便。
? 这样，我们了建立一种十字型的链表结构，每
个结点有上，下，左，右四个指针和自身的位
置坐标，大小共 7个域。
稀疏矩阵的十字链表表示 (3)
?结点类型如下定义,
struct Tnode
{
int row,col;
int value;
Tnode *left,*right,*up,*down;
};
row,col分别为该非零元素的位置,value为它的值。
left,right,up,down分别为指向四个方向的后继元素。
稀疏矩阵的十字链表表示 (4)
?为了方便的找到每一个包含非零元素的
行和列，我们把所有行串在一起，组成
一个行链表，把所有列也串在一起，组
成一个列链表。像这样,
struct TRow
{
int RowNo;
TNode * firstnode;
};
struct TCol
{
int ColNo;
TNode * firstnode;
};
矩阵表示方法小结
? 矩阵的表示方法和应用是分不开的。
? 我们衡量一种表示方法的优劣，需要从不同的
角度进行分析。
? 适用范围
? 空间需求量
? 基本操作的时间消耗
? 实现的难易程度
? 以上几种方法都在某些方面表现良好而其他方
面不够理想，因此我们需要根据实际需要的侧
重点不同，选择合适的表示方法
二、矩阵的基本运算
?矩阵的判重
?矩阵的线性运算
?矩阵的转置
?矩阵乘法
矩阵的判重
? 在二维数组表示法中，我们可以用一个二重循
环判断两个矩阵是否相等。
? 在三元组表示方法中，我们如果保证非零元素
是按照从上到下，从左到右的顺序储存的，则
可以用一个循环直接判断。但如果不能保证，
则需要二重循环。因此在未加说明的情况下，
三元组表示法均需要按顺序保存各个元素。
? 在十字链表表示方法中，我们需要依次遍历每
一个非零行（或者列）。
矩阵的线性运算
? 矩阵的数乘, B=kA
? 在任何一种表示法中，我们都可以通过遍历所有
元素的方法完成数乘运算。
? 矩阵的加法, C=A+B
? 在二维数组表示法中，我们可以通过二重循环来
进行矩阵加法
? 在稀疏矩阵中，注意到结果中的非零元素所在的
位置必对应 A或 B中的一个非零元素，所以加法运
算不会在 A和 B中原非零元素之外的其他位置上生
成新的非零元素。
矩阵的线性运算 (2)
?考虑三元组表示法中的矩阵加法。由于
都需要按顺序储存各个元素，我们应当
按顺序对每个 A或 B中非零的位置做加法。
?下面有一个例子,
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
090
053
201
070
003
200
020
050
001
矩阵的线性运算 (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中。
矩阵的线性运算 (4)
? 十字链表表示法下的加法可以一行行的做。即,
? 如果 A的当前行号比 B小，把 A的当前行整个复制到 C中。
? 如果 B的当前行号比 A小，把 B的当前行整个复制到 C中。
? 否则把 A的当前行和 B的当前行的合并结果加入 C中。
? 第三种情况和三元组表示下的加法很类似，只
是下标 pA,pB换成了指针。
? 同样的，需要注意两个非零元素之和可能等于
零，从而不能插入到结果中
矩阵的转置 (1)
?矩阵的转置
? 在二维数组中，转置可以通过简单的坐标变换得到
? 在三元组表示法中，在对每个元素进行坐标变换后
还需要进行一次排序，以维持元素位置的有序性。
? 在十字链表表示法中，我们不仅需要对每个结点进
行坐标变换，还需要交换行链表和列链表，以及更
改每个结点四个方向的指针，实现比较麻烦。
矩阵的转置 (2)
? 二维数组的转置可以通过下列代码来实现,
void MatrixT(TMatrix A)
{
TMatrix B;
B.m=A.n; B.n=A.m;
for(int i=1;i<=A.n;i++)
for(int j=1;j<=A.m;j++)
B.numbers[j][i]=A.numbers[i][j];
return B;
}
对代码稍作修改，我们可以对矩阵进行旋转和镜像变换生成 8个新矩阵
矩阵的转置 (3)
? 前面提到过，三元组表示法中，矩阵的转置可
以通过坐标变换后排序来实现。
? 不过，我们通常使用的是另外一种方法。这种
方法不用排序，而速度也更快。
? 快速转置算法：直接写到正确的位置。
? 首先，求出每一列第一非零元素转置后的序号。这一步只需
要统计一下每列的非零元素的个数就可以了。
? 由于每一列的元素在转置以后的先后次序保持不变，每个元
素就可以直接写到该行的下一个空闲位置。
矩阵的转置 (4)
? 请看下面的例子,
?
?
?
?
?
?
?
?
?
?
?
?
0045
0000
0063
2010 各列非零元素个数为,2,3,0,1
各列第一个元素序号,0,2,5,5
?
?
?
?
?
?
?
?
?
?
?
?
0002
0000
4061
5030
0 1 2 3 4 5
1 2 3 4 5 6
矩阵乘法 (1)
?矩阵乘法
? 在二维数组表示中，最简单的方法就是对每个元素用循环累
加出结果，二重循环枚举每个元素，共三层循环。
? 在三元组表示中，对于 A中的一个元素 Aij,我们只需要访问 B
中第 j行所有元素 Bjk,把每个乘积 Aij × Bjk加到 Cik中。这样，
每遍历 A的一行元素，就计算出了 C的一行元素。和快速转置
算法类似，我们可以事先算出 B的每行元素的下标范围，再用
一个循环依次考虑 A中的每个元素就可以了。
? 十字链表在本质上是三元组的链式存储，所以乘法和三元组
差别不大，但是实现却麻烦得多。该方法的好处在于，把中
间结果 Aij × Bjk 加到 Cik时，如果 Cik并不存在，就需要对矩阵
进行插入操作。在十字链表上的插入操作比三元组快得多。
矩阵乘法 (2)
? Strassen矩阵乘法
? 下面，我们来介绍基于二维数组的矩阵相乘算法。
? 考虑两个 2*2矩阵 A和 B相乘。
?
?
?
?
?
?
??
?
?
?
?
?
??
??
??
?
?
?
?
?
?
??
?
?
?
?
?
?
2221
1211
2222122121221121
2212121121121111
2221
1211
2221
1211
cc
cc
babababa
babababa
ABC
bb
bb
B
aa
aa
A
则有：
普通的方法需要进行 8次乘法。
矩阵乘法 (3)
? Strassen的新方法如下,
))((
))((
)(
)(
)(
)(
))((
22212212
12111121
221211
112122
221211
112221
22112211
bbaaV
bbaaU
baaT
bbaS
bbaR
baaQ
bbaaP
???
???
??
??
??
??
???
UQRPc
SQc
TRc
VTSPc
????
??
??
????
22
21
12
11
:则
只需要 7次乘法 !!!
矩阵乘法 (3)
?当矩阵为 2N*2N时，我们可以利用分块矩
阵，分成 2*2个 2N-1*2N-1矩阵，递归求解。
当 N=1时可以直接利用公式得出结果。
?分析指出,Strassen乘法比常规乘法的加
法和乘法运算量都有减少，但存储量增
加，是一种用空间换时间的方法。
?此方法还可以推广到矩阵的求逆运算。
三、小结与应用举例
?矩阵表示小结
?矩阵运算小结
?结束语
?鸣谢
小结 – 矩阵的表示
?矩阵的表示
? 矩阵有三种常用的表示方法：二维数组，三元组和
十字链表。
? 二维数组适合稠密矩阵，表示直观，操作方便
? 三元组是稀疏矩阵最省空间的表示方法之一，它可
以很好的支持线性运算和乘法运算，且编程复杂度
低，是稀疏矩阵表示法的首选。
? 十字链表比三元组占用空间大些，不过仍适合稀疏
矩阵的表示，尤其适用于非零元素个数变化较大的
场合，但不适合转置操作，且编程实现难度较大。
小结 – 矩阵的运算
? 矩阵的运算
? 三种方法都可以通过遍历表的方式判定两个矩阵是否相同。
? 三种表示方法都能较好的支持线性运算。数乘运算只需要遍
历一次所有元素，而稀疏矩阵的加法运算需要进行类似有序
表合并的操作。
? 二维数组的转置只需要进行坐标变换，三元组还需要排序，
而十字链表需要更新多个指针域。转置可以推广到平面点阵
图象的变换，这时一般采用数组来表示矩阵。
? 矩阵乘法的算法有很多种。基于数组的算法中,Strassen算法
是一种以空间换时间的算法。稀疏的乘法不是依次计算结果
的每个元素，而是依次考虑 A和 B的每对元素对结果的贡献。
结束语
? 在前面的内容中，我们讨论了矩阵的表示和基本运
算。希望这些内容能开阔大家的眼界，启发大家的
思维，激发大家进一步学习的兴趣。
? 这些内容只是矩阵中最最基本的东西。像初等变换，
矩阵求逆，求特征值等方面并为涉及到。但是如果
能熟练的掌握以上内容，相信各位各方面的能力都
会有显著的提高。
? 每一个内容都有它存在的理由，每一种方法都体现
出一种思路。前面提到的快速转置,Strassen矩阵乘
法等算法都值得我们去思考。
鸣 谢
? 感谢吴老师给我这次与大家交流的机会。
? 感谢各位同学，特别是我的室友在我准备期间
给我支持和鼓励
? 感谢一位不愿意我透露其姓名的同学协助我校
对本幻灯片
? 感谢大家专心听完我的《矩阵及其基本算法,
同学们辛苦了！
