数据结构报告-实现对字典的查找

数据结构课程设计报告主题：实现字典的查找学号：班级：191142姓名：指导老师：欢迎下载 欢迎下载 15内容概要(1)题目要求；(2)实现字典的查找的要点；(3)函数模块及各函数可实现的功能简介;(4)具体的源代码；(5)使用说明；(6)实验心得；一：题目要求如下：采用分块查找，哈希表查找，二叉排序树查找等不同方法实现对字典的查找，并分析不同查找方法的效率。二：构思要点：.定义一个Dictionary结构：里面包含单词和单词意义属性：structDictionary{stringword;stringpara;}；.定义一个管理器类Manage,里面包含Dictionary类型的向量容器，和读取dictionary.8的Readtxt(),以及二叉搜索树查找BiSearchTreesearch(),分块查找Blocksearch()和哈希表查找HashTablesearch(悻功能函数：classManage{private:vector<Dictionary>Dic;public:voidReadtxt();voidBiSearchTreesearch();voidBlocksearch();voidHashTablesearch();};.各个功能函数的详细代码：voidManage::Readtxt()：读取dictionary.txt里的单词表voidManage::Readtxt(){inti=0;stringa,b;Dictionaryd;ifstreamifile;ifile.open("dictionary.txt");//打开文件if(!ifile){cout<<"无法打开dictionary.txt!"<<endl;exit(1);}while(ifile.eof()!=1){ifile>>a>>b;d.word=a;d.para=b;Dic.push_back(d);i++;}ifile.close();}voidManage::HashTablesearch():哈希表查找函数voidManage::HashTablesearch(){stringword;cout<<"请输入你要查找的单词 ："<<endl;cin>>word;HashTablemyHashTable(1.7*(int)Dic.size());stringb[2025];for(inti=0;i<(int)Dic.size();i++)b[i]=Dic[i].word;DataTypea[2025];for(inti=0;i<(int)Dic.size();i++)a[i]=b[i];for(inti=0;i<(int)Dic.size();i++)myHashTable.Insert(a[i]);stringk=myHashTable.IsIn(word);if(k=="字典中没有这个单词！")cout<<k<<endl;else{for(inti=0;i<(int)Dic.size();i++){if(Dic[i].word==k){cout<<"查找成功，其位置为："<<i<<endl;/*如果找到该数，则输出其位置*/cout<<Dic[i].word<<'\t'<<Dic[i].para<<endl;}}}}voidManage::Blocksearch()：实现分块查找函数voidManage::Blocksearch(){intj=0,k;stringkey;stringa[2025];for(inti=0;i<(int)Dic.size();i++)a[i]=Dic[i].word;for(inti=0;i<=24;i++){TOC\o"1-5"\h\zindex_table[i].start=j;/*确定每个块范围的起始值 */index_table[i].end=j+81-1;/*确定每个块范围的结束值 */j=j+81;index_table[i].key=a[index_table[i].end];/* 确定每个块范围中元素的最大值 */}cout<<"请输入你要查找的单词 ："<<endl;cin>>key;k=block_search(key,a);/*调用函数进行查找*/if(k>=0){cout<<"查找成功，其位置为："<<k<<endl;/*如果找到该词，则输出其位置*/cout<<Dic[k].word<<'\t'<<Dic[k].para<<endl;}elsecout<<"查找失败！"<<endl;/*若未找到则输出提示信息 */}voidManage::BiSearchTreesearch()：实现二叉搜索树查找函数voidManage::BiSearchTreesearch(){BiSearchTree<string>searchTree;stringa[2025];for(inti=0;i<(int)Dic.size();i++)a[i]=Dic[i].word;for(inti=0;i<(int)Dic.size();i++)searchTree.Insert(a[i]);cout<<"请输入你要查找的单词 ："<<endl;stringkey;cin>>key;BiTreeNode<string>*node=searchTree.Find(key);if(node==NULL)cout<<"查找失败!"<<endl;/*若未找到则输出提示信息 */else{for(inti=0;i<(int)Dic.size();i++){if(Dic[i].word==node->Data()){cout<<"查找成功，其位置为：："<<i<<endl;/*如果找到该数，则输出其位置*/cout<<Dic[i].word<<'\t'<<Dic[i].para<<endl;}}}}三，程序运行截图：博按任意铤继续.•.为:***^*:**:******^::4:*^***:**:**:*4:*^*7*******#***^*****1*****************0—退出*1--哈希查找2--分块查找3-—二叉排序树查找p***d|t^c********:a|o|c* *********d|ci|c* ******D|n|c****:fz|c:>|>:**** ********,选择你想进行的操作！：,输入你要查找的单祠：good国战成功，其位置为：1kood好的0 退出1—一哈聚查战2-一分块查找支一二叉排肿才查找褊蠢常s3r-秘*"住*'"""*-2b清输入你要查找的单词：well查找失败！请按任意键继续...#****3C***：3|q|c坤21rsfc*********31clic ***斗*#31cll(c相*在*1c4c****1c********0--退出1--哈希查找2-—分块查找3—二叉排方树查找,********箕***：^|［：邛**冉********?|^***；^0|；*尊****?|ci|c***芈*****肃**事***植选择你想进行的操作!:请输入你要查找的单词:abandoned国战成功，其位置为…5*中*******中***************************abandoned被抛弃的abandoned被抛弃的。赶北4c北北*北*北3*:沈北北比*北*求***北北**北北北加||：比北北比北水括按任意键继续..微软拼音半：程序运行平台：Visualstudioprofessional2013四，程序源代码:程序分为：Dictionary.hBiSearchTree.hHashTable.hManage.hHashTable.cppManage.cppMain.cppDictionary.h:#ifndefDICTIONARY_H//避免重定义错误， 该文件编译一次#defineDICTIONARY」#include<iostream>#include<string>usingnamespacestd;structDictionary{stringword;stringpara;};#endifBiSearchTree.h:#ifndefBITREENODE_H//避免重定义错误， 该文件编译一次#defineBITREENODE_H#include<iostream>#include"dictionary.h"usingnamespacestd;template<classT>classBiTreeNode{private:BiTreeNode<T>*leftChild;//左子树指针BiTreeNode<T>*rightChild;//右子树指针Tdata;//数据域public:〃构造函数和析构函数BiTreeNode():leftChild(NULL),rightChild(NULL){}BiTreeNode(Titem,BiTreeNode<T>*left=NULL,BiTreeNode<T>*right=NULL):data(item),leftChild(left),rightChild(right){}~BiTreeNode(){}BiTreeNode<T>*&Left(void)〃注意返回值类型为指针的引用类型returnleftChild;}BiTreeNode<T>*&Right(void) 〃注意返回值类型为指针的引用类型{returnrightChild;}T&Data(void) 〃注意返回值类型为指针的引用类型{returndata;}};template<classT>classBiSearchTree{friendistream&operator>>(istream&in,BiSearchTree<T>*&tree);private:BiTreeNode<T>*root;//根结点指针voidInsert(BiTreeNode<T>*&ptr,constT&item);public:BiSearchTree(void):root(NULL){};//构造函数~BiSearchTree(void){};〃析构函数BiTreeNode<T>*Find(constT&item);voidInsert(constT&item){Insert(GetRoot(),item);}BiTreeNode<T>*&GetRoot(){returnroot;}};template<classT>BiTreeNode<T>*BiSearchTree<T>::Find(constT&item){if(root!=NULL){BiTreeNode<T>*temp=root;while(temp!=NULL){if(temp->Data()==item)returntemp;if(temp->Data()<item)temp=temp->Right();elsetemp=temp->Left();}}returnNULL;}template<classT>voidBiSearchTree<T>::Insert(BiTreeNode<T>*&ptr,constT&item){if(ptr==NULL)ptr=newBiTreeNode<T>(item);elseif(item<ptr->Data())Insert(ptr->Left(),item);elseif(item>ptr->Data())Insert(ptr->Right(),item);}#endifHashTable.h:#ifndefHASHTABLE_H//避免重定义错误， 该文件编译一次#defineHASHTABLE_Husingnamespacestd;#include"dictionary.h"typedefstringKeyType;enumKindOfItem{Empty,Active,Deleted};structDataType{KeyTypekey;DataType(){}DataType(KeyTypek):key(k){}intoperator==(constDataType&a){returnkey==a.key;}intoperator!=(constDataType&a){returnkey!=a.key;}};structHashItem{DataTypedata;KindOfIteminfo;HashItem(KindOfItemi=Empty):info(i){}HashItem(constDataType&D,KindOfItemi=Empty):data(D),info(i){}intoperator==(HashItem&a){returndata==a.data;}intoperator!=(HashItem&a){returndata!=a.data;}};classHashTable{private:Hashitem*ht;//哈希表动态数组intTableSize;〃哈希表的长度(即m)intcurrentSize;//当前的表项个数public:HashTable(intm);〃构造函数~HashTable(void){delete口ht;}〃析构函数//intH(KeyTypekey);//哈希函数，新增//intD(inti);//探查函数，新增intFind(constDataType&x)const;//查找intInsert(constDataType&x);//插入intDelete(constDataType&x);//删除stringIsIn(constDataType&x){stringa="NOThisWordThere!";inti=Find(x);if(i>0)returnx.key;elsereturna;}〃是否已存在DataTypeGetValue(inti)const{returnht[i].data;}〃取数据元素};#endifManage.h:#ifndefMANAGE_H//避免重定义错误， 该文件编译一次#defineMANAGE_H#include"BiSearchTree.h"#include"HashTable.h"#include<vector>classManage{private:vector<Dictionary>Dic;public:voidReadtxt();voidBiSearchTreesearch();voidBlocksearch();voidHashTablesearch();}；#endifHashTable.cpp:#include"HashTable.h"HashTable::HashTable(intm){TableSize=m;ht=newHashItem[m];currentSize=0;}intHashTable::Find(constDataType&x)const/*在Hash表中查找x.key的记录，采用开放定址法解决冲突。查找成功返回值〉0(该单元X犬态为Active),查找失败返回值v 0。*/{inti=x.key.size()%TableSize;intj=i;while(ht[j].info==Active&&ht[j].data!=x){j=(j+1)%TableSize;if(j==i)return-TableSize;}if(ht[j].info==Active)returnj;elsereturn-j;}intHashTable::Insert(constDataType&x)/*在Hash表中插入x。插入成功返回值1,插入失败返回值0。*/{inti=Find(x);if(i>=0&&ht[i].info==Active)//查找成功return0;elseif(i!=-TableSize)//查找失败并表未满{ht[-i].data=x;ht[-i].info=Active;currentSize++;return1;//插入成功}elsereturn0;//表满，插入失败}intHashTable::Delete(constDataType&x)/*在Hash表中删除x.key的记录。删除成功返回值 1,删除失败返回值0。*/{inti=Find(x);if(i>=0&&ht[i].info==Active)// 查找成功{ht[i].info=Deleted;//将其状态标记为碑currentSize--;return1;}else/鹰找失败return0;}Manage.cpp:#include"Manage.h"#include<fstream>//typedefstringDataType;voidManage::Readtxt(){inti=0;stringa,b;Dictionaryd;ifstreamifile;ifile.open("dictionary.txt");//打开文件if(!ifile){cout<<"无法打开dictionary.txt!"<<endl;exit(1);}while(ifile.eof()!=1){ifile>>a>>b;d.word=a;d.para=b;Dic.push_back(d);i++;}ifile.close();voidManage::HashTablesearch(){stringword;cout<<"请输入你要查找的单词 ："<<endl;cin>>word;HashTablemyHashTable(1.7*(int)Dic.size());stringb[2025];for(inti=0;i<(int)Dic.size();i++)b[i]=Dic[i].word;DataTypea[2025];for(inti=0;i<(int)Dic.size();i++)a[i]=b[i];for(inti=0;i<(int)Dic.size();i++)myHashTable.Insert(a[i]);stringk=myHashTable.IsIn(word);if(k=="字典中没有这个单词！")cout<<k<<endl;else{for(inti=0;i<(int)Dic.size();i++){if(Dic[i].word==k){cout<<"查找成功，其位置为："<<i<<endl;/*如果找到该数，则输出其位置*/cout<<Dic[i].word<<'\t'<<Dic[i].para<<endl;}}}}classindex/*定义块的结构*/{public:stringkey;intstart;intend;}index_table[25];/*定义结构体数组*/intblock_search(stringkey,stringa[])/*自定义实现分块查找*/{inti,j;i=0;while(i<=24&&key>index_table[i].key)/* 确定在那个块中*/i++;if(i>24)/*大于分得的块数，则返回0*/return-1;j=index_table[i].start;/*j等于块范围的起始值 */while(j<=index_table[i].end&&a[j]!=key)/* 在确定的块内进行查找 */j++;if(j>index_table[i].end)/*如果大于块范围的结束值，则说明没有要查找的数 ，j置0*/j=-1;returnj;}voidManage::Blocksearch(){intj=0,k;stringkey;stringa[2025];for(inti=0;i<(int)Dic.size();i++)a[i]=Dic[i].word;for(inti=0;i<=24;i++){TOC\o"1-5"\h\zindex_table[i].start=j;/*确定每个块范围的起始值 */index_table[i].end=j+81-1;/*确定每个块范围的结束值 */j=j+81;index_table[i].key=a[index_table[i].end];/*确定每个块范围中元素的最大值 */}cout<<"请输入你要查找的单词："<<endl;cin>>key;k=block_search(key,a);/*调用函数进行查找*/if(k>=0){cout<<"查找成功，其位置为："<<k<<endl;/*如果找到该词，则输出其位置*/cout<<Dic[k].word<<'\t'<<Dic[k].para<<endl;}elsecout<<"查找失败！"<<endl;/*若未找到则输出提示信息 */}voidManage::BiSearchTreesearch(){BiSearchTree<string>searchTree;stringa[2025];for(inti=0;i<(int)Dic.size();i++)a[i]=Dic[i].word;for(inti=0;i<(int)Dic.size();i++)searchTree.Insert(a[i]);cout<<"请输入你要查找的单词："<<endl;stringkey;cin>>key;BiTreeNode<string>*node=searchTree.Find(key);if(node==NULL)cout<<"查找失败！"<<endl;/*若未找到则输出提示信息*/else{for(inti=0;i<(int