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

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，其中每个数据元素具有相同数据类型。 结构关系：数组元素呈线性结构，且限定数组元素必须存储在地址连续的内存单元中。 基本操作：对数组可执行以下的基本操作。 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,5,数组类构造函数与赋值函数,Array(int sz=100) if(sz,6,数组类构造函数与赋值函数,Array ,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;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) 其中每一个数据元素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,二维数组的存储结构,按行排列 排列方式 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)L0inj,12,二维数组的存储结构,按列排列 排列方式 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 Matrix private: float *item; int m,n; public: Matrix()item=NULL; m=0; n=0; Matrix(float a, int row, int col); Matrix(Matrix,将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,15,矩阵转置,Matrix 要注意的是由于函数的返回类型是对象的引用，所以不能返回局部对象或无名对象，而只能是当前对象或new创建的对象。,16,矩阵相加,Matrix& plus(Matrix& b) 功能:返回当前矩阵与b相加后的矩阵， 处理过程： (1)若二矩阵的行、列数不等，则显示出错信息；否则 (2)创建一个矩阵类的对象x并按当前矩阵设置其行数与列数； 将二矩阵对应的元素相加后存入x并返回x。,17,矩阵相加,Matrix,18,矩阵相乘,设两个行列数分别为ml和ln的矩阵A、B，则 乘积矩阵C中的元素Ci,j满足以下等式： 例如：,19,矩阵相乘,Matrix& mult(Matrix& b) 功能:返回当前矩阵与b相乘后的矩阵。 处理过程： (1) 若当前矩阵的列数不等于矩阵b的行数，则显示出 错信息，否则： (2) 创建一个矩阵对象x并按结果矩阵设置行数与列数，按公式求出其中的每一个元素并返回该矩阵。,20,矩阵相乘,Matrix,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;i+ ) for (j=0;jn;j+ ) coutsetw(5)itemi*n+j; coutendl; ; cout“-“endl; ; Matrix,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; 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开始，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在该一维数组中的位置k 可计算如下(1in)： k2(i1)3j(i1)2ij,27,稀疏矩阵的压缩存储,只存储非零元素 三元组(row，col，value) 例如对于非零元素2，其三元组表示为(0,0,2),28,如果以顺序存储结构来表示三元组线性表，则可得 到稀疏矩阵的三元组表压缩存储方式。 例如，三元组表,稀疏矩阵的压缩存储,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,稀疏矩阵类定义,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;inum;i+) itemi=ai; ;,稀疏矩阵类的构造函数,32,稀疏矩阵的转置操作,a.item b.item,33,稀疏矩阵的转置操作,SMatrix& tran() 功能:返回当前矩阵对象的转置矩阵，按以下过程处理： (1)创建一个稀疏矩阵x，形成x的r, c, num，并按指定的长度分配存储空间。 (2)按当前矩阵的列（即x的行）进行循环处理：对当前矩阵的每一列扫描一次三元组，找出相应的元素，交换其行号与列号并添加到转置矩阵x的三元组表中。 (3)返回结果矩阵x。,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,i=1,i=2,35,稀疏矩阵的转置操作程序代码,SMatrix ,上述算法中要进行二重循环，算法的效率比较低 方法二：快速转置 即按ma中三元组次序转置，转置结果放入b中恰当位置此法关键是要预先确定M中每一列第一个非零元在mb中位置，为确定这些位置，转置前应先求得M的每一列中非零元个数,实现：设两个数组 numcol：表示矩阵M中第col列中非零元个数 cpotcol：指示M中第col列第一个非零元在mb中位置 显然有：,1,3,5,7,8,8,9,37,稀疏矩阵快速转置,SMatrix& tran1() 功能:使用快速转置法计算并返回当前矩阵的转置矩阵； 处理过程： (1)创建一个稀疏矩阵x，形成x的r, c, num，并按指定的长度分配存储空间。 (2)求当前矩阵中各列非零元的个数，将结果存入数组rnum。 (3)求结果矩阵中各行起始位置，将结果存入数组rstart。 (4)依次扫描当前矩阵中的三元组表，对每一个三元组行列置换后按原列号col存入x中由rstartc