数据结构 C++实现 基于不同策略的英文单词的词频统计和检索系统
文章目录 六、运行结果七、总结
一、实验目的
1、掌握基于线性表、二叉排序树和散列表不同存储结构的查找算法。
2、掌握不同检索策略对应的平均查找长度（ASL）的计算方法，明确不同检索策略的时间性能的差别。
二、设计内容
一篇英文文章存储在一个文本文件中，然后分别基于线性表、二叉排序树和哈希表不同的存储结构，完成单词词频的统计和单词的检索功能。同时计算不同检索策略下的平均查找长度ASL，通过比较ASL的大小，对不同检索策略的时间性能做出相应的比较分析（比较分析要写在实习报告中的“收获和体会”中）。
读取一篇包括标点符号的英文文章（.txt），假设文件中单词的个数最多不超过5000个。从文件中读取单词，过滤掉所有的标点。分别利用线性表（包括基于顺序表的顺序查找、基于链表的顺序查找、基于顺序表的折半查找）、二叉排序树和哈希表（包括基于开放地址法的哈希查找、基于链地址法的哈希查找）总计6种不同的检索策略构建单词的存储结构。不论采取哪种检索策略，完成功能均相同。
（1）词频统计
当读取一个单词后，若该单词还未出现，则在适当的位置上添加该单词，将其词频计为1；若该单词已经出现过，则将其词频增加1。统计结束后，将所有单词及其频率按照词典顺序写入文本文件中。其中，不同的检索策略分别写入6个不同的文件。
基于顺序表的顺序查找— .txt
基于链表的顺序查找— .txt
折半查找— .txt
基于二叉排序树的查找— .txt
基于开放地址法的哈希查找— .txt
基于链地址法的哈希查找— .txt
注：如果实现方法正确，6个文件的内容应该是一致的。
（2）单词检索
输入一个单词，如果查找成功，则输出该单词对应的频率，同时输出查找成功的平均查找长度ASL和输出查找所花费的时间。如果查找失败，则输出“查找失败”的提示。 三、测试数据
我这里只是随便找的比较短的一篇
四、设计思路
五、代码内容
这是分块写的，点击这里有糅合版
计算函数运行的时间（高精度）
#include计算函数运行的时间（低精度）
#include 1、预处理
//写一个标准的头文件避免重复编译
#ifndef _HEAD_H
#define _HEAD_H/*#include ofstream //文件写操作 内存写入存储设备ifstream //文件读操作，存储设备读取到内存中fstream //读写操作，对打开的文件可进行读写操作void open(const char* filename,int mode,int access);参数：filename： 要打开的文件名mode： 要打开文件的方式access： 打开文件的属性打开文件的方式在类ios(是所有流式I/O类的基类)中定义.常用的值如下：ios::app： 以追加的方式打开文件ios::ate： 文件打开后定位到文件尾，ios:app就包含有此属性ios::binary： 以二进制方式打开文件，缺省的方式是文本方式。两种方式的区别见前文ios::in： 文件以输入方式打开(文件数据输入到内存)ios::out： 文件以输出方式打开(内存数据输出到文件)ios::nocreate： 不建立文件，所以文件不存在时打开失败ios::noreplace：不覆盖文件，所以打开文件时如果文件存在失败ios::trunc： 如果文件存在，把文件长度设为0
*/ #include2、读入文件
// 读取TXT内容并整理
//统计文章词频(去掉重复单词)
int StatisticalWord(string word) {for (int i = 0; i < MaxSize; i++) { //循环控制，单词查重if (WF[i].word == word) { //单词重复WF[i].frequency++; //词频+1return i; //退出函数} //if} //for//单词不重复WF[sum].word = word; //添加单词WF[sum].frequency = 1; //词频置为一WF[sum].key = WordTransitionKey(word); //添加关键码sum++; //单词总数+1return 0;
}//大写英语单词转化成小写
string WordTransition(string word) {for (int i = 0; i < int(word.size()); i++) { //获取字符串长度，使用length()也可以if (word[i] >= 'A' && word[i] <= 'Z') //判断字符是否是大写字母word[i] = word[i] + 32; //ASCII码表中十进制 A==65 a==97 中间相差32，后面的也是如此} //forreturn word; //返回小写单词
}//判断单词中是否有大写字母
int WordJudge(string word) {for (int i = 0; i < int(word.size()); i++) {if (word[i] >= 'A' && word[i] <= 'Z') //判断单词中是否有大写字母return 1; //如果有，返回1} //forreturn 0; //没有返回0
}//词频统计
void StatisticsData() {system("cls"); //清屏ifstream fin; //文件读操作，存储设备读取到内存中fin.open(file); //关联文件filechar ch; //用于获取字符 string word; //用于存放单词int count = 0, min; //count用于标记单词个数，min用于标记最小的单词for (int i = 0; fin.get(ch); i++) { //读取文件内容，并去除符号if ((ch >= 'a' && ch <= 'z') || (ch >= 'A' && ch <= 'Z')) {if (word == "\0") //word为空，放入第一个字母word = ch;elseword += ch; //word不为空，拼接字母组成单词} //ifelse {if (word != "\0") { //判断之前的word里面是否有单词count++; //有单词，总数+1if (count > MaxSize) {cout << "文章单词超出统计上限，系统已退出" << endl;fin.close(); //关闭文件exit(0); //退出程序system("pause"); //暂停}StatisticalWord(word); //存放到结构体数组里面} //ifword = "\0"; //重置word，用于存放新单词} //else} //for//按照词典排序（选择排序） 从小到大WordFrequency temp; //临时存储空间for (int i = 0; i < sum; i++) {min = i; //重置minfor (int j = i + 1; j < sum; j++) {if (WordTransition(WF[j].word) < WordTransition(WF[min].word)) //将单词转换成小写进行比较min = j; //得到最小单词序号} //for//交换原始单词，词频temp = WF[i];WF[i] = WF[min];WF[min] = temp;} //forfor (int i = 0; i < sum; i++) {min = i;for (int j = i + 1; j < sum; j++) {if (WordTransition(WF[j].word) == WordTransition(WF[min].word)) //两个单词相等if (WordJudge(WF[j].word) > WordJudge(WF[min].word)) //大写的排前面min = j; //得到最小单词序号} //for//交换原始单词,词频temp = WF[i];WF[i] = WF[min];WF[min] = temp;} //forfin.close(); //关闭文件
}//将单词转换为唯一关键码
int WordTransitionKey(string word) {int a[21] = { 0,2,3,5,7,11,13,17,19,23,27,29,31,37,41,47,51,67,87,101,111 }; //最长识别20个字母的的单词int sumkey = 0;for (int i = 0; i < int(word.size()); i++) {sumkey += int(word[i]); //每个字符的ASCLL值相加}sumkey += int('h') * a[int(word.size())];return sumkey;
}3、顺序表类
//顺序表类
class SeqList{public:SeqList() {} //无参构造SeqList(datatype a[], int n){ //有参构造函数，初始化长度为n的顺序表if (n > MaxSize){cout << "单词数量过多，超出线性表最大容量" << endl;} //iffor (int i = 0; i < n; i++){wf[i].word = a[i].word;wf[i].frequency = a[i].frequency;} //for}~SeqList(){}; //析构函数int Empty(); //顺序表判空函数void PrintList(int n); //遍历操作，按序号依次输出各元素int SeqlistLocate(string word); //顺序查找int BinSearch(string word); //折半查找string getword(int n); //返回单词int getfre(int n); //返回词频private:datatype wf[MaxSize]; //存放词频结构体的数组
};//返回单词
string SeqList::getword(int n) {return wf[n].word;
}//返回词频
int SeqList::getfre(int n) {return wf[n].frequency;
}//顺序表判空函数
int SeqList::Empty(){if (sum == 0)return 1;elsereturn 0;
}//顺序查找
int SeqList::SeqlistLocate(string word){for (int i = 0; i < sum; i++){ //依次遍历if (wf[i].word == word) //找到wordreturn i; //返回下标} //forreturn -1; //未找到返回-1
}//折半查找
int SeqList::BinSearch(string word){int mid, low = 0, high = sum - 1; //初始查找区间是[0, sum-1]while (low <= high) { //当区间存在时mid = (low + high) / 2; //初始化中值if (word == wf[mid].word) //找到wordbreak; //退出循环else if (WordTransition(word) < WordTransition(wf[mid].word)) //word在前半段high = mid - 1; //改变上限，gigh前移查找区间变为 [low,mid-1]else //word在后半段，或者不存在low = mid + 1; //改变下线，low后移查找区间变为 [mid+1,high]} //whileif (low <= high)return mid; //找到返回下标elsereturn -1; //未找到返回-1
}//输出线性表顺序表，参数n用来控制输出顺序查找还是折半查找
void SeqList::PrintList(int n){system("cls"); //清屏if (n == 1){ofstream fout; //文件写操作 内存写入存储设备 fout.open("outfile1.txt");fout << "单词总数为：" << sum << endl;fout << "词频" << "\t" << "单词" << endl;for (int i = 0; i< sum; i++){fout << wf[i].frequency << "\t" << wf[i].word << endl; } //forfout.close(); //关闭文件} //ifif (n == 2){ofstream fout; //文件写操作 内存写入存储设备 fout.open("outfile3.txt");fout << "单词总数为：" << sum << endl;fout << "词频" << "\t" << "单词" << endl;for (int i = 0; i < sum; i++) {fout << wf[i].frequency << "\t" << wf[i].word << endl;} //forfout.close(); //关闭文件} //ifcout << "单词总数为：" << sum << endl;cout << "词频" << "\t" << "单词" << endl;for (int i = 0; i < sum; i++)cout << wf[i].frequency << "\t" << wf[i].word << endl;if (n == 1)cout << "单词以及词频已经保存到文件outfile1.txt文件中" << endl;else if (n == 2)cout << "单词以及词频已经保存到文件outfile3.txt文件中" << endl;system("pause"); //暂停
}4、链表类
//链表类
class LinkList{public:LinkList(datatype a[], int n) { //有参构造函数，建立有n个元素的单链表Head = new Node; //生成头结点Node* r = Head, * s = NULL; //尾指针初始化,并定义存储指针for (int i = 0; i < n; i++){s = new Node; s->data = a[i]; //数据域赋值r->next = s; //将存储节点s插入链表r = s; //更新尾指针} //forr->next = NULL; //单链表建立完毕，将终端结点的指针域置空}~LinkList() { //析构函数Node* temp = NULL; //定义临时节点while (Head != NULL){ //释放单链表的每一个结点的存储空间temp = Head; //暂存被释放结点Head = Head->next; // Head指向被释放结点的下一个结点delete temp;} //while}int Empety(); //判断链表是否为空int Locate(string word); //按值查找，返回下标void PrintList(); //遍历操作，按序号依次输出各元素datatype getdata(int n);private:Node* Head; //单链表的头指针
};//返回数据域
datatype LinkList::getdata(int n) {Node* t = Head->next; //指针初始化for (int i = 1; i < n; i++)t = t->next;return t->data;}//判空
int LinkList::Empety(){if (Head->next)return 1; //链表非空，正常返回return 0; //链表为空，返回-1
}//输出单链表
void LinkList::PrintList(){system("cls"); //清屏Node* p = Head->next;//工作指针p初始化ofstream fout; //文件写操作 内存写入存储设备 fout.open("outfile2.txt"); //打开文件fout << "单词总数为：" << sum << endl;fout << "词频" << "\t" << "单词" << endl;while (p != NULL){fout << p->data.frequency << "\t" << p->data.word << endl;p = p->next; //指针p后移} //whilefout.close(); //关闭文件cout << "单词总数为：" << sum << endl;cout << "词频" << "\t" << "单词" << endl;Node* p1 = Head->next;//工作指针p初始化while (p1){ //p <--> p != NULLcout << p1->data.frequency << "\t" << p1->data.word << endl;p1 = p1->next; //工作指针p后移，注意不能写作p++} //whilecout << "单词以及词频已经保存到文件outfile2.txt文件中" << endl;system("pause"); //暂停
}//按值查找，返回下标
int LinkList::Locate(string word){Node* p = Head->next; //指针p初始化int count = 1; //计数器count初始化,表示查找次数while (p != NULL){if (p->data.word == word) return count; //查找成功，结束函数并返回下标p = p->next; //p指针后移count++;} //whilereturn -1; //退出循环表明查找失败
}
5、线性表菜单
// 线性表菜单
void ListMenu(){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 : SequenceMenu(); //顺序查找菜单break;case 2 : HalfSortMenu(); //顺序表折半查找菜单break;case 3 : return; //结束函数default: cout << "输入的不是有效符号，请重新输入" << endl; system("pause"); //暂停} //switch} //while
}//顺序查找菜单
void SequenceMenu(){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:SeqListMenu(); //顺序查找菜单break;case 2: LinklistSeqMenu(); //链表查找菜单break;case 3: return; //结束函数default:cout << "输入的不是有效符号，请重新输入" << endl;system("pause"); //暂停break;} //switch} //while
}//顺序表顺序查找菜单
void SeqListMenu(){SeqList L(WF, sum);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: L.PrintList(1); //输出线性表顺序表词频统计break;case 2: WorLocatMenu(); //顺序表顺序单词查找菜单break;case 3:return;default: cout << "输入的不是有效符号，请重新输入" << endl; system("pause");} //switch} //whilereturn;
}//链表顺序查找菜单
void LinklistSeqMenu(){LinkList L(WF, sum);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: L.PrintList(); //输出线性表链表词频统计break;case 2:LinklistLocateMenu(); //链表单词查找break;case 3: return;default:cout << "输入的不是有效符号，请重新输入" << endl; system("pause"); //暂停} //switch} //whilereturn;
}//顺序表顺序单词查找菜单
void WorLocatMenu(){SeqList L(WF , sum); system("cls"); //清屏cout << "*******************基于不同策略的英文单词的词频统计和检索系统*******************" << endl;cout << "---顺序表单词查找---" << endl;cout << "请输入要查找的单词：";string word;cin >> word; //键盘录入要查找单词auto start = system_clock::now(); //开始时间int i = L.SeqlistLocate(word); //返回下标duration<double> diff = system_clock::now() - start; //现在时间 - 开始时间if (i+1) {cout << "此单词为：" << L.getword(i) << endl;cout << "此单词的词频：" << L.getfre(i) << endl;cout << "查找该单词所花费的时间：" << (diff.count())*1000 << "毫秒" << endl;cout << "平均查找长度：" << (sum + 1) / 2 << endl;} //ifelsecout << "查找失败" << endl;system("pause"); //暂停
}//链表单词查找菜单
void LinklistLocateMenu(){LinkList L(WF, sum);system("cls"); //清屏cout << "*******************基于不同策略的英文单词的词频统计和检索系统*******************" << endl;cout << "---链表单词查找---" << endl;cout << "请输入要查找的单词：";string word;cin >> word;auto start = system_clock::now(); //开始时间int i = L.Locate(word);duration<double> diff = system_clock::now() - start; //现在时间 - 开始时间if (i) {cout << "此单词为：" << L.getdata(i).word << endl;cout << "此单词的词频：" << L.getdata(i).frequency << endl;cout << "查找该单词所花费的时间：" << (diff.count())*1000 << "毫秒" << endl;cout << "平均查找长度：" << (sum + 1) / 2 << endl;} //ifelsecout << "查找失败" << endl;system("pause"); //暂停
}//顺序表折半查找菜单
void HalfSortMenu(){SeqList L(WF, sum);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:L.PrintList(2); //折半查找，输出break;case 2: HalfdLocateMenu(); //折半查找break;case 3:return; //退出函数default: cout << "输入的不是有效符号，请重新输入" << endl; system("pause"); //暂停} //switch} //while
}//顺序表折半查找菜单
void HalfdLocateMenu(){SeqList L(WF, sum);system("cls"); //清屏cout << "*******************基于不同策略的英文单词的词频统计和检索系统*******************" << endl;cout << "---折半单词查找---" << endl;cout << "请输入要查找的单词：";string word;cin >> word;auto start = system_clock::now(); //开始时间L.BinSearch(word);duration<double> diff = system_clock::now() - start; //现在时间 - 开始时间int i = L.BinSearch(word); //返回下标if (i >= 0) {cout << "此单词为：" << L.getword(i) << endl;cout << "此单词的词频：" << L.getfre(i) << endl;cout << "查找该单词所花费的时间：" << (diff.count())*1000 << "毫秒" << endl;cout << "平均查找长度：" << double((log(double(sum) + 1) / log(2)) - 1) << endl;} //ifelsecout << "查找失败" << endl;system("pause"); //暂停
}6、二叉排序树类
//二叉排序树类
class BiSortTree {
public:BiSortTree(datatype a[], int n); //带参构造函数，对树初始化~BiSortTree() { //析构函数Release(root);}BiNode* InsertBST(datatype data) { //函数重载，插入数据域datareturn InsertBST(root, data);}BiNode* SearchBST(string word) { //函数重载,查找值为word的结点return SearchBST(root, word);}void printf(); //输出函数
private:void Release(BiNode* bt); //释放空间BiNode* InsertBST(BiNode* bt, datatype data); //插入数据域dataBiNode* SearchBST(BiNode* bt, string word); //查找值为word的结点void InOrder(BiNode* bt); //中序遍历函数调用BiNode* root; //二叉排序树的根指针
};//构造函数
BiSortTree::BiSortTree(datatype a[], int n) {root = NULL; //根指针置空for (int i = 0; i < n; i++)root = InsertBST(root, a[i]); //遍历，插入数据
}//输出函数
void BiSortTree::InOrder(BiNode* bt) { //递归输出二叉排序树ofstream fout; //文件写操作 内存写入存储设备fout.open("outfile4.txt", ios_base::out | ios_base::app); //打开文件并将内容追加到文件尾if (bt == NULL) //递归调用的结束条件,根指针为空return; //退出函数 else {InOrder(bt->lchild); //中序递归遍历bt的左子树cout << bt->data.frequency << "\t" << bt->data.word << endl; //访问根结点bt的数据域，输出到屏幕fout << bt->data.frequency << "\t" << bt->data.word << endl; //访问根结点bt的数据域，输出到文件fout.close(); //关闭文件InOrder(bt->rchild); //中序递归遍历bt的右子树 } //else
}//输出二叉排序树到屏幕和outfile4.txt
void BiSortTree::printf() {system("cls"); //清屏ofstream fout; //文件写操作 内存写入存储设备fout.open("outfile4.txt");//打开文件fout << "单词总数为：" << sum << endl;fout << "词频" << "\t" << "单词" << endl;InOrder(root); //输出函数system("pause"); //暂停return; //退出函数
}//递归查找函数，返回指针
BiNode* BiSortTree::SearchBST(BiNode* bt, string word) {if (bt == NULL)return NULL; //未找到，返回NULLif (bt->data.word == word)return bt; //找到word，返回该指针else if (bt->data.word > word) //数据大于wordreturn SearchBST(bt->lchild, word); //递归查找左子树else //数据小于wordreturn SearchBST(bt->rchild, word); //递归查找右子树
}//递归插入函数
BiNode* BiSortTree::InsertBST(BiNode* bt, datatype data) {if (bt == NULL) { //找到插入位置BiNode* s = new BiNode; //生成一个新的储存空间s->data = data; //为数据域赋值s->lchild = NULL; //左孩子指针置空s->rchild = NULL; //右孩子指针置空bt = s; //根指针更新return bt; //返回根指针} //ifelse if (WordTransition(bt->data.word) > WordTransition(data.word)) { //根节点数据大于要插入的数据bt->lchild = InsertBST(bt->lchild, data); //更新左孩子指针return bt; //返回根指针} //else ifelse { //根节点数据小于要插入的数据bt->rchild = InsertBST(bt->rchild, data); //更新有孩子指针return bt; //返回根指针} //else
}//递归析构函数
void BiSortTree::Release(BiNode* bt) {if (bt == NULL)return; //根指针为空直接退出else {Release(bt->lchild); //释放左子树Release(bt->rchild); //释放右子树delete bt; //释放根结点}
}7、二叉排序树菜单
// 二叉排序树菜单
void BiTreeMenu(){while(true){system("cls"); //清屏cout << "*******************基于不同策略的英文单词的词频统计和检索系统*******************" << endl;cout << "---二叉排序树查找---" << endl;cout << "1.二叉排序树的顺序查找" << endl;cout << "2.返回上一级" << endl;cout << "请按相应的数字键进行选择：" << endl;int n;cin >> n;switch (n){case 1: BitreeLocateMenu(); //二叉排序树查找菜单break; //退出switchcase 2: return; //退出函数default:cout << "输入的不是有效符号，请重新输入" << endl; system("pause"); //暂停} //switch} //while
}//二叉排序树的顺序查找菜单
void BitreeLocateMenu(){BiSortTree B(WF,sum);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: B.printf(); break;case 2: BitreeWordLocMenu(); //二叉排序树查找单词菜单break;case 3:return; //退出函数default: cout << "输入的不是有效符号，请重新输入" << endl; system("pause"); //暂停} //switch} //while
}//二叉排序树查找单词菜单
void BitreeWordLocMenu(){BiSortTree B(WF,sum);system("cls"); //清屏cout << "*******************基于不同策略的英文单词的词频统计和检索系统*******************" << endl;cout << "---二叉排序单词查找---" << endl;cout << "请输入要查找的单词：";string word;cin >> word;auto start = system_clock::now(); //开始时间B.SearchBST(word);duration<double> diff = system_clock::now() - start; //现在时间 - 开始时间BiNode* p = NULL; //指针置空p = B.SearchBST(word);if (p != NULL) {cout << "此单词为：" << p->data.word << endl;cout << "此单词的词频：" << p->data.frequency << endl;cout << "查找该单词所花费的时间：" << (diff.count())*1000 << "毫秒" << endl;cout << "平均查找长度：" << sum << endl;} //ifelsecout << "查找失败" << endl;system("pause"); //暂停
}8、开放地址哈希表类
//开放地址哈希表类
class HashTable {
public:HashTable(); //构造函数，初始化空散列表~HashTable() {}; //析构函数int Insert(datatype a); //插入int Search(string word); //查找datatype Get(int a);void Print(); //输出
private:int H(int k); //哈希函数(散列函数)datatype ht[MaxSize]; //散列表
};//构造函数
HashTable::HashTable() {for (int i = 0; i < MaxSize; i++) {ht[i].key = 0; //关键码初始化ht[i].word = "";ht[i].frequency = 0; // 0表示该散列单元为空} //for
}//哈希函数，除留余数法
int HashTable::H(int k) {return k % MaxSize;
}//输出函数
void HashTable::Print() {system("cls"); //清屏ofstream fout; //文件写操作 内存写入存储设备fout.open("outfile5.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" << WF[i].word << endl;} //forsystem("pause"); //暂停
}//查找函数
int HashTable::Search(string word) {int key = WordTransitionKey(word); //将单词转化为关键码int i = H(key); //计算散列地址，设置比较的起始位置while (ht[i].key != 0) {if (ht[i].word == word)return i; //查找成功elsei = (i + 1) % MaxSize; //向后探测一个位置} //whilereturn 0; //查找失败
}//插入函数
int HashTable::Insert(datatype f_word_key) {int key = WordTransitionKey(f_word_key.word);//将单词转化为关键码int i = H(key); //计算散列地址，设置比较的起始位置while (ht[i].key != 0) { //寻找空的散列单元i = (i + 1) % MaxSize; //向后探测一个位置} //whileht[i].key = key; //关键码赋值ht[i].word = f_word_key.word; //单词赋值ht[i].frequency = f_word_key.frequency; //词频赋值return i; //返回插入位置
}//获取单词以及频率
datatype HashTable::Get(int a) {return ht[a];
}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.txt
void 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" <<WF[i].word << endl;} //forsystem("pause"); //暂停
}//查找函数
Node* HashTableLink::Search(string word){int k = WordTransitionKey(word); //转化为关键码int j = H(k); //计算散列地址Node* p = ht[j]; //指针p初始化while (p != NULL){ //p非空if (p->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<double> 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 << "查找失败" << endl;system("pause"); //暂停
}//开放地址法哈希查找
void OpenHashLocate(){HashTable HT;for (int i = 0; i < sum; i++)HT.Insert(WF[i]); //把数据插入到哈希表中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 : HT.Print(); //词频统计break;case 2 : OpenHashLocateMenu(); //开放地址法的哈希查找菜单break;case 3 :return;default: cout << "输入的不是有效符号，请重新输入" << endl; system("pause"); //暂停} //switch} //while
}//链地址法哈希查找
void LinkHashLocate(){HashTableLink HT;for (int i = 0; i < sum; i++)HT.Insert(WF[i]); //把数据插入到哈希表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: HT.Print(); //词频统计break;case 2:LinkHashWordLocateMenu(); //单词查找菜单break;case 3: return; //退出函数default: cout << "输入的不是有效符号，请重新输入" << endl; system("pause"); //暂停} //switch} //while
}//链地址法哈希查找菜单
void LinkHashWordLocateMenu(){HashTableLink HT;for (int i = 0; i < sum; i++)HT.Insert(WF[i]); //把数据插入到哈希表double load_factor = sum / MaxSize;//散列表的装填因子system("cls");cout << "*******************基于不同策略的英文单词的词频统计和检索系统*******************" << endl;cout << "---链地址单词查找---" << endl;cout << "请输入要查找的单词：";string word;cin >> word;auto start = system_clock::now(); //开始时间HT.Search(word);duration<double> diff = system_clock::now() - start; //现在时间 - 开始时间Node* p = HT.Search(word); //返回目标指针if (p != NULL) {cout << "此单词为：" << p->data.word << endl;cout << "此单词的词频：" << p->data.frequency << endl;cout << "查找该单词所花费的时间：" << (diff.count())*1000 << "毫秒" << endl;cout << "平均查找长度：" << 1 + (load_factor) / 2 << endl;} //ifelsecout << "查找失败" << endl;system("pause"); //暂停
}11、主菜单
//主函数
int main() {ifstream fin;fin.open(file);//关联文件fileif (!fin.is_open()) {cout << "file.txt文件不存在，请检查文件名或者目录下文件是否存在。" << endl;system("pause"); //暂停return 0;} //ifelse {cout << "file.txt文件加载中..." << endl;Sleep(1000);//延时1秒} //elseStatisticsData(); //数据统计MajorMenu();//主菜单return 0;
}//主菜单
void MajorMenu() {while (true) {cout << "*******************基于不同策略的英文单词的词频统计和检索系统*******************" << endl;cout << "---菜单---" << endl;cout << "1.基于线性表的查找" << endl;cout << "2.基于二叉排序树的查找" << endl;cout << "3.基于哈希表的查找" << endl;cout << "4.退出系统" << endl;cout << "请按相应的数字键进行选择：" << endl;int n;cin >> n;switch (n) {case 1:ListMenu();break;case 2:BiTreeMenu();break;case 3:HashMenu();break;case 4:cout << "系统已退出" << endl;return;default:cout << "输入的不是有效符号，请重新输入" << endl;system("cls"); //清屏system("pause"); //暂停} //switch} //for
}六、运行结果
运行结果我放在了糅合版
七、总结
通过这次实验，让我对顺序表、链表、二叉排序树、连地址哈希表和开放地址哈希表的结构有了更深刻的认识；学会如何去使用基于以上结构的顺序查找、折半查找等；还学会了如何输出查找时间以及他们的ASL(平均查找长度)
