资源描述：
《数据结构教程第三十三课哈希表(二).doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、► 数据结构教程 第三十三课 哈希表（二）数据结构教程 第三十三课 哈希表（二） 教学目的：掌握哈希表处理冲突的方法及哈希表的查找算法教学重点：哈希表处理冲突的方法教学难点：开放定址法授课内容：一、复习上次课内容什么是哈希表？如何构造哈希表？提出问题：如何处理冲突？二、处理冲突的方法 成绩一成绩二...3... ...... 24刘丽829525... 26陈伟 ...... 33吴军 ...... 42李秋梅 ...... 46刘宏英 ...... 72吴小艳 ...... 78... 如果
2、两个同学分别叫刘丽刘兰，当加入刘兰时，地址24发生了冲突，我们可以以某种规律使用其它的存储位置，如果选择的一个其它位置仍有冲突，则再选下一个，直到找到没有冲突的位置。选择其它位置的方法有：１、开放定址法Hi=(H(key)+di)MODmi=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取值可能为伪随机数列。称伪随
3、机探测再散列。例：在长度为11的哈希表中已填有关键字分别为17,60,29的记录，现有第四个记录，其关键字为38，由哈希函数得到地址为5，若用线性探测再散列，如下：012345678910 601729 (a)插入前012345678910 60172938 (b)线性探测再散列012345678910 601729 (c)二次探测再散列012345678910 38 601729 (d)伪随机探测再散列伪随机数列为9,5,3,8,1...２、再哈希法当发生冲突时，使用第二个、第三
4、个、哈希函数计算地址，直到无冲突时。缺点：计算时间增加。３、链地址法将所有关键字为同义词的记录存储在同一线性链表中。４、建立一个公共溢出区假设哈希函数的值域为[0,m-1],则设向量HashTable[0..m-1]为基本表，另外设立存储空间向量OverTable[0..v]用以存储发生冲突的记录。三、哈希表的查找//开放定址哈希表的存储结构inthashsize[]={997,...};typedefstruct{ElemType*elem;intcount;intsizeindex;}HashTable;#define
5、SUCCESS1#defineUNSUCCESS0#defineDUPLICATE-1StatusSearchHash(HashTableH,KeyTypeK,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)returnSUCCESS;elsereturnUNSUCCESS;}StatusInsertHash(HashTable&H,EleType
6、e){c=0;if(SearchHash(H,e.key,p,c))returnDUPLICATE;elseif(c
