栈与队列多维数组.docVIP

　栈、队列和多维数组 §2.4 多维数组　　多维数组是一种常见的数据结构，本节讨论多维数组的逻辑结构、基本运算和存储结构，以及特殊矩阵和稀疏矩阵的压缩存储方法。一、多维组的逻辑结构和运算　　设有二维数组A:array[1..m,1..n] of elementype; 　　　　　　　　 　┌ a11 a12　… a1n ┐　　　　　　　　 　│ a21 a22　… a2n │　　　　　　　　A＝│ a21 a22　… a2n │　　　　　　　　　 │ a… a…　… a… │　　　　　　　　　 └ am1 am2　… amn ┘ 　　它可看成是由m个行向量或者n个列向量组成的线性表。也就是说，二维数组可以看成是这样一种推广的线性表，这种线性表的每一个数据元素本身也是一个线性表。　　对于上述二维数组A，我们可以将A看成是下述线性表　　　　　A=(d1,d2,…,dn)　　其中每一个数据元素dj本身也是一个线性表　　　　　dj=(d1j,d2j,…,dmj) 1≤j≤n。　　该线性表是二维数组A的第j个列向量。同样，也可将二维数组A看成线性表A=(β1,β2,…,βm),其中每个βi本身也是一个线性表　　　　　β=(αi1,αi2,…,αin) 1≤j≤m，βi是二维数组A的第i个行向量。　　类似地，一个三维数组可以看成是数据元素为二维数组的线性表。一般地，一个n维数组可视为其数据元素为n-1维数组的线性表。　　二维数组中每个元素aij均属于两个向量：第i行的行向量和第j列的列向量。因此，除边界外，每个元素aij都恰好有两个直接前趋和直接后继：行向量上的直接前趋aij-1和直接后继aij+1，列向量上的直接前趋ai-1j和直接后继ai+1j。并且有且仅有一个开始结点a11，它没有直接前趋；有且仅有一个终端结点amn，它没有直接后继。另外，边界上的结点(开始结点和终端结点除外)只有一个直接前趋或者只有一个直接后继。即除开始结点a11外，第一行和第一列上的结点：a1j(j=2,...,n),ai1(i=2,...,m)都只有一个直接前趋；除终端结点amn外，第m行和第n列上的结点amj(j=1,...,n-1),ain(i=1,...,m-1)都只有一个直接后继。　　同样，三维数组Amnp中的每个元素aijk都属于三个向量，每个元素最多可以有三个直接前趋除和三个直接后继。　　依次类推，m维数组An1n2...nm每个元素ai1i2...im都属于m个向量，最多可以有m个直接前趋除和m个直接后继。　　数组通常只有两种基本运算——读和写。　　①读：给定一组下标，读取相应的数据元素。　　②写：给定一组下标，修改相应的数据元素。　　值得注意的是，多维数组的数据元素的类型elementype可根据实际需要而定义。相应地，读、写运算可以读取或修改一个数据元素的一部分而不必一定是整个元素。二、多维数组的存储结构　　计算机的内存结构是一维的。因此，用一维内存来表示多维数组就必须按某种次序将数组元素排成一个线性的序列，然后的将这个线性序列顺序存放在存储器中。　　多维数组的类型定义可以直接用高级程序设计语言中的数组类型给出,也就是说多维数组在语言级的存储表示是数组类型。相应地，读写运算在高级语言里的实现手段是下标变量和赋值操作。因为几乎所有高级语言都有数组类型，人们常说多维数组是一种“已经在高级语言中实现了”的数据结构。以下着重讨论多维数组的机器级实现。通常采用顺序存储结构来存放数组。对二维数组可有两种存储方式：一种是以列序为主序的存储方式，另一种是以行为主序的存储方式，如图3-14所示。 a11 a21 ┇? am1 a12 a22 ┇? am2 ┇? a1n a2n ┇? amn a11 a12 ┇? a1n a21 a22 ┇? a2n ┇ am1 am2 ┇ amn (a)以列为主序 (b)以行为主序 图3-14 　　在有的高级语言象pascal语言的编译器中,数组用的是以行序为主序的存储方法，有的高级语言象FORTRAN语言,用的是以列序为主序的存储方法。　　对于数组，一旦定义了它的维数和各维的上、下界，便可为它分配存储空间，给出一组下标即可求得相应数组元素的存储位置，下面以行序为主序的存储结构为例说明位置和下标关系。　　假定数组A:array[c1..d1,c2..d2]of datatype每个数据元素占k个存储单元,二维数组中任一元素的存储位置可由下式确定：　　loc[i,j]=loc[c1,c2]+[(d2-c2+1)(i-c1)+(j-c2)]*k　　loc[c1,c2]是a[c1,c2]的存储位置，它是该二维数组的起始地址，也称基地址。loc[i,j]是