《数据结构的多维数组和广义表.ppt》由会员分享，可在线阅读，更多相关《数据结构的多维数组和广义表.ppt（19页珍藏版）》请在三一办公上搜索。
1、数 据 结 构课程代码2331,二维数组,LOC(i,j)=LOC(0,0)+(nij)L,按行序为主序存放,按列序为主序存放,LOC(i,j)=LOC(0,0)+(mji)L,b1*b2的二维数组LOC(i,j)=LOC(0,0)+(b2*i+j)Lb1*b2*b3的三维数组LOC(i,j,k)=LOC(0,0,0)+(b2*b3*i+b3*j+k)LLOC(j1,j2,j3)=LOC(0,0,0)+(b2*b3*j1+b3*j2+j3)LLOC(j1,j2,jn)=LOC(0,0,0)+(b2*bn*j1+b3*bn*j2+bn*jn-1+jn)LLOC(j1,j2,jn)=LOC(0,0
2、,0)+,我们来练习一下,数组A15,16的每个元素占5字节，将其按行优先次序存储在起始地址为1000的内存单元中，则元素A5,5的地址是。A.1140 B.1145 C.1120 D.1125,A,我们来练习一下,三维数组A8,8,10采用行主序的方式从地址A0,0,0开始存放，问：A3,2,8的存放位置为。假设每个数组元素占用存储空间大小为L。A.A0,0,0+198*L B.A0,0,0+108*L C.A0,0,0+268*L D.A0,0,0+13*L,C,矩阵的压缩存储,矩阵是科学与工程计算问题中研究的数学对象，在矩阵中会出现许多值相同的元素或者零元素，为了节省存储空间，可以对矩阵
3、进行压缩存储。压缩存储是指为多个值相同的元只分配一个存储空间，对零元不分配空间。特殊矩阵：值相同的元素或者零元素在矩阵中的分布有一定规律。特殊矩阵包括：对角矩阵、对称矩阵和三角矩阵等。,对称矩阵,按行序为主序：,按行序为主序：,Loc(aij)=Loc(a11)+i*(i-1)/2+(j-1)*L,三角矩阵,Loc(aij)=Loc(a00)+2(i-1)+(j-1),按行序为主序：,a00 a01 a10 a11 a12 an-1n-2 an-1n-1,.,.,k=0 1 2 3 4 n(n+1)/2-1,对角矩阵,我们来练习一下,将一个A1100,1100的三角矩阵，按行优先次存入矩阵中下
4、三角的所有元素，起始位置为1，每个元素所占空间大小为1，则A中元素A66,65在B中的位置 为。A.2276 B.2210 C.2275 D.2209,B,我们来练习一下,将一个A1100,1100的对换矩阵，按行优先次存入矩阵中下三角的所有元素，起始位置为1，每个元素所占空间大小为1，则A中元素A65,66在B中的位置 为。A.2276 B.2210 C.2275 D.2209,B,我们来练习一下,将一个A1100,1100的三对角矩阵，按行优先次存入一个一维数组B1298中，A中元素A66,65在B中的位置 k 为。A.198 B.195 C.196 D.197,B,稀疏矩阵,假设在m*n
5、的矩阵中，有 t 个元素不为零，令，称为矩阵的稀疏因子，当 时称为稀疏矩阵。稀疏矩阵应该如何存储呢？稀疏矩阵中每个元素可以通过行列位置和元素值来唯一确定，一个三元组（i,j,aij）唯一确定稀疏矩阵中的一个非零元，加上矩阵的行数、列数、非零元个数就可以唯一确定一个稀疏矩阵。,稀疏矩阵,稀疏矩阵的转置,6 7 8,1 2 12,1 3 9,3 1-3,3 6 14,4 3 24,5 2 18,6 1 15,6 4-7,i j e,0 1 2 3 4 5 6 7 8,i j e,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,0 1 2 3 4 5 6 7 8,M.data,T.data,广义表,广义表：n(n0)个元素 a1,a2,an 的有限序列，其中ai或者是原子或者是一个广义表。表头：a1表尾：除a1外其余元素组成的表广义表的两个特殊基本运算取表头取表尾,
