数组的存储和运算

第十一讲数组的存储和运算第十一讲数组的定义和运算图5.1Am×n的二维数组第十一讲图5.2矩阵Am×n看成n个列向量的线性表第十一讲图5.3矩阵Am×n看成m个行向量的线性表第十一讲以上我们以二维数组为例介绍了数组的结构特性，实际上数组是一组有固定个数的元素的集合。也就是说，一旦定义了数组的维数和每一维的上下限，数组中元素的个数就固定了。例如二维数组A3×4，它有3行、4列，即由12个元素组成。由于这个性质，使得对数组的操作不像对线性表的操作那样可以在表中任意一个合法的位置插入或删除一个元素。对于数组的操作一般只有两类：(1）获得特定位置的元素值；(2）修改特定位置的元素值。第十一讲第十一讲基本操作：（1）InitArray(A,n,bound1,…,boundn)：若维数n和各维的长度合法，则构造相应的数组A，并返回TRUE。（2）DestroyArray（A）：销毁数组A。（3）GetValue（A，e,index1,…,indexn）：若下标合法，则用e返回数组A中由index1,…,indexn所指定的元素的值。（4）SetValue（A，e，index1,…,indexn）：若下标合法，则将数组A中由index1,…,indexn所指定的元素的值置为e。这里定义的数组，与C语言的数组略有不同，下标是从1开始的。第十一讲数组的顺序存储和实现数组的顺序存储结构有两种：一种是按行序存储，如高级语言BASIC、COBOL和PASCAL语言都是以行序为主；另一种是按列序存储，如高级语言中的FORTRAN语言就是以列序为主显然，二维数组Am×n以行为主的存储序列为：a11,a12,…，a1n,a21,a22,…,a2n,…,am1,am2,…,amn而以列为主的存储序列为：a11,a21,…，am1，a12,a22,…,am2,…,a1n,a2n,…,amn第十一讲假设有一个3×4×2的三维数组A，共有24个元素，其逻辑结构如图5.4所示。图5.4三维数组的逻辑结构图列行纵a311a321a331a341a211a221a231a241a111a121a131a141a112a122a132a142a242a342第十一讲三维数组元素的标号由三个数字表示，即行、列、纵三个方向。a142表示第1行，第4列，第2纵的元素。如果对A3×4×2（下标从1开始）采用以行为主序的方法存放，即行下标变化最慢，纵下标变化最快，则顺序为：a111，a112，a121，a122，…，a331，a332，a341，a342采用以纵为主序的方法存放，即纵下标变化最慢，行下标变化最快，则顺序为：a111，a211，a311，a121，a221，a321，…，a132，a232，a332，a142，a242，a342第十一讲以上的存放规则可推广到多维数组的情况。总之，知道了多维数组的维数，以及每维的上下界，就可以方便地将多维数组按顺序存储结构存放在计算机中了。同时，根据数组的下标，可以计算出其在存储器中的位置。因此，数组的顺序存储是一种随机存取的结构。以二维数组Am×n为例，假设每个元素只占一个存储单元，“以行为主”存放数组，下标从1开始，首元素a11的地址为Loc［1,1］，求任意元素aij的地址。aij是排在第i行，第j列，并且前面的第i-1行有n×（i-1）个元素，第ｉ行第j个元素前面还有ｊ-１个元素。由此得到如下地址计算公式：Loc［i,j］=Loc［1,1］+n×(i-1)+(j-1)第十一讲根据计算公式，可以方便地求得aij的地址是Loc［i,j］。如果每个元素占size个存储单元，则任意元素aij的地址计算公式为：Loc［i,j］=Loc［1,1］+(n×(i-1)+j-1)×size三维数组A（1..r,1..m,1..n）可以看成是r个m×n的二维数组，如图5.5所示。图5.5三维数组看成r个m×n的二维数组mnrmnk－1j－1第十一讲假定每个元素占一个存储单元，采用以行为主序的方法存放，即行下标r变化最慢，纵下标n变化最快。首元素a111的地址为Loc［1,1,1］，求任意元素aijk的地址。显然，ai11的地址为Loc［i,1,1］=Loc［1,1,1］+(i-1)×m×n，因为在该元素之前，有ｉ-１个ｍ×ｎ的二维数组。由ai11的地址和二维数组的地址计算公式，不难得到三维数组任意元素aijk的地址：Loc［i,j,k］=Loc［1,1,1］+(i-1)×m×n+(j-1)×n+(k-1)其中1≤i≤ｒ，1≤j≤ｍ，1≤k≤ｎ。第十一讲如果将三维数组推广到一般情况，即：用j1、j2、j3代替数组下标i、j、k，并且j1、j2、j3的下限为c1、c2、c3，上限分别为d1、d2、d3，每个元素占一个存储单元，则三维数组中任意元素a(j1，j2，j3)的地址为：Loc［j1,j2,j3］=Loc［c1,c2,c3］+l×(d2-c2+1)×(d3-c3+1)×(j1-c1)+l×(d3-c3+1)×(j2-c2)+l×(j3-c3)其中l为每个元素所占存储单元数。令α1=l×(d2-c2+1)×(d3-c3+1),α2=l×(d3-c3+1),α3=1，则：Loc［j1,j2,j3］=Loc［c1,c2,c3］+α1×(j1-c1)+α2×(j2-c2)+α3(j3-c3)=Loc［c1,c2,c3］+∑αi×(ji-ci)（1≤i≤3）第十一讲由公式可知Loc［j1,j2,j3］与j1,j2,j3呈线性关系。对于ｎ维数组A(c1∶d1,c2∶d2，…,cn∶dn)，我们只要把上式推广，就可以容易地得到ｎ维数组中任意元素aj1j2…jn的存储地址的计算公式:)(],,[],,,[12121iiniinncjacccLocjjjLoc其中nikkkicda1)1(1(1≤i≤n)。第十一讲特殊矩阵的压缩存储1三角矩阵三角矩阵大体分为三类：下三角矩阵、上三角矩阵和对称矩阵。对于一个n阶矩阵A来说，若当ij时，有aij=0，则称此矩阵为下三角矩阵；若当ij时，有aij=0，则称此矩阵为上三角矩阵；若矩阵中的所有元素均满足aij=aji，则称此矩阵为对称矩阵。图5.6下三角矩阵A第十一讲对于下三角矩阵的压缩存储，我们只存储下三角的非零元素，对于零元素则不存。我们按“行序为主序”进行存储，得到的序列是a11,a21,a22,a31,a32,a33,…,an1,an2,…,ann。由于下三角矩阵的元素个数为n(n+1)/2，即：第1行：1第2行：2第3行：3……第n行：n个1+2+3+4+5+#:+n=n(n+1)/2第十一讲所以可压缩存储到一个大小为n(n+1)/2的一维数组C中，如图5.7所示。图5.7三角矩阵的压缩形式第十一讲下三角矩阵中元素aij(ij)在一维数组A中的位置为：Loc［i,j］=Loc［1,1］+前i-1行非零元素个数+第i行中aij前非零元素个数前i-1行元素个数=1+2+3+4+…+（i-1）=i(i-1)/2，第i行中aij前非零元素个数=j-1，Loc［i,j］=Loc［1,1］+i(i-1)/2+j-1同样，对于上三角矩阵，也可以将其压缩存储到一个大小为n(n+1)/2的一维数组C中。其中元素aij(ij)在数组C中的存储位置为：Loc［i,j］=Loc［1,1］+j(j-1)/2+i-1对于对称矩阵，因其元素满足aij=aji，我们可以为每一对相等的元素分配一个存储空间，即只存下三角（或上三角）矩阵，从而将n2个元素压缩到n(n+1)/2个空间中。第十一讲图5.8带状矩阵A三对角带状矩阵有如下特点：i=1,j=1,2;#=1in,j=i-1,i,i+1;i=n,j=n-1,n;时，aij非零，其它元素均为零。当2带状矩阵第十一讲1.在这里我们假设每个非零元素所占空间的大小为1个单元。从图中观察得知，三对角带状矩阵中，除了第一行和最后一行只有2个非零元素外，其余各行均有3个非零元素。由此得到，所需一维向量空间的大小为2+2+3（n-2）=3n-2，如图5.9所示。图5.9带状矩阵的压缩形式第十一讲2.确定非零元素在一维数组空间中的位置Loc［i,j］=Loc［1,1］+前i-1行非零元素个数+第i行中aij前非零元素个数；前i-1行元素个数=3×（i-1）-1（因为第1行只有2个非零元素）；第i行中aij前非零元素个数=j-i+1，其中-1(ji)0(j=i)1(ji)j-i=由此得到Loc［i,j］=Loc［1,1］+3(i-1)-1+j-i+1=Loc［1,1］+2(i-1)+j-1第十一讲3稀疏矩阵图5.10稀疏矩阵第十一讲1.稀疏矩阵的三元组表表示法图5.11三元组的结构row该非零元素所在的行值col该非零元素所在的列值该非零元素所在的值value第十一讲图5.12稀疏矩阵的三元组表表示第十一讲稀疏矩阵的三元组表表示法虽然节约了存储空间，但比起矩阵正常的存储方式来讲，其实现相同操作要耗费较多的时间，同时也增加了算法的难度,即以耗费更多时间为代价来换取空间的节省。三元组表的类型说明如下：＃defineMAXSIZE1000/*非零元素的个数最多为1000*/typedefstruct{introw,col;/*该非零元素的行下标和列下标*/ElementTypee；/*该非零元素的值*/}Triple;typedefstruct{Tripledata［MAXSIZE+1］;/*非零元素的三元组表，data［0］未用*/intm,n,len;/*矩阵的行数、列数和非零元素的个数*/}TSMatrix；第十一讲1)下面首先以稀疏矩阵的转置运算为例，介绍采用三元组表时的实现方法。所谓的矩阵转置，是指变换元素的位置，把位于（row，col）位置上的元素换到（col，row）位置上，也就是说，把元素的行列互换。如图5.10所示的6×7矩阵M，它的转置矩阵就是7×6的矩阵N，并且N（row，col）=M（col，row），其中，1≤row≤7，1≤col≤6。采用矩阵的正常存储方式时，实现矩阵转置的经典算法如下：第十一讲voidTransMatrix（ElementTypesource［n］［m］,ElementTypedest［m］［n{/*source和dest分别为被转置的矩阵和转置以后的矩阵（用二维数组表示）*/inti,j;for(i=0;im;i++)for(j=0;jn;j++)dest［i］［j］=source［j］［i］;}①矩阵source的三元组表A的行、列互换就可以得到B中的元素，如图5.13所示。(i,j,x)———(j,i,x)↑↑AB图5.13稀疏矩阵的转置示例第十一讲②为了保证转置后的矩阵的三元组表B也是以“行序为主序”进行存放，则需要对行、列互换后的三元组表B按B的行下标（即A的列下标）大小重新排序，如图5.14所示。图5.14矩阵的转置(用三元组表示矩阵)rowcole121213931－3361443245218611564－712345678211231913－3631434242518161546－712345678②需要重新排序①行列互换rowcole第十一讲方法一：图5.15矩阵的转置第十一讲我们附设一个位置计数器j，用于指向当前转置后元素应放入三元组表B中的位置。处理完一个元素后，j加1，j的初值为1。具体转置算法如下：VoidTransposeTSMatrix(TSMatrixA,TSMatrix*B){/*把矩阵A转置到B所指向的矩阵中去，矩阵用三元组表表示*/inti,j,k;B-m=A.n;B-n=A.m;B-len=A.len;if(B-len0){第十一讲j=1;for(k=1;k=A.n;k++)for(i=1;i=A.len;i++)if(A.data［i］.col==k){B-data［j］.row=A.data［i］.colB-data［j］.col=A.data［i］.