第5章数组和广义表

,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,第5章 数组,数组可以看成是一种特殊的线性表，即线性表中数据元素本身也是一个线性表。,5.1 数组的定义和特点,定义,数组特点,数组结构固定,数据元素同构,数组运算,给定一组下标，存取相应的数据元素,给定一组下标，修改数据元素的值,(),(),(),(),(),(),(),(),(),5.2 数组的顺序表示和实现,次序约定,以行序为主序,以列序为主序,a,11,a,12,.a,1n,a,21,a,22,.a,2n,a,m1,a,m2,.a,mn,.,Loc(a,ij,)=Loc(a,11,)+(i-1)*n+j-1*l,按行序为主序存放,a,mn,.,a,m2,a,m1,.,a,2n,.,a,22,a,21,a,1n,.,a,12,a,11,0,1,n-1,m*n-1,n,按列序为主序存放,0,1,m-1,m*n-1,m,a,mn,.,a,2n,a,1n,.,a,m2,.,a,22,a,12,a,m1,.,a,21,a,11,a,11,a,12,.,a,1n,a,21,a,22,.,a,2n,a,m1,a,m2,.,a,mn,.,Loc(aij)=Loc(,a11,)+(j-1)*m+i-1)*l,5.3 矩阵的压缩存储,矩阵是很多科学与工程计算问题中研究的数学对象,本节讨论如何存储矩阵的元,从而对矩阵进行各种有效运算；对一些特殊矩阵我们可以用很少的空间来存储以到达压缩的目的。,5.3.1 特殊矩阵,对称矩阵相同元素取一次，实现了压缩,a,11,a,12,.,.,a,1n,a,21,a,22,.,a,2n,a,n1,a,n2,.,a,nn,.,a,11,a,21,a,22,a,31,a,32,a,n1,a,nn,.,.,k=0 1 2 3 4 n(n-1)/2 n(n+1)/2-1,按行序为主序：,三角矩阵,a,11,0 0,.,0,a,21,a,22,0,.,0,a,n1,a,n2,a,n3,.,a,nn,.,0,Loc(aij)=Loc(,a,11,)+(+(j-1)*l,i(i-1),2,a,11,a,21,a,22,a,31,a,32,a,n1,a,nn,.,.,k=0 1 2 3 4 n(n-1)/2 n(n+1)/2-1,按行序为主序：,对角矩阵,a,11,a,12,0,.,0,a,21,a,22,a,23,0,0,0,0,a,n-1,n-2,a,n-1,n-1,a,n-1,n,0,0,a,n,n-1,a,nn.,0,a,32,a,33,a,34,0,0,Loc(aij)=Loc(,a,11,)+2(i-1)+(j-1),a,11,a,12,a,21,a,22,a,23,a,nn-1,a,nn,.,.,k=0 1 2 3 4 n(n-1)/2 n(n+1)/2-1,按行序为主序：,M由(1,2,12),(1,3,9),(3,1,-3),(3,6,14),(4,3,24),(5,2,18),(6,1,15),(6,4,-7)和矩阵维数6,7唯一确定,5.3.2 稀疏矩阵,定义：非零元较零元少，且分布没有一定规律的矩阵,压缩存储原那么：只存矩阵的行列维数和每个非零元的行列下标及其值,稀疏程度的计算：,稀疏矩阵的压缩存储方法,顺序存储结构,三元组表,#define M 20,typedef struct node,int i,j;,int v;,JD;,JD maM;,三元组表所需存储单元个数为3(t+1),其中t为非零元个数,利用三元组表求稀疏矩阵的转置1,P9899,6,7,8,1 2 12,1 3 9,3 1 -3,3 6 14,4 3 24,5 2 18,6 1 15,6 4 -7,ma,i j v,0 1 2 3 4 5 6 7 8,ma0.i,ma0.j,ma0.v,分别存放,矩阵行列维数和非零元个数,行列下标,非零元值,带辅助行向量的二元组,增加一个辅助数组NRAm+1,其物理意义是第i行第一个非零元,在二元组表中的起始地址m为行数,显然有：,NRA1=1,NRAi=NRAi-1+第i-1,行非零元个数(i,2),0 1 2 3 4 5 6,NRA,1,3,3,5,6,7,6,7,8,2 12,3 9,1 -3,6 14,3 24,2 18,1 15,4 -7,ma,j v,0 1 2 3 4 5 6 7 8,矩阵列数和,非零元个数,列下标和,非零元值,NRA0,不用或,存矩阵行数,二元组表需存储单元个数为2(t+1)+m+1,伪地址表示法,伪地址：本元素在矩阵中包括零元素在内,按行优先顺序的相对位置如-3,按行优先顺序为15,6,7,2 12,3 9,15 -3,20 14,24 24,30 18,36 15,39 -7,ma,addr v,伪地址,非零元值,矩阵行列维数,0 1 2 3 4 5 6 7 8,伪地址表示法需存储单元个数,为2(t+1),求转置矩阵 P98,问题描述：一个稀疏矩阵的三元组表，求该矩阵转置矩阵的三元组表,问题分析,一般矩阵转置算法：,for(col=0;coln;col+),for(row=0;rowm;row+),ncolrow=mrowcol;,T(n)=O(m,n),对于一个mn的矩阵M，它的转置矩阵T是一个nm矩阵，且T(i,j)=M(j,i)，1,i,n，1,j,m。一个稀疏矩阵的转置矩阵仍然是稀疏矩阵。,例：上述矩阵M ,的转置矩阵为：,T ,由a转置到b只需：i.将矩阵的行列值相互交换；,ii.将每个三元组中的i和j相互调换；,iii.重排三元组之间的次序便可实现矩阵的转置。,(67)6行7列 (76)7行6列 (76)7行6列,i j value i(j)j(i)value i(j)j(i)value,1 2 12 2 1 12 1 3 3,1 3 9 3 1 9 1 6 15,3 1 3 1 3 3 2 1 12,4 3 24 3 4 24 3 1 9,5 2 18 2 5 18 3 4 24,6 1 15 1 6 15 4 6 7,i.和ii.,iii.,3 6 14 6 3 14 2 5 18,6 4 7 4 6 7 6 3 14,假设a和b是TSMatrix型的变量，分别表示矩阵M和T。,图5.5矩阵a转置到矩阵b的过程,实现方法：,i.直接取顺序存,算法思想：按照b.data中三元组的次序依次在a.data中找到相应的三元组进行转置。,算法5.1如下：,Status TransposeSMatrix(TSMatrix M,TSMatrix&T),/采用三元组表存储表示，求稀疏矩阵M的转置矩阵T。,T.mu=M.nu;,T.nu=M.mu;,T.tu=M.tu;,if(T.tu),q=1;,for(col=1;col=M.nu;+col),for(p=1;p=M.tu;+p),if(M.datap.j=col),T.dataq.i=M.datap.j;,T.dataq.j=M.datap.j;,T.dataq.e=M.datap.e;,+q;,return OK;,/TransposeSMatrix,M,row,col,elem,1,2,12,1,3,9,3,1,3,3,6,14,4,3,24,5,2,18,6,1,15,6,4,-7,M,row,col,elem,2,1,12,3,1,9,1,3,3,6,3,14,3,4,24,2,5,18,1,6,15,4,6,-7,M,row,col,elem,1,2,12,1,3,9,3,1,3,3,6,14,4,3,24,5,2,18,6,1,15,6,4,-7,M,row,col,elem,1,3,-3,1,6,15,2,1,12,2,5,18,3,1,9,3,4,24,4,6,-7,6,3,14,6,7,8,1 2 12,1 3 9,3 1 -3,3 6 14,4 3 24,5 2 18,6 1 15,6 4 -7,i j v,0 1 2 3 4 5 6 7 8,ma,7,6,8,1 3 -3,1 6 15,2 1 12,2 5 18,3 1 9,3 4 24,4 6 -7,6 3 14,i j v,0 1 2 3 4 5 6 7 8,mb,k,p,p,p,p,p,p,p,p,k,k,k,k,p,p,p,p,p,p,p,p,col=1,col=2,时间复杂度：O(nutu)，即和M的列数及非零元的个数的乘积乘正比。当非零,元的个数tu和munu同数量级时，算法5.1的时间复杂度就为O(mu )了（例如，,假设在100500的矩阵中有tu10000个非零元），虽然节省了存储空间，但时间复,杂度提高了。因此，该算法仅适于tumunu的情况。,ii.顺序取直接存,算法思想：按照a.data中三元组的次序进行转置，并将转置后的三元组置,入b中适当的位置。,在此，附设了num和cpot两个向量。numcol表示矩阵M中第col列中非零元的个,数，cpotcol指示M中第col列的第一个非零元在b.data中的恰当位置。显然有：,cpot1=1;,cpotcol=cpotcol1+numcol1 2cola.nu,例如，对上述矩阵M，num和cpot的值如表5.1所示。,表5.1矩阵M的向量cpot的值,col 1234567,numcol 2221010,cpotcol 1357889,6,7,8,1 2 12,1 3 9,3 1 -3,3 6 14,4 3 24,5 2 18,6 1 15,6 4 -7,i j v,0 1 2 3 4 5 6 7 8,ma,i j v,0 1 2 3 4 5 6 7 8,mb,col,numcol,cpotcol,1,1,2,2,3,2,3,5,2,4,7,1,5,8,0,6,8,1,7,9,0,7,6,8,1 3 -3,1 6 15,2 1 12,2 5 18,3 1 9,3 4 24,4 6 -7,6 3 14,p,p,p,p,p,p,p,p,4,6,2,9,7,5,3,Status FastTransposeSMatrix(TSMatrix M,TSMatrix&T),/采用三元组顺序表存储表示，求稀疏矩阵M的转置矩阵T。,T.mu=M.nu;,T.nu=M.mu;,T.tu=M.tu;,if(T.tu),for(col=1;col=M.nu;+col),num col=0;,for(t=1;t=M.tu;+t),+numM.datat.j;/求M中每一列含非零元个数,cpot1=1;/求第col列中第一个非零元在b.data中的序号,for(col=2;col=M.nu;+col),cpotcol=cpotcol1+numcol1;,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.e=M.datap.e;,+cpotcol;,/for,/if,return OK;,/FastTransposeSMatrix,算法5.2,时间复杂度,：O(nutu).在M的非零元个数tu和munu等数量级时,其时间复杂度为O(munu).,行逻辑链接的顺序表,1定义,行逻辑链接的顺序表,：带行链接信息的三元组表。,2C语言描述,typedef struct,TripledataMAXSIZE+1;/非零元三元组表,intrposMAXRC+1;/各行第一个非零元的位置表,int mu,nu,tu;/矩阵的行数、列数和非零元个数,RLSMatrix,3矩阵相乘运算,时间复杂度,是O(),i.经典算法,若设 Q=MN，其中，M是 矩阵，N是 矩阵。当n1m2时有：,for(i=1;i=m1;+i),for(j=1;j=n2;+j),Qij=0;,for(k=1;k=n1;+k),Qij+=Mik*Nkj;,ii.稀疏矩阵相乘算法,当M和N是稀疏矩阵并用三