文学研究助手数据结构报告.docVIP

PAGE

PAGE4

学号

武汉理工大学华夏学院

课程设计

课程名称数据结构

题目文学研究助手

专业

班级

姓名________

成绩____________________

年月日

文学研究助手

设计目的

（1）使学生进一步理解和掌握课堂上所学各种基本抽象数据类型的逻辑结构、存储结构和操作实现算法，以及它们在程序中的使用方法。

（2）使学生掌握数据库设计的基本内容和设计方法，并培养学生进行规范化软件设计的能力。

（3）使学生学会使用各种计算机资料和有关参考资料，提高学生进行程序设计的基本能力。

问题描述

文学研究人员需要统计某篇英文小说中某些形容词的出现次数和位置。试写一个实现这一目标的文字统计系统，称为“文学研究助手”。

基本要求

英文小说存于一个文本文件中。待统计的词汇集合要一次输入完毕，即统计工作必须在程序的一次运行之后就全部完成。程序的输出结果是每个词的出现次数和出现位置所在行的行号，格式自行设计。

算法思想

本次课程设计使用的是串模式匹配的KMP算法，模式匹配算法KMP为普通模式匹配的改进，优点在与时间复杂度由原来的O（n*m）变为O（n+m）,即是说统计时间大大缩短。当要统计的词汇量很大时，计算机统计所需时间将很漫长，如果使用者急需使用统计结果，这是又因为统计太慢导致研究受阻，这样就得不偿失了。而本程序将大大改善这种状况，让计算机在短时间内统计出使用者想要的统计结果。本程序虽然精简，但是对模式匹配算法KMP的使用极其灵活，需灵活调用模式匹配算法KMP的函数来快速解决问题。该算法的核心思想是：每当一趟匹配过程中出现字符比较不等时，不需要回测指针，而是利用已经

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); //打印关键字出现次数

}

voidmain()

{

charname[50];//存储输入的小说路径字符串

SStringwords[10];//定义字符串数组，用于存储输入的关键字

intm,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;in;i++)

scanf(%s,words[i][1]);//用户一次性输入要查找的关键字，words[i][0]用于存放字符串的长度

for(i=0;in;i++)

find(name,words[i]);//对于每一个关键字，调用查找函数进行查找统计

break;

}

elseif(m==0) //不需要服务时执行

break;

else

printf(输入错误!\n\n); //输入不合规范时执行

}

system(pause);

}

程序测试

将所设计的程序输入c++软件，经组建编译后结果如下：

程序能正常编译，说明程序没