第四、五章-串-数组和广义表PPT课件VIP

.,1,第四章串,4.1串类型的定义4.2串的表示和实现4.3串的模式匹配,.,2,4.1串类型的定义,串（也称字符串）：是由0个或多个字符组成的有限序列。通常记为：s=“a1a2a3aian”(n0)。,字母、数字或其他字符,必须有！,不属于串！,作用：避免与变量名或数的常量混淆。,例：x=“123”x=123,test=“test”,基本概念,.,3,空串：不含任何字符的串，串长度=0，用符号表示。,空格串：仅由一个或多个空格组成的串。,子串：由串中任意个连续的字符组成的子序列。,例：S=“JINAN”S1=“”、S2=“NA”、S=“JINAN”,主串：包含子串的串。,位置：字符在序列中的序号。子串在主串中的位置是子串的首字符在主串中的位置。,子串。,S4=“JAN”,非子串（非串S中的连续字符所组成）。,在S中的位置：3,在S中的位置：1,串相等的条件：当两个串的长度相等且各个对应位置的字符都相等时才相等。,例：S=“JINAN”S1=“JINAN”SS1,空串是任意串的子串，任意串是其自身的子串。,.,4,串的逻辑结构：和线性表极为相似。,串的基本操作：和线性表有很大差别。,区别：串的数据对象约定是字符集。,在线性表的基本操作中，大多以“单个元素”作为操作对象；,在串的基本操作中，通常以“串的整体”作为操作对象。例如：在串中查找某个子串、求取一个子串、在串的某个位置上插入一个子串以及删除一个子串等。,.,5,串的抽象数据类型的定义,ADTString数据对象：Dai|aiCharacterSet,i=1,2,.,n,n0数据关系：R1|ai-1,aiD,i=2,.,n基本操作：StrAssign(m=StrLength(T);/求串长i=pos;while(i=pos-1;-i)/为插入T而腾出pos之后的位置，即从S的pos位置起全部字符均后移S.chi+T.length=S.chi;,S.chpos-1.pos+T.length-2=T.ch0.T.length-1;/插入TS.length+=T.length;/刷新S串长度,4.2串的表示和实现,.,24,4.2.3串的块链存储表示,例：S=ABCDEFGHI,链表结点大小为1,链表结点大小为4,法1存储密度为1/2；法2存储密度为9/15=3/5,4.2串的表示和实现,.,25,4.3串的模式匹配算法,模式匹配：子串定位运算。(串匹配)就是在主串中找出子串出现的位置。,用函数Index(S,T,pos)实现。,在串匹配中，将主串S称为目标(串)，子串T称为模式(串)。,如果在主串S中能够找到子串T，则称匹配成功，返回第一个和子串T中第一个字符相等的字符在主串S中的序号；否则，称匹配失败，返回0。,.,26,当用模式依次从目标的头部往后移，移到的位置就叫位移，每次移动后要看模式里的字符和目标中相应的字符是否相等，若都相等，这次位移就叫有效位移（其实就是从这个位置开始的匹配成功），否则叫无效位移。,模式匹配是各种处理系统中最重要的操作之一，也是一个比较复杂的串操作。模式匹配的算法不同，效率将有很大差别。同一算法应用不同，效率亦有很大差别。,.,27,朴素的模式匹配算法,算法思想：从主串S的第pos个字符起和模式T的第一个字符比较之，若相同，则继续比较后续字符；否则从主串S的下一个字符起再重新和模式T的字符比较之。,例：S=JINANSHI，T=NAN。,匹配,匹配,3,.,28,第一趟匹配,第二趟匹配,第三趟匹配,第四趟匹配,第五趟匹配,第六趟匹配,ababcabcacbab,ababcabcacbab,ababcabcacbab,ababcabcacbab,ababcabcacbab,ababcabcacbab,abcac,abcac,abcac,abcac,abcac,abcac,4.3.1（BF）匹配算法,算法思想：用子串T中的字符依次与主串S中的字符比较：若不匹配，将T右移一个字符，从头开始与S中字符依次比较；如此反复执行，直到匹配成功或者一直将T移到无法与S继续比较为止，则匹配失败。,子串T,主串S,.,29,当采用定长顺序存储结构时，实现此操作的算法如下：intIndex(SStringS,SStringT,intpos)/返回子串T在主串S中第pos个字符之后的位置。/若不存在，则函数值为0。/其中，T非空，1posStrLength(S)。i=pos;j=1;while(iT0)returni-T0;elsereturn0;/Index,.,30,KMP算法的时间复杂度可以达到O(m+n),二、KMP算法,模式匹配：子串T(模式p）在主串S中的定位操作(mn)。S=s1s2sn主串P=p1p2pm模式(同子串T)从主串S中查找与模式P完全相同子串的过程。,.,31,第一趟匹配,第二趟匹配,第三趟匹配,ababcabcacbab,ababcabcacbab,ababcabcacbab,abcac,abcac,(a)bcac,KMP算法匹配情况：,pjsi下一步p中哪个字符和si比较？(i不回溯）Pk1kj,设主串S=“ababcabcacbab”,模式串P=“abcac”。,k值仅依赖于P本身的前个j-1字符，于目标S无关；,当sipj时，已经得到的结果：si-j+1.si-1=p1.pj-1若已知p1.pk-1=pj-k+1.pj-1则有si-k+1.si-1=p1.pk-1,.,32,定义：模式串的next函数,.,33,intIndex_KMP(SStringS,SStringT,intpos)/1posStrLength(S)i=pos;j=1;while(iT0)returni-T0;/匹配成功elsereturn0;/Index_KMP,.,34,这实际上也是一个匹配的过程，不同在于：主串和模式串是同一个串,求next函数值的过程是一个递推过程，分析如下:,已知：next1=0；,假设：nextj=k；又Tj=Tk,则：nextj+1=k+1,若：TjTk则需往前回朔，检查Tj=T？,.,35,voidget_next(SStringT,intnext)/求模式串T的next函数值并存入数组next。算法4.7inti=1,j=0;next1=0;/T的第1个字符与主串“失配”时，主串的下一字符与T的第1个字符比较while(i1时，next2=1if(j=0|Ti=Tj)/初态或两字符相等+i;/各+1继续向后比较+j;nexti=j;/主串和T在第i个字符不匹配时，前j-1个字符是匹配的，只须与第j个字符比较else/两字符不等j=nextj;/j减小到前面字符相等之处,.,36,还有一种特殊情况需要考虑：例如：S=aaabaaabaaabaaabaaabT=aaaab,nextvalj=00004,nextj=01234,.,37,voidget_nextval(SString/get_nextval,.,38,1.熟悉串的七种基本操作的定义，并能利用这些基本操作来实现串的其它各种操作的方法。,2.熟练掌握串的定长顺序存储结构及其实现串的各种操作的基本方法。,3.了解串的堆存储结构及其实现串的各种操作的基本方法。,教学要求,4.掌握朴素的模式匹配算法。,.,39,1、试问执行以下函数会产生怎样的输出结果？voiddemonstrate()StrAssign(s,THISISABOOK);Replace(s,SubString(s,3,7),ESEARE);StrAssign(t,Concat(s,S);StrAssign(u,XYXYXYXYXYXY);StrAssign(v,SubString(u,6,3);StrAssign(w,W);Printf(“t=%s,v=%s,u=%s”,t,v,Replace(u,v,w);,练习,.,40,5.1数组的定义5.2数组的顺序表示和实现5.3矩阵的压缩存储5.4广义表的定义5.5广义表的存储结构,元素的值并非原子类型，可以再分解，表中元素也是一个线性表所有数据元素仍属于同一数据类型。,数组和广义表是线性表的扩充：,第5章数组和广义表,.,41,注：,数组中的元素都具有统一的类型;数组元素的下标一般都具有固定的上界和下界，即数组一旦被定义，它的维数和维界就不再发生改变；数组的基本操作简单：初始化、销毁、存取元素和修改元素值,一维数组的特点：1个下标，ai是ai+1的直接前驱二维数组的特点：2个下标，每个元素aij受两个关系（行关系和列关系）的约束；,数组：由一组名字相同、下标不同的变量构成,一个mn的二维数组可以看成是m行的一维数组，或者n列的一维数组。,5.1数组的定义,.,42,.,43,存储单元是一维结构，而数组是个多维结构,则用一组连续存储单元存放数组的数据元素就有个次序约定问题。,二维数组可有两种存储方式：1）以行序为主序；2）以列序为主序。,a00a01a0,n-1a10a11a1,n-1am-1,0am-1,1am-1,n-1,5.2数组的顺序表示和实现,.,44,（以行序为主序为例）假设每个数据元素占L个存储单元，则二维数组Ab1b2中任一元素aij的存储位置可由下式确定：,LOC（i，j）=LOC（0，0）+（b2*i+j）*L,对于数组，一旦规定了它的维数和各维的长度，便可为它分配存储空间。反之，只要给出一组下标便可求得相应数组元素的存储位置。,数组基址,总列数，即第2维长度,aij本行前面的元素个数,每个元素所占的存储单元,若是N维数组Ab1b2bn，其中任一元素的地址:,LOC(j1,j2,jn)=LOC(0,0,0)+(j1b2bn+j2b3bn+jn-1bn+jn)L,5.2数组的顺序表示和实现,.,45,注意：,2.以“列优先顺序”存储二维数组中任一元素aij的(首)地址是：LOCaij=LOCa11+(i-1)m+(j-1)l(5-1)i=1,2,nj=1,2,m,1.以“行优先顺序”存储：由此可知，二维数组中任一元素aij的(首)地址是：LOCaij=LOCa11+(i-1)n+(j-1)l(5-1)i=1,2,mj=1,2,n,.,46,例1：一个二维数组A，行下标的范围是1到6，列下标的范围是0到7，每个数组元素用相邻的6个字节存储，存储器按字节编址。那么，这个数组的体积是个字节。,例2：设数组a160,170的基地址为2048，每个元素2个存储单元，若以列序为主序顺序存储，则元素a32,58的存储地址为。,288,8950,例3：已知二维数组M的每个元素占4个存储单元，数组行下标i的范围从0到4，列下标j的范围从0到5，数组M按行存储时，元素M35的地址和M按列存储时，元素_的地址相同。A.M24B.M34C.M35D.M44,5.2数组的顺序表示和实现,.,47,压缩存储：为多个值相同的元素分配一个存储空间；对零元素不分配空间。,具备压缩条件的矩阵包括：对称矩阵、三角矩阵、对角矩阵、稀疏矩阵。,稀疏矩阵：矩阵中非零元素的个数较少（一般小于5%）。,5.3矩阵的压缩存储,.,48,矩阵下三角部分元素是随机的，而上三角部分元素全部相同（为某常数C）或全为0。,一、三角矩阵,（1）上三角矩阵,矩阵上三角部分元素是随机的，而下三角部分元素全部相同（为某常数C）或全为0。,（2）下三角矩阵,5.3.1特殊矩阵,.,49,（3）下三角矩阵的压缩存储,矩阵中共有n(n+1)/2个非零元素，共需要n(n+1)/2+1个存储空间。若将其存放到一维向量空间S0.Sn(n+1)/2中，则SK与aij的对应关系为：,当ij时，aij是非零元素，aij前面有i行，共有1+2+3+i=i(i+1)/2个非零元素，aij前面有j列，共j个非零元素，即k=i(i+1)/2+j；当ij时，aij是零元素，存放在最后一个存储单元Sn(n+1)/2中。,5.3.1特殊矩阵,.,51,二、对称矩阵,在一个n阶方阵A中，若元素满足下述性质：aij=aji（0i，jn-1）则称A为对称矩阵。,1、对称矩阵的定义,5.3.1特殊矩阵,.,52,2、对称矩阵的压缩存储,对称矩阵中的元素关于主对角线对称，故只要存储矩阵中上三角或下三角中的元素，让每两个对称的元素共享一个存储空间。这样，能节约近一半的存储空间。在下三角矩阵中，元素的总个数为1+2+n=n(n+1)/2。按行优先顺序存储主对角线(包括对角线)以下的元素,5.3.1特殊矩阵,.,53,2、对称矩阵的压缩存储,元素aij的存放位置aij元素前有i-1行(从第1行到第i-1行)，一共有：1+2+(i-1)=(i-1)(1+(i-1)2=i(i-1)/2个元素;在第i行上，aij之前恰有j-1个元素(即ai1，ai2，ai,j-1)，因此有：aij之前共有i(i-1)2+(j-1)个元素aij和sk之间的对应关系：,5.3.1特殊矩阵,.,54,三、对角矩阵若矩阵中所有非零元素都集中在以主对角线为中心的带状区域中，区域外的值全为0，则称为对角矩阵。常见的有三对角矩阵、五对角矩阵、七对角矩阵等。,一个77的三对角矩阵,5.3.1特殊矩阵,.,55,对角矩阵的压缩存储我们仅讨论三对角矩阵的压缩存储。在一个nn的三对角矩阵中，只有n+n-1+n-1个非零元素，故只需3n-2个存储单元即可，零元已不占用存储单元。故可将nn三对角矩阵A压缩存放到只有3n-2个存储单元的s向量中，假设仍按行优先顺序存放，,sk与aij的对应关系为：,5.3.1特殊矩阵,.,56,以常规方法，即以二维数组表示高阶的稀疏矩阵时产生的问题:,1)零值元素占了很大空间;,2)计算中进行了很多和零值的运算，遇除法，还需判别除数是否为零。,解决的办法：只存储非零元素。在存储非零元素的同时，还必须同时记下它所在的行和列的位置（i,j)。因此，稀疏矩阵可由表示非零元的三元组及其行列数唯一确定。,M由(1,2,12),(1,3,9),(3,1,-3),(3,6,14),(4,3,24),(5,2,18),(6,1,15),(6,4,-7)和矩阵维数（6,7）唯一确定,.,57,稀疏矩阵的存储：,如何表示非零元素的位置信息,每个元素用一个三元组（i，j，v）来表示。,1.三元组表：,1212,139,31-3,3514,4324,5218,6115,64-7,注意：为更可靠描述，通常再加一个“总体”信息：即总行数、总列数、非零元素总个数。,5.3.2稀疏矩阵,.,58,例：试还原出下列三元组所表示的稀疏矩阵。,64,0200,12000,3000,0004,0060,16000,5.3.2稀疏矩阵,.,59,1、顺序存储结构（1）三元组表对矩阵中的每个非零元素用三个域分别表示其所在的行号、列号和元素值。#defineMAXSIZE12500typedefstructinti,j;/该非零元的行下标和列下标ElemTypee;/非零元素的值Triple;/三元组类型typedefstructTripledataMAXSIZE+1;/非零元三元组表，data0未用intmu,nu,tu;/矩阵的行数、列数和非零元个数TSMatrix;/稀疏矩阵类型,稀疏矩阵的压缩存储方法,.,60,2.十字链表：,ijv,downright,指向同一列中下一非零元素,指向同一行中下一非零元素,00501002000,5.3.2稀疏矩阵,.,61,typedefstructOLNode/结点结构定义inti,j;/该非零元的行和列下标ElemTypee;structOLNode*right,*down;/该非零元所在行表和列表的后继链域QNode,*OLink;typedefstruct/链表结构定义OLink*rhead,*chead;/行和列链表头指针向量基址由CreateSMatrix分配intmu,nu,tu;/稀疏矩阵的行数、列数和非零元个数CrossList;,十字链表,.,62,.,63,1、定义,广义表是线性表的推广，也称为列表（lists）。记为：LS=（a1，a2，an）,广义表名,n是表长,在广义表中约定：,ai可以是单个元素，也可以是广义表，分别称为原子和子表;用小写字母表示元素，用大写字母表示列表名称；当LS非空时，称第一个元素为表头(Head)，其余元素组成的表(a2，an)为表尾(Tail)。任何一个非空表，表头可能是原子，也可能是列表，但表尾一定是列表。,5.4广义表的定义,.,64,例如:A=()F=(d,(e)D=(a,(b,c),F)C=(A,D,F)B=(a,B)=(a,(a,(a,),5.4广义表的定义,.,65,广义表是一个多层次的线性结构,例如：,D=(E,F),其中:E=(a,(b,c)F=(d,(e),D,E,F,a,(),d,(),b,c,e,5.4广义表的定义,.,66,广义表LS=(1,2,n)的结构特点:,1)广义表中的数据元素有相对次序；,2)广义表的长度定义为最外层包含元素个数；,3)广义表的深度定义为所含括弧的重数；例如，A=(b,c)的深度为1，B=(A,d)的深度为2，C=(f,B,h)的深度为3。注意：“原子”的深度为0“空表”的深度为1,4)广义表可以是一个递归的表。递归表的深度是无穷值，长度是有限值。,如：E=(a,E),5.4广义表的定义,.,67,例：求下列广义表的长度。,(1)A=()(2)B=(e)(3)C=(a，(b，c，d)(4)D=（A，B，C）(5)E=(a，E),n=0，因为A是空表n=1，表中元素e是原子n=2，a为原子，(b,c,d)为子表,D=(A,B,C)=(),(e),(a,(b,c,d)，共享表,E=(a,E)=(a,(a,E)=(a,(a,(a,.)，E为递归表,n=3，3个元素都是子表,n=2，a为原子，E为子表,表中元素个数,5.4广义表的定义,.,68,例如:D=(E,F)=(a,(b,c)，F),Head(D)=ETail(D)=(F),Head(E)=aTail(E)=(b,c),Head(b,c)=(b,c)Tail(b,c)=(),Head(b,c)=bTail(b,c)=(c),Head(c)=cTail(c)=(),5.4广义表的定义,5)任何一个非空广义表LS=(1,2,n)均可分解为表头GetHead(LS)=1和表尾GetTail(LS)=(2,n)两部分。,.,69,广义表两种特殊的基本操作：,GetHead【L】取表头（可能是原子或列表）GetTail【L】取表尾（一定是列表）,（1）GetTail【(b，k，p，h)】=（2）GetHead【(a,b)，(c,d)】=（3）GetTail【(a,b)，(c,d)】=（4）GetTail【GetHead【(a,b)，(c,d)】=（5）GetTail【(e)】=（6）GetHead【()】=（7）GetTail【()】=,(k,p,h),(a,b),(c,d),(b),(),(),(),5.4广义表的定义,.,70,利用GetHead和GetTail操作，把原子banana分别从下列广义表中分离出来。(1)L1=(apple,pear,banana,orange)(2)L2=(apple,pear),(banana,orange)(3)L3=(apple),(pear),(banana),(orange),GetHead【GetTail【GetTail【L1】,GetHead【GetHead【GetTail【L2】,GetHead【GetHead【GetTail【GetTail【GetHead【L3】,练习,.,71,由于广义表的元素可以是不同结构（原子或列表），难以用顺序存储结构，通常用链式结构，每个元素用一个结点表示。,注意：列表的元素可以是原子或列表，所以结点可能有两种形式,1.原子结点：表示原子，设2个域,标志域,数值域,0,2.列表结点：表示列表，设3个域,标志域,表头指针,表尾指针,1,5.5广义表的存储结构,.,72,A=(),C=(a,(b,c,d),例：,B=(e),A=NULL,E=(a,E),(b,c,d),5.5广义表的存储结构,.,73,数组可视为一种广义线性表；数组的存储有行优先和列优先两种不同的顺序；对于稀疏矩阵，有较好