利用哈希函数进行高效的key word的检索
内容：
提供一篇英语文章，，搜索在该文章中存在某一单词的所有句子
代码如下：
头文件“prepare.h”——进行程序的准备阶段
#include <iostream>#include <string>using namespace std;const int tablesize = 100000;int line_num = 0;int word_num = 0;string sentence[10000];struct Node{string data;int line;Node *next;Node(){line = 0;data = "";next = NULL;}};
头文件“Hash_table.h”——哈希类的申明与实现
#include "prepare.h"class Hash_table{public:Hash_table();~Hash_table();int hash(string key);void build(string entry, int line);int find(string targrt);private:Node *array;};Hash_table::Hash_table(){array = new Node[tablesize];}Hash_table::~Hash_table(){delete array;array = NULL;}int Hash_table::hash(string key){unsigned long hashval = 0;int end = key.size();for (int i = 0; i < end; i++)hashval = 127 * hashval + key[i];return hashval%tablesize;}void Hash_table::build(string entry, int line){int position = hash(entry);Node *new_one;new_one = new Node();new_one->data = entry;new_one->line = line;new_one->next = array[position].next;array[position].next = new_one;}int Hash_table::find(string target){int position = hash(target);int found = 0, total = 0;int line = 0;Node *check = array[position].next;while (check != NULL && total <= word_num + 1){total++;if (check->data == target){if (line != check->line){found = 1;line = check->line;cout << sentence[line] << endl;}}check = check->next;}return found;}
头文件“read_and_store.h”——进行数据的读写过程
#include "Hash_table.h"#include <fstream>//逐词读入Hash_table essay;void read(){ifstream fin("text.txt");//The essay you wantstring s;int count = 0;while (fin >> s){string tem;word_num++;int num = s.size();if (s[num – 1] == '.'){sentence[count + 1] += (s + '\n');for (int i = 0; i < num – 1; i++)tem += s[i];essay.build(tem, count + 1);count++;line_num++;}else{if ((s[num – 1] <= 'z' && s[num – 1] >= 'a') || (s[num – 1] <= 'Z' && s[num – 1] >= 'A'))tem = s;else{for (int i = 0; i < num – 1; i++)tem += s[i];}//cout<< tem << endl;sentence[count + 1] += (s + " ");essay.build(tem, count + 1);}}sentence[0] = sentence[line_num];line_num += 1;}主函数“main.cpp”
#include "read_and_store.h"void query(string word){int found = essay.find(word);if (found == 0)cout << "Word <" << word << "> isn't exist in this essay." << endl << endl;}int main(){read();string word;while (cin >> word)query(word);}
一切都在发展变化，不断地向昨天告别，满怀信心地投入每一个崭新的今天。
