文学助手kmp

计算机科学与技术专业计科104张家琪2010081427文学研究助手实验报告一、问题描述：文学研究人员需要统计某篇英文小说中某些形容词的出现次数和位置。试写一个实现这一目标的文字统计系统，称为“文学研究助手”。英文小说存于一个文本文件中。待统计的词汇集合要一次输入完毕，即统计工作必须在程序的一次运行之后就全部完成。程序的输出结果是每个词的出现次数和出现位置所在行的行号，格式自行设计。二、需求分析：1、文本串非空且以文件形式存放，统计匹配的词集非空。文件名和词集均由用户从键盘输入；2、“单词”定义：由字母构成的字符序列，中间不含空格字符且区分大小写；3、待统计的“单词”在文本串中不跨行出现，它或者从行首开始，或者前置若干空格字符；4、在计算机终端输出的结果是：单词，出现的次数，出现的位置所在行的行号，同一行出现两次的只输出一个行号；5、测试数据：将实验的源程序作为测试文件,从中任意选取“单词”作为测试的词集。三．概要设计（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四．详细设计英文小说存于一个文本文件中。待统计的词汇集合要一次输入完毕，即统计工作必须在程序的一次运行之后就会全部完成。程序的输出结果是每个词出现次数和出现位置所在行的行号，格式自行设计。匹配时采用KMP算法。主函数设计：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]);//对于每一个关键字，调用查找函数进行查找统计}子函数设计：1//求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];}}2．//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;}3．//求串长intlenth(SStringstr)//求串长{inti=1;while(str[i])i++;return(i-1);}4.//查找函数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){printf(row=%d,col=%d,i,j);k++;}//若匹配成功则打印行号和列号while(j!=0)//若该行找到了关键字，则继续寻找看是否还能匹配成功{j=Index(text,keys,j+1);//调用KMP算法从刚找到的列号后一字符起匹配if(j!=0){printf(,%d,j);}//若匹配成功，则打印列号}i++;//行号加1，在下一行中寻找if(k)printf(\n);//输出格式控制}}五．运行环境Dev-C++六．调试分析七、用户使用说明：题目:文学研究助手设小说中的词汇一律不跨行。这样，每读入一行，就统计每个词在这行中出现的次数。出现位置所在行的行号可以用链表存储。若某行中出现了不止一次，不必存多个相同的行号。Input输入第一行为小说的文件名（包含路径的文本文件名）；第二行为一个正整数n，表示要查找单词的个数（n10）；从第三行开始共有n行，每行包括一个单词。Output输出共有n块，每块中第一行为查找的单词，从第二行开始为找到的各行的行号和列号，每个行号和列号占一行，若在同一行上出现多次，则只输出一个行号和多个列号并占一行，输出顺序按行号从小到大顺序排列。若没有找到则块内只输出第一行的单词即可。SampleInput1.txt41110ababc12345endSampleOutput1110row=1,col=10row=2,col=3,11ababcrow=1,col=1912345endrow=3,col=1八．实验心得1)理解分析问题的能力得到提高。设计一个应用程序关键是对要求做最准确的把握，也就是说弄清楚需求分析是很重要的。本程序要求我从文件中读取单词的位置，就是在文件中检索字符串，这样一抽象，问题的脉络就清晰了。接下来，如何读取，读取后如何映射，映射的字符串又怎么和待查字符串关联，这就构成了解决问题的几大关键模块。逐个解析，整个程序的框架就了然于胸了。特别要指出的是，对整个程序的把握，随着编程工作的深入，是越来越深刻，而且新的思路也是层出不穷。2）创新意识和创新能力的提高。3）对程序设计语言的细微之处又了更深刻的理解。不是想怎样就你能怎样的，还是需要多多练习实践的