《【精品数据结构】数组讲解.ppt》由会员分享，可在线阅读，更多相关《【精品数据结构】数组讲解.ppt（63页珍藏版）》请在三一文库上搜索。
1、第四章 数组,数组可以看成是一种特殊的线性表，即线性表中数据元素本身也是一个线性表 4.1 数组的定义和特点 定义,数组特点 数组结构固定 数据元素同构 数组运算 给定一组下标，存取相应的数据元素 给定一组下标，修改数据元素的值,4.2 数组的顺序存储结构 次序约定 以行序为主序 以列序为主序,4.3 矩阵的压缩存储 对称矩阵,三角矩阵,对角矩阵,Loc(aij)=Loc(a11)+2(i-1)+(j-1),数组可看成是一种特殊的线性表，其特殊在于，表中的数所元素本身也是一种线性表。 数组是我们最熟悉的数据类型，在早期的高级语言中，数组是唯一可供使用的数据类型。由于数组中各元素具有统一的类型，
2、并且数组元素的下标一般具有固定的上界和下界，因此，数组的处理比其它复杂的结构更为简单。多维数组是向量的推广。例如，二维数组： a11 a12 a1n a21 a22 a2n am1 am2 amn,Amn=,4.1 数组的定义,可以看成是由个行向量组成的向量，也可以看成是个列向量组成的向量。 在C语言中，一个二维数组类型可以定义为其分量类型为一维数组类型的一维数组类型，也就是说， typedef elemtype array2mn; 等价于： typedef elemtype array1n; typedef array1 array2m; 同理，一个维数组类型可以定义为其数据元素为维数组类型
3、的一维序组类型。 数组一旦被定义，它的维数和维界就不再改变。因此，除了结构的初始化和销毁之外，数组只有存取元素和修改元素值的操作。,2 数组的顺序表示和实现 由于计算机的内存结构是一维的，因此用一维内存来表示多维数组，就必须按某种次序将数组元素排成一列序列，然后将这个线性序列存放在存储器中。 又由于对数组一般不做插入和删除操作，也就是说，数组一旦建立，结构中的元素个数和元素间的关系就不再发生变化。因此，一般都是采用顺序存储的方法来表示数组。,通常有两种顺序存储方式： 行优先顺序将数组元素按行排列，第i+1个行向量紧接在第i个行向量后面。以二维数组为例，按行优先顺序存储的线性序列为： a11,a
4、12,a1n,a21,a22,a2n,am1,am2,amn 在PASCAL、C语言中，数组就是按行优先顺序存储的。 列优先顺序将数组元素按列向量排列，第j+1个列向量紧接在第j个列向量之后，A的m*n个元素按列优先顺序存储的线性序列为： a11,a21,am1,a12,a22,am2,an1,an2,anm 在FORTRAN语言中，数组就是按列优先顺序存储的。,以上规则可以推广到多维数组的情况：优先顺序可规定为先排最右的下标，从右到左，最后排最左下标：列优先顺序与此相反，先排最左下标，从左向右，最后排最右下标。 按上述两种方式顺序存储的序组，只要知道开始结点的存放地址（即基地址），维数和每维
5、的上、下界，以及每个数组元素所占用的单元数，就可以将数组元素的存放地址表示为其下标的线性函数。因此，数组中的任一元素可以在相同的时间内存取，即顺序存储的数组是一个随机存取结构。,例如，二维数组Amn按“行优先顺序”存储在内存中，假设每个元素占用d个存储单元。 元素aij的存储地址应是数组的基地址加上排在aij前面的元素所占用的单元数。因为aij位于第i行、第j列，前面i-1行一共有(i-1) n个元素，第i行上aij前面又有j-1个元素，故它前面一共有(i-1) n+j-1个元素，因此，aij的地址计算函数为： LOC(aij)=LOC(a11)+(i-1)*n+j-1*d 同样，三维数组Ai
6、jk按“行优先顺序”存储，其地址计算函数为： LOC(aijk)=LOC(a111)+(i-1)*n*p+(j-1)*p +(k-1)*d,上述讨论均是假设数组各维的下界是不是1，更一般的二维数组是Ac1.d1,c2.d2，这里c1,c2不一定是1。aij前一共有i-c1行，二维数组一共有d2-c2+1列，故这i-c1行共有(i-c1)*(d2-c2+1)个元素，第i行上aij前一共有j-c2个元素，因此，aij的地址计算函数为： LOC(aij)=LOC(ac1c2)+(i-c1)*(d2-c2+1)+j-c2)*d 例如，在C语言中，数组各维下标的下界是0，因此在C语言中，二维数组的地址计
7、算公式为： LOC(aij)=LOC(a00)+(i*(d2+1)+j)*d,在科学与工程计算问题中，矩阵是一种常用的数学对象，在高级语言编制程序时，简单而又自然的方法，就是将一个矩阵描述为一个二维数组。矩阵在这种存储表示之下，可以对其元素进行随机存取，各种矩阵运算也非常简单，并且存储的密度为1。但是在矩阵中非零元素呈某种规律分布或者矩阵中出现大量的零元素的情况下，看起来存储密度仍为1，但实际上占用了许多单元去存储重复的非零元素或零元素，这对高阶矩阵会造成极大的浪费，为了节省存储空间，可以对这类矩阵进行压缩存储：即为多个相同的非零元素只分配一个存储空间；对零元素不分配空间。,4.2 矩阵的压缩
8、存储,所谓特殊矩阵是指非零元素或零元素的分布有一定规律的矩阵。 1、对称矩阵 在一个n阶方阵A中，若元素满足下述性质： aij=aji 0i,jn-1 则称A为对称矩阵。对称矩阵中的元素关于主对角线对称，故只要存储矩阵中上三角或下三角中的元素，让每两个对称的元素共享一个存储空间，这样，能节约近一半的存储空间。不失一般性，我们按“行优先顺序”存储主对角线（包括对角线）以下的元素。,1 特殊矩阵,存储形式如图所示： 1 5 1 3 7 a00 5 0 8 0 0 a10 a 11 1 8 9 2 6 a20 a21 a23 3 0 2 5 1 . 7 0 6 1 3 an-1 0 a n-1 1
9、a n-1 2 a n-1 n-1 在这个下三角矩阵中，第i行恰有i+1个元素，元 素总数为：(i+1)=n(n+1)/2 可以将这些元素存放在一个向量sa0.n(n+1)/2-1中。为了便于访问对称矩阵A中的元素，我们必须在aij和sak之间找一个对应关系。,若ij，则ai j在下三角形中。 ai j之前的i行（从第0行到第i-1行）一共有1+2+i=i(i+1)/2个元素，在第i行上， ai j之前恰有j个元素（即ai0,ai1,ai2,aij-1），因此有： k=i*(i+1)/2+j 0kn(n+1)/2 若ij，则aij是在上三角矩阵中。因为aij=aji，所以只要交换上述对应关系式
10、中的i和j即可得到： k=j*(j+1)/2+i 0 kn(n+1)/2 令 I=max(i,j)， J=min(i,j)，则k和 i, j的对应关系可统一为： k=I*(I+1)/2+J 0 kn(n+1)/2,因此，aij的地址可用下列式计算： LOC(aij)=LOC(sak) =LOC(sa0)+k*d=LOC(sa0+I*(I+1)/2+J*d 有了上述的下标交换关系，对于任意给定一组下标 (i，j)，均可在sak中找到矩阵元素aij，反之，对所有 的k=0,1,2,n(n-1)/2-1，都能确定sak中的元素在矩阵中的位置(i,j)。由此，称san(n+1)/2为阶对称矩阵A的压缩
11、存储，见下图： k=0 1 2 3 n(n-1)/2 n(n-1)/2-1 例如a21和a12均存储在 sa4中，这是因为 k=I*(I+1)/2+J=2*(2+1)/2+1=4,以主对角线划分，三角矩阵有上三角和下三角两种。 上三角矩阵如图所示，它的下三角（不包括主对角线） 中的元素均为常数。下三角矩阵正好相反，它的主对 角线上方均为常数。在大多数情况下， 三角矩阵常数为零。 a00 a01 a 0 n-1 a00 0 0 0 a11 a 1 n-1 a10 a11 0 . . 0 0 a n-1 n-1 an-1 0 an-1 1 an-1 n-1 (a)上三角矩阵 (b)下三角矩阵,2、
12、三角矩阵,三角矩阵中的重复元素c可共享一个存储空间，其余的元素正好有n(n+1)/2个，因此，三角矩阵可压缩存储到向量sa0.n(n+1)/2中，其中c存放在向量的最后一个分量中， 上三角矩阵中，主对角线之上的第p行(0pj,k=,下三角矩阵的存储和对称矩阵类似，sak和aij对应关系是： i(i+1)/2+j ij n(n+1)/2 ij 3、对角矩阵 对角矩阵中，所有的非零元素集中在以主对角线为了中心的带状区域中，即除了主对角线和主对角线相邻两侧的若干条对角线上的元素之外，其余元素皆为零。下图给出了一个三对角矩阵， a00 a01 a10 a11 a12 a21 a22 a23 . . .
13、 an-2 n-3 an-2 n-2 an-2 n-1 an-1 n-2 an-1 n-1,k=,非零元素仅出现在主对角(aii,0in-1上，紧邻主对角线上面的那条对角线上(aii+1,0in-2)和紧邻主对角线下面的那条对角线上(ai+1 i,0in-2)。显然，当i-j1时，元素aij=0。 由此可知，一个k对角矩阵(k为奇数)A是满足下述条件的矩阵：若i-j(k-1)/2 ，则元素 aij=0。 对角矩阵可按行优先顺序或对角线的顺序，将其压缩存储到一个向量中，并且也能找到每个非零元素和向量下标的对应关系。,在三对角矩阵里附满足条件i=0，j=0、1，或i=n-1j=n-2、n-1或1i
14、n-1,j=i-1、i、i+1的元素aij外，其余元素都是零。 对这种矩阵，我们也可按行优序为主序来存储。除第0行和第n-1行是2个元素外，每行的非零元素都要是3个，因此，需存储的元素个数为3n-2。,K=0 1 2 3 4 5 3n-2 3n-1 数组sa中的元素sak与三对角带状矩阵中的元素aij存在一一对应关系，在aij之前有i行,共有3*i-1个非零元素，在第i行，有j-i+1个非零元素，这样，非零元素aij的地址为：,LOC(i,j)=LOC(0,0)+3*i-1+(j-i+1)*d =LOC(0,0)+(2i+j)*d 上例中，a34对应着sa10。 k=2*i+j=2*3+4=1
15、0 a21对应着sa5 k=2*2+1=5 由此，我们称sa0.3*n-2是阶三对角带状矩阵A的压缩存储表示。,上述的各种特殊矩阵非零元素的分布都是有规律的，因此总能找到一种方法将它们压缩存储到一个向量中，并且一般都能找到矩阵中的元素与该向量的对应关系，通过这个关系，仍能对矩阵的元素进行随机存取。 什么是稀疏矩阵？简单说，设矩阵A中有s个非零元素，若s远远小于矩阵元素的总数（即smn），则称A为稀疏矩阵。,4.3 稀疏矩阵,例如，下列三元组表 (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
16、,7)这一对行、列值便可作为下列矩阵M的另一种描述。而由上述三元组表的不同表示方法可引出稀疏矩阵不同的压缩存储方法。 0 12 9 0 0 0 0 0 0 -3 0 0 15 0 0 0 0 0 0 0 12 0 0 0 18 0 -3 0 0 0 0 14 0 9 0 0 24 0 0 0 0 24 0 0 0 0 0 0 0 0 0 7 0 18 0 0 0 0 0 0 0 14 0 0 0 15 0 0 7 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 稀疏矩阵M和T,M=,T=,假设以顺序存储结构来表示三元组表，则可得到稀疏矩阵的一种压缩存储方法三元顺序表。 #defin
17、e maxsize 10000 typedef int datatype; typedef struct int i,j; datatype v; triple;,一、三元组顺序表 转置,typedef struct triple datamaxsize; int m,n,t; tripletable; 设A为tripletable型的结构变量，图5.4中所示的稀疏矩阵的三元组的表示如下： i j v 1 2 12 1 3 9 3 1 -3 3 6 14 4 3 24 5 2 18 6 1 15 6 4 -7,以矩阵的转置为例，说明在这种压缩存储结构上如何实现矩阵的运算。 一个mn的矩阵A，它
18、的转置B是一个nm的矩阵，且aij=bji，0im，0jn，即A的行是B的列，A的列是B的行。 将A转置为B，就是将A的三元组表a.data置换为表B的三元组表b.data，如果只是简单地交换a.data中i和j的内容，那么得到的b.data将是一个按列优先顺序存储的稀疏矩阵B，要得到按行优先顺序存储的b.data，就必须重新排列三元组的顺序。 由于A的列是B的行，因此，按a.data的列序转置，所得到的转置矩阵B的三元组表b.data必定是按行优先存放的。,按这种方法设计的算法，其基本思想是：对A中的每一列 col(0coln-1)，通过从头至尾扫描三元表a.data，找出所有列号等于col
19、的那些三元组，将它们的行号和列号互换后依次放入b.data中，即可得到B的按行优先的压缩存储表示。 i j v 1 3 -3 1 6 15 2 1 12 2 5 18 3 1 9 3 4 24 4 6 -7 6 3 14,Void transmatrix(tripletable a,tripletable b) int p q col; b.m=a.n; b.n=a.m; b.t=a.t; if(b.t=0) printf(“A=0n”); q=0;,for(col=1;col=a.n;col+) for(p=0;p=a.t;p+) if(a.datap.j=col) b.dataq.i=a.
20、datap.j; b.dataq.j=a.datap.i; b.dataq.v=a.datap.v; q+; ,分析这个算法，主要的工作是在p和col的两个循环中完成的，故算法的时间复杂度为O(n*t)，即矩阵的列数和非零元的个数的乘积成正比。而一般传统矩阵的转置算法为： for(col=0;col=n-1;+col) for(row=0;row=m;+row) tcolrow=mrowcol; 其时间复杂度为O(n*m)。当非零元素的个数t和m*n同数量级时，算法transmatrix的时间复杂度为O(n*n2)。,三元组顺序表虽然节省了存储空间，但时间复杂度比一般矩阵转置的算法还要复杂，同
21、时还有可能增加算是法的难度。因此，此算法仅适用于t=m*n的情况。 下面给出一种快速转置的算法，其算法思想为：对A扫描一次，按A第二列提供的列号一次确定位置装入B的一个三元组。具体实施如下：一遍扫描先确定三元组的位置关系，二次扫描由位置关系装入三元组。可见，位置关系是此种算法的关键。,为了预先确定矩阵M中的每一列的第一个非零元素在数组B中应有的位置，需要先求得矩阵M中的每一列中非零元素的个数。因为：矩阵M中第一列的第一个非零元素在数组B中应有的位置等于前一列第一个非零元素的位置加上前列非零元素的个数。 为此，需要设置两个一维数组num0.n和cpot0.n num0.n：统计M中每列非零元素的
22、个数，numcol的值可以由A的第二列求得。,cpot0.n：由递推关系得出M中的每列第一个非零元素在B中的位置。 算法通过cpot数组建立位置对应关系： cpot1=1 cpoti=cpoti-1+numi-1 2=i=a.n 例如：图中的矩阵M和相应的三元组A可以求得numi和 cpoti的值如下： i 1 2 3 4 5 6 7 numi 2 2 2 1 0 1 0 cpoti 1 3 5 7 8 8 9,A i j v,第一列元素个数 第二列元素个数 第三列元素个数,num,cpot,q=cpoti,p,q,快速转置算法如下： void fasttranstri(tritupletab
23、le b,tritupletable a) int p,q,l,k; int numa.n,copta.n; b.m=a.n; b.n=a.m; b.t=a.t; if(b.t=0) printf(“a=0”n); for(l=1;l=a.n;+l) numl=0; for(k=1;k=a.t;+k) +numa.datak.j;,cpot0=1; for(l=2; l=a.t;+l) cpotl=cpotl-1+numl-1; for(p=1;p=a.t;+p) col=a.datap.j; q=cpotl; b.dataq.i=a.datap.j; b.dataq.j=a.datap.i;
24、 b.dataq.v=a.datap.v;+cpotl; ,有时为了方便某些矩阵运算，我们在按行优先存储的三元组中，加入一个行表来记录稀疏矩阵中每行的非零元素在三元组表中的起始位置。当将行表作为三元组表的一个新增属性加以描述时，我们就得到了稀疏矩阵的另一种顺序存储结构：带行表的三元组表。其类型描述如下：,二、带行表的三元组 乘法,#define maxrow 100 typedef struct triple datamaxsize; int rposmaxrow; int n,m,t; rtripletable; 下面讨论两个稀疏矩阵相乘的例子，容易看出这种表示方法的优越性。,两个矩阵相乘的
25、经典算法也是大家所熟悉的。设 Q=M*N 其中，M是m1*n1矩阵，N是m2*n2矩阵。 当n1=m2时有： for(i=1;i=m1;+i) for(j=1;j=n2;+j) qij=0; for(k=1;k=n1;+k) qij+=mik*nkj; 此算法的复杂度为O(m1*n1*n2)。,当M和N是稀疏矩阵并用三元组表存储结构时，就不能套用上述算法。假设M和N分别为：,0 0 5 0 -1 0 0 2 0 0 0,M=,0 2 1 0 -2 4 0 0,N=,则Q=M*N为：,0 6 -1 0 0 4,Q=,它们的三元组分别为： i j v i j v i j v 1 1 3 1 2 2
26、 1 2 6 1 4 5 2 1 1 2 1 -1 3 2 -1 3 1 -2 3 2 4 3 1 2 3 2 4 q.data m.data n.data,稀疏矩阵相乘的基本思想是：对于M中每个元素M，找到N 中所有满足条件的元素，求得和的乘积，而从式得知，乘积矩阵Q中每个元素的值是个累加和，这个乘积只是中的一部分。为了便于操作，应对每个元素设一累加和的变量，其初值为零，然后扫描数组M，求得相应元素的乘积并累加到适当的求累计和的变量上。,void multsmatrix(rtripletable a, rtripletable b, rtripletable c) if(a.n!=b.m)
27、/不能相乘 printf(“errorn”); exit(0); c.m=a.m; c.n=b.n; c.t=0; if(a.t*b.t!=0) for(arow=1;arow=a.m;+arow) ctemparow=0;,c.rposarow=c.t+1; for(p=a.ropsarow;pa.rposarow+1;+p) brow=a.datap.j; if(browb.t) t=b.rposbrow+1 else t=b.t+1; for(q=b.rposbrow; qt;+q) ccol=n.dataq.j; ctempccol+=a.datap.v*b.dataq.v; ,for
28、(ccol=1;ccolmaxsize) exit(0); c.datac.t=arow,ccol,ctempccol; ,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）唯一确定,稀疏矩阵 定义：非零元较零元少，且分布没有一定规律的矩阵 压缩存储原则：只存矩阵的行列维数和每个非零元的行列下标及其值,稀疏矩阵(其他讲解方式),稀疏矩阵的压缩存储方法 顺序存储结构 三元组表,#define M 20 typedef struct node int i,j; int
29、v; JD; JD maM;,三元组表所需存储单元个数为3(t+1) 其中t为非零元个数,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,ma0.i,ma0.j,ma0.v分别存放 矩阵行列维数和非零元个数,带辅助行向量的二元组表,增加一个辅助数组NRAm+1,其物理意义是第i行第一个非零元 在二元组表中的起始地址（m为行数） 显然有：,6,POS0不用或 存矩阵行数,二元组表需存储单元个数为2(t+1)+m+1,伪地址表示法,伪地址：本元素在矩阵中（包括零元素） 按行优先顺序的相对位置,伪地址表示法需存储单元个数 为2
30、(t+1),求转置矩阵 问题描述：已知一个稀疏矩阵的三元组表，求该矩阵转置矩阵的三元组表 问题分析 一般矩阵转置算法：,for(col=0;coln;col+) for(row=0;rowm;row+) ncolrow=mrowcol; T(n)=O(mn),解决思路：只要做到 将矩阵行、列维数互换 将每个三元组中的i和j相互调换 重排三元组次序，使mb中元素以N的行(M的列)为主序,方法一：按M的列序转置 即按mb中三元组次序依次在ma中找到相应的三元组进行转置。 为找到M中每一列所有非零元素，需对其三元组表ma从第一行 起扫描一遍。由于ma中以M行序为主序,所以由此得到的恰是mb 中应有的
31、顺序,算法描述：,算法分析：T(n)=O(M的列数n非零元个数t) 若 t 与mn同数量级，则,Ch4_1.c,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,col=1,col=2,方法二：快速转置 即按ma中三元组次序转置，转置结果放入b中恰当位置 此法关键是要预先确定M中每一列第一个非零元在mb中位置， 为确定这些位置，转置前应先求得M的每一列中非零元个数,实现：设两个数组 numcol：表示矩阵M中第col列中非零元个数 cpotcol：指示M中第col列第一个非零元在mb中位置 显然有：,1,3,5,7,8,8
32、,9,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,4,6,2,9,7,5,3,算法分析：T(n)=O(M的列数n+非零元个数t) 若 t 与mn同数量级，则T(n)=O(mn),算法描述：,Ch4_2.c,链式存储结构 带行指针向量的单链表表示 每行的非零元用一个单链表存放 设置一个行指针数组，指向本行第一个非零元结点；若本行无非零元，则指针为空 表头结点与单链表结点类型定义,需存储单元个数为3t+m,链式存储结构,十字链表 设行指针数组和列指针数组，分别指向每行、列第一个非零元 结点定义,typedef struc
33、t node int row,col,val; struct node *down, *right; JD;,从键盘接收信息建立十字链表算法,算法分析： T(n)=o(ts) 其中：t非零元个数 s= max(m,n),Ch4_3.c,令q=NULL,p=rhr-1, （1）寻找插入位置：当p!=NULL且cp-col时，p和q右移 （2）插入： a、若p=NULL且q=NULL，即本行空，则rhr-1=s; b、若p=NULL,q!=NULL，即走到行末，则q-right=s c、若c=p-col，则修改p-val d、若ccol且q=NULL，则在p之前插入s，即s是行链表中 第一个结点，令rhr-1=s; s-right=p; e、若ccol且q!=NULL，则在p之前插入s， 即 s-right=p; q-right=s;,m=4,n=3 1,1,3 2,2,5 2,3,4 4,1,8 2,1,7,Ch4_3.c,