9、链地址哈希表类
//链地址法哈希表类class HashTableLink{public:HashTableLink(); //构造函数，初始化开散列表~HashTableLink(); //析构函数，释放同义词子表结点int Insert(datatype fword); //插入Node* Search(string word); //查找void Print(); //输出private:int H(int k); //散列函数Node* ht[MaxSize]; //开散列表};//构造函数HashTableLink::HashTableLink(){for (int i = 0; i < MaxSize; i++)ht[i] = NULL; //链式存储结构指针置空}//析构函数，释放空间HashTableLink :: ~HashTableLink(){Node* p = NULL, * q = NULL;for (int i = 0; i < MaxSize; i++){p = ht[i];q = p; //用来储存pwhile (p != NULL){ //p非空p = p->next; //p后移delete q; //删除qq = p;} //while} //for}//除留余数法-散列函数int HashTableLink::H(int k){return k % MaxSize;}//输出到屏幕和文本文件outfile6.txtvoid HashTableLink::Print() {system("cls"); //清屏ofstream fout; //文件写操作 内存写入存储设备fout.open("outfile6.txt"); //打开文件fout << "单词总数为：" << sum << endl;fout << "词频" << "\t" << "单词" << endl;for (int i = 0; i < sum; i++) {fout << WF[i].frequency << "\t" << WF[i].word << endl;cout << WF[i].frequency << "\t" <data.word == word)return p; //已找到返回指针elsep = p->next; //p后移} //whilereturn nullptr; //未找到返回空指针}//插入函数(前插法)int HashTableLink::Insert(datatype fword){int k = WordTransitionKey(fword.word); //转化为关键码fword.key = k; //给关键码赋值int j = H(k); //计算散列地址Node* p = Search(fword.word); //调用查找函数if (p != nullptr) //p非空，表示该内容已经插入过了return -1; //已存在元素k，无法插入 else { //p为空，表示该内容未插入p = new Node; //生成新节点p->data.key = fword.key; //关键码赋值p->data.frequency = fword.frequency; //词频赋值p->data.word = fword.word; //单词赋值p->next = ht[j]; //新节点插入ht[j]ht[j] = p; //更新节点return 1; //插入成功标志 }}
10、哈希表菜单
//哈希表菜单void HashMenu(){while(true){system("cls"); //清屏cout << "*******************基于不同策略的英文单词的词频统计和检索系统*******************" << endl;cout << "---哈希表---" << endl;cout << "1.开放地址法哈希查找" << endl;cout << "2.链地址法哈希查找" << endl;cout << "3.返回上一级" << endl;cout << "请按相应的数字键进行选择：" << endl;int n;cin >> n;switch (n){case 1 : OpenHashLocate(); //开放地址法哈希查找break;case 2 : LinkHashLocate(); //链地址法哈希查找break;case 3 : return; //退出函数default: cout << "输入的不是有效符号，请重新输入" << endl; system("pause");} //switch} //whilereturn;}//开放地址法哈希查找菜单void OpenHashLocateMenu(){HashTable HT;for (int i = 0; i < sum; i++)HT.Insert(WF[i]); //把数据插入到哈希表中double bulkfactor = sum / MaxSize; //装填因子system("cls"); //清屏cout << "*******************基于不同策略的英文单词的词频统计和检索系统*******************" << endl;cout << "---开放地址单词查找---" << endl;cout << "请输入要查找的单词：";string word;cin >> word;auto start = system_clock::now(); //开始时间int i = HT.Search(word); //获取散列地址duration diff = system_clock::now() - start; //现在时间 - 开始时间if (i) {cout << "此单词为：" << HT.Get(i).word << endl;cout << "此单词的词频：" << HT.Get(i).frequency << endl;cout << "查找该单词所花费的时间：" << (diff.count())*1000 << "毫秒" << endl;cout << "平均查找长度：" << (1 + 1 / (1 - bulkfactor)) / 2 << endl;} //ifelsecout << "查找失败"