数据结构——二维数组.ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,1,版权所有,1997(,c)Dale Carnegie&Associates,Inc.,数组、矩阵与集合,2,数组的相关概念,数组,是,n(n,1),个具有相同数据类型的数据元素,a,0,a,1,a,2,a,n-1,构成的占用连续存储单元的有限序列。,操作,:主要是存取数据元素。,特点,:,采用顺序的存储结构，且不进行插入、删除等操作。,地址计算,：,假设数组,A,的首地址为,L,0,，,每个元素占,k,个存储单元，,则数组第,i,个元素的存储位置,pos(Ai,),可由下式确定：,pos(Ai)posA0)ikL,0,ik,(0=in),特别地，当,k=1,时，有：,pos(Ai)L,0,i;,3,数组抽象数据类型,数据元素,：数组的数据元素集合可表示为,a,0,a,1,a,2,a,n-1,，,其中每个数据元素具有相同数据类型。,结构关系,：数组元素呈线性结构，且限定数组元素必须存储在地址连续的内存单元中。,基本操作,：对数组可执行以下的基本操作。,Initiate(A,),构造数组,A。,Size(A,),求长度。函数值为给定数组,A,中数据元素的个数。,Set(A,i,x,),存数组元素。把数据,x,存入数组,A,的下标为,i,的数组,元素中，其约束条件为0=,i=length(A)1。,Get(A,i,),取数组元素。取出数组,A,中下标为,i,的数组元素，其,约束条件为0=,i=length(A)-1。,4,数组类定义及实现,template,class Array,private:,T *a;,int,size;,public:,Array(int,sz,=100);,Array(const,Array&,arr,);,Array()deletea,;,int,getsize()return,size;,T&,operator(int,i);,Array&operator=(const Array&,arr,);,void,resize(int,sz,=100);void,prnt,(),;,5,数组类构造函数与赋值函数,Array(int,sz,=100),if(sz,=0),printf,(“,数组长度无效,n;exit(0);,size=,sz,;,a=new,Tsize,;,;,Array(const,Array&,arr,),size=,arr.size,;,a=new,Tsize,;,for(int,i=0;i,size;i,+),ai,=,arr.ai,;,;,6,数组类构造函数与赋值函数,Array&operator=(const Array&,arr,),delete a;,size=,arr.size,;,a=new,Tsize,for(int,i=0;i,size;i,+),ai,=,arr.ai,;,return*this;,;,void,prnt,(),for(int,i=0;i,size;i,+),cout,ai,“;,cout,endl,;,7,数组类重置函数,/,重新分配空间,void,resize(int,sz,=100),if(sz,=0)printf(“,数组长度无效,n;exit(0);,if(sz,=size)return;,T*,newa,=new,Tsz,;,int,n=(,sz,=,size)?sz:size,;,for(int,i=0;i,n;i,+),newai,=,ai,;,delete a;,a=,newa,;,size=,sz,;,;,8,二维数组的初步认识,二维数组可看作线性表的一种扩展,在逻辑上可看成由若干行、列组成的表格或矩阵，例如以下的,m,行,n,列的矩阵:,可表示成二维数组,int,Amn,;,9,二维数组的初步认识,将二维数组看作是线性表的扩展,例如，如果将每一列看作,为一个元素，则以上,m,行,n,列矩阵所对应的二维数组,a,可看,成如下线性表：,a(,1,2,n,),其中每一个数据元素,j,是一个列向量,j,(,a,1j,a,2j,a,3j,a,mj,),类似地，如果将每一行看作为一个元素，则,a,可看成如下线,性表：,a(,1,2,m,),其中每一个数据元素,i,是一个行向量,i,(,a,i1,a,i2,a,i3,a,in,),10,二维数组的初步认识,一般地，二维数组的逻辑结构可表示为：,Array_2=(D,R),其中，,D=,a,ij,|i=c,1,c,1,+1,d,1,;j=c,2,c,2,+1,d,2,；,a,ij,Data,Object,R=ROW,COL,ROW=|c,1,i,d,1,;c,2,jd,2,-1;a,ij,a,i,j+1,D,COL=|c,1,i,d,1,-1;c,2,jd,2,;a,i,+1,j,a,ij,D,其中：(,c,1,d,1,),和(,c,2,d,2,),分别为数组下标,i,j,的一对,界偶,（即满,足条件,c,1,i,d,1,，c,2,jd,2,）。,称,c,1,c,2,为下界,通常取,c1=c2=1;,称,d1,d2,为上界,通常取,d1=m，d2=n,11,二维数组的存储结构,按行排列,排列方式,a,11,a,12,a,1n,a,21,a,22,a,2n,a,m1,a,m2,a,m3,a,mn,地址计算,pos(Ai,j)L,0,inkjkL,0,(inj)k (0=in,0=jm),特别地，当,k=1,时，有：,pos(Ai,j)L,0,inj,12,二维数组的存储结构,按列排列,排列方式,a,11,a,21,a,m1,a,12,a,22,a,m2,a,1n,a,2n,a,3n,a,mn,地址计算,pos(Ai,j,)=L,0,jmkik=L,0,(jmi)k(0=in,0=jm),特别地，当,k=1,时，有：,pos(Ai,j,)=L,0,jmi,13,矩阵的类定义,class Matrix,private:,float *item;,int,m,n,;,public:,Matrix()item,=NULL;m=0;n=0;,Matrix(float,a,int,row,int,col,);,Matrix(Matrix,Matrix,Matrix&,tran,();,Matrix&,plus(Matrix,Matrix&,mult(Matrix,void,prnt,();,;,将,item,设计成一维排列是为了使矩阵中的行数和列数在存储量容许的情形下可以进行变化；,定义成指针类型以便在实例生成时按指定的长度动态分配存储,14,矩阵类的构造函数,Matrix:,Matrix(float,a,int,row,int,col,),int,j;,m=row;n=,col,;,item=new float m*n;,for(j=0;jm*,n;j,+),itemj,=,aj,;,;,Matrix:,Matrix(Matrix,&b),int,j;,m=,b.m,;n=,b.n,;,item=new,floatm,*n;,for(j,=0;jm*,n;j,+),itemj,=,b.itemj,;,;,15,矩阵转置,Matrix&,tran,(),功能,:返回当前矩阵的转置矩阵但当前矩阵没有改变。,处理过程,：,(1)创建一个矩阵类对象,x,并按当前矩阵的转置设置其行数与列数,并分配存储空间。,(2)将当前矩阵中的元素转置存放到矩阵,x,中并返回,x。,Matrix&,Matrix:tran,(),Matrix,int,i,j,;,x.m,=n;,x.n,=m;,x.item,=new float m*n;,for(i=0;i,m;i,+),for(j=0;j,n;j,+),x.itemj,*,m+i,=,itemi,*,n+j,;,return x要注意的是由于函数的返回类型是对象的引用，所以不能返回局部对象或无名对象，而只能是当前对象或,new,创建的对象。,16,矩阵相加,Matrix&,plus(Matrix,&b),功能,:,返回当前矩阵与,b,相加后的矩阵，,处理过程,：,(1)若二矩阵的行、列数不等，则显示出错信息；否则,(2)创建一个矩阵类的对象,x,并按当前矩阵设置其行数与列数；,将二矩阵对应的元素相加后存入,x,并返回,x。,17,矩阵相加,Matrix&Matrix:,plus(Matrix,&b),Matrix,int,i,j,;,if(b.m,!=,m)|(b.n,!=n),cout,参数错;,exit(0)else,x.m,=m;,x.n,=n;,x.item,=new float m*n;,for(i=0;i,m;i,+),for(j=0;j,n;j,+),x.itemi,*,n+j,=,b.itemi,*,n+j+itemi,*,n+j,;,return x;,;,18,矩阵相乘,设两个行列数分别为,m,l,和,l,n,的矩阵,A、B，,则,乘积矩阵,C,中的元素,C,i,j,满足以下等式：,例如：,19,矩阵相乘,Matrix&,mult(Matrix,&b),功能,:,返回当前矩阵与,b,相乘后的矩阵,。,处理过程,：,(1),若当前矩阵的列数不等于矩阵,b,的行数，则显示出,错信息否则：,(2)创建一个矩阵对象,x,并按结果矩阵设置行数与列数，按公式求出其中的每一个元素并返回该矩阵,。,20,矩阵相乘,Matrix&Matrix:,mult(Matrix,&b),Matrix,int,i,j,k,;,if(b.m,!=,n)cout,参数错;,exit(0);,else,x.m,=m;,x.n,=,b.n,;,x.item,=new float,x.m,*,x.n,;,for(i=0;i,x.m;i,+),for(j=0;j,x.n;j,+),x.itemi,*,x.n+j,=0;,for(k=0;k,n;k,+),x.itemi,*,x.n+j,=,x.itemi,x.n+j+itemi,*,n+k,*,b.itemk,*,b.n+j,;,return x;,;,21,互动环节：,Matrix,类赋值操作的实现,问题说明：要实现,Matrix,类对象的赋值操作。,float a=5,7,3,9,0,4,2,8,1,0,4,3;,Matrix jz1(a,4,3),jz2;,可设置以下的代码对其进行赋值的操作：,jz2=jz1;,赋值函数,Matrix&operator=(Matrix&b),的功能是将矩阵,对象,b,的信息设置到当前对象中去，并返回当前对象。,为了调试程序的方便，再增设一个成员函数,prnt,(),用于,显示对象中的矩阵元素。,22,互动环节：,Matrix,类赋值操作的实现,void,Matrix:prnt,(),int,i,j,;,for(i=0;i,m;i,+),for(j=0;j,n;j,+),cout,setw(5),itemi,*,n+j,;,cout,endl,;,;,cout,-,endl,;,;,Matrix&,Matrix:operator,=(Matrix&b),int,j;,m=,b.m,;n=,b.n,;,if(item,!=,NULL)delete,item;,item=new float m*n;,for(j=0;jm*,n;j,+),itemj,=,b.itemj,;,return*this23,互动环节：,Matrix,类赋值操作测试程序,void main(),float a=5,7,3,9,0,4,2,8,1,0,4,3;,Matrix jz1(a,4,3),jz2(jz1),jz3,jz4,jz5;,jz3=jz1.tran();jz3.prnt();,jz4=jz1.plus(jz2);jz4.prnt();,jz5=jz1.mult(jz3);jz5.prnt();,程序的运行结果如下：,5 9 2 0,7 0 8 4,3 4 1 3,-,10 14 6,18 0 8,4 16 2,0 8 6,-,83 57 69 37,57 97 22 12,69 22 69 35,37 12 35 25,-,24,矩阵的压缩存储,对称矩阵,若一个,n,阶方阵,A,的元素满足性质,Ai,j,=,Aj,i,，,则称该,矩阵为,n,阶对称矩阵。,对角矩阵,所谓对角矩阵是指矩阵的所有非零元素都集中在以主对角线为中心的带状区域中。,稀疏矩阵,若在一个矩阵中，零元素的个数相对于整个矩阵元素,总个数所占比例较大，则可认为该矩阵是稀疏矩阵。,25,对称矩阵的压缩存储,仅存放对称矩阵的下三角元素,由于下标序号从0开始，,A,i,j,处于第,i+1,行，其前,i,行元素的个数为,i*(i+1)/2，,所以,A,i,j,在一维数组排列中的序号为,i*(i+1)/2+j。,A,的任意一个元素,a,i,j,在一维数组中的序号为,k，,其中,26,对角矩阵的压缩存储,在三对角矩阵,B,中，除第一行和最后一行只有两个非零元素外，其它每,行中各有三个非零元素；而且第,i,行(0,i,n),的前,i1,个元素为零。由于第,0行有2个元素，第1行到第,i-1,行的元素个数为(,i1)3，,而,B,i,j,在第,i,行,中的序号为,j(i1)，,因此，,B,中非零元素,B,i,j,在该一维数组中的位置,k,可计算如下(1,i,n)：,k,2(i1)3j(i1)2,i,j,27,稀疏矩阵的压缩存储,只存储非零元素,三元组,(,row，col，value,),例如对于非零元素2，其三元组表示为,(0,0,2),28,如果以顺序存储结构来表示三元组线性表，则可得,到稀疏矩阵的三元组表压缩存储方式。,例如，三元组表,row,col,value,0,0,2,0,6,6,1,3,4,2,2,7,4,0,12,4,4,9,5,7,5,稀疏矩阵的压缩存储,29,const,maxlen,=,三元组表允许的最大长度；,typedef,struct,int,row,col,;,float value;,RCV;,typedef,struct,int,r,c,num;,RCV,itemmaxlen,;,SMatrix,;,其中,r,c,num,分别表示稀疏矩阵的行数、列数和非零元,个数,item域中表示的非零元的三元组是以行序排列的。,三元组表数据类型的定义,30,struct,RCV,int,row,col,;,float value;,;,class,SMatrix,RCV *item;,int,r,c,num,;,public:,SMatrix()item,=NULL;r=0;c=0;num=0;,SMatrix(RCV,a,int,n,int,row,int,col,);,SMatrix,&,tran,();,SMatrix,SMatrix,&,plus(SMatrix,SMatrix,&,mult(SMatrix,void,prnt,();,;,稀疏矩阵类定义,31,SMatrix,(),无参数，仅创建一个空的三元组表。,SMatrix(RCV,a,int,n,int,row,int,col,),设置三元组表,a，,长度,n,及行数,row、,列数,col,四个参数，创建的三元组表由参数,a、n,确定，而行数、列数分别由参数,row、col,确定。,功能,:,按指定的参数分配存储空间并设置数据成员的初值。,SMatrix:SMatrix(RCV,a,int,n,int,row,int,col,),int,i;,r=row;c=,col,;num=n;,item=new RCV num;,for(i=0;i0),k=0;,for(i=0;i,c;i,+),forj=0;j,num;j,+),if(,itemj.col,=i),x.itemk.row,=,itemj.col,;,x.itemk.col,=,itemj.row,;,x.itemk.value,=,itemj.value,;,k+;,return(x,);,上述算法中要进行二重循环，算法的效率比较低,方法二：快速转置,即按,ma,中三元组次序转置，转置结果放入,b,中恰当位置此法关键是要预先确定,M,中每一列第一个非零元在,mb,中位置，为确定这些位置，转置前应先求得,M,的每一列中非零元个数,实现：设两个数组,numcol,：表示矩阵,M,中第,col,列中非零元个数,cpotcol,指示,M,中第,col,列第一个非零元在,mb,中位置,显然有：,cpot1=1;,cpotcol,=cpotcol-1+numcol-1;(2,col ma0.j),1,3,5,7,8,8,9,col,numcol,cpotcol,1,2,2,2,3,2,4,1,5,0,6,1,7,0,37,稀疏矩阵快速转置,SMatrix,&tran1(),功能,:使用快速转置法计算并返回当前矩阵的转置矩阵；,处理过程,：,(1)创建一个稀疏矩阵,x，,形成,x,的,r,c,num，,并按指定的长度分配存储空间。,(2)求当前矩阵中各列非零元的个数，将结果存入数组,rnum,。,(3),求结果矩阵中各行起始位置，将结果存入数组,rstart,。,(4),依次扫描当前矩阵中的三元组表，对每一个三元组行列置换后按原列号,col,存入,x,中由,rstartcol,指示的位置，并使其位置加1。,(5)返回结果矩阵,x。,38,稀疏矩阵快速转置,形成数组,rnum,；,for(i=0;i,c;i,+),rnumi,=0;,for(i=0;i,num;i,+),rnumitemi.col,+;,形成数组,rstart,；,rstart0=0;,for(i=1;i,c;i,+),rstarti,=rnumi-1+rstarti-1;,39,稀疏矩阵快速转置,SMatrix,&SMatrix:tran1),SMatrix,&x=*new,SMatrix,;,int,i,j,;,int,rnum100,rstart100;,x.r,=c;,x.c,=r;,x.num,=num;,x.item,=new,RCVnum,;,for(i=0;i,c;i,+),rnumi,=0;,for(i=0;i,num;i,+,),rnumitemi.col,+;,rstart0=0;,for(i=1;i,c;i,+),rstarti,=rnumi-1+rstarti-1;,for(i=0;i,num;i,+),j=,itemi.col,;,x.itemrstartj.row,=j;,x.itemrstartjcol,=,itemi.row,;,x.itemrstartj.value,=,itemi.value,;,rstartj,+;,return(x,);,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,