第4章数据结构的 多维数组和广义表

1、数 据 结 构课程代码2331,limin_ 2012.11.11,二维数组,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)L b1*b2*b3的三维数组 LOC(i,j,k)=LOC(0,0,0)+(b2*b3*i+b3*j+k)L LOC(j1,j2,j3)=LOC(0,0,0)+(b2*b3*j1+b3*j2+j3)L LOC(j1,j2,jn)=LOC(0,0,0)+ (b2*bn*j1 + b3*bn*j2

2、 + + bn*jn-1 + jn)L LOC(j1,j2,jn) = LOC(0,0,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,.

4、,.,k=0 1 2 3 4 n(n+1)/2-1,对角矩阵,我们来练习一下,将一个A1100,1100的三角矩阵，按行优先次存入矩阵中下三角的所有元素，起始位置为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的三对角

5、矩阵，按行优先次存入一个一维数组B1298中，A中元素A66,65在B中的位置 k 为 。 A. 198 B. 195 C. 196 D. 197,B,稀疏矩阵,假设在m*n的矩阵中，有 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 (