资源描述
单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,2017/10/24,#,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,#,矩阵,是一个具有,m,行,n,列,的数据表，共,包含,有,m*n,个元素，每个,元素处在确定行和列的交点位置上，与,一对行号和列号,唯一对应,。,矩阵是很多科学与工程计算问题中研究的数学对象，,在用高级语言编程时，一般采用二维数组来存储矩阵。,矩阵,普通矩阵的完全存储,如果矩阵中的每个元素的值都是不能确定的值，那么存储这样的矩阵时，每个元素都必须存储，,即,需要,完全,存储。,用高级语言描述,时，,就是使用二,维数组的形式,存储矩阵。,有的矩阵中，,非零元素,非常少,-,稀疏矩阵,还,有一些,矩阵的元素分布有一定的规律,-,特殊矩阵（比如对称矩阵、三角矩阵）,特殊矩阵和稀疏矩阵,3,6,4,7,8,6,2,8,4,2,4,8,1,6,9,7,4,6,0,5,8,2,9,5,7,对称矩阵,3,c,c,c,c,6,2,c,c,c,4 8,1,c,c,7,4,6,0,c,8,2,9,5,7,三角矩阵,特殊矩阵,a,00,a,01,0,0,0,a,10,a,11,a,12,0,0,0,a,21,a,22,a,23,0,0 0,a,32,a,33,a,34,0,0,0,a,43,a,44,对角矩阵,特殊矩阵,15 0 0 0,21 0,0,0,0 0 0 0,0,1,0 6 0 0,0 0 0 0,5,0,9,0 0 0 0 0,稀疏矩阵,稀疏矩阵,对于特殊矩阵和稀疏矩阵,若,仍采用二维数,组形式存放,，将造成存储单元的很大浪费。,可以利用这些矩阵的特点和规律，只存储部分元素，从而提高存储空间的利用率。,矩阵的压缩存储,特殊,矩阵和稀疏矩阵的压缩存储,在对,特殊,矩阵,和,稀疏矩阵,进行,存储时，为了节省存储空间，可以对这类矩阵进行,压缩存储,。,压缩,存储,的基本思想是：,多,个值,相同,的元素只分配,一个,存储空间；, 对,零,元素,不分配,存储空间。,对称矩阵,的压缩存储,3,6478,6,2,842,48,1,69,746,0,5,8295,7,A,n,阶对称矩阵（,方阵,）特点,：,a,ij,=,a,ji,如何压缩存储？,只,存储下三角部分的,元素,或是,上三角部分的元素,，使得每两个对称元素共享一个存储空间。,压缩存储后节省了多少空间？,对于一个,n,阶对称矩阵，如果完全存储需要,n,2,个存储空间；,如果压缩存储，需要,n(n+1)/2,个存储空间。,对称矩阵,的压缩存储,3,6478,6,2,842,48,1,69,746,0,5,8295,7,A,定义一个一维数组,san(n+1)/2,作为,n,阶对称矩阵,A,的存储结构，那么对称矩阵,A,中任一元素,a,ij,和,sak,之间的,对应关系,如何？,对称矩阵,的压缩存储,(,a),下三角矩阵 (,b),存储说明 (,c),计算方法,a,ij,在一维数组中,的下标,=,阴影部分的,面积,=,i,(,i,+1,),/2+,j,0,i,n-1,0,j,n-1,a,ij,每行元素个数,1,2,i,a,ij,在本行中的序号,a,ij,第,0,行,第,1,行,第,i,-1,行,对称矩阵的压缩存储,对于下三角中的元素,a,ij,（,i,=,j,）,，,在一维数组,sa,中,的,下标,k,与,i,、,j,的关系为：,k,i,(,i,1)/2,j,上三角中的元素,a,ij,（,i,j,），,因为,a,ij,a,ji,，,则访问和它对应的元素,a,ji,即可，即：,k,j,(,j,1)/2,i,对称矩阵的压缩存储,第1行,第,n-1,行,第0行,a,00,a,10,a,11,a,20,a,21,a,22,a,ij,a,n-10,a,n-11,a,n-1n-1,第2行,0 1 2 3 4 5,k,n(n+1)/2-1,例：将压缩存储在一维数组,a,中的,4x4,阶,对称矩阵按矩阵格式输出。,int i,j;,for(i=0;i4;i+),for(j=0;j=j),coutai*(i+1)/2+j;,/*,输出主对角线以及主对角线以下元素,*/,else,cout,aj*(j+1,)/,2+i;,/*,输出主对角线以上元素,*/,coutendl;,三,角,矩阵,的压缩存储,3,c,c,c,c,6 2,c,c,c,4 81,c,c,7 46 0,c,8 29 5 7,(,a),下三角矩阵,3 4 8 1 0,c,2 9 4 6,c,c, 5 7,c,c,c,0 8,c,c,c,c,7,(,b),上三角矩阵,n,阶,上,（,下,）,三角矩阵,是指,下,（,上,）,三角,（不包括主对角线）中的元素均为常数,c,三,角,矩阵,的压缩存储,3,c,c,c,c,6 2,c,c,c,4 81,c,c,7 46 0,c,8 29 5 7,(,a),下三角矩阵,3 4 8 1 0,c,2 9 4 6,c,c, 5 7,c,c,c,0 8,c,c,c,c,7,(,b),上三角矩阵,如何压缩,存储三角矩阵？,可以只,存储上三角（或下三角）部分的,元素，对于常量,c,多开辟一个空间来存储。,下三角矩阵中任一元素,a,ij,在,一维,数组,中的下标,k,与,i,、,j,的对应关系：,i,(,i,1,),/2,j,当,i,j,n,(,n,1,),/2,当,i,j,k=,下三角矩阵的压缩存储,0 1 2 3 4 5,k,n(n+1,)/,2-1 n(n+1,)/,2,第1行,第0行,a,00,a,10,a,11,a,20,a,21,a,ij,a,n-1n-1,第2行,c,a,22,存储,下三角,元素,对角线上方的常数,只存一个,数据元素,san(n+1)/2,用于存放常量,c,矩阵中任一元素,a,ij,在,数组,中的下标,k,与,i,、,j,的对应关系：,i,(2n-i+1)/,2+j-i,当,i,j,n,(,n,1,),/2,当,i,j,k=,上三角矩阵的压缩存储,存储,上三角,元素,对角线上方的常数,只存一个,数据元素,san(n+1)/2,用于存放常量,c,对角矩阵,压缩存储,对角矩阵,：,n,阶对角矩阵是指,所有,非零元素都集中在以主对角线为中心的带状区域中，除了,主,对角线和它的上,下方若干条对角线,的元素外，所有其他元素都为零。,n,阶三对角矩阵：,n,阶三对角矩阵的非零元素仅出现在主对角线,(a,ii,0=i=n-1),上以及紧邻主对角线上面的那条对角线上（,a,ii+1,0=i=n-2),和紧邻主对角线下面的那条对角线上,（,a,i+1i,0,=i1,时，元素,a,ij,=0,元素,a,ij,与一,维数,组下标,k,的关系：,k,=2 + 3,(,i,1,),+,(,j,i,+,1,),=2,i,+,j,(,b),一维数组元素,sak,和矩阵元素,a,ij,的对应关系,(,c),压缩到一维数组中,a,00,a,01,a,10,a,11,a,12,a,21,a,22,a,23,a,32,a,33,a,34,a,43,a,44,0 1 2 3 4 5 6 7 8 9 10 11 12,三,对角矩阵,的压缩存储,(,a),三对角矩阵,0,0 0,0 0,0,0,0 0,0 0 0,A,=,a,00,a,01,a,10,a,11,a,12,a,21,a,22,a,23,a,32,a,33,a,34,a,43,a,44,稀疏矩阵,的压缩存储,15 0 0,0 0 0,0,0,0 0,11 0,0 0 0 6 0 0,0 0 0 0 0 0,9,0 0 0 0 0,A,=,若矩阵,A,mxn,中的非零元素个数非常少，且非零元素的分布没有任何规律，则称该矩阵为稀疏矩阵。,稀疏矩阵,的压缩存储,15 0 0,0 0 0,0 11,0 0 0 0,0 0 0 6 0 0,0 0 0 0 0 0,9,0 0 0 0 0,A,=,如何,只存储非零元素？,稀疏矩阵,中的非零元素的分布没有规律。,由于稀疏矩阵中非零元素的分布没有规律，因此在存储,非零元素的值,的同时，还必须记下该,非零元素,在矩阵中的,行号,和,列号,。,稀疏矩阵的压缩存储,定义三元组：,稀疏矩阵,中的每个非,零元素对应一个三元组,：,(,行号，列号，非零元素值,),三元组,三元组表,：,将稀疏矩阵,的所有非,零元素对应的三元组所构成的集合，,按行优先的顺序,排列成一,个,三元组线性表,。,三元组,表,：,(0,2,1),(1,1,2),(2,0,3),(3,3,5),(4,4,6),(5,5,7),(5,6,4),如何存储三元组表？,若把稀疏矩阵的,三元组线性表,按顺序存储结构存储,则称为稀疏矩阵的,三元组顺序表,。,示例,A,56,=,0,0,35,13,0,5,31,0,0,0,17,0,0,0,6,0,0,20,0,21,0,0,0,0,1,0,0,8,0,0,row col val,数组,b,m,0,35,2,0,1,13,3,0,2,5,5,0,3,31,0,1,4,17,4,1,5,6,2,2,6,20,5,2,7,21,1,3,8,1,0,4,9,8,3,4,行号：,0,到,4,列号：,0,到,5,该三元组线性表按,“,行序为主序,”，,用,一维数组进行存放,按,“列序为主序”的三元组线性表,typedef struct,/,三元组的类型定义,int row;,/,非零元素行,号,int,col;,/,非零元素列号,ElemType val;,/,非零元素值,tupletype,;,#define MAXSIZE 100;,typedef struct,/,三元组,顺序表存储结构定义,tupletype,dataMAXSIZE,;,/,非零元素的三元组表,int rnum;,/,矩阵行,数,int cnum;,/,矩阵,列数,int len;/,矩阵,总非,零元素个数,table,;,三元组顺序表存储结构定义,三元组,顺序表,采用顺序存储结构存储三元组表,0 0,15,0 3,22,0 5,-,15,1 1,11,1 2,3,2 3,6,4 0,91,空 空 空,闲 闲 闲,row col,e,0,1,2,3,4,5,6,MAXSIZE,-,1,15 0 0 22 0,-,15,0 11 3 0 0 0,0 0 0 6 0 0,0 0 0 0 0 0,91,0 0 0 0 0,A,=,5,（,矩阵的行,数）,6,（,矩阵的列数,）,7,（,非零元,个数,）,(1),从一,个稀疏矩阵,创建,其对应三元组表,以行序方式,扫描,二,维稀疏矩阵,A,将其非零的元素插入到,三元组顺序表,m,的,后面。算法如下,：,#define M1 6,#define N1 7,void,CreatTable(table *m,ElemType AM1N1),int i,j;,m-rnum=M1;m-cnum=N1;m-len=0,;,for (,i=0;iM1;i,+), for (,j=0;jdatam-len.row=i;,m-datam-len,.col=j,;,m-,datam-len,.val=Ai,j,;,m-len+;,(2),取值操作，从三元组表中取出稀疏矩阵指定,位置的元素,值,算法,思路：先,在,三元组,m,中,找到指定的位置,然后将,该处的元素值赋给,x,。,int,getvalue(table *m,ElemType *x,int i,int j), int k=0;,if,(i=m-rnum,|,j=m-cnum),return 0;,while (klen&,im-,datak.row,) k+;,/,找第,i,行,while (klen&,jm-,datak,.col,) k+;,/,找,第,j,列,if,(m-,datak.row,=i,&,m-,datak.col,=j),/,元素存在,*x=m-datak.val;,return 1; ,else return 0;,(3),稀疏矩阵,赋值，将给定值，赋值到三元组表的指定位置,算法,思路：先,在,三元组表,m,中找到指定的,位置,k,若指定位置已经有值，则用给定值替换原有值，否则，将指定位置,k,及其后面的元素,后移一位,然后将给定的元素值,x,插入,到指定位置处。,int,putValue(table *m,ElemType,x,int,i,int j), int i,k=0;,if,(i=,m-rnum | j,=,m-cnum) return 0;,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,.,row=i;,m-datak,.,col=j;,m-datak.val=x,;,m-len+;,return 1;,(4),按矩阵格式输出以三元组顺序表存储的稀疏矩阵,算法思路：对稀疏矩阵中的每个元素，从头到尾,扫描,三元组,m,若在三元组表中存在，则输出其元素值，否则输出,0,。,void,DispTable(table,*,m),int,i,j,k,e;,for,(i,=,0;i,rnum;i,+,), for,(j,=,0;j,cnum;j,+,),e,=,0;,for,(k,=,0;k,len;k,+,),if,(i,=,m,-,datak,.,row,&,j,=,m,-,datak,.,col),e,=,m,-,datak,.,val;,break,;,cout,e, ,;,cout,rnum=ta-cnum;,tb-cnum=ta-rnum;,tb-len=ta-len;,for (i=0;i,len;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),稀疏矩阵,A,mn,用三元组顺序表,ta,存储，实现对稀疏矩阵的转置,A,34,=,0,0,9,12,5,0,0,0,0,1,0,6,row col val,三元组顺序表,ta,0,9,2,0,1,12,3,0,2,5,0,1,3,1,1,2,4,2,3,6,B,43,=,0,5,0,0,0,1,9,0,0,12,0,6,row col val,三元组顺序表,tb,0,1,2,3,4,对,A,逐列转置,即：,逐行得到,B,对,ta,按照列号从,0,到,cnum-1,依次扫描,？,(5),稀疏矩阵转置,（逐,行得到,B）,void trans(table *ta,table *tb), int,k,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),稀疏矩阵,A,mn,用三元组顺序表,ta,存储，实现对稀疏矩阵的转置,算法思路,（,3）,：分段,定位,1）,预先处理阶段,(b),计算稀疏矩阵,A,每一列,中的,第一个非零元素,在三元组表,tb,中的正确位置（,即：,A,转置后,的矩阵,B,每,一行中的,第一,个非,零元素,在,三元组表,tb,中的正确位置,）,设置一个,数组,pot,来存放,这些位置。,例如：,potk,中存放的,是矩阵,A,中第,k,列中的,第一个非,零元素,在三元组表,tb,中的正确,位置,A,56,=,0,0,35,13,0,5,31,0,0,0,17,0,0,0,6,0,0,0,0,21,0,20,0,0,1,0,0,8,0,0,row col val,0,35,2,0,1,13,3,0,2,5,5,0,3,31,0,1,4,17,4,1,5,6,2,2,6,21,1,3,7,20,3,3,8,1,0,4,9,8,3,4,三元组顺序表,ta,1,、计算数组,num ,num,数组初值为,0；,将三元组表,ta,扫描一遍，对于其中列号为,k,的元素，给相应的,numk,加,1。,2,、计算数组,pot ,pot0=0;,potk=potk-1+numk-1;,/k=1,k,0,1,2,3,4,5,numk,2,1,2,3,1,1,potk,0,2,3,5,8,9,1）,预先处理阶段,预先,处理,阶段得到一个分段定位的结果,算法思路,（,3）,：分段,定位,2）,转置阶段,对三元组表,ta,进行扫描。,数组,pot ,中,的,值记录了矩阵,A,中每一列的,第一个非零元素在三元组表,tb,中的正确,位置。,每当,矩阵,A,中,第,k,列有一个非零元素存入到,三元组表,tb,时，将,potk,+，,即：,potk,始终存放,矩阵,A,第,k,列中的下一个非零元素的正确位置。,因此，通过,potk,可以得到三元组表,ta,中每个元素转置加入到,三元组表,tb,时的正确位置。,(5),稀疏矩阵转置,（,分段定位,）,void trans(table *ta,table *tb),int,k,q,i;,int numN,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;i,len;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、,行链表组,将稀疏矩阵,A,mn,每,一行,中非零元素对应,的结点构成一个链表，,m,个,行链表,形成一个链表,组,-,行链表,组,即：创建一个指针,数组，数组元素中存放,的就是,某,一行,链表,的,第一个结点的,地址，即该行链表的,头指针,。例如：,ahi,是第,i,个行,链表的,头指针,3、,稀疏矩阵的正交链表（十字链表）存储与实现,正交链表,存储思路是：为,稀疏矩阵的每,一行非零元素设置,一个单独链表,同时也为每一列非零元素设置一个单独链表。,这样,稀疏矩阵的每一个非零元素就同时包含在两个链表中,即：,每,一个非零元素同时,包含在,所在行的,行链表,中和所在列的,列链表,中,。,从而降低,了链表的,长度,，,也方便了行,方向和列方向的,搜索。,稀疏矩阵的三元组线性表的链式存储,采用,正交链表,存储结构来存储稀疏矩阵：,稀疏矩阵每个,非,零元素存储,为一个,链表,结点,结点,结构,为：,row,col,val,down,right,row：,存储非零元素的行号,col：,存储非零元素的列号,val：,存储非零元素的值,right：,指针域，指向同一行中,的下,一个非零元素结点,down,：,指针,域，指向同一列中的下一个非零元素结点,2 0,2,M=,3 0 0 5,0 1 0 0,2 0 0 0,0 0,3,0 3,5,1 1,1,稀疏矩阵的压缩存储,正交,链表,存储所有列链表的头指针的指针数组,存储所有行链表的头指针的指针数组,任一非零元素,Mij,所对应的结点，既处在第,i-1,行的行链表上，又处在第,j-1,列的列链表上,正交链表,结点,结构定义,如下：,typedef,struct,OLNode,int,row,col;,/,行号与列号,ElemType,val;,/,值,struct,OLNode*right,*down;,/,指针域,OLNode,*,OLink;,typedef,struct,OLink,*rowhead,*colhead,;,/,存放行、列链表的头指针的数组的首地址,int,rnum,cnum,len;,/,稀疏矩阵的行数、列数和非零元个数,CrossList;,void CreateCross(CrossList,*M),int,i, j, m, n, t;,int k, flag;,cinmnt;,/,输入,M,的行数列数和非零元素个数,M-,rnum,= m;,M-,cnum,= n;,M-,len,= t,;,/,创建行链表,头指针动态数组,M-rowhead,= (OLink *),malloc(m*,sizeof(OLink);,/,创建列链表,头指针动态数组,M-,colhead,= (OLink *),malloc(n*,sizeof(OLink);,for(k=0;k,rowhead,k,=NULL;,for(k=0;k,colheadk,=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=M-,rowheadi),/ p,插在该行的第一个结点处,p-right=M-,rowheadi,; M-rowheadi = p; ,else,/,寻查在行表中的插入位置,/,从该行的行链表头开始，直到找到,for(q=M-,row,headi,; q-right & q-right-,col,right),;,p-,right=q-right;,/,完成,行,结点,插入,q-right=p;,if(NULL=M-,colheadj),p-down=M-,colheadj,; M-colheadj, = p;,/ p,插在,该列的,第一个结点处,else,/,寻查在列表中的插入位置,/,从该列的列链表头开始，直到找到,for(q=M-,colheadj,; q-down & q-down-,row,down),;,p-down=q-down;,/,完成列结点插入,q-down=p;,本章小结,本章基本学习要点如下：,(1),理解矩阵和,一般线性表之间的差异。,(2),掌握,各种特殊矩阵如对称矩阵、上、下三角矩阵和对角矩阵的压缩存储方法。,(3),掌握稀疏矩阵的各种存储结构以及基本运算实现算法,。,
展开阅读全文