数组和稀疏矩阵精选课件.ppt

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

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

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

3、下公式求出：就可由以下公式求出：LOC(ai)=LOC(a0)+i*k(0in-1)上上式式说说明明,一一维维数数组组中中任任一一数数据据元元素素的的存存储储地地址址可可直直接接计计算算得得到到,即即一一维维数数组组中中任任一一数数据据元元素素可可直直接接存存取取。因因此此,一一维维数数组组是是一一种种随随机机存存储储结结构构。同同样样,二二维维及及多多维维数数组组也也满满足随机存储特性。足随机存储特性。第四页，本课件共有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)。第五页，本课件共有57页 显显然然,二二维维数数组组同同样样满满足足数数组组的的定定义义。一一个个二二维维数数组组可可以以看看作作是是每每个个数数据据元元素素都都是是相相同同类类型型的的一一维维数数组组的的一一维维数数组组。以以此此类类推推,任任何何多多维维数数组组都都可可以以看看作作一一个个线线性性表表，这这时时线线性性表表中中的的每每个个数数据据元元素素也也是是一一个个线线性性表表。多维数组是线性表的推广。多维数组是线性表的推广。第六页，本课件共有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第七页，本课件共有57页 对对一一个个已已知知以以行行序序为为主主序序的的计计算算机机系系统统中中,当当二二维维数数组组第第一

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

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

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

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

10、元素，例如：的元素，例如：第十三页，本课件共有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之间找一个对应关之间找一个对应关系。系。第十四页，本课件共有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)/2+j

12、1 i*(i-1)/2+j1 当当i=ji=jj*(j-1)/2+i-1 j*(j-1)/2+i-1 当当ijijk=第十五页，本课件共有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)下三角矩阵下三角矩阵第十六页，本课件共有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=第十七页，本课件共有57页 3.对角矩阵的压缩存储对角矩阵的压缩存储 若若一一个个n阶阶方方阵阵A满满足足其其所所有有非非零零元元素素都都集集中中在在以以主主对对角角线线为为中中心心的的带带状状区区域域中中，则则称称其其为为n阶阶对对角角矩矩阵阵，其其主主对对角角线线上上下下方方各各有有b条条次次对对角角线线,称称b为为矩矩阵阵半半带带宽宽，(2b+1)为

15、为矩矩阵阵的的带带宽宽。对对于于半半带带宽宽为为b(0b(n-1)/2)的的对对角角矩矩阵阵，其其|i-j|b的的元元素素ai,j不不为为零零,其其余余元元素素为为零零。下图所示是半带宽为下图所示是半带宽为b的对角矩阵示意图。的对角矩阵示意图。第十八页，本课件共有57页 半带宽为半带宽为b b的对角矩阵的对角矩阵 第十九页，本课件共有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第二十页，本课件共有57页 例例5.2 按按行行优优先先顺顺序序和和按按列列优优先先顺顺序序列列出出四四维维数组数组A2222所有元素在内存中的存储次序。所有元素在内存中的存储次序。第二十一页，本课件共有57页 解：解：按行优先的存储次序按行优先的存储次序:A000

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

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

19、标。这这样样稀稀疏疏矩矩阵阵中中的的每每一一个个非非零零元元素素需需由由一一个个三三元元组组(i,j,ai,j)惟惟一一确确定定,稀稀疏疏矩矩阵阵中的所有非零元素构成三元组线性表。中的所有非零元素构成三元组线性表。第二十五页，本课件共有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)第二十六页，本

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

21、t tu;/非零元素个数非零元素个数 Triple dataMaxSize+1;TSMatrix;/三元组顺序表定义三元组顺序表定义 第二十八页，本课件共有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第二十九页，本课件共有57页用常规的二维数组表示时的算法用常规的二维数组表示时的算法 其时间复杂度为其时间复杂度为:O(M.muM.nu):O(M.muM.nu)for(col=1;col=M.nu;+col)for(row=1;row=M.mu;+row)Tcolrow=M

22、rowcol;（1）用三元组表示时矩阵转置运算的实现用三元组表示时矩阵转置运算的实现用三元组表示时如何实现？用三元组表示时如何实现？第三十页，本课件共有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第三十一页，本课件共有57页Status TransposeSMattrix(TSM

23、atrix M,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)第三十二页，本课件共有57页方法二：快速转置方法二：快速转置 其基本思想是对其基本思想是对M.dataM.data仅扫描一遍，在扫描到每一仅扫描一遍，在扫描到每一个元素时将其放在个元素时将其放在T.dataT.data的的合适合适的位置上。的位置上。cpot1=1;cpotcol=cpotcol-1+numcol-1;(2 col M.nu)1357889colnumcolcpotcol12223241506170第三十三页，本课件共有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第三十四页，本课件共有57页1）根据）根据M的的mu、nu和和tu 的值，对的值，对T的的mu、nu和和tu赋赋 相相应的值；应的值

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

27、l=1;col=M.nu;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;/FastTransposeSMat

28、rix 时间复杂度为：时间复杂度为：第三十六页，本课件共有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)第三十七页，本课件共有57页 三元组顺序表又称三元组顺序表又称有序的双下标法有序的双下标法，它的特点是，它的特点是，非零元在表中按行序有序存储，因此非零元在表中按行序有序存储，因此便于进行依行顺便

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

30、件共有57页（1）取值运算，给定一组下标，求矩阵的元素值）取值运算，给定一组下标，求矩阵的元素值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第三十九页，本课件共有57页for(i=1;i=m1;+i)for(j=1;j=n2;+j)Qij=0;for(

31、k=1;k=n1;+k)Qij+=Mik*Nkj;其时间复杂度为其时间复杂度为:O(m1n2n1)(2)矩阵乘法运算矩阵乘法运算:2.1 精典乘法运算算法：精典乘法运算算法：第四十页，本课件共有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第四十一页，本课件共有57页M、N和和Q的三元组表示分别如下：的三元组表示分别如下：i j e1 1 321 4 52 2 -1

32、33 1 2i j e1 2 222 1 13 1 -23 2 4i j e1 2 622 1 -13 2 4M.dataN.dataQ.dataQij=第四十二页，本课件共有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 中非零元压缩存储

33、到中非零元压缩存储到Q.dataQ.data；/for arow/for arow /if/if 基本思想：基本思想：第四十三页，本课件共有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(aro

34、w=1;arow=M.mu;+arow)处理处理M的每一行的每一行 /for arow /if return OK;/MultSMatrix 第四十四页，本课件共有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

35、 N.mu)t=N.rposbrow+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第四十五页，本课件共有57页/求得求得Q中第中第crow(=arow)行的非零元行的非零元for(ccol=1;ccol MAXSIZE)return ERROR;Q.dataQ.tu=（arow,ccol,ctempccol）;/if第四十六页，

36、本课件共有57页分析上述算法的时间复杂度分析上述算法的时间复杂度累加器累加器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

37、 N是是n n行行p p列的稀疏矩阵，列的稀疏矩阵，则则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

38、插在合适的位置上插在合适的位置上for(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插在合适的位置上插在合适的位置上 第五十三页，本课件共有57页for(q=M.cheadj;q-down&q-down-idown);p-down=q-down;q-down=p;/列插入，在列插入，在q后后return OK;/CreatMatrix_OL第五

39、十四页，本课件共有57页3.2 十字链表存储时两矩阵相加运算算法十字链表存储时两矩阵相加运算算法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;第五十五页，本课件共有57页 if(k)pa-e=k;pre=pa;pa=pa-right;pb=pb-right;else 在相应的行、列中，删除在相应的行、列中，删除pa所指结点；所指结点；pa、pb后后 移；移；break;/switch /while/for/addMatrix 第五十六页，本课件共有57页感谢大家观看第五十七页，本课件共有57页