杭电数据结构java版数组.ppt

数组、特殊矩阵了解更多信息，请关注新浪微博 听刘遵义讲故事 /u/2519554322 大纲要求 掌握数组顺序存储和压缩存储的概念和相关计算 掌握数组的基本操作算法 提纲 数组的定义 数组的逻辑结构 数组元素之间的关系 数组的操作 数组的顺序存储结构 数组的压缩 数组的定义 数组是相同类型数据元素的有限集合 数组中的各个分量称为数组元素 每个数组元素值可以用数组名和一个下标值唯一的确定 由于数组中各元素具有统一的类型，并且数组元素 的下标一般具有固定的上界和下界，因此，数组的 处理比其它复杂的结构更为简单。多维数组是向量 的推广。 数组的定义 二维数组： a11 a12 … a1n a21 a22 … a2n … … … … am1 am2 … amn 可以看成是由个行向量组成的向量，也可以看成 是个列向量组成的向量。 数组的定义 数组一旦被定义，它的维数和维界就不再改变。因此，除了结构的初始化和销毁之外，数组只有存取元素和修改元素值的操作。 数组的逻辑结构 二维数组 N维数组 二维数组 2_Array=(D,R) D 是某种数据类型的有限元素集合,且 D={ aij|i=(c1,d1),j=(c2,d2),aij ?D0 } R是行、列关系的有限集合，且 R={ ROW ， COL }，又 ROW={ aij,aij+1|c1?i?d1,c2?j?d2-1, aij, aij+1 ? D0 } COL={ aij,ai+1j|c1?i?d1-1,c2?j?d2, aij, ai+1j ? D0 } ci 是第i维的下界；dj 是第j维的上界 两维数组的元素个数为: (d1-c1+1)*(d2-c2+1) N维数组 n_Array=( D , R ) ji=(ci，di)，i=1，2，…n D = aj1j2…jn| aj1…jn ? D0 R={ R1 ,R2，…Rn }，又 Ri= aj1,…ji…jn,aj1,…ji+1…jn| ci?ji?di-1 a j1…ji…jn ? D0 N维数组的元素个数为: (d1-c1+1)*(d2-c2+1)*….(dn-cn+1) = ? (di-ci+1) 数组元素之间的关系 数组的操作 数组有两种基本的操作： 给定下标，存取相应的数组元素； 给定下标，修改相应数组元素的值。 数组的顺序存储结构 数组元素是连续存放的，因此采用顺序存储结构。 无论几维数组,在计算机中都是按一维数组来存放。数组存放通常采用两种方式： 按行优先顺序 按列优先顺序 按行优先顺序存储结构 按行优先顺序存放是将数组看作若干个行向量。例如，二维数组Amxn，可以看作m个行向量，每个行向量n个元素。数组中的每个元素由元素的两个下标表达式唯一的确定。 地址计算公式： 按行优先顺序存储结构 三维数组Aijk按“行优先顺序”存储，共有m*n*p个 元素，其地址计算函数为： 二维数组按行优先存储举例 按列优先顺序存储结构 按列优先顺序存放是将数组看作若干个列向量。例如，二维数组Amxn，可以看作n个列向量，每个列向量m个元素。数组中的每个元素由元素的两个下标表达式唯一的确定。 地址计算公式： 二维数组按列优先存储举例 数组的压缩存储 实际工程问题中推导出的数组常常是高阶、含大量零元素的矩阵，或者是些有规律排列的元素。为了节省存储空间，通常是对这类矩阵进行压缩存储。 压缩的含义是： 相同值的多个元素占用一个存储单元； 零元素不分配存储单元。 数组的压缩存储 特殊矩阵 稀疏矩阵 特殊矩阵 对称矩阵 三角矩阵 带状矩阵 对称矩阵 在一个n阶方阵A中，若元素满足下述性质： aij=aji 0≦i,j≦n-1 则称A为对称矩阵。 对称矩阵 1 5 1 3 7 a00 5 0 8 0 0 a10 a 11 1 8 9 2 6 a20 a21 a22