最新数据结构课件5教学讲义ppt课件.ppt

《最新数据结构课件5教学讲义ppt课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、数据结构课件55.1数组的类型定义5.3稀疏矩阵的压缩存储5.2数组的顺序表示和实现5.4广义表的类型定义5.5广义表的表示方法5.6广义表操作的递归函数2ADTArray{数据对象：D＝{aj1,j2,...,,ji,jn

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

3、0jkbk-1,1kn且ki,0jibi-2,i=2,...,n}}ADTArray基本操作:5.1数组的类型定义3DestroyArray(&A)操作结果：销毁数组A。7V

4、alue(A,&e,index1,...,indexn)初始条件：A是n维数组，e为元素变量，随后是n个下标值。操作结果：若各下标不超界，则e赋值为所指定的A的元素值，并返回OK。8Assign(&A,e,index1,...,indexn)初始条件：A是n维数组，e为元素变量，随后是n个下标值。操作结果：若下标不超界，则将e的值赋给所指定的A的元素，并返回OK。9类型特点:1)只有引用型操作，没有加工型操作;2)数组是多维的结构，而存储空间是一个一维的结构。有两种顺序映象的方式:1)以行序为主序(低下标优先);2)以列序为主序(高下标优先);5.2数组的顺序表示和实现10例如：

5、称为基地址或基址。以“行序为主序”的存储映象二维数组A中任一元素ai,j的存储位置LOC(i,j)=LOC(0,0)+(b2×i＋j)×a0,1a0,0a0,2a1,0a1,1a1,2a0,1a0,0a0,2a1,0a1,1a1,2LL11推广到一般情况，可得到n维数组数据元素存储位置的映象关系称为n维数组的映象函数。数组元素的存储位置是其下标的线性函数其中cn=L，ci-1=bi×ci,1

6、阵？5.3稀疏矩阵的压缩存储13以常规方法，即以二维数组表示高阶的稀疏矩阵时产生的问题:1)零值元素占了很大空间;2)计算中进行了很多和零值的运算，遇除法，还需判别除数是否为零;141)尽可能少存或不存零值元素;解决问题的原则:2)尽可能减少没有实际意义的运算;3)操作方便;即:能尽可能快地找到与下标值(i,j)对应的元素;能尽可能快地找到同一行或同一列的非零值元;151)特殊矩阵非零元在矩阵中的分布有一定规则例如:三角矩阵对角矩阵2)随机稀疏矩阵非零元在矩阵中随机出现有两类稀疏矩阵：165.3.1特殊矩阵所谓特殊矩阵是指非零元素或零元素的分布有一定规律的矩阵，下面我们讨论几种特

7、殊矩阵的压缩存储。1、对称矩阵在一个n阶方阵A中，若元素满足下述性质：aij=aji1≦i,j≦n则称A为对称矩阵。对称矩阵中的元素关于主对角线对称，故只要存储矩阵中上三角或下三角中的元素，让每两个对称的元素共享一个存储空间，这样，能节约近一半的存储空间。不失一般性，我们按“行优先17顺序”存储主对角线（包括对角线）以下的元素，其存储形式如图所示：图5.1对称矩阵15137a1150800a21a2218926a31a32a3330251………………..70613an1an2an2…ann在这个下三角矩阵中，第i行恰有i个元素，元素总数为：因此，我们可以按图中箭头所指的次序将这些

8、元素存放在一个向量sa[0..n(n+1)/2-1]中。为了便于访问对称矩阵A中的元素，我们必须在aij和sa[k]18之间找一个对应关系。若i≧j，则aij在下三角形中。aij之前的i-1行（从第1行到第i-1行）一共有1+2+…+(i-1)=i(i-1)/2个元素，在第i行上，aij之前恰有j-1个元素（即ai1,ai2,…,aij-1），因此有：k=i*(i-1)/2+j-10≦k

9、，J=min(i,j)，则k和i,j的对应关系可统一为：k=I*(I-1)/2+J-10≦k