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

1、數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)報(bào)告主題：實(shí)現(xiàn)字典的查找學(xué)號(hào)：班級(jí)：191142姓名：指導(dǎo)老師：內(nèi)容概要（1） 題目要求；（2） 實(shí)現(xiàn)字典的查找的要點(diǎn)；（3） 函數(shù)模塊及各函數(shù)可實(shí)現(xiàn)的功能簡介；（4） 具體的源代碼；（5） 使用說明；（6） 實(shí)驗(yàn)心得；一：題目要求如下：采用分塊查找，哈希表查找，二叉排序樹查找等不同方法實(shí)現(xiàn)對(duì)字典的查找，并分析不同查找方法的效率。二：構(gòu)思要點(diǎn)：1.定義一個(gè)dictionary 結(jié)構(gòu)：里面包含單詞和單詞意義屬性：struct dictionarystring word;string para;2.定義一個(gè)管理器類manage，里面包含dictionary類型的向量容器，和讀取di

2、ctionary.txt的readtxt()，以及二叉搜索樹查找bisearchtreesearch()，分塊查找blocksearch()和哈希表查找hashtablesearch()等功能函數(shù)：class manageprivate:vector dic;public:void readtxt();void bisearchtreesearch();void blocksearch();void hashtablesearch();3.各個(gè)功能函數(shù)的詳細(xì)代碼：void manage:readtxt()：讀取dictionary.txt里的單詞表void manage:readtxt()in

3、t i = 0;string a, b;dictionary d;ifstream ifile;ifile.open(dictionary.txt); /打開文件if (!ifile)cout 無法打開 dictionary.txt! a b;d.word = a;d.para = b;dic.push_back(d);i+;ifile.close();void manage:hashtablesearch()：哈希表查找函數(shù)void manage:hashtablesearch()string word;cout 請(qǐng)輸入你要查找的單詞: word;hashtable myhashtable(

4、1.7*(int)dic.size();string b2025;for (int i = 0; i (int)dic.size(); i+)bi = dici.word;datatype a2025;for (int i = 0; i (int)dic.size(); i+)ai = bi;for (int i = 0; i (int)dic.size(); i+)myhashtable.insert(ai);string k = myhashtable.isin(word);if (k = 字典中沒有這個(gè)單詞!)cout k endl;elsefor (int i = 0; i (int)

5、dic.size(); i+)if (dici.word = k)cout 查找成功，其位置為： i endl; /*如果找到該數(shù)，則輸出其位置*/cout dici.word t dici.para endl;void manage:blocksearch()：實(shí)現(xiàn)分塊查找函數(shù)void manage:blocksearch()int j = 0, k;string key;string a2025;for (int i = 0; i (int)dic.size(); i+)ai = dici.word;for (int i = 0; i = 24; i+)index_tablei.start

6、 = j; /*確定每個(gè)塊范圍的起始值*/index_tablei.end = j + 81 - 1; /*確定每個(gè)塊范圍的結(jié)束值*/j = j + 81;index_tablei.key = aindex_tablei.end; /*確定每個(gè)塊范圍中元素的最大值*/cout 請(qǐng)輸入你要查找的單詞: key;k = block_search(key, a); /*調(diào)用函數(shù)進(jìn)行查找*/if (k = 0)cout 查找成功，其位置為： k endl; /*如果找到該詞，則輸出其位置*/cout dick.word t dick.para endl;elsecout 查找失敗! endl; /*若

7、未找到則輸出提示信息*/void manage:bisearchtreesearch()：實(shí)現(xiàn)二叉搜索樹查找函數(shù)void manage:bisearchtreesearch()bisearchtree searchtree;string a2025;for (int i = 0; i (int)dic.size(); i+)ai = dici.word;for (int i = 0; i (int)dic.size(); i+)searchtree.insert(ai);cout 請(qǐng)輸入你要查找的單詞: key;bitreenode *node = searchtree.find(key);i

8、f (node = null)cout 查找失敗! endl; /*若未找到則輸出提示信息*/elsefor (int i = 0; i data()cout 查找成功，其位置為： i endl; /*如果找到該數(shù)，則輸出其位置*/cout dici.word t dici.para endl;三，程序運(yùn)行截圖：程序運(yùn)行平臺(tái)：visual studio professional 2013四，程序源代碼：程序分為：dictionary.hbisearchtree.hhashtable.hmanage.hhashtable.cppmanage.cppmain.cppdictionary.h：#if

9、ndef dictionary_h /避免重定義錯(cuò)誤， 該文件編譯一次#define dictionary_h#include#includeusing namespace std;struct dictionarystring word;string para;#endifbisearchtree.h:#ifndef bitreenode_h /避免重定義錯(cuò)誤， 該文件編譯一次#define bitreenode_h#include#includedictionary.husing namespace std;template class bitreenodeprivate:bitreeno

10、de *leftchild;/左子樹指針bitreenode *rightchild;/右子樹指針t data;/數(shù)據(jù)域public:/構(gòu)造函數(shù)和析構(gòu)函數(shù)bitreenode() :leftchild(null), rightchild(null)bitreenode(t item, bitreenode *left = null, bitreenode *right = null) :data(item), leftchild(left), rightchild(right)bitreenode()bitreenode* &left(void)/注意返回值類型為指針的引用類型return l

11、eftchild;bitreenode* &right(void)/注意返回值類型為指針的引用類型return rightchild;t & data(void)/注意返回值類型為指針的引用類型return data;template class bisearchtreefriend istream & operator (istream & in, bisearchtree * &tree);private:bitreenode *root;/根結(jié)點(diǎn)指針void insert(bitreenode* &ptr, const t & item);public:bisearchtree(void

12、) :root(null);/構(gòu)造函數(shù)bisearchtree(void);/析構(gòu)函數(shù)bitreenode *find(const t &item);void insert(const t &item)insert(getroot(), item);bitreenode *&getroot() return root; ;template bitreenode *bisearchtree:find(const t &item)if (root != null)bitreenode * temp = root;while (temp != null)if (temp-data() = item)

13、return temp;if (temp-data() right();elsetemp = temp-left();return null;template void bisearchtree:insert(bitreenode* &ptr, const t & item)if (ptr = null)ptr = new bitreenode(item);else if (item data()insert(ptr-left(), item);else if (item ptr-data()insert(ptr-right(), item);#endifhashtable.h:#ifndef

14、 hashtable_h /避免重定義錯(cuò)誤， 該文件編譯一次#define hashtable_husing namespace std;#includedictionary.htypedef string keytype;enum kindofitem empty, active, deleted ;struct datatypekeytype key;datatype()datatype(keytype k) :key(k)int operator=(const datatype & a)return key = a.key;int operator!=(const datatype &

15、a)return key != a.key;struct hashitem datatype data;kindofitem info;hashitem(kindofitem i = empty) : info(i)hashitem(const datatype &d, kindofitem i = empty) : data(d), info(i)int operator =(hashitem &a)return data = a.data;int operator !=(hashitem &a)return data != a.data;class hashtable private:ha

16、shitem *ht;/哈希表動(dòng)態(tài) 數(shù)組 int tablesize;/哈希表的長度（即m） int currentsize;/當(dāng)前的表項(xiàng)個(gè)數(shù) public:hashtable(int m);/構(gòu)造函數(shù) hashtable(void) deleteht;/析構(gòu)函數(shù) /int h(keytype key);/哈希函數(shù)，新增 /int d(int i);/探查函數(shù)，新增 int find(const datatype &x)const;/查找 int insert(const datatype &x);/插入 int delete(const datatype &x);/刪除 string isi

17、n(const datatype &x) string a = no this word there!;int i = find(x);if (i 0)return x.key;elsereturn a;/是否已存在 datatype getvalue(int i) constreturn hti.data;/取數(shù) 據(jù)元素 ;#endifmanage.h:#ifndef manage_h /避免重定義錯(cuò)誤， 該文件編譯一次#define manage_h#includebisearchtree.h#includehashtable.h#includeclass manageprivate:ve

18、ctor dic;public:void readtxt();void bisearchtreesearch();void blocksearch();void hashtablesearch();#endifhashtable.cpp:#includehashtable.hhashtable:hashtable(int m) tablesize = m;ht = new hashitemm;currentsize = 0;int hashtable:find(const datatype &x)const /*在hash表中查找x.key的記錄，采用開放定址法解決沖突。查 找成功返回值0(該

19、單元狀態(tài)為active)，查找失敗返回值0。 */int i = x.key.size() % tablesize;int j = i;while ( = active&htj.data != x)j = (j + 1) % tablesize;if (j = i)return -tablesize;if ( = active)return j;elsereturn -j;int hashtable:insert(const datatype &x)/*在hash表 中插入x。插入成功返回值1，插入失敗返回值0。*/int i = find(x);if (i =

20、 0 & = active) /查找成功 return 0;else if (i != -tablesize)/查找失敗并表未滿 ht-i.data = x; = active;currentsize+;return 1;/插入成功 else return 0;/表滿，插入失敗int hashtable:delete(const datatype &x) /*在hash表中刪除x.key的記錄。刪除成功返回值1，刪除失敗 返回值0。*/int i = find(x);if (i = 0 & = active) /查找成功

21、= deleted;/將其狀態(tài)標(biāo)記為碑 currentsize-;return 1;else /查找失敗 return 0;manage.cpp:#includemanage.h#include/typedef string datatype;void manage:readtxt()int i = 0;string a, b;dictionary d;ifstream ifile;ifile.open(dictionary.txt); /打開文件if (!ifile)cout 無法打開 dictionary.txt! a b;d.word = a;d.para = b;dic.push_ba

22、ck(d);i+;ifile.close();void manage:hashtablesearch()string word;cout 請(qǐng)輸入你要查找的單詞: word;hashtable myhashtable(1.7*(int)dic.size();string b2025;for (int i = 0; i (int)dic.size(); i+)bi = dici.word;datatype a2025;for (int i = 0; i (int)dic.size(); i+)ai = bi;for (int i = 0; i (int)dic.size(); i+)myhasht

23、able.insert(ai);string k = myhashtable.isin(word);if (k = 字典中沒有這個(gè)單詞!)cout k endl;elsefor (int i = 0; i (int)dic.size(); i+)if (dici.word = k)cout 查找成功，其位置為： i endl; /*如果找到該數(shù)，則輸出其位置*/cout dici.word t dici.para endl;class index /*定義塊的結(jié)構(gòu)*/public:string key;int start;int end; index_table25; /*定義結(jié)構(gòu)體數(shù)組*/i

24、nt block_search(string key, string a) /*自定義實(shí)現(xiàn)分塊查找*/int i, j;i = 0;while (i index_tablei.key) /*確定在那個(gè)塊中*/i+;if (i 24) /*大于分得的塊數(shù)，則返回0*/return -1;j = index_tablei.start; /*j等于塊范圍的起始值*/while (j index_tablei.end) /*如果大于塊范圍的結(jié)束值，則說明沒有要查找的數(shù),j置0*/j = -1;return j;void manage:blocksearch()int j = 0, k;string k

25、ey;string a2025;for (int i = 0; i (int)dic.size(); i+)ai = dici.word;for (int i = 0; i = 24; i+)index_tablei.start = j; /*確定每個(gè)塊范圍的起始值*/index_tablei.end = j + 81 - 1; /*確定每個(gè)塊范圍的結(jié)束值*/j = j + 81;index_tablei.key = aindex_tablei.end; /*確定每個(gè)塊范圍中元素的最大值*/cout 請(qǐng)輸入你要查找的單詞: key;k = block_search(key, a); /*調(diào)用函

26、數(shù)進(jìn)行查找*/if (k = 0)cout 查找成功，其位置為： k endl; /*如果找到該詞，則輸出其位置*/cout dick.word t dick.para endl;elsecout 查找失敗! endl; /*若未找到則輸出提示信息*/void manage:bisearchtreesearch()bisearchtree searchtree;string a2025;for (int i = 0; i (int)dic.size(); i+)ai = dici.word;for (int i = 0; i (int)dic.size(); i+)searchtree.insert(ai);cout 請(qǐng)輸入你要查找的單詞: key;bitreenode *n