使用开散列实现对字典的查找插入删除（C++实现）

2023-10-27

一、需求分析

【问题描述】实现对字典的查找。

【基本要求】
在分块查找、AVL树、哈希查找、B树或者B+树查找中选择一种你认为最高效的动态查找方法对字典（单词、词性加释义）在内存中的动态查找结构或者在外存的字典文件的构造、查找、插入、删除。

【逻辑操作】
1、利用字典文件构造字典
2、实现对字典的快速查找
3、在字典中任意插入之前不存在的单词
4、任意删除字典中已有的单词

【输入输出要求】
1.字典的构造：从字典文本文件中（在程序中更名为Dictionary1.txt）获取百万级别的单词，构造字典
2. 要有字典使用菜单，便利用户。

二、概要设计

（1）选择采用开散列来构造字典，使用链表来避免冲突；根据关键码直接映射找到单词所在的位置，实现快速查找。

（2）使用结构体word来存储单词及其释义，结构体word中有两个字符串，word字符串和meaning字符串。

（3）使用ChainNode结构体来存储链表结点，每个结构体中有数据data(里面存放word结构体，即一个单词)，状态state(碑，有状态{ Active, Empty, Deleted }，可判断该地址处是否存有数据，是否为空，是否已经被删除等状态)以及链表指针link。

（4）因为测试数据为百万级别的，所以我们开5000的散列，除数取小于5000的最大素数4999，映射地址为为num = 3*num+wd->word[i]（循环）;num%=4999.

三、详细设计

头文件”word.h”

#include<iostream>
#include<string>
using namespace std;

struct word {
	string word;
	string meaning;
};

头文件“ChainNode.h”

#include"word.h"

enum status { Active, Empty, Deleted };


template<class E, class K>
struct ChainNode {                 //各桶中同义词子表的链结点定义
	E data;
	status state;
	ChainNode<E, K> * link;
};

头文件“hash.h”

const int defaultSize = 5000;    //设置散列大小

1.哈希表类定义

template<class E,class K>
class HashTable {
public:
	HashTable(int d, int sz = defaultSize);
	~HashTable() { delete[]ht; }
	bool CreatHashTable();
	ChainNode<E,K>* Search(const K kl);
	void Insert(const E* wd);
	void Insert(const K kl); //重载
	void Remove(const K kl);
private:
	int TableSize;
	int CurrentSize;
	ChainNode<E, K> * ht;     //散列表定义
};

2.哈希表构造函数

template<class E,class K>
HashTable<E, K>::HashTable(int d, int sz)
{
	//divisor = d;
	TableSize = sz;
	CurrentSize = 0;
	ht = new ChainNode<E, K>[sz];
	assert(ht != NULL);
	for (int i = 0; i < TableSize; i++)
	{
		ht[i].state = Empty;
		ht[i].link = NULL;
	}
}

3.初始化函数

template<class E,class K>
bool HashTable<E, K>::CreatHashTable()
{
	E *wd = new word();
	ifstream Dictionary;
	cout << "字典生成中，请稍后……" << endl;
	Dictionary.open("Dictionary1.txt");
	do {
		Dictionary >> wd->word;
		getline(Dictionary, wd->meaning);
		//cout << wd->word << endl;
		Insert(wd);
		if (wd->word == "zoology128")break;
	} while (1);
	cout << "字典生成成功！" << endl;
	return true;
}

4.初始化专用的插入函数

template<class E,class K>
void HashTable<E, K>::Insert(const E* wd)
{
	int r = 0, num = 0;
	while (wd->word[r] != '\0')
	{
		num = 3*num+wd->word[r];
		r++;
	}
	num %= 4999;
	if (num < 0)
		num = -num;
	if (ht[num].state == Empty)
	{
		ht[num].data = *wd;
		ht[num].state = Active;
		CurrentSize++;
	}
	else
	{
		ChainNode<E, K>* newd = new ChainNode<E, K>();
		newd->data = *wd;
		ChainNode<E, K>*p = &ht[num];
		while (p->link!=NULL)
			p = p->link;
		p->link = new ChainNode<E, K>();
		p->link = newd;
	}
}

5.插入函数

template<class E, class K>
void HashTable<E, K>::Insert(const K kl)
{
	E *wd = new word();
	wd->word = kl;
	int r = 0, num = 0;
	while (wd->word[r] != '\0')
	{
		num = 3 * num + wd->word[r];
		r++;
	}
	num %= 4999;
	if (num < 0)
		num = -num;
	if (ht[num].state == Empty)
	{
		ht[num].data = *wd;
		//ht[num].state = Active;
		CurrentSize++;
	}
	else
	{
		ChainNode<E, K>* newd = new ChainNode<E, K>();
		newd->data = *wd;
		ChainNode<E, K>*p = &ht[num];
		while (p->link != NULL)p = p->link;
		p->link = new ChainNode<E, K>();
		p->link = newd;
	}
	cout << "插入成功！" << endl;
}

6.搜索函数

template<class E,class K>
ChainNode<E, K>* HashTable<E, K>::Search(const K kl)
{
	E *wd = new word();
	wd->word = kl;
	int r = 0, num = 0;
	while (wd->word[r] != '\0')
	{
		num = 3 * num + wd->word[r];
		r++;
	}
	num %= 4999;
	if (num < 0)
		num = -num;
	ChainNode<E, K>*p = &ht[num];
	while (p != NULL && p->data.word != wd->word) 
	{
		if (p->link == NULL)
			return NULL;
		p = p->link;
	}
	return p;
}

7.删除函数

template<class E,class K>
void HashTable<E, K>::Remove(const K kl)
{
	E *wd = new word();
	wd->word = kl;
	int r = 0, num = 0;
	while (wd->word[r] != '\0')
	{
		num = 3 * num + wd->word[r];
		r++;
	}
  	num %= 4999;
	if (num < 0)
		num = -num;
	if (ht[num].state == Empty)
		cout << "字典中不存在这个单词！" << endl;
	else
	{
		ChainNode<E, K>*p = &ht[num];
		ChainNode<E, K>*q = p;
		while (p != NULL && p->data.word != wd->word)
		{
			q = p;
			p = p->link;
		}
		if (p == NULL)
			cout << "字典中不存在这个单词！" << endl;
		else
		{
			q->link = p->link;
			delete p;
			p = NULL;
			p->state = Deleted;
			cout << "已删除该单词！" << endl;
		}
	}
}

测试文件“dictionary.cpp”

#include<iostream>
#include"hash.h"
using namespace std;

int Test()
{
	HashTable<word, string>hash1(1999);
	hash1.CreatHashTable();
	cout << "欢迎使用字典！" << endl;
	cout << "1.搜索" << endl;
	cout << "2.插入" << endl;
	cout << "3.删除" << endl;
	int tmp;
	do {
		cout << "请输入你需要进行的操作(按0退出)：" << endl;
		cin >> tmp;
		if (tmp == 1)
		{
			cout << "请输入你需要查找的单词：";
			string a;
			cin >> a;
			ChainNode<word, string>*p;
			p=hash1.Search(a);
			if (p == NULL)
				cout << "字典中没有这个单词！" << endl;
			else
				cout << p->data.word << "	" << p->data.meaning << endl;
		}
		if (tmp == 2)
		{
			cout << "请输入你需要插入的单词：";
			string a;
			cin >> a;
			hash1.Insert(a);
		}
		if (tmp == 3)
		{
			cout << "请输入你需要删除的单词：";
			string a;
			cin >> a;
			hash1.Remove(a);
		}
	} while (tmp);
	return 0;
}
int main()
{
	Test();
	return 0;
}

四、运行截图

在这里插入图片描述
查找和删除操作

查找、删除和插入操作

本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)

数据结构

c