第4章数据结构的 多维数组和广义表（优选课资）

1、Data Structurelimin_limin_2012.11.112012.11.11Data Structure111110111110100100.nmmmnnnmaaaaaaaaaAData 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)LData Structure01m-1m-1*n-1m am-1n-1

2、 . a1n-1 a0n-1 am-11 . a11 a01 am-10 . 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 Structure 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)LLOC(j1,j2,j3)=LOC(0,0,0)+(b2*b3*j1+b3*j2+j3)L LOC(j1,j2,j

3、n)=LOC(0,0,0)+(b2*bn*j1 + b3*bn*j2 + + bn*jn-1 + jn)L LOC(j1,j2,jn) = LOC(0,0,0) +1niiic j1,1niiicL cbcin 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. A

4、0,0,0 +198*L B. A0,0,0 + 108*L C. A0,0,0 + 268*L D. A0,0,0 + 13*LCData Structure 矩阵是科学与工程计算问题中研究的数学对象，在矩阵中会出现许多值相同的元素或者零元素，为了节省存储空间，可以对矩阵进行压缩存储。 压缩存储是指为多个值相同的元只分配一个存储空间，对零元不分配空间。 特殊矩阵：值相同的元素或者零元素在矩阵中的分布有一定规律。 特殊矩阵包括：对角矩阵、对称矩阵和三角矩阵等。Data Structure a11 a12 . . a1n a21 a22 .a2n an1 an2 . ann . 按行序为主序：a

5、11 a21 a22 a31 a32 an1 ann . k=0 1 2 3 4 n(n-1)/2 n(n+1)/2-1 jiijjjijiik, 12/ ) 1(12/ ) 1(，Data Structure按行序为主序：Loc( aij)=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

6、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 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. 220

7、9BData Structure 将一个A1100,1100的对换矩阵，按行优先次存入矩阵中下三角的所有元素，起始位置为1，每个元素所占空间大小为1，则A中元素A65,66在B中的位置 为 。 A. 2276 B. 2210 C. 2275 D. 2209BData Structure 将一个A1100,1100的三对角矩阵，按行优先次存入一个一维数组B1298中，A中元素A66,65在B中的位置 k 为 。 A. 198 B. 195 C. 196 D. 197BData Structure 假设在m*n的矩阵中，有 t 个元素不为零，令 ，称为矩阵的稀疏因子，当 时称为稀疏矩阵。 稀疏矩阵

8、应该如何存储呢？稀疏矩阵中每个元素可以通过行列位置和元素值来唯一确定，一个三元组（ i , j , aij ）唯一确定稀疏矩阵中的一个非零元，加上矩阵的行数、列数、非零元个数就可以唯一确定一个稀疏矩阵。nmt05. 0Data Structure7600070015000001800000240001400003000000000009120M6 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 8Data Structure7600070015000001800000240001400003000000000009120M6700000000014000000007000000024009018000121500300*TData 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