资源描述：
《数据结构与算法C++语言版第5章多维数组 与广 义表.ppt》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。
1、数据结构与算法（C++语言版）第5章多维数组与广义表数组数组的定义与线性表一样，数组中所有的数据元素都必须属于同一数据类型，其特点是，每个数据元素可以又是一个线性表结构。若线性表中的数据元素为简单元素，则称为一维数组，即向量；若一维数组中的数据元素又是一维数组，则称为二维数组；依次类推，若二维数组中的元素又是一个一维数组结构，则称为三维数组。因此，线性表结构可看成是数组结构的一个特例，而数组结构则是线性表结构的扩展。数组例如，在（a）所示的m行n列二维数组中，每个数据元素ai,j都受两个关系——行关系和列关系的约束。在行关系中，ai,j+1是ai,j的直接后继元素。在列关系中，a
2、i+1,j是ai,j的直接后继元素，该数组元素的个数为m×n。该数组可被看成是一个线性表A=(a0,a1,…,ap)，p=m–1或n–1，其中每个元素aj可以是如（b）所示的列向量形式线性表aj=(a0,j,a1,j,…,am–1,j)，0≤j≤n–1，也可以是如（c）所示的行向量形式线性表ai=(ai,0,ai,1,…,ai,n–1)，0≤i≤m–1。数组同理，n维数组中每个数据元素都受n个关系的约束，都对应于一组下标(j1,j2,…,jn)，元素（1≤ji≤bi–1，i=1,2,…,n）有一个直接后继元素。因此，就单个关系而言，仍是线性关系。类似于线性表，数组的抽象数据类型定
3、义参见以下ADT。数组数组C++的数组尽管在C++中数组是一个标准的数据结构，但C++数组的索引（也称为下标）必须采用[i1][i2][i3]…[ik]的形式，其中，ik为非负整数。如果k为1，则数组为一维数组；如果k为2，则数组为二维数组。i1是索引的第一个坐标，i2是第二个坐标，ik是第k个坐标。在C++中，值为整数类型的k维数组score可用intscore[u1][u2][u3]…[uk]语句来创建，其中，ui是正的常量或由常量表示的正的表达式。对于这样一个数组描述，索引ij的取值范围为：0≤ij＜uj，1≤j≤k。因此，该数组最多可容纳n=u1u2u3…uk个值。由于数
4、组score中的每个值都是整数，所以需要占用sizeof(int)个字节，因此，整个数组所需要的内存空间为sizeof(score)=n×sizeof(int)个字节。C++编译器将为数组预留这么多空间。如果预留空间的起始地址为start，则该空间将延伸至start+size(score)–1。数组数组的存储结构与寻址问题数组是一种特殊的数据结构，一般要求元素的存储地址能根据它的下标（即逻辑关系）计算出来，因此数组一般只采用顺序存储结构。讨论数组元素地址时，一般将第1个元素的起始存储单元作为参考单元，参考单元的绝对地址称为该数组的首地址，数组其他元素的相对地址均相对于首元素的起始
5、地址。设i1,i2,…,in为某n维数组中的一个元素的下标，则用Loc()表示此元素的相对地址。对一维数组，与线性表类似，可使用顺序存储方式；但对多维数组，由于其已不属于线性结构的范畴，因此不能直接使用顺序存储方式。但多维数组有其特殊性，具有线性结构的痕迹，它可唯一地转换为一维结构，并可根据元素的存储位置推算出元素的逻辑关系（下标），所以可将多维数组映射为一维结构，然后使用顺序存储方式。数组1.一维数组一维数组的每个元素只含一个下标，其实质上是一个线性表，存储方法与普通线性表的顺序存储方法完全相同，即将数组元素按它们的逻辑次序存储在一片连续区域内。设一维数组为A=(a0,a1,…
6、,an–1)，则它的元素ai的相对地址为Loc(ai)=i×c。这里，c表示每个元素占用的存储单元数目。2.二维数组二维数组的每个元素含有两个下标，不是一般的线性表。如果将二维数组的第1个下标理解为行号，第2个下标理解为列号，然后按行列次序排列各元素，则二维数组呈阵列形状。对于这种非线性结构的存储，需将多维关系映射为一维（线性）关系，即要确定多维到一维的映射。数组以之前所示的二维数组为例，它有两种存储方式：以列序为主序的存储方式（a）和以行序为主序的存储方式就（b）。数组（1）按行存储按行存储的基本思想是先行后列，即先存储行号较小的元素，对于行号相同者，先存储列号较小者。设二维数
7、组的行下标与列下标变化范围分别为闭区间[l1,h1]与[l2,h2]，按行存储，则它的任一元素ai,j的相对地址计算公式为Loc(ai,j)=((h2–l2+1)(i–l1)+(j–l2))×c，这里c为每个元素所占单元数目，i∈[l1,h1]，j∈[l2,h2]且i与j为整数。例5-1设某二维数组的两个下标的范围分别为[–1,2]与[0,1]，则它的元素按行存储的次序为（用ai,j表示元素，每个元素占两个单元）：它的元素a1,1的相对地址计算如下：Loc(a1,1)=((1
