数据结构实验报告(文学研究助手)
班级:软件一班
学号:200705070106
姓名:孙俊杰
完成日期:2008-12-2
一、 需求分析:
1. 文本串非空且以文件形式存放,统计匹配的词集非空。词集由用户重键盘输入;
2. “单词”定义:有字母构成的字符序列,中间不含空格符且区分大小写;
3. 待统计的“单词”在文本串中不跨行出现,它或者重行首开始,或者前置一个空格符;
4. 在计算机终端输出的结果是:单词、出现的行号、出现次数,同一行出现两次只输出一
个行号。
5. 测试数据:文本文件以本次实习中的 AWORD.C;待统计的词集:
if
else while
return
int
二、 概要设计:
1.ADT Aword{
数据对象:D={ai|ai∈字母字符集,i=1,2,…,n}
数据关系:R1={
| ai-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(){
输入信息初始化;
统计文件中每个单词出现的位置和次数;
输出测试结果;
}
三、 详细设计:
#include
#include
#include
#include
#include
#include
#include
using namespace std;
vector
cishu;//建立存放次数的动态数组
vector::iterator itercs;//指向数组的指针
vectorlines;//存放行数的数组
vector::iterator iterlines;//指针
vectorword;//需要匹配的单词的数组
vector::iterator iterwd;//指针
int next[100];
void get_next(char *T)
{//next 函数
int i=1;next[1]=0;int j=0;
while(istrlen(T)) return i-strlen(T);
else return 0;
}
void compare(char *m,int k)
{//将文件内容进行匹配
line=0,length,i,times;
fstream file;
get_next(m);
char tmp[100];
int
file.open("d:\\sun.txt");
if(!(file.is_open())) cout<<"file can not be open"<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&&*iterlin
es!=10000){
cout<<"出现在第"<<*iterlines<<"行"<<*itercs<<"次"<>temp;
if(temp=="end") break;
word.push_back(temp);
strcpy(temp1,temp.c_str());
compare(temp1,k);
k++;
}
output();
system("PAUSE");
return 0;
}
四、 调试分析:
1. 由于开始对建立动态数组函数 vector 的了解不够深入导致类型定义出现错误,赋值也
出现错误。
2. 在输出时由于循环条件考虑不周全导致出现死循环,因此将 10000 付给数组作为结束条
件。
3. 由于开始对输出函数的外重循环考虑不清楚导致只能识别第一输入的单词,因此加入了
一个 if 语句。
五、 测试结果: