第10讲 数组和矩阵.ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,单击此处编辑母版标题样式,Chapter 5,数组和广义表,数组的定义、顺序表示和实现,矩阵的压缩存储,广义表的定义、存储结构,5.1,数组的,ADT,定义,ADT Array,ADT Array,数据对象：,数据关系：,基本操作：,InitArray(&A,n,b1,bn,),DestroyArray(&A,),Value(A,&e,index1,indexn,),Assign(&A,e,index1,indexn,),当,n1,时，,n,维数组就退化为定长的线性表,反之，,n,维数组可以看作线性表的推广,例如，二维数组可以看作元素是线性表的线性表,5.2,数组的顺序表示和实现,二维数组的存储：,以行序为主序,(e.g.BASIC,、,PASCAL,、,C),以列序为主序,(e.g.FORTRAN),第1列,第2列,第,n,列,a,10,a,00,a,m-1,0,a,01,a,11,a,m-1,1,a,0,n-1,a,1,n-1,a,m-1,n-1,第1行,第2行,第,m,行,a,01,a,00,a,0,n-1,a,10,a,11,a,1,n-1,a,m-1,0,a,m-1,1,a,m-1,n-1,思考：如何计算数组元素的地址？,例子：,假设有二维数组,A,68,，,每个元素用相邻的6个字节存储，存储器按字节编址。已知,A,的起始存储位置为1000，计算：,1）数组,A,的体积（即所占字节数）？,2）数组,A,的最后一个元素如何表示？其地址为？,3）按,行,存储时，元素,a,14,的地址？,4）按,列,存储时，元素,a,47,的地址？,练习：,5）按,列,存储时，元素,a,14,的地址？,6）按,行,存储时，元素,a,47,的地址？,5.3,矩阵的,压缩存储,矩阵广泛应用于科学与工程计算问题中,有些程序语言提供了各种矩阵运算,e.g.,Matlab,研究目的：如何存储矩阵使得空间更节省、运算更有效。,研究内容：1.特殊矩阵,2.稀疏矩阵,5.3.1,特殊矩阵,的压缩存储,特殊矩阵：值相同的元素或零元素在矩阵中的分布有一定规律的矩阵。,e.g.,对称矩阵，三角矩阵，对角矩阵,对称矩阵的压缩存储,为,每一对,对称元素分配,一个,存储空间。,其中，,a,ij,a,ji,思考：,1.n,阶对称矩阵压缩存储所需存储单元总数？,a,11,a,21,a,22,a,31,a,n,1,a,n,n,0 1 2 3 ,2.,以一维数组,san(n+1/2),存储对称矩阵,A,nn,，如何确定,a,ij,和,sak,的对应关系？,sa,：,ADT,SparseMatrix,数据对象：,D=,a,ij,|i=1,.,m,j=1,n;,a,ij,ElemSet,数据关系：,R=Row,Col,基本操作：,ADT,SparseMatrix,5.3.2,稀疏矩阵,的压缩存储,稀疏矩阵：0元个数,远大于,非0元个数。,稀疏因子：,CreateSMatrix(&M,);,DestroySMatrix(&M,);,PrintSMatrix(M,);,CopySMatrix(M,AddSMatrix(M,N,SubSMatrix(M,N,MultSMatrix(M,N,TransposeSMatrix(M,如何实现稀疏矩阵的压缩存储？,按照压缩存储的概念，只存储稀疏矩阵的,非零元,：,包括,值,和它的,位置,(,i,j)；,反之，三元组,(,i,j,a,ij,),唯一确定矩阵,A,的一个非零元。,矩阵的另一种描述方法：,三元组表,+,行列数,1）三元组顺序表（顺序存储结构）,#,define MAXSIZE 10000,/,非0元个数的最大值,typedef,struct,int,i,j;,ElemType,e;,Triple;,typedef,struct,Triple dataMAXSIZE+1;,/,非,0,元三元组表，,data0,未用,int,mu,nu,tu,;,/,矩阵的行数、列数、非,0,元个数,TSMatrix,;,三元组顺序表的存储表示,三元组以行序为主序排列,转置运算,转置,1.,写出,M,的三元组顺序表。,2.,思考如何实现,M,的转置？,三元组顺序表求转置,Status,TransposeSMatrix(TSMatrix,M,TSMatrix,&T),T.mu,=,M.nu,;,T.nu,=,M.mu,;,T.tu,=,M.tu,;,if(,T.tu,),q=1;,for(row=1;row=,T.mu,;row+),for(p=1;pi=i;p-j=j;p-e=e;,if(,M.rheadi,=,NULL|M.rheadi,-jj),p-right=,M.rheadi;M.rheadi,=p;,else,for(q,=,M.rheadi,;(q-,right)&q,-right-jright);,p-right=q-right;q-right=p;,/,插入对应的行链表,if(,M.cheadj,=,NULL|M.cheadj,-ii),p-down=,M.cheadj,;,M.cheadj,=p;,else for(q=,M.cheadj,;(q-,down)&q,-down-idown);,p-down=q-down;q-down=p;,/,插入对应的列链表,