《数据结构》课件第5章 数组与广义表.ppt

3、特殊矩阵的压缩存储非零元素的分布有一定规律的矩阵，叫做特殊矩阵（通常为高阶矩阵）。可以利用非零元素的分布规律，只存储非零元素，从而实现有效的压缩存储。常见的特殊矩阵包括上三角矩阵、下三角矩阵、带状矩阵。4、稀疏矩阵非零元素个数只占元素总数的25%—30%或低于这个百分数，并且分布没有规律的矩阵，称为稀疏矩阵（通常为高阶矩阵）。稀疏矩阵的顺序存储结构：三元组表稀疏矩阵的链式存储结构：十字链表5、广义表广义表是n个数据元素（d1，d2，d3，…，dn）的有限序列，其中di既可以是单个元素，也可以是一个广义表。在广义表（d1，d2，d3，…，dn）中，d1是广义表的表头，而（d2，d3，…，dn）称为广义表的表尾。广义表的头尾链表存储结构广义表的扩展线性链表存储结构广义表的简单操作5.5.2典型题选解例1已知数组M[1..10,－1..6,0..3]，求：（1）数组的元素总数；（2）若数组以下标顺序为主序存储，起始地址为1000，且每个数据元素占用3个存储单元，试分别计算M[2,4,2],M[5,－1,3]的地址。解：（1）数组的元素总数为：(10－1＋1)×(6－(－1)＋1)×(3－0＋1)=320（2）地址计算公式为：Loc[i,j,k]=Loc[c1,c2,c3]＋((d2－c2＋1)×(d3－c3＋1)×(i－c1)＋(d3－c3＋1)×(j－c2)＋(k－c3))×size在此c1=1，d1=10，c2=－1，d2=6，c3=0，d3=3，所以：Loc[2,4,2]=1000＋((6－(－1)＋1)×(3－0＋1)×(2－1)＋(3－0＋1)×(4－(－1))＋(2－0))×3=1162Loc[5,－1,3]=1000＋((6－(－1)＋1)×(3－0＋1)×(5－1)＋(3－0＋1)×(－1－(－1))＋(3－0))×size=1393例2已知上三角矩阵An×n，当ij时，aij=c，要求将其压缩存储到一维数组B[1..m]中。请说明压缩存储方法，并给出任意元素aij与B[k]的对应关系：k=f(i,j)。解：显然，上三角中共有n(n+1)/2个元素，下三角中所有相同元素c可以共享一个存储单元，所以一维数组B[1..m]的上界m=n(n+1)/2+1。将上三角中n(n+1)/2个元素逐行存放到一维数组B的前m－1个单元中，相同元素c存放在最后一个单元B[m]中。上三角中第t行共有n-t+1个元素，所以，对于上三角中任意元素aij而言，排在前面的i-1行中共有元素：在上三角的第i行中，排在aij前面的元素数目为：j-(i-1)-1=j-i。所以，对于上三角中任意元素aij而言，排在aij前面的元素数目为：因此，上三角中任意元素aij在一维数组B中的位置为：综上所述，上三角矩阵An×n中任意元素aij与B[k]的对应关系为：当ij时，当i=j时，[思考题]：如何编写从一维数组B中取出任意元素aij的函数GetValue(i,j)？例3已知广义表L=((x,y,z),a,(u,t,w))，从L表中取出原子u的运算是：A)head(tail(tail(L)))B)tail(head(head(tail(L))))C)head(tail(head(tail(L))))D)head(head(tail(tail(L))))解：取出原子u的过程如下：1）用tail运算去掉表头(x,y,z)，即：tail(L)=(a,(u,t,w))2）再用tail运算去掉表头a，即：tail(tail(L))=((u,t,w))3）用head运算取出表头(u