资源描述：
《第10讲 数组和矩阵.ppt》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、Chapter5数组和广义表数组的定义、顺序表示和实现矩阵的压缩存储广义表的定义、存储结构§5.1数组的ADT定义ADTArray{}ADTArray数据对象：数据关系：基本操作：InitArray(&A,n,b1,…,bn)DestroyArray(&A)Value(A,&e,index1,…,indexn)Assign(&A,e,index1,…,indexn)当n＝1时，n维数组就退化为定长的线性表反之，n维数组可以看作线性表的推广例如，二维数组可以看作元素是线性表的线性表§5.2数组的顺
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……思考：如何计算数组元素的地址？例子：假设有二维数组A6×8，每个元素用相邻的6个字节存储，存储器按字节编址。已知A的起始存储位置为1000，计算：1）
3、数组A的体积（即所占字节数）？2）数组A的最后一个元素如何表示？其地址为？3）按行存储时，元素a14的地址？4）按列存储时，元素a47的地址？练习：5）按列存储时，元素a14的地址？6）按行存储时，元素a47的地址？§5.3矩阵的压缩存储矩阵广泛应用于科学与工程计算问题中有些程序语言提供了各种矩阵运算e.g.Matlab研究目的：如何存储矩阵使得空间更节省、运算更有效。研究内容：1.特殊矩阵2.稀疏矩阵5.3.1特殊矩阵的压缩存储特殊矩阵：值相同的元素或零元素在矩阵中的分布有一定规律的矩阵。e.
4、g.对称矩阵，三角矩阵，对角矩阵对称矩阵的压缩存储为每一对对称元素分配一个存储空间。其中，aij＝aji思考：1.n阶对称矩阵压缩存储所需存储单元总数？a11a21a22a31…an,1…an,n0123…2.以一维数组sa[n(n+1/2)]存储对称矩阵An×n，如何确定aij和sa[k]的对应关系？sa：ADTSparseMatrix{数据对象：D={aij
5、i=1,..,m,j=1,…,n;aij∈ElemSet}数据关系：R={Row,Col}基本操作：}ADTSparseMatrix5
6、.3.2稀疏矩阵的压缩存储稀疏矩阵：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,a
7、ij)唯一确定矩阵A的一个非零元。矩阵的另一种描述方法：三元组表+行列数1）三元组顺序表（顺序存储结构）#defineMAXSIZE10000//非0元个数的最大值typedefstruct{inti,j;ElemTypee;}Triple;typedefstruct{Tripledata[MAXSIZE+1];//非0元三元组表，data[0]未用intmu,nu,tu;//矩阵的行数、列数、非0元个数}TSMatrix;三元组顺序表的存储表示三元组以行序为主序排列转置运算转置1.写出M的三元
8、组顺序表。2.思考如何实现M的转置？三元组顺序表求转置StatusTransposeSMatrix(TSMatrixM,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;p<=M.tu;p++)if(M.data[p].j==row){T.data[q].i=M.data[p].j;T.data[q].j=M.data[p].i;T.data[q].e=M.data[p
9、].e;q++;}}retrurnOK;}作业1设数组a[0..20,2..15]的基址为2000，每个元素占2个存储单元，若以行序为主序存储则元素a[8,12]的地址是多少？若按列序存储则其地址是多少？假设稀疏矩阵A和B（具有相同的大小）都采用三元组顺序表表示，编写一个函数计算C=A+B，要求C也采用三元组顺序表表示。作业2（上机检验）设计并实现矩阵类型。基本要求：1）矩阵类型的基本操作包括矩阵的初始化、销毁、置为单元矩阵、元素赋值、读取指定元素、矩阵相加、矩阵的转置、矩阵的数乘。2）实现演示
