第5讲数组和广义表.pptx
《第5讲数组和广义表.pptx》由会员分享,可在线阅读,更多相关《第5讲数组和广义表.pptx(124页珍藏版)》请在咨信网上搜索。
1、Section 1Array 数组的抽象数据类型定义数组的抽象数据类型定义ADT Array D=aj1,j2,.,ji,jn|ji=0,.,bi-1,i=1,2,.,n (n称数组的维数,称数组的维数,bi是数组第是数组第i维的长度,维的长度,ji是数组元素的第是数组元素的第i维维下标下标)R=R1,R2,.,Rn Ri=|0 jk bk-1,1 k n且且k i,0 ji bi-2,i=2,.,n ADT Array 基本操作基本操作二维数组的定义二维数组的定义数据对象数据对象:D=aij|0ib1-1,0 jb2-1数据关系数据关系:R=ROW,COL COL=|0ib1-2,0jb2-
2、1 ROW=|0ib1-1,0 jb2-2基基 本本 操操 作作InitArray(&A,n,bound1,.,boundn)DestroyArray(&A)Value(A,&x,index1,.,indexn)Assign(&A,x,index1,.,indexn)InitArray(&A,n,bound1,.,boundn)操作结果:操作结果:若维数若维数 n 和各维长度和各维长度 合法,则构造相应的合法,则构造相应的 数组数组A,并返回,并返回OK。DestroyArray(&A)操作结果:操作结果:销毁数组销毁数组A。Value(A,&x,index1,.,indexn)初始条件:初始
3、条件:A是是n维数组,维数组,x为元素变为元素变 量,随后是量,随后是n 个下标值。个下标值。操作结果:操作结果:若各下标不超界,则若各下标不超界,则x赋值赋值 为所指定的为所指定的A 的元素值,并的元素值,并 返回返回OK。Assign(&A,x,index1,.,indexn)初始条件:初始条件:A是是n维数组,维数组,x为为 元素变量,随后是元素变量,随后是n 个下标值。个下标值。操作结果:操作结果:若下标不超界,则若下标不超界,则 将将 x的值赋给所指的值赋给所指 定的定的A的元素,并的元素,并 返回返回 OK。一维数组一维数组n n定义定义 相同类型的数据元素的集合。相同类型的数据元
4、素的集合。n n一维数组的示例一维数组的示例n n与顺序表的不同在于数组可以按与顺序表的不同在于数组可以按元素的下标直接存储和访问数组元素的下标直接存储和访问数组元素。元素。35 27 49 18 60 54 77 83 41 020 1 2 3 4 5 6 7 8 9一维数组一维数组(Array)类的定义类的定义template class Array Type*elements;/数组存放空间数组存放空间 int ArraySize;/当前长度当前长度 void getArray();/建立数组空间建立数组空间 public:Array(int Size=DefaultSize);Arra
5、y(const Array&x);Array()delete elements;Array&operator=/数组赋值数组赋值 (const Array&A);Type&operator(int i);/取元素值取元素值 int Length()const return ArraySize;/取数组长度取数组长度 void ReSize(int sz);/扩充数组扩充数组 一维数组一维数组公共操作的实现公共操作的实现template void Array:getArray()/私有函数:创建数组存储空间私有函数:创建数组存储空间 elements=new TypeArraySize;temp
6、late Array:Array(int sz)ArraySize=sz;getArray();template Array:Array(Array&x)int n=ArraySize=x.ArraySize;elements=new Typen;Type*srcptr=x.elements;Type*destptr=elements;while(n-)*destptr+=*srcptr+;template Array:Array(Array&x)int Size=x.ArraySize;elements=new TypeSize;for(int i=0;iSize;i+)elementsi=
7、x.elementsi;template Type&Array:operator(int i)if(i ArraySize-1)cerr “数组下标超界”endl;return NULL;return elementsi;template void Array:Resize(int sz)if(sz=0&sz!=ArraySize)Type*newarray=new Typesz;int n=(sz ArraySize)?sz:ArraySize;/按新的大小确定传送元素个数按新的大小确定传送元素个数 Type*srcptr=elements;Type*destptr=newarray;whi
8、le(n-)*destptr+=*srcptr+;delete elements;elements=newarray;ArraySize=sz;多维数组多维数组n n多维数组是一维数组的推广多维数组是一维数组的推广n n多维数组是一种非线性结构。其特点多维数组是一种非线性结构。其特点是是每一个数据元素可以有多个直接前每一个数据元素可以有多个直接前驱和多个直接后继驱和多个直接后继。n n数组元素的下标一般具有固定的下界数组元素的下标一般具有固定的下界和上界,因此它比其他复杂的非线性和上界,因此它比其他复杂的非线性结构简单。结构简单。数组元素的遍历数组元素的遍历1)以行序为主序以行序为主序(按行排
9、列按行排列):先排最右的下标先排最右的下标,依次向左依次向左,最后最后 排最左的下标排最左的下标2)以列序为主序以列序为主序(按列排列按列排列):先排最左的下标先排最左的下标,依次向右依次向右,最最 后排最右的下标后排最右的下标例如:例如:称为基地址基地址或基址。以以“行序为主序行序为主序”的存储映象的存储映象二维数组A中任一元素ai,j 的存储位置 LOC(i,j)=LOC(0,0)+(b2ij)a0,1a0,0a0,2a1,0a1,1a1,2a0,1a0,0a0,2a1,0a1,1a1,2L L 对于一般意义二维数组Ac1:d1,c2:d2,设每个元素占用1个存储单元,LOC(c1,c2)
10、是第一个元素ac1c2的存储位置则按行存放时,aij的存储位置为:LOC(i,j)=LOC(c1,c2)+(d2-c2+1)(i-c1)+(j-c2)则列行存放时,aij的存储位置为:LOC(i,j)=LOC(c1,c2)+(d1-c1+1)(j-c2)+(i-c1)推广到一般情况,可得到 n 维数组数据元素存储位置的映象关系 称为 n 维数组的映象函数。数组元素数组元素的存储位置是其下标的线性函数。的存储位置是其下标的线性函数。其中 cn=L,ci-1=bi ci,1 i n。LOC(j1,j2,.,jn)=LOC(0,0,.,0)+ci ji i=1n对于n维数组的一般情况Ac1:d1,c
11、2:d2,cn:dn,设每个元素占用个存储单元,LOC(c1,c2,cn)是第一个元素ac1c2cn的存储位置则按行存放时,aj1j2jn的存储位置如下:LOC(j1j2jn)=LOC(c1,c2,cn)+(j1-c1)(d2-c2+1)(dn-cn+1)+(j2-c2)(d3-c3+1)(dn-cn+1)+(jn-1-c n-1)(dn-cn+1)+(jn-c n)l则列行存放时,aj1j2jn的存储位置如下:LOC(j1j2jn)=LOC(c1,c2,cn)+(j1-c1)+(d1-c1+1)(j2-c2)+(d1-c1+1)(dn-2-cn-2+1)(jn-1-cn-1)+(d1-c1+
12、1)(dn-1-cn-1+1)(jn-cn)l稀疏矩阵稀疏矩阵(Sparse Matrix)非零元素个数非零元素个数远远少于矩阵元素个数远远少于矩阵元素个数假设假设 m 行行 n 列列的矩阵含的矩阵含 t 个非零元素个非零元素,则称则称 为为稀疏因子稀疏因子。通常认为通常认为 0.05 的矩阵为稀疏矩阵。的矩阵为稀疏矩阵。以常规方法,即以二维数组表示以常规方法,即以二维数组表示高阶的稀疏矩阵时产生的问题高阶的稀疏矩阵时产生的问题:1)零值元素占了很大空间零值元素占了很大空间;2)计算中进行了很多和零值的运算,计算中进行了很多和零值的运算,遇除法,还需判别除数是否为零遇除法,还需判别除数是否为零
13、。1)尽可能少存或不存零值元素;尽可能少存或不存零值元素;解决问题的原则解决问题的原则2)尽可能减少没有实际意义的运算;尽可能减少没有实际意义的运算;3)操作方便。操作方便。即:即:1.能尽可能快地找到与下标值能尽可能快地找到与下标值 (i,j)对应的元素,对应的元素,2.能尽可能快地找到同一行或能尽可能快地找到同一行或 同一列的非零值元。同一列的非零值元。1)特殊矩阵特殊矩阵 非零元在矩阵中的分布有一定规则 例如:三角矩阵 对角矩阵2)随机稀疏矩阵随机稀疏矩阵 非零元在矩阵中随机出现有两类稀疏矩阵有两类稀疏矩阵:特殊矩阵特殊矩阵 非零元在矩阵中的分布有一定规则非零元在矩阵中的分布有一定规则
14、例如例如:对称矩阵对称矩阵 三角矩阵三角矩阵 三对角矩阵三对角矩阵 n阶对称矩阵阶对称矩阵 aij=aji 1=i,j=j j(j-1)/2+i-1 当ij K=矩阵的压缩存储对称矩阵 a11 a12 .a1n a21 a22.a2n an1 an2 .ann .a11 a21 a22 a31 a32 an1 ann.k=0 1 2 3 4 n(n-1)/2 n(n+1)/2-1 按行序为主序:三角矩阵共计元素个三角矩阵共计元素个数为:数为:数为:数为:n(n+1)/2三角矩阵三角矩阵 a11 0 0.0 a21 a22 0.0 an1 an2 an3.ann .0Loc(aij)=Loc(a
15、11)+(+(j-1)*l i(i-1)2a11 a21 a22 a31 a32 an1 ann.k=0 1 2 3 4 n(n-1)/2 n(n+1)/2-1 按行序为主序:对角矩阵 a11 a12 0 .0 a21 a22 a23 0 0 0 0 an-1,n-2 an-1,n-1 an-1,n 0 0 an,n-1 ann.0 a32 a33 a34 0 0 Loc(aij)=Loc(a11)+2(i-1)+(j-1)|i-j|1a11 a12 a21 a22 a23 ann-1 ann.k=0 1 2 3 4 n(n-1)/2 n(n+1)/2-1 按行序为主序:随机稀疏矩阵的顺序压缩
16、存储随机稀疏矩阵的顺序压缩存储三元组表示法三元组表示法随机稀疏矩阵的链式压缩存储随机稀疏矩阵的链式压缩存储十字链表十字链表随机稀疏矩阵随机稀疏矩阵 非零元在矩阵中随机出现非零元在矩阵中随机出现十字链表十字链表3 0 0 50-1 0 02 0 0 01 1 31 4 52 2-13 112 1 Typedef struct OLNode int i,j;ElemType e;struct OLNode *right,*right;Typedef struct OLink*rhead,*lhead;int mu,nu,tu;#define MAXSIZE 12500 typedef struct
17、 int i,j;/该非零元的行下标和列下标 ElemType e;/该非零元的值 Triple;/三元组类型三元组类型三元组顺序表(三元组顺序表(C语言版)语言版)typedef union Triple dataMAXSIZE+1;int mu,nu,tu;TSMatrix;/稀疏矩阵类型稀疏矩阵类型已知稀疏矩阵三元组顺序表示例三元组顺序表示例三元组表示为稀疏矩阵三元组表的抽象数据类型稀疏矩阵三元组表的抽象数据类型(C+版版)const int MaxTerms=1000;template class SparseMatrix;template class Trituple friend
18、class SparseMatrix private:int row,col;/非零元素行号非零元素行号/列号列号 Type value;/非零元素的值非零元素的值templateclass SparseMatrixint Rows,Cols,Terms;/行行/列列/非零元素数非零元素数 Trituple smArrayMaxTerms;public:/三元组表三元组表 SparseMatrix(int Row,int Col,int Term);SparseMatrix&Transpose (SparseMatrix&);/转置转置 SparseMatrix&Add(SparseMatri
19、x a,SparseMatrixb);/相加相加SparseMatrix&Multiply(SparseMatrix a,SparseMatrixb);/相乘相乘 稀疏矩阵的转置稀疏矩阵的转置用常规的二维数组表示时的算法 其时间复杂度为其时间复杂度为:O(munu)for(col=1;col=nu;+col)for(row=1;row=mu;+row)Tcolrow=Mrowcol;n一个一个 m n 的矩阵的矩阵 A,它的转置矩阵,它的转置矩阵 B 是一个是一个 n m 的矩阵,且的矩阵,且 Aij=Bji。即矩阵即矩阵 A 的行成为矩阵的行成为矩阵 B 的的列,矩阵列,矩阵 A 的列成为矩
20、阵的列成为矩阵 B 的行。的行。n在稀疏矩阵的三元组表中,非零矩阵在稀疏矩阵的三元组表中,非零矩阵元素按行存放。当行号相同时,按列元素按行存放。当行号相同时,按列号递增的顺序存放。号递增的顺序存放。n稀疏矩阵的转置运算要转化为对应三稀疏矩阵的转置运算要转化为对应三元组表的转置。元组表的转置。稀疏矩阵稀疏矩阵转置矩阵转置矩阵用三元组表表示的稀疏矩阵及其转置用三元组表表示的稀疏矩阵及其转置稀疏矩阵转置算法思想稀疏矩阵转置算法思想n n设矩阵列数为设矩阵列数为 Cols,对矩阵三元组表对矩阵三元组表扫描扫描Cols 次。第次。第 k 次检测列号为次检测列号为 k 的的项。项。n n第第 k 次扫描找
21、寻所有列号为次扫描找寻所有列号为 k 的项,的项,将其行号变列号、列号变行号,顺次将其行号变列号、列号变行号,顺次存于转置矩阵三元组表。存于转置矩阵三元组表。template SparseMatrix&SparseMatrix:Transpose (SparseMatrix&a)SparseMatrix b(a.Cols,a.Rows,a.Terms);if(a.Terms 0)int CurrentP=0;for(int k=0;k a.Cols;k+)for(int i=0;i a.Terms;i+)if(a.smArrayi.col=k)b.smArrayCurrentP.row=a.s
22、mArrayi.col;b.smArrayCurrentP.col=a.smArrayi.row;b.smArrayCurrentP.value=a.smArrayi.value;CurrentP+;return b;时间复杂度时间复杂度O(nu*tu)按a.data中三元组的次序进行转换如果能预先确定矩阵如果能预先确定矩阵M中的每一列(即中的每一列(即T中中每一行)的第一个非零元在每一行)的第一个非零元在b.data中应有置,中应有置,则在对则在对a.data中的三元组依次转置时,便可中的三元组依次转置时,便可直接放到直接放到b.data中恰当的位置上去。中恰当的位置上去。(先求(先求M中每
23、一列非零元素的个数。)中每一列非零元素的个数。)首先应该确定每一列的第一个非零元首先应该确定每一列的第一个非零元在三元组中的位置。在三元组中的位置。cpot1=1;for(col=2;col=M.nu;+col)cpotcol=cpotcol-1+numcol-1;Status FastTransposeSMatrix(TSMatrix M,TSMatrix&T)T.mu=M.nu;T.nu=M.mu;T.tu=M.tu;if(T.tu)for(col=1;col=M.nu;+col)numcol=0;for(t=1;t=M.tu;+t)+numM.datat.j;cpot1=1;for(co
24、l=2;col=M.nu;+col)cpotcol=cpotcol-1+numcol-1;for(p=1;p=M.tu;+p)/if return OK;/FastTransposeSMatrix 转置矩阵元素Col=M.datap.j;/p=1 col=2;p=2 col=5q=cpotcol;/p=1 q=cpot2=2;p=2 q=cpot5=5T.dataq.i=M.datap.j;T.dataq.j=M.datap.i;T.dataq.e=M.datap.e;+cpotcol 分析算法FastTransposeSMatrix的时间复杂度:时间复杂度为时间复杂度为:O(M.nu+M.t
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 数组 广义
1、咨信平台为文档C2C交易模式,即用户上传的文档直接被用户下载,收益归上传人(含作者)所有;本站仅是提供信息存储空间和展示预览,仅对用户上传内容的表现方式做保护处理,对上载内容不做任何修改或编辑。所展示的作品文档包括内容和图片全部来源于网络用户和作者上传投稿,我们不确定上传用户享有完全著作权,根据《信息网络传播权保护条例》,如果侵犯了您的版权、权益或隐私,请联系我们,核实后会尽快下架及时删除,并可随时和客服了解处理情况,尊重保护知识产权我们共同努力。
2、文档的总页数、文档格式和文档大小以系统显示为准(内容中显示的页数不一定正确),网站客服只以系统显示的页数、文件格式、文档大小作为仲裁依据,平台无法对文档的真实性、完整性、权威性、准确性、专业性及其观点立场做任何保证或承诺,下载前须认真查看,确认无误后再购买,务必慎重购买;若有违法违纪将进行移交司法处理,若涉侵权平台将进行基本处罚并下架。
3、本站所有内容均由用户上传,付费前请自行鉴别,如您付费,意味着您已接受本站规则且自行承担风险,本站不进行额外附加服务,虚拟产品一经售出概不退款(未进行购买下载可退充值款),文档一经付费(服务费)、不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
4、如你看到网页展示的文档有www.zixin.com.cn水印,是因预览和防盗链等技术需要对页面进行转换压缩成图而已,我们并不对上传的文档进行任何编辑或修改,文档下载后都不会有水印标识(原文档上传前个别存留的除外),下载后原文更清晰;试题试卷类文档,如果标题没有明确说明有答案则都视为没有答案,请知晓;PPT和DOC文档可被视为“模板”,允许上传人保留章节、目录结构的情况下删减部份的内容;PDF文档不管是原文档转换或图片扫描而得,本站不作要求视为允许,下载前自行私信或留言给上传者【人****来】。
5、本文档所展示的图片、画像、字体、音乐的版权可能需版权方额外授权,请谨慎使用;网站提供的党政主题相关内容(国旗、国徽、党徽--等)目的在于配合国家政策宣传,仅限个人学习分享使用,禁止用于任何广告和商用目的。
6、文档遇到问题,请及时私信或留言给本站上传会员【人****来】,需本站解决可联系【 微信客服】、【 QQ客服】,若有其他问题请点击或扫码反馈【 服务填表】;文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“【 版权申诉】”(推荐),意见反馈和侵权处理邮箱:1219186828@qq.com;也可以拔打客服电话:4008-655-100;投诉/维权电话:4009-655-100。