资源描述：
《数组和广义表ppt课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、第五章 数组和广义表5.1数组的定义5.3矩阵的压缩存储5.2数组的顺序表示和实现5.4广义表的定义5.5广义表的存储结构5.6m元多项式的表示1．一维数组一维数组可以看成是一个线性表或一个向量（第二章已经介绍），它在计算机内是存放在一块连续的存储单元中，适合于随机查找。这在第二章的线性表的顺序存储结构中已经介绍。2．二维数组二维数组可以看成是向量的推广。5.1数组的定义例如，设A是一个有m行n列的二维数组，则A可以表示为：在此，可以将二维数组A看成是由m个行向量[X0，X1，…，Xm-1]T组成，其中，Xi=(ai0,ai1,….,ain-1)
2、，0≤i≤m-1；也可以将二维数组A看成是由n个列向量[Y0,Y1,……,Yn-1]组成，其中Yi=(a0i,a1i,…..,am-1i)，0≤i≤n-1。由此可知二维数组中的每一个元素最多可有二个直接前驱和两个直接后继（边界除外），故是一种典型的非线性结构。3．多维数组同理，三维数组最多可有三个直接前驱和三个直接后继，三维以上数组可以作类似分析。因此，可以把三维以上的数组称为多维数组，多维数组可有多个直接前驱和多个直接后继，故多维数组是一种非线性结构。ADTArray{数据对象：D＝{aj1,j2,...,ji,…,jn
3、ji=0,...,bi
4、-1,i=1,2,..,n}数据关系：R＝{R1,R2,...,Rn}Ri＝{
5、0jkbk-1,1kn且ki,0jibi-2,i=2,...,n}}ADTArray基本操作:4．抽象数据类型描述二维数组的定义:数据对象:D={aij
6、0≤i≤b1-1,0≤j≤b2-1}数据关系:R={ROW,COL}ROW={
7、0≤i≤b1-2,0≤j≤b2-1}COL={
8、0≤i≤b1-1,0≤j≤b2-2}基本操作：Init
9、Array(&A,n,bound1,...,boundn)DestroyArray(&A)Value(A,&e,index1,...,indexn)Assign(&A,e,index1,...,indexn)InitArray(&A,n,bound1,...,boundn)操作结果：若维数n和各维长度合法，则构造相应的数组A，并返回OK。DestroyArray(&A)操作结果：销毁数组A。Value(A,&e,index1,...,indexn)初始条件：A是n维数组，e为元素变量，随后是n个下标值。操作结果：若各下标不超界，则将所指定的A的元
10、素值赋给e，并返回OK。Assign(&A,e,index1,...,indexn)初始条件：A是n维数组，e为元素变量，随后是n个下标值。操作结果：若下标不超界，则将e的值赋给所指定的A的元素，并返回OK。5.2数组的顺序表示和实现数组一般不作插入或删除操作，即一旦建立了数组，则结构中的数据元素个数和元素之间的关系就不再发生变动。所以采用顺序存储是顺理成章的事情。但是数组是多维的，而存储空间却是一维的。有两种顺序映象的方式:1)以行序为主序(低下标优先)；2)以列序为主序(高下标优先)。行优先顺序1．存放规则（以二维数组为例）行优先顺序也称为低
11、下标优先。具体实现时，按行号从小到大的顺序，先将第一行中元素全部存放好，再存放第二行元素，第三行元素，依次类推……在BASIC语言、PASCAL语言、C/C++语言等高级语言程序设计中，都是按行优先顺序存放的。例如，对刚才的Am×n二维数组，可用如下形式存放到内存：a00，a01,…a0n-1，a10，a11，...，a1n-1，…，am-10，am-11，…，am-1n-1。即二维数组按行优先存放到内存后，变成了一个线性序列（线性表）。因此，可以得出多维数组按行优先存放到内存的规律：最左边下标变化最慢，最右边下标变化最快，右边下标变化一遍，与之
12、相邻的左边下标才变化一次。因此，在算法中，最左边下标可以看成是外循环，最右边下标可以看成是最内循环。2．地址计算由于多维数组在内存中排列成一个线性序列，因此，若知道第一个元素的内存地址，如何求得其它元素的内存地址？例如：以“行序为主序”的存储映象a0,1a0,0a0,2a1,0a1,1a1,2a0,1a0,0a0,2a1,0a1,1a1,2L我们可以将它们的地址排列看成是一个等差数列，假设每个元素占L个字节，元素aij的存储地址应为第一个元素的地址加上排在aij前面的元素所占用的单元数，而aij的前面有i行(0~i-1)共i×n个元素，而本行前面
13、又有j个(0~j-1)元素，故aij的前面一共有i×n+j个元素，设a00的内存地址为LOC(a00)，则aij的内存地址按等差数列计为
