1、数据结构数据结构1 1数据结构数据结构第第5 5章章 数组和广义表数组和广义表n什么是数组和广义表？什么是数组和广义表？n数组和广义表的存储结构数组和广义表的存储结构数据结构数据结构2 2n数组和广义表可看成是一种特殊的线性表，其数组和广义表可看成是一种特殊的线性表，其特殊在于，表中的数据元素本身也是一种线性特殊在于，表中的数据元素本身也是一种线性表。表。数据结构数据结构3 3数组数组n数组：是所有高级编程语言中都已实现的固有数据类型。但它和数组：是所有高级编程语言中都已实现的固有数据类型。但它和其它诸如整数、实数等原子类型不同，它是一种结构类型。换句其它诸如整数、实数等原子类型不同，它是一种
2、结构类型。换句话说，话说，数组数组 是一种数据结构。是一种数据结构。n一维数组一维数组An1An1：定长的线性表：定长的线性表n二维数组二维数组An1n2An1n2：每个数据元素也是一个定长的线性表的线性：每个数据元素也是一个定长的线性表的线性表。表。可以将二维数组可以将二维数组A A看成是由看成是由m m个行向量个行向量XX0 0，X X1 1，X Xm-1m-1 T T组成，其中，组成，其中，X Xi i=(a=(ai0i0,a,ai1i1,.,a.,ain-1in-1)，0im-10im-1；也可以将二维数组；也可以将二维数组A A看成是由看成是由n n个列向量个列向量yy0 0,y,y
3、1 1,y,yn-1n-1 组成，其中组成，其中 y yi i=(a=(a0i0i,a,a1i1i,.,a.,am-1im-1i)，0in-10in-1。a00 a01 a0n-1 a10 a11 a1n-1 .A=am-1 0 am-1 1 am-1 n-1 数据结构数据结构4 4数组的抽象数据类型定义数组的抽象数据类型定义ADT ArrayADT Array数据对象数据对象:D=a:D=aj1j2.jnj1j2.jn|n=0|n=0称为数组的维数称为数组的维数,ji,ji是数组元素的第是数组元素的第i i维下标维下标值，值，a aj1j2.jnj1j2.jn(-ElemSet(-ElemS
4、et 数据关系数据关系:R=R1,R2,.Rn Ri=aj1.ji.jn,aj1.ji+1.jn:R=R1,R2,.Rn Ri=|0=jk0=jk=b=bk-1k-1,1=k=n,1=k=n且且ki,0=jiki,0=ji=bi-2,=bi-2,a aj1.jij1.ji.jn.jn,a,aj1.ji+1.jnj1.ji+1.jn(-D,i(-D,i=2,.n=2,.n基本操作：基本操作：InitArray(&A,n,bound1,.,boundnInitArray(&A,n,bound1,.,boundn)构造相应的数组构造相应的数组A,A,并返回并返回OK.OK.DestroyArray(
5、&ADestroyArray(&A)销毁数组销毁数组A.A.Value(A,&e,index1,.,indexnValue(A,&e,index1,.,indexn)e)e赋值为所指定的赋值为所指定的A A的元素值的元素值.Assign(&A,e,index1,.,indexnAssign(&A,e,index1,.,indexn)将将e e的值赋给所指定的的值赋给所指定的A A的元素的元素.ADT ArrayADT Array数组一旦被定义，其维数数组一旦被定义，其维数(N)(N)和每一维的上、下界均不能再变，数组中元和每一维的上、下界均不能再变，数组中元素之间的关系也不再改变。因此数组的基
6、本操作除初始化和结构销毁之素之间的关系也不再改变。因此数组的基本操作除初始化和结构销毁之外，只有通过给定的外，只有通过给定的 一组下标一组下标 索引取得元素或修改元素的值。索引取得元素或修改元素的值。数据结构数据结构5 5n从理论上讲，数组结构也可以使用两种存储结构，即顺序从理论上讲，数组结构也可以使用两种存储结构，即顺序存储结构和链式存储结构。然而，由于数组结构没有插入、存储结构和链式存储结构。然而，由于数组结构没有插入、删除元素的操作，删除元素的操作，也就是说，数组一旦建立，结构中的元也就是说，数组一旦建立，结构中的元素个数和元素间的关系就不再发生变化。因此，一般都是素个数和元素间的关系就
7、不再发生变化。因此，一般都是采用顺序存储的方法来表示数组。采用顺序存储的方法来表示数组。n组成数组结构的元素可以是多维的，但存储数据元素的内组成数组结构的元素可以是多维的，但存储数据元素的内存单元地址是一维的，因此，在存储数组结构之前，需要存单元地址是一维的，因此，在存储数组结构之前，需要将多维关系映射到一维关系。将多维关系映射到一维关系。n通常有两种映射方法：即通常有两种映射方法：即 以行以行(序序)为主为主(序序)的映象方法的映象方法和和 以列以列(序序)为主为主(序序)的映象方法。的映象方法。数组的顺序表示和实现数组的顺序表示和实现数据结构数据结构6 6以行以行(序序)为主为主(序序)将
8、数组元素按行排列，第将数组元素按行排列，第i+1i+1个行向量紧接在个行向量紧接在第第i i个行向量后面。个行向量后面。以二维数组为例，以二维数组为例，A A的的m m*n n个元素以行个元素以行(序序)为主为主(序序)存储的线性序存储的线性序列为：列为：a a0000,a,a0101,a,a0n-10n-1,a,a1010,a,a1111,a a1n-11n-1,a,am-10m-10,a,am-11m-11,a,am-1n-1m-1n-1 推广至推广至n维的规律为：最左边下标变化最慢，最右边下标变化最维的规律为：最左边下标变化最慢，最右边下标变化最快，右边下标变化一遍，与之相邻的左边下标才
9、变化一次。因此，快，右边下标变化一遍，与之相邻的左边下标才变化一次。因此，在算法中，最左边下标可以看成是外循环，最右边下标可以看成在算法中，最左边下标可以看成是外循环，最右边下标可以看成是最内循环。是最内循环。在在PASCALPASCAL、C C语言中，数组就是以行语言中，数组就是以行(序序)为主为主(序序)存储的。存储的。以列以列(序序)为主为主(序序)将数组元素按列向量排列，第将数组元素按列向量排列，第j+1j+1个列向量紧个列向量紧接在第接在第j j个列向量之后。个列向量之后。以二维数组为例，以二维数组为例，A A的的m m*n n个元素以列个元素以列(序序)为主为主(序序)存储的线性序
10、存储的线性序列为：列为：a a0000,a,a1010,a,am-10m-10,a,a0101,a,a1111,a am-11m-11,a,a0n-10n-1,a,a1n-11n-1,a,am-1n-1m-1n-1推广至推广至n维的规律为：最右边下标变化最慢，最左边下标变化最维的规律为：最右边下标变化最慢，最左边下标变化最快，左边下标变化一遍，与之相邻的右边下标才变化一次。因此，快，左边下标变化一遍，与之相邻的右边下标才变化一次。因此，在算法中，最右边下标可以看成是外循环，最左边下标可以看成在算法中，最右边下标可以看成是外循环，最左边下标可以看成是最内循环。是最内循环。在在FORT0RANFO
11、RT0RAN语言中，数组就是按列优先顺序存储的。语言中，数组就是按列优先顺序存储的。数据结构数据结构7 7n可见，对于数组，一旦规定了它的维度和各维的长度，可见，对于数组，一旦规定了它的维度和各维的长度，便可为它根据上述方式分配存储空间。便可为它根据上述方式分配存储空间。n反之，只要给出数组中某元素的下标值，就可得出其反之，只要给出数组中某元素的下标值，就可得出其存储位置。存储位置。n假设每个数据元素占假设每个数据元素占L L个存储单元，则二维数组个存储单元，则二维数组A Amnmn中任中任一元素一元素a aijij的存储位置的存储位置在以以行在以以行(序序)为主为主(序序)存储时，可由下式确
12、定：存储时，可由下式确定：LOC(aij)=LOC(a00)+(in+j)L在以以列在以以列(序序)为主为主(序序)存储时，可由下式确定：存储时，可由下式确定：LOC(aij)=LOC(a00)+(jm+i)Ln推广开来，在以以行推广开来，在以以行(序序)为主为主(序序)存储时，存储时，三维数组三维数组A Ab1b2b3b1b2b3中任一元素中任一元素a aj1j2j3j1j2j3的存储位置，可由下式确定：的存储位置，可由下式确定：LOC(aj1j2j3j1j2j3)=LOC(a000)+(j1b2b3+j2b3+j3)LN N维数组维数组A Ab1b2b1b2bnbn中任一元素中任一元素a
13、aj1j2j1j2jnjn的存储位置，可由下式确定：的存储位置，可由下式确定：LOC(aij)=LOC(a000)+(j1b2bn+j2b3bn+jn-1 bn+jn)L数据结构数据结构8 8n矩阵是一个二维数组，它是很多科学与工程计算矩阵是一个二维数组，它是很多科学与工程计算问题中研究的数学对象。问题中研究的数学对象。n矩阵可以用行优先或列优先方法顺序存放到内存矩阵可以用行优先或列优先方法顺序存放到内存中，但是，当矩阵的阶数很大时将会占较多存储中，但是，当矩阵的阶数很大时将会占较多存储单元。而当矩阵中的非零元素分布呈现某种规律单元。而当矩阵中的非零元素分布呈现某种规律时，从节约存储单元的角度
14、出发，可考虑进行压时，从节约存储单元的角度出发，可考虑进行压缩存储。缩存储。n所谓所谓压缩存储压缩存储是指：为多个值相同的元素只分配是指：为多个值相同的元素只分配一个存储空间，而对值为零的元素不分配空间。一个存储空间，而对值为零的元素不分配空间。矩阵的压缩存储矩阵的压缩存储数据结构数据结构9 9特殊矩阵及其存储特殊矩阵及其存储n特殊矩阵就是元素值的排列具有一定规律的矩阵。常见的特殊矩阵有：特殊矩阵就是元素值的排列具有一定规律的矩阵。常见的特殊矩阵有：对称矩阵、下（上）三角矩阵、对角线矩阵等等。对称矩阵、下（上）三角矩阵、对角线矩阵等等。n对称矩阵：在一个对称矩阵：在一个n n阶方阵阶方阵A A
15、中，若元素满足中，若元素满足 a aijij=a=ajiji 0 0i,ji,jn-1n-1则称则称A A为对称矩阵为对称矩阵对称矩阵中的元素关于主对角线对称，故只要存储矩阵中上三角或下三对称矩阵中的元素关于主对角线对称，故只要存储矩阵中上三角或下三角中的元素，让每两个对称的元素共享一个存储空间，这样，能节约近角中的元素，让每两个对称的元素共享一个存储空间，这样，能节约近一半的存储空间。不失一般性，我们按一半的存储空间。不失一般性，我们按“行优先行优先顺序顺序”存储主对角线存储主对角线（包括对角线）以下的元素，其存储形式如图所示：（包括对角线）以下的元素，其存储形式如图所示：142341723
16、2012341275173510数据结构数据结构1010n在这个下三角矩阵中，第在这个下三角矩阵中，第i i行恰有行恰有i+1i+1个元素，元素总数为个元素，元素总数为n(n+1)/2.n(n+1)/2.因此，因此，我们可以按图中自上到下，自左到右的次序将这些元素存放在一个向量我们可以按图中自上到下，自左到右的次序将这些元素存放在一个向量sa0.n(n+1)/2-1sa0.n(n+1)/2-1中。中。n为了便于访问对称矩阵为了便于访问对称矩阵A A中的元素，我们必须在中的元素，我们必须在a aijij和和saksak 之间找一个对应之间找一个对应关系。关系。若若i ij j，则，则a aiji
17、j在下三角形中。在下三角形中。a aijij之前的之前的i i行（从第行（从第0 0行到第行到第i-1i-1行）一共行）一共有有1+2+1+2+i=i(i+1)/2+i=i(i+1)/2个元素，在第个元素，在第i i行上，行上，a aijij之前恰有之前恰有j j个元素，因此个元素，因此有：有：k=ik=i*(i+1)/2+j(i+1)/2+j若若ijij，则，则a aijij是在上三角矩阵中。因为是在上三角矩阵中。因为a aijij=a=ajiji，所以只要交换上述对应，所以只要交换上述对应关系式中的关系式中的i i和和j j即可得到：即可得到：k=jk=j*(j+1)/2+i(j+1)/2
18、+insa0.n(n+1)/2-1sa0.n(n+1)/2-1称为称为n n阶对称矩阵阶对称矩阵A A的压缩存储。的压缩存储。11121110222120111000.nnnnnaaaaaaaaaa数据结构数据结构11 11n三角矩阵：下（上）三角矩阵的特点是以主对角线为界的三角矩阵：下（上）三角矩阵的特点是以主对角线为界的上（下）半部分是一个固定的值上（下）半部分是一个固定的值c c，下（上）半部分的元，下（上）半部分的元素值没有任何规律。素值没有任何规律。n三角矩阵的压缩存储与上述的对称矩阵的压缩存储一样，三角矩阵的压缩存储与上述的对称矩阵的压缩存储一样，只存储其下（上）三角中的元素。除此
19、之外，需再增加一只存储其下（上）三角中的元素。除此之外，需再增加一个存储常数个存储常数c c的存储空间即可。的存储空间即可。20926130301080012600029数据结构数据结构1212n对角矩阵：对角矩阵的特点是对角矩阵：对角矩阵的特点是所有的非零元素都集中在以主对角线为所有的非零元素都集中在以主对角线为中心的带状区域中。中心的带状区域中。即除了主对角线和主对角线相邻两侧的若干条对即除了主对角线和主对角线相邻两侧的若干条对角线上的元素之外，其余元素皆为零。角线上的元素之外，其余元素皆为零。n对角矩阵可按行优先顺序或对角线的顺序，将其压缩存储到一个向量对角矩阵可按行优先顺序或对角线的顺
20、序，将其压缩存储到一个向量中，并且也能找到每个非零元素和向量下标的对应关系。中，并且也能找到每个非零元素和向量下标的对应关系。n以三对角矩阵为例，三对角矩阵除第以三对角矩阵为例，三对角矩阵除第0 0行和第行和第n-1n-1行是行是2 2个元素外，每行个元素外，每行的非零元素都要是的非零元素都要是3 3个，因此，可以用一个包含个，因此，可以用一个包含3n-23n-2个元素的数组个元素的数组sasa存存储三对角矩阵。储三对角矩阵。n数组数组sasa中的元素中的元素saksak 与三对角带状矩阵中的元素与三对角带状矩阵中的元素a aijij存在一一对应关系，存在一一对应关系，在在a aijij之前有
21、之前有i i行行,共有共有3 3*i-1i-1个非零元素，在第个非零元素，在第i i行，有行，有j-i+1j-i+1个非零元素，个非零元素，这样，非零元素这样，非零元素a aijij的地址为：的地址为：LOC(i,jLOC(i,j)=LOC(0,0)+3)=LOC(0,0)+3*i-1+(j-i+1)i-1+(j-i+1)*L=LOC(0,0)+(2i+j)L=LOC(0,0)+(2i+j)*L L11340006921000177300002059000123数据结构数据结构1313稀疏矩阵及其存储稀疏矩阵及其存储n上述的各种特殊矩阵，其非零元素的分布都是有规律的，因此总上述的各种特殊矩阵，
22、其非零元素的分布都是有规律的，因此总能找到一种方法将它们压缩存储到一个向量中，并且一般都能找能找到一种方法将它们压缩存储到一个向量中，并且一般都能找到矩阵中的元素与该向量的对应关系，通过这个关系，仍能对矩到矩阵中的元素与该向量的对应关系，通过这个关系，仍能对矩阵的元素进行随机存取。阵的元素进行随机存取。n稀疏矩阵：设矩阵稀疏矩阵：设矩阵A A中有中有s s个非零元素，若个非零元素，若s s远远小于矩阵元素的远远小于矩阵元素的总数（通常认为总数（通常认为s s0.50.5m mn n），则称），则称A A为稀疏矩阵。为稀疏矩阵。0200000000000210010070003数据结构数据结构1
23、414稀疏矩阵的存储稀疏矩阵的存储n类似于特殊矩阵的存储，可以只存储稀疏矩阵的非零元素。但由类似于特殊矩阵的存储，可以只存储稀疏矩阵的非零元素。但由于非零元素的分布一般是没有规律的，因此在存储非零元素的同于非零元素的分布一般是没有规律的，因此在存储非零元素的同时，还必须同时记下它所在的行和列的位置（时，还必须同时记下它所在的行和列的位置（i,ji,j)。反之，一个。反之，一个三元组三元组(i,j,a(i,j,aijij)唯一确定了矩阵唯一确定了矩阵A A的一个非零元。因此，稀疏矩的一个非零元。因此，稀疏矩阵可由表示非零元素的三元组及其行列数唯一确定。阵可由表示非零元素的三元组及其行列数唯一确定
24、。n下列三元组表下列三元组表(1,2,12)(1,3,9),(3,1,-(1,2,12)(1,3,9),(3,1,-3),(3,6,14),(4,3,24),(5,2,18),(6,1,15),(6,4,-7)3),(3,6,14),(4,3,24),(5,2,18),(6,1,15),(6,4,-7)加上加上(6,7)(6,7)这一对行、列值便可作为下列矩阵这一对行、列值便可作为下列矩阵M M的另一种描述。的另一种描述。00070015000001800000240001400003000000000009120M数据结构数据结构1515n假设以顺序存储结构来表示三元组表，则可得到稀疏假设以
25、顺序存储结构来表示三元组表，则可得到稀疏矩阵的一种压缩存储方法矩阵的一种压缩存储方法三元顺序表。三元顺序表。#define maxsize#define maxsize 12500 12500 typedef struct typedef struct int i,j int i,j;datatype datatype v;v;triple;triple;typedef structtypedef struct triple datamaxsize triple datamaxsize+1;/data0+1;/data0未用未用 int m,n,tint m,n,t;/t/t为非零元素的个数，
26、即线性表的长度为非零元素的个数，即线性表的长度 tripletabletripletable;稀疏矩阵的三元组顺序表稀疏矩阵的三元组顺序表数据结构数据结构1616n显然，在三元组顺序表中容易从给定的行列号显然，在三元组顺序表中容易从给定的行列号(i,j(i,j)找到对应的矩阵元素。首先按行号找到对应的矩阵元素。首先按行号i i在顺序在顺序表中进行表中进行“有序有序”搜索搜索,找到相同的找到相同的i i之后再按列之后再按列号进行有序搜索，若在三元组顺序表中找到行号号进行有序搜索，若在三元组顺序表中找到行号和列号都和给定值相同的元素，则其中的非零元和列号都和给定值相同的元素，则其中的非零元值即为所
27、求，否则为矩阵中的零元。值即为所求，否则为矩阵中的零元。n同一行的下一个非零元即为顺序表中的后继，搜同一行的下一个非零元即为顺序表中的后继，搜索同一列中下一个非零元稍微麻烦些，但由于顺索同一列中下一个非零元稍微麻烦些，但由于顺序表是以行号为主序有序的，则在依次搜索过程序表是以行号为主序有序的，则在依次搜索过程中遇到的下一个列号相同的元素即为同一列的下中遇到的下一个列号相同的元素即为同一列的下一个非零元。一个非零元。数据结构数据结构1717n讨论当以三元组顺序讨论当以三元组顺序表表示稀疏矩阵时，表表示稀疏矩阵时，如何进行如何进行“转置转置”运运算。算。n一个一个m mn n的矩阵的矩阵A A，它
28、，它的转置的转置B B是一个是一个n nm m的的矩阵，且矩阵，且aij=bjiaij=bji，0 0imim，0 0jnjn，即，即A A的行是的行是B B的列，的列，A A的列的列是是B B的行。的行。数据结构数据结构1818n由于由于A A的列是的列是B B的行，因此，按的行，因此，按a.dataa.data的列序转置，所得到的转置矩阵的列序转置，所得到的转置矩阵B B的三元组表的三元组表b.datab.data必定是按行优先存放的。必定是按行优先存放的。n按这种方法设计的算法，其基本思想是：对按这种方法设计的算法，其基本思想是：对A A中的每一列中的每一列col(0col(0colco
29、ln-1)n-1)，通过从头至尾扫描三元表，通过从头至尾扫描三元表a.dataa.data，找出所有列号，找出所有列号等于等于colcol的那些三元组，将它们的行号和列号互换后依次放入的那些三元组，将它们的行号和列号互换后依次放入b.datab.data中，即可得到中，即可得到B B的按行优先的压缩存储表示。的按行优先的压缩存储表示。nStatus TransposeSMatrix(TSMatrix M,TSMatrixStatus TransposeSMatrix(TSMatrix M,TSMatrix&T)&T)T.mu=M.nu;T.nu=M.mu;T.tu=M.tuT.mu=M.nu;
30、T.nu=M.mu;T.tu=M.tu;if(T.tu if(T.tu)q=1;q=1;for(col=1;col=M.nu;+col for(col=1;col=M.nu;+col)for(p=1;p=M.tu for(p=1;p=M.tu;+p);+p)if(M.datap.j=col if(M.datap.j=col)T.dataq.i=M.datap.j T.dataq.i=M.datap.j;T.dataq.j=M.datap.i T.dataq.j=M.datap.i;T.dataq.e=M.datap.e T.dataq.e=M.datap.e;+q;+q;return OK;r
31、eturn OK;/TransposeSMatrix/TransposeSMatrix 时间复杂度为时间复杂度为O O(M.nu(M.nu*M.tu M.tu)数据结构数据结构1919n一般传统矩阵的转置算法为：一般传统矩阵的转置算法为：for(rowfor(row=0;row=mu-1;+row)=0;row=mu-1;+row)for(colfor(col=0;col=nu-1;+col)=0;col=nu-1;+col)tcolrow=mrowcoltcolrow=mrowcol;其时间复杂度为其时间复杂度为O(M.nuO(M.nu*M.muM.mu)。n当非零元素的个数当非零元素的个数
32、tutu和和mumu*nunu同数量级时，算法同数量级时，算法transmatrixtransmatrix的时间复杂度为的时间复杂度为O(muO(mu*nunu2 2)。n三元组顺序表虽然节省了存储空间，但时间复杂三元组顺序表虽然节省了存储空间，但时间复杂度比一般矩阵转置的算法还要复杂因此，此算法度比一般矩阵转置的算法还要复杂因此，此算法仅适用于仅适用于tmtm*n n的情况。的情况。数据结构数据结构2020快速转置算法快速转置算法n快速转置算法按快速转置算法按a.dataa.data中三元组的次序进行转置，并将转置后的中三元组的次序进行转置，并将转置后的三元组放入三元组放入b b中恰当的位置
33、。中恰当的位置。n快速转置算法首先在转置前求出矩阵快速转置算法首先在转置前求出矩阵A A的每一列的每一列colcol（即（即B B中每一中每一行）的第一个非零元转置后在行）的第一个非零元转置后在b.datab.data中的正确位置中的正确位置cpotcolcpotcol（0cola.nu0cola.nu），然后在对），然后在对a.dataa.data的三元组依次作转置时，只的三元组依次作转置时，只要将三元组按列号要将三元组按列号colcol放置到放置到b.datacpotcolb.datacpotcol中，之后将中，之后将cpotcolcpotcol 内容加内容加1 1，以指示第，以指示第co
34、lcol列的下一个非零元的正确位置。列的下一个非零元的正确位置。n为了求得位置向量为了求得位置向量cpotcpot，只要先求出，只要先求出A A的每一列中非零元个数的每一列中非零元个数numcolnumcol，然后利用下面的递推公式即可确定，然后利用下面的递推公式即可确定cpotcpot：cpot1=1cpot1=1 cpotcolcpotcol=cpotcol-1+numcol-1=cpotcol-1+numcol-1 2=cpl=a.nu 2=cpl=a.nun如如 数据结构数据结构2121nStatus FastTransposeSMatrix(TSMatrix M,TSMatrix&T
35、)T.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;t=M.tu;+t)/求 M 中每一列所含非零元的个数 +numM.datat.j;cpot1=1;/求 M 中每一列的第一个非零元在 b.data 中的序号 for(col=2;col=M.nu;+col)cpotcol=cpotcol-1+numcol-1;for(p=1;p=M.tu;+p)col=M.datap.j;q=cpotcol;T.dataq.i=M.datap.j;T.dataq.j=M.datap.i;T.dataq
36、.e=M.datap.e;+cpotcol;/for /if return OK;/FastTransposeSMatrixn算法的时间复杂度为算法的时间复杂度为O O(M.nu+M.tu(M.nu+M.tu).).当非零元素的个数当非零元素的个数tutu和和mumu*nunu同数量级时，同数量级时，算法算法FasttransmatrixFasttransmatrix的时间复杂度为的时间复杂度为O(M.nuO(M.nu*M.tuM.tu)。数据结构数据结构2222稀疏矩阵的行逻辑链接顺序表稀疏矩阵的行逻辑链接顺序表n由于三元组顺序表以行序为主序存放矩阵的非零元，则为由于三元组顺序表以行序为主序
37、存放矩阵的非零元，则为取得第取得第i i行的非零元，必须从第一个元素起进行搜索查询。行的非零元，必须从第一个元素起进行搜索查询。n而从上述讨论的矩阵转置算法可见，在算法过程中计算得而从上述讨论的矩阵转置算法可见，在算法过程中计算得到的到的cpotcolcpotcol 中的值实际上起到了一个中的值实际上起到了一个“指示矩阵中每指示矩阵中每一行的第一个非零元在三元组表中的序号一行的第一个非零元在三元组表中的序号”的作用，因此的作用，因此如果在建立稀疏矩阵的三元组顺序表的同时将这个信息固如果在建立稀疏矩阵的三元组顺序表的同时将这个信息固定在存储结构中，将便于随机存取稀疏矩阵中任意一行的定在存储结构中
38、，将便于随机存取稀疏矩阵中任意一行的非零元素。这种表示方法为非零元素。这种表示方法为“行逻辑链接行逻辑链接”的顺序表。的顺序表。n#define MAXRC 100#define MAXRC 100 typedef struct typedef struct Triple dataMAXSIZE Triple dataMAXSIZE+1;+1;int rposMAXRC int rposMAXRC+1;+1;/各行第一个非零元素的位置表各行第一个非零元素的位置表 int mu,nu,tuint mu,nu,tu;RLSMATRIX RLSMATRIX数据结构数据结构2323稀疏矩阵的相乘稀疏矩
39、阵的相乘n设设Q=MQ=M*N N，其中，其中，M M是是m m1 1*n n1 1矩阵，矩阵，N N是是m m2 2*n n2 2矩阵。则当矩阵。则当n n1 1=m=m2 2时有：时有：for(ifor(i=1;i=m1;+i)=1;i=m1;+i)for(j for(j=1;j=n2;+j)=1;j=n2;+j)qij qij=0=0 for(k for(k=1;k=n1;+k)=1;k=n1;+k)qij+=mik qij+=mik*nkjnkj;此算法的复杂度为此算法的复杂度为O(mO(m1 1*n n1 1*n n2 2)。n对于稀疏矩阵，只要对对于稀疏矩阵，只要对M.dataM.
40、data中的每个元素（中的每个元素（i,k,M(i,ki,k,M(i,k)）找到）找到N.dataN.data中所中所有相应的元素（有相应的元素（k,j,N(k,jk,j,N(k,j)）相乘后累加即可。因此需要第）相乘后累加即可。因此需要第k k行的所有元素行的所有元素信息，在稀疏矩阵的行逻辑链接顺序表中，信息，在稀疏矩阵的行逻辑链接顺序表中，N.rposN.rpos为我们提供了有关的信息。为我们提供了有关的信息。n稀疏矩阵相乘稀疏矩阵相乘 Q Q初始化初始化;ifQifQ是非零矩阵是非零矩阵 for(arow=1;arow=M.mu;+arowfor(arow=1;arow=M.mu;+ar
41、ow)/)/处理处理M M的每一行的每一行 ctempctemp=0;=0;/累加器清零累加器清零计算计算 Q Q 中第中第 arowarow 行的积并存入行的积并存入 ctempctemp 中；中；将将 ctempctemp 中非零元压缩存储到中非零元压缩存储到 Q.dataQ.data；/for arow/for arow/if/if 数据结构数据结构2424nStatus MultSMatrix(RLSMatrix M,RLSMatrix N,RLSMatrixStatus MultSMatrix(RLSMatrix M,RLSMatrix N,RLSMatrix&Q)&Q)if(M.n
42、u!=N.mu if(M.nu!=N.mu)return ERROR;)return ERROR;Q.mu=M.mu;Q.nu=N.nu;Q.tu Q.mu=M.mu;Q.nu=N.nu;Q.tu=0;/Q=0;/Q初始化初始化 if(M.tuif(M.tu*N.tuN.tu!=0)/Q!=0)/Q是非零矩阵是非零矩阵 for(arow=1;arow=M.mu;+arowfor(arow=1;arow=M.mu;+arow)/)/处理处理M M的每一行的每一行 for(l=1;l=N.nu;+l)ctemplfor(l=1;l=N.nu;+l)ctempl=0;/=0;/当前行各元素累加器清零
43、当前行各元素累加器清零 Q.rposarowQ.rposarow=Q.tu+1;=Q.tu+1;if(arowM.mu)tp if(arowM.mu)tp=M.rposarow+1;=M.rposarow+1;else tp else tp=M.tu+1;=M.tu+1;for(p=M.rposarow;ptp;+p for(p=M.rposarow;ptp;+p)/)/对当前行中每一个非零元对当前行中每一个非零元 brow=M.datap.jbrow=M.datap.j;/;/找到对应元在找到对应元在N N中的行号中的行号 if(brow N.muif(brow N.mu)t=N.rposb
44、row+1;)t=N.rposbrow+1;else t=N.tu+1;else t=N.tu+1;for(q=N.rposbrow for(q=N.rposbrow;q t;+q);q t;+q)ccol=N.dataq.j ccol=N.dataq.j;/;/乘积元素在乘积元素在Q Q中列号中列号 ctempccol+=M.datap.e ctempccol+=M.datap.e*N.dataq.e N.dataq.e;/for q/for q /求得求得Q Q中第中第crow(=arowcrow(=arow)行的非零元行的非零元 for(ccol=1;ccol=Q.nu;+ccolfor
45、(ccol=1;ccol MAXSIZE)return ERROR;MAXSIZE)return ERROR;Q.dataQ.tui Q.dataQ.tui=（arowarow，ccolccol，ctempccolctempccol）;/if /if /for arow /for arow /if /if return OK;return OK;/MultSMatrix数据结构数据结构2525n上述算法中，累加器上述算法中，累加器ctempctemp初始化的时间复杂度为初始化的时间复杂度为O O(M.mu(M.mu*N.nuN.nu)，求，求Q Q的所有非零元的时间复杂度为的所有非零元的时间复
46、杂度为O O(M.tu(M.tu*N.tu/N.muN.tu/N.mu)（N.tu/N.muN.tu/N.mu表示表示N N中每一行中每一行非零元个数的平均值），对非零元个数的平均值），对Q Q进行压缩存储的时间进行压缩存储的时间复杂度为复杂度为 O O(M.mu(M.mu*N.nuN.nu)。则总的时间复杂度为。则总的时间复杂度为O O(M.mu(M.mu*N.nu)+N.nu)+O O(M.tu(M.tu*N.tu/N.mu)+N.tu/N.mu)+O O(M.mu(M.mu*N.nuN.nu)=O O(M.mu(M.mu*N.nu+M.tuN.nu+M.tu*N.tu/N.muN.tu/
47、N.mu)。n若若 M M 是是 m m 行行 n n 列的稀疏矩阵，列的稀疏矩阵，N N 是是 n n 行行 p p 列列的稀疏矩阵，则的稀疏矩阵，则M M中非零元的个数中非零元的个数 M.tu=M.tu=q qm mm mn n，N N中非零元的个数中非零元的个数 N.tu=qN.tu=qn nn np p，此时上述算法的时间复杂度就是此时上述算法的时间复杂度就是O O(m(mp p(1+nq(1+nqm mq qn n)，当，当q qm m0.05 0.05 和和q qn n0.05 0.05 及及 n1000n1000时，上述算法的时间复杂度就相当于时，上述算法的时间复杂度就相当于O(
48、mO(mp p)，显然，这是一个相当理想的结果。如果，显然，这是一个相当理想的结果。如果事先能估算出所求乘积矩阵事先能估算出所求乘积矩阵 Q Q 非是稀疏矩阵，也非是稀疏矩阵，也可设它的存储结构为二维数组，此时的矩阵相乘可设它的存储结构为二维数组，此时的矩阵相乘算法更为简单。算法更为简单。数据结构数据结构2626稀疏矩阵的十字链表稀疏矩阵的十字链表n当稀疏矩阵中的非零元素个数和位置在操作过程中变化较当稀疏矩阵中的非零元素个数和位置在操作过程中变化较大时，不宜采用顺序存储结构来表示三元组的线性表。因大时，不宜采用顺序存储结构来表示三元组的线性表。因为这会引起数据元素在线性表中的移动。此时宜采用链
49、式为这会引起数据元素在线性表中的移动。此时宜采用链式存储结构。存储结构。n十字链表是稀疏矩阵的链式存储中一种较好的存储方法，十字链表是稀疏矩阵的链式存储中一种较好的存储方法，在该方法中，每一个非零元用一个结点表示，结点中除了在该方法中，每一个非零元用一个结点表示，结点中除了表示非零元所在的行、列和值的三元组（表示非零元所在的行、列和值的三元组（i,j,vi,j,v）外，还）外，还增加了两个链域：行指针域（增加了两个链域：行指针域（rightright），用来指向本行中），用来指向本行中下一个非零元素；列指针域（下一个非零元素；列指针域（downdown），用来指向本列中下），用来指向本列中下一
50、个非零元素。一个非零元素。n此时，稀疏矩阵中同一行的非零元通过向右的此时，稀疏矩阵中同一行的非零元通过向右的rightright指针指针链接成一个带头结点的链表。同一列的非零元通过链接成一个带头结点的链表。同一列的非零元通过downdown指指针链接成一个带头结点的链表。因此，每个非零元既是第针链接成一个带头结点的链表。因此，每个非零元既是第i i行链表中的一个结点，又是第行链表中的一个结点，又是第j j列循环链表中的一个结点，列循环链表中的一个结点，相当于处在一个十字交叉路口，故称此种链表为十字链表。相当于处在一个十字交叉路口，故称此种链表为十字链表。数据结构数据结构2727数据结构数据结构
