文学研究助手与模式匹配算法KMP

1、北京理工大学珠海学院计算机学院课程设计-i -北京理工大学珠海学院课程设计说明书2010 2011学年第二学期题目:文学研究助手与模式匹配算法KMP学 院：计算机科学与技术学院专业班级：学 号：_学生姓名：_指导教师:_成 绩：_时 间：_北京理工大学珠海学院计算机学院课程设计-2 -北京理工大学珠海学院课程设计任务书20102011学年第二学期学生姓名： 专业班级：指导教师： 工作部门：一、课程设计题目文学研究助手与模式匹配算法KMP二、课程设计内容（含技术指标）【问题描述】文学研究人员需要统计某篇英文小说中某些形容词的出现次数 和位置。试写一个实现这一目标的文字统计系统【任务要求】英文小说

2、存于一个文本文件中。待统计的词汇集合要一次输入完 毕，即统计工作必须在程序的一次运行之后就全部完成。程序的输出结果是每个词的出现次数和出现位置所在的行的行号，格式白行设 计。待统计的“单词”在文本串中不跨行出现，它或者从行首开始， 或者前置以一个空格符。模式匹配要基于KMF#法。推广到更一般的模式集匹配问题，并设待查模式串可以跨行（提示：定义操作GetAChar）。【测试数据】文本文件为testword.c待统计的词集:if、else、for、while、return、void、int、char、typedef、struct三、进度安排北京理工大学珠海学院计算机学院课程设计-3 -1.初步设计

3、：写出初步设计思路，进行修改完善，并进行初步 设计。2.详细设计：根据确定的设计思想，进一步完善初步设计内容， 按要求编写出数据结构类型定义、各算法程序、主函数。编译分析调 试错误。3.测试分析：设计几组数据进行测试分析，查找存在的设计缺 陷，完善程序。4.报告撰写：根据上面设计过程和结果，按照要求写出设计报 告。5.答辩考核验收：教师按组（人）检查验收，并提出相关问题， 以便检验设计完成情况。四、基本要求1.在设计时，要严格按照题意要求独立进行设计，不能随意更 改。若确因条件所限，必须要改变课题要求时，应在征得指导教师同 意的前提下进行。2.在设计完成后，应当场运行和答辩，由指导教师验收，只

4、有 在验收合格后才能算设计部分的结束。3.设计结束后要写出课程设计报告，以作为整个课程设计评分的书面依据和存档材料。设计报告以规定格式的电子文档书写、打印 并装订，报告格式严格按照模板要求撰写，排版及图、表要清楚、工 整。从总体来说，所设计的程序应该全部符合要求，问题模型、求解 算法以及存储结构清晰；具有友好、清晰的界面；设计要包括所需要 的辅助程序，如必要的数据输入、输出、显示和错误检测功能；操作 使用要简便；程序的整体结构及局部结构要合理； 设计报告要符合规 范。课程负责人签名:北京理工大学珠海学院计算机学院课程设计-4 -题目选题四：文学研究助手与模式匹配算法KMP摘要本实践课题重在对文

5、本的查询,在实际应用中有重大作用。通过本程序,可统 计所需文本的一个或多个词汇在文本中出现的次数与位置，其作用在丁给使用者研究一篇文学著作时提供帮助。当研究一片文学著作时，不紧要理解著作的内容 和寓意，有是更需要分析作者的写作手法和习惯， 这是统计著作中词汇的出现次 数与位置成了文学研究的重点课题。本程序就可以为文学研究者提供这类帮助。 本程序基丁模式匹配算法 KMPKMP 实现，为普通模式匹配的改进，优点在与时间 复杂度由原来的 O O(n*m)(n*m)变为 O O (n+m)(n+m)，即是说统计时间大大缩短。当要统计 的词汇量很大时，计算机统计所需时间将很漫长，如果使用者急需使用统计结

6、果， 这是乂因为统计太慢导致研究受阻， 这样就得不偿失了。而本程序将大大改善这 种状况，让计算机在短时间内统计出使用者想要的统计结果。本程序虽然精简， 但是对模式匹配算法 KMPKMP 的使用极其灵活， 需开发者深刻理解模式匹配算法 KMP,KMP,思路活晰， 灵活调用模式匹配算法 KMKMP P的函数，否则开发者将极难开发 成功。关键词：文学研究模式匹配 KMPKMP北京理工大学珠海学院计算机学院课程设计-5 -摘要.-4 -关键词.-4 -1课程设计相关 .-6 -1.1题目要求 .-6 -1.1.1实验所在地点 .-6 -2课程设计实施 .-7 -2.1设计思路 .-7 -2.1.1课程

7、设计时间分配.-7 -2.2源程序代码实现 .-8 -2.3程序调试演示与分析 .10 -参考文献.-13 -心得体会.-14 -教师评语.15计算机学院课程设计答辩记录表.错误！未定义书签北京理工大学珠海学院计算机学院课程设计-6 -1课程设计相关1.1题目要求【问题描述】文学研究人员需要统计某篇英文小说中某些形容词的出现次数和位置。试写一个实现这一目标的文字统计系统【任务要求】1 1） 英文小说存丁一个文本文件中。待统计的词汇集合要一次输入完毕，即 统计工作必须在程序的一次运行之后就全部完成。程序的输出结果是每 个词的出现次数和出现位置所在的行的行号，格式自行设计。待统计的“单词”在文本申

8、中不跨行出现，它或者从行首开始，或者前置以一个 空格符。2 2） 模式匹配要基丁 KMPKMP 算法。3 3） 推广到更一般的模式集匹配问题，并设待查模式申可以跨行（提示：定 义操作GetAChaDGetAChaD。【测试数据】1 1） 文本文件为 testword.ctestword.c2 2） 待统计的词集：ifif、elseelse、forfor、whilewhile、returnreturn、voidvoid、intint、charchar、typedeftypedef、structstruct【成绩评定】1 1） 完成“任务要求”第 1 1 项成绩评定为“及格”-“中”。2 2）完成

9、“任务要求”第2项至第3项成绩评定为“良”及以上。1.1.1实验所在地点本实验实行所在地点丁学校教学楼多媒体实验室JB405,JB405,如图1-1图1-1学校设施组织结构图北京理工大学珠海学院计算机学院课程设计-7 -2课程设计实施2.1设计思路本实践重在对模式匹配算法 KMPKMP 勺调用。KMPWKMPW 法在数据结构（C C 语言版）中 的第 8 82 2页有详细解释，在此不予以解释。我的大概思路是：1.1. 打开文件2.2. 输入想要匹配的一组字符申3.3. 读取文件的一行4 4 .把每一个字符申在该行中实行模式匹配 KMPKMP5 5 .重复步骤 3 3 和 4 46 6 .输出结

10、果2.1.1课程设计时间分配本课程时间分为 4 4 天，1616 个课时，设计工作时间分配由学生自行分配。我的 课程设计工作分配时间表如表 2-12-1。表2-1详情分工时间备注思路梳理与理论了解第一天可实行部分编程编程实现第二天注怠与备注程序检验与改善第二天准备写说明书程序设计说明书整理第四天打印，答辩开发一个软件，就算再小，时间分配上也是很重要的。在第一天，我将了解模 式匹配算法 KMPKMP 的设计思路，再梳理出我设计本程序的大概思路。当思路梳理 得差不多的时候就可以开始编程，第一天的编程还是以编写程序框架为主， 先要 把思路的框架写出来，为第二天的编程实现作准备。第二天开始正式变成实现

11、，在第一天编写出的程序框架的基础上， 填写程序的实际内容。由丁第一天已编写 出大概框架，因此实际编程事半工倍。第三天实行程序的检验与改善。第二天编 写出来的程序已能够实现所需功能， 但程序的格式还比较乱，也没有对读取出错 进行处理。在这一天里，将对程序进行检验与改善，令程序更完美。在闲暇之余， 还可以适当为课程设计说明书作准备， 写出说明书模版以及完成部分内容。 第四 天对课程设计说明书进行进一部的整理和完成，并在答辩之前把说明书打印出 来。北京理工大学珠海学院计算机学院课程设计-8 -2.2源程序代码实现#include #include #define MAXSTRLEN 255最大串长t

12、ypedef char SStringMAXSTRLEN+1;串的定长顺序存储表示int nextMAXSTRLEN;/KMP算法中用到的nextint Index(SString S,SString T,int pos) /KMP算法，P82int i=pos,j=1;while(i=S0&jT0) return (i-T0);elsereturn 0;int lenth(SString str) /求串长int i=1;while(stri) i+;return(i-1);void find(char name,SString keys)查找函数SString text;/用于存放

13、从小说文件读取的一行字符串int i=1,j=0,k,q=0;/i用于存放行号,j用于存放列号，k用于输出格式的控制，q用于统计出现次数FILE *fp;if (!(fp=(fopen(name,r)/打开小说文件printf(打开文件出错!n”);exit(0);keys0=lenth(keys);求关键字的长度printf(n%sn”,&keys1);/打印关键字while (!feof(fp)/如果还没到小说文件末尾，则继续循环北京理工大学珠海学院计算机学院课程设计-9 - k=0; fgets(&text1,MAXSTRLEN,fp);从小说文件中读取一行字符串，存入t

14、ext串中text0=lenth(text);/求读入的串的长度j=Index(text,keys,j+1);/调用KMP算法，统计关键字在该行出现的位置，若匹配不成功则返回0 if (j!=0) printf(-行=%d,列=%d,i,j); k+;若匹配成功则打印行号和列号while(j!=0)/若该行找到了关键字，则继续寻找看是否还能匹配成功 j=Index(text,keys,j+1);/调用KMP算法从刚找到的列号后一字符起匹配if (j!=0) printf(,%d,j);k+; /若匹配成功，则打印列号 i+; /行号加1,在下一行中寻找q+=k;/累加k以统计关键字出现次数if

15、 (k) printf(n);输出格式控制 printf(%s出现d次。n”,&keys1,q);/打印关键字出现次数void main()char name50;/存储输入的小说路径字符串SString words10;定义字符串数组，用于存储输入的关键字int m,n,i;printf(-欢迎使用文学研究助手 -);/打印标题while(1) /不停循环，直至完成查询或者退出服务printf(是否需要为你服务：需要输入1,不需要输入0。n);/询问是否需要服务scanf(%d,&m);输入判断是否需要服务if(m=1) /需要服务时执行printf(输入你想查询的文档名字：

16、n);scanf(%s,name);/输入文件名printf(输入查询字符串的个数：n);scanf(%d”,&n);输入查询字符串个数printf(输入你要查询的字符串：n); for (i=0;in;i+) scanf(%s”,&wordsi1);/用户一次性输入要查找的关键字，wordsi0用于存放字符串的长度for (i=0;iESS乱my key to continue分析结果发现，程序统计完自动退出。 明程序正常运行并统计出了正确的数据。再对比统计结果是否正确，发现结果是正确的，表北京理工大学珠海学院计算机学院课程设计-13 -参考文献11严蔚敏，吴伟民：数据结构（

17、C C 语言版）M,M,活华大学出版社 20072007 年版,第 80-8480-84 贞。北京理工大学珠海学院计算机学院课程设计-14 -心得体会通过这一次课程实践，我获益良多，明白了很多之前不明白的，注意到了很多 之前没注意的东西。虽然这个程序比较短，可短而精，特别是对丁模式匹配算法 KMPKMP 勺运用尤其灵活。另外，我注意了很多细节，从中学到了很多。总的来说包 括以下几点：1.1. 对丁错误信息的处理问题。本程序有打开文件、输入判断等运用，如果对错 误信息不加以处理，将会导致程序运行时使用户不活楚或感到程序忽然死亡的情 况。对这一细节加以处理后不仅程序美观， 条理活晰，还对用户的使用提供了方 便，容易上手。2.2. 注释应尽量详细。详细的注释不仅能够让看的人活晰明了，对编程者本人的 思路整理有好处，使得在编程的过程中不易产生混乱。3.3. 编程时注意对程序的优化。虽然计算机的处理速度很快，可是当处理的信息 一旦太多时，计算机容易反应不过来。为了避免这种情况的发生，程序应当简洁、 省时省空间，力求在时间复杂度和空间复杂度之上有所优势，节约资源。4.4. 思路是编程的核心，在编程之前一定要理活思路，这样编程时才会事半工倍。 如果在编程是遇到了瓶颈，应当静下心来重新整理思路，并寻找