数组和稀疏矩阵课件.ppt

《数组和稀疏矩阵课件.ppt》由会员分享，可在线阅读，更多相关《数组和稀疏矩阵课件.ppt（57页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、关于数组和稀疏矩阵第1页，此课件共57页哦5.1.1 5.1.1 数组的基本概念数组的基本概念 数数组组是是n(n1)个个相相同同类类型型数数据据元元素素a0,a1,an-1构构成成的的有有限限序序列列,且且该该有有限限序序列列存存储储在在一一块块地地址址连连续续的的内内存存单单元中。元中。由此可见由此可见,数组的定义类似于采用顺序存储结构的线性表。数组的定义类似于采用顺序存储结构的线性表。第2页，此课件共57页哦数组具有以下性质：数组具有以下性质：(1)数数组组中中的的数数据据元元素素数数目目固固定定，一一旦旦定定义义了了一一个个数数组，其数据元素数目不再有增减变化。组，其数据元素数目不再有

2、增减变化。(2)数组中的数据元素具有相同的数据类型。数组中的数据元素具有相同的数据类型。(3)数数组组中中的的每每个个数数据据元元素素都都和和一一组组唯唯一一的的下下标标值值对应。对应。(4)数数组组是是一一种种随随机机存存储储结结构构，可可随随机机存存取取数数组组中中的任意数据元素。的任意数据元素。第3页，此课件共57页哦5.1.2 5.1.2 数组的存储结构数组的存储结构 在在一一维维数数组组中中,假假设设a0的的存存储储地地址址由由LOC(a0)确确定定,且且每每个个数数据据元元素素占占用用k个个存存储储单单元元,则则任任一一数数据据元元素素ai的的存存储储地地址址LOC(ai)就可由以

3、下公式求出：就可由以下公式求出：LOC(ai)=LOC(a0)+i*k(0in-1)上上式式说说明明,一一维维数数组组中中任任一一数数据据元元素素的的存存储储地地址址可可直直接接计计算算得得到到,即即一一维维数数组组中中任任一一数数据据元元素素可可直直接接存存取取。因因此此,一一维维数数组组是是一一种种随随机机存存储储结结构构。同同样样,二二维维及及多多维维数数组组也也满满足足随随机机存储特性。存储特性。第4页，此课件共57页哦对于一个对于一个m m行行n n列的二维数组列的二维数组A Amnmn,有：有：将将Am*n简记为简记为A,A是这样的一维数组：是这样的一维数组：A=(a0,a1,ai

4、,am-1)其中其中,ai=(ai,0,ai,1,ai,n1)(0im-1)。第5页，此课件共57页哦 显显然然,二二维维数数组组同同样样满满足足数数组组的的定定义义。一一个个二二维维数数组组可可以以看看作作是是每每个个数数据据元元素素都都是是相相同同类类型型的的一一维维数数组组的的一一维维数数组组。以以此此类类推推,任任何何多多维维数数组组都都可可以以看看作作一一个个线线性性表表，这这时时线线性性表表中中的的每每个个数数据据元元素素也也是是一一个个线线性性表表。多多维维数组是线性表的推广。数组是线性表的推广。第6页，此课件共57页哦 对对于于二二维维数数组组来来说说，由由于于计计算算机机的的

5、存存储储结结构构是是线线性性的的,如如何何用用线线性性的的存存储储结结构构存存放放二二维维数数组组元元素素就就有有一一个个行行列列次次序序排排放放问问题。题。以以行行序序为为主主序序的的存存储储方方式式：即即先先存存储储第第1行行,然然后后紧紧接接着着存存储第储第2行行,最后存储第最后存储第m行。此时行。此时,二维数组的线性排列次序为：二维数组的线性排列次序为：a0,0,a0,1,a0,n-1,a1,0,a1,1,a2,n-1,am-1,0,am-1,1,am-1,n-1第7页，此课件共57页哦 对对一一个个已已知知以以行行序序为为主主序序的的计计算算机机系系统统中中,当当二二维维数数组组第第

6、一一个个数数据据元元素素a0,0的的存存储储地地址址LOC(a0,0)和和每每个个数数据据元元素素所所占占用用的的存存储储单单元元k确确定定后后,则则该该二二维维数数组组中中任任一一数数据据元元素素ai,j的的存存储地址可由下式确定：储地址可由下式确定：LOC(ai,j)=LOC(a0,0)+i*n+j*k 其中其中n为列数。为列数。第8页，此课件共57页哦 同理可推出在以列序为主序的计算机系统中有：同理可推出在以列序为主序的计算机系统中有：LOC(ai,j)=LOC(a0,0)+j*m+i*k 其中其中m为行数为行数。第9页，此课件共57页哦 例例5.1 对二维数组对二维数组float a5

7、4计算：计算：(1)数组数组a中的数组元素数目；中的数组元素数目；(2)若若数数组组a的的起起始始地地址址为为2000，且且每每个个数数组组元元素素长长度度为为32位位(即即4个字节个字节)，数组元素，数组元素a32的内存地址。的内存地址。第10页，此课件共57页哦 解：该数组的元素数目共有解：该数组的元素数目共有5*4=20个。个。由于由于C语言采用行序为主序的存储方式语言采用行序为主序的存储方式,则有：则有：LOC(a3,2)=LOC(a0,0)+(i*n+j)*k =2000+(3*4+2)*4=2056第11页，此课件共57页哦5.1.3 特殊矩阵的压缩存储特殊矩阵的压缩存储 特特殊殊

8、矩矩阵阵是是指指非非零零元元素素或或零零元元素素的的分分布布有有一一定定规规律律的的矩矩阵阵，为为了了节节省省存存储储空空间间,特特别别是是在在高高阶阶矩矩阵阵的的情情况况下下，可可以以利利用用特特殊殊矩矩阵阵的的规规律律,对对它它们们进进行行压压缩缩存存储储，也也就就是是说说，使使多多个个相相同同的的非零元素共享同一个存储单元，对零元素不分配存储空间。非零元素共享同一个存储单元，对零元素不分配存储空间。特特殊殊矩矩阵阵的的主主要要形形式式有有对对称称矩矩阵阵、对对角角矩矩阵阵等等，它它们们都都是是方阵，即行数和列数相同。方阵，即行数和列数相同。第12页，此课件共57页哦 1.对称矩阵的压缩存

9、储对称矩阵的压缩存储 若若一一个个n阶阶方方阵阵Ann中中的的元元素素满满足足ai,j=aj,i(1i,jn),则则称称其为其为n阶阶对称矩阵对称矩阵。由由于于对对称称矩矩阵阵中中的的元元素素关关于于主主对对角角线线对对称称，因因此此在在存存储储时时可可只只存存储储对对称称矩矩阵阵中中上上三三角角或或下下三三角角中中的的元元素素，使使得得对对称称的的元元素素共共享享一一个个存存储储空空间间。这这样样,就就可可以以将将n2个个元元素素压压缩缩存存储储到到n(n+1)/2个个元元素素的的空空间间中中。不不失失一一般般性性,我我们们以以行行序序为主序存储其为主序存储其下三角下三角(包括对角线包括对角

10、线)的元素，例如：的元素，例如：第13页，此课件共57页哦 1 5 1 3 7 a11 5 0 8 0 0 a21 a 22 1 8 9 2 6 a31 a32 a33 3 0 2 5 1 .7 0 6 1 3 an1 a n2 an3 a nn 在这个下三角矩阵中，第在这个下三角矩阵中，第i i行恰有行恰有i i个元素，元素总数个元素，元素总数为：为：n(n+1)/2n(n+1)/2 因此，我们可以按从上到下、从左到右将这些元素存放在因此，我们可以按从上到下、从左到右将这些元素存放在一个向量一个向量b0.n(n+1)/2-1b0.n(n+1)/2-1中。为了便于访问对称矩阵中。为了便于访问对

11、称矩阵A A中中的元素，我们必须在的元素，我们必须在a aijij和和bkbk之间找一个对应关系。之间找一个对应关系。第14页，此课件共57页哦 若若ijij，则，则a aijij在下三角形中。在下三角形中。a aijij之前的之前的i-1i-1行共有行共有1+2+i-1=i(i-1)/21+2+i-1=i(i-1)/2个元素，在第个元素，在第i i行上，行上，a aijij之前有之前有j-1j-1个个元素（即元素（即a ai1i1,a,ai2i2,a,ai3i3,a,aij-1ij-1），因此有：），因此有：a11 a21 a22 a31 an1 annk=0 1 2 3-1i*(i-1)/

12、2+j1 i*(i-1)/2+j1 当当i=ji=jj*(j-1)/2+i-1 j*(j-1)/2+i-1 当当ijijk=第15页，此课件共57页哦2.三角矩阵的压缩存储三角矩阵的压缩存储 以主对角线划分，三角矩阵有上三角和下三角两种。以主对角线划分，三角矩阵有上三角和下三角两种。上三角矩阵如图上三角矩阵如图a a所示，它的下三角（不包括主对角线）所示，它的下三角（不包括主对角线）中的元素均为常数中的元素均为常数c c。下三角矩阵正好相反，它的主对。下三角矩阵正好相反，它的主对角线上方均为常数角线上方均为常数c c，如图，如图b b所示。在大多数情况下，所示。在大多数情况下，三角矩阵三角矩阵

13、常数为零常数为零。a00 a01 a 0 n-1 a00 c c c a11 a 1 n-1 a10 a11 c .c c a n-1 n-1 an-1 0 an-1 1 an-1 n-1 (a)(a)上三角矩阵上三角矩阵 (b)(b)下三角矩阵下三角矩阵第16页，此课件共57页哦 三角矩阵的重复元素三角矩阵的重复元素c c可共享一个存储空间，其余元素正好有可共享一个存储空间，其余元素正好有n(n+1)/2n(n+1)/2个，因此，三角矩阵可压缩存储到个，因此，三角矩阵可压缩存储到b0.n(n+1)/2b0.n(n+1)/2中，中，其中其中c c存放在最后一个分量中。存放在最后一个分量中。上三

14、角矩阵中，主对角线之上的第上三角矩阵中，主对角线之上的第i i行行(0in)(0ijijk=下三角矩阵的存储和对称矩阵类似，下三角矩阵的存储和对称矩阵类似，bk和和aij对应关系是：对应关系是：i(i+1)/2+j ij n(n+1)/2 ijk=第17页，此课件共57页哦 3.对角矩阵的压缩存储对角矩阵的压缩存储 若若一一个个n阶阶方方阵阵A满满足足其其所所有有非非零零元元素素都都集集中中在在以以主主对对角角线线为为中中心心的的带带状状区区域域中中，则则称称其其为为n阶阶对对角角矩矩阵阵，其其主主对对角角线线上上下下方方各各有有b条条次次对对角角线线,称称b为为矩矩阵阵半半带带宽宽，(2b+

15、1)为为矩矩阵阵的的带带宽宽。对对于于半半带带宽宽为为b(0b(n-1)/2)的的对对角角矩矩阵阵，其其|i-j|b的的元元素素ai,j不不为为零零,其其余余元元素素为为零零。下下图所示是半带宽为图所示是半带宽为b的对角矩阵示意图。的对角矩阵示意图。第18页，此课件共57页哦 半带宽为半带宽为b b的对角矩阵的对角矩阵 第19页，此课件共57页哦 a00 a01 a10 a11 a12 a21 a22 a23 .可用以行序为主序的可用以行序为主序的 an-2 n-3 an-2 n-2 an-2 n-1 an-1 n-2 an-1 n-1 形式存储形式存储b3n-2中中 当当b1时称为三对角矩阵

16、，如：时称为三对角矩阵，如：主对角线下方的元素的下标关系为主对角线下方的元素的下标关系为 i=j+1,此时此时k=3(i-1)+2主对角线上的元素的下标关系为主对角线上的元素的下标关系为 i=j,此时此时k=3(i-1)+3主对角线下的元素的下标关系为主对角线下的元素的下标关系为 i=j1,此时此时k=3(i-1)+4即：即：k=2i+j第20页，此课件共57页哦 例例5.2 按按行行优优先先顺顺序序和和按按列列优优先先顺顺序序列列出出四四维维数数组组A2222所有元素在内存中的存储次序。所有元素在内存中的存储次序。第21页，此课件共57页哦 解：解：按行优先的存储次序按行优先的存储次序:A0

17、000,A0001,A0010,A0011,A0100,A0101,A0110,A0111,A1000,A1001,A1010,A1011,A1100,A1101,A1110,A1111第22页，此课件共57页哦 按列优先的存储次序按列优先的存储次序:A0000,A1000,A0100,A1100,A0010,A1010,A0110,A1110,A0001,A1001,A0101,A1101,A0011,A1011,A0111,A1111第23页，此课件共57页哦5.2 5.2 稀疏矩阵稀疏矩阵 一一个个阶阶数数较较大大的的矩矩阵阵中中的的非非零零元元素素个个数数s相相对对于于矩矩阵阵元元素素

18、的的总总个个数数t十十分分小小时时，即即st时时,称称该该矩矩阵阵为为稀稀疏疏矩矩阵阵。例例如如一一个个100100的的矩矩阵阵,若若其其中中只只有有100个个非非零零元素元素,就可称其为就可称其为稀疏矩阵稀疏矩阵。第24页，此课件共57页哦5.2.1 5.2.1 稀疏矩阵的三元组表示稀疏矩阵的三元组表示 稀疏矩阵的压缩存储方法是稀疏矩阵的压缩存储方法是只存储非零元素只存储非零元素。由由于于稀稀疏疏矩矩阵阵中中非非零零元元素素的的分分布布没没有有任任何何规规律律,所所以以在在存存储储非非零零元元素素时时还还必必须须同同时时存存储储该该非非零零元元素素所所对对应应的的行行下下标标和和列列下下标标

19、。这这样样稀稀疏疏矩矩阵阵中中的的每每一一个个非非零零元元素素需需由由一一个个三三元元组组(i,j,ai,j)惟惟一一确确定定,稀稀疏疏矩矩阵阵中中的的所所有有非非零零元元素素构成三元组线性表。构成三元组线性表。第25页，此课件共57页哦 假假设设有有一一个个67阶阶稀稀疏疏矩矩阵阵M(为为图图示示方方便便,我我们们所所取取的的行行列列数数都都很很小小),M中中元元素素如如下下图图所所示示。则则对对应应的的三元组线性表为：三元组线性表为：(0,1,12）,(0,2,9),(2,0,-3),(2,5,14),(3,2,24),(4,1,18),(5,0,16),(5,3,-7)第26页，此课件共

20、57页哦 若若把把稀稀疏疏矩矩阵阵的的三三元元组组线线性性表表按按顺顺序序存存储储结结构构存存储储,则则称称为为稀稀疏疏矩矩阵阵的的三三元元组组顺顺序序表表。则则三三元元组组顺顺序序表表的的数数据据结结构构可可定定义如下：义如下：第27页，此课件共57页哦#define MaxSize 100 /矩阵中非零元素最多个数矩阵中非零元素最多个数 typedef struct int i;/行号行号 int j;/列号列号 ElemType e;/元素值元素值 Triple;/三元组定义三元组定义 typedef struct int mu;/行数值行数值 int nu;/列数值列数值 int tu

21、;/非零元素个数非零元素个数 Triple dataMaxSize+1;TSMatrix;/三元组顺序表定义三元组顺序表定义 第28页，此课件共57页哦i j e 1 2 12 1 3 9 3 1 -3 36 14 43 24 55 2 18 61 15 74 -7M.dataM.mu=6M.nu=7M.tu=8第29页，此课件共57页哦用常规的二维数组表示时的算法用常规的二维数组表示时的算法 其时间复杂度为其时间复杂度为:O(M.muM.nu):O(M.muM.nu)for(col=1;col=M.nu;+col)for(row=1;row=M.mu;+row)Tcolrow=Mrowcol

22、;（1）用三元组表示时矩阵转置运算的实现用三元组表示时矩阵转置运算的实现用三元组表示时如何实现？用三元组表示时如何实现？第30页，此课件共57页哦方法方法1：i j e 1 2 12 1 3 9 3 1 -3 36 14 43 24 55 2 18 61 15 76 4 -7M.dataM.mu=6M.nu=7M.tu=8转置后转置后得得Ti j v 1 3 -31 6 15 2 1 12 2 5 18 3 1 9 34 24 46 -7 6 3 14T.dataT.mu=7T.nu=6T.tu=8第31页，此课件共57页哦Status TransposeSMattrix(TSMatrix M

23、,TSMatrix&T)/采用三元组表存储表示，求稀疏矩阵的转置矩阵采用三元组表存储表示，求稀疏矩阵的转置矩阵TT.mu=M.nu;T.nu=M.mu;T.tu=M.tu;if(T.tu)q=1;/q表示下一次找到的非零元在表示下一次找到的非零元在T.data中的下标中的下标for(col=1;col=M.nu;col+)for(p=1;p=M.tu;p+)if(M.datap.j=col)T.dataq.i=M.datap.j;T.dataq.j=M.datap.i;T.dataq.e=M.datap.e;+q;return OK;/TransposeSMattrix其时间复杂度为其时间复杂

24、度为:O(M.nuM.tu)，若若 M.tu 与与M.mu M.nu同数同数量级量级 时，有时，有O(M.mu M.nu2)第32页，此课件共57页哦方法二：快速转置方法二：快速转置 其基本思想是对其基本思想是对M.dataM.data仅扫描一遍，在扫描到每一个元仅扫描一遍，在扫描到每一个元素时将其放在素时将其放在T.dataT.data的的合适合适的位置上。的位置上。cpot1=1;cpotcol=cpotcol-1+numcol-1;(2 col M.nu)1357889colnumcolcpotcol12223241506170第33页，此课件共57页哦方法方法2（快速转置）：（快速转置

25、）：i j e 1 2 12 1 3 9 3 1 -3 36 14 43 24 55 2 18 61 15 76 4 -7M.dataM.mu=6M.nu=7M.tu=8转置后转置后得得TT.mu=7T.nu=6T.tu=8T.datai j v2 1 12 3 1 91 3 -36 3 14 3 4 242 5 181 6 154 6 -7123456781357889colnumcolcpotcol1222324150617046297538第34页，此课件共57页哦1）根据）根据M的的mu、nu和和tu 的值，对的值，对T的的mu、nu和和tu赋赋 相相应的值；应的值；2）初始化数组）初

26、始化数组num;3）扫描扫描M.data，计算计算num的值；的值；4）根据）根据num的值，计算的值，计算cpot的值；的值；5）扫描）扫描M.data一遍，将非零元放在一遍，将非零元放在T.data的合适的合适 的位置上。的位置上。算法描述如下页所示：算法描述如下页所示：第35页，此课件共57页哦Status FastTransposeSMatrix(TSMatrix M,TSMatrix&T)/采用三元组表存储表示，求稀疏矩阵的转置矩阵采用三元组表存储表示，求稀疏矩阵的转置矩阵TT.mu=M.nu;T.nu=M.mu;T.tu=M.tu;if(T.tu)for(col=1;col=M.n

27、u;col+)numcol=0;for(t=1;col=M.tu;t+)+numM.datat.j;cpot1=1;/求第求第col列中第一个非零元在列中第一个非零元在T.data中的序号中的序号 for(col=2;col=M.nu;col+)cpotcol=cpotcol-1+numcol-1;for(t=1;t=M.tu;t+)col=M.datat.j;q=cpotcol;T.dataq.i=M.datat.j;T.dataq.j=M.datat.i;T.dataq.e=M.datat.e;+cpotcol;return OK;/FastTransposeSMatrix 时间复杂度为：

28、时间复杂度为：第36页，此课件共57页哦分析算法分析算法FastTransposeSMatrixFastTransposeSMatrix的时间复杂度的时间复杂度：时间复杂度为时间复杂度为:O(M.nu+M.tu)for(col=1;col=M.nu;+col)for(t=1;t=M.tu;+t)for(col=2;col=M.nu;+col)for(p=1;p=M.tu;+p)第37页，此课件共57页哦 三元组顺序表又称三元组顺序表又称有序的双下标法有序的双下标法，它的特点是，非，它的特点是，非零元在表中按行序有序存储，因此零元在表中按行序有序存储，因此便于进行依行顺序处理便于进行依行顺序处理

29、的矩阵运算的矩阵运算。然而，若需随机存取某一行中的非零元，则。然而，若需随机存取某一行中的非零元，则需从头开始进行查找。需从头开始进行查找。2.行逻辑链接的顺序表行逻辑链接的顺序表typedef struct Triple dataMAXSIZE+1;/非零元三元组表非零元三元组表 int rposMAXRC+1;/各行第一个非零元的位置表各行第一个非零元的位置表 int mu,nu,tu;RLSMatrix;/行逻辑链接顺序表类型行逻辑链接顺序表类型在在行逻辑链接的顺序表表示稀疏矩阵时，一些操作的实现。行逻辑链接的顺序表表示稀疏矩阵时，一些操作的实现。第38页，此课件共57页哦（1）取值运算

30、，给定一组下标，求矩阵的元素值）取值运算，给定一组下标，求矩阵的元素值void value(RLSMatrix M,int r,int c,ElemType&e)p=M.rposr;/第第r r行第一个非零元的位置行第一个非零元的位置 q=;/第第r r行最后一个非零元的位置行最后一个非零元的位置 while(p=q&M.datap.j q)e=0;return;if(M.datap.j=c)e=M.datap.e;else e=0;/value/value第39页，此课件共57页哦for(i=1;i=m1;+i)for(j=1;j=n2;+j)Qij=0;for(k=1;k=n1;+k)Qi

31、j+=Mik*Nkj;其时间复杂度为其时间复杂度为:O(m1n2n1)(2)矩阵乘法运算矩阵乘法运算:2.1 精典乘法运算算法：精典乘法运算算法：第40页，此课件共57页哦M=0 2102-2 430 03 0 0 5 40 -1 0 052 0 0 0N=3 44 2Q=M N0 6 -1 0 0 4Q=3 21 0 0 0 1 0 0 01 0 0 0A=B=1 10 00 00 03 44 2C=A B1 1 1 1 1 1C=3 2第41页，此课件共57页哦M、N和和Q的三元组表示分别如下：的三元组表示分别如下：i j e1 1 321 4 52 2 -133 1 2i j e1 2

32、222 1 13 1 -23 2 4i j e1 2 622 1 -13 2 4M.dataN.dataQ.dataQij=第42页，此课件共57页哦 Q Q初始化初始化;if Q if Q是非零矩阵是非零矩阵 /逐行求积逐行求积 for(arow=1;arow=M.mu;+arow)for(arow=1;arow=M.mu;+arow)/处理处理M M的每一行的每一行 ctemp=0;ctemp=0;/累加器清零累加器清零 计算计算Q Q中第中第arowarow行的积并存入行的积并存入ctemp ctemp 中；中；将将ctemp ctemp 中非零元压缩存储到中非零元压缩存储到Q.data

33、Q.data；/for arow/for arow /if/if 基本思想：基本思想：第43页，此课件共57页哦Status MultSMatrix (RLSMatrix M,RLSMatrix N,RLSMatrix&Q)/求矩阵乘积求矩阵乘积Q=M N,采用行逻辑链接存储表示采用行逻辑链接存储表示 if(M.nu!=N.mu)return ERROR;Q.mu=M.mu;Q.nu=N.nu;Q.tu=0;/初始化初始化Q，Q.tu表示现已存入表示现已存入Q中的非零元个数中的非零元个数 if(M.tu*N.tu!=0)/Q是非零矩阵是非零矩阵 for(arow=1;arow=M.mu;+ar

34、ow)处理处理M的每一行的每一行 /for arow /if return OK;/MultSMatrix 第44页，此课件共57页哦 ctemp =0;/当前行各元素累加器清零当前行各元素累加器清零 Q.rposarow=Q.tu+1;/Q的第的第arow行在行在Q.data中的位置中的位置 if(arow M.mu)tp=M.rposarow+1;else tp=M.tu+1 for(p=M.rposarow;ptp;+p)/对当前行中每一个非零元给它该乘的元素乘一遍对当前行中每一个非零元给它该乘的元素乘一遍 brow=M.datap.j;if(brow N.mu)t=N.rposbrow

35、+1;else t=N.tu+1 /t为本行最后一个非零元的下一位为本行最后一个非零元的下一位 for(q=N.rposbrow;q t;+q)ccol=N.dataq.j;/乘积元素在乘积元素在Q中列号中列号 ctempccol+=M.datap.e*N.dataq.e;/for q 处处理理 的的每每一一行行M第45页，此课件共57页哦/求得求得Q中第中第crow(=arow)行的非零元行的非零元for(ccol=1;ccol MAXSIZE)return ERROR;Q.dataQ.tu=（arow,ccol,ctempccol）;/if第46页，此课件共57页哦分析上述算法的时间复杂度

36、分析上述算法的时间复杂度累加器累加器ctempctemp初始化初始化的时间复杂度为的时间复杂度为(M.mu(M.mu N.nu)N.nu)，求求Q Q的所有非零元的所有非零元的时间复杂度为的时间复杂度为(M.tu(M.tu N.tu/N.mu)N.tu/N.mu)，进行进行压缩存储压缩存储的时间复杂度为的时间复杂度为(M.mu(M.mu N.nu)N.nu)，总的时间复杂度就是总的时间复杂度就是(M.mu(M.mu N.nu+M.tuN.nu+M.tu N.tu/N.mu)N.tu/N.mu)。若若M M是是m m行行n n列的稀疏矩阵，列的稀疏矩阵，N N是是n n行行p p列的稀疏矩阵，列

37、的稀疏矩阵，则则M M中非零元的个数中非零元的个数 M.tu=M.tu=M M m m n n，N N中非零元的个数中非零元的个数 N.tu=N.tu=N N n n p p，相乘算法的时间复杂度就是相乘算法的时间复杂度就是 (m(m p p(1+n(1+n M M N N)，当当 M M0.05 0.05 和和 N N0.050.05及及 n 1000n i=i;p-j=j;p-e=e;/生成结点生成结点if(M.rheadi=NULL|M.rheadi-jj)/插在表头插在表头p-right=M.rheadi;M.rheadi=p;else /将将p插在合适的位置上插在合适的位置上for(

38、q=M.rheadi;q-right&q-right-jright);p-right=q-right;q-right=p;/行插入，在行插入，在q后后if(M.cheadj=NULL|M.cheadj-ii)/插在表头插在表头 p-down=M.cheadj;M.rheadj=p;else/将将p插在合适的位置上插在合适的位置上 第53页，此课件共57页哦for(q=M.cheadj;q-down&q-down-idown);p-down=q-down;q-down=p;/列插入，在列插入，在q后后return OK;/CreatMatrix_OL第54页，此课件共57页哦3.2 十字链表存储

39、时两矩阵相加运算算法十字链表存储时两矩阵相加运算算法void addMatrix(CrossList&A,CrossList B)/A=A+B for(row=1;rowjpb-j:产生一个结点产生一个结点p；p所指结点所指结点 的值的值=pb所指结点的值；将所指结点的值；将p 插在插在pa的前面（的前面（pre的后面）的后面）完成行插入；将完成行插入；将p插在相应列插在相应列 的适当位置上的适当位置上,pb后移后移,pre=p;break;case pa-jj:pre=pa;pa=pa-right;break;case pa-j=pb-j:k=pa-e+pb-e;第55页，此课件共57页哦 if(k)pa-e=k;pre=pa;pa=pa-right;pb=pb-right;else 在相应的行、列中，删除在相应的行、列中，删除pa所指结点；所指结点；pa、pb后后 移；移；break;/switch /while/for/addMatrix 第56页，此课件共57页哦感感谢谢大大家家观观看看第57页，此课件共57页哦