第五章数据结构-数组与广义表.ppt

《第五章数据结构-数组与广义表.ppt》由会员分享，可在线阅读，更多相关《第五章数据结构-数组与广义表.ppt（23页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。

1、上页上页 下页下页节节末页末页结束结束无论在数值计算抑或非数值计算中数组无论在数值计算抑或非数值计算中数组均有广泛的应用均有广泛的应用,因此因此,绝大多数高级语言绝大多数高级语言都将数组设定为固有数据类型都将数组设定为固有数据类型,提供数组提供数组的定义和操作方法的定义和操作方法.如如C语言中语言中int a45;a11=2本章一方面以抽象数据类型的的角度讨本章一方面以抽象数据类型的的角度讨论数组的定义和实现论数组的定义和实现(广义线性表广义线性表)，加深，加深对数组的理解；另一方面，对数组的理解；另一方面，讨论一些特讨论一些特殊结构的矩阵殊结构的矩阵(如稀疏矩阵如稀疏矩阵)的定义和存储的定义

2、和存储表示方法表示方法引引第五章第五章 数组和广义表数组和广义表5.1 数组的定义5.2 数组的顺序表示和实现5.3 5.3 特殊矩阵的压缩存储特殊矩阵的压缩存储5.45.7 广义表的定义/存储与表示上页上页 下页下页节节末页末页结束结束：5.1 5.1 数组的定义数组的定义ADT Array 数据对象数据对象:Daj1,j2,.jn|n为维数,设第i维长度为bi,则ji=0.bi-1 数据关系数据关系：RR1,R2,.,Rn /Ri代表第i维上的相邻关系 Ri|0jk bk-1,0jibi-2 基本操作：基本操作：InitArray(&A,n,bound InitArray(&A,n,bou

3、nd1 1,.,.,boundboundn n)/n /n为维数，为维数，boundboundi i为第为第i i维长度维长度 DestroyArray(&ADestroyArray(&A)Assign(&AAssign(&A,e,index1,.,e,index1,.,indexnindexn)/将指定下标的元素赋值为e Value(AValue(A,&e,index,&e,index1 1,.,.,indexindexn n)/用用e e返回指定下标的元素的值返回指定下标的元素的值/ADT Array普通数组的各项操作普通数组的各项操作都不会引起元素的插都不会引起元素的插入或删除，故数组常

4、入或删除，故数组常采用顺序存储结构采用顺序存储结构上页上页 下页下页节节末页末页结束结束5.2 5.2 数组的顺序表示和实现数组的顺序表示和实现高维数组是个多维的结构，而存储空间是顺序编址的一维结构，如何存储多维数组呢？a0,1a0,0a0,2a1,0a1,1a1,2a00a01a02a10a11a12a00a10a01a11a02a12行优先,以行为主序,如C/Basic列优先,以列为主序,如Fortran数组为随机存取结构,以下标从零开始的二维数组为例,在以行序为主的存储结构中aij的存储地址Loc(i,j)：Loc(0,0)+(i*b2+j)*sizeof(ElemType)其中b2为一

5、行中元素个数即第二维长度对以列序为主的存储结构或者更高维的数组,元素的存储地址类似可得数组操作的具体实现各语言不同,如下标越界的检查，此处不作要求上页上页 下页下页节节末页末页结束结束说明：说明：二维数组可以看作一种特殊的一维数组，该一维数组的每个元素又是一个一维数组（如原二维数组的一行）。例如C中二维数组“float b34”可看作是由b0、b1和b2组成的一维数组，而b0可以看作由首行元素b00、b01、b02和b03组成的一维数组，b1与b2类似。Fortran或更高维的数组类似b0b1b2b00b10b20b01b11b21b02b12b22b03b13b23btypedef elem

6、type array_2mn;等价于：typedef elemtype array_1n;/行 typedef array1 array_2m;数组可看作普通线性表的一个推广，表中的每个数据元素本身又是一种线性表数据结构上页上页 下页下页节节末页末页结束结束5.3 5.3 矩阵的压缩存储矩阵的压缩存储5.3.1 特殊矩阵特殊矩阵-对称矩阵对称矩阵 1 5 1 3 7 a11 *5 0 8 0 0 a21 a22 *1 8 9 2 6 a31 a32 a33 *3 0 2 5 1 .7 0 6 1 3 an 1 a n 2 an 3 ann压缩压缩:n*n:n*n对称矩阵实际需对称矩阵实际需存储

7、的元素数为存储的元素数为1+2+n=n(n+1)/21+2+n=n(n+1)/2存储存储:动态分配的一维数组动态分配的一维数组+矩阵阶数矩阵阶数 typedeftypedef structstruct ElemTypeElemType*elemelem;intint length;length;SymMatrixSymMatrix;操作示例操作示例初始化对称矩阵初始化对称矩阵:Status Status InitSymMatrix(SymMatrixInitSymMatrix(SymMatrix M,intM,int n)n)M.elemM.elem=(=(ElemTypeElemType*)

8、*)malloc(sizeof(ElemTypemalloc(sizeof(ElemType););if(!M.elem)exit(OVERFLOWif(!M.elem)exit(OVERFLOW););M.lengthM.length=0;return OK;=0;return OK;上页上页 下页下页节节末页末页结束结束5.3 5.3 矩阵的压缩存储矩阵的压缩存储5.3.1 特殊矩阵特殊矩阵-对称矩阵对称矩阵 1 5 1 3 7 a11 *5 0 8 0 0 a21 a22 *1 8 9 2 6 a31 a32 a33 *3 0 2 5 1 .7 0 6 1 3 an 1 a n 2 an

9、 3 ann压缩存储压缩存储:typedeftypedef structstruct ElemTypeElemType*elemelem;intint length;length;SymMatrixSymMatrix;操作示例操作示例-取元素操作取元素操作GetElem(M,i,j,&eGetElem(M,i,j,&e)/取取i i行行j j列元素用列元素用e e返回返回,i1,j1,i,i1,j1,i与与j j要合法要合法 i=j i=j时为时为k=k=(1+2+i-1)(1+2+i-1)+j j -1-1=(i*(i-1)/2)+j-1=(i*(i-1)/2)+j-1 ij ij时转换为求

10、时转换为求ajiaji，如上，如上 k=(j*(j-1)/2)+i-1k=(j*(j-1)/2)+i-1思考思考:已知已知k k求求i/ji/j：k -1 -2 k -1 -2 -(i-1)-(i-1)直至直至0 0 余余j-1j-1上上/下三角矩阵、对角矩阵下三角矩阵、对角矩阵:类似找对应关系类似找对应关系,分析分析+验证验证上页上页 下页下页节节末页末页结束结束5.3.2 5.3.2 稀疏矩阵稀疏矩阵(SparseMatrixSparseMatrix)普通存储结构问题：普通存储结构问题：用二维数组存储稀疏矩阵，一方面用二维数组存储稀疏矩阵，一方面空间利用率低，实际只存储非零元素即可，其余默

11、认为空间利用率低，实际只存储非零元素即可，其余默认为“零零”;另一方面，很多操作可仅处理非零元素，如转置另一方面，很多操作可仅处理非零元素，如转置解决原则解决原则：1)尽可能少存或不存“零值零值”元素；2)尽可能减少没有实际意义的运算1 2 141 5 -52 2 -73 1 363 4 28u稀疏矩阵稀疏矩阵:稀疏因子稀疏因子=t/(m*n)0.05的矩阵的矩阵 上页上页 下页下页节节末页末页结束结束1 1、静态分配的三元组顺序表存储结构、静态分配的三元组顺序表存储结构1 2 141 5 -52 2 -73 1 363 4 28#define MAXSIZE 12500 typedef st

12、ruct int i,j;/非零元的下标 ElemType e;/非零元的值 Triple;/三元组类型三元组类型typedef struct Triple dataMAXSIZE+1;/data0不用不用 int mu,nu,tu;/行列序号序号与非零元个数 TSMatrix;/三元组顺序表类型类型上页上页 下页下页节节末页末页结束结束矩阵转置在三元组顺序表中的实现矩阵转置在三元组顺序表中的实现B=AB=AT T1 2 141 5 -52 2 -73 1 363 4 28记记P98：初始化新稀疏矩阵初始化新稀疏矩阵按照按照B中的出现次序对中的出现次序对A中元素逐个转置中元素逐个转置列号列号c

13、ol 从从1变到变到n,每次从头至尾扫描每次从头至尾扫描M.data,对列标等于对列标等于col的的三元组，将其行标、列标互换后放入三元组，将其行标、列标互换后放入T.data中中2 1 145 1 -52 2 -71 3 364 3 28上页上页 下页下页节节末页末页结束结束TransposSMatrix(M,&TTransposSMatrix(M,&T)Status TransposSMatrix(TSMatrix M,TSMatrix&T)/列号col 从1变到n,每次从头至尾扫描M.data,对列标等于col的三元组，将其行标、列标互换后依次放入T.data中 T.mu=S.nu;T.

14、nu=S.mu;T.tu=S.tu;if(T.tu)q=1;for(col=1;col=M.nu;+col)/原原A中列号由小变大中列号由小变大 for(p=1;p=M.tu;+p)/遍历遍历A中所有非零元素中所有非零元素 if(M.datap.j=col)/找列标等于找列标等于col元素修改后入元素修改后入B T.dataq.e=M.datap.e;T.dataq.i=M.datap.j;T.dataq.j=M.datap.i;+q;return OK;/复杂度复杂度O(M.nu*M.tu).二维数组转置二维数组转置O(M.nu*M.mu).当足够稀疏当足够稀疏以致以致M.tuM.mu时当前

15、算法更有效时当前算法更有效,否则不然否则不然,最坏最坏O(M.mu*M.nu2)关键原因在于要重复遍历多次顺序表,能否只遍历一次，直接将M中的元素转置后放入B中”恰当恰当”位置呢？上页上页 下页下页节节末页末页结束结束int cpotM.nu+1；cpot1=1;for(col=2;col=M.nu;+col)cpotcol=cpotcol-1+numcol-1;确定M中每一列拥有的非零元个数,记入数组numcolM中第col列的第一个元素在T中的位置cpotcol满足满足cpot(1)=1且且cpotcol=cpotcol-1+numcol-1用用p遍历遍历M,第一次遇到的列标为第一次遇到的

16、列标为col的元素直接插入到的元素直接插入到T中中cpotcol,每插入一个都将每插入一个都将cpotcol增增1,后遇到后遇到col列的元素直接插入列的元素直接插入cpotcolFastTransposSMatrix(M,&TFastTransposSMatrix(M,&T)int numM.nu+1;/0号不用，故多分配号不用，故多分配1个个 for(col=1;col=M.nu;+col)numcol=0;for(t=1;t=M.tu;+t)+numM.datat.j;上页上页 下页下页节节末页末页结束结束for(p=1;p=M.tu;+p)col=M.datap.j;/求列号 q=cp

17、otcol;/求插入位置T.dataq.i=M.datap.j;T.dataq.j=M.datap.i;T.dataq.e=M.datap.e;+cpotcol;/插入位置自增用用p遍历遍历M,第一次遇到的列标为第一次遇到的列标为col的元素直接插入到的元素直接插入到T中中cpotcol,每插入一个都将每插入一个都将cpotcol增增1,后遇到后遇到col列的元素直接插入列的元素直接插入cpotcol上页上页 下页下页节节末页末页结束结束Status FastTransposeSMatrix(TSMatrix M,TSMatrix&T)T.mu=M.nu;T.nu=M.mu;T.tu=M.tu

18、;if(T.tu)for(col=1;col=M.nu;+col)numcol=0;/初始化 for(t=1;t=M.tu;+t)+numM.datat.j;/求各列非零元个数 cpot1=1;/M中第1个列标为1的非零元必在T的第1位置 for(col=2;col=M.nu;+col)/求col列第1非零元在T中位置 cpotcol=cpotcol-1+numcol-1;for(p=1;p=M.tu;+p)/if return OK;/FastTransposeSMatrix元素转置插入cpotcol,后cpotcol+时间复杂度为时间复杂度为:O(M.nu+M.tu)空间多空间多numco

19、l与与cpotcol,O(M.nu)上页上页 下页下页节节末页末页结束结束稀疏矩阵的十字链表表示：稀疏矩阵的十字链表表示：3 0 0 50-1 0 02 0 0 01 1 31 4 52 2-13 1 2 typedef Struct OLink*rhead,*chead;/行、列链表头指针数组 int mu,nu,tu CrossList上页上页 下页下页节节末页末页结束结束小结：小结：l对称矩阵、上对称矩阵、上/下三角矩阵、对角矩阵的压缩下三角矩阵、对角矩阵的压缩存储与下标计算存储与下标计算l稀疏矩阵的三元组顺序存储表示与稀疏矩阵的三元组顺序存储表示与(快速快速)转置转置操作操作l了解稀疏

20、矩阵的十字链表表示了解稀疏矩阵的十字链表表示l作业作业7三对角矩阵三对角矩阵Ann,非零元逐行存储到非零元逐行存储到一维数组一维数组B3n-2中中,问问ij到到k及及k到到ij变换公式变换公式l推荐：推荐：1 2 5 6 7 8 21 25上页上页 下页下页节节末页末页结束结束 三元组顺序表中随机存取某一行中的非零元需从头开始进行查找，为此可加入一个行表来记录稀疏矩阵中每行的第一个非零元素在三元组表中的位置。称这种带“行链接信息”的三元组顺序表为行逻辑链接的顺序表 选选 行逻辑链接的顺序表行逻辑链接的顺序表 typedef struct Triple dataMAXSIZE+1;/三元组表,d

21、ata0不用,下同 int rposMAXMN+1;/记录各行第1个非零元的位置 int mu,nu,tu;RLSMatrix;/行逻辑链接顺序表类型#define MAXSIZE 12500 typedef struct int i,j;ElemType e;Triple;上页上页 下页下页节节末页末页结束结束例如：给定下标，求矩阵的元素值例如：给定下标，求矩阵的元素值ElemType value(RLSMatrix M,int r,int c)k=M.rposr;while(M.datak.i=r&M.datak.j c)k+;if(M.datak.i=r&M.datak.j=c)retu

22、rn M.datak.e;else return 0;/注意分析效率提升的情况上页上页 下页下页节节末页末页结束结束 for(i=1;i=m1;+i)for(j=1;j=n2;+j)Qij=0;for(k=1;k=n1;+k)Qij+=Mik*Nkj;其时间复杂度为其时间复杂度为:O(m1n2n1)矩阵乘法经典算法矩阵乘法经典算法Q=MN上页上页 下页下页节节末页末页结束结束初始化Q；/Q.tu=0if(Q是”合法”矩阵)/逐行求积 for(Mrow=1;Mrow=M.mu;+Mrow)/处理M各行 Qtemp1.T.nu=0;/Q中当且行各列累加器清零 计算计算Q中当前行的积并存入中当前行的

23、积并存入Qtemp 中；中；遍历Qtemp将非零元压缩存储到Q.data+Q.tu；稀疏矩阵相乘（稀疏矩阵相乘（Q M N）遍历M中当前行非零元M.datarposMrow.rposMrow+1-1,设在j列 遍历N中第j行非零元N.datarposj.rposJ+1-1,设坐标为jcol 计算M.dataMrowj*N.datajcol累计至Qtempcol上页上页 下页下页节节末页末页结束结束 if(M.nu!=N.mu)return ERROR;Q.mu=M.mu;Q.nu=N.nu;Q.tu=0;if(M.tu*N.tu!=0)/Q是非零矩阵 for(Mrow=1;Mrow=M.mu;

24、+Mrow)/逐行求积逐行求积 Qtemp1.T.nu=0;/Q中当且行各列累加器清零 计算计算Q中当前行的积并存入中当前行的积并存入Qtemp 中；中；遍历Qtemp将非零元压缩存储到Q.data+Q.tu /if return OK;Status Status MultSMatrixMultSMatrix(RLSMatrix M,RLSMatrix N,RLSMatrix&Q)上页上页 下页下页节节末页末页结束结束 ctemp=0;/当前行各元素累加器清零 Q.rposarow=Q.tu+1;for(p=M.rposarow;pM.rposarow+1;+p)/对当前行中每一个非零元 br

25、ow=M.datap.j;if(brow N.nu)t=N.rposbrow+1;else t=N.tu+1 for(q=N.rposbrow;q t;+q)ccol=N.dataq.j;/乘积元素在Q中列号 ctempccol+=M.datap.e*N.dataq.e;/for q /求得Q中第crow(=arow)行的非零元 for(ccol=1;ccol MAXSIZE)return ERROR;Q.dataQ.tu=arow,ccol,ctempccol;/if处理 的每一行M上页上页 下页下页节节末页末页结束结束分析上述算法的时间复杂度分析上述算法的时间复杂度累加器ctemp初始化的

26、时间复杂度为(M.muN.nu)，求Q的所有非零元的时间复杂度为(M.tuN.tu/N.mu)，进行压缩存储的时间复杂度为(M.muN.nu)，总的时间复杂度就是总的时间复杂度就是(M.mu N.nu+M.tu N.tu/N.mu)。若若M是是m行行n列的稀疏矩阵，列的稀疏矩阵，N是是n行行p列的稀疏矩阵，列的稀疏矩阵，则则M中非零元的个数中非零元的个数 Mate=M m n，N中非零元的个数中非零元的个数 N.tu=N n p，相乘算法的时间复杂度就是相乘算法的时间复杂度就是 (m p(1+n M N)，当当 M0.05 和和 N0.05及及 n 1000时，时，相乘算法的时间复杂度就相当于相乘算法的时间复杂度就相当于 (m p)。