武汉理工大学-信息工程学院-数据结构-ppt-课件ch05-1-数组与广义表1-数组

第5章数组与广义表数据结构讲义—数组信息工程学院魏洪涛Email:[e-mail]数组和广义表数组和广义表可看成是一种特殊的线性表，其特殊在于，表中的数据元素本身也是一种线性表。几乎所有的程序设计语言都有数组类型。本节重点讲解稀疏矩阵的实现。5.1数组的定义由于数组中各元素具有统一的类型，并且数组元素的下标一般具有固定的上界和下界，因此，数组的处理比其它复杂的结构更为简单。多维数组是向量的推广。例如，二维数组：mnmmnnnmaaaaaaaaaA.................................212222111211()()()()()()()()()可以看成是由一个行向量组成的向量，也可以看成是由一个列向量组成的向量。5.2数组的顺序表示和实现由于计算机的内存结构是一维的，因此用一维内存来表示多维数组，就必须按某种次序将数组元素排成一列序列，然后将这个线性序列存放在存储器中。又由于对数组一般不做插入和删除操作，也就是说，数组一旦建立，结构中的元素个数和元素间的关系就不再发生变化。因此，一般都是采用顺序存储的方法来表示数组。通常有两种顺序存储方式:(1)以行序为主序(2)以列序为主序a11a12……..a1na21a22……..a2nam1am2……..amn………………….Loc(aij)=Loc(a11)+[(i-1)n+(j-1)]*l按行序为主序存放amn……..am2am1……….a2n……..a22a21a1n…….a12a1101n-1m*n-1n按列序为主序存放01m-1m*n-1mamn……..a2na1n……….am2……..a22a12am1…….a21a11a11a12……..a1na21a22……..a2nam1am2……..amn………………….Loc(aij)=Loc(a11)+[(j-1)m+(i-1)]*l计算二维数组元素地址的通式设一般的二维数组是A[c1..d1,c2..d2]，这里c1,c2不一定是0。无论规定行优先或列优先，只要知道以下三要素便可随时求出任一元素的地址（这样数组中的任一元素便可以随机存取！）：二维数组列优先存储的通式为：LOC(aij)=LOC(ac1，c2)+[(j-c2)*(d1-c1+1)+i-c1)]*Lac1,c2…ac1,d2…aij…ad1,c2…ad1,d2Amn=单个元素长度aij之前的行数数组基址总列数，即第2维长度aij本行前面的元素个数①开始结点的存放地址（即基地址）②维数和每维的上、下界；③每个数组元素所占用的单元数则行优先存储时的地址公式为：LOC(aij)=LOC(ac1，c2)+[(i-c1)*(d2-c2+1)+j-c2)]*L例2：已知二维数组Am,m按行存储的元素地址公式是：Loc(aij)=Loc(a11)+[(i-1)*m+(j-1)]*K,按列存储的公式是？Loc(aij)=Loc(a11)+[(j-1)*m+(i-1)]*K（尽管是方阵，但公式仍不同）例1〖软考题〗：一个二维数组A，行下标的范围是1到6，列下标的范围是0到7，每个数组元素用相邻的6个字节存储，存储器按字节编址。那么，这个数组的体积是个字节。288例3：〖某考研题〗设数组a[1…60,1…70]的基地址为2048，每个元素占2个存储单元，若以列序为主序顺序存储，则元素a[32,58]的存储地址为。8950LOC(aij)=LOC(ac1，c2)+[(j-c2)*(d1-c1+1)+i-c1)]*L得：LOC(a32,58)=2048+[(58-1)*(60-1+1)+32-1)]*2＝8950答：请注意审题！利用列优先通式：答：Volume=m*n*L=(6-1+1)*(7-0+1)*6=48*6=2885.3矩阵的压缩存储在矩阵中非零元素呈某种规律分布或者矩阵中出现大量的零元素的情况下，占用了许多单元去存储重复的非零元素或零元素，这对高阶矩阵会造成极大的浪费，为了节省存储空间，我们可以对这类矩阵进行压缩存储：–即为多个相同的非零元素只分配一个存储空间；–对零元素不分配空间。5.3.1特殊矩阵所谓特殊矩阵是指非零元素或零元素的分布有一定规律的矩阵，下面我们讨论几种特殊矩阵的压缩存储。1、对称矩阵在一个n阶方阵A中，若元素满足下述性质：aij=aji0≦i,j≦n-1则称A为对称矩阵。如图5.1便是一个5阶对称矩阵。对称矩阵中的元素关于主对角线对称，故只要存储矩阵中上三角或下三角中的元素。其存储形式如图所示：15137a0050800a10a1118926a20a21a2330251………………..70613an-10an-11an-12…an-1n-1图5.1对称矩阵在这个下三角矩阵中，第i行恰有i+1个元素，元素总数为：n(n+1)/2因此，我们可以按从上到下、从左到右将这些元素存放在一个向量sa[0..n(n+1)/2-1]中。为了便于访问对称矩阵A中的元素，我们必须在aij和sa[k]之间找一个对应关系。若i≧j，则aij在下三角形中。aij之前的i行（从第0行到第i-1行）一共有1+2+…+i=i(i+1)/2个元素，在第i行上，aij之前恰有j个元素（即ai0,ai1,ai2,…,aij-1），因此有：k=i*(i+1)/2+j0≦kn(n+1)/2若ij，则aij是在上三角矩阵中。因为aij=aji，所以只要交换上述对应关系式中的i和j即可得到：k=j*(j+1)/2+i0≦kn(n+1)/22、三角矩阵以主对角线划分，三角矩阵有上三角和下三角两种。上三角矩阵如图所示，它的下三角（不包括主对角线）中的元素均为常数。下三角矩阵正好相反，它的主对角线上方均为常数，如图所示。在大多数情况下，三角矩阵常数为零。a00a01…a0n-1a00c…cca11…a1n-1a10a11…c…………………..……………..cc…an-1n-1an-10an-11…an-1n-1(a)上三角矩阵(b)下三角矩阵三角矩阵中的重复元素c可共享一个存储空间，其余的元素正好有n(n+1)/2个，因此，三角矩阵可压缩存储到向量sa[0..n(n+1)/2]中，其中c存放在向量的最后一个分量中，上三角矩阵中，主对角线之上的第i行(0≦in)恰有n-i个元素，按行优先顺序存放上三角矩阵中的元素aij时，aij之前的i行一共有i(2n-i+1)/2个元素，在第i行上，aij前恰好有j-i个元素：aii,aii+1,…aij-1。因此，sa[k]和aij的对应关系是：k=i(2n-i+1)/2+j-i当i≦jn(n+1)/2当ij5.3.2稀疏矩阵什么是稀疏矩阵？简单说，设矩阵A中有s个非零元素，若s远远小于矩阵元素的总数（即sm×n），则称A为稀疏矩阵。精确地说，设在的矩阵A中，有s个非零元素。令e=s/(m*n)，称e为矩阵的稀疏因子。通常认为e≦0.05时称之为稀疏矩阵。用三元组表存储稀疏矩阵三元组表((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,8)这一对行、列、非零元的个数的描述，便可代表矩阵M：0129000000-30015000000012000180-3000014090024000024000000000–70180000000140001500–7000000000000000图5.4稀疏矩阵M和TM=T=一、三元组顺序表假设以顺序存储结构来表示三元组表，则可得到稀疏矩阵的一种压缩存储方法—三元顺序表。#definemaxsize10000typedefintdatatype;typedefstruct{inti,j;datatypev;}triplet;typedefstruct{tripledata[maxsize];intm,n,t;}tripletable;稀疏矩阵的转置的实现一个m×n的矩阵A，它的转置B是一个n×m的矩阵，且a[i][j]=b[j][i]，0≦i≦m，0≦j≦n，即A的行是B的列，A的列是B的行。将A转置为B，就是将A的三元组表a.data置换为表B的三元组表b.data，如果只是简单地交换a.data中i和j的内容，那么要得到按行优先顺序存储的b.data，就必须重新排列三元组的顺序。由于A的列是B的行，因此，按a.data的列序转置，所得到的转置矩阵B的三元组表b.data必定是按行优先存放的。7600070015000001800000240001400003000000000009120M6700000000014000000007000000024009018000121500300N678121213931-3361443245218611564-7ijv012345678maijv76813-3161521122518319342446-76314012345678mb?解决思路：只要做到将矩阵行、列维数互换将每个三元组中的i和j相互调换重排三元组次序，使mb中元素以N的行(M的列)为主序方法一：按M的列序转置即按mb中三元组次序依次在ma中找到相应的三元组进行转置。为找到M中每一列所有非零元素，需对其三元组表ma从第一行起扫描一遍。由于ma中以M行序为主序,所以由此得到的恰是mb中应有的顺序。算法描述：P99算法5.1算法分析：T(n)=O(M的列数n非零元个数t)，若t与mn同数量级，则)()(2nmOnT三元组表的转置算法演示678121213931-3361443245218611564-7ijv012345678ma76813-3161521122518319342446-76314ijv012345678mbqppppppppqqqqppppppppcol=1col=2方法二：快速转置即按ma中三元组次序转置，转置结果放入b中恰当位置此法关键是要预先确定M中每一列第一个非零元在mb中位置，为确定这些位置，转置前应先求得M的每一列中非零元个数实现：设两个数组num[col]：表示矩阵M中第col列中非零元个数cpot[col]：指示M中第col列第一个非零元在mb中位置显然有：cpot[1]=1;cpot[col]=cpot[col-1]+num[col-1];(2colma[0].j)1357889colnum[col]cpot[col]122232415061707600070015000001800000240001400003000000000009120M678121213931-3361443245218611564-7ijv012345678maijv012345678mbcolnum[col]cpot[col]11223235247158068179076813-3161521122518319342446-76314pppppppp4629753作业写完整C程序，描述稀疏矩阵，并且实现转置操作。