《数据结构——二维数组.ppt》由会员分享，可在线阅读，更多相关《数据结构——二维数组.ppt（40页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、1版权所有,1997(c)Dale Carnegie&Associates,Inc.数组、矩阵与集合2数组的相关概念数组是n(n1)个具有相同数据类型的数据元素a0,a1,a2,an-1构成的占用连续存储单元的有限序列。操作:主要是存取数据元素。特点:采用顺序的存储结构，且不进行插入、删除等操作。地址计算：假设数组A的首地址为L0，每个元素占k个存储单元，则数组第i个元素的存储位置pos(Ai)可由下式确定：pos(Ai)pos(A0)ikL0ik(0=in)特别地，当k=1时，有：pos(Ai)L0i;3数组抽象数据类型 数据元素：数组的数据元素集合可表示为a0,a1,a2,an-1，其中每
2、个数据元素具有相同数据类型。结构关系：数组元素呈线性结构，且限定数组元素必须存储在地址连续的内存单元中。基本操作：对数组可执行以下的基本操作。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
3、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
4、;isize;i+)ai=arr.ai;6数组类构造函数与赋值函数 Array&operator=(const Array&arr)delete a;size=arr.size;a=new Tsize;for(int i=0;isize;i+)ai=arr.ai;return*this;void prnt()for(int i=0;isize;i+)coutai“;coutendl;7数组类重置函数/重新分配空间void resize(int sz=100)if(sz=0)printf(“数组长度无效n;exit(0);if(sz=size)return;T*newa=new Tsz;int
5、n=(sz=size)?sz:size;for(int i=0;in;i+)newai=ai;delete a;a=newa;size=sz;8二维数组的初步认识二维数组可看作线性表的一种扩展,在逻辑上可看成由若干行、列组成的表格或矩阵，例如以下的m行n列的矩阵:可表示成二维数组 int Amn;9二维数组的初步认识将二维数组看作是线性表的扩展,例如，如果将每一列看作为一个元素，则以上m行n列矩阵所对应的二维数组a可看成如下线性表：a(1,2,n)其中每一个数据元素j是一个列向量j(a1j,a2j,a3j,amj)类似地，如果将每一行看作为一个元素，则a可看成如下线性表：a(1,2,m)其中每
6、一个数据元素i是一个行向量i(ai1,ai2,ai3,ain,)10二维数组的初步认识一般地，二维数组的逻辑结构可表示为：Array_2=(D,R)其中，D=aij|i=c1,c1+1,d1;j=c2,c2+1,d2；aijData Object R=ROW,COL ROW=|c1id1;c2jd2-1;aij,ai,j+1D COL=|c1id1-1;c2jd2;ai+1,j,aijD其中：(c1,d1)和(c2,d2)分别为数组下标i,j的一对界偶界偶（即满足条件c1id1，c2jd2）。称c1,c2为下界,通常取c1=c2=1;称d1,d2为上界,通常取d1=m，d2=n 11二维数组的
7、存储结构按行排列排列方式a11 a12 a1n a21 a22 a2n am1 am2 am3 amn地址计算pos(Ai,j)L0inkjkL0(inj)k (0=in,0=jm)特别地，当k=1时，有：pos(Ai,j)L0inj12二维数组的存储结构按列排列排列方式a11 a21 am1 a12 a22 am2 a1n a2n a3n amn地址计算pos(Ai,j)=L0jmkik=L0(jmi)k(0=in,0=jm)特别地，当k=1时，有：pos(Ai,j)=L0jmi 13矩阵的类定义class Matrixprivate:float *item;int m,n;public:M
8、atrix()item=NULL;m=0;n=0;Matrix(float a,int row,int col);Matrix(Matrix&b);Matrix&operator=(Matrix&b);Matrix&tran();Matrix&plus(Matrix&b);Matrix&mult(Matrix&b);void prnt();将item设计成一维排列是为了使矩阵中的行数和列数在存储量容许的情形下可以进行变化；定义成指针类型以便在实例生成时按指定的长度动态分配存储 14矩阵类的构造函数Matrix:Matrix(float a,int row,int col)int j;m=row
9、;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&x=*new Matrix;int i,
10、j;x.m=n;x.n=m;x.item=new float m*n;for(i=0;im;i+)for(j=0;jn;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(Ma
11、trix&b)Matrix&x=*new 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;im;i+)for(j=0;jn;j+)x.itemi*n+j=b.itemi*n+j+itemi*n+j;return x;18矩阵相乘设两个行列数分别为ml和ln的矩阵A、B，则乘积矩阵C中的元素Ci,j满足以下等式：例如：19矩阵相乘Matrix&mult(Matrix&b)功能:返回当前矩阵与b相乘后的矩阵。处理过程：(1)若当前矩阵的列数不等于矩阵b的行
12、数，则显示出 错信息，否则：(2)创建一个矩阵对象x并按结果矩阵设置行数与列数，按公式求出其中的每一个元素并返回该矩阵。20矩阵相乘Matrix&Matrix:mult(Matrix&b)Matrix&x=*new 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;ix.m;i+)for(j=0;jx.n;j+)x.itemi*x.n+j=0;for(k=0;kn;k+)x.itemi*x.n+j=x.itemi*x.n+j+itemi*n+k*b.ite
13、mk*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;im
14、;i+)for(j=0;jn;j+)coutsetw(5)itemi*n+j;coutendl;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*this;23互动环节：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
15、;jz3=jz1.tran();jz3.prnt();jz4=jz1.plus(jz2);jz4.prnt();jz5=jz1.mult(jz3);jz5.prnt();程序的运行结果如下：5 9 2 07 0 8 43 4 1 3-10 14 6 18 0 8 4 16 2 0 8 6 -83 57 69 3757 97 22 1269 22 69 3537 12 35 25-24矩阵的压缩存储对称矩阵 若一个n阶方阵A的元素满足性质Ai,j=Aj,i，则称该矩阵为n阶对称矩阵。对角矩阵 所谓对角矩阵是指矩阵的所有非零元素都集中在以主对角线为中心的带状区域中。稀疏矩阵 若在一个矩阵中，零元素
16、的个数相对于整个矩阵元素总个数所占比例较大，则可认为该矩阵是稀疏矩阵。25对称矩阵的压缩存储仅存放对称矩阵的下三角元素 由于下标序号从0开始，Aij处于第i+1行，其前i行元素的个数为i*(i+1)/2，所以Aij在一维数组排列中的序号为i*(i+1)/2+j。A的任意一个元素ai,j在一维数组中的序号为k，其中 26对角矩阵的压缩存储在三对角矩阵B中，除第一行和最后一行只有两个非零元素外，其它每行中各有三个非零元素；而且第i行(0 in)的前i1个元素为零。由于第0行有2个元素，第1行到第i-1行的元素个数为(i1)3，而Bij在第i行中的序号为j(i1)，因此，B中非零元素Bij在该一维数
17、组中的位置k可计算如下(1in)：k2(i1)3j(i1)2ij27稀疏矩阵的压缩存储只存储非零元素三元组(row，col，value)例如对于非零元素2，其三元组表示为(0,0,2)28如果以顺序存储结构来表示三元组线性表，则可得到稀疏矩阵的三元组表压缩存储方式。例如，三元组表rowcolvalue0020661342274012449575稀疏矩阵的压缩存储29const maxlen=三元组表允许的最大长度；typedef struct int row,col;float value;RCV;typedef struct int r,c,num;RCV itemmaxlen;SMatri
18、x;其中r,c,num分别表示稀疏矩阵的行数、列数和非零元个数,item域中表示的非零元的三元组是以行序排列的。三元组表数据类型的定义30struct 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&tran1();SMatrix&plus(SMatrix&b);SMatrix&mult(SMatrix&b);void
19、 prnt();稀疏矩阵类定义 31lSMatrix()无参数，仅创建一个空的三元组表。lSMatrix(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;ic;i+)for(j=0;jnum;j
20、+)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+n
21、umcol-1;(2col ma0.j)1357889colnumcolcpotcol1222324150617037稀疏矩阵快速转置SMatrix&tran1()功能:使用快速转置法计算并返回当前矩阵的转置矩阵；处理过程：(1)创建一个稀疏矩阵x，形成x的r,c,num，并按指定的长度分配存储空间。(2)求当前矩阵中各列非零元的个数，将结果存入数组rnum。(3)求结果矩阵中各行起始位置，将结果存入数组rstart。(4)依次扫描当前矩阵中的三元组表，对每一个三元组行列置换后按原列号col存入x中由rstartcol指示的位置，并使其位置加1。(5)返回结果矩阵x。38稀疏矩阵快速转置形成数
22、组rnum；for(i=0;ic;i+)rnumi=0;for(i=0;inum;i+)rnumitemi.col+;形成数组rstart；rstart0=0;for(i=1;ic;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;ic;i+)rnumi=0;for(i=0;inum;i+)rnumitemi.col+;r
23、start0=0;for(i=1;ic;i+)rstarti=rnumi-1+rstarti-1;for(i=0;inum;i+)j=itemi.col;x.itemrstartj.row=j;x.itemrstartj.col=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 v0 1 2 3 4 5 6 7 8mai j v0 1 2 3 4 5 6 7 8mbcolnumcolcpotcol1122323524715806817907 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 pppppppp4629753