9.3.4闭散列表的算法实现 实现方式 字典( dictionary) 实现方式 种特殊的集合,其元素是(关键码,属 有序线性表 关键码必须是互不相同的(在同一个字典之 字符树 ■主要操作是依据关键码来存储和析取值 散列方法 lookup(key) 物啦 散列字典ADT(属性 散列字典ADT(方法) template <class Key class Elem, class Comp, class EEComp> class hashdict ashdict(int sz, Elem e){//构造函数 currcnt=O; HT=new Elem[sz Eem*HT;//散列 for(int i=O; i<M; i++)HT[]=EMPTY int M /散列表大小 nt;∥/现有元素数目 Elem EMPty//空福 whashdict(i delete []HT; 1 bool hash search(const Key&, Elem&)const; ti)∥/探查函数 bool hashinsert const elem& inth(intx) const;//散列函 Elem hash Delete(const Key& K); inth(char*x) const;//字符串散列函数 int size( return currcnt}//元素数目 权新有:轨命究 T恤息@ 积新有,究 插入算法 插入算法(程序) 散列函数h,假设给定的值为K /将舞元膏e入到列衰H 范淼:支她葉减皮该显未教占用,则 emplate <class Key r class Elem, class KEComp, class 拥率地比随集与相等,则报告“散 t home=h( getkey(e);/home存储基位 探查序列的初始位量 厚别的擎设宋地处理油先点 找探查 if (EEComp: eq(e, HTlposD)return false; 直到某个地址空间未被占用(可以插入) pos =(home+p(getkeye), i)% M;//E 或者关键码比较相等(不需要插入)为止 /攔入元膏e18 北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 103 9.3.4 闭散列表的算法实现 字典(dictionary) „ 一种特殊的集合，其元素是(关键码，属 性值)二元组。 „ 关键码必须是互不相同的(在同一个字典之 内) „ 主要操作是依据关键码来存储和析取值 „ insert(key, value) „ lookup(key) 北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 104 实现方式 „ 实现方式 „ 有序线性表 „ 字符树 „ 散列方法 北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 105 散列字典ADT（属性） template <class Key，class Elem，class KEComp，class EEComp> class hashdict { private: Elem* HT;// 散列表 int M; // 散列表大小 int currcnt; // 现有元素数目 Elem EMPTY; // 空槽 int p(Key K，int i) // 探查函数 int h(int x) const ; // 散列函数 int h(char* x)const ; // 字符串散列函数 北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 106 散列字典ADT（方法） public: hashdict(int sz，Elem e) { // 构造函数 M=sz; EMPTY=e; currcnt=0; HT=new Elem[sz]; for (int i=0; i<M; i++) HT[i]=EMPTY; } ～hashdict() { delete [] HT; } bool hashSearch(const Key&，Elem&) const; bool hashInsert(const Elem&); Elem hashDelete(const Key& K); int size() { return currcnt; } // 元素数目 }; 北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 107 插入算法 散列函数h，假设给定的值为K „ 若表中该地址对应的空间未被占用，则 把待插入记录填入该地址 „ 如果该地址中的值与K相等，则报告“散 列表中已有此记录” „ 否则，按设定的处理冲突方法查找探查 序列的下一个地址，如此反复下去 „ 直到某个地址空间未被占用（可以插入） „ 或者关键码比较相等（不需要插入）为止 北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 108 插入算法（程序） // 将数据元素e插入到散列表 HT template <class Key, class Elem, class KEComp, class EEComp> bool hashdict<Key, Elem, KEComp, EEComp>::hashInsert(const Elem& e) { int home= h(getkey(e)); //home存储基位置 int i=0; int pos = home; // 探查序列的初始位置 while (!EEComp::eq(EMPTY, HT[pos])) { if (EEComp::eq(e, HT[pos])) return false; i++; pos = (home+p(getkey(e), i)) % M; //探查 } HT[pos] = e; // 插入元素e return true; }