-!
北京理工大学珠海学院
课程设计说明书
2010 — 2011 学年第二学期
题目: 文学研究助手与模式匹配算法KMP
学 院： 计算机科学与技术学院
专业班级：
学 号：
学生姓名：
指导教师：
成 绩：
时 间：
北京理工大学珠海学院
课程设计任务书
2010 ～2011学年第二学期
学生姓名： 专业班级：
指导教师： 工作部门：
一、课程设计题目
文学研究助手与模式匹配算法KMP
二、课程设计内容（含技术指标）
【问题描述】
文学研究人员需要统计某篇英文小说中某些形容词的出现次数和位置。试写一个实现这一目标的文字统计系统
【任务要求】
英文小说存于一个文本文件中。待统计的词汇集合要一次输入完毕，即统计工作必须在程序的一次运行之后就全部完成。程序的输出结果是每个词的出现次数和出现位置所在的行的行号，格式自行设计。待统计的“单词”在文本串中不跨行出现，它或者从行首开始，或者前置以一个空格符。
模式匹配要基于KMP算法。
推广到更一般的模式集匹配问题，并设待查模式串可以跨行（提示：定义操作GetAChar）。
【测试数据】
文本文件为testword.c
待统计的词集：if、else、for、while、return、void、int、char、typedef、struct
三、进度安排
1．初步设计：写出初步设计思路，进行修改完善，并进行初步设计。
2．详细设计：根据确定的设计思想，进一步完善初步设计内容，按要求编写出数据结构类型定义、各算法程序、主函数。编译分析调试错误。
3．测试分析：设计几组数据进行测试分析，查找存在的设计缺陷，完善程序。
4．报告撰写：根据上面设计过程和结果，按照要求写出设计报告。
5．答辩考核验收：教师按组（人）检查验收，并提出相关问题，以便检验设计完成情况。
四、基本要求
1．在设计时，要严格按照题意要求独立进行设计，不能随意更改。若确因条件所限，必须要改变课题要求时，应在征得指导教师同意的前提下进行。
2．在设计完成后，应当场运行和答辩，由指导教师验收，只有在验收合格后才能算设计部分的结束。
3．设计结束后要写出课程设计报告，以作为整个课程设计评分的书面依据和存档材料。设计报告以规定格式的电子文档书写、打印并装订，报告格式严格按照模板要求撰写，排版及图、表要清楚、工整。
从总体来说，所设计的程序应该全部符合要求，问题模型、求解算法以及存储结构清晰；具有友好、清晰的界面；设计要包括所需要的辅助程序，如必要的数据输入、输出、显示和错误检测功能；操作使用要简便；程序的整体结构及局部结构要合理；设计报告要符合规范。
课程负责人签名：
年 月 日
题目
选题四：文学研究助手与模式匹配算法KMP
摘 要
本实践课题重在对文本的查询，在实际应用中有重大作用。通过本程序，可统计所需文本的一个或多个词汇在文本中出现的次数与位置，其作用在于给使用者研究一篇文学著作时提供帮助。当研究一片文学著作时，不紧要理解著作的内容和寓意，有是更需要分析作者的写作手法和习惯，这是统计著作中词汇的出现次数与位置成了文学研究的重点课题。本程序就可以为文学研究者提供这类帮助。本程序基于模式匹配算法KMP实现，为普通模式匹配的改进，，优点在与时间复杂度由原来的O（n*m）变为O（n+m）,即是说统计时间大大缩短。当要统计的词汇量很大时，计算机统计所需时间将很漫长，如果使用者急需使用统计结果，这是又因为统计太慢导致研究受阻，这样就得不偿失了。而本程序将大大改善这种状况，让计算机在短时间内统计出使用者想要的统计结果。本程序虽然精简，但是对模式匹配算法KMP的使用极其灵活，需开发者深刻理解模式匹配算法KMP，思路清晰，灵活调用模式匹配算法KMP的函数，否则开发者将极难开发成功。
关键词：文学研究 模式匹配 KMP
目 录
摘 要 6
关键词 6
1 课程设计相关 8
1.1题目要求 8
1.1.1实验所在地点 8
2 课程设计实施 9
2.1设计思路 9
2.1.1课程设计时间分配 9
2.2源程序代码实现 10
2.3 程序调试演示与分析 12
参考文献 15
心得体会 16
教师评语 17
计算机学院课程设计答辩记录表 18
1 课程设计相关
1.1题目要求
【问题描述】
文学研究人员需要统计某篇英文小说中某些形容词的出现次数和位置。试写一个实现这一目标的文字统计系统
【任务要求】
1) 英文小说存于一个文本文件中。待统计的词汇集合要一次输入完毕，即统计工作必须在程序的一次运行之后就全部完成。程序的输出结果是每个词的出现次数和出现位置所在的行的行号，格式自行设计。待统计的“单词”在文本串中不跨行出现，它或者从行首开始，或者前置以一个空格符。
2) 模式匹配要基于KMP算法。
3) 推广到更一般的模式集匹配问题，并设待查模式串可以跨行（提示：定义操作GetAChar）。
【测试数据】
1) 文本文件为testword.c
2) 待统计的词集：if、else、for、while、return、void、int、char、typedef、struct
【成绩评定】
1) 完成“任务要求”第1项成绩评定为“及格”-“中”。
2) 完成“任务要求”第2项至第3项成绩评定为“良”及以上。
1.1.1实验所在地点
本实验实行所在地点于学校教学楼多媒体实验室JB405，如图1-1
北理工珠海学院
教学楼
机车楼
化工楼
多媒体实验室
网络实验室
无机化学
图1-1 学校设施组织结构图
2 课程设计实施
2.1设计思路
本实践重在对模式匹配算法KMP的调用。KMP算法在数据结构（C语言版）中的第82页有详细解释，在此不予以解释。我的大概思路是：
1．打开文件
2．输入想要匹配的一组字符串
3．读取文件的一行
4．把每一个字符串在该行中实行模式匹配KMP
5．重复步骤3和4
6．输出结果
2.1.1课程设计时间分配
本课程时间分为4天，16个课时，设计工作时间分配由学生自行分配。我的课程设计工作分配时间表如表2-1。
表2-1
详情
分工
时间
备注
思路梳理与理论了解
第一天
可实行部分编程
编程实现
第二天
注意写备注
程序检验与改善
第三天
准备写说明书
程序设计说明书整理
第四天
打印，答辩
开发一个软件，就算再小，时间分配上也是很重要的。在第一天，我将了解模式匹配算法KMP的设计思路，再梳理出我设计本程序的大概思路。当思路梳理得差不多的时候就可以开始编程，第一天的编程还是以编写程序框架为主，先要把思路的框架写出来，为第二天的编程实现作准备。第二天开始正式变成实现，在第一天编写出的程序框架的基础上，填写程序的实际内容。由于第一天已编写出大概框架，因此实际编程事半工倍。第三天实行程序的检验与改善。第二天编写出来的程序已能够实现所需功能，但程序的格式还比较乱，也没有对读取出错进行处理。在这一天里，将对程序进行检验与改善，令程序更完美。在闲暇之余，还可以适当为课程设计说明书作准备，写出说明书模版以及完成部分内容。第四天对课程设计说明书进行进一部的整理和完成，并在答辩之前把说明书打印出来。
2.2源程序代码实现
#include
#include
#define MAXSTRLEN 255 //最大串长
typedef char SString[MAXSTRLEN+1]; //串的定长顺序存储表示
int next[MAXSTRLEN]; //KMP算法中用到的next
int Index(SString S,SString T,int pos) //KMP算法,P82
{
int i=pos,j=1;
while(i<=S[0]&&j<=T[0])
{
if(j==0||S[i]==T[j]) {++i;++j;}
else
j=next[j];
}
if (j>T[0]) return (i-T[0]);
else
return 0;
}
int lenth(SString str) //求串长
{
int i=1;
while(str[i]) i++;
return(i-1);
}
void find(char name[],SString keys) //查找函数
{
SString text; //用于存放从小说文件读取的一行字符串
int i=1,j=0,k,q=0; //i用于存放行号，j用于存放列号,k用于输出格式的控制,q用于统计出现次数
FILE *fp;
if (!(fp=(fopen(name,"r")))) //打开小说文件
{
printf("打开文件出错!\n");
exit(0);
}
keys[0]=lenth(keys); //求关键字的长度
printf("\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算法，统计关键字在该行出现的位置，若匹配不成功则返回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 (k) printf("\n"); //输出格式控制
}
printf("%s出现%d次。\n",&keys[1],q); //打印关键字出现次数
}
void main()
{
char name[50]; //存储输入的小说路径字符串
SString words[10]; //定义字符串数组，用于存储输入的关键字
int m,n,i;
printf("-----------------------------欢迎使用文学研究助手-------------------------------"); //打印标题
while(1) //不停循环，直至完成查询或者退出服务
{
printf("是否需要为你服务：需要输入1，不需要输入0。\n"); //询问是否需要服务
scanf("%d",&m); //输入判断是否需要服务
if(m==1) //需要服务时执行
{
printf("输入你想查询的文档名字:\n");
scanf("%s",name); //输入文件名
printf("输入查询字符串的个数：\n");
scanf("%d",&n); //输入查询字符串个数
printf("输入你要查询的字符串:\n");
for (i=0;i
展开阅读全文
相关搜索