数据结构第五章课件数组和广义表_第1页
数据结构第五章课件数组和广义表_第2页
数据结构第五章课件数组和广义表_第3页
数据结构第五章课件数组和广义表_第4页
数据结构第五章课件数组和广义表_第5页
已阅读5页,还剩47页未读 继续免费阅读

下载本文档

版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领

文档简介

数据结构第五章课件数组和广义表第1页,共52页,2023年,2月20日,星期六5.1.1数组的定义数组是大家都已经很熟悉的一种数据类型,几乎所有高级语言程序设计中都设定了数组类型。1.一维数组一维数组可以看成是一个线性表或一个向量(第2章已经介绍),它在计算机内是存放在一块连续的存储单元中,适合于随机查找。这在第2章的线性表的顺序存储结构中已经介绍。5.1多维数组的定义第2页,共52页,2023年,2月20日,星期六2.二维数组二维数组中的每一个元素最多可有两个直接前驱和两个直接后继(边界除外),故是一种典型的非线性结构。例如,设A是一个有m行n列的二维数组,则A可以表示为:二维数组可以看成是这样一个定长的线性表,它的每个数据元素也是一个定长的线性表。第3页,共52页,2023年,2月20日,星期六二维数组可以看成是一个线性表A=(a0,a1,……,an-1)其中每个数据元素aj是一个列向量形式的线性表A=(a0,a1,……,an-1)第4页,共52页,2023年,2月20日,星期六或者,可以看成是一个线性表A=(a0,a1,……,am-1)其中每个数据元素aj是一个行向量形式的线性表A=(a0,a1,...am-1)第5页,共52页,2023年,2月20日,星期六同理,n维数组可以看成是这样一个定长的线性表,它的每个数据元素也是n-1维的数组。n维数组最多可有n个直接前驱和n个直接后继,故n维数组是一种非线性结构。3.n维数组

第6页,共52页,2023年,2月20日,星期六数组的操作数组一旦被定义,它的维数和维界就不再改变,因此,除了结构的初始化和销毁之外,数组只有存取元素和修改元素值的操作。第7页,共52页,2023年,2月20日,星期六数组宜采用顺序存储结构:由于数组一般不作插入或删除操作,也就是说,一旦建立了数组,则结构中的数组元素个数和元素之间的关系就不再发生变动,即它们的逻辑结构就固定下来了,不再发生变化。本章仅重点讨论二维数组的存储,三维及三维以上的数组可以作类似分析。5.2数组顺序表示和实现第8页,共52页,2023年,2月20日,星期六由于计算机内存结构是一维的(线性的),因此,用一维内存存放多维数组就必须按某种次序将数组元素排成一个线性序列,然后将这个线性序列顺序存放在存储器中。二维数组的顺序存储有两种形式:怎样将数组中元素存入到计算机内存中呢?第9页,共52页,2023年,2月20日,星期六1.行优先顺序a00a01……a0,n-1a10a11……a1,n-1am-1,0am-1,1……am-1,n-1……在BASIC语言、PASCAL语言、C/C++语言等高级语言程序设计中,都是按行优先顺序存放的。可以得出多n维数组按行优先存放到内存的规律:最左边下标变化最慢,最右边下标变化最快,右边下标变化一遍,与之相邻的左边下标才变化一次。a0a1am-1第10页,共52页,2023年,2月20日,星期六2.列优先顺序a00a10……am-1,0a01a11……am-1,

1a0,n-1a1,n-1……am-1,n-1……在FORTRAN语言程序设计中,数组是按列优先顺序存放的。可以得出n维数组按行优先存放到内存的规律:最左边下标变化最慢,最右边下标变化最快,右边下标变化一遍,与之相邻的左边下标才变化一次。a0a1am-1第11页,共52页,2023年,2月20日,星期六二维数组元素存储位置的计算设二维数组Am×n的起始地址(基地址),即a00的起始地址为LOC(0,0),每个数据元素占L个存储单元,则A中任一元素aij的起始地址为:行优先顺序:LOC(i,j)=LOC(0,0)+(i*n+j)*L列优先顺序:LOC(i,j)=LOC(0,0)+(j*m+i)*L第12页,共52页,2023年,2月20日,星期六三维数组元素存储位置的计算设三维数组Am×n×p的起始地址(基地址),即a000的起始地址为LOC(0,0,0),每个数据元素占L个存储单元,则A中任一元素aijk的起始地址为:行优先顺序:LOC(i,j,k)=LOC(0,0,0)+(i*n*p+j*p*k)*L列优先顺序:LOC(i,j,k)=LOC(0,0,0)+(k*m*n+j*m+i)*L第13页,共52页,2023年,2月20日,星期六所以,数组元素是其下标的线性函数.由于计算各个元素存储位置的时间相等,所以存取数组中任一元素的时间也相等.我们称具有这一特点的存储结构为随机存储结构.第14页,共52页,2023年,2月20日,星期六矩阵是一个二维数组,它是很多科学与工程计算问题中研究的数学对象。当矩阵的阶数很大时将会占较多存储单元。而当里面的元素分布呈现某种规律时,这时,从节约存储单元出发,可考虑若干元素共用一个存储单元,即进行压缩存储。所谓压缩存储是指:为多个值相同的元素只分配一个存储空间,值为零的元素不分配空间。假若值相同的元素或者零元素在矩阵中的分布有一定规律,则此类矩阵为特殊矩阵;非零元素较零元素少,且分布没有一定规律的矩阵,为稀疏矩阵.5.3矩阵的压缩存储第15页,共52页,2023年,2月20日,星期六1.对称矩阵若一个n阶方阵A中元素满足下列条件:aij=aji其中1≤i,j≤n,则称A为对称矩阵。例如,下图是一个3*3的对称矩阵。5.3.1特殊矩阵图一个对称矩阵第16页,共52页,2023年,2月20日,星期六对称矩阵的压缩存储为每一对对称元分配一个存储空间,则可将n2个元压缩存储到n(n+1)/2个元的空间中.以行优先存储其下三角(包括对角线)中的元.假设以一维数组sa[n(n+1)/2]作为n阶对称矩阵A的存储结构,则sa[k]和矩阵元素aij存在一一对应关系:K=i(i-1)/2+j-1当i≥jj(j-1)/2+i-1当i<jai1………aij

aiisaa11a21a22a31…an1…annk0123n(n-1)/2n(n+1)/2-1第17页,共52页,2023年,2月20日,星期六所谓下(上)三角矩阵中接线员矩阵的上(下)三角(不包括)对角线)中的无均为常数c或零的n阶矩阵.与对称矩阵类似,除了只存储其下(上)三角中的元之个外,再加一个存储常数C的存储空间即可.2.三角矩阵第18页,共52页,2023年,2月20日,星期六(a)上三角矩阵b)下三角矩阵图5.2三角矩阵第19页,共52页,2023年,2月20日,星期六所有的非零元都集中在以主对角线为中心的带状区域中的矩阵.如:三对角矩阵3.对角矩阵(带状矩阵)第20页,共52页,2023年,2月20日,星期六在实际应用中,我们还经常会遇到一类矩阵:其矩阵阶数很大,非零元个数较少,零元很多,但非零元的排列没有一定规律,我们称这一类矩阵为稀疏矩阵。按照压缩存储的概念,要存放稀疏矩阵的元素,由于没有某种规律,除存放非零元的值外,还必须存储适当的辅助信息,才能迅速确定一个非零元是矩阵中的哪一个位置上的元素。5.3.2稀疏矩阵第21页,共52页,2023年,2月20日,星期六在压缩存放稀疏矩阵的非零元同时,若还存放此非零元所在的行号和列号,则称为三元组表法,即称稀疏矩阵可用三元组表进行压缩存储,但它是一种顺序存储(按行优先顺序存放)。一个非零元有行号、列号、值,为一个三元组,整个稀疏矩阵中非零元的三元组合起来称为三元组表。1.三元组顺序表第22页,共52页,2023年,2月20日,星期六图三元组的结构eji第23页,共52页,2023年,2月20日,星期六稀疏矩阵的三元组顺序表存储表示:#defineMAXSIZE12500

/*非零元素的最多个数*/typedefstruct{inti,j;

/*该非零元素的行下标和列下标*/

ElemType

e;/*该非零元素的值*/}Triple;typedefstruct{Triple

data[MAXSIZE+1];/*非零元素的三元组表。data[0]未用*/

intmu,

nu,tu;/*矩阵的行数、列数和非零元素的个数*/}TSMatrix;第24页,共52页,2023年,2月20日,星期六稀疏矩阵M对应的三元组表121213931-3361443245218611564-7第25页,共52页,2023年,2月20日,星期六000000稀疏矩阵N对应的三元组表13-3161521122518319342446-76314-T第26页,共52页,2023年,2月20日,星期六000000在三元组表存储结构下的

矩阵的转置运算所谓的矩阵转置是指变换元素的位置,把位于(i,j)位置上的元素换到(j,i)位置上,也就是说,把元素的行列互换。如下图的6×7矩阵M,它的转置矩阵就是7×6的矩阵N,并且N(i,j)=M(j,i),其中,1≤i≤7,1≤j≤6。-T第27页,共52页,2023年,2月20日,星期六算法分析显然,稀疏矩阵的转置仍旧是稀疏矩阵。假设M和T分别表示矩阵M和T.如何由M得到T呢?ije121213931-3361443245218611564-7ije13-3161521122518319342446-76314M.dataT.data只需(1)将每个元组中的i,j相互调换(2)重排三元组的次序第28页,共52页,2023年,2月20日,星期六处理方法1:按照T.data中三元组的次序依次在M.data中找到相应的三元组进行转置.即,按照M的列序进行转置StatusTransposeSMatrix(TSMatrixM,TSMatrix&T){T.mu=M.nu;T.nu=M.mu;T.tu=M.tu;if(T.tu){q=1;for(col=1;col<=M.nu;++col)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(nu*tu)当tu和mn*nu等数量级时为O(mu*nu2)第29页,共52页,2023年,2月20日,星期六处理方法2:按照M.data中三元组的次序依次进行转置,并将转置后的三元组置入T.data中恰当的位置.为了能将待转置三元组M.data中元素一次定位到三元组T.data的正确位置上,需要预先计算以下数据:①

待转置矩阵M每一列中非零元素的个数。(即转置后矩阵T每一行中非零元素的个数)。②

待转置矩阵M每一列中第一个非零元素在三元组T.data中的正确位置(即转置后矩阵T每一行中第一个非零元素在三元组T.data中的正确位置。)第30页,共52页,2023年,2月20日,星期六为此,需要设两个num[]和cpot[]。其中num[col]用来存放矩阵M中第col列中非零元素个数(转置矩阵T中第col行非零元素的个数)。cpot[col]用来存放转置前矩阵M中第col列(转置后矩T中第col行)中第一个非零元素在三元组T.data中的正确位置。则cpot[1]=1,cpot[col]=cpot[col-1]+num[col-1]。

其中2≤col≤M.nu。c第31页,共52页,2023年,2月20日,星期六StatusTransposeSMatrix(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)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];}//for}//ifreturnOK;}O(nu+tu)当tu和mn*nu等数量级时为O(mu*nu)第32页,共52页,2023年,2月20日,星期六为了便于随机存取任意一行的非零元,则需知道每一行的第一个非零元在三元组表中的位置。为此可将上节快速转置矩阵的算法中创建的,指示“行”信息的辅助数组cpot固定在稀疏矩阵的存储结构中。其类型描述如下:typedefstruct{Triple

data[MAXSIZE+1];//非零元素的三元组表intrpos[MAXRC+1];//各行第一个非零元的位置表

intmu,

nu,tu;//矩阵的行数、列数和非零元素的个数}RLSMatrix2.行逻辑链接的顺序表第33页,共52页,2023年,2月20日,星期六当矩阵的非零元个数和位置在操作过程中变化较大时,就不宜采用顺序存储结构来表示了。如“将矩阵B加至矩阵A”操作,由于非零元的插入或删除将会引起A.data中元素的移动,此时宜采用链式存储。十字链表为稀疏矩阵中的链接存储中的一种较好的存储方法3.十字链表第34页,共52页,2023年,2月20日,星期六每一个非零元用一个结点表示,结点包括五个域:除了表示非零元所在的行、列和值的三元组(i,j,e)外,还需增加两个链域:行指针域(right),用来指向本行中下一个非零元素;列指针域(down),用来指向本列中下一个非零元素。十字链表结点定义ijrightdowne第35页,共52页,2023年,2月20日,星期六稀疏矩阵中同一行的非零元通过向右的right指针链接成一个带表头结点的线性链表。同一列的非零元也通过down指针链接成一个带表头结点的线性链表。因此,每个非零元既是第i行循环链表中的一个结点,又是第j列循环链表中的一个结点,相当于处在一个十字交叉路口,故称链表为十字链表。可用两个分别存储行链表的头指针和列链表的头指针的一维数组表示之。十字链表类型定义第36页,共52页,2023年,2月20日,星期六M=0050-100200011314522-1312M.rheadM.chead^^^^^^^例:矩阵M的十字链表第37页,共52页,2023年,2月20日,星期六稀疏矩阵的十字链表存储表示typedefstructOLNode{inti,j;

/*该非零元素的行下标和列下标*/

ElemType

e;/*该非零元素的值*/structOLNode*right,*down;}OLNode;*Olink;typedefstruct{Olink*rhead,*chead;

intmu,

nu,tu;}CrossList;第38页,共52页,2023年,2月20日,星期六广义表是第2章提到的线性表的推广。线性表中的元素仅限于原子项,即不可以再分,而广义表中的元素既可以是原子项,也可以是子表(另一个线性表)。广义表也称为列表(lists).1.广义表的定义广义表是n≥0个元素a1,a2,…,an的有限序列,其中每一个ai或者是原子,或者是一个子表。5.4广义表的定义第39页,共52页,2023年,2月20日,星期六广义表通常记为LS=(a1,a2,…,an),其中LS为广义表的名字,n为广义表的长度,每一个ai为广义表的元素,可以是单个元素(原子),也可以是广义表(子表)。在习惯中,一般用大写字母表示广义表,小写字母表示原子。当广义表LS非空时,称第一个元素a1为LS的表头(Head),称其余元素组成的表(a2,…,an)是LS的表尾(Tail).第40页,共52页,2023年,2月20日,星期六(1)A=(),A为空表,长度为0。(2)B=(a,(b,c)),B是长度为2的广义表,第一项为原子,第二项为子表。(3)C=(x,y,z),C是长度为3的广义表,每一项都是原子。(4)D=(B,C),D是长度为2的广义表,每一项都是上面提到的子表。(5)E=(a,E),是长度为2的广义表,第一项为原子,第二项为它本身。2.广义表举例第41页,共52页,2023年,2月20日,星期六(1)用LS=(a1,a2,…,an)形式,其中每一个ai为原子或广义表例如:A=(b,c)B=(a,A)E=(a,E)都是广义表。3.广义表的表示方法第42页,共52页,2023年,2月20日,星期六(2)将广义表中所有子表写到原子形式,并利用圆括号嵌套例如,上面提到的广义表A、B、C可以描述为:A(b,c)B(a,A(b,c))E(a,E(a,E(…)))第43页,共52页,2023年,2月20日,星期六(3)将广义表用树和图来描述(a)A=(b,c)(b)B=(a,A)(c)C=(A,B)图广义表用树或图来表示第44页,共52页,2023年,2月20日,星期六一个广义表的深度是指该广义表展开后所含括号的层数。例如,A=(b,c)的深度为1,B=(A,d)的深度为2,C=(f,B,h)的深度为34.广义表的深度

第45页,共52页,2023年,2月20日,星期六GetHead(A)=bGetTail(A)=(c)GetHead(B)=AGetTail(B)=(d)GetHead(C)=fGetTail(C)=(B,h)5.广义表的操作取表头GetHead()和取表尾GetTail()如:对A=(b,c)B=(A,d),C=(f,B,h)分别做上述操作6.区分列表()和(())的不同前者为空表,长度n=0;后者长度为n=1,可分解得其表头和表尾均为空表()第46页,共52页,2023年,2月20日,星期六由于广义表的元素类型不一定相同,因此,难以用顺序结构存储表中元素,通常采用链接存储方法来存储广义表中元素,并称之为广义链表。常见的表示方法:5.5

温馨提示

  • 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
  • 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
  • 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
  • 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
  • 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
  • 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
  • 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

评论

0/150

提交评论