数据结构——二维数组.ppt
《数据结构——二维数组.ppt》由会员分享,可在线阅读,更多相关《数据结构——二维数组.ppt(40页珍藏版)》请在得力文库 - 分享文档赚钱的网站上搜索。
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的行
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 数据结构 二维 数组
限制150内