【12】Chapter7 散列及应用

1、12345678v允许多个元素有相同关键值的字典允许多个元素有相同关键值的字典v Word dictionary. Pairs are of the form (word, meaning). May have two or more entries for the same word. (bolt, a threaded pin) (bolt, a crash of thunder) (bolt, to shoot forth suddenly) (bolt, a gulp) (bolt, a standard roll of cloth) etc.910132354111233451213

2、14如何调用？如何调用？SortedChain Z;E和和K一定要类型相同吗？一定要类型相同吗？15161718如何修改为如何修改为InsertInsert算法？算法？1920v在一个使用有序链表描述的具有在一个使用有序链表描述的具有n 个元素的字典中进个元素的字典中进行搜索，至多需进行行搜索，至多需进行 n 次比较次比较v跳表基本思想跳表基本思想：如果在链中部节点加一个指针，则比：如果在链中部节点加一个指针，则比较次数可以减少到较次数可以减少到 n/ 2 + 1 。搜索时，首先将欲。搜索时，首先将欲搜索元素与中间元素进行比较。如果欲搜索的元素较搜索元素与中间元素进行比较。如果欲搜索的元素较小

3、，则仅需搜索链表的左半部分，否则，只要在链表小，则仅需搜索链表的左半部分，否则，只要在链表右半部分进行比较即可。右半部分进行比较即可。类似折半查找类似折半查找！2122v跳表是一组有层次的链：跳表是一组有层次的链：0级链是包含所有元素的级链是包含所有元素的有序链表，有序链表，1级链是级链是0级链的一个子集。级链的一个子集。vi 级链所包含的元素是级链所包含的元素是i-1级链的子集，即：级链的子集，即：i 级链级链上所有的元素均在上所有的元素均在i- 1级链上级链上v搜索时，从第最高链到第搜索时，从第最高链到第0链分级查找。链分级查找。2324252627282930v定义：如果元素定义：如果元

4、素e的关键字为的关键字为k ，散列函数为，散列函数为f ，那，那么么e 在散列表中的位置为在散列表中的位置为f (k)v搜索关键字为搜索关键字为k的元素，首先要计算出的元素，首先要计算出f (k)，然后，然后看表中看表中f (k)处是否有元素。如果有就找到了该元处是否有元素。如果有就找到了该元素；如果没有，说明该字典中不包含该元素素；如果没有，说明该字典中不包含该元素v插入：把元素插入：把元素k放在放在f (k)位置以实现位置以实现v删除：把删除：把f (k)位置置为空位置置为空31v学生记录字典：学生记录字典：Key采用学生采用学生ID号号(6位整数位整数)v假设一个班最多有假设一个班最多有

5、 1 0 0个学生，他们的个学生，他们的ID号在号在951000952000之间之间v定义散列函数：定义散列函数：f(k)=k-951000，映射到，映射到0, 1000v这种理想情况下，初始化这种理想情况下，初始化(b)(b)，各种操作，各种操作(1)(1)v但但是是还有许多应用还有许多应用，因为因为关键字变化范围太大关键字变化范围太大而而不能创建一个这样的散列表不能创建一个这样的散列表v例如：例如：12个字母组合个字母组合1, 2712-132v散列查找（搜索）散列查找（搜索）v冲突或碰撞（冲突或碰撞（Collision）v建立散列表建立散列表v散列函数的构造方法散列函数的构造方法v散列冲

6、突的解决方法散列冲突的解决方法333435363738 散列函数的定义域散列函数的定义域必须包括需要存储的全部关键字必须包括需要存储的全部关键字，如果，如果散列表允许有散列表允许有 m 个地址时个地址时, 其值域必须在其值域必须在 0 到到 m-1 之间。之间。 散列函数计算出来的地址应能散列函数计算出来的地址应能均匀分布均匀分布在整个地址空间中：在整个地址空间中：若若 key 是从关键字集合中随机抽取的一个关键字，散列函数是从关键字集合中随机抽取的一个关键字，散列函数应能以应能以同等概率同等概率取取0 到到 m-1 中的每一个值。中的每一个值。 散列函数应是散列函数应是简单简单的，能在较短的

7、时间内计算结果。的，能在较短的时间内计算结果。3940414221)/(rikikrn43u 例如，设有如下例如，设有如下8个关键字，它们均为个关键字，它们均为9位十进制数，假设采用位十进制数，假设采用的散列表的范围位的散列表的范围位0-1000，用数字分析法确定它们的散列地址。，用数字分析法确定它们的散列地址。44【潜在的缺点潜在的缺点】连续的关键字映射成连续的散列值，在某些连续的关键字映射成连续的散列值，在某些实现方法中可能导致检索性能降低。实现方法中可能导致检索性能降低。454647484950static unsigned long hashpjw(char *arKey, unsig

8、ned int nKeyLength) unsigned long h = 0, g; char *arEnd=arKey+nKeyLength; while (arKey arEnd) h = (h 24); h = h g; return h; 5152535455565758596061626364656667v当当D D为素数或为素数或D D没有小于没有小于2020的素数因子时，可以使的素数因子时，可以使性能达到最佳性能达到最佳(D(D等于桶的个数等于桶的个数b)b)v另一种计算另一种计算D D的方法是首先根据散列表的最大空间的方法是首先根据散列表的最大空间来确定来确定b b的最大可能

9、值，然后取的最大可能值，然后取D D为不大于这个最为不大于这个最大值的整数，该整数要么是素数，要么没有小于大值的整数，该整数要么是素数，要么没有小于 2 02 0的素数因子。的素数因子。v例如，如果在表中最多可以分配例如，如果在表中最多可以分配530530个桶，则个桶，则D D 和和b b 的最佳选择为的最佳选择为23 (23 (因因23 23 * * 23 = 529 ) 23 = 529 )68697001234561423462318257172INT_MAX=2147483647p & p-datadatak7374u 设散列表的表长设散列表的表长m14，散列函数，散列函数H（k）k mod 11，表中，表中已有四个数据元素，如果用已有四个数据元素，如果用二次探测再散列法二次探测再散列法处理冲突，试求关处理冲突，试求关键字为键字为49的数据元素的存储地址。的数据元素的存储地址。01234567891011121315386184解：解： Key=49 H(49)=49 mod 1