chapter05_数组和广义表_数据结构(c语言版)_严蔚敏_配套ppt课件

《chapter05_数组和广义表_数据结构(c语言版)_严蔚敏_配套ppt课件》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第五章数组和广义表5.1数组的类型定义5.2数组的顺序表示和实现5.3矩阵的压缩存储5.4广义表的类型定义5.5广义表的表示方法5.1数组的类型定义一、数组的定义•数组是有限个数据元素的集合;•数组的所有数组元素具有相同特性;•每个数组元素名由数组名和下标组成;•每组有定义的下标值都有一个与该下标对应的数组元素值.一维数组A[n]：简单的线性表(a1,a2,…,an)；二维数组A[m,n]：看成由m个行向量组成的线性表，或a00a01a02…a0,n-1a10a11a12…a1,n-1……………am-1,0am-1,1am-

2、1,2…am-1,n-1N维数组:看成其数据元素为n-1维数组类型的线性表。二、抽象数据类型数组的定义ADTArray{数据对：D＝{aj1,j2,...,,ji,jn

3、ji=0,...,bi-1,i=1,2,..,n}数据关系：R＝{R1,R2,...,Rn}Ri＝{

4、0≤jk≤bk-1,1≤k≤n且k≠i,0≤ji≤bi-2,i=2,...,n}基本操作:}ADTArray二维数组的定义:数据对象:D={aij

5、0≤i≤b1-1,0≤j≤b2-1}数据

6、关系:R={ROW,COL}ROW={

7、0≤i≤b1-2,0≤j≤b2-1}COL={

8、0≤i≤b1-1,0≤j≤b2-2}数组一旦被定义，其维数和维界就不再改变，因此，除了初始化和销毁之外，数组只有两种运算：⑴给定一组下标，存取相应的数据元素；⑵给定一组下标，修改相应数据元素中的某个数据项的值。数组不能进行元素的插入和删除运算。基本操作：InitArray(&A,n,bound1,...,boundn)DestroyArray(&A)Value(A,&e,index1,.

9、..,indexn)Assign(&A,e,index1,...,indexn)InitArray(&A,n,bound1,...,boundn)DestroyArray(&A)操作结果：若维数n和各维长度合法，则构造相应的数组A，并返回OK。操作结果：销毁数组A。Value(A,&e,index1,...,indexn)初始条件：A是n维数组，e为元素变量，随后是n个下标值。操作结果：若各下标不超界，则e赋值为所指定的A的元素值，并返回OK。Assign(&A,e,index1,...,indexn)初始条件：A是n维数组

10、，e为元素变量，随后是n个下标值。操作结果：若下标不超界，则将e的值赋给所指定的A的元素，并返回OK。5.2数组的顺序表示和实现类型特点:1)只有引用型操作，没有加工型操作；2)数组是多维的结构，而存储空间是一个一维的结构。有两种顺序映象的方式:1)以行序为主序(低下标优先)；2)以列序为主序(高下标优先)。以“行序为主序”的存储映象(P92)例如：a0,0a0,1a0,2a1,0a1,1a1,2a0,1a,00a0,2a1,0a1,1a1,2L二维数组A中任一元素ai,j的存储位置LOC(i,j)=LOC(0,0)+(b2

11、×i＋j)×L称为基地址或基址。推广到一般情况，可得到n维数组数据元素存储位置的映象关系：nLOC(j1,j2,...,jn)=LOC(0,0,...,0)+∑i=1ciji其中cn=L，ci-1=bi×ci,1

12、基址。5.3矩阵的压缩存储•压缩的含义–为多个值相同的元素只分配一个存贮空间；–零元素不分配或少分配存贮空间。•特殊矩阵：元素值相同或零元素分布有一定规律的矩阵。•稀疏矩阵：元素值相同或零元素分布没有规律的矩阵。•特殊矩阵的压缩存贮实际是将二维数组的数据元素压缩到一维数组上。特殊矩阵的压缩存储特殊矩阵:非零元在矩阵中的分布有一定规则例如:三角矩阵对角矩阵1、对称矩阵a00a11an-1n-1若n阶矩阵A满足aij=aji0≤i,j≤n-1则称为n阶对称矩阵。对于对称矩阵，我们可以为每一对对称元分配一个存储空间，则可将n2个元

13、压缩存储到n*(n-1)/2个元的空间中。不失一般性，我们可以以行序为主序存储其下三角（包括对角线）中的元。对称矩阵的压缩存储：a00a10a11a20…an-1,0…an-1,n-1存贮地址计算公式：Loc(aij)=Loc(a00)+[i*(i-1)/2+(j-1)]*L1、三角矩阵所