第5章数组和广义表.pptx

数组和广义表可看成是一种特殊的线性表，其特殊在于，表中的所有元素本身也是一种线性表。二维数组可以看成是由行向量组成的向量，也可以看成是由列向量组成的向量。1、顺序存储结构通常有两种顺序存储方式：以上规则推广到多维数组的情况：行优先顺序可规定为先排最右的下标，从右到左，最后排最左的下标；例如，二维数组Amn按“行优先顺序”存储在内存中，假设每个元素占用d个存储单元。上述讨论均是假设数组各维的下界是1，更一般的二维数组是A[c1..d1,c2..d2]，这里c1,c2不一定是1。aij前一共有i-c1行，二维数组一共有d2-c2+1列，故这i-c1行共有(i-c1)*(d2-c2+1)个元素，在第i行上aij前一共有j-c2个元素，因此，aij的地址计算函数为：在高级语言编制程序时，将一个矩阵描述为一个二维数组。但是在矩阵中非零元素呈某种规律重复分布或者矩阵中出现大量的零元素的情况下，实际上占用了许多单元去存储重复的非零元素或零元素，这对高阶矩阵会造成极大的浪费，为了节省存储空间，可以对这类矩阵进行压缩存储。1、对称矩阵a00a10a11a20a21a22………………..an-10an-11an-12…an-1n-1若i≧j，则aij在下三角形中。aij之前的i行（从第0行到第i-1行）一共有1+2+…+i=i(i+1)/2个元素，在第i行上，aij之前恰有j个元素（即ai0,ai1,ai2,…,aij-1），因此有：因此，aij的地址可用下列式计算：LOC(aij)=LOC(sa[k])=LOC(sa[0])+k*d=LOC(sa[0])+[I*(I+1)/2+J]*d以主对角线划分，三角矩阵有上三角和下三角两种。在带状矩阵中，所有的非零元素集中在以主对角线为中心的带状区域中，即除了主对角线和主对角线相邻两侧的若干条对角线上的元素之外，其余元素皆为零。这个带状区域若包含主对角线下面及上面各d条对角线上的元素，那么，该方阵称为半带宽为d的带状矩阵。2d+1称为带状矩阵的带宽。非零元素仅出现在主对角上、紧邻主对角线上面的d条对角线上和紧邻主对角线下面的d条对角线上。显然，当∣i-j∣>d时，元素aij=0。上述的各种特殊矩阵，其非零元素的分布都是有规律的，因此总能找到一种方法将它们压缩存储到一个一维数组中，并且一般都能找到矩阵中的元素与该一维数组元素的对应关系，通过这个关系，能对矩阵的元素进行随机存取。在存储稀疏矩阵时，为了节省存储单元，很自然地想到使用压缩存储方法。但由于其非零元素的分布一般是没有规律的，因此在存储非零元素的同时，还必须同时记下它所在的行和列的位置（i，j)。例如，下列三元组表((1,2,12),(1,3,9),(3,1,-3),(3,6,14),(4,3,24),(5,2,18),(6,1,15),(6,4,-7))加上(6,7)这一对行、列值便可作为下列矩阵M的另一种描述。而由上述三元组表的不同表示方法可引出稀疏矩阵不同的压缩存储方法。#defineM20typedefstructnode{inti,j;intv;}JD;JDma[M];3、求转置矩阵一个m×n的矩阵A，它的转置B是一个n×m的矩阵，且aij=bji，0≤i≤m-1，0≤j≤n-1，即A的行是B的列，A的列是B的行。由于A的列是B的行，因此，按a.data的列序转置，所得到的转置矩阵B的三元组表b.data必定是按行优先顺序存放的。StatusTransposeSMatrix(TSMatrixM,TSMatrix&T)这个算法，主要的工作是在p和col的两个循环中完成的，故算法的时间复杂度为O(nu*tu)，即矩阵的列数和非零元的个数的乘积成正比。而一般传统矩阵的转置算法为：当非零元素的个数tu和mu*nu同数量级时，方法一的时间复杂度为O(mu*nu2)。按照a.data中三元组的次序进行转置，并将转置后的三元组置入b.data中的恰当位置。实现：需要附设num和cpot两个数组。num[col]：表示矩阵M中第col列中非零元的个数；cpot[col]：指示矩阵M中第col列第一个非零元在mb中的位置显然有：StatusFastTransposeSMatrix(TSMatrixM,TSMatrix&T){for(col=2;col<=M.nu;++col)cpot[col]=cpot[col-1]+num[col-1];//求第col列中第1个非零元素在b.data中的序号。这个算法仅比前一个算法多用了两个辅助数组。typedefstructOLNode{inti，j;ElemTypee;structOLNode*down,*right;}OLNode,*OLink;i1还有一种情况是：和A矩阵中的某个非零元相对应，和矩阵A’中是零元，即对