数据结构之数组与广义表课件.ppt

第5章 数组与广义表 5.1 数组 5.1.1 数组的定义 数组是由n个相同类型的元素组成的有序序列，并存储在一个连续的空间中。 数组的特点： 元素类型必须相同； 可对每一个元素随机访问, 数组中的元素个数是固定的。 数组分为一维数组和多维数组 一维数组 如: A[10] (1行,共10个元素) 二维数组 如: B[3][4] (3行4列, 共12个元素) 5.1.2 数组的顺序存储 在计算机中，数组是按一定的规则存储在一个连续的地址空间中. 可以用下标随机的访问该数组的任意一个元素。 计算数组元素存储地址的公式称为寻址公式。 设数组为A，每个数组元素占k个存储单元，一旦定义了它的维数和各维的上、下界，就可以得到数组中任一元素的寻址公式。 1. 一维数组的寻址公式 对于一维数组，若其第一个元素的首地址为Loc(a0)，下标为 i 的数组元素A[i]的地址为Loc(ai)， 则 Loc(ai) = Loc(a0) + k * i ( 0≤i≤n-1) 2. 二维数组的寻址公式 二维数组分为以行为主序存储和以行为主序存储. 在C语言中，采用以行为主序存储 在FORTRAN语言中，采用以列为主序存储 设二维数组A[m][n]，m、n分别表示数组的行数和列数，用 Loc (aij)表示数组元素A[i][j]的地址. 设每个元素占用k个存储单元，则寻址公式为: 若以行为主序，则 Loc(ai,j) = Loc(a00) + (i*n+j)*k 若以列为主序，则 Loc(ai,j) = Loc(a00) + (j*m+i)*k [注]:假设数组从0开始编址. 例：二维数组A[5, 6]，设每一元素占32位，若以行序为主序存储， 1. 数组A共占多少个字节? 2. 若A的起始地址是1000，A[2,5]的地 址是多少？ 解：1. 共有30个元素 30*4=120 个字节 2. Loc[2,5]=loc[0,0]+(2*6+5)*4 =1068 5.2 特殊矩阵的压缩存储 1. 对称矩阵的压缩存储 一个n阶矩阵，满足 A[i,j]=A[j,i] 则称为对称矩阵。 例： 1 5 1 3 7 5 0 8 0 0 A= 1 8 9 2 6 3 0 2 5 1 7 0 6 1 3 对称矩阵有n*n个元素，但只存储n*(n+1)/2个元素即可. 若以行序为主序，把下三角中的元素，存储在一个一维数组SA[n*(n+1)/2] 中，则 A[i,j] 和SA[k] 的对应关系如下： 若 i=j , 则A[i, j]在下三角中，A[i, j]之前共有1+2+……+i+j = i*(i+1)/2+j 个元素，因此有 k= i*(i+1)/2 + j [注]:假定矩阵的行和列从0开始, 一维数组的编址从0开始. 若 ij , 则A[i, j]在上三角中，因为A[i,j]=A[j,i], 所以交换上述公式中的i和j即可,因此有 k= j*(j+1)/2 + i 上页的矩阵对应的一维数组如下： 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 A[3,0]对应的地址：k=3*4/2+0=6 A[2,4]对应的地址：k=4*5/2+2=12 2. 三角矩阵的压缩存储 三角矩阵: 矩阵的上(下)三角(不包含主 角线)元素为同一个常数的方阵. 我们可用对称矩阵存储的思想存储之.