第四章数组和矩阵

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,第四章 数组和矩阵,-,蒋菲菲,主 要 内 容,1,、,数组的定义,2,、,数组的顺序存储和实现,3,、,特殊矩阵的压缩存储,1,）,三角矩阵,2,）,稀疏矩阵,数组的定义,从逻辑结构上看，,数组可以看成是一般线性表的扩充。,二维数组可以看成是,“其数据元素是一维数组（线性表）”,的线性表。,以二维数组为例：,二维数组中的每个元素都受两个线性关系的约束即行关系和列关系，在每个关系中，每个元素,aij,都有且仅有一个直接前趋，都有且仅有一个直接后继。,在行关系中,a ij,直接前趋是,aij-1,a ij,直接后继是,aij+1,在列关系中,a ij,直接前趋是,ai-1j,a ij,直接后继是,ai+1j,数组的特性,二维数组可看成一个线性表A=(a,0,，a,1,，a,p,) (p=m-1或n-1)，其中a,j,是一个,列向量,形式的线性表：,a,j,=（a,0j,，a,1j,，a,m-1,j,）， 0jn-1,或a,i,是一个行向量形式的线性表：,a,i,=（a,i0,，a,i1,，a,i,n-1,）， 0im-1,a,00,a,01,a,0,n-1,a,10,a,11,a,1,n-1,a,m-1,0,a,m-1,1,a,m-1,n-1,a,00,a,01, a,0,n-1,a,10,a,11, a,1,n-1, ,a,m-1,0,a,m-1,1, a,m-1,n-1,a,0,a,1,a,p,a,0,a,1,a,p,数组的顺序存储和实现,实际上,数组是一组有固定个数的元素的集合,。也就是说，,一旦定义了数组的维数和每一维的上下限，数组中元素的的个数就固定了,。例如二维数组A34，它有3行，4列，即由12个元素组成。由于这个性质，使得对数组的操作不象对线性表的操作那样，,不,可以在表中任意一个合法的位置插入或删除一个元素,对于数组的操作一般只有两类：,1）,获得特定位置的元素值,；,2）,修改特定位置的元素值,。,一维数组在内存中的存放很简单，只要顺序存放在连续的内存单元即可。,二维数组，如何用顺序结构表示？内存地址是一维的，而数组是二维的，要将二维数组挤入一维的地址中，有两个策略：,以行为主序（,C,语言使用）,以列为主序,a,00,a,01,a,0n-1,a,10,a,11,a,1n-1,a,m-10,a,m-11,a,m-1n-1,a,00,a,01, a,0,n-1,a,10,a,11, a,1,n-1, ,a,m-1,0,a,m-1,1, a,m-1,n-1,a,m-1,n-1,a,m-1,1,a,m-1,0,a,1,n-1,a,11,a,10,a,0,n-1,a,01,a,00,a,m-1,n-1,a,1,n-1,a,0,n-1,a,m-1,1,a,11,a,01,a,m-1,0,a,10,a,00,a,00,a,01,a,0,n-1,a,10,a,11,a,1,n-1,a,m-1,0,a,m-1,1,a,m-1,n-1,行,优,先,顺,序,列,优,先,顺,序,数组的顺序表示与实现,对于数组A，一旦给定其维数n及各维长度bi（1in），则该数组中元素的个数是固定的，不可以对数组做插入和删除操作，不涉及移动元素操作，因此对于数组而言，采用,顺序存储法,比较合适。,以二维数组Amn为例，假设每个元素只占一个存储单元，,“以行为主”,存放数组，,下标从1开始,，首元素a11的地址为Loc1,1，求任意元素aij的地址。aij是排在第i，第j列，并且前面的第i-1行有n*（i-1）个元素，第行第j个前面还有个元素。由此得到如下地址计算公式：,Loci,j=Loc1,1+n(i-1)+(j-1),以列为主：,Loci,j=Loc1,1+,m,(,j,-1)+(,i,-1),例,2,：,已知二维数组,A,m,m,按行存储的元素地址公式是：,Loc(a,ij,)= Loc(a,11,)+(i-1)*m+(j-1)*K ,按列存储的公式是？,Loc(a,ij,)=Loc(a,11,)+(,j,-1)*m+(,i,-1)*K,（尽管是方阵，但公式仍不同）,例,1,：,一个二维数组,A,，行下标的范围是,1,到,6,，列下标的范围是,0,到,7,，每个数组元素用相邻的,6,个字节存储，存储器按字节编址。那么，这个数组的体积是,个字节。,288,例3：,设数组a60,70的,首,地址为2048，每个元素占2个存储单元，若以,列序为主序顺序存储，则元素a32,58的存储地址为,。,8950,LOC,(a,ij,)=LOC(a,c,1,，,c,2,)+(,j-c,2,)*(,d,1,-c,1,+1)+,i-c,1,)*L,得：,LOC(,a,32,58,)=2048+(58-1)*(60-1+1)+32-1)*2,8950,答：请注意审题！,利用列优先通式：,答：,Volume=m*n*L=(6-1,+1,)*(7- 0,+1,)*6=48*6=288,特殊矩阵的压缩存储,有些高阶矩阵中，非零元素非常少（远小于,mn,），此时若仍采用二维数组顺序存放就不合适了，因为,很多存储空间存储的都是,0,，,只有很少的一些空间存放的是有效数据，这将造成,存储单元很大的浪费,。另外，还有一些,矩阵其元素的分布有一定规律,，我们可以利用这些规律，只存储部分元素，从而提高存储空间的利用率。上述矩阵叫做特殊矩阵。,为了节省空间，对这类矩阵进行压缩存储,压缩原则是：,对有规律的元素和值相同的元素只分配一个存储空间，对于零元素不分配空间。,1,、三角矩阵,三角矩阵大体分为三类,对于一个,n,阶矩阵,A,来说：,下三角矩阵,：,当,ij,时，有,aij=C,(,典型,C=0),对称矩阵,：,矩阵中的所有元素均满足,aij=aji,下三角矩阵,对于,下三角矩阵的压缩存储，我们只存储下三角的非零元素，对于零元素则不存。我们按“行序为主序”进行存储,，得到的序列是,a11,a21,a22,a31,a32,a33an1,an2ann,。由于下三角矩阵的元素个数为,n(n+1)/2,：,第,1,行：,1,个,第,2,行：,2,个,第,3,行：,3,个,第,n,行：,n,个,1+2+3+n=n(n+1)/2,下三角矩阵的压缩形式：,a,11,a,21,a,22,a,31,a,32,a,33,a,nn,1,2 3,4,5 6,n(n+1)/2,下三角矩阵中元素,aij(ij),，在一维数组,A,中的位置为：,Loc i ,j=,Loc1,1,+,前,i-1,行非零元素个数,+,第,i,行中,aij,前非零元素个数,前,i-1,行元素个数,=1+2+3+4+ +,（,i-1,）,= i (i -1)/2,，,第,i,行中,aij,前非零元素个数,=j-1,，所以有：,LOC i ,j= LOC1,1+ i (i -1)/2+ j-1,同样，,对于上三角矩阵,，也可以将其压缩存储到一个大小为,n(n+1)/2,的一维数组,C,中。其中元素,aij(i1时，元素a,ij,=0。,K=0 1 2 3 4 5 3n-2 3n-,1,数组a中的元素k与三对角带状矩阵中的元素a,ij,存在,一一对应关系,，在a,ij,之前有i,-1,行,共有3*,(,i,-1),-1个非零元素，在第i行，有j-i+1个非零元素，这样，非零元素a,ij,的地址为：,LOC(i,j)=LOC(,1,1,)+3*,(,i,-1),-1+(j-i+1)*d,=LOC(,1,1,)+(2i+j,-3,)*d,稀疏矩阵,1,什么是稀疏矩阵,有较多值相同元素或较多零元素，,且值相同元素或者零元素分布没有一定规律的矩阵称为稀疏矩阵。,例,A,=,0,12 9,0 0 0 0,0 0 0 0 0 0 0,-3,0 0 0 0,14,0,0 0,24,0 0 0 0,0,18,0 0 0 0 0,15,0 0,-7,0 0 0,A,有,42,（,6,7,）个元素,有,8,个非零元素,如何进行稀疏矩阵的,压缩存储？,2,、,稀疏矩阵的压缩存储,对于稀疏矩阵的压缩存储，我们采取,只存储非零元素的方法,。但由于稀疏矩阵中非零元素,aij,的分布一般是,没有规律,的，因此，对于稀疏矩阵的压缩存储就要求在,存储非零元素的同时，还必须存储一些辅助信息,，即该非零元素在矩阵中所处的,行号和列号,。我们将这种存储方法叫做稀疏矩阵的,三元组表示法,把这些三元组按,“行序为主序”,用一维数组进行存放，即将,j,矩阵的,任何一行的全部非零元素的三元组按列号递增存放,。由此得到矩阵,M,，,N,的三元组表，,2,稀疏矩阵的压缩存储（只讨论有较多零元素矩阵的压缩存储）,1,）三元组表,（,i, j, a,ij,),A=( (0,1,12), (0,2,9), (2,0,-3),(2,5,14),(3,2,24), (4,1,18), (5,0,15), (5,3,-7) ),加上行、列数,6,，,7,A,=,0,12 9,0 0 0 0,0 0 0 0 0 0 0,-3,0 0 0 0,14,0,0 0,24,0 0 0 0,0,18,0 0 0 0 0,15,0 0,-7,0 0 0,表示非零元的,三元组,2,）三元组顺序表,假设以顺序存储结构来表示三元组表，则可得稀疏矩阵的一种压缩存储方式,我们称之为三元组顺序表。,三元组线性表结点的类型定义,#define elemtype int,#define MAXSIZE 100 /*,非零元素的个数最多为,100*/,typedef struct node,int row, col; /*,该非零元素的行下标和列下标*,/,elemtype e,；,/*,该非零元素的值*,/,xnode;,顺序存储的稀疏矩阵用,C,语言定义：,typedef struct matrix,xnode dataMAXSIZE; /*,非零元素的三元组表*,/,int m, n, len; /*,矩阵的行数、列数和非零元素的个数*,/,smatrix,；,用于存储非零元,三元组的结构,A,的三元组顺序表,图示,A,=,0,12 9,0 0 0 0,0 0 0 0 0 0 0,-3,0 0 0 0,14,0,0 0,24,0 0 0 0,0,18,0 0 0 0 0,15,0 0,-7,0 0 0,例如,ma1.row=0, ma1.col=1, ma1.value=12,row col value,0,1,2,3,4,5,6,7,8,2 0 -3,5 0 15,0 1 12,4 1 18,0 2 9,3 2 24,5 3 -7,2 5 14,6 7 8,3 ),转置运算算法,转置运算是一种最常用的矩阵运算。对于一个,m,行,n,列的矩阵,A,，它的转置矩阵,B,是一个,n,行,m,列的矩阵。例如，下图中的矩阵,A,和,B,互为转置矩阵,。,A,=,0,12 9,0 0 0 0,0 0 0 0 0 0 0,-3,0 0 0 0,14,0,0 0,24,0 0 0 0,0,18,0 0 0 0 0,15,0 0,-7,0 0 0,B,=,0 0,-3,0 0,15,12,0 0 0,18,0,9,0 0,24,0 0,0 0 0 0 0,-7,0 0 0 0 0 0,0 0,14,0 0 0,0 0 0 0 0 0,A,第,0,列,第一列,第二列,第三列,第四列,第五列,第六列,.,B,第,0,行,第一行,第二行,第三行,第四行,第五行,第六行,.,转置运算算法,矩阵,B,矩阵,A,分析：,（,1,）将矩阵的行列数的值交换,（,2,）将每一个三元组的,i,和,j,相互调换,（,3,）重排三元组之间的次序,row col value,0,1,2,3,4,5,6,7,8,2 0 -3,5 0 15,0 1 12,4 1 18,0 2 9,3 2 24,5 3 -7,2 5 14,6 7 8,row colv alue,0,1,2,3,4,5,6,7,8,1 0 12,3 5 -7,0 2 -3,2 3 24,0 5 15,2 0 9,5 2 14,1 4 18,7 6 8,转置运算算法,按照,A,的列序来进行转换的基本思想,对,a ,从头至尾扫描：,第一次扫描时，将,a ,中列号为,0,的所有元组交换行列值后，依次赋值到,b ,中,第二次扫描时，将,ma ,中列号为,1,的所有元组交换行列值后，依次赋值到,mb ,中,依此类推，直至将,ma ,的所有三元组赋值到,mb ,中,i j v,0 1 12,0 2 9,2 0 -3,2 5 14,3 2 24,4 1 18,5 0 15,5 3 -7,i j v,2 0 -3,1 4 18,0 2 -3,5 0 15,0 5 15,0 1 12,1 0 12,4 1 18,0 2 9,2 0 9,3 2 24,2 3 24,5 3 -7,3 5 -7,2 5 14,5 2 14,A,矩阵,B,矩阵,对,A,六次扫描完成转置运算,第一次扫描查找第,0,列元素,第一次扫描结束,第二次扫描结束,第二次扫描查找第,1,列元素,第三次扫描查找第,2,列元素,第四次扫描查找第,3,列元素,第五次扫描查找第,4,列元素,第六次扫描查找第,5,列元素,转置运算算法图示,0,1,2,3,4,5,6,7,8,6 7 8,7 6 8,int transpose(smatrix a),/*a,转置为,b*/, smatrix b; int cols,m,k,n=0;,if(a.term=0)return(0);,b.row=a.col; b.col=a.row; b.term=a.term;,for(cols=0;colsa.col;cols+),/*,按列号扫描*,/,for(m=0;ma.term;m+),/*,对三元组扫描*,/,if(a.datam.j=cols),/*,进行转置*,/, b.datan.i=a.datam.j;,b.datan.j=a.datam.i;,b.datan.e=a.datam.e;,n+; ,printf(n,转置后的矩阵为,:n);,for(k=0;ka.term;k+),printf(%5d%5d%5dn,b.datak.i,b.datak.j,b.datak.e); ,void main(), int s; smatrix a;,printf(n,请输入,a,得行数、列数以及非零的个数,:n);,scanf(%d%d%d,printf(n,请输入转置前的三元组,:n);,for(s=0;sa.term;s+),scanf(%d%d%d,transpose(a); ,时间复杂度分析,算法的基本操作为将,a,中的,三元组赋值到,b,，是,在两个循环中完成的，故算法的时间复杂度为,O(n,t,),其中,n,为,A,矩阵的列数,t,为非,0,元素个数,。,当非零元的个数,t,和矩阵元素个数,m,n,同数量级时，即,t m,n,，转置运算算法的时间复杂度为,O,（,m,n,）,。,由此可见：在这种情况下，用,三元组顺序表存储矩阵，虽然可能节省了存储空间，但时间复杂度提高了，因此算法仅适于,t,m,n,的情况。,该算法效率不高的原因是：对为实现,A,到,B,的转置，该,算法,对,a,进行了多次扫描。其特点是：以,B,矩阵的三元组为中心，在,A,矩阵的三元组中通盘查找合适的结点置入,bk,中,经典算法,Void transport(enm,elemtype destmn),int I,j;,for(i=o;im;i+),for(j=0;jn;j+),destij=sourceji;,二、稀疏矩阵的链式存储结构,-,十字链表,用三元组表法表示的稀疏矩阵，比起用二维数组存储，,节约了空间,.,但是，在进行矩阵加法、减法和乘法等运算时，有时矩阵中的,非零元素的位置和个数会发生很大的变化,如,A=A+B,，将矩阵,B,加到矩阵,A,上，此时，若还用三元组的表示法，势必会为了保持三元组表“以行序为主序”，而大量移动元素。为了避免大量移动元素，这一节我们介绍稀疏矩阵的链式存储法,-,十字链表，它能够灵活地插入因运算而产生的新的非零元素、删除因运算而产生的新的零元素，实现矩阵的各种运算,十字链表的存储结构,结点的数据结构如下：,struct node, int row, col, val;,struct node *down, *right;,;,typedef struct node NODE;,row col val,down right,例如矩阵,A,=,3 2,0,5,0,-1,0 0,2,0 0 0,0 0 0 0,4 4 5,0 0 0,0 0 0,0 0 0,0 0 0,0 3 5,0 1 2,0 0 3,0 0 0,0 0 0,0 0 0,0 0 0,2 0 2,1 1 -1,head,1 0 22,22,1 0 22,小 结,1,矩阵压缩存储是指为多个值相同的元素分配一个,存储空间，对零元素不分配存储空间；,2,特殊矩阵的压缩存储是根据元素的分布规律，确定,元素的存储位置与元素在矩阵中的位置的对应关系；,3,稀疏矩阵的压缩存储除了要保存非零元素的值外，还,要保存非零元素在矩阵中的位置；,