会计学第五章多维数组和广义(guǎngyì)表本章主题：多维数组、特殊矩阵和广义表教学目的：掌握(zhǎngwò)数组和广义表的定义、运算教学难点：矩阵的压缩存储对许多应用程序来说，使用简单的线性表和数组完成任务就足够了，但是有一些应用程序不能使用简单线性表来有效地实现。人们(rénmen)可以对线性表进行扩展，实现一些功能更强大、具有更多操作的高级线性结构。前几章讨论的线性结构中的数据元素都是非结构的原子类型，元素的值是不再分解的。本章讨论的两种数据结构----数组和广义表可以看成是线性表在下述含义上的扩展：表中的数据元素本身也是一个数据结构。多维数组和广义表的逻辑特征是：一个数据元素可能有多个直接前趋和多个直接后继。5.1多维数组数组是我们最熟悉的数据类型，在早期的高级语言中，数组是唯一可供使用的结构类型。数组（Array）是由n(n>1)个相同类型数据元素a0，al，…ai…，an-1构成的有限序列(xùliè)。n是数组的长度。其中数组中的数据元素ai是一个数据结构，即ai可以是线性表中的一个元素，本身也可以是一个线性表，而线性子表中的每一个数据元素还可以再分解……。根据数组元素ai的组织形式不同，数组可以分为一维数组、二维数组以及多维（n维）数组。有时也把一维数组称为向量，二维数组称为矩阵。数组中每个元素都是由一个值和一组下标来确定的。同线性表一样，数组中的所有数据元素都必须属于同一数据类型。元素下标的个数被称为数组的维数。显然，当维数为1时，数组就退化为定长的线性表。由于数组中各元素具有统一的类型，并且数组元素的下标一般具有固定的上界和下界，因此，数组的处理比其它复杂的结构更为简单。多维数组是向量的推广。例如，二维数组：a11a12…a1na21a22…a2n…………am1am2…amn可以看成是由m个行向量组成的向量，也可以看成是n个列向量组成的向量。二维数组中的每个元素aij均属于两个向量：第i行的行向量和第j列的列向量，即除边界(biānjiè)外，每个元素aij都恰好有两个直接前趋和两个直接后继结点。二维数组仅有一个开始点a11，它没有前趋；仅有一个终端结点amn，它没有后继。边界(biānjiè)上的结点（开始结点和终端结点除外）只有一个直接前趋或者只有一个直接后继。三维数组中的每个元素aijk都属于三个向量：每个元素最多可以有三个直接前趋和三个直接后继。依次类推，m维数组的每个元素都属于m个向量，最多可以有m个直接前趋和m个直接后继。由于计算机的内存结构是一维的，因此用一维内存来表示多维数组，就必须按某种次序将数组元素排成一个线性序列，然后将这个(zhège)线性序列存放在存储器中。又由于对数组一般不做插入和删除操作，也就是说，数组一旦建立，结构中的元素个数和元素间的关系就不再发生变化。因此，一般都是采用顺序存储的方法来表示数组。通常有两种顺序存储方式：⑴行优先顺序——将数组元素按行排列，第i+1个行向量紧接在第i个行向量后面。以二维数组为例，按行优先顺序存储的线性序列为：a11,a12,…,a1n,a21,a22,…a2n,……,am1,am2,…,amn在PASCAL、C语言中，数组就是按行优先顺序存储的。⑵列优先顺序——将数组元素按列向量排列，第j+1个列向量紧接在第j个列向量之后，A的m*n个元素按列优先顺序存储的线性序列为：a11,a21,…,am1,a12,a22,…am2,……,an1,an2,…,anm在FORTRAN语言中，数组就是按列优先顺序存储的。amnamn假设有一个3×4×2的三维数组A，共有24个元素，其逻辑结构如图所示。三维数组的标号由三个数字表示，即行、列、纵三个方向。a142表示第1行，第4列，第2纵的元素。如果对A3×4×2（下标从1开始）采用以行优先(yōuxiān)的方法存放，即行下标变化最慢，纵下标变化最快，则顺序为：a111,a112,a121,a122,…,a331,a332,a341,a342以上规则可以推广到多维数组的情况：优先顺序可规定为先排最右的下标，从右到左，最后排最左下标：列优先顺序与此相反，先排最左下标，从左向右，最后排最右下标。按上述两种方式顺序存储的数组，只要知道开始结点的存放地址（即基地址），维数和每维的上、下界，以及每个数组元素所占用的单元数，就可以将数组元素的存放地址表示为其下标的线性函数。因此，数组中的任一元素可以在相同(xiānɡtónɡ)的时间内存取，即顺序存储的数组是一个随机存取结构。总结：任何多维数组都可以看作一个线性表，这时线性表中的每个数据元素也是一个线性表。例如一个二维数组可以看作是每个数据元素都是相同类型的一维数组。多维数组是特殊的线性表，是线性表的推广。数