《数组和广义表》PPT课件

1,第五章数组和广义表,2,作为抽象数据类型的数组,一维数组一维数组的示例,5.1数组的定义,3,一维数组的特点,连续存储的线性聚集（别名向量）除第一个元素外，其他每一个元素有一个且仅有一个直接前驱。除最后一个元素外，其他每一个元素有一个且仅有一个直接后继。,4,数组的定义和初始化,#includeclassszclinte;public:szcl()e=0;szcl(intvalue)e=value;intget_value()returne;,5,main()szcla13=3,5,7,*elem;for(inti=0,i3,i+)couta1i.get_value()“n”;/打印静态数组elem=,6,一维数组(Array)类的定义,#include#includetemplateclassArrayType*elements;/数组存放空间intArraySize;/当前长度voidgetArray();/建立数组空间public:Array(intSize=DefaultSize);Array(constArray,7,Array()deleteelements;Array,8,templatevoidArray:getArray()/私有函数：创建数组存储空间elements=newTypeArraySize;if(elements=0)cerrMemoryAllocationErrorendl;,一维数组公共操作的实现,9,templatevoidArray:Array(intsz)/构造函数if(sz=0)cerrInvalidArraySize=0,13,行向量下标i页向量下标i列向量下标j行向量下标j列向量下标k,二维数组三维数组,14,数组的ADT定义,ADTArray数据对象：ji=0,bi-1,i=1,2,nD=aj1j2jn|n称为数组的维数,bi是数组第i维的长度,ji是数组元素的第i维下标，aj1j2jnElemSetR=R1,R2,Rn/每个元素受到n个关系的约束Ri=|0jkbk-1,1kn且ki0jibi-2,aj1jijn,aj1,ji+1jnD,i=2,nP:InitArray(/转置三元组表存放指针,37,for(intk=0;kCols;k+)for(inti=0;iTerms;i+)if(smArrayi.col=k)b.smArrayCurrentB.row=k;b.smArrayCurrentB.col=smArrayi.row;b.smArrayCurrentB.value=smArrayi.value;CurrentB+;returnb;,38,快速转置算法5.2p100,建立辅助数组rowSize和rowStart，记录矩阵转置后各行非零元素个数和各行元素在转置三元组表中开始存放位置。（转置前为列）扫描矩阵三元组表，根据某项的列号，确定它转置后的行号，查rowStart表，按查到的位置直接将该项存入转置三元组表中。转置时间代价为O(max(Terms,Cols)。若矩阵有200列，10000个非零元素，总共需10000次处理。,39,快速转置算法例,40,for(inti=0;iCols;i+)rowSizei=0;for(i=0;iTerms;i+)rowSizesmArrayi.col+;/rowStart0=0;for(i=1;iCols;i+)rowStarti=rowStarti-1+rowSizei-1;/A的第i列开始存放的位置=A的第i-1列开始存放的位置+A的第i-1列非零个数,41,42,2带行指针的链表把具有相同行号的非零元用一个单链表连接起来，稀疏矩阵中的若干行组成若干个单链表，合起来称为带行指针的链表。例如，图1的稀疏矩阵M的带行指针的链表描述形式见图2。,图2带行指针的链表,2带行指针的链表,图1稀疏矩阵M,43,44,在上节提到的特殊矩阵中，元素的分布呈现某种规律，故一定能找到一种合适的方法，将它们进行压缩存放。但是，在实际应用中，我们还经常会遇到一类矩阵：其矩阵阶数很大，非零元个数较少，零元很多，但非零元的排列没有一定规律，我们称这一类矩阵为稀疏矩阵。按照压缩存储的概念，要存放稀疏矩阵的元素，由于没有某种规律，除存放非零元的值外，还必须存储适当的辅助信息，才能迅速确定一个非零元是矩阵中的哪一个位置上的元素。下面将介绍稀疏矩阵的几种存储方法及一些算法的实现。,5.4稀疏矩阵,45,5.4.1稀疏矩阵的存储,1三元组表在压缩存放稀疏矩阵的非零元同时，若还存放此非零元所在的行号和列号，则称为三元组表法，即称稀疏矩阵可用三元组表进行压缩存储，但它是一种顺序存储（按行优先顺序存放）。一个非零元有行号、列号、值，为一个三元组，整个稀疏矩阵中非零元的三元组合起来称为三元组表。此时，数据类型可描述如下：#definemaxsize100/*定义非零元的最大数目*/structnode/*定义一个三元组*/inti,j;/*非零元行、列号*/intv;/*非零元值*/;structsparmatrix/*定义稀疏矩阵*/introws,cols;/*稀疏矩阵行、列数*/intterms;/*稀疏矩阵非零元个数*/nodedatamaxsize;/*三元组表*/;,46,47,2带行指针的链表把具有相同行号的非零元用一个单链表连接起来，稀疏矩阵中的若干行组成若干个单链表，合起来称为带行指针的链表。例如，图5-6的稀疏矩阵M的带行指针的链表描述形式见图5-9。,图5-9带行指针的链表,48,3十字链表当稀疏矩阵中非零元的位置或个数经常变动时，三元组就不适合于作稀疏矩阵的存储结构，此时，采用链表作为存储结构更为恰当。十字链表为稀疏矩阵中的链接存储中的一种较好的存储方法，在该方法中，每一个非零元用一个结点表示，结点中除了表示非零元所在的行、列和值的三元组（i,j,v）外，还需增加两个链域：行指针域（rptr），用来指向本行中下一个非零元素；列指针域（cptr），用来指向本列中下一个非零元素。稀疏矩阵中同一行的非零元通过向右的rptr指针链接成一个带表头结点的循环链表。同一列的非零元也通过cptr指针链接成一个带表头结点的循环链表。因此，每个非零元既是第i行循环链表中的一个结点，又是第j列循环链表中的一个结点，相当于处在一个十字交叉路口，故称链表为十字链表。另外，为了运算方便，我们规定行、列循环链表的表头结点和表示非零元的结点一样，也定为五个域，且规定行、列、域值为0(因此，为了使表头结点和表示非零元的表结点不发生混淆，三元组中，输入行和列的下标不能从0开始!而必须从1开始)，并且将所有的行、列链表和头结点一起链成一个循环链表。在行（列）表头结点中，行、列域的值都为0，故两组表头结点可以共用，即第i行链表和第i列链表共用一个表头结点，这些表头结点本身又可以通过V域（非零元值域，但在表头结点中为next，指向下一个表头结点）相链接。另外，再增加一个附加结点（由指针hm指示，行、列域分别为稀疏矩阵的行、列数目），附加结点指向第一个表头结点，则整个十字链表可由hm指针惟一确定。,49,例如，图5-6的稀疏矩阵M的十字链表描述形式见图5-10。十字链表的数据类型描述如下：structlinknodeinti,j;structlinknode*cptr,*rptr;unionvnext/*定义一个共用体*/intv;/*表结点使用V域,表示非零元值*/structlinknodenext;/*表头结点使用next域*/k;,50,图5-10稀疏矩阵的十字链表,51,5.4.2稀疏矩阵的运算,1稀疏矩阵的转置运算下面将讨论三元组表上如何实现稀疏矩阵的转置运算。转置是矩阵中最简单的一种运算。对于一个mn的矩阵A，它的转置矩阵B是一个nm的，且Bij=Aji，0in,0j0)for(col=0;cola.cols;col+)/*按列号扫描*/for(ano=0;anoa.terms;ano+)/*对三元组扫描*/,53,if(a.dataano.j=col)/*进行转置*/b.databno.j=a.dataano.i;b.databno.i=a.dataano.j;for(i=0;ia.terms;i+)/*输出转置后的三元组结果*/printf(%5d%5d%5dn,b.datai.i,b.datai.j,b.datai.v);voidmain()inti;structsparmatrixa;scanf(%d%d%d,/*调用转置算法*/,54,分析这个算法，主要工作在col和ano二重循环上，故算法的时间复杂度为O(a.cols*a.terms)。而通常的mn阶矩阵转置算法可描述为：for(col=0;coln;col+)for(row=0;rowm;row+)bcolrow=arowcol;它的时间复杂度为O(mn)。而一般的稀疏矩阵中非零元个数a.terms远大于行数m，故压缩存储时，进行转置运算，虽然节省了存储单元，但增大了时间复杂度，故此算法仅适应于a.ternsa.rowsa.cols的情形。,（2）按照A的行序进行转置即按a.data中三元组的次序进行转置，并将转置后的三元组放入b中恰当的位置。若能在转置前求出矩阵A的每一列col（即B中每一行）的第一个非零元转置后在b.data中的正确位置potcol（0cola.cols），那么在对a.data的三元组依次作转置时，只要将三元组按列号col放置到b.datapotcol中，之后将potcol内容加1，以指示第col列的下一个非零元的正确位置。为了求得位置向量pot，只要先求出A的每一列中非零元个数numcol，然后利用下面公式：potcol=potcol-1+numcol-1当1cola.cols,pot0=0,55,为了节省存储单元，记录每一列非零元个数的向量num可直接放入pot中，即上面的式子可以改为：potcol=potcol-1+potcol，其中1col0),57,for(col=0;col=a.cols;col+)potcol=0;for(t=0;ta.terms;t+)/*求出每一列的非零元个数*/col=a.datat.j;potcol+1=potcol+1+1;pot0=0;for(col=1;cola.cols;col+)/*求出每一列的第一个非零元在转置后的位置*/potcol=potcol-1+potcol;for(ano=0;anoj且pa-k.v+pb-k.v0，则只要将aij+bij的值送到pa所指结点的值域中即可，其他所有域的值都不变化。2）pa-j=pb-j且pa-k.v+pb-k.v=0,则需要在A矩阵的链表中删除pa所指的结点。这时，需改变同一行中前一结点的rptr域值，以及同一列中前一结点的cptr域值。3）pa-jj且pa-j0，则只要将pa指针往右推进一步，并重新加以比较即可。4）pa-jpb-j或pa-j=0，则需在A矩阵的链表中插入pb所指结点。,62,下面将对矩阵B加到矩阵A上面的操作过程大致描述如下:设ha和hb分别为表示矩阵A和B的十字链表的总表头；ca和cb分别为指向A和B的行链表的表头结点，其初始状态为：ca=ha-k.next;cb=hb-k.next;pa和pb分别为指向A和B的链表中结点的指针。开始时，pa=ca-rptr;pb=cb-rptr;然后按下列步骤执行：当ca-i=0时，重复执行、步，否则，算法结束；当pb-j0时，重复执行步，否则转第步；比较两个结点的列序号，分三种情形：a若pa-jj且pa-j0，则令pa指向本行下一结点，即qa=pa;pa=pa-rptr;转步;b若pa-jpb-j或pa-j=0，则需在A中插入一个结点。假设新结点的地址为P，则A的行表中指针变化为：qa-rptr=p;p-rptr=pa;同样，A的列表中指针也应作相应改变，用hlj指向本列中上一个结点，则A的列表中指针变化为：p-cptr=hlj-cptr;hlj-cptr=p;转第步；c若pa-j=pb-j，则将B的值加上去，即pa-k.v=pa-k.v+bp-k.v，此时若pa-k.v0，则指针不变，否则，删除A中该结点，于是行表中指针变为：qa-rptr=pa-rptr;同时，为了改变列表中的指针，需要先找同列中上一个结点，用hlj表示，然后令hlj-cptr=pa-cptr，转第步。一行中元素处理完毕后，按着处理下一行，指针变化为：ca=ca-k.next;cb=cb-k.next;转第1)步。,63,64,5.5.1基本概念广义表是第2章提到的线性表的推广。线性表中的元素仅限于原子项，即不可以再分，而广义表中的元素既可以是原子项，也可以是子表（另一个线性表）。,5.5广义表,广义表的概念n(0)个表元素组成的有限序列，记作LS=(a0,a1,a2,an-1)LS是表名，ai是表元素，它可以是表(称为子表)，可以是数据元素(称为原子)。n为表的长度。n=0的广义表为空表。n0时，表的第一个表元素称为广义表的表头(head)，除此之外，其它表元素组成的表(a1,a2,an-1)称为广义表的表尾(tail)。,65,求下列广义表运算的结果：(1)head(p,h,w);(2)tail(b,k,p,h);(3)head(a,b),(c,d);(4)tail(a,b),(c,d);(5)head(tail(a,b),(c,d);(6)tail(head(a,b),(c,d).,head(p,h,w)=ptail(b,k,p,h)=(k,p,h)head(a,b),(c,d)=(a,b)tail(a,b),(c,d)=(c,d)head(tail(a,b),(c,d)=ctail(head(a,b),(c,d)=b,66,广义表的特性,有次序性有长度有深度,可递归可共享,A=()B=(6,2)C=(a,(5,3,x)D=(B,C,A)E=(B,D)F=(4,F),67,广义表的分类,（1）线性表：元素全部是原子的广义表。（2）纯表：与树对应的广义表，（3）再入表：与图对应的广义表(允许结点共享)。（4）递归表：允许有递归关系的广义表，例如E=(a,E)。这四种表的关系满足：递归表再入表纯表线性表,68,各种广义表的示意图,A=(),B=(6,2),C=(a,(5,3,x),D=(B,C,A),E=(B,D),F=(4,F),存储表示,69,广义表的表示方法,（1）用LS=(a1，a2，an)形式，其中每一个ai为原子或广义表例如：A=(b,c)B=(a,A)E=(a,E)都是广义表。（2）将广义表中所有子表写到原子形式，并利用圆括号嵌套例如，上面提到的广义表A、B、C可以描述为：A(b,c)B(a,A(b,c)E(a,E(a,E（）)（3）将广义表用树和图来描述,70,广义表的表示,只包括整数和字符型数据的广义表链表表示,表中套表情形下的广义表链表表示,表头指针p109层次列表长度,71,广义表结点定义,标志域utype,表明结点类型。0为表头结点，1为整型原子结点，2为字符型原子结点，3为子表结点。值域value。当utype=0时为表引用计数，=1时为整数值，=2时为字符值，=3时为指向子表的表头结点的指针。尾指针域tlink。当utype=0时为指向该表表头元素的指针；当utype0时为指向同一层下一个表结点的指针。,utype=0/1/2/3,value=ref/intgrinfo/charinfo/hlink,tlink,72,广义表的带表头结点的存储表示,标志域utype,表明结点类型。0为表头结点，1为整型原子结点，2为字符型原子结点，3为子表结点。,A=()B=(6,2)C=(a,(5,3,x)D=(B,C,A)E=(B,D)F=(4,F)各种广义表的示意图,73,广义表的类定义,#defineHEAD0#defineINTGR1#defineCH2#defineLST3classGenList;classGenListNodefriendclassGenlist;private:intutype;GenListNode*tlink;,74,unionintref;/utype=0,表头结点intintgrinfo;/utype=1,整型charcharinfo;/utype=2,字符型GenListNode*hlink;/utype=3,子表结点value;public:GenListNode*Info(GenListNode*elem);intnodetype(GenListNode*elem)returnelemutype;voidsetInfo(GenListNode*elem,GenListNode*x);,75,classGenListprivate:GenListNode*first;GenListNode*GenList:Copy(GenListNode*ls);intdepth(GenListNode*ls);intequal(GenListNode*s,GenListNode*t);voidGenList:Remove(GenListNode*ls);public:Genlist();GenList();GenListNode*Head();GenListNode*Tail();,76,GenListNode*First();GenListNode*Next(GenListNode*elem);voidPush(GenListNode*x);GenList,77,广义表的访问算法,广义表结点类的存取成员函数GenListNode*GenListNode:Info(GenListNode*elem)/提取广义表中指定表元素elem的值GenListNode*pitem=newGenListNode;pitemutype=elemutype;pitemvalue=elemvalue;returnpitem;,78,voidGenListNode:setInfo(GenListNode*elem,GenListNode*x)/将表元素elem中的值修改为xelemutype=xutype;elemvalue=xvalue;广义表类的构造和访问成员函数Genlist:GenList()GenListNode*first=newGenListNode;firstutype=0;firstref=0;firsttlink=NULL;/仅建立表头结点,79,GenListNode*GenList:Head()/若广义表非空，返回表的表头元素的值if(firsttlink=NULL)/空表cout“无效的head操作.endl;exit(1);elseGenListNode*temp=newGenListNode;temputype=fristtlinkutype;tempvalue=fristtlinkvalue;returntemp;,80,voidGenList:Push(GenListNode*x)/将表结点x加到表的最前端if(firsttlink=NULL)firsttlink=x;elsextlink=firsttlink;firsttlink=x;,81,GenList,82,广义表的递归算法p114,广义表的复制算法voidGenList:Copy(constGenList/复制utype,83,switch(lsutype)caseHEAD:qref=lsref;break;caseINTGR:qintgrinfo=lsintgrinfo;break;caseCH:qcharinfo=lscharinfo;break;caseLST:qhlink=Copy(lshlink);break;qtlink=Copy(lstlink);returnq;,84,广义表的深度,深度为广义表中括号的重数或（）的层数，是广义表的一种量度。,LS=(a0,a1,a2,an-1),85,求广义表的深度,例如，对于广义表E(B(a,b),D(B(a,b),C(u,(x,y,z),A()按递归算法分析：,Depth(E)=1+MaxDepth(B),Depth(D)Depth(B)=1+MaxDepth(a),Depth(b)=1Depth(D)=1+MaxDepth(B),Depth(C),Depth(A),86,E(B(a,b),D(B(a,b),C(u,(x,y,z),A(),Depth(C)=1+MaxDepth(u),Depth(x,y,z)Depth(A)=1Depth(u)=0Depth(x,y,z)=1+MaxDepth(x),Depth(y),Depth(z)=1Depth(C)=1+MaxDepth(u),Depth(x,y,z)=1+Max0,1=2Depth(D)=1+MaxDepth(B),Depth(C),Depth(A)=1+Max1,2,1=3Depth(E)=1+MaxDepth(B),Depth(D)=1+Max1,3=4,87,intGenList:depth(GenListNode*ls)if(lstlink=NULL)return1;/空表GenListNode*temp=lstlink;intm=-1;while(temp!=NULL)/横扫广义表if(temputype=LST)/子表深度intn=depth(temphlink);if(m1的字符串,递归的终结状态,递归调用,Sever：对非空字符串分离第一个元素,设str=(2,(b,7),(),(d),得到的广义表链表结构,96,98,99,多项式(Polynomial),n阶多项式Pn(x)有n+1项。系数a0,a1,a2,an指数0,1,2,n。按升幂排列,100,多项式的存储表示,第一种：private:(静态数intdegree;组表示)floatcoefmaxDegree+1;Pn(x)可以表示为：pl.degree=npl.coefi=ai,0in,101,第二种：private:(动态数intdegree;组表示)float*coef;Polynomial:Polynomial(intsz)degree=sz;coef=newfloatdegree+1;以上两种存储表示适用于指数连续排列的多项式。但对于指数不全的多项式如P101(x)=3+5x50-14x101,不经济。,102,第三种：classPolynomial;classterm/多项式的项定义friendPolynomial;private:floatcoef;/系数intexp;/指数;,103,classPolynomial/多项式定义public:private:statictermtermArrayMaxTerms;/项数组staticintfree;/当前空闲位置指针/termPolynomial:termArrayMaxTerms;/intPolynomial:free=0;intstart,finish;/多项式始末位置,104,A(x)=2.0 x1000+1.8B(x)=1.2+51.3x50+3.7x101,两个多项式存放在termArray中,105,两个多项式的相加,结果多项式另存扫描两个相加多项式，若都未检测完：若当前被检测项指数相等，系数相加。若未变成0，则将结果加到结果多项式。若当前被检测项指数不等，将指数小者加到结果多项式。若有一个多项式已检测完，将另一个多项式剩余部分复制到结果多项式。,106,PolynomialPolynomial:Add(PolynomialB)PolynomialC;inta=start;intb=B.start;C.start=free;floatc;while(a:NewTerm(termArrayb.coef,termArrayb.exp);b+;break;case:NewTerm(termArraya.coef,termArraya.exp);a+;for(;a=finish;a+)/a未检测完时NewTerm(termArraya.coef,t