文学研究助手系统

数据结构课程设计之“文学研究助手系统”的设计与实现第1页共11页实验名称：“文学研究助手系统”的设计与实现实验人员：xxxxxx专业班级：11计科专业实验指导老师：xxxxxxx实验日期：2013年3月21日数据结构课程设计之“文学研究助手系统”的设计与实现第2页共11页目录1.设计要求..........................................................31.1问题描述....................................................31.2需求分析....................................................32概要设计..........................................................32.建立和读入文本文件............................................32.2存储结构设计................................................32.3字符串的模式匹配问题.........................................33模块设计..........................................................33.1模块设计....................................................33.2程序子程序及功能设计........................................43.3函数主要调用关系............................................44详细设计..........................................................44.1数据类型定义................................................44.2系统主要子程序详细设计......................................45测试分析..........................................................66用户手册..........................................................87实验分工..........................................................88实验心得..........................................................89实验创新..........................................................910附录源代码.....................................................9数据结构课程设计之“文学研究助手系统”的设计与实现第3页共11页“文学研究助手系统”的设计与实现1.设计要求1.1问题描述文学研究人员需要统计某篇英文小说中某些特定单词的出现次数和位置（行号和列号）。试写出一个实现这一目标的文字统计系统，称为“文学研究助手系统”。1.2需求分析要求建立一个文本文件，每个单词不包含空格且不跨行，单词由字符序列构成且区分大小写；检索输出给定单词出现在文本中的行号，以及在该行中出现的位置（列号）；统计给定单词在文本文件中出现的总次数。2概要设计该设计可分为三个部分实现；第一，建立文本文件，文件名由用户通过键盘输入；第二，检索给定单词：输入一个单词，检索并输出该单词所在的行号和列号；第三，给定单词的计数：输入一个单词，统计输出该单词在文本中的出现次数。可从3个方面着手设计。2.1建立和读入文本文件建立和读入文件的实现步骤如下：（1）定义一个串变量；（2）定义文本文件；（3）输入文件名，打开该文件；（4）循环读入文本行，写入文本文件，其过程如下：While(不是文件输入结束符){读入一文本行至串变量；串变量写入文件；输入是否结束输入标志；}2.2存储结构设计主串和模式串都采用定长顺序存储表示，其0号单元存放串的长度：#defineMAXSTRLEN255//最大串长TypedefcharSString[MAXSTRLEN+1];//定长顺序存储表示2.3字符串的模式匹配问题本系统使用改进的KMP匹配算法实现字符串的模式匹配问题。匹配可如下进行：假设以指针i和j分别指示主串和模式中的比较字符，令i的初值为pos,j的初值为1.若在匹配过程中si=sj,则i和j分别增1，若si≠sj匹配失败后，则i不变，j退到next[j]位置再比较，若相等，则指针各自增1，否则j再退到下一个next值的位置，依次类推。直至下列两种情况：一种是j退到某个next值时字符比较相等，则i和j分别增1继续进行匹配；另一种是j退到值为零（即模式的第一个字符失败），则此时i和j也要分别增1，表明从主串的下一个字符起和模式重新开始匹配。3模块设计（1）.模块设计本程序包含3个模块：主程序模块，查找模块，功能模块。数据结构课程设计之“文学研究助手系统”的设计与实现第4页共11页其调用关系如图所示。3.2程序（2）.子程序及功能设计本系统共设置5个子程序，各子程序的函数名及功能说明如下。（1）Voidget_next(SStringT,intnext[])//求模式串T的next函数值并存入数组next（2）IntIndex(SStringS,SStringT,intpos）//KMP匹配函数（3）Intlenth(SStringstr)//取串str的长度（4）Voidfind(charname[],SStringkeys)//查找函数，对于输入的每一个要查找的关键字，从文本文件中逐行读取字符串查找。//调用(1),(2),(3)（5）Voidmain()//主函数，负责系统的输入和输出。调用(4)3.3函数主要调用关系本系统5程序之间的主要调用关系如图所示。图中数字是各函数的编号系统函数调用关系图4详细设计4.1数据类型定义(1)定长顺序存储串类型的定义#defineMAXSTRLEN255//最大串长typedefcharSString[MAXSTRLEN+1];//串的定长顺序存储表示，0号单元存放串的长度（2）全局变量的定义intnext[MAXSTRLEN]//KMP算法中用到的next数组4.2系统主要子程序详细设计（1）主函数模块设计，负责系统的输入输出工作，调用查找函数。voidmain(){输入包含路径的文本文件名；输入要查找的关键字个数；一次性输入要查找的关键字；主程序模块查找模块功能模块5main()4fine(charname[],SStringkeys)123数据结构课程设计之“文学研究助手系统”的设计与实现第5页共11页对于每一个关键字，循环调用find函数进行查找统计；}（2）查找模块设计voidfind(charname[],SStringkeys){//该函数是整个程序的重要部分，对于输入的每一个要查询的关键字，从小说文件中逐行//杜取字符串查找SStringtext;//存放从小说文件中读取的一行字符串inti=1,j=0,k;//i用于存放行号，j用于存放列号，k用于输出格式的控制intn=0;//n用于记录出现的次数FILE*fp;if(!(fp=(fopen(name,r))))//打开小说文件{printf(Openfileerror!\n);exit(0);}keys[0]=lenth(keys);//调用lenth函数求关键字get_next(keys,next);调用get_next函数求模式串（关键字）每一个字符对应的nextprintf(\n%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(\trow=%d,\tcol=%d,i,j);k++;n++;}while(j!=0){j=Index(text,keys,j+1);if(j!=0){n++;printf(,%d,j);}}i++;if(k)printf(\n);}printf(%s公出现%d次\n,keys[1],n);数据结构课程设计之“文学研究助手系统”的设计与实现第6页共11页}（3）其他功能模块设计1.求next函数值voidget_next(SStringT,intnext[]){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];}}}2.KMP匹配函数intIndex(SStringS,SStringT,intpos){//利用模式串T的next函数球T主串S中第POS个字符之后的位置的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;//匹配失败}5测试分析系统运行后，要求用户输入带路径的小说文件名，如图所示。数据结构课程设计之“文学研究助手系统”的设计与实现第7页共11页用户输入D：\shiyan4.txt并回车。此文本文件已正确建立，内容为：-----------------------------------------------------------------Springisadelightfulseason.Thetemperaturesaremoderate,andthebloomingtreesandflowersmakethecitybrightwithcolors.Itisthetimewhenwecanbegintowearlighterandmorebrightlycoloredclothesandgooutdoorsmoreoften.Smallerchildrenliketobringtheirkitesouttothespacioussquare.AlsoIenjorgoingbacktothevillageonthisholidayafterbejininthecityforthewintermonths.------------------------------------------------------------------回车后，系统提示用户输入待查找的单词个数，如图所示用户输入3并回车，系统提示用户输入单词内容，如图所示数据结构课程设计之“文学研究助手系统”的设计与实现第8页共11页6用户手册（1）本程序执行文件为“文学研究助手系统.exe”。（2）进入本系统后，随即显示系统主菜单界面。用户可以在该界面下按提示输入命令并观察结果。7实验分工段志芳：负责代码的添加与修改编写代码和测试纠错，严晓燕：编写代码和讨论、分析程序代码测试分析和实验报告的编写8实验心得数据结构课程设计之“文学研究助手系统”的设计与实现第9页共11页串