数据结构：思想与方法-翁惠玉-27783第九章幻灯片.ppt

* 闭散列表类的实现 闭散列表是用一个数组实现，数组的大小是由用户定义散列表时指定 由于闭散列表中的删除是用迟删除的方法实现的，为此每个数组元素除了要保存对应的数据元素之外还必须保存一个数组元素的状态。 必须定义数组元素的类型。 由于迟删除会引起性能下降，希望有一个真正实现删除的函数 * 闭散列表类的定义 template class Type class closeHashTable:public hashTableType { private: struct node { Type data; int state; //0 -- empty 1 -- active 2 -- deleted node() {state = 0;} }; node *array; int size; * public: closeHashTable(int length = 101, int (*f)(const Type x) = defaultKey); ~closeHashTable() {delete [] array;} bool find(const Type x) const; bool insert(const Type x); bool remove(const Type x) ; void rehash(); }; * 构造函数 template class Type closeHashTableType::closeHashTable (int length, int (*f)(const Type x) ) { size = length; array = new node[size]; key = f; } * insert函数的实现 template class Type bool closeHashTableType::insert(const Type x) {int initPos, pos ; initPos = pos = key(x) % size; do { if (array[pos].state != 1) { array[pos].data = x; array[pos].state = 1; return true; } if (array[pos].state == 1 key(array[pos].data) == key(x)) return true; pos = (pos+1) % size; } while (pos != initPos); return false; } * remove函数的实现 template class Type bool closeHashTableType::remove(const Type x) {int initPos, pos ; initPos = pos = key(x) % size; do { if (array[pos].state == 0) return false; if (array[pos].state == 1 key(array[pos].data) == key(x)) { array[pos].state = 2; return true;} pos = (pos+1) % size; } while (pos != initPos); return false; } * find函数的实现 template class Type bool closeHashTableType::find(const Type x) const { int initPos, pos ; initPos = pos = key(x) % size; do { if (array[pos].state == 0) return false; if (array[pos].state == 1 key(array[pos].data) == key(x)) return true; pos = (pos+1) % size; } while (pos != initPos); return