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

矩阵是一个具有m行n列的数据表，共包含有m*n个元素，每个元素处在确定行和列的交点位置上，与一对行号和列号唯一对应。矩阵是很多科学与工程计算问题中研究的数学对象，在用高级语言编程时，一般采用二维数组来存储矩阵。,矩阵,普通矩阵的完全存储,如果矩阵中的每个元素的值都是不能确定的值，那么存储这样的矩阵时，每个元素都必须存储，即需要完全存储。用高级语言描述时，就是使用二维数组的形式存储矩阵。,有的矩阵中，非零元素非常少-稀疏矩阵还有一些矩阵的元素分布有一定的规律-特殊矩阵（比如对称矩阵、三角矩阵）,特殊矩阵和稀疏矩阵,对称矩阵,三角矩阵,特殊矩阵,对角矩阵,特殊矩阵,稀疏矩阵,稀疏矩阵,对于特殊矩阵和稀疏矩阵若仍采用二维数组形式存放，将造成存储单元的很大浪费。可以利用这些矩阵的特点和规律，只存储部分元素，从而提高存储空间的利用率。,矩阵的压缩存储,特殊矩阵和稀疏矩阵的压缩存储,在对特殊矩阵和稀疏矩阵进行存储时，为了节省存储空间，可以对这类矩阵进行压缩存储。压缩存储的基本思想是：多个值相同的元素只分配一个存储空间；对零元素不分配存储空间。,对称矩阵的压缩存储,3647862842481697460582957,A,n阶对称矩阵（方阵）特点：aij=aji,如何压缩存储？,只存储下三角部分的元素或是上三角部分的元素，使得每两个对称元素共享一个存储空间。,压缩存储后节省了多少空间？,对于一个n阶对称矩阵，如果完全存储需要n2个存储空间；如果压缩存储，需要n(n+1)/2个存储空间。,对称矩阵的压缩存储,3647862842481697460582957,A,定义一个一维数组san(n+1)/2作为n阶对称矩阵A的存储结构，那么对称矩阵A中任一元素aij和sak之间的对应关系如何？,对称矩阵的压缩存储,(a)下三角矩阵(b)存储说明(c)计算方法,aij在一维数组中的下标=阴影部分的面积=i(i+1)/2+j,0in-1,0jn-1,aij,对称矩阵的压缩存储,对于下三角中的元素aij（i=j），在一维数组sa中的下标k与i、j的关系为：ki(i1)/2j上三角中的元素aij（ij），因为aijaji，则访问和它对应的元素aji即可，即：kj(j1)/2i,对称矩阵的压缩存储,例：将压缩存储在一维数组a中的4x4阶对称矩阵按矩阵格式输出。,inti,j;for(i=0;i=j)coutai*(i+1)/2+j;/*输出主对角线以及主对角线以下元素*/elsecoutaj*(j+1)/2+i;/*输出主对角线以上元素*/coutendl;,三角矩阵的压缩存储,3cccc62ccc481cc7460c82957,(a)下三角矩阵,34810c2946cc57ccc08cccc7,(b)上三角矩阵,n阶上（下）三角矩阵是指下（上）三角（不包括主对角线）中的元素均为常数c,三角矩阵的压缩存储,3cccc62ccc481cc7460c82957,(a)下三角矩阵,34810c2946cc57ccc08cccc7,(b)上三角矩阵,如何压缩存储三角矩阵？,可以只存储上三角（或下三角）部分的元素，对于常量c多开辟一个空间来存储。,下三角矩阵中任一元素aij在一维数组中的下标k与i、j的对应关系：,下三角矩阵的压缩存储,数据元素san(n+1)/2用于存放常量c,矩阵中任一元素aij在数组中的下标k与i、j的对应关系：,上三角矩阵的压缩存储,数据元素san(n+1)/2用于存放常量c,对角矩阵压缩存储,对角矩阵：n阶对角矩阵是指所有非零元素都集中在以主对角线为中心的带状区域中，除了主对角线和它的上下方若干条对角线的元素外，所有其他元素都为零。,n阶三对角矩阵：n阶三对角矩阵的非零元素仅出现在主对角线(aii,0=i=n-1)上以及紧邻主对角线上面的那条对角线上（aii+1,0=i=n-2)和紧邻主对角线下面的那条对角线上（ai+1i,0rnum=M1;m-cnum=N1;m-len=0;for(i=0;idatam-len.row=i;m-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,(3)稀疏矩阵赋值，将给定值，赋值到三元组表的指定位置算法思路：先在三元组表m中找到指定的位置k,若指定位置已经有值，则用给定值替换原有值，否则，将指定位置k及其后面的元素后移一位,然后将给定的元素值x插入到指定位置处。intputValue(table*m,ElemTypex,inti,intj)inti,k=0;if(i=m-rnum|j=m-cnum)return0;while(klen/用给定值x替换原值,else/*元素不存在时，将其插入*/for(i=m-len-1;i=k;i-)/*元素后移*/m-datai+1=m-datai;m-datak.row=i;m-datak.col=j;m-datak.val=x;m-len+;return1;,(4)按矩阵格式输出以三元组顺序表存储的稀疏矩阵算法思路：对稀疏矩阵中的每个元素，从头到尾扫描三元组m,若在三元组表中存在，则输出其元素值，否则输出0。voidDispTable(table*m)inti,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,(5)矩阵转置对于一个mn的稀疏矩阵Amn,其转置矩阵是一个nm的稀疏矩阵Bnm。,矩阵正常存储时，转置的一般算法？,(5)稀疏矩阵Amn用三元组顺序表ta存储，实现对稀疏矩阵的转置算法思路（1）：显然，稀疏矩阵的转置依旧是稀疏矩阵。稀疏矩阵Bnm是稀疏矩阵Amn的转置矩阵,假设使用三元组表ta存储稀疏矩阵A，如何得到存储稀疏矩阵B的三元组表tb简单方法是：将存储存储稀疏矩阵Amn的三元组表ta的行列号互换就可以得到转置后的三元组表tb,rowcolval,三元组顺序表ta,rowcolval,三元组顺序表tb,三元组表ta的行列号互换,(5)稀疏矩阵转置(互换行列号）voidtrans(table*ta,table*tb)inti;tb-rnum=ta-cnum;tb-cnum=ta-rnum;tb-len=ta-len;for(i=0;ilen;i+)tb-datai.row=ta-datai.col;tb-datai.col=ta-datai.row;tb-datai.val=ta-datai.val;,算法缺点：无法保证三元组表tb也是以“行序为主序”进行存放,算法思路（2）：为了保证三元组表tb也是以“行序为主序”进行存放，按照三元组ta的列序（即转置后三元组表tb的行序）进行转置。即将稀疏矩阵A，按照列序将每列中的非零元素，转置后依次送入三元组表tb中存储，这样得到的三元组表tb恰好是以“行序为主序”。具体过程：第一次扫描三元组表ta时，逐个找出所有列号为0的三元组，转置后按顺序送入三元组表tb中；同理，第二遍扫描三元组表ta,逐个找出所有列号为1的三元组，转置后按顺序送入三元组表tb中；反复进行，将所有列号都进行一遍。最后一遍扫描三元组表tb,逐个找出所有列号为cunm-1的三元组，转置后按顺序送入三元组表tb中。,(5)稀疏矩阵Amn用三元组顺序表ta存储，实现对稀疏矩阵的转置,rowcolval,三元组顺序表ta,rowcolval,三元组顺序表tb,对A逐列转置即：逐行得到B,对ta按照列号从0到cnum-1依次扫描？,(5)稀疏矩阵转置（逐行得到B）voidtrans(table*ta,table*tb)intk,b,q;tb-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列矩阵中时,其转置算法的时间复杂度为O(m*n)当非零元素个数较小时，O(ta-cnum*ta-len)优于O(m*n),算法思路（3）：分段定位总体思路：转置时，对三元组表ta中的三元组依次进行转置，转置后的三元组直接放到对应稀疏矩阵B的三元组表tb中的分段位置上。为了能将待转置的三元组表ta中的元素一次定位到三元组表tb的正确位置，需要预先对三元组表tb进行分段定位。1）预先处理阶段(a)计算稀疏矩阵A每一列中非零元素的个数（即：A转置后的稀疏矩阵B每一行中非零元素的个数）设置一个数组num来存放这些数。例如：numk中存放的是矩阵A中第k列的非零元素的个数（即：矩阵B中第k行的非零元素的个数）,(5)稀疏矩阵Amn用三元组顺序表ta存储，实现对稀疏矩阵的转置,算法思路（3）：分段定位1）预先处理阶段(b)计算稀疏矩阵A每一列中的第一个非零元素在三元组表tb中的正确位置（即：A转置后的矩阵B每一行中的第一个非零元素在三元组表tb中的正确位置）设置一个数组pot来存放这些位置。例如：potk中存放的是矩阵A中第k列中的第一个非零元素在三元组表tb中的正确位置,三元组顺序表ta,1、计算数组num,num数组初值为0；将三元组表ta扫描一遍，对于其中列号为k的元素，给相应的numk加1。,2、计算数组pot,pot0=0;potk=potk-1+numk-1;/k=1,1）预先处理阶段,预先处理阶段得到一个分段定位的结果,算法思路（3）：分段定位2）转置阶段对三元组表ta进行扫描。数组pot中的值记录了矩阵A中每一列的第一个非零元素在三元组表tb中的正确位置。每当矩阵A中第k列有一个非零元素存入到三元组表tb时，将potk+，即：potk始终存放矩阵A第k列中的下一个非零元素的正确位置。因此，通过potk可以得到三元组表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加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本行上下一个非零元素的位置*/,以上算法的时间主要耗费在四个并列的单循环上，这四个并列的单循环分别循环了：ta-cnum、ta-len、ta-cnum、ta-len次，因此总的时间复杂度为：O(ta-cnum+ta-len),除了顺序存储，也可以把稀疏矩阵按链式存储结构进行压缩存储。,稀疏矩阵的三元组线性表的链式存储,1、简单链式存储,稀疏矩阵A的每个非0元素对应一个结点，结点含有的域为:row(行号)、col(列号),val(元素值),next(链域)。将所有的结点串成一个链表。,稀疏矩阵简单链式存储示例,稀疏矩阵的三元组线性表的链式存储,2、行链表组,将稀疏矩阵Amn每一行中非零元素对应的结点构成一个链表，m个行链表形成一个链表组-行链表组即：创建一个指针数组，数组元素中存放的就是某一行链表的第一个结点的地址，即该行链表的头指针。例如：ahi是第i个行链表的头指针,3、稀疏矩阵的正交链表（十字链表）存储与实现正交链表存储思路是：为稀疏矩阵的每一行非零元素设置一个单独链表,同时也为每一列非零元素设置一个单独链表。这样稀疏矩阵的每一个非零元素就同时包含在两个链表中,即：每一个非零元素同时包含在所在行的行链表中和所在列的列链表中。从而降低了链表的长度，也方便了行方向和列方向的搜索。,稀疏矩阵的三元组线性表的链式存储,采用正交链表存储结构来存储稀疏矩阵：稀疏矩阵每个非零元素存储为一个链表结点结点结构为：,row：存储非零元素的行号col：存储非零元素的列号val：存储非零元素的值right：指针域，指向同一行中的下一个非零元素结点down：指针域，指向同一列中的下一个非零元素结点,稀疏矩阵的压缩存储正交链表,存储所有列链表的头指针的指针数组,存储所有行链表的头指针的指针数组,任一非零元素Mij所对应的结点，既处在第i-1行的行链表上，又处在第j-1列的列链表上,正交链表结点结构定义如下：typedefstructOLNodeintrow,col;/行号与列号ElemTypeval;/值structOLNode*right,*down;/指针域OLNode,*OLink;,typedefstructOLink*rowhead,*colhead;/存放行、列链表的头指针的数组的首地址intrnum,cnum,len;/稀疏矩阵的行数、列数和非零元个数CrossList;,voidCreateCross(CrossList*M)int