数据结构 C++实现 基于不同策略的英文单词的词频统计和检索系统（糅合版）

文章目录

• 
  

  一、实验目的

• 
  

  二、设计内容

• 
  

  三、测试数据

• 
  

  四、设计思路

• 
  

  五、代码内容

• • 1、函数运行时间方法一
  • 2、函数运行时间方法二
  • 3、代码实现
• 
  

  六、总结

一、实验目的

1、掌握基于线性表、二叉排序树和散列表不同存储结构的查找算法。

2、掌握不同检索策略对应的平均查找长度（ASL）的计算方法，明确不同检索策略的时间性能的差别。

二、设计内容

一篇英文文章存储在一个文本文件中，然后分别基于线性表、二叉排序树和哈希表不同的存储结构，完成单词词频的统计和单词的检索功能。

同时计算不同检索策略下的平均查找长度ASL，通过比较ASL的大小，对不同检索策略的时间性能做出相应的比较分析（比较分析要写在实习报告中的“收获和体会”中）。

1. 读取一篇包括标点符号的英文文章（InFile.txt），假设文件中单词的个数最多不超过5000个。
   

   
   

   从文件中读取单词，过滤掉所有的标点。
   

   
   

2. 分别利用线性表（包括基于顺序表的顺序查找、基于链表的顺序查找、基于顺序表的折半查找）、二叉排序树和哈希表（包括基于开放地址法的哈希查找、基于链地址法的哈希查找）总计6种不同的检索策略构建单词的存储结构。
   

   
   

3. 不论采取哪种检索策略，完成功能均相同。
   

   
   

   
   （1）词频统计
   当读取一个单词后，若该单词还未出现，则在适当的位置上添加该单词，将其词频计为1；若该单词已经出现过，则将其词频增加1。
   

   
   

   统计结束后，将所有单词及其频率按照词典顺序写入文本文件中。
   

   
   

   其中，不同的检索策略分别写入6个不同的文件。
   

   
   

   
   基于顺序表的顺序查找— OutFile1.txt
   基于链表的顺序查找— OutFile2.txt
   折半查找— OutFile3.txt
   基于二叉排序树的查找— OutFile4.txt
   基于开放地址法的哈希查找— OutFile5.txt
   基于链地址法的哈希查找— OutFile6.txt
   注：如果实现方法正确，6个文件的内容应该是一致的。
   

   
   

   
   （2）单词检索
   输入一个单词，如果查找成功，则输出该单词对应的频率，同时输出查找成功的平均查找长度ASL和输出查找所花费的时间。
   

   
   

   如果查找失败，则输出“查找失败”的提示。
   

   
   

三、测试数据

我这里只是随便找的比较短的一篇

四、设计思路

五、代码内容

点击这里有分块写的代码

1、函数运行时间方法一

精度比较高

#include
#include
using namespace std ;
using namespace chrono;	//使用命名空间chrono
template <typename T>	//函数模板

/*
关键词 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<double> 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<<s<<endl;
}
int main(){
	measure(func);
	return 0;
}

2、函数运行时间方法二

精度比较低

#include 
#include 
using namespace std;

void func(){
	long long s = 0;
	for(int i=0;i<20000000;i++){
		s+=i;
	}
	cout<<s<<endl;
}
int main(){
	clock_t start = clock();
	func();
	clock_t end   = clock();
	cout << "花费了" << (double)(end - start) / CLOCKS_PER_SEC << "秒" << endl;	
}

3、代码实现

//写一个标准的头文件避免重复编译
#ifndef _HEAD_H
#define _HEAD_H

#include
#include
#include
#include
#include
#include
using namespace std;

//常量
const int MaxSize = 300;	//文章单词最大容量
const char* file = "file.txt";	//待检索文件
static int sum = 0;	//单词总数(不重复)

// 结构体

// 词频顺序存储结构
struct WordFrequency {	//词频
	string word;	//单词
	int frequency;	//频率
	int key;	//关键码
}WF[MaxSize];

typedef WordFrequency datatype;	//为数据类型定义一个新的名字

//词频链式存储结构
struct Node {
	datatype data;	//数据域
	Node* next;	//指针域
};

//二叉排序树链式存储结构
struct BiNode {
	datatype data;	//节点数据域
	BiNode* lchild, * rchild;	//左右孩子指针
};

//ReadFile函数声明
int StatisticalWord(string word);	//统计文章词频(去掉重复单词)
string WordTransition(string word);	//大写英语单词转化成小写
int WordJudge(string word);	//判断单词中是否有大写字母
void StatisticsData();	//数据统计
int  WordTransitionKey(string word);	//将单词转换为唯一关键码

//LinkedListMenu函数声明
void ListMenu();	// 线性表菜单
void SequenceMenu();	//顺序查找菜单
void SeqListMenu();	//顺序表顺序查找菜单
void WorLocatMenu();//顺序表单词查找菜单
void LinklistSeqMenu();//链表顺序查找菜单
void LinklistLocateMenu();	//链表单词查找菜单
void HalfSortMenu();	//顺序表折半查找菜单
void HalfdLocateMenu();	//顺序表折半单词查找菜单

//BiTreeMenu函数声明
void BiTreeMenu();	// 二叉排序树菜单
void BitreeLocateMenu();	//二叉排序树的顺序查找菜单
void BitreeWordLocMenu();	//二叉排序树查找单词菜单

//HashTableMenu函数声明
void HashMenu();	//哈希表菜单
void OpenHashLocateMenu();	//开放地址法哈希查找菜单
void OpenHashLocate();	//开放地址法哈希查找
void LinkHashLocate();	//链地址法哈希查找
void LinkHashWordLocateMenu();	//开放地址法哈希查找菜单

void MajorMenu();	//主菜单


#endif // !_HEAD_H



//主函数
int main(){
	ifstream fin;
	fin.open(file);//关联文件file
	if (!fin.is_open()){
		cout << "file.txt文件不存在，请检查文件名或者目录下文件是否存在。

" << endl;
		system("pause");	//暂停
		return 0;
	}	//if
	else{
		cout << "file.txt文件加载中..." << endl;
		Sleep(1000);//延时1秒
	}	//else
	StatisticsData();	//数据统计
	MajorMenu();//主菜单
	return 0;
}

//主菜单
void MajorMenu(){
	while(true){
		system("cls");	//清屏
		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
}

// 读取TXT内容并整理
//统计文章词频(去掉重复单词)
int StatisticalWord(string word){
	for (int i = 0; i < MaxSize; i++){	//循环控制，单词查重
		if (WF[i].word == word){	//单词重复
			WF[i].frequency++;	//词频+1
			return i;	//退出函数
		}	//if
	}	//for
	//单词不重复
	WF[sum].word = word;	//添加单词
	WF[sum].frequency = 1;	//词频置为一
	WF[sum].key = WordTransitionKey(word);	//添加关键码
	sum ++;	//单词总数+1
	return 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，后面的也是如此
	}	//for
	return word;	//返回小写单词
}

//判断单词中是否有大写字母
int WordJudge(string word){
	for (int i = 0; i < int(word.size()); i++){
		if (word[i] >= 'A' && word[i] <= 'Z')	//判断单词中是否有大写字母
			return 1;	//如果有，返回1
	}	//for
	return 0;	//没有返回0
}

//词频统计
void StatisticsData(){
	system("cls");	//清屏
	ifstream fin;	//文件读 *** 作，存储设备读取到内存中
	fin.open(file);	//关联文件file
	char 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 == ")"//word为空，放入第一个字母	=
				word ; chelse
			+=
				word ; ch//word不为空，拼接字母组成单词	}
		//if	else
		if{
			( !=word ")" //判断之前的word里面是否有单词++{	;
				count//有单词，总数+1if	(
				) <<count > MaxSize"文章单词超出统计上限，系统已退出"{
					cout << ; . endlclose
					fin();//关闭文件exit	(
					0);//退出程序system	(
					"pause");//暂停}	StatisticalWord
				(
				);word//存放到结构体数组里面}	//if
			=	";"
			word //重置word，用于存放新单词 }//else	}
		//for	//按照词典排序（选择排序） 从小到大
	;	//临时存储空间
	for
	WordFrequency temp(	int
	= 0; i < ;++ i ) sum= i;//重置min{
		min for i(	int
		= +1 j ; i < ;++ j ) sumif j(WordTransition{
			( [].WF)j<WordTransitionword( [ ].WF)min)//将单词转换成小写进行比较word=;	//得到最小单词序号
				min } j//for	//交换原始单词，词频
		=	[
		]
		temp ; WF[i]=
		WF[i] ; WF[min]=
		WF;min} //for tempfor
	(	int
	= 0; i < ;++ i ) sum= i;for{
		min ( iint
		= +1 j ; i < ;++ j ) sumif j(WordTransition{
			( [].WF)j==WordTransitionword( [ ].WF)min)//两个单词相等wordif(	WordJudge
				( [].WF)jWordJudge(word[ > ].WF)min)//大写的排前面word=;	//得到最小单词序号
					min } j//for	//交换原始单词,词频
		=	[
		]
		temp ; WF[i]=
		WF[i] ; WF[min]=
		WF;min} //for temp.
	close	(
	fin);//关闭文件}//将单词转换为唯一关键码	int
WordTransitionKey

(
)  int[string word18{
	] a=0, 0 { ,1,3,6,10,15,21,28,36,45,55,66,78,91,105,120,136};//最长识别17个字母的的单词 int=	0
	; sumkey for (int
	= 0; i < int( i . size(word));++)+= iint({
		sumkey [ ])word;i}+=int
	(
	sumkey 'z' )*[int ( a.size(word))];return;}
	//顺序表类 sumkeyclass
SeqList



public
: SeqList{
	()
		}//无参构造SeqList {(	[
		],datatype aint)//有参构造函数，初始化长度为n的顺序表 if n({	)
			<< "单词数量过多，超出线性表最大容量"n > MaxSize<<{
				cout ; } //if endlfor
			(	int
			= 0; i < ;++ i ) n[ i].{
				wf=i[]word . a;i[]word.
				wf=i[]frequency . a;i}//forfrequency}
			~	SeqList
		(

		)};//析构函数{intEmpty   (
		) ;//顺序表判空函数voidPrintList    (
		int );//遍历 *** 作，按序号依次输出各元素 nintSeqlistLocate   (
		) ;//顺序查找string wordintBinSearch  (
		) ;//折半查找string wordgetword(     int
		string );//返回单词 nintgetfre	(
		int );//返回词频 nprivate:	[

	];
		datatype wf//存放词频结构体的数组MaxSize};         //返回单词
SeqList::

getword
string (int)return[ n] {
	. wf;n}//返回词频wordint
SeqList

::
getfre (int)return[ n] {
	. wf;n}//顺序表判空函数frequencyint
SeqList

::
Empty ()if(=={
	0 )sum return 1;
		else return0
	;
		} //顺序查找int
SeqList

::
SeqlistLocate ()for(string wordint{
	= 0; i < ;++ i ) sum//依次遍历 iif({	[
		] .wf==i)//找到wordword return word;	//返回下标
			} i//for	return
	-	1
	; //未找到返回-1}//折半查找	int
SeqList

::
BinSearch  ()int,string word={
	0 mid, low = -1 high ; sum //初始查找区间是[0, sum-1] while(	<=
	) //当区间存在时low = high( {	+
		mid ) /low 2 high; //初始化中值 if(	==
		[ ]word . wf)mid//找到wordbreakword;	//退出循环
			elseif	(
		WordTransition ( )<WordTransitionword( [ ].wf)mid)//word在前半段word=-	1
			high ; mid //改变上限，gigh前移查找区间变为	[low,mid-1] else//word在后半段，或者不存在	=
		+	1
			low ; mid //改变下线，low后移查找区间变为	[mid+1,high] }//while	if
	(	<=

	) returnlow ; high//找到返回下标
		else midreturn	-
	1
		; //未找到返回-1}//输出线性表顺序表，参数n用来控制输出顺序查找还是折半查找	void
SeqList

::
PrintList (int)system( n"cls"{
	);//清屏if(	==
	1 )n ; //文件写 *** 作 内存写入存储设备 .{
		ofstream foutopen	(
		fout"outfile1.txt");<<"单词总数为："<<
		fout << ; << sum "词频" endl<<
		fout "\t" << "单词" << ; for ( endlint
		= 0; i < ;++ i) sum<< i[]{
			fout . wf<<i"\t"<<frequency [ ] . wf<<i;}word //for endl.	
		close	(
		fout);//关闭文件}//if	if
	(	==
	2 )n ; //文件写 *** 作 内存写入存储设备 .{
		ofstream foutopen (
		fout"outfile3.txt");<<"单词总数为："<<
		fout << ; << sum "词频" endl<<
		fout "\t" << "单词" << ; for ( endlint
		= 0; i < ;++ i ) sum<< i[] {
			fout . wf<<i"\t"<<frequency [ ] . wf<<i;}word //for endl.
		close	(
		fout);//关闭文件}//if	<<
	"单词总数为："	<<
	cout << ; << sum "词频" endl<<
	cout "       " << "单词" << ; for ( endlint
	= 0; i < ;++ i ) sum<< i[]
		cout . wf<<i"    "<<frequency [ ] . wf<<i;ifword ( endl==
	1 )n << "单词以及词频已经保存到文件outfile1.txt文件中"<<
		cout ; else if endl(
	== 2 )n << "单词以及词频已经保存到文件outfile3.txt文件中"<<
		cout ; system ( endl"pause"
	);//暂停}//链表类	class
LinkList


public
: LinkList{
	([
		],datatype aint)//有参构造函数，建立有n个元素的单链表 = nnew {	;
			Head //生成头结点 * Node=	,
			Node* r = HeadNULL ; s //尾指针初始化,并定义存储指针 for(	int
			= 0; i < ;++ i ) n= inew;{
				s = [ Node] 
				s->data ; a//数据域赋值i=;	//将存储节点s插入链表
				r->next = s;	//更新尾指针
				r } s//for	=
			NULL	;
			r->next //单链表建立完毕，将终端结点的指针域置空 }~	LinkList
		(
 
		)//析构函数*= {	NULL
			Node; temp //定义临时节点 while(	!=
			NULL )Head //释放单链表的每一个结点的存储空间 =;{	//暂存被释放结点
				temp = Head;	// Head指向被释放结点的下一个结点
				Head delete Head->next;	}
				//while temp}
			int	Empety
		(

		) ;//判断链表是否为空intLocate	(
		) ;//按值查找，返回下标string wordvoidPrintList	(
		) ;//遍历 *** 作，按序号依次输出各元素getdata(	int
		datatype );private n:*

	;//单链表的头指针
		Node} Head;           //返回数据域
LinkList::

getdata
datatype (int)*= n; {
	Node//指针初始化 t for Head->next(	int
	= 0; i <= ;++ i ) n= i;return
		t ; t->next}
	//判空 t->dataint

LinkList

::
Empety ()if(){
	return 1Head->next;
		//链表非空，正常返回 return0	;
	//链表为空，返回-1 }//输出单链表	void
LinkList

::
PrintList ()system("cls"{
	);//清屏*=	;
	Node//工作指针p初始化 p ; Head->next//文件写 *** 作 内存写入存储设备 .
	ofstream foutopen	(
	fout"outfile2.txt");//打开文件<<"单词总数为："	<<
	fout << ; << sum "词频" endl<<
	fout "\t" << "单词" << ; while ( endl!=
	NULL )p << .<<{
		fout "\t" p->data<<frequency . << ; p->data=word ; endl//指针p后移
		p } p->next//while	.
	close	(
	fout);//关闭文件<<"单词总数为："	<<
	cout << ; << sum "词频" endl<<
	cout "\t" << "单词" << ; * = endl;
	Node//工作指针p初始化 p1 while Head->next()
	<< .p1<<{	//p <--> p != NULL
		cout "\t" p1->data<<frequency . << ; p1->data=word ; endl//工作指针p后移，注意不能写作p++
		p1 } p1->next//while                 <<
	"单词以及词频已经保存到文件outfile2.txt文件中"	<<
	cout ; system ( endl"pause"
	);//暂停}//按值查找，返回下标	int
LinkList

::
Locate ()*=string word;{
	Node//指针p初始化 p int Head->next=   0
	; count //计数器count初始化 while(	!=
	NULL )p if (.{
		== )p->datareturnword ; word//查找成功，结束函数并返回下标 
			= count;     //p指针后移
		p ++ p->next;	}
		count//whilereturn
	-	1
	; //退出循环表明查找失败}// 线性表菜单	void
ListMenu

(
) while(true{
	)system("cls" {
		);//清屏<<"*******************基于不同策略的英文单词的词频统计和检索系统*******************"	<<
		cout ; << "---基于线性表的查找---" endl<<
		cout ; << "1.顺序查找" endl<<
		cout ; << "2.折半查找" endl<<
		cout ; << "3.返回上一级" endl<<
		cout ; << "请按相应的数字键进行选择：" endl<<
		cout ; int ; endl;
		switch n(
		cin >> n)
		case 1n:{
		SequenceMenu ( ) 
			;//顺序查找菜单break;	case
			2:
		HalfSortMenu ( ) 
			;//顺序表折半查找菜单break;	case
			3:
		return ; //结束函数 
			default:	<<
		"输入的不是有效符号，请重新输入"<< 
			cout ; system ( endl"pause" 
		);//暂停}//switch	}
		//while	}
	//顺序查找菜单	void
SequenceMenu

(
) while(true{
	)system("cls"{
		);//清屏<<"*******************基于不同策略的英文单词的词频统计和检索系统*******************"	<<
		cout ; << "---顺序查找---" endl<<
		cout ; << "1.顺序表顺序表查找" endl<<
		cout ; << "2.链表顺序查找" endl<<
		cout ; << "3.返回上一级" endl<<
		cout ; << "请按相应的数字键进行选择：" endl<<
		cout ; int ; endl;
		switch n(
		cin >> n)
		case 1n:{
		SeqListMenu ()
			;//顺序查找菜单break;		case
			2:
		LinklistSeqMenu () 
			;//链表查找菜单break;	case
			3:
		return ;//结束函数 
			default:	<<
		"输入的不是有效符号，请重新输入"<<
			cout ; system ( endl"pause"
			);//暂停break;	}
			//switch}
		//while	}
	//顺序表顺序查找菜单	void
SeqListMenu

(
) L(,{
	SeqList );WFwhile sum(true
	)system("cls"{
		);<<"*******************基于不同策略的英文单词的词频统计和检索系统*******************"<<
		cout ; << "---顺序表顺序查找---" endl<<
		cout ; << "1.词频统计" endl<<
		cout ; << "2.单词查找" endl<<
		cout ; << "3.返回上一级" endl<<
		cout ; << "请按相应的数字键进行选择：" endl<<
		cout ; int ; endl;
		switch n(
		cin >> n)
		case 1n:{
		. PrintList( 
			L1);//输出线性表顺序表词频统计break;	case
			2:
		WorLocatMenu () 
			;//顺序表顺序单词查找菜单break; case
			3:
		return ;default
			:<<
		"输入的不是有效符号，请重新输入"<< cout ; system ( endl"pause" 
			);}//switch}
		//while	return
	;	}

	//链表顺序查找菜单void
LinklistSeqMenu

(
) L(,{
	LinkList );WFwhile sum(true
	)system("cls"{
		);//清屏<<"*******************基于不同策略的英文单词的词频统计和检索系统*******************"	<<
		cout ; << "---链表顺序查找---" endl<<
		cout ; << "1.词频统计" endl<<
		cout ; << "2.单词查找" endl<<
		cout ; << "3.返回上一级" endl<<
		cout ; << "请按相应的数字键进行选择：" endl<<
		cout ; int ; endl;
		switch n(
		cin >> n)
		case 1n:{
		. PrintList( 
			L);//输出线性表链表词频统计break;	case
			2:
		LinklistLocateMenu ()
			;//链表单词查找break;	case
			3:
		return ;default 
			:<<
		"输入的不是有效符号，请重新输入"<<
			cout ; system ( endl"pause" 
			);//暂停}//switch	}
		//while	return
	;	}

	//顺序表顺序单词查找菜单void
WorLocatMenu

(
) L(,{
	SeqList );WF system sum("cls"	
	);//清屏<<"*******************基于不同策略的英文单词的词频统计和检索系统*******************"	<<
	cout ; << "---单词查找---" endl<<
	cout ; << "请输入要查找的单词：" endl;
	cout ; ;//键盘录入要查找单词
	string word=
	cin >> wordclock	(
	clock_t start ) ;//开始时间.SeqlistLocate	(
	L);=wordclock(
	clock_t end ) ;//结束时间int=	.
	SeqlistLocate i ( L)+1word; //返回下标 if(	)
	<< "此单词为："i<< {
		cout . getword ( L-1)i << ;<< "此单词的词频：" endl<<
		cout . getfre ( L-1)i << ;<< "查找该单词所花费的时间：" endl<<
		cout ( double ) (-)/end << start"秒" << CLOCKS_PER_SEC ; << "平均查找长度：" endl<<
		cout ( + 1 )sum / 2<< ; } //if endlelse
	<<	"查找失败"
	<<
		cout ; system ( endl"pause"
	);//暂停}//链表单词查找菜单	void
LinklistLocateMenu

(
) L(,{
	LinkList );WFsystem sum("cls"
	);//清屏<<"*******************基于不同策略的英文单词的词频统计和检索系统*******************"	<<
	cout ; << "---单词查找---" endl<<
	cout ; << "请输入要查找的单词：" endl;
	cout ; ;=
	string wordclock
	cin >> word(
	clock_t start ) ;//开始时间.Locate	(
	L);=wordclock(
	clock_t end ) ;//结束时间int=	.
	Locate i ( L)+1word; if ()
	<< "此单词为："i<< {
		cout . getdata ( L-1)i . <<;<<word "此单词的词频：" endl<<
		cout . getdata ( L-1)i . <<;<<frequency "查找该单词所花费的时间：" endl<<
		cout ( double ) (-)/end << start"秒" << CLOCKS_PER_SEC ; << "平均查找长度：" endl<<
		cout ( + 1 )sum / 2<< ; } //if endlelse
	<<	"查找失败"
	<<
		cout ; system ( endl"pause"
	);//暂停}//顺序表折半查找菜单	void
HalfSortMenu

(
) L(,{
	SeqList );WFwhile sum(true
	)system("cls"{
		);//清屏<<"*******************基于不同策略的英文单词的词频统计和检索系统*******************"	<<
		cout ; << "---基于顺序表的折半查找---" endl<<
		cout ; << "1.词频统计" endl<<
		cout ; << "2.单词查找" endl<<
		cout ; << "3.返回上一级" endl<<
		cout ; << "请按相应的数字键进行选择：" endl<<
		cout ; int ; endl;
		switch n(
		cin >> n)
		case 1n:{
		. PrintList(
			L2);//折半查找，输出break;	case
			2:
		HalfdLocateMenu () 
			;//折半查找break;	case
			3:
		return ;//退出函数
			default:	<<
		"输入的不是有效符号，请重新输入"<< 
			cout ; system ( endl"pause" 
			);//暂停}//switch	}
		//while	}
	//顺序表折半查找菜单	void
HalfdLocateMenu

(
) L(,{
	SeqList );WFsystem sum("cls"
	);//清屏<<"*******************基于不同策略的英文单词的词频统计和检索系统*******************"	<<
	cout ; << "---单词查找---" endl<<
	cout ; << "请输入要查找的单词：" endl;
	cout ; ;=
	string wordclock
	cin >> word(
	clock_t start ) ;//开始时间.BinSearch	(
	L);=wordclock(
	clock_t end ) ;//结束时间int=	.
	BinSearch i ( L);//返回下标wordif(	0
	) <<i >= "此单词为："<< {
		cout . getword ( L)<<;i<< "此单词的词频：" endl<<
		cout . getfre ( L)<<;i<< "查找该单词所花费的时间：" endl<<
		cout ( double ) (-)/end << start"秒" << CLOCKS_PER_SEC ; << "平均查找长度：" endl<<
		cout double ( ( log(double()+1sum) / log( 2 ))-1) << ;} //if endlelse
	<<	"查找失败"
	<<
		cout ; system ( endl"pause"
	);//暂停}//开放地址哈希表类	class
HashTable


public
: HashTable{
	()
		;//构造函数，初始化空散列表~HashTable	(
		)};//析构函数{intInsert	(
		) ;//插入datatype aintSearch	(
		) ;//查找string wordGet(	int
		datatype );void aPrint(
		) ;//输出private:	int
	H(
		int );//哈希函数(散列函数) k[]	;
		datatype ht//散列表MaxSize};	//构造函数
HashTable::

HashTable
()for(int{
	= 0; i < ;++ i ) MaxSize[ i].{
		ht=i0;key //关键码初始化 []	.
		ht=i"";word [ ].
		ht=i0;frequency // 0表示该散列单元为空 }//for	}
	//哈希函数，除留余数法	int
HashTable

::
H (int)return% k;{
	} k //输出函数 MaxSizevoid
HashTable

::
Print ()system("cls"{
	);//清屏;//文件写 *** 作 内存写入存储设备	.
	ofstream foutopen	(
	fout"outfile5.txt");//打开文件<<"单词总数为："	<<
	fout << ; << sum "词频" endl<<
	fout "\t" << "单词" << ; for ( endlint
	= 0; i < ;++ i ) MaxSizeif i([{
		] .ht!=i0)key << []{
			fout . ht<<i"\t"<<frequency [ ] . ht<<i;<<word [ endl]
			cout . ht<<i"\t"<<frequency [ ] . ht<<i;}word //if endl}
		system	(
	"pause"
	);//暂停}//查找函数	int
HashTable

::
Search ()int=string wordWordTransitionKey{
	( key ) ;//将单词转化为关键码wordint=	H
	( i ) ;//计算散列地址，设置比较的起始位置keywhile(	[
	] .ht!=i0)key if ([{
		] .ht==i)returnword ; word//查找成功 
			else i=         (
		+ 
			i 1 )i % ;//向后探测一个位置 } MaxSize//while	return
	0	;
	//查找失败 }//插入函数	int
HashTable

::
Insert ()int=datatype f_word_keyWordTransitionKey{
	( key . );f_word_key//将单词转化为关键码wordint=H
	( i ) ;//计算散列地址，设置比较的起始位置keywhile(                        [
	] .ht!=i0)key //寻找空的散列单元 =({	+
			i 1 )i % ;//向后探测一个位置 } MaxSize//while	[
	]	.
	ht=i;//关键码赋值key [ key]	.
	ht=i.;word //单词赋值 f_word_key[word]	.
	ht=i.;frequency //词频赋值 f_word_keyreturnfrequency;	//返回插入位置 
	} i//获取单词以及频率	HashTable
::

Get
datatype  (int)return[ a]{
	; ht}a//链地址法哈希表类class
HashTableLink



public
: HashTableLink{
	()
		;//构造函数，初始化开散列表~HashTableLink	(
		);//析构函数，释放同义词子表结点intInsert	(
		) ;//插入datatype fword*Search	(
		Node) ;//查找string wordvoidPrint	(
		) ;//输出private:	int

	H(
		int );//散列函数 k*[	]
		Node; ht//开散列表MaxSize};	//构造函数
HashTableLink::

HashTableLink
()for(int{
	= 0; i < ;++ i ) MaxSize[ i]=
		htNULLi; //链式存储结构指针置空 }//析构函数，释放空间	HashTableLink
::

~
HashTableLink ( )*=NULL{
	Node, p * =NULL ; q for (int
	= 0; i < ;++ i ) MaxSize= i[]{
		p ; ht=i;//用来储存p
		q while p(	!=
		NULL )p //p非空 =;{	//p后移
			p delete p->next;	//删除q
			= q;	}
			q //while p}
		//for	}
	//除留余数法-散列函数	int
HashTableLink

::
H (int)return% k;{
	} k //输出到屏幕和文本文件outfile6.txt MaxSizevoid
HashTableLink

::
Print ()system("cls"{
	);//输出到文件outfile中;.
	open
	ofstream fout(
	fout"outfile6.txt");<<"单词总数为："<<
	fout << ; << sum "词频" endl<<
	fout "    " << "单词" << ; * = endlNULL
	Node; p for (int
	= 0; i < ;++ i ) MaxSize= i[]
	{
		p ; htwhilei(!=
		NULL )p << .<<
		{
			fout "\t" p->data<<frequency . << "\t" p->data<<word ; << . endl<<
			cout "\t" p->data<<frequency . << "\t" p->data<<word ; = ; endl}
			p } p->nextsystem
		(
	"pause"
	);}//查找函数*

HashTableLink

::
NodeSearch ()int=string wordWordTransitionKey{
	( k ) ;//转化为关键码wordint=	H
	( j ) ;//计算散列地址k*=	[
	Node] p ; ht//指针p初始化jwhile(	!=
	NULL )p //p非空 if({	.
		== )p->datareturnword ; word//已找到返回指针
			else p=	;
		//p后移
			p } p->next//while	return
	nullptr	;
	//未找到返回空指针 }//插入函数(前插法)	int
HashTableLink

::
Insert ()int=datatype fwordWordTransitionKey{
	( k . );fword//转化为关键码word.=	;
	fword//给关键码赋值key int k=	H
	( j ) ;//计算散列地址k*=	Search
	Node( p . );fword//调用查找函数wordif(	!=
	nullptr )p //p非空，表示该内容已经插入过了 return-	1
		; //已存在元素k，无法插入 else//p为空，表示该内容未插入	=
	new {	;
		p //生成新节点 . Node=	.
		p->data;key //关键码赋值 fword.key=	.
		p->data;frequency //词频赋值 fword.frequency=	.
		p->data;word //单词赋值 fword=word[	]
		p->next ; ht//新节点插入ht[j]j[]	=
		ht;j//更新节点 return p1	;
		//插入成功标志  }}	//哈希表菜单
	void
HashMenu

(
) while(true{
	)system("cls"{
		);//清屏<<"*******************基于不同策略的英文单词的词频统计和检索系统*******************"	<<
		cout ; << "---哈希表---" endl<<
		cout ; << "1.开放地址法哈希查找" endl<<
		cout ; << "2.链地址法哈希查找" endl<<
		cout ; << "3.返回上一级" endl<<
		cout ; << "请按相应的数字键进行选择：" endl<<
		cout ; int ; endl;
		switch n(
		cin >> n)
		case 1n:{
		OpenHashLocate ( ) 
			;//开放地址法哈希查找break;	case
			2:
		LinkHashLocate ( ) 
			;//链地址法哈希查找break;	case
			3:
		return ; //退出函数 
			default:	<<
		"输入的不是有效符号，请重新输入"<< 
			cout ; system ( endl"pause" 
			);}//switch}
		//while	return
	;	}
	//开放地址法哈希查找菜单void
OpenHashLocateMenu

(
) ;for({
	HashTable HTint
	= 0; i < ;++ i ) sum. iInsert(
		HT[])WF;i//把数据插入到哈希表中double=	/
	; bulkfactor //装填因子 sum system MaxSize(	"cls"
	);//清屏<<"*******************基于不同策略的英文单词的词频统计和检索系统*******************"	<<
	cout ; << "---单词查找---" endl<<
	cout ; << "请输入要查找的单词：" endl;
	cout ; ;=
	string wordclock
	cin >> word(
	clock_t start ) ;//开始时间.Search	(
	HT);=wordclock(
	clock_t end ) ;//结束时间int=	.
	Search i ( HT);//获取散列地址wordif(	)
	<< "此单词为："i<< {
		cout . Get ( HT).<<i;<<word "此单词的词频：" endl<<
		cout . Get ( HT).<<i;<<frequency "查找该单词所花费的时间：" endl<<
		cout ( double ) (-)/end << start"秒" << CLOCKS_PER_SEC ; << "平均查找长度：" endl<<
		cout ( 1 + 1/ ( 1 - )) / bulkfactor2<< ; } //if endlelse
	<<	"查找失败"
	<<
		cout ; system ( endl"pause"
	);//暂停}//开放地址法哈希查找	void
OpenHashLocate

(
) ;for({
	HashTable HTint
	= 0; i < ;++ i ) sum. iInsert(
		HT[])WF;i//把数据插入到哈希表中while(	true
	)system("cls"{
		);//清屏<<"*******************基于不同策略的英文单词的词频统计和检索系统*******************"	<<
		cout ; << "---基于开放地址法的哈希查找---" endl<<
		cout ; << "1.词频统计" endl<<
		cout ; << "2.单词查找" endl<<
		cout ; << "3.返回上一级" endl<<
		cout ; << "请按相应的数字键进行选择：" endl<<
		cout ; int ; endl;
		switch n(
		cin >> n)
		case 1n:{
		. Print ( 
			HT);//词频统计break; case
			2:
		OpenHashLocateMenu ( ) 
			;//开放地址法的哈希查找菜单break;	case
			3:
		return ; default
			:<<
		"输入的不是有效符号，请重新输入"<< 
			cout ; system ( endl"pause" 
			);//暂停}//switch	}
		//while	}
	//链地址法哈希查找	void
LinkHashLocate

(
) ;for({
	HashTableLink HTint
	= 0; i < ;++ i ) sum. iInsert(
		HT[])WF;i//把数据插入到哈希表while(	true
	)system("cls"{
		);//清屏<<"*******************基于不同策略的英文单词的词频统计和检索系统*******************"	<<
		cout ; << "---基于链地址法的哈希查找---" endl<<
		cout ; << "1.词频统计" endl<<
		cout ; << "2.单词查找" endl<<
		cout ; << "3.返回上一级" endl<<
		cout ; << "请按相应的数字键进行选择：" endl<<
		cout ; int ; endl;
		switch n(
		cin >> n)
		case 1n:{
		. Print( 
			HT);//词频统计break; case
			2:
		LinkHashWordLocateMenu ()
			;//单词查找菜单break;	case
			3:
		return ;//退出函数 
			default:	<<
		"输入的不是有效符号，请重新输入"<< 
			cout ; system ( endl"pause" 
			);//暂停}//switch	}
		//while	}
	//开放地址法哈希查找菜单	void
LinkHashWordLocateMenu

(
) ;for({
	HashTableLink HTint
	= 0; i < ;++ i ) sum. iInsert(
		HT[])WF;i//把数据插入到哈希表double=	/
	; load_factor //散列表的装填因子 sum system MaxSize("cls"
	);<<"*******************基于不同策略的英文单词的词频统计和检索系统*******************"<<
	cout ; << "---单词查找---" endl<<
	cout ; << "请输入要查找的单词：" endl;
	cout ; ;=
	string wordclock
	cin >> word(
	clock_t start ) ;//开始时间.Search	(
	HT);=wordclock(
	clock_t end ) ;//结束时间*=	.
	NodeSearch p ( HT);//返回目标指针wordif(	!=
	NULL )p << "此单词为："<< {
		cout . << ; p->data<<word "此单词的词频：" endl<<
		cout . << ; p->data<<frequency "查找该单词所花费的时间：" endl<<
		cout ( double ) (-)/end << start"秒" << CLOCKS_PER_SEC ; << "平均查找长度：" endl<<
		cout 1 + ( ) / 2load_factor<< ; } //if endlelse
	<<	"查找失败"
	<<
		cout ; system ( endl"pause"
	);//暂停}//二叉排序树类	class
BiSortTree

public
: BiSortTree{
	([
		],datatype aint); //带参构造函数，对树初始化 n~BiSortTree	(
		)//析构函数Release({	)
			;}root*InsertBST 
		(              
		          
		BiNode) //函数重载，插入数据域datareturndatatype dataInsertBST{	(
			, );root} data*SearchBST
		( 

		BiNode) //函数重载,查找值为word的结点returnstring wordSearchBST{	(
			, );root} wordvoidprintf
		(  
		) ;//输出函数private:	void
	Release(
		* );BiNode//释放空间 bt*InsertBST	(
		BiNode* ,)BiNode; bt//插入数据域data datatype data*SearchBST	(
		BiNode* ,)BiNode; bt//查找值为word的结点 string wordvoidInOrder	(
		* );BiNode//中序遍历函数调用 bt*;	//二叉排序树的根指针
		BiNode} root;	//构造函数
BiSortTree::

BiSortTree
([],datatype aint)= NULL n; {
	root //根指针置空 for(	int
	= 0; i < ;++ i ) n= iInsertBST(
		root , []root) a;i//遍历，插入数据}//输出函数	void
BiSortTree

::
InOrder  (*)//递归输出二叉排序树BiNode; bt//文件写 *** 作 内存写入存储设备{	.
	ofstream foutopen	(
	fout"outfile4.txt",::|:: ios_base)out ; ios_base//打开文件并将内容追加到文件尾appif(	==
	NULL )bt //递归调用的结束条件,根指针为空 return;	//退出函数     
		elseInOrder	(
	){
		;//中序递归遍历bt的左子树bt->lchild<<.	<<
		cout "\t" bt->data<<frequency . << ; bt->data//访问根结点bt的数据域，输出到屏幕word << endl.	<<
		fout "\t" bt->data<<frequency . << ; bt->data//访问根结点bt的数据域，输出到文件word . endlclose (
		fout);//关闭文件InOrder(	)
		;//中序递归遍历bt的右子树  bt->rchild}//else	}
	//输出二叉排序树到屏幕和outfile4.txt	void
BiSortTree

::
printf ()system("cls" {
	);//清屏;//文件写 *** 作 内存写入存储设备	.
	ofstream foutopen	(
	fout"outfile4.txt");//打开文件<<"单词总数为："<<
	fout << ; << sum "词频" endl<<
	fout "\t" << "单词" << ; InOrder ( endl)
	;//输出函数rootsystem(	"pause"
	);//暂停return;	//退出函数
	}//递归查找函数，返回指针	*
BiSortTree

::
BiNodeSearchBST (*,)BiNodeif bt( string word=={
	NULL )bt return NULL; 
		//未找到，返回NULL if(	.
	== )bt->datareturnword ; word//找到word，返回该指针 
		else btif	(
	. ) //数据大于wordbt->datareturnword > wordSearchBST	(
		, );bt->lchild//递归查找左子树 wordelse//数据小于word	return
	SearchBST	(
		, );bt->rchild//递归查找右子树 word}//递归插入函数	*
BiSortTree

::
BiNodeInsertBST (*,)BiNodeif bt( datatype data=={
	NULL )bt //找到插入位置 *={	new
		BiNode; s //生成一个新的储存空间 = BiNode;	//为数据域赋值
		s->data = dataNULL	;
		s->lchild //左孩子指针置空 =NULL	;
		s->rchild //右孩子指针置空 =;	//根指针更新
		bt return s;	//返回根指针
		} bt//if	else
	if	(
	WordTransition ( .)WordTransitionbt->data(word. > ))data//根节点数据大于要插入的数据word=InsertBST{	(
		bt->lchild , );bt->lchild//更新左孩子指针 datareturn;	//返回根指针
		} bt//else if	else
	//根节点数据小于要插入的数据	=
	InsertBST{	(
		bt->rchild , );bt->rchild//更新有孩子指针 datareturn;	//返回根指针
		} bt//else	}
	//递归析构函数	void
BiSortTree

::
Release (*)ifBiNode( bt=={
	NULL )bt return ;//根指针为空直接退出
		elseRelease	(
	) {
		;//释放左子树bt->lchildRelease(	)
		;//释放右子树bt->rchilddelete;	//释放根结点
		} bt}	// 二叉排序树菜单
	void
BiTreeMenu

(
) while(true{
	)system("cls"{
		);//清屏<<"*******************基于不同策略的英文单词的词频统计和检索系统*******************"	<<
		cout ; << "---二叉排序树查找---" endl<<
		cout ; << "1.二叉排序树的顺序查找" endl<<
		cout ; << "2.返回上一级" endl<<
		cout ; << "请按相应的数字键进行选择：" endl<<
		cout ; int ; endl;
		switch n(
		cin >> n)
		case 1n:{
		BitreeLocateMenu () 
			;//二叉排序树查找菜单break;		//退出switch
			case2	:
		return ;//退出函数 
			default:	<<
		"输入的不是有效符号，请重新输入"<<
			cout ; system ( endl"pause" 
			);//暂停}//switch	}
		//while	}
	//二叉排序树的顺序查找菜单	void
BitreeLocateMenu

(
) B(,{
	BiSortTree );WFwhilesum(true
	)system("cls"{
		);//清屏<<"*******************基于不同策略的英文单词的词频统计和检索系统*******************"	<<
		cout ; << "---基于二叉排序树的顺序查找---" endl<<
		cout ; << "1.词频统计" endl<<
		cout ; << "2.单词查找" endl<<
		cout ; << "3.返回上一级" endl<<
		cout ; << "请按相应的数字键进行选择：" endl<<
		cout ; int ; endl;
		switch n(
		cin >> n)
		case 1n:{
		. printf( 
			B);break;case 
			2:
		BitreeWordLocMenu () 
			;//二叉排序树查找单词菜单break;	case
			3:
		return ;//退出函数
			default:	<<
		"输入的不是有效符号，请重新输入"<< 
			cout ; system ( endl"pause" 
			);//暂停}//switch	}
		//while	}
	//二叉排序树查找单词菜单	void
BitreeWordLocMenu

(
) B(,{
	BiSortTree );WFsystemsum("cls"
	);//清屏<<"*******************基于不同策略的英文单词的词频统计和检索系统*******************"	<<
	cout ; << "---单词查找---" endl<<
	cout ; << "请输入要查找的单词：" endl;
	cout ; ;=
	string wordclock
	cin >> word(
	clock_t start ) ;//开始时间.SearchBST	(
	B);=wordclock(
	clock_t end ) ;//结束时间*=	NULL
	BiNode; p //指针置空 =.	SearchBST
	p ( B);ifword(!=
	NULL )p << "此单词为："<< {
		cout . << ; p->data<<word "此单词的词频：" endl<<
		cout . << ; p->data<<frequency "查找该单词所花费的时间：" endl<<
		cout ( - ) /end << start"秒" << CLOCKS_PER_SEC ; << "平均查找长度：" endl<<
		cout << ; } sum //if endlelse
	<<	"查找失败"
	<<
		cout ; system ( endl"pause"
	);//暂停}	

六、总结

这个程序有这几个问题
1、输出查找时间，因为查找时间太短，精度不够所以输出的都是0
2、哈希表写入文件时是乱序写入，我没有重新排序，想要排序在写入文件前边排下序就行