矩阵及其基本算法.ppt

结束语在前面的内容中，我们讨论了矩阵的表示和基本运算。希望这些内容能开阔大家的眼界，启发大家的思维，激发大家进一步学习的兴趣。这些内容只是矩阵中最最基本的东西。像初等变换，矩阵求逆，求特征值等方面并为涉及到。但是如果能熟练的掌握以上内容，相信各位各方面的能力都会有显著的提高。每一个内容都有它存在的理由，每一种方法都体现出一种思路。前面提到的快速转置，Strassen矩阵乘法等算法都值得我们去思考。第31页,共33页，星期六，2024年，5月鸣谢感谢吴老师给我这次与大家交流的机会。感谢各位同学，特别是我的室友在我准备期间给我支持和鼓励感谢一位不愿意我透露其姓名的同学协助我校对本幻灯片感谢大家专心听完我的《矩阵及其基本算法》同学们辛苦了！第32页,共33页，星期六，2024年，5月感谢大家观看第33页,共33页，星期六，2024年，5月关于矩阵及其基本算法矩阵及其基本算法矩阵的表示矩阵的基本运算小结和应用举例第2页,共33页，星期六，2024年，5月一、矩阵的表示三角矩阵的压缩表示法稀疏矩阵的三元组表示法稀疏矩阵的十字链表表示法矩阵在形式上最直接的表示是一个二维数组，但是在一些特殊的场合中，我们需要引入一些特殊的方法来表示一些特殊的矩阵。在本节中，大家还将了解到以下几种表示方法:第3页,共33页，星期六，2024年，5月矩阵的二维数组表示法structTMatrix{intn,m;intnumbers[MAXN+1][MAXN+1];};我们用二维数组很容易表示一个矩阵。加上矩阵的维数M和N，我们可以定义一个TMatrix结构:这就是矩阵的二维数组表示法。怎么样，容易吧？第4页,共33页，星期六，2024年，5月三角矩阵的压缩表示(1)N阶上三角矩阵，对称矩阵和反对称矩阵都只需要储存主对角线以上的共(N+1)*N/2个元素。因此，我们可以用一个大小为(N+1)*N/2的一维数组来表示。不过，我们需要一个公式，把每个元素原来的位置(i,j)映射到一维数组的下标k。第5页,共33页，星期六，2024年，5月三角矩阵的压缩表示(2)我们从上到下，从左到右地储存各个元素，如下图：Aij前面的数的个数为：计算得:第6页,共33页，星期六，2024年，5月稀疏矩阵在前面的二维数组表示法中，我们表示一个N*M的矩阵需要N*M个内存单元。如果已知矩阵中存在着大量的0元素，那么这种表示方法是很浪费空间的。由于非零元素的个数L十分有限，我们可以只储存下这L个元素的位置和大小，占用的空间便会少得多。第7页,共33页，星期六，2024年，5月稀疏矩阵的三元组表示法显然，表示稀疏矩阵最直接的方法就是仅记录下非零元素的个数L和这L个元素的位置(row,col)和大小(value)，即下面这个结构：structTMatrix2{intl;introw[MAXL],col[MAXL],value[MAXL];};第8页,共33页，星期六，2024年，5月稀疏矩阵的十字链表表示(1)三元组表示法比较好的解决了稀疏矩阵的空间存储问题，却忽视了稀疏矩阵可能进行了一些基本操作。考虑两个稀疏矩阵A和B相加的问题。对于运算结果矩阵C来说，可能会因为正负抵消而产生出很多新的零元素和非零元素，导致三元组需要进行一些插入和删除操作。当这些操作很频繁的时候，程序的速度会明显变慢。在某些特定情况下，我们需要对元素进行检索，由于三元组的元素之间联系并不紧密，所以检索很不方便。第9页,共33页，星期六，2024年，5月稀疏矩阵的十字链表表示(2)为了加强同一行和同一列之间元素的联系，我们把每一行分别做成一个链表，把每一列也分别做成一个链表。通过对链表的遍历，我们可以很方便的按顺序访问到某一特定行或列的所有元素。插入和删除操作也很方便。这样，我们了建立一种十字型的链表结构，每个结点有上，下，左，右四个指针和自身的位置坐标，大小共7个域。第10页,共33页，星期六，2024年，5月稀疏矩阵的十字链表表示(3)结点类型如下定义：structTnode{introw,col;intvalue;Tnode*left,*right,*up,*down;};row,col分别为该非零元素的位置，value为它的值。left,right,up,down分别为指向四个方向的后继元素。第11页,共33页，星期六，2024年，5月稀疏矩阵的十字链表表示(4)为了方便的找到每一个包含非零元素的行和列，我们把所有行串在一起，组成一个行链表，把所有列也串在一起，组成一个列链表。像这样：