文学研究助手
2018年12月1日
文学研究助手
【问题描述】
统计一篇英文小说中某些形容词出现的次数。
【基本要求】
英文小说存在一篇txt文档中，统计工作一次进行完毕，需要统计的词一次性输入完毕。
【测试数据】
自行设计
【实现提示】
文件名，输入的单向都由
string
储存，因为输入带空行，所以用
getline
函数读入，一次读一行，具体实现方法为字典树，可以理解为弱化的AC自动机，因为不需要其中的fail指针，首先将输入的单词一个个分离出来然后构造一棵字典树，遍历英文小说，每个词放在字典树里面匹配一下，匹配成功就将最后一个字母的数字加一。
【问题分析】
字典树的每个节点为
struct node{
node *next[26];
int count;
node(){
count = 0;
memset(next,NULL,sizeof(next));
}
};
其中
*next[26]
是节点的子节点，构造的时候默认设置成NULL。
创建字典树的函数为
void insert(char* str,node *root){
int i = 0,index;
node *p = root;
while(str[i] != '\0'){
index = str[i] - 'a';
if(p->next[index] == NULL)p->next[index] = new node();
p = p->next[index];
i++;
}
}
root
是根节点，根节点不包含任何字母，
i
是传入的字符串的下标，对传入的字符串遍历一下，对于某个节点下一个，如果字符串对应的下一个字母节点为空的话，那么就c创建一个新的节点。否者，直接将指针指向对应的下一个节点。
对应的主函数里面的部分为
string input;
node *root = new node();
map<char*,int> my_word;
char *cstr = new char[input.length()+1];
strcpy(cstr,input.c_str());
char* token = strtok(cstr," ");
while(token != NULL){
my_word.insert(pair<char*,int>(token,0));
insert(token,root);
token = strtok(NULL," ");
}
这里需要用到一个
strtok
函数。用来将每个单词分离出来。其中
my_word
用来方便后面的遍历，输出。
读入小说的部分为
void read_file(string file_name,node* root){
ifstream istr{file_name,ios::binary | ios::ate};
if(!istr.is_open()){
cout<<"Failed to open "<<file_name<<endl;
}else{
auto size = istr.tellg();
string file(size,'\0');
istr.seekg(0);//这儿是回溯
istr.read(&file[0],size);//将文件读入string中
char *cstr = new char[file.length()+1];
strcpy(cstr,file.c_str());
char *token = strtok(cstr," ");
while(token != NULL){
my_compare(token,root);//这个函数用来计数
token = strtok(NULL," ");
}
}
}
void my_compare(char* str,node *root){
node *p = root;
int index,i = 0;
while(str[i] != '\0'){
index = str[i] - 'a';
if(p->next[index] == NULL)return;
else p = p->next[index];
i++;
}
p->count+=1;
}
用来计数的
my_compare
函数具体是遍历，然后每个对比，只有字符串在字典树里面有才会走到字典树的最后节点，并将最后节点的计数数值加一，只要其中一个不一样，就会直接结束比较。
随后主函数里面的遍历输出为
for(map<char*,int>::iterator it = my_word.begin();it != my_word.end();it++){
it->second = find(it->first,root);
cout<<"The total number of "<<it->first<<" is "<<it->second<<endl;
}
最后附上全部代码
#include <iostream>
#include <string.h>
#include <cstdlib>
#include <fstream>
#include <map>
using namespace std;
struct node{
node *next[26];
int count;
node(){
count = 0;
memset(next,NULL,sizeof(next));
}
};
void insert(char* str,node *root){
int i = 0,index;
node *p = root;
while(str[i] != '\0'){
index = str[i] - 'a';
if(p->next[index] == NULL)p->next[index] = new node();
p = p->next[index];
i++;
}
}
void my_compare(char* str,node *root){
node *p = root;
int index,i = 0;
while(str[i] != '\0'){
index = str[i] - 'a';
if(p->next[index] == NULL)return;
else p = p->next[index];
i++;
}
p->count+=1;
}
int find(char* str,node *root){
node *p = root;
int index,i = 0;
while(str[i] != '\0'){
index = str[i] - 'a';
p = p->next[index];
i++;
}
return p->count;
}
void read_file(string file_name,node* root){
ifstream istr{file_name,ios::binary | ios::ate};
if(!istr.is_open()){
cout<<"Failed to open "<<file_name<<endl;
}else{
auto size = istr.tellg();
string file(size,'\0');
istr.seekg(0);
istr.read(&file[0],size);
char *cstr = new char[file.length()+1];
strcpy(cstr,file.c_str());
char *token = strtok(cstr," ");
while(token != NULL){
my_compare(token,root);
token = strtok(NULL," ");
}
}
}
int main(){
string input;
string filename;
map<char*,int> my_word;
node *root = new node();
cout<<"Please in put your file name"<<endl;
getline(cin,filename);
cout<<"input your key words"<<endl;
getline(cin,input);
char *cstr = new char[input.length()+1];
strcpy(cstr,input.c_str());
char* token = strtok(cstr," ");
while(token != NULL){
my_word.insert(pair<char*,int>(token,0));
insert(token,root);
token = strtok(NULL," ");
}
read_file(filename,root);
for(map<char*,int>::iterator it = my_word.begin();it != my_word.end();it++){
it->second = find(it->first,root);
cout<<"The total number of "<<it->first<<" is "<<it->second<<endl;
}
}