搜索
数据结构课程设计报告主题：实现字典的查找学号：班级：191142姓名：指导老师：内容概要（1）题目要求；（2）实现字典的查找的要点；（3）函数模块及各函数可实现的功能简介；（4）具体的源代码；（5）使用说明；（6）实验心得；一：题目要求如下：采用分块查找，哈希表查找，二叉排序树查找等不同方法实现对字典的查找，并分析不同查找方法的效率。二：构思要点：1.定义一个Dictionary结构：里面包含单词和单词意义属性：structDictionary{stringword;stringpara;};2.定义一个管理器类Manage，里面包含Dictionary类型的向量容器，和读取dictionary.txt的Readtxt()，以及二叉搜索树查找BiSearchTreesearch()，分块查找Blocksearch()和哈希表查找HashTablesearch()等功能函数：classManage{private:vectorDictionaryDic;public:voidReadtxt();voidBiSearchTreesearch();voidBlocksearch();voidHashTablesearch();};3.各个功能函数的详细代码：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){ifileab;d.word=a;d.para=b;Dic.push_back(d);i++;}ifile.close();}voidManage::HashTablesearch()：哈希表查找函数voidManage::HashTablesearch(){stringword;cout请输入你要查找的单词:endl;cinword;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==字典中没有这个单词!)coutkendl;else{for(inti=0;i(int)Dic.size();i++){if(Dic[i].word==k){cout查找成功，其位置为：iendl;/*如果找到该数，则输出其位置*/coutDic[i].word'\t'Dic[i].paraendl;}}}}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++){index_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;cinkey;k=block_search(key,a);/*调用函数进行查找*/if(k=0){cout查找成功，其位置为：kendl;/*如果找到该词，则输出其位置*/coutDic[k].word'\t'Dic[k].paraendl;}elsecout查找失败!endl;/*若未找到则输出提示信息*/}voidManage::BiSearchTreesearch()：实现二叉搜索树查找函数voidManage::BiSearchTreesearch(){BiSearchTreestringsearchTree;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;cinkey;BiTreeNodestring*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查找成功，其位置为：：iendl;/*如果找到该数，则输出其位置*/coutDic[i].word'\t'Dic[i].paraendl;}}}}三，程序运行截图：程序运行平台：Visualstudioprofessional2013四，程序源代码：程序分为：Dictionary.hBiSearchTree.hHashTable.hManage.hHashTable.cppManage.cppMain.cppDictionary.h：#ifndefDICTIONARY_H//避免重定义错误，该文件编译一次#defineDICTIONARY_H#includeiostream#includestringusingnamespacestd;structDictionary{stringword;stringpara;};#endifBiSearchTree.h:#ifndefBITREENODE_H//避免重定义错误，该文件编译一次#defineBITREENODE_H#includeiostream#includedictionary.husingnamespacestd;templateclassTclassBiTreeNode{private:BiTreeNodeT*leftChild;//左子树指针BiTreeNodeT*rightChild;//右子树指针Tdata;//数据域public://构造函数和析构函数BiTreeNode():leftChild(NULL),rightChild(NULL){}BiTreeNode(Titem,BiTreeNodeT*left=NULL,BiTreeNodeT*right=NULL):data(item),leftChild(left),rightChild(right){}~BiTreeNode(){}BiTreeNodeT*&Left(void)//注意返回值类型为指针的引用类型{returnleftChild;}BiTreeNodeT*&Right(void)//注意返回值类型为指针的引用类型{returnrightChild;}T&Data(void)//注意返回值类型为指针的引用类型{returndata;}};templateclassTclassBiSearchTree{friendistream&operator(istream&in,BiSearchTreeT*&tree);private:BiTreeNodeT*root;//根结点指针voidInsert(BiTreeNodeT*&ptr,constT&item);public:BiSearchTree(void):root(NULL){};//构造函数~BiSearchTree(void){};//析构函数BiTreeNodeT*Find(constT&item);voidInsert(constT&item){Insert(GetRoot(),item);}BiTreeNodeT*&GetRoot(){returnroot;}};templateclassTBiTreeNodeT*BiSearchTreeT::Find(constT&item){if(root!=NULL){BiTreeNodeT*temp=root;while(temp!=NULL){if(temp-Data()==item)returntemp;if(temp-Data()item)temp=temp-Right();elsetemp=temp-Left();}}returnNULL;}templateclassTvoidBiSearchTreeT::Insert(BiTreeNodeT*&ptr,constT&item){if(ptr==NULL)ptr=newBiTreeNodeT(item);elseif(itemptr-Data())Insert(ptr-Left(),item);elseif(itemptr-Data())Insert(ptr-Right(),item);}#endifHashTable.h:#ifndefHASHTABLE_H//避免重定义错误，该文件编译一次#defineHASHTABLE_Husingnamespacestd;#includedictionary.htypedefstringKeyType;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(constDataTyp