數(shù)據(jù)結(jié)構(gòu)報(bào)告-實(shí)現(xiàn)對(duì)字典的查找

數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)報(bào)告主題：實(shí)現(xiàn)字典的查找學(xué)號(hào)：班級(jí)：191142姓名：指導(dǎo)老師：歡迎下載 歡迎下載 15內(nèi)容概要(1)題目要求；(2)實(shí)現(xiàn)字典的查找的要點(diǎn)；(3)函數(shù)模塊及各函數(shù)可實(shí)現(xiàn)的功能簡(jiǎn)介;(4)具體的源代碼；(5)使用說(shuō)明；(6)實(shí)驗(yàn)心得；一：題目要求如下：采用分塊查找，哈希表查找，二叉排序樹查找等不同方法實(shí)現(xiàn)對(duì)字典的查找，并分析不同查找方法的效率。二：構(gòu)思要點(diǎn)：.定義一個(gè)Dictionary結(jié)構(gòu)：里面包含單詞和單詞意義屬性：structDictionary{stringword;stringpara;}；.定義一個(gè)管理器類Manage,里面包含Dictionary類型的向量容器，和讀取dictionary.8的Readtxt(),以及二叉搜索樹查找BiSearchTreesearch(),分塊查找Blocksearch()和哈希表查找HashTablesearch(悻功能函數(shù)：classManage{private:vector<Dictionary>Dic;public:voidReadtxt();voidBiSearchTreesearch();voidBlocksearch();voidHashTablesearch();};.各個(gè)功能函數(shù)的詳細(xì)代碼：voidManage::Readtxt()：讀取dictionary.txt里的單詞表voidManage::Readtxt(){inti=0;stringa,b;Dictionaryd;ifstreamifile;ifile.open("dictionary.txt");//打開文件if(!ifile){cout<<"無(wú)法打開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():哈希表查找函數(shù)voidManage::HashTablesearch(){stringword;cout<<"請(qǐng)輸入你要查找的單詞 ："<<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=="字典中沒有這個(gè)單詞！")cout<<k<<endl;else{for(inti=0;i<(int)Dic.size();i++){if(Dic[i].word==k){cout<<"查找成功，其位置為："<<i<<endl;/*如果找到該數(shù)，則輸出其位置*/cout<<Dic[i].word<<'\t'<<Dic[i].para<<endl;}}}}voidManage::Blocksearch()：實(shí)現(xiàn)分塊查找函數(shù)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;/*確定每個(gè)塊范圍的起始值 */index_table[i].end=j+81-1;/*確定每個(gè)塊范圍的結(jié)束值 */j=j+81;index_table[i].key=a[index_table[i].end];/* 確定每個(gè)塊范圍中元素的最大值 */}cout<<"請(qǐng)輸入你要查找的單詞 ："<<endl;cin>>key;k=block_search(key,a);/*調(diào)用函數(shù)進(jìn)行查找*/if(k>=0){cout<<"查找成功，其位置為："<<k<<endl;/*如果找到該詞，則輸出其位置*/cout<<Dic[k].word<<'\t'<<Dic[k].para<<endl;}elsecout<<"查找失?。?<<endl;/*若未找到則輸出提示信息 */}voidManage::BiSearchTreesearch()：實(shí)現(xiàn)二叉搜索樹查找函數(shù)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<<"請(qǐng)輸入你要查找的單詞 ："<<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;/*如果找到該數(shù)，則輸出其位置*/cout<<Dic[i].word<<'\t'<<Dic[i].para<<endl;}}}}三，程序運(yùn)行截圖：博按任意鋌繼續(xù).?.為:***^*:**:******^::4:*^***:**:**:*4:*^*7*******#***^*****1*****************0—退出*1--哈希查找2--分塊查找3-—二叉排序樹查找p***d|t^c********:a|o|c* *********d|ci|c* ******D|n|c****:fz|c:>|>:**** ********,選擇你想進(jìn)行的操作?。?輸入你要查找的單祠：good國(guó)戰(zhàn)成功，其位置為：1kood好的0 退出1—一哈聚查戰(zhàn)2-一分塊查找支一二叉排腫才查找褊蠢常s3r-秘*"住*'"""*-2b清輸入你要查找的單詞：well查找失?。≌?qǐng)按任意鍵繼續(xù)...#****3C***：3|q|c坤21rsfc*********31clic ***斗*#31cll(c相*在*1c4c****1c********0--退出1--哈希查找2-—分塊查找3—二叉排方樹查找,********箕***：^|［：邛**冉********?|^***；^0|；*尊****?|ci|c***羋*****肅**事***植選擇你想進(jìn)行的操作!:請(qǐng)輸入你要查找的單詞:abandoned國(guó)戰(zhàn)成功，其位置為…5*中*******中***************************abandoned被拋棄的abandoned被拋棄的。趕北4c北北*北*北3*:沈北北比*北*求***北北**北北北加||：比北北比北水括按任意鍵繼續(xù)..微軟拼音半：程序運(yùn)行平臺(tái)：Visualstudioprofessional2013四，程序源代碼:程序分為：Dictionary.hBiSearchTree.hHashTable.hManage.hHashTable.cppManage.cppMain.cppDictionary.h:#ifndefDICTIONARY_H//避免重定義錯(cuò)誤， 該文件編譯一次#defineDICTIONARY」#include<iostream>#include<string>usingnamespacestd;structDictionary{stringword;stringpara;};#endifBiSearchTree.h:#ifndefBITREENODE_H//避免重定義錯(cuò)誤， 該文件編譯一次#defineBITREENODE_H#include<iostream>#include"dictionary.h"usingnamespacestd;template<classT>classBiTreeNode{private:BiTreeNode<T>*leftChild;//左子樹指針BiTreeNode<T>*rightChild;//右子樹指針Tdata;//數(shù)據(jù)域public:〃構(gòu)造函數(shù)和析構(gòu)函數(shù)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;//根結(jié)點(diǎn)指針voidInsert(BiTreeNode<T>*&ptr,constT&item);public:BiSearchTree(void):root(NULL){};//構(gòu)造函數(shù)~BiSearchTree(void){};〃析構(gòu)函數(shù)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//避免重定義錯(cuò)誤， 該文件編譯一次#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;//哈希表動(dòng)態(tài)數(shù)組intTableSize;〃哈希表的長(zhǎng)度(即m)intcurrentSize;//當(dāng)前的表項(xiàng)個(gè)數(shù)public:HashTable(intm);〃構(gòu)造函數(shù)~HashTable(void){delete口ht;}〃析構(gòu)函數(shù)//intH(KeyTypekey);//哈希函數(shù)，新增//intD(inti);//探查函數(shù)，新增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;}〃取數(shù)據(jù)元素};#endifManage.h:#ifndefMANAGE_H//避免重定義錯(cuò)誤， 該文件編譯一次#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犬態(tài)為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;//將其狀態(tài)標(biāo)記為碑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<<"無(wú)法打開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<<"請(qǐng)輸入你要查找的單詞 ："<<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=="字典中沒有這個(gè)單詞！")cout<<k<<endl;else{for(inti=0;i<(int)Dic.size();i++){if(Dic[i].word==k){cout<<"查找成功，其位置為："<<i<<endl;/*如果找到該數(shù)，則輸出其位置*/cout<<Dic[i].word<<'\t'<<Dic[i].para<<endl;}}}}classindex/*定義塊的結(jié)構(gòu)*/{public:stringkey;intstart;intend;}index_table[25];/*定義結(jié)構(gòu)體數(shù)組*/intblock_search(stringkey,stringa[])/*自定義實(shí)現(xiàn)分塊查找*/{inti,j;i=0;while(i<=24&&key>index_table[i].key)/* 確定在那個(gè)塊中*/i++;if(i>24)/*大于分得的塊數(shù)，則返回0*/return-1;j=index_table[i].start;/*j等于塊范圍的起始值 */while(j<=index_table[i].end&&a[j]!=key)/* 在確定的塊內(nèi)進(jìn)行查找 */j++;if(j>index_table[i].end)/*如果大于塊范圍的結(jié)束值，則說(shuō)明沒有要查找的數(shù) ，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;/*確定每個(gè)塊范圍的起始值 */index_table[i].end=j+81-1;/*確定每個(gè)塊范圍的結(jié)束值 */j=j+81;index_table[i].key=a[index_table[i].end];/*確定每個(gè)塊范圍中元素的最大值 */}cout<<"請(qǐng)輸入你要查找的單詞："<<endl;cin>>key;k=block_search(key,a);/*調(diào)用函數(shù)進(jìn)行查找*/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<<"請(qǐng)輸入你要查找的單詞："<<endl;stringkey;cin>>key;BiTreeNode<string>*node=searchTree.Find(key);if(node==NULL)cout<<"查找失敗！"<<endl;/*若未找到則輸出提示信息*/else{for(inti=0;i<(int