C语言算法查找字符串在文中出现的次数.docx
- 文档编号:17360338
- 上传时间:2023-07-24
- 格式:DOCX
- 页数:12
- 大小:36.26KB
C语言算法查找字符串在文中出现的次数.docx
《C语言算法查找字符串在文中出现的次数.docx》由会员分享,可在线阅读,更多相关《C语言算法查找字符串在文中出现的次数.docx(12页珍藏版)》请在冰点文库上搜索。
C语言算法查找字符串在文中出现的次数
C语言算法-査找字符串在文中出现的次数。
1.问题描述
1
2.基本要求1
3.数据结构1
4.算法设计思想及流程图
1
5.源程序5
6.测试情况8
参考文献8
问题描述
建立一个文本文件,每个单词不包含空格且不跨行,单词由字符序列构成且区分大小写。
统计给定单词在文本文件中出现的总次数;检索输出某个单词出现在文本中的行号、在该行中出现的位置。
2.基本要求
].才^文彳牛
2.输入一个不含空格的单词,统计输出在文本中出现的次数
3.输入一个,检索并输出在文本中出现的行号和该行中的相应位置
3.数据结构
1.子函数设计:
(1).voidget_next(SStringT,intnext[])〃求next值
(2).intIndex(SStringS,SStringT,intpos)//KMP算法
(3).voidfind(charname[],SStringkeys)//查找函数
2.主函数调用设计:
intmainO〃主函数
3.结构设计:
^defineMAXSTRLEN255〃最大串长
typedefcharSString[MAXSTRLEN+1];//串的定长顺序存储表
示
intnext[MAXSTRLEN]//KMP算法中用到的next
4.算法设计思想及流程图
主函数设计:
intmain()
{
charname[50];〃存储输入的小说路径字符串
SStringwords[10];//定义字符串数组,用于存储输入的关键字
intn,i;
RZjptf("Plea理剖pyt迪@gfc块亘卫
scanfname);
pHntf("IfejLJJSOXJRSJ血卫SLXQLWnttofind?
(n〈]0)\n"肚
sc妙f血;
printf(^Pleaseinputthewordsyouwanttofind:
\n");
for(i=0;i 一g逊血如虫[辽[丄LL;一〃用户二次堆输‘入•裏查找的JIM室亠words[i][0]用于存放字符串的长度 for(i=0;i find(name,words[i]);//对于每一个关键字,调用查找函数进行查找统 it L 子函数设计: 〃求next值 voidget_next(SStringT,intnext[])〃求next值 {" intj=l,k=0; next[l]=0; while(j { if(k=0||T[k]二二T[j]) { ++j;++k; if(T[j]! =T[kJ)next[j]=k; elsenext[j]=next[k]; } elsek=next[k]; } } //KMP算法 intIndex(SStringS,SStringT,intpos)//KMP算法 { inti二pos,j=l; while(i<=S[O]&&j<=T[Oj) { if(j=O||S[i]=T[j]){++i;++j;} else j=next[j]; } if(j>T[O])return(i-T[0]); else return0; //求串长 intlenth(SStringstr)//求串长 inti=l; while(str[i])i++; return(i-l); } 〃査找函数 voidfind(charname[],SStringkeys)//对于输入的每一个/要査找的 关键字,从小说文件中逐行读取字符串査找 { SStringtext;//存放从小说文件读取的一行字符串 inti=l,j=0,k;//i用于存放行号,j用于存放列号,k用于输出格式的控制 FILE*fp; if(! (fp=(fopen(name,*r0)))〃打开小说文件 { printf("0penfileerror! \n^); exit(0); keys[0]=lenth(keys);//求关键字的长度 get_next(keys,next): 〃求模式串(关键字)每一个字符对应 的next值 printf("%s\iT,&keys[l]);〃打印关键字 wh订e(! feof(fp))〃如果还没到小说文件末尾 { k=0; fgets(&text[l],MAXSTRLEN,fp);〃从小说文件中读取一行字符串,存 入text串中 text[0]=lenth(text);//求读入的串的长度 j=Index(text,keys,j+1);//调用KMP算法,统计关键字在该行出 现的位置,若匹配不成功则返回0 if(J! =0) {num++;〃次数加1 printf('第%d次出现在第%d行第%d列\n^>num,i,j);k++;}〃若匹配成功则打印次数、行号和列号 while(j! =0)〃若该行找到了关键字,则继续寻找看是否还能匹配 成功 { j=Index(text,keys,j+1);〃调用KMP算法从刚找到的列号后一字符起匹配 if(J! =0) {num++;〃次数加1 printfC第%<1次出现在第%d行第%(1列\n',num,i,j);}//若匹配成功, 则打印次数.行号.列号 } i++;//行号加1,在下一行中寻找 if(k)printf("\n");//输出格式控制 算法流程图: KMP串匹配示意图: 1=2 第一趟 产舷]! 二炕刀J不变,jjt动到引 第二趟 第三趟 戸2W觀磁卿鸿 b七收, ff j=0j=4rg回! =-b[4]j,不变j潰动到門 r6i=io r6-a^ababcabcacbab" b=W^ 11 j=LJ=5 严j大于b子勇的长度丿匹配成功,函数返回F6 甸46无回測算法匹配过程 5.源程序 #include #include #defineMAXSTRLEN255〃最大串长 typedefcharSString[MAXSTRLEN+l];〃串的定长顺序存储表示 intnext[MAXSTRLEN];//KMP算法中用到的next voidget_next(SStringT,intnext】])//求next值 { intj=l,k=0; next[l]=0; while(j if(k==O||T[k]=T[j]) ++j;++k; if(T[j]! =T[k])next[j]=k;elsenext[j]=next[k]; } elsek=next[k]: } }intIndex(SStringS,SStringT,intpos)//KMP算法 { inti=pos,j=l; while(i<=S[0]&&j<=T[01) { 辻(j==0||S[i]==T[j]){++i;卄j;} else j=next[j]; } if(j>T[O])return(i-T[0]); else return0; } intlenth(SStringstr)//求串长 { inti=l; while(str[i])i++; return(iT); } voidfind(charname[],SStringkeys)〃査找函数,该函数是整个程序的重要部分,对于输入的每一个 {〃要査找的关键字,从小说文件中逐 行读取字符串査找 SStringtext;〃存放从小说文件读取的一行字符串 inti=l,j=0,k,num=0;//i用于存放行号,j用于存放列号,k用于输出格式 的控制 FILE*fp; if(! (fp=(fopen(name,*r^))))//打开小说文件 { printf("Openfileerror! \n^); exit(0); } keys[O]=lenth(keys);〃求关键字的长度 get.next(keys,next);〃求模式串(关键字)每一个字符对应的next 值 printf(*%s\n^>&keys[1]);//打印关键字 while(! feof(fp))〃如果还没到小说文件末尾 { k=0; fgets(fttext[1],MAXSTRLEN,fp);〃从小说文件中读取一行字符串,存 入text串中 text[0]=lenth(text);〃求读入的串的长度 j=Index(text,keys,j+1);//调用KMP算法'统计关键字在该行出 现的位置,若匹配不成功则返回0 if(j! =0) {num++; printf("第%d次岀现在第%d行第%d列\iT,num,i,j); k++;}〃若匹配成功则打印行号和列号 while(j! =0)〃若该行找到了关键字,则继续寻找看是否还能匹配 成功 { j二Index(text,keys,j+1);〃调用KMP算法从刚找到的列号后一字符起匹配 if(J! =0) {num++; printf("第%d次出现在第%d行第%d列\『,num,i,j);}//若匹配成功,则打印列号 } i++;//行号加1,在下一行中寻找 辻(k)printfC\n");//输出格式控制 } }intmain() { charname[50];〃存储输入的小说路径字符串 SStringwords[10];〃定义字符串数组,用于存储输入的关键字 intn,i; printf("Pleaseinputthenameofthenovel: \n"); scanfname); printf("Howmanywordsdoyouwanttofind? (n〈10)\n");scanf&n); printf("Pleaseinputthewordsyouwanttofind: \rT); for(i=0;i scanf&words[i][1]);//用户一次性输入要査找的关键字,words[i][01用于存放字符串的长度 for(i=0;i find(name,words[i]); }//对于每一个关键字,调用査找函数进行査找统计 6.测试情况 ca*D: \l\c\Debu^\Cppl.exe* Pressanykeytocontinue JDJx 涣歹炎 596 5G8笫第第気仃行在在在现现现岀出岀次次次123 Pleaseinputthenameofthenoue1: 123.txt Howmanyv/ordsdoyouv/anttofind? Pleaseinputthewordsyouv/anttofind: m 参考文献: [1]谭浩强.c程序设计(第三版)[M].北京: 清华大学出版社.330-336. [2]陈守孔,孟佳娜,武秀川.算法与数据结构[M].北京: 机械工业出版社・71-80
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 语言 算法 查找 字符串 文中 出现 次数