数据结构与算法ppt-下载

数据结构与算法2004.2-5数据结构与算法ppt-下载全文共45页，当前为第1页。字符串(String)字符串是n(0)个字符的有限序列，记作S:“c1c2c3…cn”

其中，S是串名字

“c1c2c3…cn”是串值

ci是串中字符

n是串的长度。

数据结构与算法ppt-下载全文共45页，当前为第2页。constintmaxLen=128;

classString{intcurLen;//串的当前长度

char

*ch;//串的存储数组

public:

String(constString&ob);

String(constchar*init);

String(

);~String(){delete[]ch;}

intLength()const{

return

curLen;}字符串抽象数据类型和类定义数据结构与算法ppt-下载全文共45页，当前为第3页。

String

&operator()

(int

pos,

intlen);

intoperator

==(const

String&ob)const{returnstrcmp(ch,ob.ch)==0;}

intoperator!=(const

String&ob)const{returnstrcmp(ch,ob.ch)!=0;}

intoperator!()

const

{returncurLen==0;}

String

&operator=(const

String

&ob);

String&operator+=(const

String&ob);char&operator[](inti);

intFind(Stringpat)const;}数据结构与算法ppt-下载全文共45页，当前为第4页。

String::String(constString&ob){

//复制构造函数：从已有串ob复制

ch=newchar[maxLen+1];

if(!ch){

cout<<“AllocationError\n”;

exit(1);

}

curLen=

ob.curLen;

strcpy(ch,ob.ch);}

字符串部分操作的实现数据结构与算法ppt-下载全文共45页，当前为第5页。String::String(const

char*init){//复制构造函数:从已有字符数组*init复制

ch=newchar[maxLen+1];

if(!ch){cout<<“AllocationError\n”;

exit(1);

}

curLen=

strlen(init);

strcpy(ch,init);

}数据结构与算法ppt-下载全文共45页，当前为第6页。String::String(

){//构造函数：创建一个空串

ch=newchar[maxLen+1];

if(!ch){

cout<<“AllocationError\n”;

exit(1);}

curLen=0;

ch[0]=‘\0’;}数据结构与算法ppt-下载全文共45页，当前为第7页。提取子串的算法示例pos+len-1 pos+len-1

curLen-1

curLen数据结构与算法ppt-下载全文共45页，当前为第8页。String&String::operator()(intpos,

int

len){

//从串中第pos个位置起连续提取len个字符

//形成子串返回

if(pos<0

||pos+len-1>=maxLen

||len<0){

temp.curLen=0;

//返回空串

temp.ch[0]='\0';

}

else{//提取子串

String*temp=newString;//动态分配数据结构与算法ppt-下载全文共45页，当前为第9页。

if(pos+len-1>=curLen)

len=curLen-pos;

temp→curLen=len;//子串长度

for(inti=0,j=pos;i<len;i++,j++)

temp→ch[i]=ch[j];//传送串数组

temp→ch[len]=‘\0’;//子串结束

}

return

temp;}

数据结构与算法ppt-下载全文共45页，当前为第10页。String&String::operator=

(const

String&ob){//串赋值：从已有串ob复制

if(&ob!=this){

delete[]ch;

ch=new

char[maxLen+1];//重新分配

if(!ch){cerr<<“OutOfMemory!\n”;

exit(1);

}

curLen=ob.curLen;//串复制

strcpy(ch,ob.ch);

}数据结构与算法ppt-下载全文共45页，当前为第11页。

elsecout<<“AttemptedassignmentofaStringtoitself!\n”;

return*this;}

char&String::operator[](inti){//按串名提取串中第i个字符

if(i<0&&i>=curLen

){cout<<“OutOfBoundary!\n”;

exit(1);

}returnch[i];}数据结构与算法ppt-下载全文共45页，当前为第12页。String&String:://串连接operator+=

(const

String&ob){

char*temp=ch;//暂存原串数组

curLen+=ob.curLen;//串长度累加

ch=new

char[maxLen+1];

if(!ch)

{cerr<<“OutOfMemory!\n”;

exit(1);

}

strcpy(ch,temp);

//拷贝原串数组

strcat(ch,ob.ch);

//连接ob串数组

delete[]temp;return

*this;

}数据结构与算法ppt-下载全文共45页，当前为第13页。串的模式匹配定义在串中寻找子串（第一个字符）在串中的位置词汇在模式匹配中，子串称为模式，串称为目标。示例

目标T:“Beijing”

模式P:“jin”

匹配结果

=3

数据结构与算法ppt-下载全文共45页，当前为第14页。第1趟

T abbaba穷举的模式

P aba

匹配过程

第2趟

T abbaba P aba

第3趟

T abbaba P aba

第4趟

T abbaba Paba

数据结构与算法ppt-下载全文共45页，当前为第15页。intString::Find(String&pat)const{

//穷举的模式匹配

char*p=pat.ch,*s=ch;

inti=0;

if(*p&&*s) //当两串未检测完

while(i<=curLen

-pat.curLen)

if(*p++==*s++)//比较串字符

if(!*p)

return

i;//相等

else{

i++;s=ch+i;p=pat.ch;}

//对应字符不相等，对齐目标的 //下一位置，继续比较

return

-1;

}数据结构与算法ppt-下载全文共45页，当前为第16页。

目标

T

t0

t1

t2……tm-1…tn-1

模式

pat

p0

p1

p2……pm-1

目标

T

t0

t1

t2……tm-1

tm…tn-1

模式

pat

p0

p1……pm-2pm-1

目标

T

t0

t1……ti

ti+1……ti+m-2

ti+m-1…tn-1 ‖‖‖‖

模式

pat

p0

p1……pm-2pm-1改进的模式匹配数据结构与算法ppt-下载全文共45页，当前为第17页。

穷举的模式匹配算法时间代价：最坏情况比较n-m+1趟，每趟比较m次，

总比较次数达(n-m+1)*m

原因在于每趟重新比较时，目标串的检测指针要回退。改进的模式匹配算法可使目标串的检测指针每趟不回退。

改进的模式匹配(KMP)算法的时间代价：若每趟第一个不匹配，比较n-m+1趟，总比较次数最坏达(n-m)+m=n

若每趟第m个不匹配，总比较次数最坏亦达到n数据结构与算法ppt-下载全文共45页，当前为第18页。Tt0

t1…ts-1

ts

ts+1

ts+2…ts+j-1

ts+j

ts+j+1…tn-1

‖‖‖‖‖P

p0

p1

p2…pj-1

pjpj+1

则有

tsts+1

ts+2…ts+j

=p0

p1

p2…pj(1)

为使模式P与目标T匹配，必须满足

p0

p1

p2…pj-1…pm-1=ts+1

ts+2

ts+3…ts+j…ts+m

如果

p0

p1…pj-1

p1

p2…pj (2)

则立刻可以断定

p0

p1…pj-1

ts+1

ts+2…ts+j

下一趟必不匹配数据结构与算法ppt-下载全文共45页，当前为第19页。同样，若

p0

p1…pj-2

p2

p3…pj则再下一趟也不匹配，因为有

p0

p1…pj-2

ts+2

ts+3…ts+j直到对于某一个“k”值，使得

p0

p1…pk+1

pj-k-1

pj-k

…pj

且

p0

p1…pk

=

pj-k

pj-k+1…pj则

p0

p1…pk

=ts+j-k

ts+j-k+1…ts+j

‖‖‖

pj-k

pj-k+1…pj数据结构与算法ppt-下载全文共45页，当前为第20页。k的确定方法

当比较到模式第j个字符失配时，k的值与模式的前j个字符有关，与目标无关。利用失效函数

f(j)可描述。利用失效函数f(j)的匹配处理如果j

=0，则目标指针加1，模式指针回到p0。如果j

>0，则目标指针不变，模式指针回到

pf(j-1)+1。数据结构与算法ppt-下载全文共45页，当前为第21页。若设

模式

P=p0p1…pm-2pm-1示例：确定失效函数

f(j)数据结构与算法ppt-下载全文共45页，当前为第22页。朴素匹配算法(Naive)intindex_naive(charS[],charT[]){i=j=0;while(i<S_len&&j<T_len){if(S[i]==T[j]){i++;j++;}else{i=i-(j-1);j=0;}}if(j==T_len)return(i-T_len);elsereturn-1;}数据结构与算法ppt-下载全文共45页，当前为第23页。朴素匹配算法效率较低abbacabcacbababcacabcacabcacabcacabcacabcacabcacTS总共进行了六趟匹配:-<数据结构与算法ppt-下载全文共45页，当前为第24页。模式匹配的改进abbacabcacbababcacTSabcacabcacabcac只需进行三趟匹配:-）数据结构与算法ppt-下载全文共45页，当前为第25页。Knuth-Morris-Pratt算法Demo

当主串S[i]与子串T[j]失配时，i不回溯，仅j回溯到一个尽量“偏右”的位置k。因此KPM算法的核心问题是寻找确定k=next[j]的方法。abcaaabaabcacabaabci=7j=5k=2=next[5]数据结构与算法ppt-下载全文共45页，当前为第26页。KMP算法分析(I)S[i-k...i-1]=T[0...k-1]abcaaabaabcacabaabcijkST数据结构与算法ppt-下载全文共45页，当前为第27页。KMP算法分析(II)abcaaabaabcacabaabcijkSTS[i-k...i-1]

=

T[

j-k...

j-1]

数据结构与算法ppt-下载全文共45页，当前为第28页。KMP算法分析(III)S[i-k...i-1]

=

T[0...next[j]-1]

abcaaabaabcacabaabcinext[j]kST数据结构与算法ppt-下载全文共45页，当前为第29页。KMP算法分析(IV)T[0...k-1]

=

T[j-k...j-1]＝T[0...next[j]-1]

因此得到k=next[j]的定义(注意下标范围)：由(I)，(II)，和(III)我们得到：以上定义也说明next[j]与主串S无关。数据结构与算法ppt-下载全文共45页，当前为第30页。abcaaabaabcacnext[j]函数举例abaabcT:ac-1001120101234567j:next[j]:使主串指针i前行abcaaabaabcacabcaaabaabcacabbaaabaabcacaabaaabaabcacaabababaabcacaababcbaabcacaababcaaabcac数据结构与算法ppt-下载全文共45页，当前为第31页。KMP算法intindex_kmp(charS[],charT[]){i=j=0;while(i<S_len&&j<T_len){if(j==-1||S[i]==T[j]){i++;j++;}else{j=next[j];}}if(j==T_len)return(i-T_len);elsereturn-1;}Naive数据结构与算法ppt-下载全文共45页，当前为第32页。next[j]函数的求法根据定义next[0]=-1;设next[j]=k，求next[j+1]若T[j]=T[k]，则next[j+1]=k+1=next[j]+1;否则(T[j]T[k])，若T[[j]=T[next[k]],则next[j+1]=next[k]+1;否则......abaabcT:ac-1001120101234567j:next[j]:j=5next[6]=next[5+1]=next[next[next[5]]]+1=next[next[2]]+1=next[0]+1=-1+1=0数据结构与算法ppt-下载全文共45页，当前为第33页。next[j]函数voidget_next(charT[],intnext[]){i=0;j=-1;next[0]=-1;while(i<T_len){if(j==-1||T[i]==T[j]){i++;j++;next[i]=j;elsej=next[i];}}数据结构与算法ppt-下载全文共45页，当前为第34页。

运用KMP算法的匹配过程第1趟目标

acabaabaabcacaabc

模式

abaabcac

j=1

j=f(j-1)+1=0第2趟目标acabaabaabcacaabc

模式

abaabcac

j=5

j=f(j-1)+1=2第3趟目标acabaabaabcacaabc

模式

(ab)aabcac

数据结构与算法ppt-下载全文共45页，当前为第35页。

int

String::fastFind(Stringpat)const{

//带失效函数的KMP匹配算法

int

posP=0,

posT=0;

int

lengthP=pat.curLen,lengthT=curLen;

while(posP<lengthP&&posT<lengthT)

if(pat.ch[posP]==ch[posT]){

posP++;posT++;//相等继续比较

}elseif(posP==0)posT++;//不相等

elseposP=pat.f[posP-1]+1;

if(posP<lengthP)return

-1;

else

return

posT-lengthP; }数据结构与算法ppt-下载全文共45页，当前为第36页。计算失效函数f[j]

的方法首先确定f[0]=-1，再利用f[j]求f[j+1]。其中,f(1)[j]=f[j],

f

(m)[j]=f[f

(m-1)[j]]

数据结构与算法ppt-下载全文共45页，当前为第37页。f[0]=

-1;j=1时,f[0]+1=0,p0

p1,f[1]=-1;j=2时,f[1]+1=0,p0

=p2,f[2]=f[1]+1=0;j=3时,f[2]+1=1,p1

p3,

f[1]+1=0,p0

=p3,f[3]=f[1]+1=0;j=4时,f[3]+1=1,p1

=p4,f[4]=f[3]+1=1;数据结构与算法ppt-下载全文共45页，当前为第38页。void

String::fail(){//计算失效函数

int

lengthP=curLen;

f[0]=

-1;//直接赋值

for(intj=1;j<lengthP;j++){//依次求f

[j]

inti=f[j-1];

while(*(ch+j)

!=*(ch+i+1)

&&i>=0)

i=f[i]; //递推

if(*(ch+j)==*(ch+i+1))f[j]=i+1;

else

f[j]=

-1;

}}数据结构与算法ppt-下载全文共45