數(shù)據(jù)結構報告—實現(xiàn)對字典的查找

1、數(shù)據(jù)結構課程設計報告主題：實現(xiàn)字典的查找學號：班級：191142姓名：指導老師：內(nèi)容概要（1） 題目要求；（2） 實現(xiàn)字典的查找的要點；（3） 函數(shù)模塊及各函數(shù)可實現(xiàn)的功能簡介；（4） 具體的源代碼；（5） 使用說明；（6） 實驗心得；一：題目要求如下：采用分塊查找，哈希表查找，二叉排序樹查找等不同方法實現(xiàn)對字典的查找，并分析不同查找方法的效率。二：構思要點：1.定義一個Dictionary 結構：里面包含單詞和單詞意義屬性：struct Dictionarystring word;string para;2.定義一個管理器類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.各個功能函數(shù)的詳細代碼：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 請輸入你要查找的單詞: 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 = 字典中沒有這個單詞!)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()：實現(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; /*確定每個塊范圍的起始值*/index_tablei.end = j + 81 - 1; /*確定每個塊范圍的結束值*/j = j + 81;index_tablei.key = aindex_tablei.end; /*確定每個塊范圍中元素的最大值*/cout 請輸入你要查找的單詞: key;k = block_search(key, a); /*調用函數(shù)進行查找*/if (k = 0)cout 查找成功，其位置為： k endl; /*如果找到該詞，則輸出其位置*/cout Dick.word t Dick.para endl;elsecout 查找失敗! endl; /*若

7、未找到則輸出提示信息*/void Manage:BiSearchTreesearch()：實現(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 請輸入你要查找的單詞: 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;三，程序運行截圖：程序運行平臺：Visual studio professional 2013四，程序源代碼：程序分為：Dictionary.hBiSearchTree.hHashTable.hManage.hHashTable.cppManage.cppMain.cppDictionary.h：#if

9、ndef DICTIONARY_H /避免重定義錯誤， 該文件編譯一次#define DICTIONARY_H#include#includeusing namespace std;struct Dictionarystring word;string para;#endifBiSearchTree.h:#ifndef BITREENODE_H /避免重定義錯誤， 該文件編譯一次#define BITREENODE_H#include#includedictionary.husing namespace std;template class BiTreeNodeprivate:BiTreeNo

10、de *leftChild;/左子樹指針BiTreeNode *rightChild;/右子樹指針T data;/數(shù)據(jù)域public:/構造函數(shù)和析構函數(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;/根結點指針void Insert(BiTreeNode* &ptr, const T & item);public:BiSearchTree(void

12、) :root(NULL);/構造函數(shù)BiSearchTree(void);/析構函數(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 /避免重定義錯誤， 該文件編譯一次#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;/哈希表動態(tài) 數(shù)組 int TableSize;/哈希表的長度（即m） int currentSize;/當前的表項個數(shù) public:HashTable(int m);/構造函數(shù) HashTable(void) deleteht;/析構函數(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 /避免重定義錯誤， 該文件編譯一次#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)標記為碑 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 請輸入你要查找的單詞: 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 = 字典中沒有這個單詞!)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 /*定義塊的結構*/public:string key;int start;int end; index_table25; /*定義結構體數(shù)組*/i

24、nt block_search(string key, string a) /*自定義實現(xiàn)分塊查找*/int i, j;i = 0;while (i index_tablei.key) /*確定在那個塊中*/i+;if (i 24) /*大于分得的塊數(shù)，則返回0*/return -1;j = index_tablei.start; /*j等于塊范圍的起始值*/while (j index_tablei.end) /*如果大于塊范圍的結束值，則說明沒有要查找的數(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; /*確定每個塊范圍的起始值*/index_tablei.end = j + 81 - 1; /*確定每個塊范圍的結束值*/j = j + 81;index_tablei.key = aindex_tablei.end; /*確定每個塊范圍中元素的最大值*/cout 請輸入你要查找的單詞: key;k = block_search(key, a); /*調用函

26、數(shù)進行查找*/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 請輸入你要查找的單詞: key;BiTreeNode *n