串的模式匹配(5)

} }

if(j>=T.length) return i+1-T.length;//匹配成功 else return -1;

④int IndexBF(SeqString S,SeqString T,int k)

{//返回子串T在主串S中第pos个字符之后的位置。若不存在，则函数值为0。其中，T非空，1=

int i,j;

i=k-1;//作为扫描S的下标，下标从0开始 j=0;

while(i

if(S.ch[i]==T.ch[j]) {++i;++j;}//继续比较后继字符 else {i=i-j+1;j=0;}//指针后退重新开始匹配 if(j>=T.length) return i+1-T.length; else return -1;

⑤int IndexKMP2(SeqString S,SeqString T,int(&next)[64],int pos)

{//利用GetNextVal函数求next数组值的KMP算法。其中T非空，1=

int i,j; i=pos-1;j=0;

while(i

if(j==-1||S.ch[i]==T.ch[j]) {++i;++j;}//继续比较后继字符 else j=next[j];//模式串向右移动

⑶建立文本文件函数、对文本文件中的单词计数、检索单词出现在文本文件中的行号、位置及在该行中出现的次数函数，此部分的函数实现如下：

19

① void CreateTextFile()//建立文本文件函数

{

SeqString S;

char filename[10],yn; FILE *fp;

printf(\请输入要建立的文件名(如abc.txt)：\ scanf(\

fp=fopen(filename,\以写的方式打开一个新的文件 yn='n';//输入结束的标志 while(yn=='n'||yn=='N'){ printf(\请输入一行文本：\ getchar(); gets(S.ch);

S.length=strlen(S.ch);

fwrite(&S,sizeof(S),1,fp);//写一行文本到文本文件中 printf(\是否结束输入：y/n:\ yn=getchar();

}

fclose(fp);//关闭文件 printf(\文件建立成功！\\n\}

②void Count()//对文本文件中的单词计数

{

FILE *fp,*fp1;long fsizes; SeqString S,T;//定义两个变量

20

char filename[15],filename1[15]; int i=0,j=0,k=0,xz=0; int next[64]={-1};

printf(\您知道吗？串的模式匹配算法有很多种，以下哪种算法是您想要使用的呢？\\t\\n\

printf(\朴素模式匹配算法 2.串的模式匹配KMP算法 3.串的模式匹配KMP改进算法 4.其它 请选择(1/2/3)：\\t\\n\

scanf(\ if(xz==1){

printf(\请输入文本文件名(如abc.txt)：\ scanf(\

if((fp=fopen(filename,\以读的方式打开文件 { printf(\文件打开失败，按请按任意键退出！\\n\ getch(); exit(0); }

printf(\输入要统计计数的单词：\ scanf(\ T.length=strlen(T.ch);

while(!feof(fp)){//循环扫描整个文本

fgets(S.ch,MAXSTRLEN,fp);//读入一行文本，并为S.length赋值 S.length=lenth(S.ch);//求读入的串的长度

if(feof(fp)) break;//不加则会多统计一次最后一行的数值 k=1;//初始化开始检索的位置

while(k

21

{ j=IndexBF(S,T,k);//调用串匹配函数 if(j<0) break; else{ i++;//单词计数器累加1

k=j+T.length;//继续下一个子串的检索

}

}

}

printf(\单词%s在文本%s中共出现%d次！\\n\ }//if1 if(xz==2){

printf(\请输入文本文件名(如abc.txt)：\ scanf(\

if((fp1=fopen(filename1,\以读的方式打开文件 { printf(\文件打开失败，按请按任意键退出！\\n\ getch(); exit(0); }

printf(\输入要统计计数的单词：\scanf(\ T.length=strlen(T.ch); GetNext(T,next);

while(!feof(fp1)){//循环扫描整个文本

22

fgets(S.ch,MAXSTRLEN,fp1);//读入一行文本，并为S.length赋值

}

printf(\单词%s在文本%s中共出现%d次！\\n\ }//if2 }

S.length=lenth(S.ch);//求读入的串的长度

if(feof(fp1)) break;//不加则会多统计一次最后一行的数值 k=1;//初始化开始检索的位置 while(k

j=IndexKMP1(S,T,next,k);//调用串匹配函数 if(j<0) break; else{ }

i++;//单词计数器累加1

k=j+T.length;//继续下一个子串的检索

③void StrPP()//检索单词出现在文本文件中的行号、位置及在该行中出现的次数函数

{

FILE *fp;

SeqString S,T;//定义两个串变量 char filename[15]; int i=0,j=0,k=0,l=0,m=0;

int sz[20];//存放一行中子串匹配的多个位置 printf(\请输入文件名(如abc.txt)：\

23