一、实验目的
二、设计内容
三、测试数据
四、设计思路
五、代码内容
- 1、函数运行时间方法一
- 2、函数运行时间方法二
- 3、代码实现
六、总结
一、实验目的
1、掌握基于线性表、二叉排序树和散列表不同存储结构的查找算法。
2、掌握不同检索策略对应的平均查找长度(ASL)的计算方法,明确不同检索策略的时间性能的差别。
二、设计内容
一篇英文文章存储在一个文本文件中,然后分别基于线性表、二叉排序树和哈希表不同的存储结构,完成单词词频的统计和单词的检索功能。
同时计算不同检索策略下的平均查找长度ASL,通过比较ASL的大小,对不同检索策略的时间性能做出相应的比较分析(比较分析要写在实习报告中的“收获和体会”中)。
- 读取一篇包括标点符号的英文文章(InFile.txt),假设文件中单词的个数最多不超过5000个。
从文件中读取单词,过滤掉所有的标点。
- 分别利用线性表(包括基于顺序表的顺序查找、基于链表的顺序查找、基于顺序表的折半查找)、二叉排序树和哈希表(包括基于开放地址法的哈希查找、基于链地址法的哈希查找)总计6种不同的检索策略构建单词的存储结构。
- 不论采取哪种检索策略,完成功能均相同。
(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、哈希表写入文件时是乱序写入,我没有重新排序,想要排序在写入文件前边排下序就行
欢迎分享,转载请注明来源:内存溢出
评论列表(0条)