第九章　符号表.pptVIP

第九章　符号表 9.1 实现符号表的简单方法 9.2 用散列表实现符号表 开散列 闭散列 散列函数及其效率 闭散列的重新散列技术 9.3 应用 实现符号表的简单方法 符号表的概念： 实现符号表的简单方法： 概念 实现符号表的简单方法 用数组实现符号表的结构定义如下 : 创建一个定长数组大小为size的空符号表 符号表成员查询 在符号表T中插入元素x 在符号表T中删除元素x 用散列表实现符号表 用数组实现含有n个元素的符号表，在最坏情况下运算TableMember、TableInsert 和 TableDelete 运算所需的计算时间为O(n)。 实现符号表的另一个重要技巧是－－散列技术 开散列 示例：给出一符号表 { Burke, Ekers, Broad, Blum, Attlee, Alton, Hecht, Ederly }。 散列函数为：取其第一个字母在字母表中的位置再除以2。 Hash (x) = ?( ord (x) - ord (‘A’) +1 )/2? //ord ( ) 是求字符内码的函数 用它计算可得： Hash (Burke) = 1 Hash (Ekers) = 2 Hash (Broad) = 1 Hash (Blum) = 1 Hash (Attlee) = 0 Hash (Hecht) = 4 Hash (Alton) = 0 Hash (Ederly) = 2 若散列表为 HT[0..13]，B = 14。 开散列表是将数组和链表结合在一起的一种数据结构，并希望能利用各自的优点，克服各自的缺点。 因此，如何选择“随机”的散列函数，使它能将集合中的元素均匀地散列到各个桶中是散列技术的一个关键。 用开散列表实现的符号表结构定义如下: typedef struct open *OpenHashTable； typedef struct open { int size； /* 桶数组的大小 */ int (*hf) (SetItem x)；/* 散列函数 */ List *ht； /* 桶数组 */ }Open; 创建一个空的开散列表 OpenHashTable HTInit ( int nbuckets， int (*hashf)(SetItem x) ) { int i； OpenHashTable H=(OpenHashTable ) malloc( sizeof(*H) ); H-size = nbuckets; //桶数组大小为nbuckets H-hf = hashf；//散列函数为hashf(x) H-ht = (List *) malloc ( H-size*sizeof (List) )； for ( i =0; iH-size; i++ ) H-ht[i] = ListInit()；//初始化每个桶 return H；} 成员查询 插入元素 删除元素 闭散列 将符号表的元素直接存放在桶数组单元中，而不用桶数组来存放链表。 因此闭散列表中的每个桶都只能存放集合中的一个元素 当要把元素x存放到桶h(x)中，但发现这个桶已被其他元素占用时，就发生了冲突。 为了解决闭散列中的冲突，需要使用重新散列技术，使得发生冲突时，按重新散列技术可以选取一个桶序列h1(x)，h2(x)… 只要桶数组尚未全部被占用，顺序试探这个桶序列中各个桶，一定能找到一个空桶来存放元素x。 如： 若设散列表中的编址(桶号)为 0 到 B-1, 当要加入一个元素a时, 通过散列函数 h(a) 的计算，得到它的存放的桶号 j。 但在存放时发现此桶已被另一个元素b 占据, 发生了冲突。 为此, 需把 a存放到表中“下一个”空位中。 如果表未被装满, 则在允许的范围内必定还有空位。 最简单的重新散列技术是－－线性重新散列技术 线性重新散列技术 当发生冲突时, 探查下一个地址。当循环 B-1 次后就会回到开始探查时的位置, 说明待查元素不在表内, 而且表已满, 不能再插入新的元素。 设散列表 HT[0..9], B = 10。采用线性探查法处理冲突, 则散列结果如图所示。 检测一个元素 x 是否在一个闭散列表中，只要顺序查看桶 h(x)，