C语言算法-查找字符串在文中出现的次数。

0目录一．问题描述-------------------------------------------1二．基本要求---------------------------------------------------------------1三．数据结构----------------------------------------------------------------1四．算法设计思想及流程图-----------------------------------------------1五．源程序-------------------------------------------------------------------5六．测试情况----------------------------------------------------------------8参考文献---------------------------------------------------------------------81一．问题描述建立一个文本文件，每个单词不包含空格且不跨行，单词由字符序列构成且区分大小写。统计给定单词在文本文件中出现的总次数；检索输出某个单词出现在文本中的行号、在该行中出现的位置。二．基本要求1.建立一个文本文件2.输入一个不含空格的单词，统计输出在文本中出现的次数3.输入一个，检索并输出在文本中出现的行号和该行中的相应位置三．数据结构1．子函数设计:(1).voidget_next(SStringT,intnext[])//求next值(2).intIndex(SStringS,SStringT,intpos)//KMP算法(3).voidfind(charname[],SStringkeys)//查找函数2.主函数调用设计:intmain()//主函数3.结构设计:#defineMAXSTRLEN255//最大串长typedefcharSString[MAXSTRLEN+1];//串的定长顺序存储表示intnext[MAXSTRLEN]//KMP算法中用到的next四．算法设计思想及流程图主函数设计：intmain(){charname[50];//存储输入的小说路径字符串SStringwords[10];//定义字符串数组，用于存储输入的关键字intn,i;printf(Pleaseinputthenameofthenovel:\n);scanf(%s,name);printf(Howmanywordsdoyouwanttofind?(n10)\n);scanf(%d,&n);printf(Pleaseinputthewordsyouwanttofind:\n);for(i=0;in;i++)scanf(%s,&words[i][1]);//用户一次性输入要查找的关键字，words[i][0]用于存放字符串的长度for(i=0;in;i++)find(name,words[i]);//对于每一个关键字，调用查找函数进行查找统计}2子函数设计：//求next值voidget_next(SStringT,intnext[])//求next值{intj=1,k=0;next[1]=0;while(jT[0]){if(k==0||T[k]==T[j]){++j;++k;if(T[j]!=T[k])next[j]=k;elsenext[j]=next[k];}elsek=next[k];}}//KMP算法intIndex(SStringS,SStringT,intpos)//KMP算法{inti=pos,j=1;while(i=S[0]&&j=T[0]){if(j==0||S[i]==T[j]){++i;++j;}elsej=next[j];}if(jT[0])return(i-T[0]);elsereturn0;}//求串长intlenth(SStringstr)//求串长{inti=1;while(str[i])i++;return(i-1);}3//查找函数voidfind(charname[],SStringkeys)//对于输入的每一个/要查找的关键字，从小说文件中逐行读取字符串查找{SStringtext;//存放从小说文件读取的一行字符串inti=1,j=0,k;//i用于存放行号，j用于存放列号,k用于输出格式的控制FILE*fp;if(!(fp=(fopen(name,r))))//打开小说文件{printf(Openfileerror!\n);exit(0);}keys[0]=lenth(keys);//求关键字的长度get_next(keys,next);//求模式串（关键字）每一个字符对应的next值printf(%s\n,&keys[1]);//打印关键字while(!feof(fp))//如果还没到小说文件末尾{k=0;fgets(&text[1],MAXSTRLEN,fp);//从小说文件中读取一行字符串，存入text串中text[0]=lenth(text);//求读入的串的长度j=Index(text,keys,j+1);//调用KMP算法，统计关键字在该行出现的位置，若匹配不成功则返回0if(j!=0){num++；//次数加1printf(第%d次出现在第%d行第%d列\n,num,i,j);k++;}//若匹配成功则打印次数、行号和列号while(j!=0)//若该行找到了关键字，则继续寻找看是否还能匹配成功{j=Index(text,keys,j+1);//调用KMP算法从刚找到的列号后一字符起匹配if(j!=0){num++;//次数加1printf(第%d次出现在第%d行第%d列\n,num,i,j);}//若匹配成功，则打印次数、行号、列号}i++;//行号加1，在下一行中寻找if(k)printf(\n);//输出格式控制}}4算法流程图：KMP串匹配示意图：读入一个文本文档以只读形式打开文件，读取数据读入一行数据KMP串匹配计数，输出单词所在位置本行结束查找完成成功5五．源程序#includestdio.h#includestdlib.h#defineMAXSTRLEN255//最大串长typedefcharSString[MAXSTRLEN+1];//串的定长顺序存储表示intnext[MAXSTRLEN];//KMP算法中用到的nextvoidget_next(SStringT,intnext[])//求next值{intj=1,k=0;next[1]=0;while(jT[0]){if(k==0||T[k]==T[j]){++j;++k;if(T[j]!=T[k])next[j]=k;elsenext[j]=next[k];6}elsek=next[k];}}intIndex(SStringS,SStringT,intpos)//KMP算法{inti=pos,j=1;while(i=S[0]&&j=T[0]){if(j==0||S[i]==T[j]){++i;++j;}elsej=next[j];}if(jT[0])return(i-T[0]);elsereturn0;}intlenth(SStringstr)//求串长{inti=1;while(str[i])i++;return(i-1);}voidfind(charname[],SStringkeys)//查找函数，该函数是整个程序的重要部分，对于输入的每一个{//要查找的关键字，从小说文件中逐行读取字符串查找SStringtext;//存放从小说文件读取的一行字符串inti=1,j=0,k,num=0;//i用于存放行号，j用于存放列号,k用于输出格式的控制FILE*fp;if(!(fp=(fopen(name,r))))//打开小说文件{printf(Openfileerror!\n);exit(0);}keys[0]=lenth(keys);//求关键字的长度get_next(keys,next);//求模式串（关键字）每一个字符对应的next值7printf(%s\n,&keys[1]);//打印关键字while(!feof(fp))//如果还没到小说文件末尾{k=0;fgets(&text[1],MAXSTRLEN,fp);//从小说文件中读取一行字符串，存入text串中text[0]=lenth(text);//求读入的串的长度j=Index(text,keys,j+1);//调用KMP算法，统计关键字在该行出现的位置，若匹配不成功则返回0if(j!=0){num++;printf(第%d次出现在第%d行第%d列\n,num,i,j);k++;}//若匹配成功则打印行号和列号while(j!=0)//若该行找到了关键字，则继续寻找看是否还能匹配成功{j=Index(text,keys,j+1);//调用KMP算法从刚找到的列号后一字符起匹配if(j!=0){num++;printf(第%d次出现在第%d行第%d列\n,num,i,j);}//若匹配成功，则打印列号}i++;//行号加1，在下一行中寻找if(k)printf(\n);//输出格式控制}}intmain(){charname[50];//存储输入的小说路径字符串SStringwords[10];//定义字符串数组，用于存储输入的关键字intn,i;printf(Pleaseinputthenameofthenovel:\n);scanf(%s,name);printf(Howmanywordsdoyouwanttofind?(n10)\n);scanf(%d,&n);printf(Pleaseinputthewordsyouwanttofind:\n);for(i=0;in;i++)scanf(%s,&words[i][1]);//用户一次性输入要查找的关键字，words[i][0]用于存放字符串的长度for(i=0;in;i++)8find(name,words[i]);}//对于每一个关键字，调用查找函数进行查找统计六．测试情况参考文献：[1]谭浩强.C程序设计(第三版)[M].北京：清华大学出版社.330-336.[2]陈守孔，孟佳娜，武秀川.算法与数据结构[M].北京：机械工业出版社.71-80