Rookie's blog

Chapter9 动态查找表

Chapter9 动态查找表

  • 既要支持快速查找，又要支持插入删除
  • 动态查找表的抽象类
1
2
3
4
5
6
7
8
template <class KEY, class OTHER>
class dynamicSearchTable {
public:
    virtual SET<KEY, OTHER> *find(const KEY &x) const = 0;
    virtual void insert(const SET<KEY, OTHER> &x) = 0;
    virtual void remove(const KEY &x) = 0;
    virtual ~dynamicSearchTable() {};
};

实现方法

  • 通常用树和哈希表实现
  • 常用三种方法：
    • 二叉查找树
    • AVL树
    • 散列表

二叉查找树

  • 二叉查找树是二叉树在查找方面的重要应用。
  • 二叉查找树或者为空，或者具有如下性质：
    对任意一个结点p：
    • 如果p的左子树非空，则左子树上的所有结点的关键字值均小于p结点的关键字值。
    • 如果p的右子树非空，则右子树上的所有结点的关键字值均大于p结点的关键字值。
    • 结点p的左右子树同样是二叉查找树。

注意：
在二叉查找树中，最大和最小的元素不一定是叶节点，但最多只能有一个分支。

二叉查找树存储设计

  • 采用标准的二叉链表存储一棵二叉查找树，需要一个指向根结点的数据成员

二叉查找树类

  • 公有的成员函数：find、insert和remove 以及构造、析构函数
  • 二叉查找树的插入、删除和查找都是通过递归实现的，而这三个公有函数的参数表中并不需要包含递归参数。
    • 为此，对于每个公有的成员函数都定义了一个对应的带有递归参数的私有的成员函数（包裹函数）

类的定义

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
template <class KEY, class OTHER>
class BinarySearchTree: public dynamicSearchTable<KEY, OTHER>
{ 
private:
    struct BinaryNode
    {
        SET<KEY, OTHER> data;
        BinaryNode *left;
        BinaryNode *right; 
        BinaryNode( const SET<KEY, OTHER> & thedata,
                    BinaryNode *lt=NULL,  BinaryNode *rt=NULL )
        : data( thedata ), left( lt ), right( rt ) { }
    };
   BinaryNode *root;
public:
    BinarySearchTree() ;
    ~BinarySearchTree();
    SET<KEY, OTHER> *find(const KEY &x) const ;
    void insert( const SET<KEY, OTHER> & x );
    void remove( const KEY & x );
 
private:  
    void insert( const SET<KEY, OTHER> & x, BinaryNode * & t );
    void remove( const KEY & x, BinaryNode * & t );
    SET<KEY, OTHER> *find(const KEY &x, BinaryNode *t ) const;
    void makeEmpty( BinaryNode *t );//析构用，同二叉树的clear
};

二叉查找树的操作

  • 包括
    • 查找
    • 插入
    • 删除
  • 由于树是递归定义的，因此这些操作往往也用递归实现。因为二叉树的平均高度为logN，这些操作的时间复杂度也是O(logN)

查找:find()

  • 若根结点的关键字值等于查找的关键字，成功。
  • 否则，若关键字值小于根结点，查其左子树；若关键字值大于根结点，查其右子树。在左右子树上的操作类似。
  • 递归描述：
    • 如果树为空，返回空//没找到
    • 如果根结点等于被查结点，返回根结点地址//找到
    • 如果被查结点小于根结点，递归查找左子树，否则递归查找右子树

代码实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
template <class KEY, class OTHER>
SET<KEY, OTHER> * BinarySearchTree<KEY, OTHER>::find(
                                        const KEY &x ) const
{      return find( x, root );     }
 
template <class KEY, class OTHER>
SET<KEY, OTHER> *BinarySearchTree<KEY, OTHER>::find( 
                                         const KEY & x, BinaryNode *t ) const
{   
    if  ( t == NULL || t->data.key == x )
        return (SET<KEY, OTHER> *) t;//强制类型转换
    if( x < t->data.key )   return find( x, t->left );  
    else return find( x, t->right );  
}

插入：insert()

  • 若二叉树为空，则新插入的结点成为根结点。
  • 如二叉树非空
    • 首先执行查找算法，找出被插结点的父亲结点。
    • 判断被插结点是其父亲结点的左、右儿子。将被插结点作为叶结点插入。

注意：

  • 新插入的结点总是叶结点
  • 什么样的输入会使二叉查找树退化成表？从小到大插入数据或者一直从大到小插入数据

插入操作的递归实现：

  • 如果当前树为空，插入值作为树的根结点，返回
  • 如果插入值小于根结点，插入到左子树，否则插入到右子树。

代码实现：（递归实现）
使用两个指针（父节点和要插入的节点本身），可以有非递归实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
template <class KEY, class OTHER>
void BinarySearchTree<KEY, OTHER>::insert( const SET<KEY,
                                                 OTHER> & x )
{    insert( x, root );    } 
template <class KEY, class OTHER>
void BinarySearchTree<KEY, OTHER>::insert( const SET<KEY, 
                                                          OTHER> & x, BinaryNode *&t )
{	  
    if( t == NULL )
        t = new BinaryNode( x, NULL, NULL );
    else if( x.key < t->data.key )
        insert( x, t->left );
    else if( x.key > t->data.key )
        insert( x, t->right );
    else cout<<x.key<<“is exist”<<endl;
}

删除操作

分三种情况

删除叶节点

直接删除，更改它的父亲结点的相应指针字段为空。这不会改变二叉查找树的特性。

image-20240611132057328
删除有一个儿子的结点

若被删结点只有一个唯一的儿子，将此儿子取代被删结点的位置，就能保持二叉查找树的有序性

删除有两个儿子的结点
  • 删除这个结点会使其他结点从树上脱离。
  • 选取“替身”取代被删结点。
  • 替身的要求：维持二叉查找树的特性不变，故有以下两种方法：
    • 用左子树中的最右结点做替身
    • 用右子树中的最左结点做替身
image-20240611132419251 image-20240611132500998

AVL树

二叉平衡树介绍

  1. 二叉平衡树就是满足某种平衡条件的二叉查找树，需满足排序条件
  2. 平衡条件
    1. 容易维护
    2. 满足树的高度是O(logN)O(logN)

为了查找树的性能尽可能好，要使树尽可能丰满

平衡树(AVL树)的定义

  1. 定义：对于任一结点两棵子树的高度至多相差1。
  2. 平衡因子（平衡度）：结点的左子树的高度－右子树的高度。平衡树上每个结点的平衡因子都为 ＋1、-1、0 。
  3. 平衡树的优点：查找、插入、删除的复杂性均为O(logN)。

注意：

  1. 平衡树不一定是丰满树

二叉平衡树的查找性能

易知查找性能与二叉树的高度成正比

定义：具有N个结点的平衡树，高度h满足

log2(N+1)≤h≤1.44log2(N+1)−0.328log_2(N+1) \leq h \leq 1.44 log_2(N+1) - 0.328

易知，最好情况：平衡二叉树

N≤2h−1h≥⌈log2(N+1)⌉N \leq 2^h - 1 \\ h \geq \lceil log_2(N+1) \rceil

最坏情况为：斐波那契树，即每一子树的左右子树高度都相差1

斐波那契树

定义：

  1. 空树是高度为0的斐波那契树。
  2. 单个结点是高度为1的斐波那契树。
  3. 若Th−1T_{h-1}和与Th−2T_{h-2}分别是高度为h-1和h-2的斐波那契树，则Th={Th-1,x,Th-2}是高度为h的斐波那契树。
  4. 没有其他的树是斐波那契树。

对于高度为h的斐波那契树，其结点数n与高度有如下关系：

n0=0n1=1nh=nh−1+nh−2+1n_0 = 0 n_1 =1 n_h = n_{h-1} + n{h-2} + 1

差分后是斐波那契数列的递推式，故易知nhn_h其实是斐波那契数列的各项和

易知结论

nh=Fh+2−1n_{h} = F_{h+2} - 1

  ⟹  nh=\implies n_h =

AVL树的存储实现

  1. 采用二叉链表
  2. 每个结点必须保存平衡信息
  3. 平衡信息采用每棵树的高度，结点的平衡度是左右子树高度差

AVL树类的实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
template <class KEY, class OTHER>
class AvlTree: public dynamicSearchTable<KEY, OTHER> {
    struct AvlNode
    {    
        SET<KEY, OTHER>   data;
        AvlNode           *left;
        AvlNode           *right;
        int               height; //结点的高度
  
        AvlNode( const SET<KEY, OTHER> &element , 
                                    AvlNode *lt, AvlNode *rt, int h=1)
        : data(element), left( lt ), right( rt ), height(h) { }
     };
 
    AvlNode *root;
public:
    AvlTree() { root = NULL; }
    ~AvlTree( ) { makeEmpty( root); }
    SET<KEY, OTHER> *find( const KEY & x ) const;
    void insert( const SET<KEY, OTHER> & x ) ;
    void remove( const KEY & x );
private:
    void insert( const SET<KEY, OTHER> & x, AvlNode * & t ) ;
    bool remove( const KEY & x, AvlNode * & t ) ;
    void makeEmpty( AvlNode *t );
    int height( AvlNode *t ) const { return t == NULL ? 0 : t->height;}
    void LL( AvlNode * & t );//用于插入
    void LR( AvlNode * & t ); //用于插入
    void RL( AvlNode * & t ); //用于插入
    void RR( AvlNode * & t ); //用于插入
    int max(int a, int b) {return (a>b)?a:b;}//用于树的高度计算
    bool adjust(AvlNode *&t, int subTree); //用于删除
};

AVL树的插入

  • 插入过程与二叉查找树的插入相同，只是插入后可能出现两种情况：
    • 插入后，不破坏平衡性，只是改变了树根到插入点的路径上的某些结点的平衡度，因此需要自底向上修改结点的平衡度
    • 破坏了路径上的某些结点的平衡性，需要向上调整树的结构
    • 在调整平衡的过程中，只要有一个结点的平衡度不变，它上面的结点的平衡度也不变，调整可以结束。
  • 时间复杂度O(log N)

重新平衡的基本思路

  • 从插入位置向根回溯
  • 如果结点原来的平衡度为0，则插入后该结点不可能失衡，重新计算平衡度，继续往上回溯（可能会影响上层结点）
  • 如果结点原来的平衡度非0，可能成为失衡结点
    • 重新计算平衡度
    • 如果平衡度在合法范围，调整结束（因为这种情况下该节点的子树树高肯定没变）
    • 如果失去平衡，重新调整树的结构，调整结束

可能引起不平衡的情况

  • 在结点的左孩子的左子树上插入（LL）
  • 在结点的左孩子的右子树上插入（LR）
  • 在结点的右孩子的左子树上插入（RL）
  • 在结点的右孩子的右子树上插入（RR）
  • LL和RR镜像对称，LR和RL镜像对称

重新平衡的方法

LL问题

解决方法：单次旋转，对不平衡节点右旋(RightRotate)，将该方法称为LL单旋

  • 将失衡结点的左儿子作为根
  • 原来的根结点作为他的右子树
  • 原先的右儿子作为原先根的左儿子

该方法满足平衡调整的要求：

  • 保持了树的有序性
  • 保持了原先的高度
image-20240611134642639
RR问题

与LL问题为镜像对称

解决方法：单次旋转，对不平衡节点左旋(LeftRotate)，将该方法称为RR单旋

LR问题

解决方法：双旋转

  • 先对不平衡节点的左子节点进行RR单旋（LeftRotate，左旋）
  • 再对不平衡节点进行LL单旋（RightRotate，右旋）
image-20240611134815674
RL问题

解决方法：双旋转

  • 先对不平衡节点的右子节点进行LL单旋（RightRotate，右旋）
  • 再对不平衡节点进行RR单旋（LeftRotate，左旋）
总结
  • LL和RR
    • LL和RR的解决方案互为镜像对称
    • 两者都是单旋转解决，对不平衡节点本身做单旋转
    • 引起失衡的儿子作根节点
  • LR和RL
    • LR和RL的解决方案互为镜像对称
    • 两者都是双旋转，即先对引起失衡的子节点单旋转，再对不平衡节点本身单旋转
    • 最终结果是引起失衡的孙子作根节点
  • 所有情况的共性
    • 重构不会破坏有序性
    • 重构后树的高度保持不变，调整可以结束！

程序实现

私有的insert函数
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
template <class KEY, class OTHER>
void AvlTree<KEY, OTHER>::insert( const SET<KEY, OTHER> & x, AvlNode * & t )
{  
  if( t == NULL )              //在空树上插入
    t = new AvlNode( x, NULL, NULL);
  else if( x.key < t->data.key) {                          //在左子树上插入
    insert( x, t->left );
    if ( height( t->left ) - height( t->right ) == 2 )    //t失衡
    if( x.key < t->left->data.key ) LL( t ); else LR(t);
  }
  else if( x.key > t->data.key )  {                        //在右子树上插入
    insert( x, t->right );
  if( height( t->right ) - height( t->left ) == 2 )     //t失衡
    if( t->right->data.key < x.key ) RR(t); else RL(t);
  }
  //重新计算t的高度 
  t->height = max( height( t->left ) , height( t->right ) ) + 1;
}
LL单旋(右旋)
1
2
3
4
5
6
7
8
9
10
template <class KEY, class OTHER>
void AvlTree<KEY, OTHER>::LL( AvlNode * & t )
{
  AvlNode *t1 = t->left;       // 未来的树根
  t->left = t1->right;
  t1->right = t;
  t->height = max( height( t->left ),  height( t->right ) ) + 1;
  t1->height = max( height( t1->left ), height(t)) + 1;
  t = t1;//儿子做根
}
RR单旋（左旋）
1
2
3
4
5
6
7
8
9
10
template <class KEY, class OTHER>
void AvlTree<KEY, OTHER>::RR( AvlNode * & t )
{
  AvlNode *t1 = t->right;
  t->right = t1->left;
  t1->left = t;
  t->height = max( height( t->left ),  height( t->right ) ) + 1;
  t1->height = max( height( t1->right ), height(t)) + 1;
  t = t1;
}
LR和RL（双旋）
1
2
3
4
5
6
7
8
9
10
11
12
13
template <class KEY, class OTHER>
void AvlTree<KEY, OTHER>::LR( AvlNode * & t )
{
  RR( t->left );
  LL( t );
}
 
template <class KEY, class OTHER>
void AvlTree<KEY, OTHER>::RL( AvlNode * & t )
{
  LL( t->right );
  RR( t );
}

AVL树的删除

  • 首先在AVL树上删除结点x，删除结点的操作与二叉查找树一样
  • 然后调整平衡，调整平衡与插入类似

平衡调整的基本思路

  • 与插入操作一样， 失衡结点存在于被删结点到根结点的路径上。在删除了一个结点后，必须沿着到根结点的路径向上回溯，随时调整路径上的结点的平衡度。
  • 删除操作没有插入操作那么幸运。插入时，最多只需要调整一个结点。而删除时，我们无法保证子树在平衡调整后的高度不变。只有当某个结点的高度在删除前后保持不变，才无需继续调整。
  • 递归的删除函数有一个布尔型的返回值。当返回值为true时，调整停止。当返回值为false时，继续调整。

平衡调整的各种情况及方法

注意：

  • 此处讨论时假设删除发生在左子树
  • 删除发生在右子树的情况和发生在左子树的情况是对称的，处理方法也对称
  • 总体的情况个数是这边讨论的*2

技巧：

  • 重构时，可以将删除看成在另外的子树插入了一个元素，这样就可以套用插入时的平衡调整方法。
情况a
image-20240611135242770

没有失衡，高度没变，返回true

情况b
image-20240611135532725

没有失衡，高度变矮，返回false

情况c
image-20240611135829644
  • 发生了失衡，需要调整：对不平衡节点P进行RR旋转（单次LeftRotate，左旋），重新平衡
  • 高度变矮（h+1→hh+1\to h），返回false
情况d
image-20240611140247299
  • 发生了失衡，需要调整：对不平衡节点P进行RL旋转（先对引起失衡的子节点右旋，再对不平衡节点本身左旋），重新平衡
  • 高度变矮（h+1→hh+1\to h），返回false
情况e
image-20240611141043073
  • 发生了失衡，需要调整：对不平衡节点P进行RL旋转（先对引起失衡的子节点右旋，再对不平衡节点本身左旋）或RR旋转（单次LeftRotate，左旋），重新平衡
  • 高度不变（一直是h+1h+1），返回true

删除总结

  • 结点删除同二叉查找树。在删除了叶结点或只有一个孩子的结点后，子树变矮，返回false
  • 每次递归调用后，检查返回值。如果是true，直接返回true。否则分5*2=10种情况进行处理

程序实现

私有的remove函数
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
template <class KEY, class OTHER>
bool AvlTree<KEY, OTHER>::remove( const KEY & x, AvlNode * & t ) 
{   
  if( t == NULL )     return true;   //被删除结点不存在
  if (x == t->data.key) {                           // 删除根结点
    if ( t->left == NULL || t->right == NULL ) {   
      AvlNode *oldNode = t;
      t = ( t->left != NULL ) ? t->left : t->right;
      delete oldNode;
      return false;
    }
    else {   
      AvlNode *tmp = t->right;
      while(tmp->left != NULL) tmp = tmp->left; 
      t->data = tmp->data;
      if (remove(tmp->data.key, t->right)) return true;
      else return adjust(t, 1);//右子树高度降低，调整
    }
  }
  if( x < t->data.key )   {                          // 在左子树上删除
    if (remove( x, t->left )) return true;
    else return adjust(t, 0);//左子树高度降低，调整
  }
  else  {                                        // 在右子树上删除
    if (remove( x, t->right )) return true;
    else return adjust(t, 1); //右子树高度降低，调整
  }
  }
调整函数adjust
  • 进入调整函数，一定是某棵子树变矮了
  • 调整函数检查结点有没有失衡。如果失衡，则做相应的调整。
  • 函数的返回值是子树有没有变矮，变矮返回false，否则返回true
  • 函数的第一个参数是所要检查的结点的地址t。第二个参数是t的哪棵子树变矮了。0是左子树变矮，1 是右子树变矮
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
template <class KEY, class OTHER>
bool AvlTree<KEY, OTHER>::adjust(AvlNode * &t, int subTree)
{   
  if (subTree) {                           //  在右子树上删除，使右子树变矮
    if (height(t->left) - height(t->right) == 1 ) return true;            // 情况a
    if (height(t->right) == height(t->left)) { --t->height; return false;} // 情况b
		if (height(t->left->right) > height(t->left->left))                 // 情况d
    { 
      LR(t);
      return false;
    }
		LL(t);//情况c和e
		if (height(t->right) == height(t->left)) return false;
    else return true;
	}
	else {      // 在左子树删除
		if (height(t->right) - height(t->left) == 1 ) return true;             // 情况a
		if (height(t->right) == height(t->left)) { --t->height; return false;} // 情况b
		if (height(t->right->left) > height(t->right->right))               // 情况d
    {
      RL(t);
      return false;
    }
		RR(t); //情况c和e
		if (height(t->right) == height(t->left)) return false;
    else return true;
	}
}

散列表

散列法，也称哈希法。它不用比较的办法，而是直接根据所求结点的关键字值 KEY 找到这个结点。因此理论上，它的时间复杂性为 O(1)，优于任何其它的查找算法。

一些概念：

  • 负载因子：非空单元的比例

散列函数

D = H（key）

  • D为存储位置，key为关键值，H为散列函数
  • 散列函数的值域为[0,m-1]，m为散列表的长度
  • 两个问题：
    1. 设计散列函数
    2. 解决冲突（碰撞）
  • 散列函数的选择标准
    • 计算速度快
    • 散列地址尽可能均匀，使得冲突机会尽可能的少

除留余数法

H(key)= key MOD p 或 H(key)= key MOD p + c

  • 这里p为小于等于m的素数。如：m = 1024, 则 p = 1019 。
  • 最常用，余数总在0～p-1之间。
  • 选取p为素数的理由：较为均匀，碰撞较少

数字分析法

对关键字集合中的所有关键字，分析每一位上数字分布。取数字分布均匀的位作为地址的组成部分

平方取中法

  • 如果关键字中各位的分布都比较均匀，但关键字的值域比数组规模大，则可以将关键字平方后，取其结果的中间各位作为散列函数值。由于中间各位和每一位数字都有关系，因此均匀分布的可能性较大。

  • 比如：47314731 = 22，382，361。中间部分究竟要选取几位，依赖于散列表的单元总数。若散列表总共有100
    个单元，我们可以选取最中间的部分，即第4、5位，那么关键字值为4731的结点的散列地址可选为82。

冲突问题及解决方法

冲突解决的方法：

  • 闭散列表：利用本散列表中的空余单元
    • 线性探测法
    • 二次探测法
    • 再次散列法
  • 开散列表：将碰撞的结点存放在散列表外的各自的线性表中（链接法）

线性探测法

  • 当散列发生冲突时，探测下一个单元，直到发现一个空单元
  • 在一个规模为11的散列表中依次插入关键字17、12，23，60、29、38 ，采用的散列函数为H(key) = key MOD 11。
  • 负载因子小于0.5时，插入新元素一定能找到位置
  • 也就是说，如果提前知道元素数量，申请元素数量*2倍的空间即可
image-20240611165826612

  • 查找：

    1
    2
    3
    4
    5
    6
    7
    计算 addr = H(key)
    while (addr的内容非空 && 不等于要查找的键)
    	++addr
    	if (addr内容为空）
    		没有找到
    	else
    		找到

  • 删除：一般来讲，删除某一元素，先要找到该元素，然后把该空间的内容清空。但这样就给查找带来了问题，某些元素会查不到。解决的方案是采用迟删除，即不真正删除元素，而是做一个删除标记。

二次探测法

地址序列为H+12H+1^2, H+22H+2^2, H+32H+3^2​, ……

保证探测到的是新单元
  • 定理：如果采用二次探测法，并且表的大小是一个素数，那么，如果表至少有一半是空的（负载因子<0.5），新的元素总能被插入。而且，在插入过程中，没有一个单元被探测两次。
散列表扩展
  • 如果负载因子>0.5，需将数组扩大一倍
  • 不能把原数组的内容复制到新数组的前半部分，需要重新计算每一元素的散列值，称为重新散列

再次散列法

  • 采用第二个散列函数 H1(x),H1(x)+H2(x), H1(x)+2*H2(x),……
  • H2(x)的选择是非常重要的。建议采用H2(x) = R - (x mod R)，其中R是小于表长的一个素数

闭散列表的共性

  • 都需要迟删除！
  • 不论用什么方法，闭散列表在处理冲突问题时都无法完全避免聚集！！！

开散列表

将碰撞的结点存放在散列表外的各自的线性表中（链接法）

链地址法
开散列表的实现
  • 开散列表是将所有散列到同一地址的元素链成一个单链表，于是需要定义了一个单链表中的结点类。
  • 采用不带头结点的单链表散列表保存在一个数组中，数组的每个元素是一个指针，指向对应的单链表的首地址。

代码实现

闭散列表的实现

  • 散列表必须支持的三个操作：查找、插入、删除。
  • 闭散列表是用一个数组实现，数组的大小是由用户定义散列表时指定
  • 由于闭散列表中的删除是用迟删除的方法实现的，为此每个数组元素除了要保存对应的数据元素之外还必须保存一个数组元素的状态（空/正常存储/已删除）。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
template <class KEY, class OTHER>
class closeHashTable:public dynamicSearchTable<KEY, OTHER> {
  private:
      struct node { //散列表的结点类
          SET <KEY, OTHER>  data;
		  int state;  //0 -- empty   1 -- active   2 -- deleted
		  node() {state = 0;}
	  };
      node *array;
      int  size;
      int (*key)(const KEY &x);//哈希函数
      static int defaultKey(const int &x) {return x;} 
  public: 
     closeHashTable(int length = 101, int (*f)(const KEY &x) = defaultKey) ;
     ~closeHashTable() {delete [] array;}
     SET<KEY, OTHER> *find(const KEY &x) const;
      void insert(const SET<KEY, OTHER> &x);
      void remove(const KEY &x) ;
};
构造函数
1
2
3
4
5
6
7
8
9
template < class KEY, class OTHER >
closeHashTable<KEY, OTHER>:: 
closeHashTable
            (int length, int (*f)(const KEY  &x) )
{
	size = length;
	array = new node[size];
	key = f;    //哈希函数为f
}
insert函数的实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
template <class KEY, class OTHER>
void closeHashTable<KEY, OTHER>::insert(const SET<KEY, OTHER> &x)
{
	   int initPos, pos ;
	
	   initPos = pos = key(x.key) % size;  //%size保护作用，避免越界
	   do {  
              if (array[pos].state != 1) {       // 0或2，找到空单元
                   array[pos].data = x; 
                   array[pos].state = 1; 
                   return;
              }
	       pos = (pos+1) % size;
        } while (pos != initPos);
}
remove函数的实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
template <class KEY, class OTHER>
void closeHashTable<KEY, OTHER>::remove(const KEY &x) 
{
	   int initPos, pos ;
 
	   initPos = pos = key(x) % size;
       do {
            if (array[pos].state == 0) return;  //没找到
 	        if (array[pos].state == 1 && array[pos].data.key == x) {  // 找到，删除
		      array[pos].state = 2;
		      return;
	        }
	        pos = (pos+1) % size;  //没找到，需要往后找
       } while (pos != initPos);
}
find函数的实现
1
2
3
4
5
6
7
8
9
10
11
12
13
template <class KEY, class OTHER>
SET<KEY, OTHER> *closeHashTable<KEY, OTHER>::find(const KEY &x) const
{
 	    int initPos, pos ;
 
	    initPos = pos = key(x) % size;
         do {
              if (array[pos].state == 0) return NULL;     // 没有找到
	          if (array[pos].state == 1 && array[pos].data.key == x)    // 找到
                   return (SET<KEY,OTHER> *)&array[pos];
	           pos = (pos+1) % size;
          } while (pos != initPos);
}

开散列表的实现

0%