面不够理想，因此我们需要根据实际需要的侧 重点不同，选择合适的表示方法
二、矩阵的基本运算
矩阵的判重 矩阵的线性运算 矩阵的转置 矩阵乘法
矩阵的判重
在二维数组表示法中，我们可以用一个二重循 环判断两个矩阵是否相等。
在三元组表示方法中，我们如果保证非零元素 是按照从上到下，从左到右的顺序储存的，则 可以用一个循环直接判断。但如果不能保证， 则需要二重循环。因此在未加说明的情况下， 三元组表示法均需要按顺序保存各个元素。
struct TCol
{
{
int RowNo;
int ColNo;
TNode * firstnode; TNode * firstnode;
};
};
矩阵表示方法小结
矩阵的表示方法和应用是分不开的。 我们衡量一种表示方法的优劣，需要从不同的
角度进行分析。 适用范围 空间需求量 基本操作的时间消耗 实现的难易程度 以上几种方法都在某些方面表现良好而其他方
矩阵及其基本算法
矩阵的表示 矩阵的基本运算 小结和应用举例
一、矩阵的表示
矩阵在形式上最直接的表示是一个二维数组，但 是在一些特殊的场合中，我们需要引入一些特殊 的方法来表示一些特殊的矩阵。在本节中，大家 还将了解到以下几种表示方法:
三角矩阵的压缩表示法 稀疏矩阵的三元组表示法 稀疏矩阵的十字链表表示法
因此，我们可以用一个大小为(N+1)*N/2 的一维数组来表示。
不过，我们需要一个公式，把每个元素 原来的位置(i,j)映射到一维数组的下标k。
三角矩阵的压缩表示(2)
我们从上到下，从左到右地储存各个元 素，如下图：
a11 a12 a13 a14

a22
a23
a24


row,col分别为该非零元素的位置，value为它的值。 left,right,up,down分别为指向四个方向的后继元素。
稀疏矩阵的十字链表表示(4)
为了方便的找到每一个包含非零元素的 行和列，我们把所有行串在一起，组成 一个行链表，把所有列也串在一起，组 成一个列链表。像这样：
struct TRow
矩阵的线性运算(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中。
如果已知矩阵中存在着大量的0元素，那 么这种表示方法是很浪费空间的。
由于非零元素的个数L十分有限，我们可 以只储存下这L个元素的位置和大小，占 用的空间便会少得多。
稀疏矩阵的三元组表示法
显然，表示稀疏矩阵最直接的方法就是 仅记录下非零元素的个数L和这L个元素 的位置(row,col)和大小(value)，即下面这 个结构：
a33
a34


a44
a1 a2 a3 a4

a5
a6
a7


a8
a9


a10
i 1
Aij前面的数的个数为： (n l 1) ( j 1)
计算得:


1
l 1
(2n i
2)(i 1)
j
2
稀疏矩阵
在前面的二维数组表示法中，我们表示 一个N*M的矩阵需要N*M个内存单元。
这样，我们了建立一种十字型的链表结构，每 个结点有上，下，左，右四个指针和自身的位 置坐标，大小共7个域。
稀疏矩阵的十字链表表示(3)
结点类型如下定义：
struct Tnode {
int row, col; int value; Tnode *left, *right, *up, *down; };
在十字链表表示方法中，我们需要依次遍历每 一个非零行（或者列）。
矩阵的线性运算
矩阵的数乘: B=kA
在任何一种表示法中，我们都可以通过遍历所有 元素的方法完成数乘运算。
矩阵的加法: C=A+B
在二维数组表示法中，我们可以通过二重循环来 进行矩阵加法
在稀疏矩阵中，注意到结果中的非零元素所在的 位置必对应A或B中的一个非零元素，所以加法运 算不会在A和B中原非零元素之外的其他位置上生 成新的非零元素。
struct TMatrix2 {
int l; int row[MAXL],col[MAXL],value[MAXL]; };
稀疏矩阵的十字链表表示(1)
三元组表示法比较好的解决了稀疏矩阵的空间存储问 题，却忽视了稀疏矩阵可能进行了一些基本操作。
考虑两个稀疏矩阵A和B相加的问题。对于运算结果矩 阵C来说，可能会因为正负抵消而产生出很多新的零元 素和非零元素，导致三元组需要进行一些插入和删除 操作。当这些操作很频繁的时候，程序的速度会明显 变慢。
矩阵的线性运算(2)
考虑三元组表示法中的矩阵加法。由于 都需要按顺序储存各个元素，我们应当 按顺序对每个A或B中非零的位置做加法。
下面有一个例子：
1 0 0 0 0 2 1 0 2
0
5
0 3
0
0 3
5
0

0 2 0 0 7 0 0 9 0
矩阵的二维数组表示法
我们用二维数组很容易表示一个矩阵。加上矩阵的维数 M和N，我们可以定义一个TMatrix结构:
struct TMatrix {
int n,m; int numbers[MAXN+1][MAXN+1]; };
这就是矩阵的二维数组表示法。怎么样，容易吧？
三角矩阵的压缩表示(1)
N阶上三角矩阵，对称矩阵和反对称矩阵 都只需要储存主对角线以上的共 (N+1)*N/2个元素。
在某些特定情况下，我们需要对元素进行检索，由于 三元组的元素之间联系并不紧密，所以检索很不方便。
稀疏矩阵的十字链表表示(2)
为了加强同一行和同一列之间元素的联系，我 们把每一行分别做成一个链表，把每一列也分 别做成一个链表。
通过对链表的遍历，我们可以很方便的按顺序 访问到某一特定行或列的所有元素。插入和删 除操作也很方便。