文档介绍：矩阵及其基本算法
计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)
我们从上到下,从左到右地储存各个元素,如下图:
Aij前面的数的个数为:
计算得:
稀疏矩阵
在前面的二维数组表示法中,我们表示一个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个域。