文章目录六、运行结果七、总结
一、实验目的
1、掌握基于线性表、二叉排序树和散列表不同存储结构的查找算法 。
2、掌握不同检索策略对应的平均查找长度（ASL）的计算方法，明确不同检索策略的时间性能的差别 。
二、设计内容
一篇英文文章存储在一个文本文件中，然后分别基于线性表、二叉排序树和哈希表不同的存储结构，完成单词词频的统计和单词的检索功能 。同时计算不同检索策略下的平均查找长度ASL，通过比较ASL的大小，对不同检索策略的时间性能做出相应的比较分析（比较分析要写在实习报告中的“收获和体会”中） 。
读取一篇包括标点符号的英文文章（.txt），假设文件中单词的个数最多不超过5000个 。从文件中读取单词，过滤掉所有的标点 。分别利用线性表（包括基于顺序表的顺序查找、基于链表的顺序查找、基于顺序表的折半查找）、二叉排序树和哈希表（包括基于开放地址法的哈希查找、基于链地址法的哈希查找）总计6种不同的检索策略构建单词的存储结构 。不论采取哪种检索策略，完成功能均相同 。
（1）词频统计
当读取一个单词后，若该单词还未出现，则在适当的位置上添加该单词，将其词频计为1；若该单词已经出现过，则将其词频增加1 。统计结束后，将所有单词及其频率按照词典顺序写入文本文件中 。其中，不同的检索策略分别写入6个不同的文件 。
基于顺序表的顺序查找— .txt
基于链表的顺序查找— .txt
折半查找— .txt
基于二叉排序树的查找— .txt
基于开放地址法的哈希查找— .txt
【数据结构 C++实现 基于不同策略的英文单词的词频统计和检索系统】基于链地址法的哈希查找— .txt
注：如果实现方法正确，6个文件的内容应该是一致的 。
（2）单词检索
输入一个单词，如果查找成功，则输出该单词对应的频率，同时输出查找成功的平均查找长度ASL和输出查找所花费的时间 。如果查找失败，则输出“查找失败”的提示 。三、测试数据
文章插图
我这里只是随便找的比较短的一篇
四、设计思路
五、代码内容
这是分块写的，点击这里有糅合版
计算函数运行的时间（高精度）
#include#includeusing namespace std ;using namespace chrono; //使用命名空间chronotemplate //函数模板/*关键词 auto 看上去很高大上，它是一个“自动类型”，可以理解成“万能类型”，想成为啥，就成为啥system_clock 是 C++11 提供的一个 clock 。除此之外，还有两个clock：steady_clock 和 high_resolution_clock clock：时钟now( ) 表示计时的那“一瞬间”duration_cast< > 表示类型转换 duration:持续时间count( ) 用来返回时间*/void measure(T&& func) {auto start = system_clock::now(); //开始时间func(); //执行函数duration diff = system_clock::now() - start; //现在时间 - 开始时间cout << "elapsed: " << diff.count() << "秒" << endl;}void func(){long long s = 0;for(int i=0;i<20000000;i++){s+=i;}cout<<
计算函数运行的时间（低精度）
#include #include using namespace std;void func(){long long s = 0;for(int i=0;i<20000000;i++){s+=i;}cout<<
1、预处理
//写一个标准的头文件避免重复编译#ifndef _HEAD_H#define _HEAD_H/*#include
- vue双向绑定的原理及实现双向绑定MVVM源码分析
- vue中如何简单使用vue.draggable组件实现拖拽功能
- 三 用Abp实现短信验证码免密登录：Vue网页端开发
- 使用Yeoman实现vue项目结构创建
- android framework 系统native c/c++源码查看跳转工具
- angular ui-router：简单的单页面嵌套路由的实现过程
- 提升生鲜B2B电商系统的效率与品质，实现采购与销售的双赢
- 来自本科生的暴击：清华开源「天授」强化学习平台，纯PyTorch实现
- 支持单选、多选 Android本地历史记录、及产品标签实现（附源码）（使用
- micropython 驱动是如何实现的_ESP8266使用Micropytho