《数据结构与算法》PPT课堂课件-第9章-符号表.ppt

《《数据结构与算法》PPT课堂课件-第9章-符号表.ppt》由会员分享，可在线阅读，更多相关《《数据结构与算法》PPT课堂课件-第9章-符号表.ppt（6页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、2023/3/2319.2 用用散列表实现符号表散列表实现符号表9.2.1 开散列（外部散列）开散列（外部散列）n基本思想：基本思想：把集合中的所有元素划分成有限个类。例如：划分为0，1，B-1这B个类。用散列函数h将集合中的每个元素映射到0，1，B-1之一，h(x)的值就是x所属的类。函数h(x)的值称为元素x的散列值。上面所说的每一个类称为一个桶，并且称x属于桶h(x)。n散列散列(hashing)：即映射到一个桶数组(散列表)的桶中。当有多个不同元素被散列到同一个桶时，这些元素链在一个表里。第九章第九章 符号表符号表2023/3/232n散列的目的：散列的目的：期望散列能均匀，使得当桶数

2、组的规模与集合的规模同阶时，桶数组的每一个桶中大致有常数个，从而对符号表的三个基本操作都只需要常数时间。第九章第九章 符号表符号表2023/3/2339.2.1.1开散列的数据要素开散列的数据要素 按照设想，开散列首先需要拥有一个桶数组，桶数组的规模与字典的规模同阶，桶数组中的每一个桶有一个指针各指向一个链表。其次需要拥有一个散列(映射)函数，它把字典中的元素分别散列(映射，分散)到各桶所对应的链表中。第九章第九章 符号表符号表2023/3/2349.2.1.2 散列函数的例子散列函数的例子 假设字典的元素是字符串x，桶数组的规模为 101，那么，下面是散列函数的一个具体例子int hash1

3、(char*x)int len=strlen(x),hashval=0;for(int i=0;i len;i+)hashval+=xi;return hashval%101;第九章第九章 符号表符号表2023/3/235n例，课后P172 9.19.1 设散列函数为h(i)=i%7，问：(1)将完全立方数1，8，27，64，125，216，343插入到一个初始为空的开散列表中，结果如何？第九章第九章 符号表符号表2023/3/2369.2符号表符号表9.2.2 实现实现符号表符号表的简单方法的简单方法闭散列闭散列9.2.2.1 与开散列的相同点和区别与开散列的相同点和区别相同点：把字典中的所

4、有元素散列相同点：把字典中的所有元素散列(hashing)即即 映射到一个桶数组映射到一个桶数组(散列表散列表)的桶中。的桶中。区别：桶数组区别：桶数组(散列表散列表)的桶直接用来存放字典的桶直接用来存放字典 元素，而且一个桶只存放一个元素。出现多个元素，而且一个桶只存放一个元素。出现多个 元素散列到同一个桶时元素散列到同一个桶时(这叫冲突这叫冲突)，需要按照，需要按照 确定的规则在桶数组中进行探测，找还没有存确定的规则在桶数组中进行探测，找还没有存 放元素的桶放元素的桶(这叫空桶这叫空桶)，然后将发生冲突的后，然后将发生冲突的后 到元素放入空桶，解决冲突，实现散列。到元素放入空桶，解决冲突，实现散列。