矩阵及其基本算法 计13刘汝佳
矩阵及其基本算法 计13 刘汝佳
中b2 矩阵及其基本算法 8矩阵的表示 矩阵的基本运算 8小结和应用举例
矩阵及其基本算法 矩阵的表示 矩阵的基本运算 小结和应用举例
中b2 矩阵的表示 矩阵在形式上最直接的表示是一个二维数组,但 是在些特殊的场合中,我们需要引入一些特殊 的方法来表示一些特殊的矩阵。在本节中,大家 还将了解到以下几种表示方法: 8三角矩阵的压缩表示法 8稀疏矩阵的三元组表示法 ε稀疏矩阵的十字链表表示法
一、矩阵的表示 三角矩阵的压缩表示法 稀疏矩阵的三元组表示法 稀疏矩阵的十字链表表示法 矩阵在形式上最直接的表示是一个二维数组，但 是在一些特殊的场合中，我们需要引入一些特殊 的方法来表示一些特殊的矩阵。在本节中，大家 还将了解到以下几种表示方法:
丰 or esTers 矩阵的二维数组表示法 我们用二维数组很容易表示一个矩阵。加上矩阵的维数 M和N,我们可以定义一个 Matrix结构 s七uc七 MAtrix int n, m. int numbers [MAxN+1] [MAXN+1]; 这就是矩阵的二维数组表示法。怎么样,容易吧?
矩阵的二维数组表示法 struct TMatrix { int n,m; int numbers[MAXN+1][MAXN+1]; }; 我们用二维数组很容易表示一个矩阵。加上矩阵的维数 M和N，我们可以定义一个TMatrix结构: 这就是矩阵的二维数组表示法。怎么样，容易吧？
丰 or esTers 三角矩阵的压缩表示(1) N阶上三角矩阵,对称矩阵和反对称矩阵 都只需要储存主对角线以上的共 (N+1)*N2个元素。 8因此,我们可以用一个大小为N+1)+N2 的一维数组来表示。 8不过,我们需要一个公式,把每个元素 原来的位置(ij映射到_维数组的下标k
三角矩阵的压缩表示(1) N阶上三角矩阵，对称矩阵和反对称矩阵 都只需要储存主对角线以上的共 (N+1)*N/2个元素。 因此，我们可以用一个大小为(N+1)*N/2 的一维数组来表示。 不过，我们需要一个公式，把每个元素 原来的位置(i,j)映射到一维数组的下标k
中b2 三角矩阵的压缩表示(2) 8我们从上到下,从左到右地储存各个元 素,如下图:m aa d aa a3 a4 2223u24 567 3334 ag ao 44 A1前面的数的个数为:∑(n-1+1)+(1-1) 计算得:k=(2n-i+2i-1)+j
三角矩阵的压缩表示(2) 我们从上到下，从左到右地储存各个元 素，如下图： 44 33 34 22 23 24 11 12 13 14 a a a a a a a a a a 10 8 9 5 6 7 1 2 3 4 a a a a a a a a a a Aij前面的数的个数为： 计算得: ( 1) ( 1) 1 1 − + + − − = n l j i l k = (2n −i + 2)(i −1) + j 2 1
中b2 稀疏矩阵 8在前面的二维数组表示法中,我们表示 一个N*M的矩阵需要N*M个内存单元 ε8如果已知矩阵中存在着大量的0元素,那 么这种表示方法是很浪费空间的。 8由于非零元素的个数L十分有限,我们可 以只储存下这L个元素的位置和大小,占 用的空间便会少得多
稀疏矩阵 在前面的二维数组表示法中，我们表示 一个N*M的矩阵需要N*M个内存单元。 如果已知矩阵中存在着大量的0元素，那 么这种表示方法是很浪费空间的。 由于非零元素的个数L十分有限，我们可 以只储存下这L个元素的位置和大小，占 用的空间便会少得多
丰 or esTers 稀疏矩阵的三元组表示法 B8显然,表示稀疏矩阵最直接的方法就是 仅记录下非零元素的个数和这个元素 的位置 (row, co和大小 A(value),即下面这 个结构 s七ruc七 Matrix2 in七1; int row [MaXl], col [MAXL] value [maxl]i
稀疏矩阵的三元组表示法 显然，表示稀疏矩阵最直接的方法就是 仅记录下非零元素的个数L和这L个元素 的位置(row,col)和大小(value)，即下面这 个结构： struct TMatrix2 { int l; int row[MAXL],col[MAXL],value[MAXL]; };
中b2 稀疏矩阵的十字链表表示(1) ε三元组表示法比较好的解决了稀疏矩阵的空间存储问 题,却忽视了稀疏矩阵可能进行了一些基本操作。 8考虑两个稀疏矩阵A和B相加的问题。对于运算结果矩 阵C来说,可能会因为正负抵消而产生出很多新的零元 素和非零元素,导致三元组需要进行一些插入和删除 操作。当这些操作很频繁的时候,程序的速度会明显 变慢。 38在某些特定情况下,我们需要对元素进行检索,由于 三元组的元素之间联系并不紧密,所以检索很不方便
稀疏矩阵的十字链表表示(1) 三元组表示法比较好的解决了稀疏矩阵的空间存储问 题，却忽视了稀疏矩阵可能进行了一些基本操作。 考虑两个稀疏矩阵A和B相加的问题。对于运算结果矩 阵C来说，可能会因为正负抵消而产生出很多新的零元 素和非零元素，导致三元组需要进行一些插入和删除 操作。当这些操作很频繁的时候，程序的速度会明显 变慢。 在某些特定情况下，我们需要对元素进行检索，由于 三元组的元素之间联系并不紧密，所以检索很不方便
中b2 稀疏矩阵的十字链表表示(2) 8为了加强同一行和同一列之间元素的联系,我 们把每一行分别做成一个链表,把每一列也分 别做成一个链表。 B8通过对链表的遍历,我们可以很方便的按顺序 访问到某一特定行或列的所有元素。插入和删 除操作也很方便。 8这样,我们了建立一种十字型的链表结构,每 个结点有上,下,左,右四个指针和自身的位 置坐标,大小共7个域
稀疏矩阵的十字链表表示(2) 为了加强同一行和同一列之间元素的联系，我 们把每一行分别做成一个链表，把每一列也分 别做成一个链表。 通过对链表的遍历，我们可以很方便的按顺序 访问到某一特定行或列的所有元素。插入和删 除操作也很方便。 这样，我们了建立一种十字型的链表结构，每 个结点有上，下，左，右四个指针和自身的位 置坐标，大小共7个域