《算法与数据结《算法与数据结构》构》AlgorithmsandDataStructuresAlgorithmsandDataStructures第9章符号表9.1实现符号表的简单方法9.2用散列表实现符号表9.3符号表的应用吴英杰《算法与数据结《算法与数据结构》构》AlgorithmsandDataStructuresAlgorithmsandDataStructures第9章符号表学习要点：理解抽象数据类型符号表的概念。掌握数组实现符号表的方法。理解开散列和闭散列的概念。掌握用开散列表实现符号表的方法。掌握除余法、数乘法、平方取中法、基数转换法和随机数法等散列函数构造方法。掌握采用线性重新散列技术的闭散列表实现符号表的方法。返回章目录《算法与数据结《算法与数据结构》构》AlgorithmsandDataStructuresAlgorithmsandDataStructures9.1实现符号表的简单方法9.1.1引言ADT符号表的概念以集合为基础，并支持Member、Insert和Delete三种运算的抽象数据类型叫做符号表。ADT符号表的应用公司的客户符号表一个地区的固定/移动电话号码符号表软件开发中的数据符号表网上的在线符号表互联网/企业网/局域网网管中的IP地址符号表等等《算法与数据结《算法与数据结构》构》AlgorithmsandDataStructuresAlgorithmsandDataStructures可以用表示集合的链表或位向量来实现符号表。实现符号表的另一简单方法是用一个定长数组来存储集合中的元素。这种方法的优点是结构简单，易于操作。它的缺点是所支持的符号表运算的时间复杂度较高。表示集合大小受数组大小的限制。《算法与数据结《算法与数据结构》构》AlgorithmsandDataStructuresAlgorithmsandDataStructures9.1实现符号表的简单方法9.1.2用固定数组实现符号表数组实现符号表的结构定义如下：typedefstructatab*Table;Typedefstructatab{intarraysize;intlast;SetItem*data;}Atab;《算法与数据结《算法与数据结构》构》AlgorithmsandDataStructuresAlgorithmsandDataStructures9.1实现符号表的简单方法9.1.2用固定数组实现符号表优点：结构简单，实现操作的逻辑简单。缺点：所表示的集合的大小受到数组大小的限制。三个基本操作在最坏情况下都需要O(n)。通常集合元素并不占满整个数组，空间没有得到充分利用。返回章目录《算法与数据结《算法与数据结构》构》AlgorithmsandDataStructuresAlgorithmsandDataStructures9.2用散列表实现符号表实现符号表的另一个重要技巧是散列（hashing）技术。用散列来实现符号表可以使符号表的每个运算所需的平均时间是一个常值。在最坏情况下每个运算所需的时间正比于集合的大小。散列有两种形式，一种是开散列（外部散列），它将符号表元素存放在一个潜无穷的空间里，能处理任意大小的集合。另一种是闭散列（内部散列），它使用一个固定大小的存储空间，所能处理的集合大小不能超过其存储空间大小。《算法与数据结《算法与数据结构》构》AlgorithmsandDataStructuresAlgorithmsandDataStructures9.2.1开散列开散列的基本思想是将集合的元素（可能有无穷多个）划分成有限个类。例如，划分为0，1，…，B－1这B个类。用散列函数h将集合中的每个元素x映射到0，1，…，B－１之一，h(x)的值就是x所属的类。函数h(x)的值称为元素x的散列值。每一个类称为一个桶，并且称x属于桶h(x)。期望散列能均匀，使得当桶数组的规模与符号表的规模同阶时，桶数组的每一个桶中大致有常数个元素，从而对符号表的三个基本操作都只需要常数时间。这里的问题是如何散列即如何构造散列(映射)函数去达到设想的期望？《算法与数据结《算法与数据结构》构》AlgorithmsandDataStructuresAlgorithmsandDataStructures例一组关键字为（21，14，19，58，65，32，72）H(K)=K%11216532∧19∧72∧1458∧∧∧∧∧∧∧∧012345678910《算法与数据结《算法与数据结构》构》AlgorithmsandDataStructuresAlgorithmsandDataStructures•inthash1(char*x)•{•intlen,i,j=0;•len=strlen(x);•for(inti=0;i
