数据结构chap005

第五章数组和广义表5.1数组的类型定义5.3稀疏矩阵的压缩存储5.2数组的顺序表示和实现5.4广义表的类型定义5.5广义表的表示方法5.6广义表操作的递归函数5.1数组的类型定义ADTArray{数据对象：D＝{aj1,j2,...,,ji,jn|ji=0,...,bi-1,i=1,2,..,n}数据关系：R＝{R1,R2,...,Rn}Ri＝{aj1,...ji,...jn,aj1,...ji+1,...jn|0jkbk-1,1kn且ki,0jibi-2,i=2,...,n}}ADTArray基本操作:二维数组的定义:数据对象:D={aij|0≤i≤b1-1,0≤j≤b2-1}数据关系:R={ROW,COL}ROW={ai,j,ai+1,j|0≤i≤b1-2,0≤j≤b2-1}COL={ai,j,ai,j+1|0≤i≤b1-1,0≤j≤b2-2}基本操作：InitArray(&A,n,bound1,...,boundn)DestroyArray(&A)Value(A,&e,index1,...,indexn)Assign(&A,e,index1,...,indexn)InitArray(&A,n,bound1,...,boundn)操作结果：若维数n和各维长度合法，则构造相应的数组A，并返回OK。DestroyArray(&A)操作结果：销毁数组A。Value(A,&e,index1,...,indexn)初始条件：A是n维数组，e为元素变量，随后是n个下标值。操作结果：若各下标不超界，则e赋值为所指定的A的元素值，并返回OK。Assign(&A,e,index1,...,indexn)初始条件：A是n维数组，e为元素变量，随后是n个下标值。操作结果：若下标不超界，则将e的值赋给所指定的A的元素，并返回OK。5.2数组的顺序表示和实现类型特点:1)只有引用型操作，没有加工型操作；2)数组是多维的结构，而存储空间是一个一维的结构。有两种顺序映象的方式:1)以行序为主序(低下标优先)；2)以列序为主序(高下标优先)。例如：称为基地址或基址。以“行序为主序”的存储映象二维数组A中任一元素ai,j的存储位置LOC(i,j)=LOC(0,0)+(b2×i＋j)×a0,1a0,0a0,2a1,0a1,1a1,2a0,1a0,0a0,2a1,0a1,1a1,2LL推广到一般情况，可得到n维数组数据元素存储位置的映象关系称为n维数组的映象函数。数组元素的存储位置是其下标的线性函数。其中cn=L，ci-1=bi×ci,1in。LOC(j1,j2,...,jn)=LOC(0,0,...,0)+∑cijii=1n5.3矩阵的压缩存储矩阵是在很多科学与工程计算中遇到的数学模型。在数学上，矩阵是这样定义的：它是一个由m×n个元素排成的m行（横向）n列（纵向）的表。下面就是一个矩阵：•它是一个m×n的矩阵。mnmmnnaaaaaaaaa.....................212222111211假设m行n列的矩阵含t个非零元素，则称为稀疏因子。通常认为0.05的矩阵为稀疏矩阵。nmt何谓稀疏矩阵？0200000000000210010070003以常规方法，即以二维数组表示高阶的稀疏矩阵时产生的问题:1)零值元素占了很大空间;2)计算中进行了很多和零值的运算，如是除法，还需判别除数是否为零。1)尽可能少存或不存零值元素；解决问题的原则:2)尽可能减少没有实际意义的运算；3)操作方便。即：能尽可能快地找到与下标值(i，j)对应的元素；能尽可能快地找到同一行或同一列的非零值元。1)特殊矩阵非零元在矩阵中的分布有一定规则例如:三角矩阵对角矩阵2)随机稀疏矩阵非零元在矩阵中随机出现有两类稀疏矩阵：所谓特殊矩阵就是元素值的排列具有一定规律的矩阵。常见的这类矩阵有：对称矩阵、下（上）三角矩阵、对角线矩阵等等。对称矩阵的特点是aij=aji，比如，下面就是一个对称矩阵：1423417232012341275173510•下（上）三角矩阵的特点是以主对角线为界的上（下）半部分是一个固定的值，下（上）半部分的元素值没有任何规律。比如，下面是一个下三角矩阵：20926130301080012600029•对角矩阵的特点是所有的非零元素都集中在以主对角线为中心的带状区域中。比如，下面就是一个3阶对角矩阵：11340006921000177300002059000123•压缩的方法是首先将二维关系映射成一维关系，并只存储其中必要的n(n+1)/2个（主对角线和下三角）元素内容，这些元素的存储顺序以行为主序。举例：•假设定义一个数组型变量：intA[10];01234567891057312201742314k是对称矩阵位于（i，j）位置的元素在一维数组中的存放位置。ji12)1(ji12)1(当当ijjjiik（2）下（上）三角矩阵下三角矩阵的压缩存储与上面讲述的对称矩阵的压缩存储一样，只是将上三角部分的常量值存储在0单元，下三角和主对角上的元素从1号单元开始存放。012345678910029612810301326920ji0ji2)1(当当jiik对于任意的（i，j），在一维数组中的存放位置可利用下列公式求得：（3）对角矩阵我们以三阶对角矩阵为例讨论一下它的压缩存储方法。对于对角矩阵，压缩存储的主要思路是只存储非零元素。这些非零元素按以行为主序的顺序，从下标为1的位置开始依次存放在一维数组中，而0位置存放数值0。0123456789101112130312952030717219-63411下面我们讨论一下对于任意给定的（i，j），求得在一维数组中存储位置k的方法。否则当0111i-j1)-(i3ijik随机稀疏矩阵的压缩存储方法:一、三元组顺序表二、行逻辑联接的顺序表三、十字链表#defineMAXSIZE12500typedefstruct{inti,j;//该非零元的行下标和列下标ElemTypee;//该非零元的值}Triple;//三元组类型一、三元组顺序表typedefunion{Tripledata[MAXSIZE+1];intmu,nu,tu;}TSMatrix;//稀疏矩阵类型如何求转置矩阵？028003600070500140005280000007143600用常规的二维数组表示时的算法其时间复杂度为:O(mu×nu)for(col=1;col=nu;++col)for(row=1;row=mu;++row)T[col][row]=M[row][col];用“三元组”表示时如何实现？121415-522-731363428211451-522-713364328首先应该确定每一行的第一个非零元在三元组中的位置。121515-522-731363428col12345Num[pos]12011Cpot[col]12445cpot[1]=1;for(col=2;col=M.nu;++col)cpot[col]=cpot[col-1]+num[col-1];StatusFastTransposeSMatrix(TSMatrixM,TSMatrix&T){T.mu=M.nu;T.nu=M.mu;T.tu=M.tu;if(T.tu){for(col=1;col=M.nu;++col)num[col]=0;for(t=1;t=M.tu;++t)++num[M.data[t].j];cpot[1]=1;for(col=2;col=M.nu;++col)cpot[col]=cpot[col-1]+num[col-1];for(p=1;p=M.tu;++p){}}//ifreturnOK;}//FastTransposeSMatrix转置矩阵元素Col=M.data[p].j;q=cpot[col];T.data[q].i=M.data[p].j;T.data[q].j=M.data[p].i;T.data[q].e=M.data[p].e;++cpot[col]分析算法FastTransposeSMatrix的时间复杂度：时间复杂度为:O(M.nu+M.tu)for(col=1;col=M.nu;++col)……for(t=1;t=M.tu;++t)……for(col=2;col=M.nu;++col)……for(p=1;p=M.tu;++p)……三元组顺序表又称有序的双下标法，它的特点是，非零元在表中按行序有序存储，因此便于进行依行顺序处理的矩阵运算。然而，若需随机存取某一行中的非零元，则需从头开始进行查找。二、行逻辑联接的顺序表#defineMAXMN500typedefstruct{Tripledata[MAXSIZE+1];intrpos[MAXMN+1];intmu,nu,tu;}RLSMatrix;//行逻辑链接顺序表类型修改前述的稀疏矩阵的结构定义，增加一个数据成员rpos，其值在稀疏矩阵的初始化函数中确定。例如：给定一组下标,求矩阵的元素值ElemTypevalue(RLSMatrixM,intr,intc){p=M.rpos[r];while(M.data[p].i==r&&M.data[p].jc)p++;if(M.data[p].i==r&&M.data[p].j==c)returnM.data[p].e;elsereturn0;}//value矩阵乘法的精典算法:for(i=1;i=m1;++i)for(j=1;j=n2;++j){Q[i][j]=0;for(k=1;k=n1;++k)Q[i][j]+=M[i][k]*N[k][j];}其时间复杂度为:O(m1×n2×n1)Q初始化；ifQ是非零矩阵{//逐行求积for(arow=1;arow=M.mu;++arow){//处理M的每一行ctemp[]=0;//累加器清零计算Q中第arow行的积并存入ctemp[]中；将ctemp[]中非零元压缩存储到Q.data；}//forarow}//if两个稀疏矩阵相乘（QMN）的过程可大致描述如下：StatusMultSMatrix(RLSMatrixM,RLSMatrixN,RLSMatrix&Q){if(M.nu!=N.mu)returnERROR;Q.mu=M.mu;Q.nu=N.nu;Q.tu=0;if(M.tu*N.tu!=0){//Q是非零矩阵for(arow=1;arow=M.mu;++arow){//处理M的每一行}//forarow}//ifreturnOK;}//MultSMatrixctemp[]=0;//当前行各元素累加器清零Q.rpos[arow]=Q.tu+1;for(p=M.rpos[arow];pM.rpos[arow+1];++p){//对当前行中每一个非零元brow=M.data[p].j;if(browN.nu)t=N.rpos[brow+1];else{t=N.tu+1}for(q=N.rpos[brow];qt;++q){ccol=N.data[q].j;//乘积元素在Q中列号ctemp[ccol]+=M.data[p].e*N.data[q].e;}//forq}//求得Q中第crow(=arow)行的非零元for(ccol=1;ccol=Q.nu;++ccol)if(ctemp[ccol]){if(++Q.tuMAXSIZE)returnERROR;Q.data[Q.tu]={arow,ccol,ctemp[ccol]};}//if处理的每一行M分析上述算法的时间复杂度累加器ctemp初始化的时间复杂度为(M.m