5章数组和广义表.pptVIP

第5章 第5章 数组和广义表 前几章讨论的线性结构中的数据元素都是非结构的原子类型，元素的值是不再分解的。本章讨论的两种数据结构——数组和广义表可以看成是特殊的线性表，其特殊性在于，表中的数据元素本身也是一种数据结构。 一、一维数组： 一维数组（Array）是n(n≥1)个相同类型数据元素a0,a1,…,an-1构成的有限序列，且该有限序列存储在一块地址连续的内存单元中。由此可见，一维数组可以看成是一个线性表或一个向量，一维数组的定义类似于采用顺序存储的线性表。 对于一维数组，一旦a0的存储地址Loc(a0)确定，若每个数据元素占用L个存储单元，则任一数据元素ai的存储地址Loc(ai)可由以下公式求出： Loc(ai)= Loc(a0)+i*L (5-1) (5-1)式说明，一维数组中任一数据元素的存储地址可直接计算得到，因此，一维数组是一种随机存储结构。 二、二维数组： 二维数组可以看成是一维数组的推广。设A是一个有m行、n列的二维数组，则A可以表示为： 显然，在二维数组中，每个数据元素对应一对数组下标，在行方向上和列方向上都存在一个线性关系，即存在两个直接前驱和两个直接后继（边界除外）。 可以看成是由m个行向量组成的向量，也可以看成是n个列向量组成的向量。 行向量形式：把每一行看成是一个数据元素 列向量形式：把每一列看成是一个数据元素 二维数组可以看作“数据元素是一维数组”的一维数组。 三、多维数组： 同理，三维数组中的数据元素（边界除外）最多可有三个直接前驱和三个直接后继。可以把三维以上的数组称为多维数组，多维数组中的数据元素（边界除外）可有多个直接前驱和多个直接后继，故多维数组是一种非线性结构。 n维数组中，每个数据元素对应n个下标，受n个关系的制约，其中任一个关系都是线性关系。可看作是数据元素为n-1维数组的一维数组。 在C语言中，一个二维数组类型可以定义为其分量类型为一维数组类型的一维数组类型，也就是说 typedef ElemType Array2[m][n]； 等价于 typedef ElemType Array1[n]； typedef Array1 Array2[m]； 同理，一个n维数组类型可以定义为其数据元素为n-1维数组类型一维数组类型。 数组一旦被定义，它的维数和维界就不再改变。因此，除了结构的初始化和销毁之外，数组只有存取元素和修改元素值的操作。 数组具有以下性质： 1.?数组中的数据元素数目固定，一旦定义了一个数组，其数据元素数目不再有增减变化； 2.?数组中的每个数据元素具有相同的数据类型； 3. 数组中的每个数据元素都和一组唯一的下标相对应； 4. 数组是一种随机存取结构，可随机存取数组中的任意数据元素。 5.2 数组的顺序表示和实现 由于数组一般不作插入或删除操作，一旦建立了数组，则结构中的数据元素个数和元素之间的关系就不再发生变动。因此，适合采用顺序存储结构表示数组。本章中，仅重点讨论二维数组的存储，三维及三维以上的数组可以作类似分析。 由于存储单元是一维的结构，而二维数组是个多维的结构，则用一组连续存储单元存放数组的数据元素就有个次序约定问题。 两种顺序存储方式： 以行序为主序（行优先顺序） 以列序为主序（列优先顺序） 一、以行序为主序： 1．存放规则 行优先顺序也称为低下标优先或右边下标优先于左边下标。具体实现时，按行号从小到大的顺序，先将第一行中元素全部存放好，再存放第二行元素，第三行元素，依次类推…… BASIC语言、PASCAL语言、C/C++语言都是按行优先顺序存放的。 例如，对二维数组Am×n ，可用如下形式存放到内存：a00，a01,…a0n-1，a10，a11，...， a1 n-1，…，am-1 0 ， am-1 1，…，am-1 n-1。即二维数组按行优先存放到内存后，变成了一个线性序列（线性表）。 2．地址计算 假设二维数组Am×n每个元素占L个字节，元素aij的存储地址应为第一个元素的地址加上排在aij前面的元素所占用的单元数，而aij 的前面有i行(0?i-1)共i×n个元素，而第i行上aij前面又有j个元素，故aij的前面一共有i×n+j个元素，设a00的地址为LOC(a00)，则aij的地址为： LOC(aij)=LOC(a00)+（i×n+j）×L 同理，三维