数据结构与算法ppt课件

.,1,数据结构与算法,2004.2-5,.,2,字符串(String),字符串是n(0)个字符的有限序列，记作S:“c1c2c3cn”其中，S是串名字“c1c2c3cn”是串值ci是串中字符n是串的长度。,.,3,constintmaxLen=128;classStringintcurLen;/串的当前长度char*ch;/串的存储数组public:String(constString,字符串抽象数据类型和类定义,.,4,String,.,5,String:String(constString,字符串部分操作的实现,.,6,String:String(constchar*init)/复制构造函数:从已有字符数组*init复制ch=newcharmaxLen+1;if(!ch)cout“AllocationErrorn”;exit(1);curLen=strlen(init);strcpy(ch,init);,.,7,String:String()/构造函数：创建一个空串ch=newcharmaxLen+1;if(!ch)cout=curLen)len=curLen-pos;tempcurLen=len;/子串长度for(inti=0,j=pos;ilen;i+,j+)tempchi=chj;/传送串数组tempchlen=0;/子串结束returntemp;,.,11,String,.,12,elsecout=curLen)cout0，则目标指针不变，模式指针回到pf(j-1)+1。,.,22,若设模式P=p0p1pm-2pm-1,示例：确定失效函数f(j),.,23,朴素匹配算法(Naive),intindex_naive(charS,charT)i=j=0;while(iS_len,.,24,朴素匹配算法效率较低,T,S,总共进行了六趟匹配:-,.,25,模式匹配的改进,T,S,只需进行三趟匹配:-）,.,26,Knuth-Morris-Pratt算法,Demo,当主串Si与子串Tj失配时，i不回溯，仅j回溯到一个尽量“偏右”的位置k。因此KPM算法的核心问题是寻找确定k=nextj的方法。,a,b,c,a,a,a,b,a,a,b,c,a,c,a,b,a,a,b,c,i=7,j=5,k=2=next5,.,27,KMP算法分析(I),Si-k.i-1=T0.k-1,a,b,c,a,a,a,b,a,a,b,c,a,c,a,b,a,a,b,c,i,j,k,S,T,.,28,KMP算法分析(II),a,b,c,a,a,a,b,a,a,b,c,a,c,a,b,a,a,b,c,i,j,k,S,T,Si-k.i-1=Tj-k.j-1,.,29,KMP算法分析(III),Si-k.i-1=T0.nextj-1,a,b,c,a,a,a,b,a,a,b,c,a,c,a,b,a,a,b,c,i,nextj,k,S,T,.,30,KMP算法分析(IV),T0.k-1=Tj-k.j-1T0.nextj-1,因此得到k=nextj的定义(注意下标范围)：,由(I)，(II)，和(III)我们得到：,以上定义也说明nextj与主串S无关。,.,31,nextj函数举例,使主串指针i前行,.,32,KMP算法,intindex_kmp(charS,charT)i=j=0;while(iS_len,Naive,.,33,nextj函数的求法,根据定义next0=-1;设nextj=k，求nextj+1若Tj=Tk，则nextj+1=k+1=nextj+1;否则(TjTk)，若Tj=Tnextk,则nextj+1=nextk+1;否则.,a,b,a,a,b,c,T:,a,c,-1,0,0,1,1,2,0,1,0,1,2,3,4,5,6,7,j:,nextj:,j=5,next6=next5+1=nextnextnext5+1=nextnext2+1=next0+1=-1+1=0,.,34,nextj函数,voidget_next(charT,intnext)i=0;j=-1;next0=-1;while(iT_len)if(j=-1|Ti=Tj)i+;j+;nexti=j;elsej=nexti;,.,35,运用KMP算法的匹配过程第1趟目标acabaabaabcacaabc模式abaabcacj=1j=f(j-1)+1=0第2趟目标acabaabaabcacaabc模式abaabcacj=5j=f(j-1)+1=2第3趟目标acabaabaabcacaabc模式(ab)aabcac,.,36,intString:fastFind(Stringpat)const/带失效函数的KMP匹配算法intposP=0,posT=0;intlengthP=pat.curLen,lengthT=curLen;while(posPlengthP,.,37,计算失效函数fj的方法首先确定f0=-1，再利用fj求fj+1。其中,f(1)j=fj,f(m)j=ff(m-1)j,.,38,f0=-1;j=1时,f0+1=0,p0p1,f1=-1;j=2时,f1+1=0,p0=p2,f2=f1+1=0;j=3时,f2+1=1,p1p3,f1+1=0,p0=p3,f3=f1+1=0;j=4时,f3+1=1,p1=p4,f4=f3+1=1;,.,39,voidString:fail()/计算失效函数intlengthP=curLen;f0=-1;/直接赋值for(intj=1;j=0)i=fi;/递推if(*(ch+j)=*(ch+i+1)fj=i+1;elsefj=-1;,.,40,字符串操作应用举例,文本编辑建立词索引表,.,41,文本编辑,MicrosoftNotePadMicrosoftWord(WYSIWYG)UnixsVIEmacsandEmacsenwhouseGNUEmacsXEmacs,.,42,文本编辑的基本数据结构“行”,#defineMAXLINE65535typedefstructchar*line;intlength;Line;LinetextMAXLINE;,100,104,101,102,103,105,i,texti,.,43,建立词索引表,建立词索引表可以加速信息检索,数据库,建立索引程序,索引表,用户接口,用户请求,检索结果,检索程序,.,44,书目检索举例(建立书目关键词索引表),关键词索引表,书目文件,.,45,关键词