长春网站如何制作,百度收录网站有什么好处,wordpress 客户端使用,个体工商户备案网站备案散列表
完整可编译运行代码#xff1a;Github:Data-Structures-Algorithms-and-Applications/_22hash/
定义
字典的另一种表示方法是散列#xff08;hashing#xff09;。它用一个散列函数#xff08;也称哈希函数#xff09;把字典的数对映射到一个散列表#xff08…散列表
完整可编译运行代码Github:Data-Structures-Algorithms-and-Applications/_22hash/
定义
字典的另一种表示方法是散列hashing。它用一个散列函数也称哈希函数把字典的数对映射到一个散列表也称哈希表的具体位置。如果数对p的关键字是k散列函数为f那么在理想情况下p 在散列表中的位置为fk。暂时假定散列表的每一个位置最多能够存储一个记录。为了搜索关键字为 k 的数对先要计算fk然后查看在散列表的fk处是否已有一个数对。如果有便找到了该数对。如果没有字典就不包含该数对。在前一种情况下可以删除该数对为此只需使散列表的fk位置为空。在后一种情况下可以把该数对插在fk的位置。
初始化一个空字典需要的时间为 Obb 为散列表拥有的位置数查找、插入、删除操作的时间均为01。
散列函数和散列表
桶和起始桶
当关键字的范围太大不能用理想方法表示时可以采用并不理想的散列表和散列函数散列表位置的数量比关键字的个数少散列函数把若干个不同的关键字映射到散列表的同一个位置。散列表的每一个位置叫一个桶bucket对关键字为 k的数对fk是起始桶home bucket桶的数量等于散列表的长度或大小。因为散列函数可以把若干个关键字映射到同一个桶所以桶要能够容纳多个数对。本章我们考虑两种极端情况。第一种情况是每一个桶只能存储一个数对。第二种情况是每一个桶都是一个可以容纳全部数对的线性表。
除法散列函数 f ( k ) k % D ( 10 − 2 ) f(k)k\%D (10-2) f(k)k%D(10−2)
其中 k 是关键字D 是散列表的长度即桶的数量为求模操作符。散列表的位置索引从0到D-1。当D11时与关键字3、22、27、40、80和96分别对应的起始桶是f33f220f275f407f803 和f968。
冲突和溢出
散列表有 11 个桶序号从 0 到 10而且每一个桶可以存储一个数对。除数D为11。因为80%113则 80 的位置为340的位置为40%11765的位置为65%1110。每个数对都在相应的起始桶中。散列表余下的桶为空。 现在假设要插入 58。58 的起始桶为f5858%113。这个桶已被另一个关键字占用。这时就发生了冲突。**当两个不同的关键字所对应的起始桶相同时就是冲突collision发生了。**因为一个桶可以存储多个数对因此发生碰撞也没什么了不起。只要起始桶足够大所有对应同一个起始桶的数对都可存储在一起。如果存储桶没有空间存储一个新数对就是溢出overflow发生了。
我需要一个好的散列函数
当映射到散列表中任何一个桶里的关键字数量大致相等时冲突和溢出的平均数最少。**均匀散列函数uniform hash function**便是这样的函数。
在实际应用中关键字不是从关键字范围内均匀选择的因此有的均匀散列函数表现好一点有一些就差一些。那些在实际应用中性能表现好的均匀散列函数被称为良好散列函数good hash function。
对于除法散列函数假设 D 是偶数。当 k是偶数时fk是偶数当k 是奇数时fk是奇数。例如 k%20当k是偶数时为偶数当k是奇数时为奇数。如果你的应用以偶数关键字为主那么大部分关键字都被映射到序号为偶数的起始桶里。如果你的应用以奇数关键字为主那么大部分关键字都被映射到序号为奇数的起始桶里。因此选择D为偶数得到的是不良散列函数。
当 D 可以被诸如 3、5 和 7 这样的小奇数整除时不会产生良好散列函数。因此要使除法散列函数成为良好散列函数你要选择的除数D应该既不是偶数又不能被小的奇数整除。理想的D是一个素数。当你不能用心算找到一个接近散列表长度的素数时你应该选择不能被2和19之间的数整除的D。
因为在实际应用的字典中关键字是相互关联的所以你所选择的均匀散列函数其值应该依赖关键字的所有位而不是仅仅取决于前几位或后几位或中间几位。当D既是素数又不能被小于20的数整除就能得到良好散列函数。
除法和非整型关键字
为使用除法散列函数在计算fk之前需要把关键字转换为非负整数。
需要将串数据、结构和算法转换为整数。
冲突和溢出的解决方案
线性探查
插入元素
散列表有 11 个桶序号从 0 到 10而且每一个桶可以存储一个数对。除数D为11。因为80%113则 80 的位置为340的位置为40%11765的位置为65%1110。每个数对都在相应的起始桶中。散列表余下的桶为空。 现在假设要插入 58。58 的起始桶为f5858%113。这个桶已被另一个关键字占用。这时就发生了冲突。 要在图 10-2a 的散列表中把 58放进去最简单方法是找到下一个可用的桶。这种解决溢出的方法叫作线性探查Linear Probing。
58 因此被存储在 4 号桶。假设下一个要插入的数对关键字为 2424%1122 号桶为空于是把24放入2号桶。这时的散列表如图 10-2b所示。现在要插入35。35的起始桶2已满。用线性探查结果如图 10-2c 所示。最后一例插入 98。它的起始桶 10已满而下一个可用桶是 0 号桶于是 98 被插入在此。由此看来在寻找下一个可用桶时散列表被视为环形表。
查找元素
假设要查找关键字为k的数对首先搜索起始桶fk然后把散列表当做环表继续搜索下一个桶直到以下情况之一发生为止
1存有关键字 k 的桶已找到即找到了要查找的数对
2到达一个空桶
3又回到起始桶fk。
后两种情况说明关键字为k的数对不存在。
删除一个元素
删除一个记录要保证上述的搜索过程可以正常进行。若在图 10-2c 中删除了关键字 58不能仅仅把4号桶置为空否则就无法找到关键字为35的数对。删除需要移动若干个数对。从删除位置的下一个桶开始逐个检查每个桶以确定要移动的元素直至到达一个空桶或回到删除位置为止。在做删除移动时一定要注意不要把一个数对移到它的起始桶之前否则对这个数对的查找就可能失败。
实现删除的另一个策略是为每个桶增加一个域 neverUsed。在散列表初始化时这个域被置为true。当一个数对存入一个桶中时neverUsed域被置为false。现在搜索的结束条件2变成桶的 neverUsed域为 true。不过在删除时只是把表的相应位置置为空。一个新元素被插入在其对应的起始桶之后所找到的第一个空桶中。注意在这种方案中neverUsed不会重新置为true。用不了多长时间所有或几乎所有桶的neverUsed域都等于false这时搜索是否失败只有检查所有的桶之后才可以确定。为了提高性能当很多空桶的neverUsed域等于false时必须重新组织这个散列表。例如可把所有余下的数对都插到一个空的散列表中。这种方案不太可行
性能分析
我们只分析时间复杂度。设b为散列表的桶数D为散列函数的除数且bD。散列表初始化的时间为0b。当表中有n个记录时最坏情况下的插入和查找时间均为0n。当所有关键字都对应同一个起始桶时便是最坏情况。把字典的散列在最坏情况下的复杂度与线性表在最坏情况下的复杂度相比较二者完全相同。
然而就平均性能而言散列远远优于线性表。令 U n U_n Un和 S n S_n Sn分别表示在一次成功搜索和不成功搜索中平均搜索的桶数其中 n是很大的值。这个平均值是由插入的 n个关键字计算得来的。对于线性探查有如下近似公式 U n ≈ 1 2 ( 1 1 ( 1 − α ) 2 ) ( 10 − 3 ) U_n\approx\frac{1}{2}\left(1 \frac{1}{(1-\alpha)^2}\right)(10-3) Un≈21(1(1−α)21)(10−3) S n ≈ 1 2 ( 1 1 1 − α ) ( 10 − 4 ) S_n\approx\frac{1}{2}\left(1 \frac{1}{1-\alpha}\right)(10-4) Sn≈21(11−α1)(10−4)
其中 α \alpha αn/b为负载因子loading factor。
从上述公式可以证明当 α \alpha α0.5时一次不成功的搜索将平均查找2.5 个桶一次成功的搜索将平均查找 1.5 个桶。当 α \alpha α0.9时这些数字分别为 50.5 和 5.5。当然这时假定 n 比 51 大得多。当负载因子比较小时使用线性探查散列的平均性能比线性表的平均性能要优越许多。一般情况下都是 α \alpha α0.75。可以根据 α \alpha α和n的值确定b的值从什么样的 α \alpha α能接受上考虑。
随机探查分析
用随机数生成器产生一个桶的搜索序列然后用这个序列去确定插入位置。
理 10-1 设p 是某一事件发生的概率。为了该事件发生独立试验的期望次数是 1/p。 U n U_n Un公式按如下方式导出当装载因子是a时一个桶有数对的概率是a没有数对的概率为 p1-a。在随机探查中使用一个独立试验序列进行搜索一次失败的搜索是找到一个空桶为此我们期望搜索的桶数是: U n ≈ a p 1 1 − α ( 10 − 5 ) U_n\approx\frac{a}{p}\frac{1}{1-\alpha}(10-5) Un≈pa1−α1(10−5) S n S_n Sn公式可以从 U n U_n Un公式推导出来。按照插入顺序给散列表的 n个记录编号为12…n。当插入第i个数对时首先通过一次不成功的搜索找到一个空桶然后把该数对插到这个空桶里。在插入第i个数对时装载因子是i-1/b其中b是桶数。从公式10-5得出在搜索第i个桶时查看的期望桶数是: a 1 − i − 1 b \frac{a}{1-\frac{i-1}{b}} 1−bi−1a 假设每一个数对搜索的概率是相等的由此可得 就需要查看的桶数而言线性探查的性能不如随机探查。例如当a0.9时使用线性探查进行一次不成功的搜索而期望查看的桶数是50.5而用随机探查时这个数降到10。
为什么不使用随机探查
真正影响运行时间的不是要查看的桶数。计算一个随机数比查看若干个桶更需要时间。随机探查是用随机方式搜索散列表高速缓存使运行时间增大。因此尽管随机探查需要查看的桶数要比线性探查少但是它实际使用的时间很多除非装载因子接近1。
链式散列
如果散列表的每一个桶可以容纳无限多个记录那么溢出问题就不存在了。实现这个目标的一个方法是给散列表的每一个位置配置一个线性表。这时每一个数对可以存储在它的起始桶线性表中。 为搜索关键字值为 k的记录首先计算其起始桶k%D然后搜索该桶所对应的链表。为插入一个记录首先要保证散列表没有一个记录与该记录的关键字相同为此而进行的搜索仅限于该记录的起始桶所对应的链表。要删除一个关键字为k的记录我们要搜索它所对应的起始桶链表找到该记录然后删除。 在图 10-4的每个链表上增加一个尾节点可以改进一些程序的性能。尾节点的关键字值最起码要比插入的所有数对的关键字都大。在图10-4中尾节点的关键字用正无穷来表示。在实际应用中当关键字为整数时可以用limits.h文件中定义的INT_MAX常量来替代。有了尾节点就可以省去在sortedChain的方法中出现的大部分对空指针的检验操作。注意在图 10-4 中每个链表都有不同的尾节点而实际上所有链表可共用一个尾节点。
链式散列与线性探查相比
线性探查占用的空间小于链式散列的空间因为链式散列需要存储一些指针。
使用链表时要检查的节点数比使用线性和随机探查时要检查的桶数少。详细证明见《数据结构、算法与应用C语言描述》原书第二版链式散列介绍中 与线性探查比较 公式详细介绍
链式散列与跳表相比
通过使用随机过程跳表和散列操作的平均复杂度分别是对数级和常数级。跳表方法的最坏时间复杂度为OnmaxLevel而散列的最坏时间复杂度为On。跳表中指针平均占用的空间约为maxLeveln/1-p最坏情况需要maxLevel*n1个指针空间。就最坏情况下的空间需求而言跳表远远大于链式散列。链式散列需要的指针空间为Dn。
不过跳表比散列更灵活。例如只需简单地沿着 0 级链就可以在线性时间内按关键字升序输出所有的元素。使用链式散列时需要OD时间去搜索最多D个非空链表另外需要OnlogD时间把有序链表按关键字升序合并。合并过程如下
1把链表放到一个队列中
2从队列中提取一对链表把它们合并为一个有序链表然后放入队列
3重复步骤2直至队列中仅剩一个链表。其他的操作如查找或删除其关键字最大或最小的数对使用散列也要花费更多的时间仅考虑平均复杂度。
代码测试
main.cpp
/*
Project name : allAlgorithmsTest
Last modified Date: 2022年8月13日17点38分
Last Version: V1.0
Descriptions: main()函数控制运行所有的测试函数
*/
#include iostream
#include _25hashTable.h
#include _26hashChains.hint main()
{hashTableTest();hashChainsTest();return 0;
}_25hash.h
/*
Project name : allAlgorithmsTest
Last modified Date: 2022年8月23日10点18分
Last Version: V1.0
Descriptions: 哈希---散列函数(将type K转换为非负整数)
// functions to convert from type K to nonnegative integer
// derived from similar classes in SGI STL
*/
#pragma once
#ifndef _HASH_H_
#define _HASH_H_
#include iostream
#include string
using namespace std;
/*之前名称时hash实例化hash一直报错然后我就各种找原因*/
/*后来发现原因可能是 CSTL源文件定义了hash类所以我后面定义的模板就不作数所以一直报错*/
/*因此解决方案就是将类名称hash改为hashNode*/
template class K
class hashNode
{
public:size_t operator()(const int theKey) const{return size_t(theKey);}
};/*这是一个实例化*/
template
class hashNodestring
{
public:size_t operator()(const string theKey) const{// Convert theKey to a nonnegative integer.unsigned long hashNodeValue 0;int length (int)theKey.length();for (int i 0; i length; i)hashNodeValue 5 * hashNodeValue theKey.at(i);return size_t(hashNodeValue);}
};
/*这是一个实例化*/
template
class hashNodeint
{
public:size_t operator()(const int theKey) const{return size_t(theKey);}
};
/*这是一个实例化*/
template
class hashNodelong
{
public:size_t operator()(const long theKey) const{return size_t(theKey);}
};#endif_25hashTable.h
/*
Project name : allAlgorithmsTest
Last modified Date: 2022年8月23日10点18分
Last Version: V1.0
Descriptions: 哈希表(数组存储)---使用线性探查的头文件---是无序的
// hash table using linear open addressing and division
// implements dictionary methods other than erase
*/
#pragma once
#ifndef _HASHTABLE_H_
#define _HASHTABLE_H_
#include iostream
#include _1myExceptions.h
#include _25hash.h // mapping functions from K to nonnegative integer
using namespace std;
/*测试函数*/
void hashTableTest();templateclass K, class E
class hashTable
{
public:hashTable(int theDivisor 11);~hashTable() { delete[] table; }bool empty() const { return dSize 0; }int size() const { return dSize; }pairconst K, E* find(const K) const;void insert(const pairconst K, E);void erase(const K theKey);/*友元函数*//*输入字典*/istream input(istream in);
// friend istream operator K, E(istream in, hashTableK, E m);/*输出字典*/ostream output(ostream out) const;
// friend ostream operator K, E(ostream out, const hashTableK, E m);protected:int search(const K) const;pairconst K, E** table; // hash tablehashNodeK hashNode; // maps type K to nonnegative integerint dSize; // number of pairs in dictionaryint divisor; // hash function divisor
};/*输入字典*/
templateclass K, class E
istream hashTableK, E::input(istream in)
{int numberOfElement 0;cout Please enter the number of element:;while (!(in numberOfElement)){in.clear();//清空标志位while (in.get() ! \n)//删除无效的输入continue;cout Please enter the number of element:;}K first;E second;for (int i 0; i numberOfElement; i){cout Please enter the element i 1 :;while (!(in first second)){in.clear();//清空标志位while (in.get() ! \n)//删除无效的输入continue;cout Please enter the element i 1 :;}const pairconst K, E element(first, second);insert(element);}return in;
}
templateclass K, class E
istream operator(istream in, hashTableK, E m){m.input(in);return in;
}
/*输出字典*/
templateclass K, class E
ostream hashTableK, E::output(ostream out) const
{for (int i 0; i divisor; i)if (table[i] nullptr)cout nullptr ;elsecout ( table[i]-first , table[i]-second ) ;cout endl;return out;
}templateclass K, class E
ostream operator(ostream out, const hashTableK, E m){m.output(out);return out;
}templateclass K, class E
hashTableK, E::hashTable(int theDivisor)
{divisor theDivisor;dSize 0;// allocate and initialize hash table arraytable new pairconst K, E*[divisor];for (int i 0; i divisor; i)table[i] nullptr;
}templateclass K, class E
int hashTableK, E::search(const K theKey) const
{// Search an open addressed hash table for a pair with key theKey.// Return location of matching pair if found, otherwise return// location where a pair with key theKey may be inserted// provided the hash table is not full.int i (int)hashNode(theKey) % divisor; // home bucketint j i; // start at home bucketdo{if (table[j] nullptr || table[j]-first theKey)return j;j (j 1) % divisor; // next bucket} while (j ! i); // returned to home bucket?return j; // table full
}templateclass K, class E
pairconst K, E* hashTableK, E::find(const K theKey) const
{// Return pointer to matching pair.// Return nullptr if no matching pair.// search the tableint b search(theKey);// see if a match was found at table[b]if (table[b] nullptr || table[b]-first ! theKey)return nullptr; // no matchreturn table[b]; // matching pair
}templateclass K, class E
void hashTableK, E::insert(const pairconst K, E thePair)
{// Insert thePair into the dictionary. Overwrite existing// pair, if any, with same key.// Throw hashTableFull exception in case table is full.// search the table for a matching pairint b search(thePair.first);// check if matching pair foundif (table[b] nullptr){// no matching pair and table not fulltable[b] new pairconst K, E(thePair);dSize;}else{// check if duplicate or table fullif (table[b]-first thePair.first){// duplicate, change table[b]-secondtable[b]-second thePair.second;}else // table is fullthrow hashTableFull();}
}/*删除关键字为theKey的元素*/
templateclass K, class E
void hashTableK, E::erase(const K theKey)
{int i (int)hashNode(theKey) % divisor;int j i;/*从起始桶开始寻找关键字为theKey的元素*/while (table[j] ! nullptr table[j]-first ! theKey){j (j) % divisor;/*如果找完了所有桶都没找到以theKey为关键字的数对说明该数对不存在抛出异常*/if (j i)throw illegalParameterValue(The key is not exist);}if(table[j] nullptr)throw illegalParameterValue(The key is not exist);/*能到这里说明已经找到以theKey为关键字的数对了*/i j;//使用i记录该数对的位置delete table[i];//将该数对删除table[i] nullptr;j;//找到下一个数对/*将后面的数对前移*//*不是空桶不是起始桶不是原始桶*/while (table[j] ! nullptr (int)hashNode(table[j]-first) % divisor ! j j ! i){table[j - 1] table[j];//移动后面的元素j (j) % divisor;}
}
#endif_25hashTable.cpp
/*
Project name : allAlgorithmsTest
Last modified Date: 2022年8月23日10点18分
Last Version: V1.0
Descriptions: 哈希表(数组存储)---使用线性探查的cpp文件
*/
#include iostream
#include _25hashTable.h
using namespace std;void hashTableTest()
{cout endl *********************************hashTableTest()函数开始************************************** endl;hashTableint, int a;//测试输入和输出cout endl 测试友元函数******************************************* endl;cout 输入输出************************ endl;cin a;cout hashTable a is: a;cout endl 测试成员函数******************************************* endl;cout empty()************************* endl;cout a.empty() a.empty() endl;cout size()************************** endl;cout a.size() a.size() endl;cout find()************************** endl;cout a.find(1)-second a.find(1)-second endl;cout insert()************************ endl;pairconst int, int insertData(3, 4);a.insert(insertData);cout hashTable a is: a;cout erase()************************* endl;a.erase(2);cout hashTable a is: a;cout *********************************hashTableTest()函数结束************************************** endl;
}_23dictionary.h
/*
Project name : allAlgorithmsTest
Last modified Date: 2022年8月22日09点17分
Last Version: V1.0
Descriptions: 字典的抽象类
*/
/*
pair:介绍是将2个数据组合成一组数据,是一个结构体主要的两个成员变量first和second分别存储两个数据.使用使用std命名空间引入对组std::pair
*/
#pragma once
#ifndef _DICTIONARY_H_
#define _DICTIONARY_H_
using namespace std;
templateclass K,class E
class dictionary
{
public:virtual ~dictionary() {}/*返回为true当且仅当字典为空*/virtual bool empty() const 0;/*返回字典中数对的数目*/virtual int size() const 0;/*返回匹配数对的指针*/virtual pairconst K, E* find(const K) const 0;/*删除匹配的数对*/virtual void erase(const K) 0;/*往字典中插入一个数对*/virtual void insert(const pairconst K, E) 0;
};
#endif_23pairNode.h
/*
Project name : allAlgorithmsTest
Last modified Date: 2022年8月22日09点17分
Last Version: V1.0
Descriptions: 是字典的一个节点
*/
#pragma once
#ifndef _PAIRNODE_H_
#define _PAIRNODE_H_
using namespace std;
template class K, class E
struct pairNode
{typedef pairconst K, E pairType;pairType element;pairNodeK, E* next;pairNode(const pairType thePair) :element(thePair) {}pairNode(const pairType thePair, pairNodeK, E* theNext):element(thePair) {next theNext;}
};
#endif_23dictionaryChain.h
/*
Project name : allAlgorithmsTest
Last modified Date: 2022年8月22日09点17分
Last Version: V1.0
Descriptions: 使用链表实现的字典的头文件---是有序的
*/
#pragma once
#ifndef _DICTIONARY_CHAIN_H_
#define _DICTIONARY_CHAIN_H_
#include iostream
#include _23pairNode.h
#include _23dictionary.h
using namespace std;
/*测试函数*/
void dictionaryChainTest();templateclass K, class E
class dictionaryChain : public dictionaryK, E
{
public:/*成员函数*//*构造函数和析构函数*/dictionaryChain() { firstNode nullptr; dSize 0; }~dictionaryChain();/*其他成员函数*/bool empty() const { return dSize 0; }int size() const { return dSize; }pairconst K, E* find(const K) const;void erase(const K);void insert(const pairconst K, E);/*友元函数*//*输入字典*/istream input(istream in);
// friend istream operator K,E(istream in, dictionaryChainK,E m);/*输出字典*/ostream output(ostream out) const;
// friend ostream operator K,E(ostream out, const dictionaryChainK,E m);
protected:pairNodeK, E* firstNode; // pointer to first node in chainint dSize; // number of elements in dictionary
};/*输入字典*/
templateclass K, class E
istream dictionaryChainK, E::input(istream in)
//istream operator(istream in, dictionaryChainK,E m)
{int numberOfElement 0;cout Please enter the number of element:;while (!(in numberOfElement)){in.clear();//清空标志位while (in.get() ! \n)//删除无效的输入continue;cout Please enter the number of element:;}pairK, E element;for (int i 0; i numberOfElement; i){cout Please enter the element i 1 :;while (!(in element.first element.second)){in.clear();//清空标志位while (in.get() ! \n)//删除无效的输入continue;cout Please enter the element i 1 :;}insert(element);}return in;
}
templateclass K, class E
istream operator(istream in, dictionaryChainK,E m){m.input(in);return in;
}
/*输出字典*/
templateclass K, class E
ostream dictionaryChainK, E::output(ostream out) const
//ostream operator(ostream out, const dictionaryChainK,E m)
{pairNodeK, E* currentNode firstNode;while (currentNode ! nullptr){out ( currentNode-element.first , currentNode-element.second ) ;currentNode currentNode-next;}cout endl;return out;
}
templateclass K, class E
ostream operator(ostream out, const dictionaryChainK,E m){m.output(out);return out;
}
/*析构函数*/
templateclass K,class E
dictionaryChainK,E::~dictionaryChain()
{pairNodeK, E* nextNode;while (firstNode ! nullptr){nextNode firstNode-next;delete firstNode;firstNode nextNode;}
}
/*寻找关键字为key的数对并返回*/
templateclass K, class E
pairconst K, E* dictionaryChainK, E::find(const K key) const
{//返回匹配的数对的指针//如果不存在匹配的数对则返回nullptrpairNodeK, E* currentNode firstNode;while (currentNode ! nullptr currentNode-element.first ! key)currentNode currentNode-next;if (currentNode ! nullptr currentNode-element.first key)return currentNode-element;return nullptr;//如果没找到就返回nullptr
}
/*删除关键字为key的数对*/
templateclass K, class E
void dictionaryChainK, E::erase(const K key)
{//删除关键字为key的数对pairNodeK, E* p firstNode;//存储的是插入元素之后的位置pairNodeK, E* tp nullptr;//存储的是插入元素之前的位置//搜索关键字为key的数对while (p ! nullptr p-element.first key){tp p;p p-next;}//确定是否匹配if (p ! nullptr p-element.first key)if (tp nullptr) firstNode p-next;//p是第一个节点else tp-next p-next;delete p;dSize--;
}
/*往字典中插入data,覆盖已经存在的匹配的数对*/
templateclass K,class E
void dictionaryChainK, E::insert(const pairconst K, E data)
{pairNodeK, E* p firstNode;//存储的是插入元素之后的位置pairNodeK, E* tp nullptr;//存储的是插入元素之前的位置while (p ! nullptr p-element.first data.first){tp p;p p-next;}//检查是否有匹配的数对if (p ! nullptr p-element.first data.first){p-element.second data.second;return;}//无匹配的数对为thePair建立新节点pairNodeK, E* newNode new pairNodeK, E(data, p);//在tp之后插入新节点if (tp nullptr) firstNode newNode;else tp-next newNode;dSize;return;
}#endif_26hashChains.h
/*
Project name : allAlgorithmsTest
Last modified Date: 2022年8月24日11点16分
Last Version: V1.0
Descriptions: 哈希表---链式散列(链表存储)---头文件---是无序的
// hash table using sorted chains and division
// implements all dictionary methods
*/
#pragma once
#ifndef _HASHCHAINDS_H_
#define _HASHCHAINDS_H_
#include iostream
#include _23dictionary.h
#include _23dictionaryChain.h
#include _25hash.h
using namespace std;
/*测试函数*/
void hashChainsTest();templateclass K, class E
class hashChains : public dictionaryK, E
{
public:hashChains(int theDivisor 11){divisor theDivisor;dSize 0;// allocate and initialize hash table arraytable new dictionaryChainK, E[divisor];}~hashChains() { delete[] table; }bool empty() const { return dSize 0; }int size() const { return dSize; }pairconst K, E* find(const K theKey) const{return table[hashNode(theKey) % divisor].find(theKey);}void insert(const pairconst K, E thePair){int homeBucket (int)hashNode(thePair.first) % divisor;int homeSize table[homeBucket].size();table[homeBucket].insert(thePair);if (table[homeBucket].size() homeSize)dSize;}void erase(const K theKey){table[hashNode(theKey) % divisor].erase(theKey);}/*友元函数*//*输入字典*/istream input(istream in);
// friend istream operator K, E(istream in, hashChainsK, E m);/*输出字典*/ostream output(ostream out) const;
// friend ostream operator K, E(ostream out, const hashChainsK, E m);
protected:dictionaryChainK, E* table; // hash tablehashNodeK hashNode; // maps type K to nonnegative integerint dSize; // number of elements in listint divisor; // hash function divisor
};/*输入字典*/
templateclass K, class E
istream hashChainsK, E::input(istream in)
{int numberOfElement 0;cout Please enter the number of element:;while (!(in numberOfElement)){in.clear();//清空标志位while (in.get() ! \n)//删除无效的输入continue;cout Please enter the number of element:;}K first;E second;for (int i 0; i numberOfElement; i){cout Please enter the element i 1 :;while (!(in first second)){in.clear();//清空标志位while (in.get() ! \n)//删除无效的输入continue;cout Please enter the element i 1 :;}const pairconst K, E element(first, second);cout element.first endl;cout element.second endl;insert(element);}return in;
}
templateclass K, class E
istream operator(istream in, hashChainsK, E m){m.input(in);return in;
}
/*输出字典*/
templateclass K, class E
ostream hashChainsK, E::output(ostream out) const
{for (int i 0; i divisor; i){if (table[i].size() 0)cout nullptr endl;elsecout table[i] ;}return out;
}
templateclass K, class E
ostream operator(ostream out, const hashChainsK, E m){m.output(out);return out;
}#endif_26hashChains.cpp
/*
Project name : allAlgorithmsTest
Last modified Date: 2022年8月24日11点16分
Last Version: V1.0
Descriptions: 哈希表---链式散列(链表存储)---cpp文件
// hash table using sorted chains and division
// implements all dictionary methods
*/
#include iostream
#include _26hashChains.h
using namespace std;void hashChainsTest()
{cout endl *********************************hashChainsTest()函数开始************************************* endl;hashChainsint, int a;//测试输入和输出cout endl 测试友元函数******************************************* endl;cout 输入输出************************ endl;cin a;cout hashChains a is: a;cout endl 测试成员函数******************************************* endl;cout empty()************************* endl;cout a.empty() a.empty() endl;cout size()************************** endl;cout a.size() a.size() endl;cout find()************************** endl;cout a.find(1)-second a.find(1)-second endl;cout insert()************************ endl;pairconst int, int insertData(3, 4);a.insert(insertData);cout hashChains a is: a;cout erase()************************* endl;a.erase(1);cout hashChains a is: a;cout *********************************hashChainsTest()函数结束************************************* endl;
}_1myExceptions.h
/*
Project name : allAlgorithmsTest
Last modified Date: 2022年8月13日17点38分
Last Version: V1.0
Descriptions: 综合各种异常
*/
#pragma once
#ifndef _MYEXCEPTIONS_H_
#define _MYEXCEPTIONS_H_
#include string
#includeiostreamusing namespace std;// illegal parameter value
class illegalParameterValue
{
public:illegalParameterValue(string theMessage Illegal parameter value){message theMessage;}void outputMessage() {cout message endl;}
private:string message;
};// illegal input data
class illegalInputData
{
public:illegalInputData(string theMessage Illegal data input){message theMessage;}void outputMessage() {cout message endl;}
private:string message;
};// illegal index
class illegalIndex
{
public:illegalIndex(string theMessage Illegal index){message theMessage;}void outputMessage() {cout message endl;}
private:string message;
};// matrix index out of bounds
class matrixIndexOutOfBounds
{
public:matrixIndexOutOfBounds(string theMessage Matrix index out of bounds){message theMessage;}void outputMessage() {cout message endl;}
private:string message;
};// matrix size mismatch
class matrixSizeMismatch
{
public:matrixSizeMismatch(string theMessage The size of the two matrics doesnt match){message theMessage;}void outputMessage() {cout message endl;}
private:string message;
};// stack is empty
class stackEmpty
{
public:stackEmpty(string theMessage Invalid operation on empty stack){message theMessage;}void outputMessage() {cout message endl;}
private:string message;
};// queue is empty
class queueEmpty
{
public:queueEmpty(string theMessage Invalid operation on empty queue){message theMessage;}void outputMessage() {cout message endl;}
private:string message;
};// hash table is full
class hashTableFull
{
public:hashTableFull(string theMessage The hash table is full){message theMessage;}void outputMessage() {cout message endl;}
private:string message;
};// edge weight undefined
class undefinedEdgeWeight
{
public:undefinedEdgeWeight(string theMessage No edge weights defined){message theMessage;}void outputMessage() {cout message endl;}
private:string message;
};// method undefined
class undefinedMethod
{
public:undefinedMethod(string theMessage This method is undefined){message theMessage;}void outputMessage() {cout message endl;}
private:string message;
};
#endif运行结果
C:\Users\15495\Documents\Jasmine\prj\_Algorithm\Data Structures, Algorithms and Applications in C\_22hash\cmake-build-debug\_22hash.exe*********************************hashTableTest()函数开始**************************************测试友元函数*******************************************
输入输出************************
Please enter the number of element:3
Please enter the element 1:1 2
Please enter the element 2:2 4
Please enter the element 3:5 6
hashTable a is:nullptr (1,2) (2,4) nullptr nullptr (5,6) nullptr nullptr nullptr nullptr nullptr 测试成员函数*******************************************
empty()*************************
a.empty() 0
size()**************************
a.size() 3
find()**************************
a.find(1)-second 2
insert()************************
hashTable a is:nullptr (1,2) (2,4) (3,4) nullptr (5,6) nullptr nullptr nullptr nullptr nullptr
erase()*************************
hashTable a is:nullptr (1,2) nullptr (3,4) nullptr (5,6) nullptr nullptr nullptr nullptr nullptr
*********************************hashTableTest()函数结束***********************************************************************hashChainsTest()函数开始*************************************测试友元函数*******************************************
输入输出************************
Please enter the number of element:3
Please enter the element 1:1 2
1
2
Please enter the element 2:3 5
3
5
Please enter the element 3:6 9
6
9
hashChains a is:nullptr
(1 ,2)nullptr
(3 ,5)nullptr
nullptr
(6 ,9)nullptr
nullptr
nullptr
nullptr测试成员函数*******************************************
empty()*************************
a.empty() 0
size()**************************
a.size() 3
find()**************************
a.find(1)-second 2
insert()************************
hashChains a is:nullptr
(1 ,2)nullptr
(3 ,4)nullptr
nullptr
(6 ,9)nullptr
nullptr
nullptr
nullptr
erase()*************************
hashChains a is:nullptr
nullptr
nullptr
(3 ,4)nullptr
nullptr
(6 ,9)nullptr
nullptr
nullptr
nullptr
*********************************hashChainsTest()函数结束*************************************Process finished with exit code 0
