数组和广义表.ppt
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 数组 广义
- 资源描述:
-
,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,第5章 数组和广义表,1,本章目录,5.1,数组的定义及其基本操作,5.1.1,数组,5.1.2,数组的逻辑定义,5.2,数组的顺序存储,5.3,矩阵的压缩存储,5.3.1,特殊矩阵,5.3.2,稀疏矩阵,2,知识点和难点重点,知识点,基本概念:数组、稀疏矩阵,数组地址计算,特殊矩阵,难点重点,特殊矩阵,3,数组,数组,逻辑上是线性结构的推广;,数组,是以元素为线性表的线性结构,而且元素的结构相同;,数组,可以看作是,下标和值的偶对,的集合;,数组,是一种,逻辑结构。,4,高级语言中的数组,int,a10;,char B45;,5,数组的逻辑定义,n(n1),维数组可看作是一个向量,它的每个元素是,n-1,维数组,且具有相同的上限和下限,6,n,维数组的元素个数,设,n,维数组为:,Ac,1,.d,1,c,2,.d,2,c,n,.d,n,,其元素个数为:,7,数组的操作,数组一般不做插入和删除操作,对于数组的操作一般只有两类:,Content 02,Content 01,给定一组下标存取相应的数据元素,给定一组下标修改相应的数据元素的值,8,顺序存储时按行序和列序的约定,数组顺序存储时,必须确定按行序或列序存储,:,PASCAL,、,C,以,行序为主,存储,1,2,FORTRAN,以,列序为主,存储,9,a,11,a,12,a,1n,a,21,a,22,a,2n,a,m1,a,m2,a,mn,a,11,a,21,a,m1,a,12,a,22,a,m2,a,1n,a,2n,a,mn,数组的顺序存储,以行为主序,以列为主序,10,设二维数组,Aij(c1id1,c2jd2),其中,c1,、,c2,和,d1,、,d2,分别为二维数组,A,的下标的下界和上界,每个数组元素占,L,个存储单元,设第一个元素,Ac1c2,的存储位置为,LOC(c1,c2),,则该二维数组中任一元素,Aij,的存储位置可由下式确定:,LOC(i,j,)=LOC(c1,c2)+(i-c1)*(d2-c2+1)+(j-c2)*L,在,C,语言,中,,下标从零开始,则数组元素,Aij,的存储位置是,:,LOC(i,j,)=LOC(0,0)+(i*(d2+1)+j)*L,数组的顺序,存储,如何从下标求得相应数组元素的存储位置?,11,n,维数组的元素存储位置,设,n,维数组为:,Ac,1,.d,1,c,2,.d,2,c,n,.d,n,LOC(j,1,j,2,j,n,),=LOC(c,1,c,2,c,n,)+(j,1,-c,1,)*(d,2,-c,2,+1)*(d,3,-c,3,+1)*(d,n,-c,n,+1),+(j,2,-c,2,)*(d,3,-c,3,+1)*(d,n,-c,n,+1),+(j,n-1,-c,n-1,)*(d,n,-c,n,+1)+(j,n,-c,n,)*L,=LOC(c,1,c,2,c,n,)+,N,维数组中,数组元素存储位置的确定:,12,三维数组的表示,若,l1=l2=l3=0;,LOC(i,j,k)=LOC(0,0,0)+(i*b2*b3+j*b3+k);,13,矩阵的压缩存储,压缩存储:,对多个值相同的元素分配一个存储空间,对零元素不分配空间。,两类矩阵:,非零元素分布有一定的规律,特殊矩阵,非零元素少,(,一般认为小于,5%),分布无规律,稀疏矩阵,14,特殊矩阵,(,对称矩阵,),对称矩阵,若,n,阶矩阵,A,中的元素满足下述性质,a,ij,=,a,ji,1i,jn,则称,A,为,n,阶对称矩阵,n,2,个元素可以压缩到,n(n+1)/2,个空间中;,以行序为主序将其下三角(包括对角线)中的元素存储到一个向量,Bn(n+1)/2,中,:,k=0 1 2 3,a,00,a,10,a,11,a,20,a,n-1,,,0,a,n-1,,,n-1,15,特殊矩阵(,对称矩阵,),(2),向量,Bk,和矩阵中的元素,a,ij,之间的关系:,由,i,和,j,推导,k,:,(1),向量,Bk,和矩阵中的元素,a,ij,之间存在着一一对应关系,16,特殊矩阵(,三角矩阵,),三角矩阵,:,下三角矩阵是指矩阵的上三角(不包括对角线)中的元素均为常数,c,或零的,n,阶矩阵,a,ij,和,Bk,之间的对应关系为,:,17,对角矩阵:,所有非零元素都集中在以主对角线为中心的带状区域中。即除了主对角线上和直接在对角线上、下方若,干条对角线上的元素之外,所有其它的元素均为零,特殊矩阵(,对角矩阵,),b,条对角线,n,行,n,列,(,a),a,11,a,12,a,21,a,22,a,23,a,n-1,n,a,n,n,a,n,n-1,O,O,(,b),18,三对角矩阵,a,11,a,12,a,21,a,22,a,23,a,n-1,n,a,n,n,a,n,n-1,O,O,三对角矩阵,:,共,3n-2,个元素,存入,B3n-2,中,元素在一维数组,B,中的下标,k,和元素在矩阵中的下标,i,和,j,的对应关系为:,k=3(i-1),(,主对角线左下角,即,i=j+1),k=3(i-1)+1,(,主对角线上,即,i=j),k=3(i-1)+2,(,主对角线右上角,即,i=j-1),由以上三式,得,k=2(i-1)+j,(1,i,j,n;1,k,3n-2),19,稀疏矩阵,非零元素较少,分布无规律,稀疏因子:,=t/(m*n)=0.05,存储结构,顺序存储结构,三元组表,链式存储结构,十字链表,20,三元组顺序表,define MAXSIZE 1000,用户自定义,typedef,struct,三元组,int,row,col,;,非零元的行、列号,ElemType,e;,非零元的值,Triple;,typedef,struct,Triple dataMAXSIZE+1;,三元组表,,data0,未用,int,m,n,len,;,矩阵的行数、列数和非零元个数,TSMatrix,;,21,压缩存储下矩阵的转置,转置矩阵的定义,:,对于一个,m,n,的矩阵,M,它的转置矩阵,T,是一个,n,m,的矩阵,且,Tij=Mji,(1=i=n,,,1=j=m),。,请看下面具体示例。,22,矩阵转置,row,col,e,1,2,6,1,6,-2,3,4,-8,4,2,3,4,6,7,5,1,-12,5,3,9,row,col,e,1,5,-12,2,1,6,2,4,3,3,5,9,4,3,-8,6,1,-2,6,4,7,23,矩阵转置,求一个矩阵的转置矩阵可以经过下列步骤来完成:,step1,step2,step3,将矩阵的行、列值互换,对每个三元组所表示的非零元,将该元素的行、列值互换,按行序重排三元组,24,三元组表的矩阵转置运算,row,col,e,1,2,6,1,6,-2,3,4,-8,4,2,3,4,6,7,5,1,-12,5,3,9,row,col,e,1,5,-12,2,1,6,2,4,3,3,5,9,4,3,-8,6,1,-2,6,4,7,1,2,3,4,5,6,7,25,矩阵转置,TSMatrix,TransMatrix(TSMatrix,A,TSMatrix,B),采用三元组表方式存储,实现矩阵的转置,B.m=A.n;B.n=A.m;,B.len,=,A.len,;,if(B.len,),q,l;,for(j,1;j,A.n;j+),for(p,1;p,A.len;+p),if(A.datap,col,=j),B.dataq,row,=,A.datap,col,;,B.dataq,col,=,A.datap,row,;,B.dataq,e,=,A.datap,e,;,q+;,return B;,26,算法分析,时间复杂度为:,n*,len,对于,m*n,矩阵,一般算法的时间复杂度为:,O(m,*n),。,当非零元个数,len,和,m*n,同数量级时,该算法的时间复杂度为:,O(m,*n,2,);,这里每次找第,j,列的元素时,必须从头开始遍历。,若知道,T,的每一行的非零元素的开始位置,就可把算法的时间复杂度降低。,27,矩阵的快速转置,思想:,一遍扫描,三元组表,A.data,,将每个元素放到转置后的三元组表,B.data,的,正确位置,上。因此,需求出矩阵,A,中,每列第一个非零元的位置,和,每列非零元素的个数,。为此,增加存放每列非零元素个数的一维数组,number,和每列第一个非零元素在,B,中位置的一维数组,position,。并有以下公式:,position0=0,positionj,=positionj-1+numberj-1 1j,A.n,28,number,和,position,向量实例,row,col,e,1,2,6,1,6,-2,3,4,-8,4,2,3,4,6,7,5,1,-12,5,3,9,row,col,e,1,5,-12,2,1,6,2,4,3,3,5,9,4,3,-8,6,1,-2,6,4,7,矩阵,A,的,number,和,position,向量的值:,j,0,1,2,3,4,5,numberj,1,2,1,1,0,2,positionj,0,1,3,4,5,5,29,TSMatrix,FastTransMatrix(TSMatrix,A,TSMatrix,B),三元组表上实现矩阵的快速转置的算法,B.m,=,A.n,;B.n=A.m;,B.len,=,A.len,;,if(A.len,),for(j=1;j=,A.n;j,+),矩阵,A,每一列非零元初始化为零,numberj=0;,for(t=1;t=,A.len;t,+),求矩阵,A,每一列的非零元个数,numberA.datat.col,+;,position1=0;,for(j=2;j=,A.n;j,+,;,求,A.data,第,j,列第一个非零元在,B.data,中的序号,positioncol,=positioncol-1+numbercol-1;,三元组表的矩阵快速转置,(1),30,for(p=1;px)j-;,else i+;,if(flag),printf(“A%d%d,=%,d”,i,j,x,);,/,假定,x,为整型,.,else,printf,(“,矩阵,A,中无,%d,元素”,,x),;,36,展开阅读全文

咨信网声明:本文档由用户上传并分享,仅供学习交流、研究之用,未经授权,严禁复制、发行、汇编、翻译或网络传播等,侵权必究。
咨信网小贴示:
1、浏览或下载可查看了解,请点击【咨信网告知】。
2、下载文件中如有侵权或不适当内容,将立即纠正。
3、如果因为网速或其他原因下载失败请重新下载,重复下载[60天内]不扣币。
4、开具发票登录电脑端申请,请点击【索取发票】。
咨信网客服组:【微信客服】
1、浏览或下载可查看了解,请点击【咨信网告知】。
2、下载文件中如有侵权或不适当内容,将立即纠正。
3、如果因为网速或其他原因下载失败请重新下载,重复下载[60天内]不扣币。
4、开具发票登录电脑端申请,请点击【索取发票】。
咨信网客服组:【微信客服】


数组和广义表.ppt
















自信AI助手














微信客服
客服QQ
发送邮件
意见反馈



链接地址:https://www.zixin.com.cn/doc/14772628.html