计算机软件就是基础 软件基础之数据结构-数组.ppt

16:05:26 1第二章常用数据结构及其运算---- 数组 16:05:26 2 主要介绍多维数组的概念及在计算机中的存放,特殊矩阵的压缩存储及相应运算,广义表的概念和存储结构及其相关运算的实现。通过学****要求掌握如下内容:; 2 .对称矩阵、三角矩阵、对角矩阵等特殊矩阵在计算机中的压缩存储表示及地址计算公式; ; ; 16:05:26 3多维数组多维数组的概念数组是大家都已经很熟悉的一种数据类型, 几乎所有高级语言程序设计中都设定了数组类型。在此,我们仅简单地讨论数组的逻辑结构及在计算机内的存储方式。 ,它在计算机内是存放在一块连续的存储单元中,适合于随机查找。这在线性表的顺序存储结构中已经介绍。 16:05:26 4 。例如,设 A 是一个有 m行n列的二维数组,则 A可以表示为: a 00 a 01 …… a 0n-1 a 10a 11 …… a 1n-1 …………………………. A=a m- 1 0 a m- 1 1 …… a m- 1 n-1 16:05:26 5 ?在此,可以将二维数组 A看成是由 m个行向量[X 0,X 1,…,X m -1] T组成,其中, X i =( a i0, a i1, ….,a in -1),0≤i≤ m-1 ;也可以将二维数组 A 看成是由 n个列向量[y 0, y 1, ……,y n -1]组成,其中 y i =(a 0i, a 1i, …..,a m-1i ),0≤i≤ n-1 。由此可知二维数组中的每一个元素最多可有两个直接前驱和两个直接后继(边界除外),故是一种典型的非线性结构。 a ija i j-1a i -1 ja i j+1 a i +1 j 16:05:26 6 ,三维数组最多可有三个直接前驱和三个直接后继,三维以上数组可以作类似分析。因此,可以把三维以上的数组称为多维数组,多维数组可有多个直接前驱和多个直接后继,故多维数组是一种非线性结构。多维数组在计算机内的存放怎样将多维数组中元素存入到计算机内存中呢?由于计算机内存结构是一维的(线性的),因此,用一维内存存放多维数组就必须按某种次序将数组元素排成一个线性序列,然后将这个线性序列顺序存放在存储器中,具体实现方法在下一节介绍。 16:05:26 7 。具体实现时,按行号从小到大的顺序,先将第一行中元素全部存放好,再存放第二行元素,第三行元素,依次类推……在 BASIC 语言、 PASCAL 语言、 C/C++ 语言等高级语言程序设计中,都是按行优先顺序存放的。例如,对刚才的 A m×n 二维数组,可用如下形式存放到内存: a 00, a 01,…a 0n-1 ,a 10,a 11, ...,a 1 n-1 ,…,a m-1 0 ,a m-1 1 ,…,a m-1 n-1 。即二维数组按行优先存放到内存后,变成了一个线性序列(线性表)。因此,可以得出多维数组按行优先存放到内存的规律:最左边下标变化最慢,最右边下标变化最快,右边下标变化一遍,与之相邻的左边下标才变化一次。因此, 在算法中,最左边下标可以看成是外循环,最右边下标可以看成是最内循环。 16:05:26 8 , 因此,若知道第一个元素的内存地址,如何求得其他元素的内存地址?我们可以将它们的地址排列看成是一个等差数列,假设每个元素占 l 个字节,元素 a ij 的存储地址应为第一个元素的地址加上排在 a ij 前面的元素所占用的单元数,而 a ij 的前面有 i行(0~ i-1) 共i×n 个元素,而本行前面又有 j 个元素,故 a ij 的前面一共有 i× n+j 个元素,设 a 00 的内存地址为 LOC(a 00) ,则 a ij 的内存地址按等差数列计算为 LOC( a ij )=LOC(a 00 )+(i× n+j )×l。同理,三维数组 A m×n×p 按行优先存放的地址计算公 式为: LOC( a ijk )=LOC(a 000 )+(i ×n× p+j × p+k) ×l。 16:05:26 9 同理,三维数组 A m×n×p 按行优先存放的地址 计算公式为: LOC( a ijk )=LOC(a 000 )+(i ×n× p+j × p+k) ×l。 16:05:26 10 列优先顺序