数据结构_数组-副本.pptVIP

数据结构 数组 4.1 数组的定义 数组是我们最熟悉的数据类型，在早期的高级语言中，数组是唯一可供使用的数据类型。由于数组中各元素具有统一的类型，并且数组元素的下标一般具有固定的上界和下界，因此，数组的处理比其它复杂的结构更为简单 4.1 数组的定义 多维数组是向量的推广。例如，二维数组： a00 a01 … … … a0n-1 a10 a11 … … … a1n-1 … … … … … … … … am-10 am-11 … am-1n-1 Amn= 可以看成是由m个行向量组成的向量，也可以看成是n个列向量组成的向量。 4.1 数组的定义 4.2 数组的顺序表示和实现 由于计算机的内存结构是一维的，因此用一维内存来表示多维数组，就必须按某种次序将数组元素排成一列序列，然后将这个线性序列存放在存储器中。 又由于对数组一般不做插入和删除操作，也就是说，数组一旦建立，结构中的元素个数和元素间的关系就不再发生变化。因此，一般都是采用顺序存储的方法来表示数组。 4.2 数组的顺序表示和实现 ⑴行优先顺序——将数组元素按行排列，第i+1个行向量紧接在第i个行向量后面。以二维数组为例，按行优先顺序存储的线性序列为： ⑵列优先顺序——将数组元素按列向量排列，第j+1个列向量紧接在第j个列向量之后，按列优先顺序存储的线性序列为： a0,1 a0,0 a0,2 a1,0 a1,1 a1,2 a0,1 a0,0 a0,2 a1,0 a1,1 a1,2 d a1,0 a0,0 a2,0 a2,1 a0,1 a1,1 a1,0 a0,0 a2,0 a0,1 a1,1 a2,1 d 例如，二维数组Amn按“行优先顺序”存储在内存中，假设每个元素占用d个存储单元。 元素aij的存储地址应是数组的基地址加上排在aij前面的元素所占用的单元数。因为aij位于第i行、第j列，前面i-1行一共有i×n个元素，第i行上aij前面又有j个元素，故它前面一共有(i×n+j）个元素，因此，aij的地址计算函数为： LOC(aij)=LOC(a00)+[i*n+j]*d (0≤im， 0≤jn) 注：C语言中数组元素采用行主序的存放方法，即行优先顺序。 一个m×n的二维数组可以看成是m行的一维数组，或者n列的一维数组。 a0,0 a0,1 … a0,n-1 a1,0 a1,1 … a1,n-1 … … … … am-1,0 am-1,1 … am-1,n-1 Amn= 4.2 数组的顺序表示和实现 4.2 数组的顺序表示和实现 同样，三维数组Aijk按“行优先顺序”存储，其地址计算函数为： LOC(aijk)=LOC(a000)+[i×n×p+j×p+k]×d 注：只要知道以下三要素便可随时求出任一元素的地址（意义：数组中的任一元素可随机存取）①开始结点的存放地址（即基地址）；②维数和每维的上、下界；③每个数组元素所占用的单元数 例１：一个二维数组A，行下标的范围是1到6，列下标的范围是0到7，每个数组元素用相邻的6个字节存储，存储器按字节编址。那么，这个数组的体积是 多少个字节。 答： Volume=m*n*L=(6-1+1)*(7- 0 +1)*6=48*6=288 例２ 设数组a[０…60, ０…70]的基地址为2048，每个元素占2个存储单元，若以行序为主序顺序存储，则元素a[32,58]的存储地址？ 答：根据行优先公式 LOC(aij)=LOC(a00)+(i*n+j)*k (0≤im，0≤jn) 　　得：LOC(a32,58)=2048+(32*70+58)*2＝6644 5.3 数组的压缩存储 所谓特殊矩阵是指非零元素或零元素的分布有一定规律的矩阵，下面我们讨论几种特殊矩阵的压缩存储。 5.3.1 特殊矩阵 5.3.2 稀疏矩阵 5.3.1 特殊矩阵 5.3 数组的压缩存储 1、对称矩阵 在一个n阶方阵A中，若元素满足下述性质： aij=aji （0≦i,j≦n-1） 则称A为对称矩阵。如图5.1便是一个5阶对称矩阵。 5.3.1 特殊矩阵 5.3 数组的压缩存