亚洲激情专区-91九色丨porny丨老师-久久久久久久女国产乱让韩-国产精品午夜小视频观看

溫馨提示×

溫馨提示×

您好,登錄后才能下訂單哦!

密碼登錄×
登錄注冊×
其他方式登錄
點擊 登錄注冊 即表示同意《億速云用戶服務條款》

模擬實現英漢字典(使用key/value形式的哈希表)

發布時間:2020-06-29 07:40:06 來源:網絡 閱讀:639 作者:稻草陽光L 欄目:開發技術

    上一篇博客我們實現了key形式的線性探測法處理哈希沖突,有了前面的基礎,我們就可以實現更加有難度的key/value形式的二次探測。

  •   什么是key/value形式呢?

 key/value形式就是在哈希表中,有一個決定數據在表中位置的關鍵字key這個關鍵字所攜帶的值value

   在這里我們的目標是實現一個英漢字典,一個英語字符串就是key,對應的有一個漢語翻譯value,通過key我們可以找到value。所以在這里key和value是“綁”在一起的,我們就用一個結構體來聚合起來:

template<class K,class V>
struct Key_Value
{
	K _key;
	V _value;
	Key_Value(const K& key=K(), const V& value=V())
		:_key(key)
		, _value(value)
	{}
};

 key_value的構造函數中的形參key和value都有一個默認值,默認值是一個臨時對象。

  • 還是同樣的方法,我們用哈希表來實現字典,哈希表的查找效率真的太誘人!!

    字典的結構如下:

#pragma once
#include<iostream>
#include<string>
using namespace std;
enum State
{
	EXIST,
	EMPTY,
	DELETE
};
template<class T>
struct DefaultFunc
{
	size_t operator()(const T& data)
	{
		return (size_t)data;
	}
};

struct StringFunc
{
	size_t operator()(const string& str)
	{
		size_t sum = 0;
		for (size_t i = 0; i < str.size(); ++i)
		{
			sum += str[i];
		}
		return sum;
	}
};
template<class K,class V,class FuncModel=DefaultFunc<K>>
class Dictionary
{
	typedef Key_Value<K, V> KV;
public:
	Dictionary();
	//~Dictionary();
	Dictionary(size_t size);//初始化字典的大小
	bool Add(const K& key, const V& value);
	bool Delete(const K& key);
	size_t Find(const K& key);
	bool Alter(const K& key,const K& newkey,const V& newvalue);
	void Print();
protected:
	size_t HashFunc(const K& key);//哈希函數
	void Swap(Dictionary<K, V, FuncModel>& d);
protected:
	KV* _table;
	State* _state;
	size_t _size;
	size_t _capacity;
	FuncModel _HF;
};

對于一個英漢字典我們要實現的是它的增刪改查功能

(一)添加條目:

template<class K, class V, class FuncModel = DefaultFunc<K>>
bool Dictionary<K, V, FuncModel>::Add(const K& key, const V& value)
{
	if (_size * 10 >= _capacity * 8)//載荷因子超過0.8,增容
	{
		Dictionary<K, V, FuncModel> tmp(_capacity * 2 + 1);
		for (size_t i = 0; i < _capacity; ++i)
		{
			if (_state[i] == EXIST)
			{
				KV node(_table[i]._key, _table[i]._value);
				size_t adress = HashFunc(_table[i]._key);
				size_t index = adress;
				size_t flag = 0;
				while (tmp._state[index] == EXIST)
				{
					index = adress + flag*flag;
					while (index >= _capacity)//如果到了散列表的末尾,要返回表的頭
					{
						index -= _capacity;
					}
					flag++;
				}
				tmp._table[index] = node;
				tmp._size++;
				tmp._state[index] = EXIST;
			}
		}
		Swap(tmp);//this和tmp交換內容
	}
	size_t adress = HashFunc(key);
	size_t index = adress;//adress是不能變的,用index來標記最后的位置
	size_t flag = 0;
	while (_state[index] == EXIST)//二次探測
	{
		index = adress + flag*flag;
		while(index >= _capacity)//如果到了散列表的末尾,要返回表的頭
		{
			index -= _capacity;
		}
		flag++;
	}
	KV tmp(key, value);
	_table[index] = tmp;
	_state[index] = EXIST;
	_size++;
	return true;
}

(二)查找條目:

template<class K, class V, class FuncModel = DefaultFunc<K>>
size_t Dictionary<K, V, FuncModel>::Find(const K& key)
{
	size_t adress = HashFunc(key);
	size_t index = adress;
	for (size_t flag = 0; flag < _capacity;)
	{
		if (_table[index]._key == key)//二次探測
		{
			return index;
		}
		index = adress + flag*flag;
		while (index >= _capacity)
		{
			index -= _capacity;
		}
		flag++;
	}
	return -1;
}

  在查找的時候flag不僅用來控制查找的次數,還可以控制二次探測的增量(i^2,i++)。最多查找_capacity次就可以了。找了_capacity次還沒找到就說明不存在。

(三)刪除條目:

   調用查找條目,若找到則刪除,否則返回flase.

template<class K, class V, class FuncModel = DefaultFunc<K>>
bool Dictionary<K, V, FuncModel>::Delete(const K& key)
{
	size_t index = Find(key);
	if (index >= 0)
	{
		_state[index] = DELETE;
		_size--;
		return true;
	}
	return false;
}

(四)修改條目:

   調用查找條目,若找到則修改,否則返回flase.

emplate<class K, class V, class FuncModel = DefaultFunc<K>>
bool Dictionary<K, V, FuncModel>::
Alter(const K& key,const K& newkey,const V& newvalue)
{
	size_t index = Find(key);
	if (index > 0)
	{
		_table[index]._key = newkey;
		_table[index]._value = newvalue;
		return true;
	}
	return false;
}


向AI問一下細節

免責聲明:本站發布的內容(圖片、視頻和文字)以原創、轉載和分享為主,文章觀點不代表本網站立場,如果涉及侵權請聯系站長郵箱:is@yisu.com進行舉報,并提供相關證據,一經查實,將立刻刪除涉嫌侵權內容。

AI

拉孜县| 吉水县| 大渡口区| 曲沃县| 枣庄市| 黄骅市| 托里县| 湖北省| 加查县| 灵石县| 紫金县| 武山县| 黄梅县| 贡山| 双城市| 博罗县| 红河县| 平定县| 建阳市| 新泰市| 望江县| 安化县| 江永县| 安溪县| 利辛县| 高邑县| 泸水县| 太康县| 阳曲县| 广汉市| 敖汉旗| 惠水县| 阜城县| 宜章县| 平罗县| 周口市| 沙河市| 枣庄市| 全州县| 霍州市| 卓资县|