文章目录六、运行结果七、总结
一、实验目的
1、掌握基于线性表、二叉排序树和散列表不同存储结构的查找算法 。
2、掌握不同检索策略对应的平均查找长度(ASL)的计算方法,明确不同检索策略的时间性能的差别 。
二、设计内容
一篇英文文章存储在一个文本文件中,然后分别基于线性表、二叉排序树和哈希表不同的存储结构,完成单词词频的统计和单词的检索功能 。同时计算不同检索策略下的平均查找长度ASL,通过比较ASL的大小,对不同检索策略的时间性能做出相应的比较分析(比较分析要写在实习报告中的“收获和体会”中) 。
读取一篇包括标点符号的英文文章(.txt),假设文件中单词的个数最多不超过5000个 。从文件中读取单词,过滤掉所有的标点 。分别利用线性表(包括基于顺序表的顺序查找、基于链表的顺序查找、基于顺序表的折半查找)、二叉排序树和哈希表(包括基于开放地址法的哈希查找、基于链地址法的哈希查找)总计6种不同的检索策略构建单词的存储结构 。不论采取哪种检索策略,完成功能均相同 。
(1)词频统计
当读取一个单词后,若该单词还未出现,则在适当的位置上添加该单词,将其词频计为1;若该单词已经出现过,则将其词频增加1 。统计结束后,将所有单词及其频率按照词典顺序写入文本文件中 。其中,不同的检索策略分别写入6个不同的文件 。
基于顺序表的顺序查找— .txt
基于链表的顺序查找— .txt
折半查找— .txt
基于二叉排序树的查找— .txt
基于开放地址法的哈希查找— .txt
【数据结构 C++实现 基于不同策略的英文单词的词频统计和检索系统】基于链地址法的哈希查找— .txt
注:如果实现方法正确,6个文件的内容应该是一致的 。
(2)单词检索
输入一个单词,如果查找成功,则输出该单词对应的频率,同时输出查找成功的平均查找长度ASL和输出查找所花费的时间 。如果查找失败,则输出“查找失败”的提示 。三、测试数据
![数据结构 C++实现 基于不同策略的英文单词的词频统计和检索系统](http://img.gansulong.com/230916/0201121K4-0.png)
文章插图
我这里只是随便找的比较短的一篇
四、设计思路
五、代码内容
这是分块写的,点击这里有糅合版
计算函数运行的时间(高精度)
#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