答是要 2.1数组的定义 2.2数组的版序表示与实现 2.3距阵的压缩存储
内容提要 2.1 数组的定义 2.2 数组的顺序表示与实现 2.3 距阵的压缩存储
21数组 数组:相同类型数据的有序集合。是数据结构中最 基本的结构类型 数组的操作: 通过给定下标取出相应元素的值 通过给定下标修改相应元素的值 数组只有顺序存储结构,多维数组实际 上也是按照一维数组存放的 二维数组aNIM]中每个单元占有L个字节,那么a 的存储位置 组的 Loc(ai=Loc(aoo+(M+j*L akiko.k 三维数组aPNM中每单元占个字的存情位 的存储位置: Loc(aik=Loc(a000)+(i N*M+j*M+k)I
2.1 数组 数组：相同类型数据的有序集合。是数据结构中最 基本的结构类型 数组的操作： 通过给定下标取出相应元素的值 通过给定下标修改相应元素的值 数组只有顺序存储结构，多维数组实际 上也是按照一维数组存放的 二维数组a[N][M]中每个单元占有L个字节，那么a[i][j] 的存储位置： Loc(aij)=Loc(a00)+(i*M+j)*L 三维数组a[P][N][M]中每单元占L个字节，那么a[i][j][k] 的存储位置： Loc(aijk)=Loc(a000)+(i*N*M+j*M+k)*L n维数组的 a[k1][k2]..[kn] 的存储位置 如何求？
2数组的顺表示与线现 数组的顺序表示 ∥---数组的版序存信表示 include <stdarg. h> ∥|准头文件提供宏 va start, va arg 和 va end,用于存取变长参数表 # define maX Array dim8∥假设数组维数的最大值为8 ty pede struct t ElemType‘base; ∥数组元素基址,由 InitArray分配 int dim ∥/数组维数 int bounds;∥数组维界基址,由 nitArray分配 int constants;∥/数组映象函数常量基址, ∥/由 nitArray分配 Array 数组的顺序实现(见书P93)
2.2 数组的顺序表示与实现 数组的顺序表示 //---------数组的顺序存储表示----------- #include <stdarg.h> // 标准头文件,提供宏va_start,va_arg // 和va_end，用于存取变长参数表 #define MAX_ARRAY_DIM 8 // 假设数组维数的最大值为8 typedef struct { ElemType *base; // 数组元素基址，由InitArray分配 int dim; // 数组维数 int *bounds; // 数组维界基址，由InitArray分配 int *constants; // 数组映象函数常量基址， // 由InitArray分配 }Array; 数组的顺序实现（见书 P93）
23的的纺在 利用数组猜存信矩阵|a0a1C 20a21a22 a04020320以压缩存储的矩阵夕 a30 a31 a32 a33 10a11a2a31 特殊矩阵 三角矩阵 a20a21a2a32 (1)三角矩阵 00c01 30 a31 a32 a33 )对称矩阵 10a11a12 对称矩阵 (3)带状矩阵 a21 a22 a 2、稀疏矩阵 a32 a33 NxM个单元中,只有T个非 带状矩阵 零元素,当T/N×M)<=0.05时, 就是稀疏矩阵
2.3 距阵的压缩存储 利用数组压缩存储矩阵 可以压缩存储的矩阵有两种： 1、特殊矩阵 (1)三角矩阵 (2)对称矩阵 (3)带状矩阵 2、稀疏矩阵 NM个单元中，只有T个非 零元素，当T/(N M)<=0.05时， 就是稀疏矩阵。 a00 a10 a11 C a20 a21 a22 a30 a31 a32 a33 下三角矩阵 a00 a10 a20 a30 a10 a11 a21 a31 a20 a21 a22 a32 a30 a31 a32 a33 对称矩阵 a00 a01 a10 a11 a12 a21 a22 a23 a32 a33 带状矩阵
的的能cm (1)三角矩阵的压缩存储 需要将矩阵中的三角区域的数据按照顺序存放 到一维数组中即可,关键的问题是确定矩阵的两个 下标团与一维数组的下标的对应关系: 以上三角矩阵为例,A[=前面的元素个数 是: N+N-1+N-2+.+N+1=(2N-+1)2 在本行前面有i个元素,因此,在一维数组中, A[的位置:k=1(2N-+1)2+i ao0 a01 a02 a03 11a12a13 ooao1 a02 a12a13a22a23a a 33
距阵的压缩存储(cont’d) (1)三角矩阵的压缩存储 只需要将矩阵中的三角区域的数据按照顺序存放 到一维数组中即可，关键的问题是确定矩阵的两个 下标[i][j]与一维数组的下标[k]的对应关系： 以上三角矩阵为例，A[i][j](j>=i)前面的元素个数 是： N+N-1+N-2+…+N-i+1=i*(2N-i+1)/2 在本行前面有j-i个元素，因此，在一维数组中， A[i][j]的位置：k= i*(2N-i+1)/2+j-i a00 a01 a02 a03 a11 a12 a13 a22 a23 a33 a00 a01 a02 a03 a11 a12 a13 a22 a23 a33