第10讲 数组和矩阵.ppt
Chapter 5 数组和广义表数组和广义表数组的定义、顺序表示和实现数组的定义、顺序表示和实现矩阵的压缩存储矩阵的压缩存储广义表的定义、存储结构广义表的定义、存储结构5.1 数组的数组的ADTADT定义定义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列列a10a00am-1,0a01a11am-1,1a0,n-1a1,n-1am-1,n-1第第1行行第第2行行第第m行行a01a00a0,n-1a10a11a1,n-1am-1,0am-1,1am-1,n-1思考：如何计算数组元素的地址？思考：如何计算数组元素的地址？例子：例子：假设有二维数组假设有二维数组A68，每个元素用相邻的每个元素用相邻的6个字节个字节存储，存储器按字节编址。已知存储，存储器按字节编址。已知A的起始存储位的起始存储位置为置为1000，计算：，计算：1）数组）数组A的体积（即所占字节数）？的体积（即所占字节数）？2）数组）数组A的最后一个元素如何表示？其地址为？的最后一个元素如何表示？其地址为？3）按）按行行存储时，元素存储时，元素a14的地址？的地址？4）按）按列列存储时，元素存储时，元素a47的地址？的地址？练习：练习：5）按）按列列存储时，元素存储时，元素a14的地址？的地址？6）按）按行行存储时，元素存储时，元素a47的地址？的地址？5.3 矩阵的矩阵的压缩存储压缩存储矩阵广泛应用于科学与工程计算问题中矩阵广泛应用于科学与工程计算问题中 有些程序语言提供了各种矩阵运算有些程序语言提供了各种矩阵运算 e.g.Matlab研究目的：如何存储矩阵使得空间更节省、运算更有效。研究目的：如何存储矩阵使得空间更节省、运算更有效。研究内容：研究内容：1.1.特殊矩阵特殊矩阵 2.2.稀疏矩阵稀疏矩阵5.3.1 5.3.1 特殊矩阵特殊矩阵的压缩存储的压缩存储特殊矩阵：值相同的元素或零元素在矩阵中的分布特殊矩阵：值相同的元素或零元素在矩阵中的分布有一定规律的矩阵。有一定规律的矩阵。e.g.对称矩阵，三角矩阵，对角矩阵对称矩阵，三角矩阵，对角矩阵 对称矩阵的压缩存储对称矩阵的压缩存储 为为每一对每一对对称元素分配对称元素分配一个一个存储空间。存储空间。其中，其中，aijaji思考：思考：1.n阶对称矩阵压缩存储所需存储单元总数？阶对称矩阵压缩存储所需存储单元总数？a11a21a22a31 an,1an,n0 1 2 3 2.以一维数组以一维数组san(n+1/2)存储对称矩阵存储对称矩阵Ann，如何确定如何确定aij和和sak的对应关系？的对应关系？sa：ADT SparseMatrix 数据对象：数据对象：D=aij|i=1,.,m,j=1,n;aij ElemSet 数据关系：数据关系：R=Row,Col 基本操作：基本操作：ADT SparseMatrix5.3.2 5.3.2 稀疏矩阵稀疏矩阵的压缩存储的压缩存储稀疏矩阵：稀疏矩阵：0 0元个数元个数远大于远大于非非0 0元个数。元个数。稀疏因子：稀疏因子：CreateSMatrix(&M);DestroySMatrix(&M);PrintSMatrix(M);CopySMatrix(M,&T);AddSMatrix(M,N,&Q);SubSMatrix(M,N,&Q);MultSMatrix(M,N,&Q);TransposeSMatrix(M,&T);如何实现稀疏矩阵的压缩存储？如何实现稀疏矩阵的压缩存储？按照压缩存储的概念，只存储稀疏矩阵的按照压缩存储的概念，只存储稀疏矩阵的非零元非零元：包括包括值值和它的和它的位置位置(i,j)；反之，三元组反之，三元组(i,j,aij)唯一确定矩阵唯一确定矩阵A的一个非零元。的一个非零元。矩阵的另一种描述方法：矩阵的另一种描述方法：三元组表三元组表 +行列数行列数1 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;/插入对应的列链表插入对应的列链表
