数据结构的多维数组和广义表.ppt

《数据结构的多维数组和广义表.ppt》由会员分享，可在线阅读，更多相关《数据结构的多维数组和广义表.ppt（19页珍藏版）》请在得力文库 - 分享文档赚钱的网站上搜索。

1、Data Structure数 据 结 构课程代码课程代码23312331Data Structure二维数组Data Structure a00 a01 a0n-1 a10 a11 a1n-1 am-1,0 am-1,1 am-1,n-1 .am-1,n-1 .am-1,1 am-1,0 .a1n-1 .a11 a10 a0n-1 .a01 a0001n-1m-1*n-1nLOC(i,j)=LOC(0,0)+(nij)L按行序为主序存放Data Structure按列序为主序存放01m-1m-1*n-1m am-1n-1 .a1n-1 a0n-1 am-11 .a11 a01 am-10 .

2、a10 a00 a00 a01 .a0n-1 a10 a11 .a1n-1 am-10 am-11 am-1n-1 .LOC(i,j)=LOC(0,0)+(mji)LData Structureb1*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

3、(j1,j2,jn)=LOC(0,0,0)+Data Structure我们来练习一下数组A15,16的每个元素占5字节，将其按行优先次序存储在起始地址为1000的内存单元中，则元素A5,5的地址是 。A.1140 B.1145 C.1120 D.1125AData Structure我们来练习一下三维数组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*LCData Structure矩阵的压缩存储矩阵

4、是科学与工程计算问题中研究的数学对象，在矩阵中会出现许多值相同的元素或者零元素，为了节省存储空间，可以对矩阵进行压缩存储。压缩存储是指为多个值相同的元只分配一个存储空间，对零元不分配空间。特殊矩阵：值相同的元素或者零元素在矩阵中的分布有一定规律。特殊矩阵包括：对角矩阵、对称矩阵和三角矩阵等。Data Structure对称矩阵 a11 a12 .a1n a21 a22 .a2n an1 an2 .ann .按行序为主序：a11 a21 a22 a31 a32 an1 ann.k=0 1 2 3 4 n(n-1)/2 n(n+1)/2-1 Data Structure按行序为主序：Loc(aij

5、)=Loc(a11)+i*(i-1)/2+(j-1)*L a11 0 0.0 a21 a22 0.0 an1 an2 an3.ann .0a11 a21 a22 a31 a32 an1 ann.k=0 1 2 3 4 n(n-1)/2 n(n+1)/2-1 三角矩阵Data Structure a00 a01 0 .0 a10 a11 a12 0 0 0 0 an-2,n-3 an-2,n-2 an-1,n-1 0 0 an-1,n-2 an-1,n-1 0 a21 a22 a23 0 0 Loc(aij)=Loc(a00)+2(i-1)+(j-1)按行序为主序：a00 a01 a10 a11

6、 a12 an-1n-2 an-1n-1.k=0 1 2 3 4 n(n+1)/2-1 对角矩阵Data Structure我们来练习一下将一个A1100,1100的三角矩阵，按行优先次存入矩阵中下三角的所有元素，起始位置为1，每个元素所占空间大小为1，则A中元素A66,65在B中的位置 为 。A.2276 B.2210 C.2275 D.2209BData Structure我们来练习一下将一个A1100,1100的对换矩阵，按行优先次存入矩阵中下三角的所有元素，起始位置为1，每个元素所占空间大小为1，则A中元素A65,66在B中的位置 为 。A.2276 B.2210 C.2275 D.2

7、209BData Structure我们来练习一下将一个A1100,1100的三对角矩阵，按行优先次存入一个一维数组B1298中，A中元素A66,65在B中的位置 k 为 。A.198 B.195 C.196 D.197BData Structure稀疏矩阵假设在m*n的矩阵中，有 t 个元素不为零，令 ，称为矩阵的稀疏因子，当 时称为稀疏矩阵。稀疏矩阵应该如何存储呢？稀疏矩阵中每个元素可以通过行列位置和元素值来唯一确定，一个三元组（i,j,aij）唯一确定稀疏矩阵中的一个非零元，加上矩阵的行数、列数、非零元个数就可以唯一确定一个稀疏矩阵。Data Structure稀疏矩阵6 7 8 1 2

8、 12 1 3 9 3 1 -3 3 6 14 4 3 24 5 2 18 6 1 15 6 4 -7 i j e0 1 2 3 4 5 6 7 8Data Structure6700000000014000000007000000024009018000121500300*-=T稀疏矩阵的转置Data Structure6 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 e0 1 2 3 4 5 6 7 8i j e7 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.dataT.dataData Structure广义表广义表广义表：广义表：n(n0)个元素个元素 a1,a2,an 的有限序列，其中的有限序列，其中ai或或者是原子或者是一个广者是原子或者是一个广义义表。表。表表头头：a1表尾：除表尾：除a1外其余元素外其余元素组组成的成的表表广广义义表的两个特殊基本运算表的两个特殊基本运算取表取表头头取表尾取表尾