《计算机程序设计基础》矩阵及其基本算法

矩阵及其基本算法 计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个域