数据结构第5章数组.pptx

第五章 数组 2 本章目录 5.1 数组的定义与存储 5.2 矩阵的压缩存储 小 结 习 题 3 5.1 数组的定义与存储 数组的顺序存储 2 数组的定义 1 4 数组定义 数组(Array)是由一组类型相同的数据元素构成的有限序列。 若数组只有一个下标，这样的数组称为“一维数组” 。 [a1 a2 a3 … an ] 当数组的每个数据元素含有两个下标时，称该数组为“二维数组” 。 5 二 维 数 组 一个二维数组可以看成是每个数据元素是相同类型的一维数组的一维数组。 6 数组的特性 数据元素具有相同的类型。 am1 am2 …….. amn a11 a12 …….. a1n a21 a22 …….. a2n ………… aij ……. 每个数据元素都和一组惟一的下标值对应，因此，数组是一种随机存储结构。 7 数据元素数目固定。一旦被定义，数组的维数和维界就不能再改变，只能对数组元素进行存取和修改元素的值。 数组元素本身可以具有某种结构。 am1 am2 …….. amn a11 a12 …….. a1n a21 a22 …….. a2n ………… aij ……. 8 数组的基本操作 DestroyMatrix (M ) 数组只有引用型操作，没有加工型操作。 InitMatrix (M ) SetMatrix (M，i1,…，j1...，e) GetMatrix (M，i1,…，j1...，e) 数组初始化 数组销毁 获取元素 元素赋值 9 二维数组 数据对象： D = {aij | 0≤ib1, 0 ≤jb2 ,aij ∈ElemSet } 数据关系： R = { ROW, COL } ROW = {ai,j , ai+1,j| 0≤i≤b1-2, 0≤j≤b2-1} COL = {ai,j , ai,j+1| 0≤i≤b1-1, 0≤ j≤b2-2} a00 a01 … a0,n-1 a10 a12 … a1,n-1 … … aij … am-1,0 am-1,1 … am-1,n-1 Amn= 10 数组的顺序表示 数组是多维的结构，而存储空间是一维的结构。因此，存储时，多维一维。 有两种顺序映象的方式: 1)以行序为主序(低下标优先) 2)以列序为主序(高下标优先) 11 Loc( aij)=Loc(a11)+((i -1)× n+j-1) )× L am1 am2 …….. amn a11 a12 …….. a1n a21 a22 …….. a2n ………… aij ……. k = (i-1) ×n + (j-1) 在PASCAL、C语言中，数组就是按行优先顺序存储的。 按行序为主序存放 行优先—低下标优先 am,n …….. am,2 am,1 …… aij …… a22 a21 a1n ……. a11 a11 1 2 n m ×n k k = ? 12 Loc(aij)=Loc(a11)+((j-1) × m+i-1)) × L k = (j -1)× m + i-1 在FORTRAN语言中，数组就是按列优先顺序存储的。 按列序为主序存放 列优先—高下标优先 a11 a12 …….. a1,n a21 a22 …….. a2n am1 am2 …….. amn ………… aij ……. m*n 1 2 m am,n …….. a2,n a1,n ………. aij …….. a22 a12 am1 …….