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

数据结构课程设计报告主题：实现字典的查找学号：班级：191142姓名：指导老师：内容概要（1） 题目要求；（2） 实现字典的查找的要点；（3） 函数模块及各函数可实现的功能简介；（4） 具体的源代码；（5） 使用说明；（6） 实验心得；一：题目要求如下：采用分块查找，哈希表查找，二叉排序树查找等不同方法实现对字典的查找，并分析不同查找方法的效率。二：构思要点：1.定义一个Dictionary 结构：里面包含单词和单词意义属性：struct Dictionarystring word;string para;2.定义一个管理器类Manage，里面包含Dictionary类型的向量容器，和读取dictionary.txt的Readtxt()，以及二叉搜索树查找BiSearchTreesearch()，分块查找Blocksearch()和哈希表查找HashTablesearch()等功能函数：class Manageprivate:vector Dic;public:void Readtxt();void BiSearchTreesearch();void Blocksearch();void HashTablesearch();3.各个功能函数的详细代码：void Manage:Readtxt()：读取dictionary.txt里的单词表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_back(d);i+;ifile.close();void Manage:HashTablesearch()：哈希表查找函数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+)myHashTable.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; /*如果找到该数，则输出其位置*/cout Dici.word t Dici.para endl;void Manage:Blocksearch()：实现分块查找函数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 = j; /*确定每个块范围的起始值*/index_tablei.end = j + 81 - 1; /*确定每个块范围的结束值*/j = j + 81;index_tablei.key = aindex_tablei.end; /*确定每个块范围中元素的最大值*/cout 请输入你要查找的单词: key;k = block_search(key, a); /*调用函数进行查找*/if (k = 0)cout 查找成功，其位置为： k endl; /*如果找到该词，则输出其位置*/cout Dick.word t Dick.para endl;elsecout 查找失败! endl; /*若未找到则输出提示信息*/void Manage:BiSearchTreesearch()：实现二叉搜索树查找函数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);if (node = NULL)cout 查找失败! endl; /*若未找到则输出提示信息*/elsefor (int i = 0; i Data()cout 查找成功，其位置为： i endl; /*如果找到该数，则输出其位置*/cout Dici.word t Dici.para endl;三，程序运行截图：程序运行平台：Visual studio professional 2013四，程序源代码：程序分为：Dictionary.hBiSearchTree.hHashTable.hManage.hHashTable.cppManage.cppMain.cppDictionary.h：#ifndef 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:BiTreeNode *leftChild;/左子树指针BiTreeNode *rightChild;/右子树指针T data;/数据域public:/构造函数和析构函数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 leftChild;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) :root(NULL);/构造函数BiSearchTree(void);/析构函数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)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 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 & 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:HashItem *ht;/哈希表动态 数组 int TableSize;/哈希表的长度（即m） int currentSize;/当前的表项个数 public:HashTable(int m);/构造函数 HashTable(void) deleteht;/析构函数 /int H(KeyType key);/哈希函数，新增 /int D(int i);/探查函数，新增 int Find(const DataType &x)const;/查找 int Insert(const DataType &x);/插入 int Delete(const DataType &x);/删除 string IsIn(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;/取数 据元素 ;#endifManage.h:#ifndef MANAGE_H /避免重定义错误， 该文件编译一次#define MANAGE_H#includeBiSearchTree.h#includeHashTable.h#includeclass Manageprivate:vector 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(该单元状态为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 = 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) /查找成功 = Deleted;/将其状态标记为碑 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_back(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+)myHashTable.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; /*如果找到该数，则输出其位置*/cout Dici.word t Dici.para endl;class index /*定义块的结构*/public:string key;int start;int end; index_table25; /*定义结构体数组*/int block_search(string key, string a) /*自定义实现分块查找*/int i, j;i = 0;while (i index_tablei.key) /*确定在那个块中*/i+;if (i 24) /*大于分得的块数，则返回0*/return -1;j = index_tablei.start; /*j等于块范围的起始值*/while (j index_tablei.end) /*如果大于块范围的结束值，则说明没有要查找的数,j置0*/j = -1;return j;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 = j; /*确定每个块范围的起始值*/index_tablei.end = j + 81 - 1; /*确定每个块范围的结束值*/j = j + 81;index_tablei.key = aindex_tablei.end; /*确定每个块范围中元素的最大值*/cout 请输入你要查找的单词: key;k = block_search(key, a); /*调用函数进行查找*/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