安徽省巢湖学院计算机与信息工程学院
课程设计报告
课程名称《数据结构》
课题名称文学研究助手的实现
专业计算机科学与技术
班级 10计本2班
学号10012094
姓名韦玉坤
联系方式187********
指导教师蔡敏
20 11 年月日
目录
1、数据结构课程设计任务书.............................................................................................. １
1.1、题目..................................................................................................................... １
1.2、要求..................................................................................................................... １
2、总体设计....................................................................................................................... １
2.1、功能模块设计 ...................................................................................................... １
2.2、所有功能模块的流程图........................................................................................ １
3、详细设计....................................................................................................................... １
3.1、程序中所采用的数据结构及存储结构的说明........................................................ １
3.2、算法的设计思想................................................................................................... ２
3.3、稀疏矩阵各种运算的性质变换 .................................................错误！未定义书签。
4、调试与测试：................................................................................................................ ２
4.1、调试方法与步骤： ............................................................................................... ２
4.2、测试结果的分析与讨论： .................................................................................... ３
4.3、测试过程中遇到的主要问题及采取的解决措施：................................................. ３
5、时间复杂度的分析：..................................................................................................... ３
6、源程序清单和执行结果 ................................................................................................. ３
7、C程序设计总结 ............................................................................................................ ３
8、致谢.............................................................................................................................. ６
9、参考文献....................................................................................................................... ６
1、数据结构课程设计任务书
1.1、题目
文学研究助手的实现
1.2【设计要求】英文小说存于一个文本文件中。待统计的词汇集合要一次输入完毕。程序的输出结果是每个词的出现次数和出现位置所在行的行号,格式自行设计。
2、总体设计
2.1、功能模块设计
根据课程设计题目的功能要求，各个功能模块的组成框图如下：
输入矩阵1
2.2、所有功能模块的流程图
略
3、详细设计
1.ADT Aword{
数据对象：D={ai|a i∈字母字符集，i=1，2，…，n}
数据关系:R1={| a i-1,,ai∈D，i=2，3，…，n}
基本操作：
void get_next(char *T)
初始条件：T存在。
操作结果：求出T的next函数将结果存在next数组中。
int index_KMP(char *s,char *T,int pos)
操作结果：利用模式串T的next函数球T在主串S中第pos个字符之后的位置。
void compare(char *m,int k)
操作条件：文件存在。
操作结果：利用KMP算法将模式串m与文件内容匹配。
void output()
输出函数。
}
2.void main(){
输入信息初始化；
统计文件中每个单词出现的位置和次数；
输出测试结果；
}
3.1、程序中所采用的数据结构及存储结构的说明
英文小说存于一个文本文件中。待统计的词汇集合要一次输入完毕，即统计工作必须
在程序的一次运行之后就会全部完成。程序的输出结果是每个词出现次数和出现位置所在行的行号，格式自行设计。匹配时采用KMP算法。
实现提示：
设小说中的词汇一律不跨行。这样，每读入一行，就统计每个词在这行中出现的次数。出现位置所在行的行号可以用链表存储。若某行中出现了不止一次，不必存多个相同的行
号。
Input
输入第一行为小说的文件名（包含路径的文本文件名）；第二行为一个正整数n，表示要查找单词的个数（n<10）；从第三行开始共有n行，每行包括一个单词。
Output
输出共有n块，每块中第一行为查找的单词，从第二行开始为找到的各行的行号和列号，每个行号和列号占一行，若在同一行上出现多次，则只输出一个行号和多个列号并占一行，输出顺序按行号从小到大顺序排列。若没有找到则块内只输出第一行的单词即可。
3.2、算法的设计思想
略
4、调试与测试：
4.1、调试方法与步骤：
略
4.2、测试结果的分析与讨论：
4.3、测试过程中遇到的主要问题及采取的解决措施：
略
5、时间复杂度的分析：
略
6、源程序清单和执行结果
#include
#include
#include
#include
#include
#include
#include
using namespace std;
vector
vector
vector
vector
vector
vector
int next[100];
void get_next(char *T)
{//next函数
int i=1;next[1]=0;int j=0;
while(i if(j==0||T[i]==T[j]){++i;++j;next[i]=j;} else j=next[j]; } int index_KMP(char *s,char *T,int pos){//KMP匹配函数int i=pos,j=1; while(i<=strlen(s)&&j<=strlen(T)){ if(j==0||s[i]==T[j-1]){++i;++j;} else j=next[j]; } if(j>strlen(T)) return i-strlen(T); else return 0; } void compare(char *m,int k) {//将文件内容进行匹配 fstream file; get_next(m); char tmp[100]; int line=0,length,i,times; file.open("d:\\sun.txt"); if(!(file.is_open())) cout<<"file can not be open"< while(!(file.eof())) { line++; file.getline(tmp,100,'\n'); i=0,times=0; length=strlen(tmp); while(i<=length) { if(i i=index_KMP(tmp,m,i), times++; i++; } if(times!=0) { cishu.push_back(times); lines.push_back(line); } } cishu.push_back(10000); lines.push_back(10000); file.clear(); file.seekg(0,ios_base::beg); } void output() {//输出行数和所在次数 itercs=cishu.begin(); iterlines=lines.begin(); iterwd=word.begin(); while(iterwd!=word.end()) { cout<<*iterwd; iterwd++; while(itercs!=cishu.end()&&iterlines!=lines.end()&&*itercs!=10000&&*iterlines!=10000){ cout<<"出现在第"<<*iterlines<<"行"<<*itercs<<"次"< itercs++;iterlines++; } if(*itercs==10000&&*iterlines==10000) {itercs++;iterlines++;} } } int main() { string temp="NONE"; size_t max = 10; iterwd=word.begin(); char temp1[100]; int k=0; cout<<"输入你需要匹配的单词"< while(temp!="end") { cin>>temp; if(temp=="end") break; word.push_back(temp); strcpy(temp1,temp.c_str()); compare(temp1,k); k++; } output(); system("PAUSE"); return 0; } 7、C程序设计总结 本程序在刚开始调试时有许多错误，但在我的努力及同学的帮助下都被一一克服，现在 在操作本程序时可根据提示进行相关操作，能正确输出结果。在刚开始的几次调试中曾 经出现过不能运行、不能产生十以内随机数字、不能随机出现加减、不会正确输出结果、 不能进行循环练习等等问题。经过我的努力及同学的帮助，这些问题得到克服，并且使 程序的功能也得到了一定的完善。现在它能对出错的题目发出报警声，并且给出正确答 案。最后还能分别输出对错的题数及所得分数。 在这次设计过程中，不仅复习课本上所学知识，还通过查资料、问同学学到了课本上没有的知识。从而启发我，要想写好程序，在写好课本知识的同时还需要多读和专业有关的一些书籍，同时还需要多动脑子，尽量把所学的知识综合起来应用，力争写出完美的程序。除此之外，我还得到了一些有用的教训：写程序时必须要细心，不能输错一个字符标点，就连全角半角也得注意。在修改时要有耐心，编译出错后必须逐个错误去改正，绝不能心急浮躁，否则修改之后还会有新的错误。 8、致谢 能够完成这次课程设计必须感谢C语言课程老师蔡敏、陶正华同学（她帮我修改了几处重要错误，同时启发我完善了该程序的功能）。 9、参考文献 [1] 贾宗璞、许合利，C语言程序设计，江苏：中国矿业大学出版社，2007.6 [2] 谭浩强，C程序设计（第二版），北京：清华大学出版社，2001.1 [3] https://www.doczj.com/doc/2f17892627.html,
相关主题
文本预览