哈希表的C++实现(转)
2018-06-18 00:02:21来源:未知 阅读 ()
哈希表的几个概念:
映像:由哈希函数得到的哈希表是一个映像。
冲突:如果两个关键字的哈希函数值相等,这种现象称为冲突。
处理冲突的几个方法:
1、开放地址法:用开放地址处理冲突就是当冲突发生时,形成一个地址序列,沿着这个序列逐个深测,直到找到一个“空”的开放地址,将发生冲突的关键字值存放到该地址中去。
例如:hash(i)=(hash(key)+d(i)) MOD m (i=1,2,3,......,k(k<m-1)) d为增量函数,d(i)=d1,d2,d3,...,dn-1
根据增量序列的取法不同,可以得到不同的开放地址处理冲突探测方法。
有线性探测法、二次方探测法、伪随机探测法。
2、链地址法:把所有关键字为同义词的记录存储在一个线性链表中,这个链表成为同义词链表,即把具有相同哈希地址的关键字值存放在同义链表中。
3、再哈希表:费时间的一种方法
下面是代码:
文件"myhash.h"
- #include<iostream>
- using namespace std;
- typedef int KeyType; //设关键字域为整形,需要修改类型时,只需修改这里就可以
- const int NULLKEY=0; //NULLKEY表示该位置无值
- int c=0; //用来统计冲突次数
- struct Elemtype //数据元素类型
- {
- KeyType key;
- int ord;
- };
- int hashsize[]={11,19,29,37,47}; //hash表容量递增表
- int Hash_length=0;//hash表表长
- class HashTable
- {
- private:
- Elemtype *elem; //数据元素数组,动态申请
- int count;// 当前数据元素个数
- int size; //决定hash表的容量为第几个,hashsize[size]为当前hash容量
- public:
- int Init_HashTable() //构造一个空hash表
- {
- int i;
- count=0;
- size=0; //初始化容量为hashsize[0]=11
- Hash_length=hashsize[0];
- elem=new Elemtype[Hash_length];
- if(!elem)
- {
- cout<<"内存申请失败"<<endl;
- exit(0);
- }
- for(i=0;i<Hash_length;i++)
- elem[i].key=NULLKEY;
- return 1;
- }
- void Destroy_HashTable()
- {
- delete[]elem;
- elem=NULL;
- count=0;
- size=0;
- }
- unsigned Hash(KeyType k) //hash函数的一种(取模法)
- {
- return k%Hash_length;
- }
- void Collision(int &p,int d) //解决冲突
- {
- p=(p+d)%Hash_length; //采用开放地址法里的线性探测
- }
- bool Search_Hash(KeyType k,int &p) //查找
- {
- //在开放地址hash表中查找关键字等于k的元素
- //若找到用p表示待查数据,查找不成功时,p指向的是可插入地址
- c=0;
- p=Hash(k); //求hash地址
- while(elem[p].key!=NULLKEY && elem[p].key!=k)
- {
- c++;
- if(c<Hash_length)
- Collision(p,c);
- else
- return 0; //表示查找不成功
- }
- if(elem[p].key==k)
- return 1;
- else
- return 0;
- }
- int Insert_Hash(Elemtype e) //插入
- {
- //在查找不成功的情况下将k插入到hash表中
- int p;
- if(Search_Hash(e.key,p))
- return -1; //表示该元素已在hash表中
- else if(c<hashsize[size]/2) //冲突次数未达到上限
- {
- //插入e
- elem[p]=e;
- count++;
- return 1;
- }
- else
- ReCreate_HashTable(); // 重建hash表
- return 0; //插入失败
- }
- void ReCreate_HashTable() //重建hash表
- {
- int i,count2=count;
- Elemtype *p,*elem2=new Elemtype[count];
- p=elem2;
- cout<<"____重建hash表_____"<<endl;
- for(i=0;i<Hash_length;i++) //将原有元素暂存到elem2中
- if(elem[i].key!=NULLKEY)
- *p++=*(elem+i);
- count=0;
- size++; //hash容量增大
- Hash_length=hashsize[size];
- p=new Elemtype[Hash_length];
- if(!p)
- {
- cout<<"空间申请失败"<<endl;
- exit(0);
- }
- elem=p;
- for(i=0;i<Hash_length;i++)
- elem[i].key=NULLKEY;
- for(p=elem2;p<elem2+count2;p++) //将原有元素放回新表
- Insert_Hash(*p);
- }
- void Traverse_HashTable()
- {
- cout<<"哈希地址0->"<<Hash_length-1<<endl;
- for(int i=0;i<Hash_length;i++)
- if(elem[i].key!=NULLKEY)
- cout<<"元素的关键字值和它的标志分别是:"<<elem[i].key<<" "<<elem[i].ord<<endl;
- }
- void Get_Data(int p)
- {
- cout<<"元素的关键字值和它的标志分别是:"<<elem[p].key<<" "<<elem[p].ord<<endl;
- }
- };
测试函数"main.cpp"
- #include"myhash.h"
- int main()
- {
- Elemtype r[12]={{17,1},{60,2},{29,3},{38,4},{1,5},{2,6},{3,7},{4,8},{5,9},{6,10},{7,11},{8,12}};
- HashTable H;
- int i,p,j;
- KeyType k;
- H.Init_HashTable();
- for(i=0;i<11;i++) //插入前11个记录
- {
- j=H.Insert_Hash(r[i]);
- if(j==-1)
- cout<<"表中已有关键字为"<<r[i].key<<" "<<r[i].ord<<"的记录"<<endl;
- }
- cout<<"按哈希地址顺序遍历哈希表"<<endl;
- H.Traverse_HashTable();
- cout<<endl;
- cout<<"输入要查找的记录的关键字:";
- cin>>k;
- j=H.Search_Hash(k,p);
- if(j==1)
- H.Get_Data(p);
- else
- cout<<"无此记录"<<endl;
- j=H.Insert_Hash(r[11]); //插入最后一个元素
- if(j==0)
- {
- cout<<"插入失败"<<endl;
- cout<<"需要重建哈希表才可以插入"<<endl;
- cout<<"____重建哈希表____"<<endl;
- H.Insert_Hash(r[i]); //重建后重新插入
- }
- cout<<"遍历重建后的哈希表"<<endl;
- H.Traverse_HashTable();
- cout<<endl;
- cout<<"输入要查找的记录的关键字:";
- cin>>k;
- j=H.Search_Hash(k,p);
- if(j==1)
- H.Get_Data(p);
- else
- cout<<"该记录不存在"<<endl;
- cout<<"____销毁哈希表____"<<endl;
- H.Destroy_HashTable();
- return 0;
- }
测试结果:
- 按哈希地址顺序遍历哈希表
- 哈希地址0->10
- 元素的关键字值和它的标志分别是:5 9
- 元素的关键字值和它的标志分别是:1 5
- 元素的关键字值和它的标志分别是:2 6
- 元素的关键字值和它的标志分别是:3 7
- 元素的关键字值和它的标志分别是:4 8
- 元素的关键字值和它的标志分别是:60 2
- 元素的关键字值和它的标志分别是:17 1
- 元素的关键字值和它的标志分别是:29 3
- 元素的关键字值和它的标志分别是:38 4
- 元素的关键字值和它的标志分别是:6 10
- 元素的关键字值和它的标志分别是:7 11
- 输入要查找的记录的关键字:5
- 元素的关键字值和它的标志分别是:5 9
- ____重建hash表_____
- 插入失败
- 需要重建哈希表才可以插入
- ____重建哈希表____
- 遍历重建后的哈希表
- 哈希地址0->18
- 元素的关键字值和它的标志分别是:38 4
- 元素的关键字值和它的标志分别是:1 5
- 元素的关键字值和它的标志分别是:2 6
- 元素的关键字值和它的标志分别是:3 7
- 元素的关键字值和它的标志分别是:4 8
- 元素的关键字值和它的标志分别是:5 9
- 元素的关键字值和它的标志分别是:60 2
- 元素的关键字值和它的标志分别是:6 10
- 元素的关键字值和它的标志分别是:7 11
- 元素的关键字值和它的标志分别是:8 12
- 元素的关键字值和它的标志分别是:29 3
- 元素的关键字值和它的标志分别是:17 1
- 输入要查找的记录的关键字:7
- 元素的关键字值和它的标志分别是:7 11
- ____销毁哈希表____
- Press any key to continue
标签:
版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有
- C++ 转换函数搭配友元函数 2020-06-10
- C++ 自动转换和强制类型转换(用户自定义类类型) 2020-06-10
- C++ rand函数 2020-06-10
- C++ 友元函数 2020-06-10
- C++ 运算符重载 2020-06-10
IDC资讯: 主机资讯 注册资讯 托管资讯 vps资讯 网站建设
网站运营: 建站经验 策划盈利 搜索优化 网站推广 免费资源
网络编程: Asp.Net编程 Asp编程 Php编程 Xml编程 Access Mssql Mysql 其它
服务器技术: Web服务器 Ftp服务器 Mail服务器 Dns服务器 安全防护
软件技巧: 其它软件 Word Excel Powerpoint Ghost Vista QQ空间 QQ FlashGet 迅雷
网页制作: FrontPages Dreamweaver Javascript css photoshop fireworks Flash