第5章数组和广义表ppt课件.ppt

《第5章数组和广义表ppt课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第5章数组和广义表5.1数组的定义5.2数组的顺序表示和实现5.3矩阵的压缩存储5.4广义表5.1数组的定义图5.1Am×n的二维数组图5.2矩阵Am×n看成n个列向量的线性表图5.3矩阵Am×n看成m个行向量的线性表以上我们以二维数组为例介绍了数组的结构特性，实际上数组是一组有固定个数的元素的集合。也就是说，一旦定义了数组的维数和每一维的上下限，数组中元素的个数就固定了。例如二维数组A3×4，它有3行、4列，即由12个元素组成。由于这个性质，使得对数组的操作不像对线性表的操作那样可以在表中任意一个合法的位置插入或删除一个元素。对于数组的操作一般只有两类：(1）获得特定位置的元素值

2、；(2）修改特定位置的元素值。基本操作：（1）InitArray(&A,n,bound1,…,boundn)：若维数n和各维的长度合法，则构造相应的数组A，并返回TRUE。（2）DestroyArray（&A）：销毁数组A。（3）Value（A，&e,index1,…,indexn）：若下标合法，则用e返回数组A中由index1,…,indexn所指定的元素的值。（4）Assign(&A,e,indexl,…indexn)：若各下标不超界，则将e赋值为所指定的A的元素值，并返回OK。。n维数组中每个元素都受着n个关系的约束，在每个关系中，元素aj1j2…jn(0≤ji≤bi

3、-2)都有一个直接后继元素。因此，就其单个关系而言，这n个关系仍是线性关系。所有数据元素必须属于同一数据类型。数组的每个元素都对应于一组下标（j1,j2,…jn）,其中每个下标的取值范围是0≤ji≤bi-1,bi称为第i维的长度。当n=1时，n维数组就退化为定长的线性表。由此，n维数组是线性表的扩广。5.2数组的顺序表示和实现数组一般不做插入和删除操作，因此采用顺序存储结构。由于存储单元是一维结构，而数组是多维结构，则用一组连续存储单元存放数组的数据元素就有个次序约定问题。数组的顺序存储结构有两种：一种是按行序存储，如高级语言BASIC、C和PASCAL语言都是以行序为主；另一种是按列

4、序存储，如高级语言中的FORTRAN语言就是以列序为主显然，二维数组Am×n以行为主的存储序列为：a11,a12,…，a1n,a21,a22,…,a2n,…,am1,am2,…,amn而以列为主的存储序列为：a11,a21,…，am1，a12,a22,…,am2,…,a1n,a2n,…,amn假设有一个3×4×2的三维数组A，共有24个元素，其逻辑结构如图5.4所示。图5.4三维数组的逻辑结构图三维数组元素的标号由三个数字表示，即行、列、纵三个方向。a142表示第1行，第4列，第2纵的元素。如果对A3×4×2（下标从1开始）采用以行为主序的方法存放，即行下标变化最慢，纵下标变化

5、最快，则顺序为：a111，a112，a121，a122，…，a331，a332，a341，a342采用以纵为主序的方法存放，即纵下标变化最慢，行下标变化最快，则顺序为：a111，a211，a311，a121，a221，a321，…，a132，a232，a332，a142，a242，a342以上的存放规则可推广到多维数组的情况。总之，知道了多维数组的维数，以及每维的上下界，就可以方便地将多维数组按顺序存储结构存放在计算机中了。同时，根据数组的下标，可以计算出其在存储器中的位置。因此，数组的顺序存储是一种随机存取的结构。以二维数组Am×n为例，假设每个元素只占一个存储单元，

6、“以行为主”存放数组，下标从1开始，首元素a11的地址为Loc［1,1］，求任意元素aij的地址。aij是排在第i行，第j列，并且前面的第i-1行有n×（i-1）个元素，第ｉ行第j个元素前面还有ｊ-１个元素。由此得到如下地址计算公式：Loc［i,j］=Loc［1,1］+n×(i-1)+(j-1)根据计算公式，可以方便地求得aij的地址是Loc［i,j］。如果每个元素占size个存储单元，则任意元素aij的地址计算公式为：Loc［i,j］=Loc［1,1］+(n×(i-1)+j-1)×size三维数组A（1..r,1..m,1..n）可以看成是r个m×n的二维数组，如图5.5所示

7、。图5.5三维数组看成r个m×n的二维数组假定每个元素占一个存储单元，采用以行为主序的方法存放，即行下标r变化最慢，纵下标n变化最快。首元素a111的地址为Loc［1,1,1］，求任意元素aijk的地址。显然，ai11的地址为Loc［i,1,1］=Loc［1,1,1］+(i-1)×m×n，因为在该元素之前，有ｉ-１个ｍ×ｎ的二维数组。由ai11的地址和二维数组的地址计算公式，不难得到三维数组任意元素aijk的地址：Loc［i,j,k］=L