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

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

ID:58717043

大小:838.00 KB

页数:67页

时间:2020-10-04

第 05 章 数组和广义表ppt课件.ppt_第1页
第 05 章 数组和广义表ppt课件.ppt_第2页
第 05 章 数组和广义表ppt课件.ppt_第3页
第 05 章 数组和广义表ppt课件.ppt_第4页
第 05 章 数组和广义表ppt课件.ppt_第5页
资源描述:

《第 05 章 数组和广义表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个元素组成。由于这个性质,使得对数组的操作不像对线性表的操作那样可以在表中任意一个合法的位置插入或

2、删除一个元素。对于数组的操作一般只有两类:(1)获得特定位置的元素值;(2)修改特定位置的元素值。基本操作:(1)InitArray(A,n,bound1,…,boundn):若维数n和各维的长度合法,则构造相应的数组A,并返回TRUE。(2)DestroyArray(A):销毁数组A。(3)GetValue(A,e,index1,…,indexn):若下标合法,则用e返回数组A中由index1,…,indexn所指定的元素的值。(4)SetValue(A,e,index1,…,indexn):若下标合法,则将数组A中由i

3、ndex1,…,indexn所指定的元素的值置为e。这里定义的数组,与C语言的数组略有不同,下标是从1开始的。5.2数组的顺序存储和实现数组的顺序存储结构有两种:一种是按行序存储,如高级语言BASIC、COBOL和PASCAL语言都是以行序为主;另一种是按列序存储,如高级语言中的FORTRAN语言就是以列序为主显然,二维数组Am×n以行为主的存储序列为:a11,a12,…,a1n,a21,a22,…,a2n,…,am1,am2,…,amn而以列为主的存储序列为:a11,a21,…,am1,a12,a22,…,am2,…,a1n

4、,a2n,…,amn假设有一个3×4×2的三维数组A,共有24个元素,其逻辑结构如图5.4所示。图5.4三维数组的逻辑结构图三维数组元素的标号由三个数字表示,即行、列、纵三个方向。a142表示第1行,第4列,第2纵的元素。如果对A3×4×2(下标从1开始)采用以行为主序的方法存放,即行下标变化最慢,纵下标变化最快,则顺序为:a111,a112,a121,a122,…,a331,a332,a341,a342采用以纵为主序的方法存放,即纵下标变化最慢,行下标变化最快,则顺序为:a111,a211,a311,a121,a22

5、1,a321,…,a132,a232,a332,a142,a242,a342以上的存放规则可推广到多维数组的情况。总之,知道了多维数组的维数,以及每维的上下界,就可以方便地将多维数组按顺序存储结构存放在计算机中了。同时,根据数组的下标,可以计算出其在存储器中的位置。因此,数组的顺序存储是一种随机存取的结构。以二维数组Am×n为例,假设每个元素只占一个存储单元,“以行为主”存放数组,下标从1开始,首元素a11的地址为Loc[1,1],求任意元素aij的地址。aij是排在第i行,第j列,并且前面的第i-1行有n×(i-1)个元素,第i行

6、第j个元素前面还有j-1个元素。由此得到如下地址计算公式: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所示。图5.5三维数组看成r个m×n的二维数组假定每个元素占一个存储单元,采用以行为主序的方法存放,即行下标r变化最慢,纵下标n

7、变化最快。首元素a111的地址为Loc[1,1,1],求任意元素aijk的地址。显然,ai11的地址为Loc[i,1,1]=Loc[1,1,1]+(i-1)×m×n,因为在该元素之前,有i-1个m×n的二维数组。由ai11的地址和二维数组的地址计算公式,不难得到三维数组任意元素aijk的地址:Loc[i,j,k]=Loc[1,1,1]+(i-1)×m×n+(j-1)×n+(k-1)其中1≤i≤r,1≤j≤m,1≤k≤n。如果将三维数组推广到一般情况,即:用j1、j2、j3代替数组下标i、j、k,并且j1、j2、j3的下限为c1、

8、c2、c3,上限分别为d1、d2、d3,每个元素占一个存储单元,则三维数组中任意元素a(j1,j2,j3)的地址为:Loc[j1,j2,j3]=Loc[c1,c2,c3]+l×(d2-c2+1)×(d3-c3+1)

当前文档最多预览五页,下载文档查看全文

此文档下载收益归作者所有

当前文档最多预览五页,下载文档查看全文
温馨提示:
1. 部分包含数学公式或PPT动画的文件,查看预览时可能会显示错乱或异常,文件下载后无此问题,请放心下载。
2. 本文档由用户上传,版权归属用户,天天文库负责整理代发布。如果您对本文档版权有争议请及时联系客服。
3. 下载前请仔细阅读文档内容,确认文档内容符合您的需求后进行下载,若出现内容与标题不符可向本站投诉处理。
4. 下载文档时可能由于网络波动等原因无法下载或下载错误,付费完成后未能成功下载的用户请联系客服处理。