第5章数组和广义表
本章讨论的是数组和广义表这两种数据结构。它们都可看成是线性表的扩展，这是因为表中的数据元素也可以具有线性结构。
5.1数组5.1.1数组的基本概念数组是一种十分常用的结构,现在几乎所有程序设计语言都直接支持数组类型。在对数组进行操作前，要对元素进行定位。本节的主要内容是给出数组的定义及其存储映射的方法。
数组由一组相同类型的数据元素构成。可借助线性表的概念递归进行定义。
数组是一个元素可直接按序号寻址的线性表:
a=(a0,a1,…,am-1)
若ai(i=0,1,…,m-1)是简单元素,则a是一维数组;当一维数组的每个元素ai本身又是一个一维数组时,则一维数组扩充为二维数组。同理,当ai是一个二维数组时,则二维数组扩充为三维数组。以此类推,若ai是k-1维数组,则a是k维数组。
可以看出,在n维数组中,每个元素受n个线性关系的约束(n≥1),若它在第1～n个线性关系中的序号分别为i1,i2,…,in,则称它的下标为i1,i2,…,in。如果数组名为a,则记下标为i1,i2,…,in的元素为ai1,i2,…,in。
从上面的定义可以看出,如果一个n(n>0)维数组的第i维长度为bi,则此数组中共含有∏ni=1bi个数据元素,每个元素都受n个关系的约束,就其单个关系而言,这n个关系都是线性关系。
数组的基础操作如下:ElemType &operator()(int sub0, …)初始条件: 数组已存在。
操作结果: 重载函数运算符。
5.1.2数组的顺序表
由于很少在数组中进行插入和删除操作,所以数组的存储通常采用顺序存储方式。设n维数组共有m=∏ni=1bi个元素,数组存储的首地址为base,数组中的每个元素需要size个存储单元,则整个数组共需m·size个存储单元。为了存取数组中某个特定下标的元素,必须确定下标为i1, i2,…,in的元素的存储位置。实际上就是把下标i1, i2,…,in映射到［0, m-1］中的某个数Map(i1, i2, …, in),使得该下标所对应的元素值存储在以下位置:
Loc(i1,i2,…,in)=base+Map(i1,i2,…,in)·size
用Loc(i1,i2,…,in)表示下标为i1,i2,…,in的数组元素的存储地址。可见,如果已经知道数组的首地址,要确定其他元素的存储位置,只需求出Map(i1,i2,…,in)即可。下面讨论Map(i1,i2,…,in)的计算。在后面的例子中,都是用C++中表示数组的方式来描述数组及其元素。
对于一维数组,Map(i1)=i1。
对于二维数组,各元素可按图5.1所示的表格形式进行排列。第1维下标相同的元素位于同一行,第2维下标相同的元素位于同一列。a［0］［0］ a［0］［1］ a［0］［2］ a［0］［3］ a［0］［4］ a［0］［5］
a［1］［0］ a［1］［1］ a［1］［2］ a［1］［3］ a［1］［4］ a［1］［5］
a［2］［0］ a［2］［1］ a［2］［2］ a［2］［3］ a［2］［4］ a［2］［5］
a［3］［0］ a［3］［1］ a［3］［2］ a［3］［3］ a［3］［4］ a［3］［5］
a［4］［0］ a［4］［1］ a［4］［2］ a［4］［3］ a［4］［4］ a［4］［5］图5.1数组a［5］［6］的元素列表对于图5.1中的元素,从第1行开始,依次对每一行中的每个元素从左至右进行连续编号,即可得到图5.2(a)所示的映射结果。这种按行把二维数组中的元素位置映射为［0,m-1］中的某个数的方式称为行优先映射。C++中就采用行优先映射模式。图5.2(b)中给出了另外一种映射模式,把所有元素按列的次序进行连续编号,称为列优先映射。01234567891011121314151617181920212223242526272829(a) 行优先映射05101520251611162126271217222738131823284914192429(b) 列优先映射图5.2数组a［5］［6］的映射可以看出,一个b1行b2列的二维数组a［b1］［b2］的行优先映射所对应的映射函数为
Map(i1,i2)=i1b2+i2
读者可用图5.1中的5行6列的数组来验证上述的行优先映射函数。因为列数为6,所以映射公式为Map(i1,i2)=6i1+i2,从而有Map(2,3)=6×2+3=15,Map(3,5)=6×3+5=23,与图5.2(a)中所给出的编号完全相同。
可以扩充上述行优先映射模式,得到二维以上数组的行优先映射函数。在二维数组的行优先次序中,首先列出所有第一个下标为0的元素,然后是第一个下标为1的元素……第一个下标相同的所有元素按其第二个下标的递增次序排列。以此类推,对于三维数组,首先列出所有第一个下标为0的元素,然后是第一个下标为1的元素……第一个下标相同的所有元素按其第二个下标的递增次序排列,前两个下标相同的所有元素按其第三个下标的递增次序排列。例如数组a［4］［2］［4］中的元素,按行优先次序排列为
a［0］［0］［0］a［0］［0］［1］a［0］［0］［2］a［0］［0］［3］a［0］［1］［0］a［0］［1］［1］a［0］［1］［2］a［0］［1］［3］
a［1］［0］［0］a［1］［0］［1］a［1］［0］［2］a［1］［0］［3］a［1］［1］［0］a［1］［1］［1］a［1］［1］［2］a［1］［1］［3］
a［2］［0］［0］a［2］［0］［1］a［2］［0］［2］a［2］［0］［3］a［2］［1］［0］a［2］［1］［1］a［2］［1］［2］a［2］［1］［3］
a［3］［0］［0］a［3］［0］［1］a［3］［0］［2］a［3］［0］［3］a［3］［1］［0］a［3］［1］［1］a［3］［1］［2］a［3］［1］［3］
三维数组a［b1］［b2］［b3］的行优先映射函数为
Map(i1, i2, i3)=i1b2b3+i2b3+i3
类推可得,n维数组a［b1］［b2］…［bn］的行优先映射函数为Map(i1,i2,…,in)=i1b2b3…bn+i2b3…bn+…+in-1bn+in=∑n-1j=1ij∏nk=j+1bk+in=∑nj=1cjij进一步可得如下公式:Loc(i1,i2,…,in)=base+(i1b2b3…bn+i2b3…bn+…+in-1bn+in)size=base+∑nj=1cjijsize其中cn=1,cj-1=bjcj,1<j≤n。
在有些语言中,数组各维的下标范围不一定为［0,bj-1］(j=1,2,…,n),而是某个闭区间［lj,hj］内的整数,则其行优先和列优先映射函数要随之改变。设n维数组的第k维的下标范围是［lk,hk］,记
dk=hk-lk+1,k=1,2,…,n
显然,dk为第k维的长度(元素个数),则此时有Map(i1,i2,…,in)=(i1-l1)d2d3…dn+(i2-l2)d3…dn+…+(in-1-ln-1)dn+(in-ln)=∑n-1j=1(ij-lj)∏nk=j+1dk+(in-ln)列优先映射的映射函数可以类推得到,下面为列优先队列的结论。
n维数组a［b1］［b2］…［bn］的列优先映射函数为Map(i1,i2,…,in)=i1+b1i2+…+b1b2…bn-2in-1+b1b2…bn-1in=i1+∑nj=2∏j-1k=1bkij=∑nj=1cjijLoc(i1,i2,…,in)=base+(i1+b1i2+…+b1b2…bn-2in-1+b1b2…bn-1in)size=base+∑nj=1cjijsize其中c1=1,cj+1=bjcj,1≤i<n。
设n维数组的第k维的下标范围是［lk,hk］,记
dk=hk-lk+1,k=1,2,…,n
dk为第k维的长度(元素个数),此时有Map(i1,i2,…,in)=(i1-l1)+d1(i2-l2)+…+d1d2…dn-1(in-ln)=(i1-l1)+∑nj=2∏j-1k=1dk(ij-lj)5.1.3数组的类模板定义
在C++的数组中,n维数组的下标采用形式［i1］［i2］…［in］,ij为非负整数。但C++本身无法保证数组下标ij的合法性,为克服C++标准数组的不足,下面给出一个数组类模板声明://数组类模板
template<class ElemType>
class Array
{
protected:
//数据成员