资源描述：
《数据结构之数组 和广 义表.ppt》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。
1、Chap5数组和广义表5.1数组类型的定义5.2数组的顺序表示和实现5.3稀疏矩阵的压缩存储5.4广义表的类型5.5广义表的表示方法15.1数组的类型定义ADTArray{数据对象：D＝{aj1,j2,...,ji,...jN
2、ji=0,...,bi-1,i=1,2,..,N,称N(>0)为数组的维数,bi为数组第i维的长度，ji为数组元素的第i维下标，aj1...jN∈ElemSet}数据关系：R＝{R1,R2,...,RN}Ri＝{
3、0≤jk≤bk-1,1
4、≤k≤N且k≠i,0≤ji≤bi-2,aj1,...,ji,...,jN,aj1,...ji+1,...,jN∈D,i=2,...,N}基本操作}2数组中共有b1×b2×…×bn个元素，每个元素都处在n个关系中，但因为每个关系本身都是“线性关系”，所以数组也是线性结构。看一个二维数组的简单情况。a11a12…a1bj-1a21a22…a2bj-1…………abi-11abi-12…abi-1bj-1Aij=3D={ai,j
5、0≤i≤m-1,0≤j≤n-1,ai,j∈ElemType}R={ROW,COL}其中：COL={6、,ai,j>
7、i=1,…,m-2,0≤j≤n-1,ai-1,j,ai,j∈ElemType} (称作“行关系”)ROW={
8、j=1,…,n-2,0≤i≤m-1,ai,j-1,ai,j∈ElemType}(称作"列关系")4和线性表类似，数组中的每个元素都对应于一组下标(j1,j2,…jN)，每个下标的取值范围是0≤ji≤bi-1，称bi为第i维的长度(i=1,2,…,N)。因此，也可以将数组看成是由“一组下标”和“元素值”构成的二元组的集合。需要注意的是，在此给出的数组定义中，各维下标的下限均约定为常量0，
9、这只是C语言的限定。在一般情况下，数组每一维的下标ji的取值范围均可设置为任意值的整数。5基本操作InitArray(&A,n,bound1,...,boundn)DestroyArray(&A)Value(A,&e,index1,...,indexn)Assign(&A,e,index1,...,indexn) }ADTArray6Value(A,&e,index1,...,indexn)初始条件：A是n维数组，e为元素变量,随后是n个下标值。操作结果：若各下标不超界，则e赋值为所指定的A的元素值，并返回OK。7Assign(&A
10、,e,index1,...,indexn)初始条件：A是n维数组，e为元素变量，随后是n个下标值。操作结果：若下标不超界，则将e的值赋给A中指定下标的元素。85.2数组的顺序表示和实现类型特点1）只有引用型操作，没有加工型操作2）数组是多维的结构，而存储空间是一个一维的结构有两种顺序映像的方式：1）以行序为主序（低下标优先）2）以列序为主序（高下标优先）9由于数组中的数据元素之间是一个“多维"的关系，而存储地址是一维的，因此数组的顺序存储表示要解决的是一个"如何用一维的存储地址来表示多维的关系"的问题。10以图示的二维数组为例，“以
11、行为主”的存储结构是对二维数组进行“按行切分”，即将数组中的数据元素“按行依次排放”在存储器中ABCDEMNOPQUVXYZABCDEMNOPQUVXYZ01234012a00a01a02a03a04a10a11a12a13a14a20a21a22a23a24低下标先变化11“以列为主”的存储结构是对二维数组进行“按列切分”，即将数组中的数据元素“按列依次排放”在存储器中。AMUBNVCOXDPYEQZABCDEMNOPQUVXYZ01234012a00a10a20a01a11a21a02a12a22a03a13a23a04a14a
12、24高下标先变化12低下标优先变化a000=Aa001=Ba002=Ca010=Da011=Ea012=Fa100=Ga101=Ha102=Ia110=Ja111=Ka112=L13a000=Aa100=Ga010=Da110=Ja001=Ba101=HA011=Ea111=KA002=Ca102=IA012=Fa112=L高下标优先变化14行序为主序假设二维数组R[m][n]中每个数据元素占L个存储地址，并以LOC(i,j)表示下标为(i,j)的数据元素的存储地址，则该数组中任何一对下标(i,j)对应的数据元素在“以行为主”的顺序
13、映象中的存储地址为：LOC(i,j)=LOC(0,0)+(i×n+j)L ↑称为数组的基地址或基址在“以列为主”的顺序映象中的存储地址为：LOC(i,j)=LOC(0,0)+(j×m+i)L ↑称为数组的基地址或基址15类似地，假设三
