提示：文章写完后，目录可以自动生成，如何生成可参考右边的帮助文档

一、实验目的

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和输出查找所花费的时间。如果查找失败，则输出“查找失败”的提示。

实验提示：不同的检索策略所采取的数据结构不一样，算法实现的过程不一样，但查找结果是一样的。

三、测试数据

事先将一篇英文文章存储在文件InFile.txt中，例如下图所示：

四、源码 

#include
#include     
#include    
#include
#include
#include
#include   
#include 
using namespace std;
#define MAXN 5005
#define CLOCKS_PER_SEC 1000
int sum;
//调整时间精度的函数 
BOOL WINAPI QueryPerformanceFrequency(
  _Out_  LARGE_INTEGER *lpFrequency
);
BOOL WINAPI QueryPerformanceCounter(
  _Out_  LARGE_INTEGER *lpPerformanceCount
);
//时间类 
 
class stop_watch
{
	public:
	    stop_watch()
	        : elapsed_(0)
	    {
	        QueryPerformanceFrequency(&freq_);    ///返回硬件支持的高精度计数器的频率 
	    }
	    ~stop_watch(){}    //时间停止，析构函数 
		
		 
	    void start()
	    {
	        QueryPerformanceCounter(&begin_time_);    ///是返回定时器的频率 ，获取时间 
	    }
	    void stop()
	    {
	        LARGE_INTEGER end_time;
	        QueryPerformanceCounter(&end_time);                      //这里控制时间 ，获取时间 
	        elapsed_ += (end_time.QuadPart - begin_time_.QuadPart) * 10000000 / freq_.QuadPart;
	    }
	    void restart()
	    {
	        elapsed_ = 0;
	        start();
	    }
	    //微秒
	    double elapsed()
	    {
	        return static_cast(elapsed_);
	    }
	    //毫秒
	    double elapsed_ms()
	    {
	        return elapsed_ / 1000.0;
	    }
	    //秒
	    double elapsed_second()
	    {
	        return elapsed_ / 1000000.0;
	    }
	private:
	    LARGE_INTEGER freq_;
	    LARGE_INTEGER begin_time_;
	    long long elapsed_;
};
typedef struct w{
	char ch[30];      //单词数组 
	int num;         //出现频率 
}word;
word words[MAXN];      //结构数组 
typedef struct ss{      //顺序表，哈希表 
	word *r;            //数据域 
	int len;             // 顺序表长度 
}SqList;
typedef struct LNode{     //链表，哈希表 
	word data;           //数据域 
	struct LNode *next;      //下一结点 
}LNode, *Linklist;
typedef struct BSTNode{    //二叉排序树 
	word data;           //数据域 
	struct BSTNode *lch, *rch;     //下一左节点， 下一右节点 
}BSTNode, *BSTree;
	void HomePage();                    // 主目录            //一级目录 
	void Linearlist();                  //    //二级目录
	void SqSearch();                    //    //三级目录
	void BiSearch();                  //    //四级目录
	void Sq_SqSearch();                //  基于顺序表的顺序查找
	void Link_SqSearch();              //  基于链表的顺序查找 
	void BisortTree();                    // 基于二叉排序树的查找
	void HashTable();                    // 基于哈希表的查找
	void Openad_Hash();                   // 基于开放地址法的哈希查找
	void Linkad_Hash();                    // 基于链地址法的哈希查找
	void readfile(char essay[]);             // 读取文件  
	void Insert(BSTree &T,word e);                  // 二叉树插入 
	void MTraverse(BSTree &T,FILE *fp);              // 中序遍历将二叉排序树从小到大输出 
	void Hash(SqList &H,char *key,int k);               // 哈希表，开放链地址
	void Hash2(Linklist H[],char *key,int k);               //   链地址法的数据插入 
	void WordSearch1();                              // 基于顺序表的顺序查找  单词查找
	void WordSearch2();                           // 基于链表的顺序查找  单词查找
	void WordSearch3();                          // 基于顺序表的折半查找  单词查找
	void WordSearch4();                              // 基于二叉排序树查找  单词查找 
	void WordSearch5();                                  // 基于开放地址法的哈希查找  单词查找
	void WordSearch6();                                   // 基于链地址法的哈希查找  单词查找 
	void WordfreStatistic1();              // 基于顺序表的顺序查找 词频统计
	void WordfreStatistic2();                      // 基于链表的顺序查找 词频统计
	void WordfreStatistic3();                     // 基于顺序表的折半查找 词频统计
	void WordfreStatistic4();                       // 基于二叉排序树的查找 词频统计
	void WordfreStatistic5();                         // 基于开放地址法的哈希查找 词频统计 
	void WordfreStatistic6();                             // 基于链地址法的哈希查找 词频统计 
	void QSort1(SqList &L,int low,int high);         // 顺序表排序 
	void QSort2(Linklist pbegin,Linklist pend);        //链表排序 
	void QSort3(SqList &H,int low,int high);                // 开放连地址法排序
	int Partition1(SqList &L,int low,int high);            // 排序 
	Linklist Partition2(Linklist pbegin,Linklist pend);         //排序 
	int Partition3(SqList &H,int low,int high);         // 排序 
	int Search_Seq(SqList &L,char c[]);             //   顺序表
	LNode* Search_link(Linklist &L,char c[]);             // 基于链表查找 单词
	int Search_Bin(SqList &L,char c[]);            // 折半查找单词
	BSTree Search_BST(BSTree T,char c[]);               // 基于二叉树的查找单词
	int Search_openhash(SqList &H,char *c);                // 开放链地址的查找单词 
	int Search_linkhash(Linklist H[],char *c);             // 基于链地址的查找单词
	float ASL(BSTNode *T);                              //计算ASL 
void title(){        //标题头 
	cout<>a;
    return a;
} 
        
void  HomePage(){       //一级主目录单 
	title();
	cout<<"       *           1.基于线性表的查找           *"<= 0) 
			--high;
		strcpy(L.r[low].ch, L.r[high].ch);
		L.r[low].num = L.r[high].num;
        while(low < high && stricmp(L.r[low].ch, t) <= 0) 
			++low;
		strcpy(L.r[high].ch, L.r[low].ch);
		L.r[high].num = L.r[low].num;		
	}
	strcpy(L.r[low].ch, t);      //将t复制给L.r[low].ch 
	L.r[low].num = k;
	return low;
}
//基于链表的顺序查找 词频统计 
void WordfreStatistic2(){         
	char essay[MAXN*20];
	readfile(essay);                   //读入数组，存入缓存区 
	FILE *fp;
	Linklist L,r,p;                  
    L = new LNode;
	L->next = NULL;
	r = L;
	for(int i=0; idata = words[i];
		p->next = NULL;
		r->next = p;
		r = p;
	}
	QSort2(L->next, r);
	fp = fopen("OutFile2.txt", "w");
	if(!fp)
	    cout<<"打开文件OutFile2.txt失败！"<next;
    for(int i=0; idata.ch, L->data.num);                  //将单词、单词频数读到文件中
	   L = L->next; 
    }
    fclose(fp);
    cout<next, pend);		                      //递归调用 
	} 
}
             /// 字符交换 
LNode* Partition2(LNode* pbegin, LNode* pend){
	char t[20], w[20];
	strcpy(t, pbegin->data.ch);              //将字符串复制给t 
    Linklist p = new LNode;
    Linklist q = new LNode;
    p = pbegin;
    q = p->next;
	while(q != pend){
        if(stricmp(q->data.ch, t) < 0){        //比较字符串，如果指针所指的字符串小于0， 那么交换p和q两个链表的字符串和频率 
        	p = p->next;
        	strcpy(w, p->data.ch);    
        	strcpy(p->data.ch, q->data.ch);
        	strcpy(q->data.ch, w);
        	swap(p->data.num, q->data.num);
		}
		q = q->next;
	}
    strcpy(w, p->data.ch);                          //将p指针的字符复制给w数组 
    strcpy(p->data.ch, pbegin->data.ch);               //将字符复制给p指针 
    strcpy(pbegin->data.ch, w);                  //交换字符 
    swap(p->data.num, pbegin->data.num);      //交换 频率 
	return p;
}
//基于顺序表的折半查找 词频统计 存储结构和顺序表的顺序查找一样即可
void WordfreStatistic3(){         
	char essay[MAXN*20];
	readfile(essay);              // 读入数组，存入缓存区
	FILE *fp;
	SqList L;
	L.len = sum;
	L.r = new word[MAXN];
	for(int i=0; idata = e;
		T->lch = NULL;
		T->rch = NULL;
	}
	else{
		if(stricmp(T->data.ch, e.ch) > 0)     //如果根节点不为空，那么比较单词的大小和该结点单词的大小，若该结点的单词大于单词，则进入左结点 
			Insert(T->lch, e);
		else
			Insert(T->rch, e);             //反之进入右节点 
	}
}
//中序遍历将二叉排序树从小到大输出 
void MTraverse(BSTree &T, FILE *fp){   
	if(T == NULL)
		return;
	else{
		MTraverse(T->lch, fp);
        fprintf(fp,"%s         %dtn",T->data.ch, T->data.num);
		MTraverse(T->rch, fp);
	}
}
//基于开放地址法的哈希查找 词频统计 
void WordfreStatistic5(){         
	char essay[MAXN*20];
	readfile(essay);
	FILE *fp;
	SqList H;
	H.len = sum;
	H.r = new word[MAXN];
	for(int i=0; i= 0) --high;            /// high位置的字符大于t（low）位置的字符，high-- 
		strcpy(H.r[low].ch, H.r[high].ch);             //将哈希表最大位置的字符复制给位置最小的 
		H.r[low].num = H.r[high].num;                       //频率复制 
        while(low < high && stricmp(H.r[low].ch, t) <= 0) ++low;             /// low位置的字符小于t位置的字符，++low 
		strcpy(H.r[high].ch, H.r[low].ch);             // 将low位置的字符复制给high位置 
		H.r[high].num = H.r[low].num;		           // 频率复制 
	}
	strcpy(H.r[low].ch, t);             //更新low位置的字符和频率 
	H.r[low].num = k;
	return low;               //返回最小值 
}
//开放连地址法排序 
void QSort3(SqList &H, int low, int high){
	int piv;
	if(low < high){
		piv = Partition3(H, low, high);         ///选出最小位置 
        QSort3(H, low, piv-1);            //递归调用 
		QSort3(H, piv+1, high);		      //递归调用 
	} 
}
//基于链地址法的哈希查找 词频统计 
void WordfreStatistic6(){         
	char essay[MAXN*20];
	readfile(essay);           // 读入数组，存入缓存区
	FILE *fp;
	Linklist H[MAXN], L, l, r;
	L = new LNode;
	l = new LNode;
	L->next = NULL;
	l = L;
	for(int i=0; inext = NULL;
	}
	for(int i=0; inext;
		while(H[i]){
			L->next = H[i];   
			H[i] = H[i]->next;
			L = L->next; 
		}
	} 
	QSort2(l->next, L);                //排序 
	fp = fopen("OutFile6.txt", "w");    cout<<"完成"<next->data.ch, l->next->data.num);     //将单词、单词频数读到文件中
	   l = l->next; 
    }
    fclose(fp);
    cout<next != nullptr){             //p指针指向的表结点存在数据了就后移一个结点 
		p = p->next;         //p后移  
	}
	Linklist q = new LNode;
	strcpy(q->data.ch, t);           //将单词复制给q的数据域 
	q->data.num = k;                //词频赋值给q  
	q->next = NULL;
	p->next = q; 
	
}
   //基于顺序表的顺序查找  单词查找 
void WordSearch1(){    
	//system("cls");
	title();
	cout<<"       *         -------单词查找-------         *"<>c;
	watch.start();         //查找时间计时开始 
	k = Search_Seq(L, c);  /// 查找单词所在位置 
    watch.stop();          //查找时间计时停止 
	if(k!=-1){
		cout<<"       此单词的词频为："<next=NULL;
	r=L;
	for(int i=0; idata=words[i];
		p->next=NULL;
		r->next=p;
		r=p;
	}
	cout<<"       *                                        *"<>c;
	pn = new LNode;
	watch.start(); 
	pn = Search_link(L, c);
    watch.stop();
	if(pn){
		cout<<"       此单词的词频为："<data.num<next;                 //p指向首元结点 
    while(p && stricmp(p->data.ch, c) != 0){
    	p = p->next;
	}	
	return p;	
}
//基于顺序表的折半查找  单词查找 
void WordSearch3(){    
	//system("cls");
	title();
	cout<<"       *         -------单词查找-------         *"<>c;
    watch.start(); 
	k = Search_Bin(L, c);
    watch.stop();
	if(k){
		double a = log(sum+1)/log(2);
		cout<<"       此单词的词频为："< 0)  high = mid-1;
		else low = mid+1;
	}
	return 0;	
}
//基于二叉排序树查找  单词查找 
void WordSearch4(){    
	//system("cls");
	title();
	cout<<"       *         -------单词查找-------         *"<>c;
	BSTree t = NULL;
    watch.start(); 
	t = Search_BST(T,c);
    watch.stop();
	if(t){
		cout<<"       此单词的词频为："<data.num<data.ch, c) > 0) 
		return Search_BST(T->lch, c);
	else 
		return Search_BST(T->rch, c);
}
    //计算ASL 
float ASL(BSTNode* T){
	BSTNode *Q[MAXN], *p;
	int rear, front, h, end, n=0;  //h为层数，end为每层最后位置，n为节点个数
	float s=0;  //总次数
	if(!T) 
		return 0;   
	front=rear=0;
	Q[rear++] = T;
	h = 1;   //设初值 
	end = rear; 
	while(front != rear){
		p = Q[front++]; //出队列 ，并记录结点个数 
		n++;          
		s = s+h;
		if(p->lch) Q[rear++]=p->lch;
		if(p->rch) Q[rear++]=p->rch;
		if(front == end){
			end = rear;
			h++;
		}
	}
	return s/n;
}
//基于开放地址法的哈希查找  单词查找 
void WordSearch5(){    
	//system("cls");
	title();
	cout<<"       *         -------单词查找-------         *"<>c;
	watch.start(); 
	k = Search_openhash(H,c);
    watch.stop();
    int a = sum;
    for(int i=0; inext = NULL;
	l = L;
	for(int i=0; inext = NULL;
	}
	for(int i=0; i>c;
	a = sum;
	watch.start(); 
	k = Search_linkhash(H, c);
    watch.stop();
    double b = (double) sum/a;
	if(k != 0){
		cout<<"       此单词的词频为："<next;
	while(H[hash]){
		if(stricmp(H[hash]->data.ch, t)==0){
            return H[hash]->data.num;
		}
		H[hash] = H[hash]->next;
		sum--;
	}
	return 0;
}
int main(){
	HomePage();
	return 0;
} 

五、实验结果

线性表查找单词：

链表查找单词：

折半查找：

二叉树查找：

开放地址查找：

链地址查找：

查找失败：