武汉理工大学《数据结构》课程设计报告书
学 号: 0120910340528
课 程 设 计
题 目 文学研究助手
学 院 计算机科学与技术学院
专 业 计算机科学与技术专业
班 级 计算机 sy0901 班
姓 名 陈艳恩
指导教师 刘春老师
2011 年 7 月 1 日
武汉理工大学《数据结构》课程设计报告书
课程设计任务书
学生姓名: 陈艳恩
专业班级: 计算机 sy0901 班
指导教师: 刘春老师
工作单位: 计算机科学系
题 目: 文学研究助手
初始条件:
文学研究人员需要统计某篇英文小说中某些形容词的出现次数和位置。试写一个实现
这一目标的文字统计系统,称为“文学研究助手”。
英文小说存于一个文本文件中。待统计的词汇集合要一次输入完毕,即统计工作必须
在程序的一次运行之后就全部完成。程序的输出结果是每个词的出现次数和出现位置所在
行的行号,格式自行设计。
测试用例见题集 p116。
要求完成的主要任务: (包括课程设计工作量及其技术要求,以及说明书撰写
等具体要求)
课程设计报告按学校规定格式用 A4 纸打印(书写),并应包含如下内容:
1、 问题描述
简述题目要解决的问题是什么。
2、 设计
存储结构设计、主要算法设计(用类 C 语言或用框图描述)、测试用例设计;
3、 调试报告
调试过程中遇到的问题是如何解决的;对设计和编码的讨论和分析。
4、 经验和体会(包括对算法改进的设想)
5、 附源程序清单和运行结果。源程序要加注释。如果题目规定了测试数据,则运行
结果要包含这些测试数据和运行输出,
6、 设计报告、程序不得相互抄袭和拷贝;若有雷同,则所有雷同者成绩均为 0 分。
时间安排:
1、第 20 周(6 月 29 日至 7 月 3 日)完成。
2、7 月 3 日 8:00 到计算中心检查程序、交课程设计报告、源程序(CD 盘)。
指导教师签名:
年
月 日
系主任(或责任教师)签名:
年
月 日
1
武汉理工大学《数据结构》课程设计报告书
目录
1.问题描述:....................................................................3
2. 需求分析:..................................................................3
3. 概要设计:..................................................................3
3.1 模块设计:.......................................................4
4. 详细设计....................................................................4
4.1 主程序用到的宏定义:.......................................4
4.2 存储结构设计.....................................................4
4.3 主要算法设计:...................................................4
4.3.1 求所检索文档的串长....................................4
4.3.2 求 next 值...................................................... 5
4.3.3 KMP 算法................................................... 5
4.3.4 查找函数..................................................... 6
5. 调试报告:................................................................7
6. 经验体会:..................................................................8
7. 测试结果:................................................................8
8. 附录:........................................................................9
2
武汉理工大学《数据结构》课程设计报告书
文学研究助手课程设计
1.问题描述:
文学研究人员需要统计某篇英文小说中某些形容词的出现次数和位置。试写
一个实现这一目标的文字统计系统,称为“文学研究助手”。
英文小说存于一个文本文件中。待统计的词汇集合要一次输入完毕,即统计
工作必须在程序的一次运行之后就全部完成。程序的输出结果是每个词的出现次
数和出现位置所在行的行号,格式自行设计。
2. 需求分析:
1、文本串非空且以文件形式存放,统计匹配的词集非空。文件名和词集均由用
户从键盘输入;
2、“单词”定义:由字母构成的字符序列,中间不含空格字符且区分大小写;
3、待统计的“单词”在文本串中不跨行出现,它或者从行首开始,或者前置若干
空格字符;
4、在计算机终端输出的结果是:单词,出现的次数,出现的位置所在行的行号,
同一行出现两次的只输出一个号行;
5、测试数据:将实验的源程序作为测试文件,从中任意选取“单词”作为测试的
词集。
3. 概要设计:
采用 KMP 算法来完成“单词匹配比较”,从而统计出其出现的位置和次数。
3
武汉理工大学《数据结构》课程设计报告书
3.1 模块设计:
3.1.1 主程序模块:主函数设计如下
int main ( ) {
登陆界面和使用提示;
调用查找函数,统计单词,并输出结果;
3.1.2 模式匹配模块------实现文本字符串和键盘字符串的匹配统计;
3.1.3 构造查找函数-------对结果进行统计;
4. 详细设计
4.1 主程序用到的宏定义:
#define MAXSTRLENGTH 255
4.2 存储结构设计
typedef char SString[MAXSTRLENGTH+1]; 将字符串用定长顺序表示
4.3 主要算法设计:
4.3.1 求所检索文档的串长
//求所检索文档的串长
int length(SString string)
{
int i=1;
while(string[i]) i++;
4
武汉理工大学《数据结构》课程设计报告书
return(i-1);
}
4.3.2 求 next 值
void next(SString T,int next[])
{
int i=1,k=0;thenext[1]=0;
while(iT[0]) return
else
return 0;
i-T[0] ;
5
武汉理工大学《数据结构》课程设计报告书
}//KMP 算法
4.3.4 查找函数
void find(char name[],SString keys) //程序查找函数, 要查找的关键字,从所输入
的文件中文件中逐行查找
{ FILE *fp;
int i=1,j=0,m=0,k;
式的控制
//i 放行号,j 放列号,m 放关键字出现的次数,k 用于输出格
SString novelrow; //存放文件中的一行字符串
if (!(fp=(fopen(name,"r")))) //打开所要检测的文件
{
printf("所输入文文件路径错误!\n");
exit(0);
}
keys[0]=length(keys);
next(keys,thenext);
printf("关键字%s 出现在:\n",&keys[1]);
while (!feof(fp))
{
//如果还没到文件末尾
//关键字之长
//关键字每个字符对应的 next
//打印关键字
k=0;
fgets(&novelrow[1],MAXSTRLENGTH,fp);
字符串,存入 text 串中
//从文件中文件中读取一行
novelrow[0]=length(novelrow);
j=IndexKMP(novelrow,keys,j+1);
//求读入的串的长度
//调用 KMP 算法,统计关键字在该
行出现的位置,若匹配不成功则返回 0
if (j!=0)
6
武汉理工大学《数据结构》课程设计报告书
{
printf("row=%d",i);
k++;m++;
//若检索到关键字则打印行号
}
while(j!=0)
//若该行找到了关键字,则继续寻找看是否还能匹配成
功
{
j=IndexKMP(novelrow,keys,j+1); //调用 KMP 算法从刚找到的列号后一字符
起匹配
if (j!=0)
{m++;} //若匹配成功,则打印列号
}
i++; //行号加 1,在下一行中寻找
if (k) printf("\n"); //输出格式控制
}printf("该关键字在这篇文档中共出现%d 次\n",m);
}
5. 调试报告:
1、程序在设计过程中主要遇到了如下几个主要的问题:
。
1)在统计出现次数的时候,其值放的位置不对,导致输出时关键词出现的
次数不正确。具体改进是把 m 的自加运算换一层循环。
2)在计算串长的时候,i 的起始值不对,造成整个程序出现意想不到的结果。
7