计算机基础综合PPT课件之数据结构-数组与广义表

数据结构第五章数组与广义表本章要点•深入掌握数组的相关概念,数组元素顺序存储位置的计算方法•掌握对特殊矩阵进行压缩时的下标变换公式.•了解稀疏矩阵的压缩存储方法•掌握广义表的结构特点及其存储表示方法数组的定义•数组的定义方式1–一个n维数组类型可以定义为其数组元素为n-1维数组的一维数组类型.–当n=1时,n维数组就退化为定长的线性表，每个元素不可再分解。1,11,10,11,111101,00100.....................nmmmnnnmaaaaaaaaaA数组的定义（2）•数组定义方式2（抽象数据类型数组）ADTArray{数据对象：ji=0,1,…bi-1,i=1,2,3,…,n.D={aj1j2…jn|n(0)称为数组维数，bi是数组第i维的长度，ji是数组元素的第i维下标，aj1j1…jnElemSet}数据关系：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,aj1…ji…jn,aj1…ji+1…jnD,i=2,…n}数组的定义（3）基本操作:InitArray(&A,n,bound1,…boundn)//构造数组A,维数n,各维长度bound1,…boundnDestroyArray(&A)//销毁数组AValue(A,&e,index1,…indexn)//将指定的A元素赋给eAssign(&A,e,index1,…indexn)//将e的值赋给所指定的A的元素}ADTArray数组的顺序存储•二维数组Am×n–元素aij,0≤i≤m-1,0≤j≤n-1–存储结构•以行序为主序Loc(i,j)=Loc(0,0)+(n*i+j)×L•以列序为主序Loc(i,j)=Loc(0,0)+(m*j+i)×L•n维数组的数据元素存储地址(以第一维优先存储)Loc(j1,j2,…jn)=Loc(0,0,…)+(b2×…bn×j1+b3×…bn×j2+bn×jn-1+jn)×L矩阵mnmmnnaaaaaaaaa.....................212222111211矩阵的存储•特殊矩阵–矩阵中的元素排列是有规律的–矩阵的非零元素很少•压缩存储–为多个值相同的元素只分配一个存储空间–对零元素不分配空间1423417232012341275173510对称矩阵示例对称矩阵•性质:在n阶矩阵A中,aij=aji,1≤i,j≤n•压缩存储:只存主对角线以上或以下元素(包括主对角线)。可用一维数组存储。•减少存储空间:n2-n(n+1)/2•下三角元素aij,(i≥j)与一维数组Sa[k](1≤k≤n)元素的对应关系k=i(i-1)/2+j-1•上三角元素aij,(i≤j)与一维数组Sa[k]元素的对应关系k=j(j-1)/2+i-1Sa下标k=01234…n(n+1)/2-2n(n+1)/2-1a00a10a11a20a21…an-1,n-3an-1,n-2an-1,n-1对角矩阵•性质:一个n阶方阵的所有非零元素都集中在以主对角为中心的带状区域中•压缩存储:将非零元素存储到一维数组中11340006921000177300002059000123004544433433322322211211aaaaaaaaaaa稀疏矩阵•性质:矩阵中大多数元素值为0,元素分布没有一定规律.•设在m×n矩阵中,有t个元素不为零,稀疏因子为:σ=t/(m×n)σ≤0.05时,称为稀疏矩阵•压缩存储方式:–三元组顺序存储–链表存储稀疏矩阵示例0200000000000210010070003三元组顺序表•形式描述:(i,j,aij)•存储表示#defineMAXSIZE12500typedefstruct{inti,j;ElemTypee;}Triple;三元组顺序表(2)typedefstruct{Tripledata[MAXSIZE+1];intmu,nu,tu;//矩阵的行数,列数和非零元个数}TSMatrix;存储特点:非零元在表中按行序有序存储;最后一行一个元素在data中的序号为tu.•示例0200000000000210010070003ije11315723-131-132-2542A.DataA.mu=5A.nu=5A.tu=6A=稀疏矩阵的转置算法•方法1：按列序递增转置法算法的基本思想是：按照被转置矩阵M的“列序”（即转置后T的行序）递增的顺序进行转置，并依次送入转置后矩阵的三元组表中，则转置后矩阵的三元组表恰好是以“行序为主序”StatusTransposeSMaxtrix(TSMatrixM,TSMaxtrix&T)//求M的转置矩阵T{T.mu=M.nu;T.nu=M.mu;T.tu=M.Tu;if(T.tu){q=1;//q为T.data数组下标,从1开始for(col=1;col=M.nu;++col)//按M.data的列读取for(p=1;p=M.tu;++p)//对所有非零元素{if(M.data[p].j==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;++q;}}returnOK;}算法的复杂度为O(M.nu×M.mu)•方法2：快速转置算法需要设num和cpot两个数组。–num[col]表示矩阵M中第col列的非零元素个数；–数组cpot[col]表示矩阵M第col列中第一个非零元素在T.data中恰当的存储位置。–存在下列公式：]1[]1[][;1]1[colnumcolcpotcolcpotcpotvoidFastTransposeSMatrix(TSMatrixM,TSMaxtrix&T){//求M的转置矩阵TT.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]++;//统计M中每一列含非零元个数cpot[1]=1;//求第col列中第一个非零元在T.data中的序号for(col=2;col≤M.nu;++col)cpot[col]=cpot[col-1]+num[col-1];•for(p=1;p≤M.tu;++p){•col=M.data[p].j;//取M.data的列号存放到col中•q=cpot[col];//q为T中当前存储位置•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]=cpot[col]+1;//计算第col列中下一个非零元素存储位置•}//for•}//if•}•时间复杂度为O(M.nu+M.tu)行逻辑链接的顺序表•目的:便于随机存储任意一行的非零元素•存储表示增加一个“行”信息的辅助数组rpostypedefstruct{Tripledata[MAXSIZE+1];//三元组表intrpos[MAXRC+1];//各行第一个非零元素的位置数组intmu,nu,tu;//矩阵的行数,列数和非零元个数}RLSMatrix;问题:rpos[row]rpos[row+1]-1分别代表什么?两个稀疏矩阵相乘求：Q=A×B初始化Q//Q.mu=A.mu;Q.nu=B.nu;Q.tu=0;If(A.tu*B.tu!=0)//逐行求积和{for(arow=1;arow=A.mu;++arow){ctemp[1……B.nu]=0;计算Q中第arow行的积和并存入ctemp[]中将ctemp[]中非零元素压缩到Q.data中}}两个稀疏矩阵相乘•采用行逻辑连接的顺序表存储稀疏矩阵A和B–(1)对A.data[1…A.tu]中的每一元素(i,k,A(i,k))(1≤i≤m1,1≤j≤n1)，找到B.data中所有对应的元素(k,j,B(k,j))(1≤i≤m2,1≤j≤n2)相乘并求累计和，即关键要找到所有满足:A.data[p].j=B.data[q].i的元素。–(2)两个稀疏矩阵相乘的乘积不一定是稀疏矩阵，乘积矩阵Q中的元素是否为非零元素，只有在求得其累加和后才能得到。两个稀疏矩阵相乘的详细算法StatusMultSMatrix(RLSMatrixA,RLSMatrixB,RLSMatrixQ){//求Q＝A×BIf(A.nu!=B.mu)returnERROR;Q.mu=A.mu;Q.nu=B.nu;Q.tu=0;//初始化Qif(A.tu*B.tu!=0){for(arow=1;arrow=A.mu;++arow){//处理A的每一行ctemp[]=0;//当前行各元素累加器清零Q.rpos[arow]=Q.tu+1;//计算当前行第一个非零元素的位置if(arowA.mu)ca=A.rpos[arow+1];//ca为A的下一行第一个非零元素的位置elseca=A.tu+1;//当前行为最后一行详细算法（2）for(p=A.rpos[arow];pca;++p){//对当前行的每一非零元素brow=A.data[p].j;//找到对应元素在B中的行号if(browB.mu)cb=B.rpos[brow+1];//cb为B的下一行第一个非零元素的位置elsecb=B.tu+1;//brow为B的最后一行for(q=B.rpos[brow];qcb;++q){ccol=B.data[q].j;//乘积元素在Q中列号ctemp[ccol]=ctemp[ccol]+A.data[p].e*B.data[q].e;}//forq}//forp详细算法（3）for(ccol=1;ccol=Q.nu;++ccol)//压缩存储该行非零元素if(ctemp[ccol]){Q.tu++;if(Q.tuMAXISIZE)returnERROR;Q.data[Q.tu]=(arow,ccol,ctemp[ccol]);}//if}//forarow}//ifreturnOK;}链式存储结构•带行指针向量的单链表表示法–每行的非0元素链成一个单链表–每行的头指针组成一个表头指针数组链式存储结构（2）•十字链表表示法–在链表中每个非0元素用一个含5个域的结点表示.–每行的头指针组成一个一维数组–每列的头指针组成一个一维数组•十字链表的结点结构ijedownright13242856-534723521-1A.cheadA.rhead链式存储结构(3)•十字链表存储表示typedefstructOLNode{inti,j;Elemtypee;structOLNode*right,*down;}OLNode,*Olink;typedefstruct{Olink*rhead,*chead;intmu,nu,tu;}CrossList;稀疏矩阵十字链表的创建•voidCreateSMatrix_OL(CrossList&A){//创建稀疏矩阵A•if(A)free(A);•scanf(&m,&n,&t);//输入A的行数、列数和非零元素个数•A.mu=m;A.nu=n;A.tu=t;•if(!(A.rhead=(OLink*)malloc((m+1)*sizeof(OLNode))))•exit(OVERFLOW);•if(!(A.chead=(OLink*)malloc((n+1)*sizeof(OLNode))))•exit(OVERFLOW);•A.rhead[]=A.chead[]=