本课主题: 哈希表(二)
教学目的: 把握哈希表处理冲突的方法及哈希表的查找算法
教学重点: 哈希表处理冲突的方法
教学难点: 开放定址法
授课内容:
一、复习上次课内容
什么是哈希表?如何构造哈希表?
提出问题:如何处理冲突?
二、处理冲突的方法
成绩一
成绩二...
3
...
...
...
24
刘丽
82
95
25
...
26
陈伟
...
...
33
吴军
...
...
42
李秋梅
...
...
46
刘宏英
...
...
72
吴小艳
...
...
78
...
假如两个同学分别叫 刘丽 刘兰,当加入刘兰时,地址24发生了冲突,我们可以以某种规律使用其它的存储位置,假如选择的一个其它位置仍有冲突,则再选下一个,直到找到没有冲突的位置。选择其它位置的方法有:
1、开放定址法
Hi=(H(key)+di) MOD m i=1,2,...,k(k<=m-1)
其中m为表长,di为增量序列
假如di值可能为1,2,3,...m-1,称线性探测再散列。
假如di取值可能为1,-1,2,-2,4,-4,9,-9,16,-16,...k*k,-k*k(k<=m/2)
称二次探测再散列。
假如di取值可能为伪随机数列。称伪随机探测再散列。
例:在长度为11的哈希表中已填有要害字分别为17,60,29的记录,现有第四个记录,其要害字为38,由哈希函数得到地址为5,若用线性探测再散列,如下:
0
1
2
3
4
5
6
7
8
9
10
60
17
29
(a)插入前
0
1
2
3
4
5
6
7
8
9
10
60
17
29
38
(b)线性探测再散列
0
1
2
3
4
5
6
7
8
9
10
60
17
29
(c)二次探测再散列
0
1
2
3
4
5
6
7
8
9
10
38
60
17
29
(d)伪随机探测再散列
伪随机数列为9,5,3,8,1...
2、再哈希法
当发生冲突时,使用第二个、第三个、哈希函数计算地址,直到无冲突时。缺点:计算时间增加。
3、链地址法
将所有要害字为同义词的记录存储在同一线性链表中。
4、建立一个公共溢出区
假设哈希函数的值域为[0,m-1],则设向量HashTable[0..m-1]为基本表,另外设立存储空间向量OverTable[0..v]用以存储发生冲突的记录。
三、哈希表的查找
//开放定址哈希表的存储结构
int hashsize[]={997,...};
typedef struct{
ElemType *elem;
int count;
int sizeindex;
}HashTable;
#define SUCCESS 1
#define UNSUCCESS 0
#define DUPLICATE -1
Status SearchHash(HashTable H,KeyType K,int &p,int &c){
p=Hash(K);
while(H.elem[p].key!=NULLKEY && !EQ(K,H.elem[p].key))
collision(p,++c);
if(EQ(K,H.elem[p].key)
return SUCCESS;
else return UNSUCCESS;
}
Status InsertHash(HashTable &H,EleType e){
c=0;
if(SearchHash(H,e.key,p,c))
return DUPLICATE;
else if(c<hashsize[H.sizeindex]/2){
H.elem[p]=e; ++H.count; return OK;
}
else RecreateHashTable(H);
}
四、总结
处理冲突的要求是什么?
视频教程列表文章教程搜索C语言程序设计推荐教程
- .学习C语言最快速入门教程.
- .北大青鸟C语言PPT学习大纲第十章
- .北大青鸟C语言PPT学习大纲第十章
- .北大青鸟C语言PPT学习大纲第九章
- .C语言视频教程(21视频教程网)
- .2002年4月计算机等级考试二级C语
- .2001年9月计算机等级考试二级C语
- .2001年9月计算机等级考试二级C语
- .2001年9月计算机等级考试二级C语
- .2001年9月计算机等级考试二级C语
- .2001年9月计算机等级考试二级C语
- .国家计算机二级考试程序修改与设
- .国家计算机二级考试程序修改与设
- .国家计算机二级考试程序修改与设
- .国家计算机二级考试程序修改与设
- .全国计算机等级考试二、三、四级考
- .1998年9月全国计算机等级考试二
- .1998年4月全国计算机等级考试二
- .1997年9月全国计算机等级考试二
- .1997年4月全国计算机等级考试二
- .1996年9月全国计算机等级考试二
- .1996年4月全国计算机等级考试二
- .2001年9月基础知识知识和C语言程
- .2001年9月全国计算机等级考试二
- .2001年4月基础知识知识和C语言程
- .2001年4月全国计算机等级考试二
- .2000年9月基础知识知识和C语言程
- .2000年9月全国计算机等级考试二
- .2000年4月基础知识知识和C语言程
- .2000年4月全国计算机等级考试二
C语言程序设计热门教程
- .C语言编写的Mysql编程接口(4)
- .C语言编写的Mysql编程接口(3)
- .C语言编写的Mysql编程接口(2)
- .C语言编写的Mysql编程接口(1)
- .C语言教程:2013年计算机二级VB常
- .C语言教程:2013年计算机二级VB常
- .C语言教程:2013年计算机二级VB常
- .C语言教程:2013年计算机二级VB常
- .C语言教程:2013年计算机二级VB常
- .C语言教程:变态的C语言Hello Wo
- .C语言教程:变态的C语言Hello Wo
- .C语言教程:变态的C语言Hello Wo
- .C语言教程:变态的C语言Hello Wo
- .C语言教程:变态的C语言Hello Wo
- .C语言教程:变态的C语言Hello Wo
- .C语言教程:C语言模拟试题五
- .C语言教程:C语言模拟试题四
- .C语言教程:C语言模拟试题三
- .C语言教程:C语言模拟试题二
- .C语言教程:C语言模拟试题一
- .C语言考试:2012年全国计算机等级
- .C语言考试:2012年全国计算机等级
- .C语言考试:2012年全国计算机等级
- .C语言考试:2012年全国计算机等级
- .C语言考试:2012年全国计算机等级
- .C语言教程:指针变量的运算分析
- .C语言教程:main函数的参数分析
- .C语言教程:指针型函数分析
- .C语言教程:函数指针变量分析
- .C语言教程:多维数组的指针变量分
Word教程网 Excel教程网 Dreamweaver教程网 Fireworks教程网 PPT教程网 FLASH教程网 PS教程网 HTML教程网 DIV CSS教程网 FLASH AS教程网 ACCESS教程网 SQL SERVER教程网 C语言教程网 JAVASCRIPT教程网 ASP教程网 ASP.NET教程网 CorelDraw教程网
关于我们 | 教程购买 | 广告刊登 | 网站地图 |湖北继续教育网 |QQ:2693987339(点击联系)购买教程光盘
地址:湖北省武汉市曹家湾32号501室 电话:027-86646545 15972130058--教程购买问题汇总
21视频教程网专业的网站开发视频教程学习网站
ICP备案号:鄂ICP备14009716号-13 公安备案号:42011102002974