第5章 数组及广义表

《第5章 数组及广义表》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第5章数组和广义表（4学时）（一）教学目的：掌握数组的定义及顺序表示与实现；掌握矩阵的压缩存储；广义表的定义及存储结构。（二）教学重点：1、数组的定义及其存储2、特殊矩阵的压缩存储3、稀疏矩阵逻辑结构和存储结构4、广义表的逻辑结构和存储结构5、数组和广义表的操作应用举例（三）教学难点：1、矩阵的压缩存储2、广义表的存储结构5．1数组的定义一、数组的抽象类型定义：数据对象：D=

2、n(>0)称为数组的维数，bi是数组第i维的长度，ji是数组元素的第i维下标，∈ElemSet}数据关系：R={R1，R2，…，Rn}Ri=>0≤jk≤bk-1，1≤k≤n且

3、k≠i，0≤ji≤bi-2，∈D，I=2,…,n}二、数组基本操作：1、InitArray(&A,n,bound1,…,boundn)操作结果：若维数n和各维长度合法，则构造相应的数组A，并返回OK。2、DestroyArray（&A）操作结果：销毁数组A。3、Value(A,&e,indeex1,…,indexn)初始条件：A是n维数组，e为元素变量，随后是n个下标值。操作结果：若各下标不超界，则e赋值为所指定的A的元素值，并返回OK。4、Assign(&A,e,index1,…,indexn)初始条件：A是n维数组，e为元素变量，随后是n个下标

4、值。操作结果：若下标不超界，则将e的值赋给所指定的A的元素，并返回OK。三、数组与线性表的关系：1、二维数组与线性表的关系：以把二维数组看成是这样一具定长线性表：它的每个数据元素也是一个定长线性表。A=(a0,a1,…,ap)(p=m-1或n-1)其中每个数据元素aj是一个列向量形式的线性表aj=(a0j,aij,…,am-1j)0≤j≤n-1ai=(ai0,ai1,…,ai,n-1)0≤i≤m-1在C语言中，一个二维数组类型可以定义为其分量类型为一维数组类型的一维数组类型，也就是说，typedefElemTypeArray2[m][n];等价于t

5、ypedefElemTypeArray1[n];typedefArray1Array2[m];(a)(b)(C)图5·1二维数组图例（a）矩阵形式表示；（b）列向量的一维数组；（c）行向量的一维数组2、n维数组与线性表的关系：同理，一个n维数组类型可以定义为其数据元素为n-1维数组类型的一维数组类型。四、数组的基本操作数组一旦被定义，它的维数和维界就不再改变。因此，除了结构的初始化和销毁之外，数组只有存取元素和修改元素值的操作。5．2数组的顺序表示和实现一、二维数组的顺序存储：则用一组连续存储单元存放数组的数据元素就有个次序约定问题。对二维数组可有

6、两种存储方式：在扩展BASIC、PL/1、COBOL、PASCAL和C语言中，用的都是以行序为主序的存储结构，而在FORTRAN语言中，用的是以列序为主序的存储结构。（a）以列序为主序（b）以行序为主序图5.2二维数组的两种存储结构二、数组的地址计算：1、二维数组的地址计算：假设每个数据元素占L个存储单元，则二维数组A中任一元素aij的存储位置可由下式确定LOC（i,j）=LOC（0，0）+（b2×i+j）L(5——1)式中，LOC（i,j）是aij的存储位置；LOC（0，0）是a00的存储位置，即二维数组A的起始存储位置，也称为基地址或基址。2、

7、n维数组地址计算：LOC(j1,j2,…,jn)=LOC(0,0,…,0)＋(b2×…bn×j1＋b3×…bn×j2＋…＋bn×jn-1＋jn)L=LOC(0,0,…,0)＋()L或缩写成LOC（j1,j2,…,jn）=LOC(0,0,…,0)+(5—2)其中Cn=L,ci-1=bi×ci,1

8、为稀疏矩阵。5．3．1特殊矩阵一、对称矩阵：1、对称矩阵定义：若n阶矩阵A中的元满足下述性质aij=aji1≤i,j≤n，则称为n阶对称矩阵。2、对称矩阵的压缩存储：对于对称矩阵，我们可以为每一对对称元分配一个存储空间，则可将n2个元压缩存储到n(n+1)/2个元的空间中。3、压缩存储元素与存储地址之间的对应关系：假设以一维数组sa[n(n+1)/2]作为n阶对称矩阵A的存储结构，则sa[k]和矩阵元aij之间存在着一一对应的关系：（5—3）a11a21a31a41…an,1…an,nk=0123图5.3对称矩阵的压缩存储二、三角矩阵：所谓下（上）

9、三角矩阵是指矩阵的上（下）三角（不包括对角线）中的元均为常数c或零的n阶矩阵。则除了和对称矩阵一样只存储其下（上）三角中的