C语言算法,查找字符串在文中出现的次数.doc

目录一问题描述-1二基本要求-1三数据结构-1四算法设计思想及流程图-1五源程序-5六测试情况-8参考文献-8 一 问题描述建立一个文本文件，每个单词不包含空格且不跨行，单词由字符序列构成且区分大小写。统计给定单词在文本文件中出现的总次数；检索输出某个单词出现在文本中的行号、在该行中出现的位置。二 基本要求 1.建立一个文本文件2.输入一个不含空格的单词，统计输出在文本中出现的次数3.输入一个，检索并输出在文本中出现的行号和该行中的相应位置三 数据结构1子函数设计:(1). void get_next(SString T,int next) /求next值(2). int Index(SString S,SString T,int pos) /KMP算法(3). void find(char name,SString keys) /查找函数2. 主函数调用设计:int main() /主函数3. 结构设计: #define MAXSTRLEN 255 /最大串长typedef char SStringMAXSTRLEN+1; /串的定长顺序存储表示int nextMAXSTRLEN /KMP算法中用到的next四算法设计思想及流程图主函数设计：int main()char name50; /存储输入的小说路径字符串SString words10; /定义字符串数组，用于存储输入的关键字int n,i;printf(Please input the name of the novel:n);scanf(%s,name);printf(How many words do you want to find?(n10)n);scanf(%d,&n);printf(Please input the words you want to find:n);for (i=0;in;i+) scanf(%s,&wordsi1); /用户一次性输入要查找的关键字，wordsi0用于存放字符串的长度for (i=0;in;i+) find(name,wordsi); /对于每一个关键字，调用查找函数进行查找统计 子函数设计：/求next值void get_next(SString T,int next) /求next值int j=1,k=0;next1=0; while(jT0) if(k=0|Tk=Tj) +j;+k; if(Tj!=Tk) nextj=k; else nextj=nextk; else k=nextk;/KMP算法int Index(SString S,SString T,int pos) /KMP算法int i=pos,j=1; while(i=S0&jT0) return (i-T0); else return 0;/求串长int lenth(SString str) /求串长int i=1;while(stri) i+;return(i-1);/查找函数void find(char name,SString keys) /对于输入的每一个/要查找的关键字，从小说文件中逐行读取字符串查找 SString text; /存放从小说文件读取的一行字符串 int i=1,j=0,k; /i用于存放行号，j用于存放列号,k用于输出格式的控制FILE *fp;if (!(fp=(fopen(name,r) /打开小说文件 printf(Open file error!n); exit(0); keys0=lenth(keys); /求关键字的长度get_next(keys,next); /求模式串（关键字）每一个字符对应的next值printf(%sn,&keys1); /打印关键字while (!feof(fp) /如果还没到小说文件末尾 k=0; fgets(&text1,MAXSTRLEN,fp); /从小说文件中读取一行字符串，存入text串中 text0=lenth(text); /求读入的串的长度 j=Index(text,keys,j+1); /调用KMP算法，统计关键字在该行出现的位置，若匹配不成功则返回0 if (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+; /次数加1 printf(第%d次出现在第%d行第%d列n,num,i,j); /若匹配成功，则打印次数、行号、列号 i+; /行号加1，在下一行中寻找 if (k) printf(n); /输出格式控制 算法流程图：读入一个文本文档以只读形式打开文件，读取数据读入一行数据KMP串匹配成功本行结束计数，输出单词所在位置查找完成KMP串匹配示意图：五源程序#include #include #define MAXSTRLEN 255 /最大串长typedef char SStringMAXSTRLEN+1; /串的定长顺序存储表示int nextMAXSTRLEN; /KMP算法中用到的nextvoid get_next(SString T,int next) /求next值int j=1,k=0;next1=0; while(jT0) if(k=0|Tk=Tj) +j;+k; if(Tj!=Tk) nextj=k; else nextj=nextk; else k=nextk;int Index(SString S,SString T,int pos) /KMP算法int i=pos,j=1; while(i=S0&jT0) return (i-T0); else return 0;int lenth(SString str) /求串长int i=1;while(stri) i+;return(i-1);void find(char name,SString keys) /查找函数，该函数是整个程序的重要部分，对于输入的每一个 /要查找的关键字，从小说文件中逐行读取字符串查找SString text; /存放从小说文件读取的一行字符串 int i=1,j=0,k,num=0; /i用于存放行号，j用于存放列号,k用于输出格式的控制FILE *fp;if (!(fp=(fopen(name,r) /打开小说文件 printf(Open file error!n); exit(0); keys0=lenth(keys); /求关键字的长度get_next(keys,next); /求模式串（关键字）每一个字符对应的next值printf(%sn,&keys1); /打印关键字while (!feof(fp) /如果还没到小说文件末尾 k=0; fgets(&text1,MAXSTRLEN,fp); /从小说文件中读取一行字符串，存入text串中 text0=lenth(text); /求读入的串的长度j=Index(text,keys,j+1); /调用KMP算法，统计关键字在该行出现的位置，若匹配不成功则返回0 if (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); /输出格式控制int main()char name50; /存储输入的小说路径字符串SString words10; /定义字符串数组，用于存储输入的关键字int n,i;printf(Please input the name of the novel:n);scanf(%s,name);printf(How many words do you want to find?(n10)n);scanf(%d,&n);printf(Please input the words you want to find:n);for (i=0;in;i+) scanf(%s,