哈希表之单词查找
- 英文文章，写入一个文本文档，作为基础测试数据。 建立一个待查关键字文件，存储待查询的单词。
- 输入查询的单词，输出该单词的出现次数，及每个出现位置的上下文（前一句，单词/短语所在的句子，下一句）。
- 目前只支持查询一个单词。
以下为代码：
#include <iostream>
#include <string.h>
#include<vector>
#include <map>
#include <set>
#include<sstream>
#include <fstream>
#include <windows.h>
const int HASHNUM = 29989;
typedef struct Hashtable{ //哈希表结构体
char *word;
int count;
struct Hashtable * next;
}Hashnode;
Hashnode* hashtable[HASHNUM]; //HASHNUMBER大小的指针数组(储存指针的数组) 作为hash表
std::vector<std::string>lines;
std::map<std::string,std::set<int>> wordline; //需要使用到迭代器匹配行号所以使用map嵌套set
unsigned int Hashfuntion(const char *str);
void Hashinsert(char *str);
void readintohash(char *path);
void findquery(char *path);
void getlinecplusplus(char *path,char *str);
void readintohash(char *path){
char ch[1024] = {NULL}; //存储一行字符串
char *p;
FILE *fp = fopen(path,"r");
if(fp == NULL)
exit(-1);
while(( fgets(ch,sizeof (ch),fp) != NULL )) //读取到换行符时，或者到达文件末尾时停止
{
if(strcmp( " " , ch ) == 0) //空行继续
continue;
const char *ch1 = ", \n\t."; //要分割的字符(逗号、空格、换行、制表符、句号)
p = strtok(ch,ch1); //用strtok函数从一行字符串中分离出每个单词，分隔符设置为(空格、逗号、换行、制表符)
while(p != NULL)
{
Hashinsert(p);
p = strtok(NULL, ch1); //每次找到一个分隔符后，一个空（NULL）就被放到分隔符处，strtok函数用这种方法来连续查找该字符串，此处的NULL是一个指向后面还未分割的单词的指针，因此，首次调用时，第一个元素必须指向要分解的字符串，随后调用要把元素设成NULL。
}
}
fclose(fp);
}
void Hashinsert(char *str){
int hashcode = Hashfuntion(str);
Hashnode *newnode;
for (newnode = hashtable[hashcode]; newnode != NULL ; ++newnode) {
if(strcmp(str, newnode->word) == 0){ //查找单词是否已经在hash表中了
(newnode->count)++;
return;
}
}
//如果上面没返回，也就是说hash表中没有这个单词，添加新节点，加入这个单词
newnode = new Hashnode;
newnode->count = 1;
newnode->word = (char *)malloc(strlen(str) + 1);
strcpy(newnode->word,str);
newnode->next = hashtable[hashcode]; //将新生成的节点插入到hashcode为下标的链表中去
hashtable[hashcode] = newnode;
}
unsigned int Hashfuntion(const char *str)
{
unsigned int index = 0;
for (; *str != '\0' ; str++) {
index = index * 31 + *str;
}
return index % HASHNUM;
}
void findquery(char *path){
char ch[50] = {NULL};
FILE *fp = fopen(path,"r");
std::ofstream outfile1("E:\\answer.txt");
while(fgets(ch,sizeof (ch),fp)){ //把待查关键字读入
int hashcode2 = Hashfuntion(ch);
outfile1 << hashtable[hashcode2]->word << "出现了" << hashtable[hashcode2]->count << "次" << std::endl;
}
getlinecplusplus("E:\\database.txt",ch);
fclose(fp);
}
void getlinecplusplus(char *path,char *str){
std::ifstream readfile(path); //用ifstream读入txt文件path并与readfile相连
std::ofstream outfile("E:\\answer.txt",std::ofstream::app); //用ofstream将答案输出到answer.txt
int linecount = 0;
std::string line;
std::string word;
while(std::getline(readfile, line)){
lines.push_back(line); //将一行放入vector<string>中
std::istringstream iss(line); //获取一行
++linecount; //行号加1
while(iss >> word){
wordline[word].insert(linecount); //加入词的行号
}
}
std::set<int>::const_iterator itset;
std::vector<std::string>::const_iterator itvector; //新建两个迭代器
int i;
for(itset = (wordline.find(str)->second).begin();itset != (wordline.find(str)->second).end(); itset++)
{
outfile << "出现在第 "<< *itset <<"行" << std::endl;
i = 0;
for (itvector = lines.begin(); itvector != lines.end(); itvector++) { //前一句，单词所在的句子，下一句
if (*itset == ++i) //行号与vector循环次数匹配上了
{
if(itvector != lines.begin()){ //第一句不能打印前一句
outfile << *(itvector-1) << std::endl;
}
if(itvector != lines.end()-1){ //最后一句不能打印后一句
outfile << *(itvector+1) << std::endl;
}
outfile << *itvector << std::endl; //单词本身句
}
}
}
outfile.close();
}
int main(){
SetConsoleOutputCP(65001); //避免控制台中文乱码
readintohash("E:\\database.txt"); //自行更改路径
findquery("E:\\query.txt");
return 0;
}