《数组和稀疏矩阵精选PPT.ppt》由会员分享，可在线阅读，更多相关《数组和稀疏矩阵精选PPT.ppt（57页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
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的的存存储储
3、地址地址LOC(ai)就可由以下公式求出：就可由以下公式求出：LOC(ai)=LOC(a0)+i*k(0in-1)上上式式说说明明,一一维维数数组组中中任任一一数数据据元元素素的的存存储储地地址址可可直直接接计计算算得得到到,即即一一维维数数组组中中任任一一数数据据元元素素可可直直接接存存取取。因因此此,一一维维数数组组是是一一种种随随机机存存储储结结构构。同同样样,二二维维及及多多维维数数组组也也满满足足随机存储特性。随机存储特性。第4页，讲稿共57张，创作于星期二对于一个对于一个m m行行n n列的二维数组列的二维数组A Amnmn,有：有：将将Am*n简记为简记为A,A是这样的一维数组：
4、是这样的一维数组：A=(a0,a1,ai,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为行数为
7、行数。第9页，讲稿共57张，创作于星期二 例例5.1 对二维数组对二维数组float a54计算：计算：(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
8、)*4=2056第11页，讲稿共57张，创作于星期二5.1.3 特殊矩阵的压缩存储特殊矩阵的压缩存储 特特殊殊矩矩阵阵是是指指非非零零元元素素或或零零元元素素的的分分布布有有一一定定规规律律的的矩矩阵阵，为为了了节节省省存存储储空空间间,特特别别是是在在高高阶阶矩矩阵阵的的情情况况下下，可可以以利利用用特特殊殊矩矩阵阵的的规规律律,对对它它们们进进行行压压缩缩存存储储，也也就就是是说说，使使多多个个相相同同的的非非零零元元素素共共享享同同一一个个存存储储单单元元，对对零零元元素素不不分分配配存存储储空空间。间。特特殊殊矩矩阵阵的的主主要要形形式式有有对对称称矩矩阵阵、对对角角矩矩阵阵等等，它它
9、们们都是方阵，即行数和列数相同。都是方阵，即行数和列数相同。第12页，讲稿共57张，创作于星期二 1.对称矩阵的压缩存储对称矩阵的压缩存储 若若一一个个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 因此，我们可以按从上到下、从左到右将这些元素存放因此，我们可以按从上到下、从左到右
11、将这些元素存放在一个向量在一个向量b0.n(n+1)/2-1b0.n(n+1)/2-1中。为了便于访问对称矩阵中。为了便于访问对称矩阵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,ai
12、3i3,a,aij-1ij-1），因此有：），因此有：a11 a21 a22 a31 an1 annk=0 1 2 3-1i*(i-1)/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。下三角矩阵正好相反，它的主
13、对。下三角矩阵正好相反，它的主对角线上方均为常数角线上方均为常数c c，如图，如图b b所示。在大多数情况下，所示。在大多数情况下，三角矩阵三角矩阵常数为零常数为零。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个，因此，三角矩
14、阵可压缩存储到个，因此，三角矩阵可压缩存储到b0.n(n+1)/2b0.n(n+1)/2中，其中中，其中c c存放在最后一个分量中。存放在最后一个分量中。上三角矩阵中，主对角线之上的第上三角矩阵中，主对角线之上的第i i行行(0in)(0ijijk=下三角矩阵的存储和对称矩阵类似，下三角矩阵的存储和对称矩阵类似，bk和和aij对应关系是：对应关系是：i(i+1)/2+j ij n(n+1)/2 ijk=第17页，讲稿共57张，创作于星期二 3.对角矩阵的压缩存储对角矩阵的压缩存储 若若一一个个n阶阶方方阵阵A满满足足其其所所有有非非零零元元素素都都集集中中在在以以主主对对角角线线为为中中心心的
15、的带带状状区区域域中中，则则称称其其为为n阶阶对对角角矩矩阵阵，其其主主对对角角线线上上下下方方各各有有b条条次次对对角角线线,称称b为为矩矩阵阵半半带带宽宽，(2b+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
16、 .可用以行序为主序的可用以行序为主序的 an-2 n-3 an-2 n-2 an-2 n-1 an-1 n-2 an-1 n-1 形式存储形式存储b3n-2中中 当当b1时称为三对角矩阵，如：时称为三对角矩阵，如：主对角线下方的元素的下标关系为主对角线下方的元素的下标关系为 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 按按行行优优先先顺顺序
17、序和和按按列列优优先先顺顺序序列列出出四四维维数数组组A2222所有元素在内存中的存储次序。所有元素在内存中的存储次序。第21页，讲稿共57张，创作于星期二 解：解：按行优先的存储次序按行优先的存储次序:A0000,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
18、,A1101,A0011,A1011,A0111,A1111第23页，讲稿共57张，创作于星期二5.2 5.2 稀疏矩阵稀疏矩阵 一一个个阶阶数数较较大大的的矩矩阵阵中中的的非非零零元元素素个个数数s相相对对于于矩矩阵阵元元素素的的总总个个数数t十十分分小小时时，即即st时时,称称该该矩矩阵阵为为稀稀疏疏矩矩阵阵。例例如如一一个个100100的的矩矩阵阵,若若其其中中只只有有100个个非非零零元元素素,就可称其为就可称其为稀疏矩阵稀疏矩阵。第24页，讲稿共57张，创作于星期二5.2.1 5.2.1 稀疏矩阵的三元组表示稀疏矩阵的三元组表示 稀疏矩阵的压缩存储方法是稀疏矩阵的压缩存储方法是只存储
19、非零元素只存储非零元素。由由于于稀稀疏疏矩矩阵阵中中非非零零元元素素的的分分布布没没有有任任何何规规律律,所所以以在在存存储储非非零零元元素素时时还还必必须须同同时时存存储储该该非非零零元元素素所所对对应应的的行行下下标标和和列列下下标标。这这样样稀稀疏疏矩矩阵阵中中的的每每一一个个非非零零元元素素需需由由一一个个三三元元组组(i,j,ai,j)惟惟一一确确定定,稀稀疏疏矩矩阵阵中中的的所所有有非非零零元素构成三元组线性表。元素构成三元组线性表。第25页，讲稿共57张，创作于星期二 假假设设有有一一个个67阶阶稀稀疏疏矩矩阵阵M(为为图图示示方方便便,我我们们所所取取的的行行列列数数都都很很小
20、小),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页，讲稿共57张，创作于星期二 若若把把稀稀疏疏矩矩阵阵的的三三元元组组线线性性表表按按顺顺序序存存储储结结构构存存储储,则则称称为为稀稀疏疏矩矩阵阵的的三三元元组组顺顺序序表表。则则三三元元组组顺顺序序表表的的数数据结构可定义如下：据结构可定义如下：第27页，讲稿共57张，创作于星期二#define MaxSize 100 /矩阵中非零元素最多个数矩阵中非零元
21、素最多个数 typedef struct int i;/行号行号 int j;/列号列号 ElemType e;/元素值元素值 Triple;/三元组定义三元组定义 typedef struct int mu;/行数值行数值 int nu;/列数值列数值 int tu;/非零元素个数非零元素个数 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页
22、，讲稿共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;（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
23、.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,TSMatrix&T)/采用三元组表存储表示，求稀疏矩阵的转置矩阵采用三元组表存储表示，求稀疏矩阵的转置矩阵TT.mu=M.nu;T.nu=M.mu;T.tu=M.tu;if(T.tu)q=1;/q表示下一次找到的非零元在表示下一次找到的非零元在T.data中的下标中的下标for(col=
24、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其时间复杂度为其时间复杂度为:O(M.nuM.tu)，若若 M.tu 与与M.mu M.nu同同数量级数量级 时，有时，有O(M.mu M.nu2)第32页，讲稿共57张，创作于星期二方法二：快速转置方法二：快速转置 其基本思想是对其基本思想是对M.dataM.data仅扫描一遍，在扫描到每一个元仅扫描一遍，在扫描
25、到每一个元素时将其放在素时将其放在T.dataT.data的的合适合适的位置上。的位置上。cpot1=1;cpotcol=cpotcol-1+numcol-1;(2 col M.nu)1357889colnumcolcpotcol12223241506170第33页，讲稿共57张，创作于星期二方法方法2（快速转置）：（快速转置）：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
26、 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）初始化数组）初始化数组num;3）扫描扫描M.data，计算计算num的值；的值；4）根据）根据num的值，计算的值，计算cpot的值；的值；5）扫描）扫描M.data一遍，将非零元放在一遍，将非零元放在T.data的合适的合适 的位置上。的位置上。算法描述如下页所示：算法描
27、述如下页所示：第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.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+)cpo
28、tcol=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 时间复杂度为：时间复杂度为：第36页，讲稿共57张，创作于星期二分析算法分析算法FastTransposeSMatrixFastTransposeSMatrix的时间复杂度的时间复杂度：时间复杂度为时间复杂度为:O(M.nu+M.tu)for(col=1;col=M
29、.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张，创作于星期二 三元组顺序表又称三元组顺序表又称有序的双下标法有序的双下标法，它的特点是，非，它的特点是，非零元在表中按行序有序存储，因此零元在表中按行序有序存储，因此便于进行依行顺序处便于进行依行顺序处理的矩阵运算理的矩阵运算。然而，若需随机存取某一行中的非零元，。然而，若需随机存取某一行中的非零元，则需从头开始进行查找。则需从头开始进行查找。2.行逻辑链接的顺序表行逻辑链接的顺序表typedef struct Triple data
30、MAXSIZE+1;/非零元三元组表非零元三元组表 int rposMAXRC+1;/各行第一个非零元的位置表各行第一个非零元的位置表 int mu,nu,tu;RLSMatrix;/行逻辑链接顺序表类型行逻辑链接顺序表类型在在行逻辑链接的顺序表表示稀疏矩阵时，一些操作的实现。行逻辑链接的顺序表表示稀疏矩阵时，一些操作的实现。第38页，讲稿共57张，创作于星期二（1）取值运算，给定一组下标，求矩阵的元素值）取值运算，给定一组下标，求矩阵的元素值void value(RLSMatrix M,int r,int c,ElemType&e)p=M.rposr;/第第r r行第一个非零元的位置行第一个
31、非零元的位置 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)Qij+=Mik*Nkj;其时间复杂度为其时间复杂度为:O(m1n2n1)(2)矩阵乘法运算矩阵乘法运算:2.1 精典乘法运算算法：精典乘法运算算法：第40页，讲稿共57张，创作于星期二M=0 2102-2 430
32、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 222 1 13 1 -23 2 4i j e1 2 622 1 -13 2 4M.dataN.dataQ.dataQij=第42页，讲稿共57张，创作于星期二 Q Q初始化初始化;if Q
33、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.dataQ.data；/for arow/for arow /if/if 基本思想：基本思想：第43页，讲稿共57张，创作于星期二Status MultSMatrix (RLSMatrix
34、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;+arow)处理处理M的每一行的每一行 /for arow /if return OK;/MultSMatrix 第44页，讲稿共57张，创作于星期二 ctemp =0;/当前行
35、各元素累加器清零当前行各元素累加器清零 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+1;else t=N.tu+1 /t为本行最后一个非零元的下一位为本行最后一个非零元的下一位 for(q=N.rposbrow;q t;+q)ccol=N.da
36、taq.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张，创作于星期二分析上述算法的时间复杂度分析上述算法的时间复杂度累加器累加器ctempctemp初始化初始化的时间复杂度为的时间复杂度为(M.mu(M.mu N.nu)N.nu)，求
37、求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列的稀疏矩阵，列的稀疏矩阵，则则M M中非零元的个数中非零元的个数 M.tu=M.tu=M M m m n n，N N中非零元的个数中非零元的个数 N.tu=
38、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(q=M.rheadi;q-right&q-right-jright);p-right=q-right;q-right=p;/行插入，在行插入，
39、在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 十字链表存储时两矩阵相加运算算法十字链表存储时两矩阵相加运算算法void addMatrix(CrossList&A,CrossLis
40、t 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张，创作于星期二