正在加载图片...
例:删除带来的问题 墓碑 [o2|34s67s。112 荛态个特殊的标记位,记录散列表中的单 单元被占用 霜,4度2,孔,定关网 二次探查序列 经的二次意序列是2、31.61116,5 操露豢把饼否别导删究浇被西什森态特 3的角512210 不可以 型除{2设男婆列的最后位置2的元素错换 ■被删除标记值称为基碑 tombstone) 志一个记录曾经占用这个植 检棠的同义词,查不到 但是现在已经不再占用了 可事实上它们还存放在位量3和1上 物啦 墓碑对操作的影响 带墓碑的插入操作 加入了删除操作后,闭散列的插入操作 在插入时,如果遇到标志为墓碑 需要进行修改 的槽,可以把新记录存储在该槽 ■检索操作可以不修改 中吗? ■检索时,如果遇到基碑,检索过程会顺着探 查序列继续进行 避免插入两个相同的关键码 可以把墓碑看成是不等于任何关健码的特殊 值,对于算法没有影响 下去,直到找到一个真正的空位 置 权新有:轨命究 T恤息@ 积新有,究 带墓碑的删除算法 带墓碑的插入算法 e <class Key, class Elem, class KEComp cass lict<Key, Elem, KEComp, EEComp>: hashDelete(const t int i=0,pos=home=ho;/初始位置 boEEcomp ct hasaYn sermons Eme MPTY, HTLposd)< nti=o HTLpos]=ToMB;/设碑 if(KEComp: : eq(g urn temp;/返回目标 return false;J/不允许复关健罚 pos=(home p(getkey(e),D))%o M: pos=(home+ p(K i))% M; /插入e return EMPTY:20 北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 115 例：删除带来的问题 例如，一个长度M = 13的散列表，假定关键码k1 和k2，h(k1) = 2，h(k2) = 6。 二次探查序列 k1的二次探查序列是2、3、1、6、11、11、6、5、 12、... k2的二次探查序列是6、7、5、10、2、2、10、9、 3、... k2的同义词占用 删除位置6，用该序列的最后位置2的元素替换 之，位置2设为空 检索k1的同义词，查不到 可事实上它们还存放在位置3和1上! 0 1 2 3 4 5 6 7 8 9 10 11 1 2 K 1K 2K 1 K 2K 2K 2 K 2 北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 116 墓碑 设置一个特殊的标记位，来记录散列表中的单 元状态 单元被占用 空单元 已删除 是否可以把空单元、已删除这两种状态，用特 殊的值标记，以区别于“单元被占用”状态？ 不可以！ 被删除标记值称为墓碑( tombstone ) 标志一个记录曾经占用这个槽 但是现在已经不再占用了 北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 117 墓碑对操作的影响 加入了删除操作后，闭散列的插入操作 需要进行修改 检索操作可以不修改 检索时，如果遇到墓碑，检索过程会顺着探 查序列继续进行 可以把墓碑看成是不等于任何关键码的特殊 值，对于算法没有影响 北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 118 带墓碑的插入操作 在插入时，如果遇到标志为墓碑 的槽，可以把新记录存储在该槽 中吗? 避免插入两个相同的关键码 检索过程仍然需要沿着探查序列 下去，直到找到一个真正的空位 置 北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 119 带墓碑的删除算法 template <class Key, class Elem, class KEComp, class EEComp>Elem hashdict<Key,Elem,KEComp,EEComp>::hashDelete(const Key& K) { int i=0, pos = home= h(K); //初始位置 while (!EEComp::eq(EMPTY, HT[pos])) { if (KEComp::eq(K, HT[pos])){ temp = HT[pos]; HT[pos] = TOMB; //设置墓碑 return temp; //返回目标 } i++; pos = (home + p(K, i)) % M; } return EMPTY; } 北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 120 带墓碑的插入算法 template <class Key, class Elem, class KEComp, class EEComp> bool hashdict <Key, Elem, KEComp, EEComp>::hashInsert(const Elem &e) { int i=0, pos=home= h(getkey(e)); //初始 while (!EEComp::eq(EMPTY, HT[pos]) && !EEComp::eq(TOMB, HT[pos])) { if (KEComp::eq(getkey(e), HT[pos])) return false; //不允许重复关键码 i++; pos = (home + p(getkey(e), i)) % M; } HT[pos]=e; //插入e return true; }