数据结构-第七周-稀疏矩阵课件.pptx

1、矩阵矩阵是一个具有是一个具有m行行n列列的数据表，共的数据表，共包包含含有有m*n个元素，每个个元素，每个元素处在确定行和列元素处在确定行和列的交点位置上，与的交点位置上，与一对行号和列号一对行号和列号唯一对应唯一对应。矩阵是很多科学与工程计算问题中研究矩阵是很多科学与工程计算问题中研究的数学对象，的数学对象，在用高级语言编程时，一般采在用高级语言编程时，一般采用二维数组来存储矩阵。用二维数组来存储矩阵。矩阵矩阵普通矩阵的完全存储普通矩阵的完全存储u 如果矩阵中的每个元素的值都是不如果矩阵中的每个元素的值都是不能确定的值，那么存储这样的矩阵能确定的值，那么存储这样的矩阵时，每个元素都必须存储，

2、时，每个元素都必须存储，即即需要需要完全完全存储。存储。u 用高级语言描述用高级语言描述时，时，就是使用二就是使用二维维数组的形式数组的形式存储矩阵。存储矩阵。u 有的矩阵中，有的矩阵中，非零元素非零元素非常少非常少-稀疏矩阵稀疏矩阵u 还还有一些有一些矩阵的元素分布有一定的规律矩阵的元素分布有一定的规律-特特殊矩阵（比如对称矩阵、三角矩阵）殊矩阵（比如对称矩阵、三角矩阵）特殊矩阵和稀疏矩阵特殊矩阵和稀疏矩阵3647862842481697460582957对称矩阵对称矩阵3cccc62ccc481cc7460c82957三角矩阵三角矩阵特殊矩阵a00a01000a10a11a12000a21

3、a22a23000a32a33a34000a43a44对角矩阵对角矩阵特殊矩阵15000210000000010600000050900000稀疏矩阵稀疏矩阵稀疏矩阵对于特殊矩阵和稀疏矩阵对于特殊矩阵和稀疏矩阵若若仍采用二维数仍采用二维数组形式存放组形式存放，将造成，将造成存储单元的很大浪费。存储单元的很大浪费。可以利用这些矩阵的特点和规律，只可以利用这些矩阵的特点和规律，只存储部分元素，从而提高存储空间的存储部分元素，从而提高存储空间的利用率。利用率。矩阵的压缩存储矩阵的压缩存储特殊矩阵和稀疏矩阵的压缩存储 在对特殊矩阵和稀疏矩阵进行存储时，为了节省存储空间，可以对这类矩阵进行压缩存储。压缩

4、存储的基本思想是：多个值相同的元素只分配一个存储空间；对零元素不分配存储空间。对称矩阵对称矩阵的压缩存储的压缩存储3647862842481697460582957An阶对称矩阵（阶对称矩阵（方阵方阵）特点特点：aij=aji如何压缩存储？如何压缩存储？只只存储下三角部分的存储下三角部分的元素元素或是或是上三角部分上三角部分的元素的元素，使得每两个对称元素共享一个存，使得每两个对称元素共享一个存储空间。储空间。压缩存储后节省了多少空间？压缩存储后节省了多少空间？对于一个对于一个n阶对称矩阵，如果完全存储需要阶对称矩阵，如果完全存储需要n2个个存储空间；存储空间；如果压缩存储，需要如果压缩存储，

5、需要n(n+1)/2个存储空间。个存储空间。对称矩阵对称矩阵的压缩存储的压缩存储3647862842481697460582957A定义一个一维数组定义一个一维数组san(n+1)/2作为作为n阶阶对称矩阵对称矩阵A的存储结构，那么对称矩阵的存储结构，那么对称矩阵A中任一元素中任一元素aij和和sak之间的之间的对应关系对应关系如何？如何？对称矩阵对称矩阵的压缩存储的压缩存储(a)下三角矩阵下三角矩阵(b)存储说明存储说明(c)计算方法计算方法aij在一维数组中在一维数组中的的下标下标=阴影部分的阴影部分的面面积积=i(i+1)/2+j0 i n-10j n-1 aij每行元素个数每行元素个数

6、12iaij在本行中的序号在本行中的序号aij第第0行行第第1行行第第i-1行行对称矩阵的压缩存储对称矩阵的压缩存储对于下三角中的元素对于下三角中的元素aij（i=j），在一维数组在一维数组sa中中的的下下标标k与与i、j的关系为：的关系为：ki(i1)/2j 上三角中的元素上三角中的元素aij（ij），），因为因为aijaji，则访问和它则访问和它对应的元素对应的元素aji即可，即：即可，即：kj(j1)/2i对称矩阵的压缩存储对称矩阵的压缩存储第第1行行第第n-1行行第第0行行 a00 a10 a11 a20 a21 a22 aij a n-10 an-11 an-1n-1 第第2行行01

7、2345kn(n+1)/2-1例：将压缩存储在一维数组例：将压缩存储在一维数组a a中的中的4x44x4阶阶对称矩阵按矩阵格式输出。对称矩阵按矩阵格式输出。int i,j;for(i=0;i4;i+)for(j=0;j=j)coutai*(i+1)/2+j;/*输出主对角线以及主对角线以下元素*/else coutaj*(j+1)/2+i;/*输出主对角线以上元素*/coutendl;三三角角矩阵矩阵的压缩存储的压缩存储3cccc62ccc481cc7460c82957(a)下三角矩阵下三角矩阵34810c2946cc57ccc08cccc7(b)上三角矩阵上三角矩阵n n阶阶上上（下下）三角

8、矩阵三角矩阵是指是指下下（上上）三角三角（不（不包括主对角线）中的元素均为常数包括主对角线）中的元素均为常数c c三三角角矩阵矩阵的压缩存储的压缩存储3cccc62ccc481cc7460c82957(a)下三角矩阵下三角矩阵34810c2946cc57ccc08cccc7(b)上三角矩阵上三角矩阵如何压缩如何压缩存储三角矩阵？存储三角矩阵？可以只可以只存储上三角（或下三角）部分的存储上三角（或下三角）部分的元元素，对于常量素，对于常量c多开辟一个空间来存储。多开辟一个空间来存储。下三角矩阵中任一元素下三角矩阵中任一元素aij在在一维一维数组数组中的下标中的下标k与与i、j的的对应关系：对应关

9、系：i(i1)/2j 当当ijn(n1)/2当当ijk=下三角矩阵的压缩存储下三角矩阵的压缩存储012345kn(n+1)/2-1n(n+1)/2第第1行行第第0行行 a00 a10 a11 a20 a21 aij an-1n-1 第第2行行 c a22存储存储下三角下三角元素元素对角线上方的常数对角线上方的常数只存一个只存一个数据元素数据元素sasan(n+1)/2n(n+1)/2用于存放常量用于存放常量c c矩阵中任一元素矩阵中任一元素aij在在数组数组中的下标中的下标k与与i、j的对应关系：的对应关系：i(2n-i+1)/2+j-i 当当ijn(n1)/2当当ijk=上三角矩阵的压缩存储

10、上三角矩阵的压缩存储存储存储上三角上三角元素元素对角线上方的常数对角线上方的常数只存一个只存一个数据元素数据元素sasan(n+1)/2n(n+1)/2用于存放常量用于存放常量c c对角矩阵对角矩阵压缩存储压缩存储对角矩阵对角矩阵：n n阶对角矩阵是指阶对角矩阵是指所有所有非零元素都集中在非零元素都集中在以主对角线为中心的带状区域中，除了以主对角线为中心的带状区域中，除了主主对角线和它的上对角线和它的上下方若干条对角线下方若干条对角线的元素的元素外，所有其他元素都为零。外，所有其他元素都为零。n n阶三对角矩阵：阶三对角矩阵：n n阶三对角矩阵的非零元素仅出现在阶三对角矩阵的非零元素仅出现在主

11、对角线主对角线(a(aiiii,0=i=n-1),0=i=n-1)上以及紧邻主对角线上面的上以及紧邻主对角线上面的那条对角线上（那条对角线上（a aii+1ii+1,0=i=n-2),0=i=n-2)和紧邻主对角线下面和紧邻主对角线下面的那条对角线上的那条对角线上（a ai+1ii+1i,0,0=i=n-2=i1时，时，元素元素aijij=0元素元素aij与一与一维数维数组下标组下标k的关系：的关系：k=2+3(i1)+(ji+1)=2i+j(b)一维数组元素一维数组元素sak和矩阵和矩阵元素元素aij的对应关系的对应关系(c)压缩到一维数组中压缩到一维数组中a00 a01 a10 a11 a

12、12 a21 a22 a23 a32 a33 a34 a43 a440123456789101112三三对角矩阵对角矩阵的压缩存储的压缩存储(a)三对角矩阵三对角矩阵000000000000A=a00a01a10a11a12a21a22 a23a32a33 a34a43a44稀疏矩阵稀疏矩阵的压缩存储的压缩存储15000000000110000600000000900000A=若矩阵若矩阵A Amxnmxn中的非零元素个数非常少，且非中的非零元素个数非常少，且非零元素的分布没有任何规律，则称该矩阵为零元素的分布没有任何规律，则称该矩阵为稀疏矩阵。稀疏矩阵。稀疏矩阵稀疏矩阵的压缩存储的压缩存储1

13、5000000110000000600000000900000A=如何如何只存储非零元素？只存储非零元素？稀疏矩阵稀疏矩阵中的非零元素的分布没有规律。中的非零元素的分布没有规律。由于稀疏矩阵中非零元素的分布没有规律，因此由于稀疏矩阵中非零元素的分布没有规律，因此在存储在存储非零元素的值非零元素的值的同时，还必须记下该的同时，还必须记下该非零非零元素元素在矩阵中的在矩阵中的行号行号和和列号列号。稀疏矩阵的压缩存储稀疏矩阵的压缩存储定义三元组：定义三元组：稀疏矩阵稀疏矩阵中的每个非中的每个非零元素对应一个三元组零元素对应一个三元组：(行号，列号，非零元素值行号，列号，非零元素值)三元组三元组三元组

14、表三元组表：将稀疏矩阵将稀疏矩阵的所有非的所有非零元素对应的三元零元素对应的三元组所构成的集合，组所构成的集合，按行优先的顺序按行优先的顺序排列成一排列成一个个三元三元组线性表组线性表。三元组三元组表表：(0,2,1),(1,1,2),(2,0,3),(3,3,5),(4,4,6),(5,5,7),(5,6,4)如何存储三元组表？如何存储三元组表？47000000060000000500000000030000020000010076A若把稀疏矩阵的若把稀疏矩阵的三元组线性表三元组线性表按顺序存储结按顺序存储结构存储构存储,则称为稀疏矩阵的则称为稀疏矩阵的三元组顺序表三元组顺序表。示例示例A5

15、6=003513053100017000600200210000100800rowcolval数组数组bbm 0352011330255033101417415622620527211381049834行号：行号：0到到4列号：列号：0到到5该三元组线性表按该三元组线性表按“行序为主序行序为主序”，用用一维数组进行存放一维数组进行存放按按“列序为主序列序为主序”的三元组线性表的三元组线性表typedefstruct/三元组的类型定义三元组的类型定义introw;/非零元素行非零元素行号号intcol;/非零元素列号非零元素列号ElemTypeval;/非零元素值非零元素值tupletype;#

16、defineMAXSIZE100;typedefstruct/三元组三元组顺序表存储结构定义顺序表存储结构定义tupletypedataMAXSIZE;/非零元素的三元组表非零元素的三元组表intrnum;/矩阵行矩阵行数数intcnum;/矩阵矩阵列数列数intlen;/矩阵矩阵总非总非零元素个数零元素个数table;三元组顺序表存储结构定义 三元组三元组顺序表顺序表采用顺序存储结构存储三元组表采用顺序存储结构存储三元组表0015032205-1511111232364091空空空空空空闲闲闲闲闲闲rowcole0123456MAXSIZE-11500220-1501130000006000

17、000009100000A=5（矩阵的行矩阵的行数）数）6（矩阵的列数矩阵的列数）7（非零元非零元个数个数）(1)从一从一个稀疏矩阵个稀疏矩阵创建创建其对应三元组表其对应三元组表以行序方式以行序方式扫描扫描二二维稀疏矩阵维稀疏矩阵A,将其非零的元素插入到将其非零的元素插入到三元三元组顺序表组顺序表m的的后面。算法如下后面。算法如下：#defineM16#defineN17voidCreatTable(table*m,ElemTypeAM1N1)inti,j;m-rnum=M1;m-cnum=N1;m-len=0;for(i=0;iM1;i+)for(j=0;jdatam-len.row=i;m

18、-datam-len.col=j;m-datam-len.val=Aij;m-len+;(2)取值操作，从三元组表中取出稀疏矩阵指定取值操作，从三元组表中取出稀疏矩阵指定位置的位置的元素元素值值算法算法思路：先思路：先在在三元组三元组m中中找到指定的位置找到指定的位置,然后将然后将该处该处的元素值赋给的元素值赋给x。intgetvalue(table*m,ElemType*x,inti,intj)intk=0;if(i=m-rnum|j=m-cnum)return0;while(klen&im-datak.row)k+;/找第找第i行行while(klen&jm-datak.col)k+;/找

19、找第第j列列if(m-datak.row=i&m-datak.col=j)/元素存在元素存在*x=m-datak.val;return1;elsereturn0;(3)稀疏矩阵稀疏矩阵赋值，将给定值，赋值到三元组表的指定位置赋值，将给定值，赋值到三元组表的指定位置算法算法思路：先思路：先在在三元组表三元组表m中找到指定的中找到指定的位置位置k,若指定若指定位置已经有值，则用给定值替换原有值，否则，将指位置已经有值，则用给定值替换原有值，否则，将指定位置定位置k及其后面的元素及其后面的元素后移一位后移一位,然后将给定的元素然后将给定的元素值值x插入插入到指定位置处。到指定位置处。intputVa

20、lue(table*m,ElemTypex,inti,intj)inti,k=0;if(i=m-rnum|j=m-cnum)return0;while(klen&im-datak.row)k+;/找找第第i行行while(klen&jm-datak.col)k+;/找找第第j列列if(m-datak.row=i&m-datak.col=j)/元素存在元素存在m-datak.val=x;/用给定值用给定值x替换原值替换原值else/*元素不存在时，将其插入元素不存在时，将其插入*/for(i=m-len-1;i=k;i-)/*元素后移元素后移*/m-datai+1=m-datai;m-datak

21、.row=i;m-datak.col=j;m-datak.val=x;m-len+;return1;(4)按矩阵格式输出以三元组顺序表存储的稀疏矩阵按矩阵格式输出以三元组顺序表存储的稀疏矩阵算法思路：对稀疏矩阵中的每个元素，从头到尾算法思路：对稀疏矩阵中的每个元素，从头到尾扫描扫描三元组三元组m,若在三元组表中存在，则输出其元素值，否若在三元组表中存在，则输出其元素值，否则输出则输出0。void DispTable(table*m)int i,j,k,e;for(i=0;irnum;i+)for(j=0;jcnum;j+)e=0;for(k=0;klen;k+)if(i=m-datak.row

22、&j=m-datak.col)e=m-datak.val;break;coute ;cout-rnumrnum=ta-=ta-cnumcnum;tbtb-cnumcnum=ta-=ta-rnumrnum;tbtb-lenlen=ta-=ta-lenlen;for(i=0;ita-for(i=0;i len;ilen;i+)+)tbtb-datai.row=ta-datai.row=ta-datai.datai.col;col;tbtb-datai.col=ta-datai.col=ta-datai.datai.row;row;tbtb-datai.datai.valval=ta-=ta-dat

23、ai.datai.valval;算法缺点：算法缺点：无法无法保证三元保证三元组组表表tbtb也也是以是以“行序为主序行序为主序”进行进行存放存放算法思路（算法思路（2）：为了保证三元组为了保证三元组表表tb也也是以是以“行序为主序行序为主序”进行进行存放，按照三存放，按照三元组元组ta的列序（的列序（即转置后三元组表即转置后三元组表tb的行序的行序）进行转置。）进行转置。即将稀疏矩阵即将稀疏矩阵A，按照列序将每列中的非零元素，转置后依次按照列序将每列中的非零元素，转置后依次送入三元组表送入三元组表tb中存储，这样得到的三元组表中存储，这样得到的三元组表tb恰好是以恰好是以“行行序为主序序为主序

24、”。具体具体过程：第一次扫描三元组过程：第一次扫描三元组表表ta时，逐个找出所有列号为时，逐个找出所有列号为0的三元组，转置后按顺序送入三元组的三元组，转置后按顺序送入三元组表表tb中；同理，第二遍扫中；同理，第二遍扫描三元组表描三元组表ta,逐个找出所有列号为逐个找出所有列号为1的的三元组，转置后按顺序三元组，转置后按顺序送入送入三元组三元组表表tb中；反复进行，将所有列号都进行一遍。中；反复进行，将所有列号都进行一遍。最后一遍最后一遍扫描三元组扫描三元组表表tb,逐个找出所有列号逐个找出所有列号为为cunm-1的的三元三元组，转置后按顺序送入组，转置后按顺序送入三元组三元组表表tb中。中。

25、(5)稀疏矩阵稀疏矩阵Amn用三元组顺序表用三元组顺序表ta存储，实现对稀存储，实现对稀疏矩阵的转置疏矩阵的转置A34=009 1250000106rowcolval三元组顺序表三元组顺序表tata092011230250131124236B43=0500019001206rowcolval三元组顺序表三元组顺序表tbtb01234对对A逐列转置逐列转置即：即：逐行得到逐行得到B对对tata按照按照列号从列号从0 0到到cnum-1cnum-1依依次扫描次扫描？(5)稀疏矩阵转置稀疏矩阵转置（逐（逐行得到行得到B）voidtrans(table*ta,table*tb)intk,b,q;tb-

26、rnum=ta-cnum;tb-cnum=ta-rnum;tb-len=ta-len;q=0；/*q为为tb-data的下标的下标*/if(tb-len!=0)for(k=0;kcnum;k+)for(p=0;plen;p+)/*p为为ta-data的下标的下标*/if(ta-datap.col=k)tb-dataq.row=ta-datap.col;tb-dataq.col=ta-datap.row;tb-dataq.val=ta-datap.val;q+;以上算法的时间复杂度以上算法的时间复杂度为为O(ta-cnum*ta-len)而而将二维数组存储在一个将二维数组存储在一个m行行n列矩阵

27、中时列矩阵中时,其其转置算法的时间复杂度为转置算法的时间复杂度为O(m*n)当非零元素个数较小时，当非零元素个数较小时，O(ta-cnum*ta-len)优于优于O(m*n)算法思路算法思路（3）：分段定位：分段定位总体思路：转置时，总体思路：转置时，对对三元组表三元组表ta中的三元组依次进行转置，中的三元组依次进行转置，转置后的三元组直接放到对应稀疏矩阵转置后的三元组直接放到对应稀疏矩阵B的的三元组三元组表表tb中的中的分段位置上。分段位置上。为了能将待为了能将待转置的三元组表转置的三元组表ta中的元素一次定位到中的元素一次定位到三元组三元组表表tb的正确位置，的正确位置，需要需要预先对三元

28、组预先对三元组表表tb进行分段定位。进行分段定位。1）预先处理阶段预先处理阶段(a)计算稀疏矩阵计算稀疏矩阵A每一列中非零元素的个数（即：每一列中非零元素的个数（即：A转置后的转置后的稀疏矩阵稀疏矩阵B每一行中非零元素的个数）每一行中非零元素的个数）设置设置一个一个数组数组num来存放这些数。例如：来存放这些数。例如：numk中存放的是中存放的是矩阵矩阵A中第中第k列的非零元素的列的非零元素的个数（即个数（即：矩阵：矩阵B中第中第k行的行的非零非零元素的元素的个数）个数）(5)稀疏矩阵稀疏矩阵Amn用三元组顺序表用三元组顺序表ta存储，实现对稀存储，实现对稀疏矩阵的转置疏矩阵的转置算法思路算法

29、思路（3）：分段：分段定位定位1）预先处理阶段预先处理阶段(b)计算稀疏矩阵计算稀疏矩阵A每一列每一列中的中的第一个非零元素第一个非零元素在三元组表在三元组表tb中中的正确位置（的正确位置（即：即：A转置后转置后的矩阵的矩阵B每每一行中的一行中的第一第一个非个非零元零元素素在在三元组表三元组表tb中的正确位置中的正确位置）设置一个设置一个数组数组pot来存放来存放这些位置。这些位置。例如：例如：potk中存放的中存放的是矩阵是矩阵A中第中第k列中的列中的第一个非第一个非零元素零元素在在三元组表三元组表tb中的正确中的正确位置位置A56=00351305310001700060000210200

30、0100800rowcolval0352011330255033101417415622621137203381049834三元组顺序表三元组顺序表tata1 1、计算数组、计算数组numnum numnum数组初值为数组初值为0 0；将三元组表将三元组表tata扫描一遍，对于其中列扫描一遍，对于其中列号为号为k k的元素，给相应的的元素，给相应的numnumkk加加1 1。2 2、计算数组、计算数组pot pot pot0=0;pot0=0;potk=potk-1+potk=potk-1+numnumk-1;k-1;/k=1/k=1k012345numk212311potk0235891）预

31、先处理阶段预先处理阶段预先预先处理处理阶段得到一个分段定位的结果阶段得到一个分段定位的结果算法思路算法思路（3）：分段：分段定位定位2）转置阶段转置阶段对三元组表对三元组表ta进行扫描。进行扫描。数组数组pot中中的的值记录了矩阵值记录了矩阵A中每一列的中每一列的第一个非零第一个非零元素在三元组表元素在三元组表tb中的正确中的正确位置。位置。每当每当矩阵矩阵A中中第第k列有一个非零元素存入到列有一个非零元素存入到三元组表三元组表tb时，将时，将potk+，即：即：potk始终存放始终存放矩阵矩阵A第第k列中列中的下一个非零元素的正确位置。的下一个非零元素的正确位置。因此，通过因此，通过potk

32、可以得到三元组表可以得到三元组表ta中每个元素转中每个元素转置加入到置加入到三元组表三元组表tb时的正确位置。时的正确位置。(5)稀疏矩阵转置稀疏矩阵转置（分段定位分段定位）voidtrans(table*ta,table*tb)intk,q,i;intnumN,potN;tb-rnum=ta-cnum;tb-cnum=ta-rnum;tb-len=ta-len;for(k=0;kcnum;k+)/*初始化初始化num为为0*/numk=0;for(i=0;ilen;i+)/*将三元组表将三元组表ta扫描一遍，对于其中列号扫描一遍，对于其中列号为为k的元素，给相应的的元素，给相应的numk加加

33、1。*/numta-datai.col+;pot0=0;for(k=1;kcnum;k+)/*计算计算pot各数组元素的值各数组元素的值*/potk=potk-1+numk;for(p=0;ilen;p+)j=ta-datap.col;q=potj;tb-dataq.row=ta-datap.col;tb-dataq.col=ta-datap.row;tb-dataq.val=ta-datap.val;potj+;/*矩阵矩阵A本列上下一个非零元素的本列上下一个非零元素的位置，即矩阵位置，即矩阵B本行本行上下一个非零元素的位置上下一个非零元素的位置*/以上算法的以上算法的时间主要耗费在四个并列

34、的单循环上，时间主要耗费在四个并列的单循环上，这四个并列的单这四个并列的单循环分别循环了：循环分别循环了：ta-cnum、ta-len、ta-cnum、ta-len次，次，因此总的时间复杂度为：因此总的时间复杂度为：O(ta-cnum+ta-len)除了顺序存储，也可以把稀疏矩阵按除了顺序存储，也可以把稀疏矩阵按链式存链式存储结构储结构进行压缩存储。进行压缩存储。稀疏矩阵的三元组线性表的链式存储稀疏矩阵的三元组线性表的链式存储1 1、简单链式存储简单链式存储稀疏矩阵稀疏矩阵A A的每个非的每个非0 0元素对应一个结点，结点含有的元素对应一个结点，结点含有的域为域为:row(row(行号行号)、

35、colcol(列号列号),),valval(元素值元素值),next(),next(链链域域)。将所有的结点串成一个链表。将所有的结点串成一个链表。稀疏矩阵简单链式存储示例稀疏矩阵简单链式存储示例稀疏矩阵的三元组线性表的链式存储稀疏矩阵的三元组线性表的链式存储2 2、行链表组行链表组将稀疏矩阵将稀疏矩阵Amn每每一行一行中非零元素对应中非零元素对应的结点构成一个链表，的结点构成一个链表，m m个个行链表行链表形成一个链表形成一个链表组组-行链表行链表组组即：创建一个指针即：创建一个指针数组，数组元素中存放数组，数组元素中存放的就是的就是某某一行一行链表链表的的第一个结点的第一个结点的地址，即该

36、行链表的地址，即该行链表的头指针头指针。例如：。例如：ahiahi 是第是第i i个行个行链表的链表的头指针头指针3 3、稀疏矩阵的正交链表（十字链表）存储与稀疏矩阵的正交链表（十字链表）存储与实现实现正交链表正交链表存储思路是：为存储思路是：为稀疏矩阵的每稀疏矩阵的每一行非零元素一行非零元素设置设置一个单独链表一个单独链表,同时也为每一列非零元素设置一同时也为每一列非零元素设置一个单独链表。个单独链表。这样这样稀疏矩阵的每一个非零元素就同时包含在两个链稀疏矩阵的每一个非零元素就同时包含在两个链表中表中,即：即：每每一个非零元素同时一个非零元素同时包含在包含在所在行的所在行的行链表行链表中和中

37、和所在列的所在列的列链表列链表中中。从而降低从而降低了链表的了链表的长度长度，也方便了行也方便了行方向和列方向的方向和列方向的搜索。搜索。稀疏矩阵的三元组线性表的链式存储稀疏矩阵的三元组线性表的链式存储采用采用正交链表正交链表存储结构来存储稀疏矩阵：存储结构来存储稀疏矩阵：稀疏矩阵每个稀疏矩阵每个非非零元素存储零元素存储为一个为一个链表链表结点结点结点结点结构结构为：为：rowcolvaldownrightrow：存储非零元素的行号存储非零元素的行号col：存储非零元素的列号存储非零元素的列号val：存储非零元素的值存储非零元素的值right：指针域，指向同一行中指针域，指向同一行中的下的下一

38、个非零元素结点一个非零元素结点down：指针指针域，指向同一列中的下一个非零元素结点域，指向同一列中的下一个非零元素结点202M=300501002000003035111稀疏矩阵的压缩存储稀疏矩阵的压缩存储正交正交链表链表存储所有列链表的头指针的指针数组存储所有列链表的头指针的指针数组存储所有行链表的存储所有行链表的头指针的指针数组头指针的指针数组任一非零元素任一非零元素MijMij所对应的结点，既处在第所对应的结点，既处在第i-1i-1行的行链表上，行的行链表上，又处在第又处在第j-1j-1列的列链表上列的列链表上正交链表正交链表结点结点结构定义结构定义如下：如下：typedefstruc

39、tOLNodeintrow,col;/行号与列号ElemTypeval;/值structOLNode*right,*down;/指针域OLNode,*OLink;typedefstructOLink*rowhead,*colhead;/存放行、列链表的头指针的数组的首地址intrnum,cnum,len;/稀疏矩阵的行数、列数和非零元个数CrossList;voidCreateCross(CrossList*M)inti,j,m,n,t;intk,flag;cinmnt;/输入输入M的行数列数和非零元的行数列数和非零元素个数素个数M-rnum=m;M-cnum=n;M-len=t;/创建行链表

40、创建行链表头指针动态数组头指针动态数组M-rowhead=(OLink*)malloc(m*sizeof(OLink);/创建列链表创建列链表头指针动态数组头指针动态数组M-colhead=(OLink*)malloc(n*sizeof(OLink);for(k=0;krowheadk=NULL;for(k=0;kcolheadk=NULL;for(k=1;klen;k+)cout输入输入第第k个个结点行号、列号以及结点行号、列号以及值值“ije;p=(OLNode*)malloc(sizeof(OLNode);p-row=i;p-col=j;p-val=e;/生成结点生成结点if(NULL=

41、M-rowheadi)/p插在该行的第一个结点处插在该行的第一个结点处p-right=M-rowheadi;M-rowheadi=p;else/寻查在行表中的插入位置寻查在行表中的插入位置/从该行的行链表头开始，直到找到从该行的行链表头开始，直到找到for(q=M-rowheadi;q-right&q-right-colright);p-right=q-right;/完成完成行行结点结点插入插入q-right=p;if(NULL=M-colheadj)p-down=M-colheadj;M-colheadj=p;/p插在插在该列的该列的第一个结点处第一个结点处else/寻查在列表中的插入位置寻

42、查在列表中的插入位置/从该列的列链表头开始，直到找到从该列的列链表头开始，直到找到for(q=M-colheadj;q-down&q-down-rowdown);p-down=q-down;/完成列结点插入完成列结点插入q-down=p;本章小结本章小结本章基本学习要点如下：本章基本学习要点如下：(1)(1)理解矩阵和理解矩阵和一般线性表之间的差异。一般线性表之间的差异。(2)(2)掌握掌握各种特殊矩阵如对称矩阵、上、下三各种特殊矩阵如对称矩阵、上、下三角矩阵和对角矩阵的压缩存储方法。角矩阵和对角矩阵的压缩存储方法。(3)(3)掌握稀疏矩阵的各种存储结构以及基本运掌握稀疏矩阵的各种存储结构以及基本运算实现算法算实现算法。